KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > versant > core > server > PersistGraphFullSort


1
2 /*
3  * Copyright (c) 1998 - 2005 Versant Corporation
4  * All rights reserved. This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License v1.0
6  * which accompanies this distribution, and is available at
7  * http://www.eclipse.org/legal/epl-v10.html
8  *
9  * Contributors:
10  * Versant Corporation - initial API and implementation
11  */
12 package com.versant.core.server;
13
14 import com.versant.core.common.OID;
15 import com.versant.core.common.State;
16 import com.versant.core.metadata.ModelMetaData;
17 import com.versant.core.util.IntArray;
18
19 import javax.jdo.JDOFatalUserException; //only appears in throws clause, to discuss, whether useful there at all
20 import java.util.Date JavaDoc;
21
22 /**
23  * This class does a full topological sort of the graph and must be used for
24  * any graph containing new instances using post-insert key generators.
25  *
26  * @see PersistGraph
27  */
28 public final class PersistGraphFullSort extends PersistGraph {
29
30     private int[] oidLevels;
31     private int[] oidDepth;
32
33     public PersistGraphFullSort(ModelMetaData jmd, int maxSize) {
34         super(jmd, maxSize);
35         oidDepth = new int[maxSize];
36     }
37
38     /**
39      * Empty the graph so it can be reused.
40      */
41     public void clear() {
42         super.clear();
43         oidLevels = null;
44     }
45
46     /**
47      * Sort the graph so that the nodes that do not depend on (reference) any
48      * other nodes are first, then those that depend on them and so on. This
49      * is the correct ordering for persisting a graph with new instances
50      * using post-insert key generators.
51      *
52      * @throws javax.jdo.JDOFatalUserException
53      * if a cycle is detected
54      */
55     public void sort() {
56         int size = this.size;
57         int[] oidEdgeStart = new int[size];
58         int[] oidEdgeCount = new int[size];
59         boolean[] rootVertex = new boolean[size];
60         boolean[] isVisited = new boolean[size];
61         boolean[] isInserted = new boolean[size];
62
63         for (int i = 0; i < size; i++) {
64             rootVertex[i] = true;
65             isVisited[i] = false;
66             isInserted[i] = false;
67         }
68
69         int[] oidEdges = findEdges(size, oidEdgeStart, oidEdgeCount,
70                 rootVertex);
71
72         for (int i = 0; i < size; i++) {
73             if (rootVertex[i]) {
74                 topsort(i, oidEdges, oidEdgeStart, oidEdgeCount,
75                         isVisited, isInserted);
76             }
77         }
78
79         super.sort();
80
81         oidLevels = new int[oidDepth[size - 1] + 1];
82         for (int i = 0; i < oidLevels.length; oidLevels[i++] = 0) ;
83         oidLevels[0] = 0;
84
85         for (int i = 0, j = 0; i < size; i++) {
86             if (j != oidDepth[i]) oidLevels[++j] = i;
87         }
88
89         oidIndexMap.clear(); // no longer valid
90 }
91
92     /**
93      * Do a full topological sort of the graph.
94      *
95      * @throws javax.jdo.JDOFatalUserException
96      * if there are cycles
97      */
98     private int topsort(int index, int[] oidEdges, int[] oidEdgeStart,
99             int[] oidEdgeCount, boolean[] isVisited,
100             boolean[] isInserted) throws JDOFatalUserException {
101         if (isVisited[index]) return 0;
102         int edgeCount = oidEdgeCount[index];
103         if (edgeCount == 0) { // aleaf
104 if (!isInserted[index]) {
105                 oidDepth[index] = 0;
106                 isInserted[index] = true;
107             }
108             return 0;
109         }
110         isVisited[index] = true; // push index on stack of current path
111 int depth = 0;
112         int t = 0;
113         while (edgeCount > 0) {
114             t = topsort(oidEdges[oidEdgeStart[index] + (--edgeCount)],
115                     oidEdges, oidEdgeStart, oidEdgeCount,
116                     isVisited, isInserted);
117             depth = t > depth ? t : depth;
118         }
119         depth = depth + 1; //Depth = max( depth of children) + 1
120 if (!isInserted[index]) {
121             oidDepth[index] = depth;
122             isInserted[index] = true;
123         }
124         isVisited[index] = false; // pop out index from the stack
125 return depth;
126     }
127
128     /**
129      * Find all the edges in the graph. This also updates autoSet fields.
130      */
131     private int[] findEdges(int size, int[] oidEdgeStart,
132             int[] oidEdgeCount, boolean[] rootVertex) {
133         IntArray edges = new IntArray(size);
134         int start;
135         int fin;
136         Date JavaDoc now = new Date JavaDoc();
137         for (int i = 0; i < size; i++) {
138             start = oidEdgeStart[i] = edges.size();
139             State ns = newStates[i];
140             OID oid = oids[i];
141             if (oid.isNew()) {
142                 ns.updateAutoSetFieldsCreated(now);
143             } else {
144                 ns.updateAutoSetFieldsModified(now, oldStates[i]);
145             }
146             ns.findDirectEdges(this, edges);
147             fin = edges.size();
148             oidEdgeCount[i] = fin - start;
149             for (int j = start; j < fin; j++) {
150                 rootVertex[edges.get(j)] = false;
151             }
152         }
153         return edges.toArray();
154     }
155
156     /**
157      * Compare graph entries at and a and b. Return 0 if equal, less than 0
158      * if a is less than b or greater than 0 if a is greater than b. This
159      * orders entries by depth, by class index, by new objects first,
160      * by field numbers.
161      */
162     protected int compare(int a, int b) {
163         int diff = oidDepth[a] - oidDepth[b];
164         if (diff != 0) return diff;
165         return super.compare(a, b);
166     }
167
168     /**
169      * Swap entries.
170      */
171     protected void swap(int index1, int index2) {
172         super.swap(index1, index2);
173         int tempDepth = oidDepth[index1];
174         oidDepth[index1] = oidDepth[index2];
175         oidDepth[index2] = tempDepth;
176     }
177 }
178
Popular Tags