001: /*
002: * Copyright (c) 1998 - 2005 Versant Corporation
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * Versant Corporation - initial API and implementation
010: */
011: package com.versant.core.server;
012:
013: import com.versant.core.common.OID;
014: import com.versant.core.common.State;
015: import com.versant.core.metadata.ModelMetaData;
016: import com.versant.core.util.IntArray;
017:
018: import javax.jdo.JDOFatalUserException; //only appears in throws clause, to discuss, whether useful there at all
019: import java.util.Date;
020:
021: /**
022: * This class does a full topological sort of the graph and must be used for
023: * any graph containing new instances using post-insert key generators.
024: *
025: * @see PersistGraph
026: */
027: public final class PersistGraphFullSort extends PersistGraph {
028:
029: private int[] oidLevels;
030: private int[] oidDepth;
031:
032: public PersistGraphFullSort(ModelMetaData jmd, int maxSize) {
033: super (jmd, maxSize);
034: oidDepth = new int[maxSize];
035: }
036:
037: /**
038: * Empty the graph so it can be reused.
039: */
040: public void clear() {
041: super .clear();
042: oidLevels = null;
043: }
044:
045: /**
046: * Sort the graph so that the nodes that do not depend on (reference) any
047: * other nodes are first, then those that depend on them and so on. This
048: * is the correct ordering for persisting a graph with new instances
049: * using post-insert key generators.
050: *
051: * @throws javax.jdo.JDOFatalUserException
052: * if a cycle is detected
053: */
054: public void sort() {
055: int size = this .size;
056: int[] oidEdgeStart = new int[size];
057: int[] oidEdgeCount = new int[size];
058: boolean[] rootVertex = new boolean[size];
059: boolean[] isVisited = new boolean[size];
060: boolean[] isInserted = new boolean[size];
061:
062: for (int i = 0; i < size; i++) {
063: rootVertex[i] = true;
064: isVisited[i] = false;
065: isInserted[i] = false;
066: }
067:
068: int[] oidEdges = findEdges(size, oidEdgeStart, oidEdgeCount,
069: rootVertex);
070:
071: for (int i = 0; i < size; i++) {
072: if (rootVertex[i]) {
073: topsort(i, oidEdges, oidEdgeStart, oidEdgeCount,
074: isVisited, isInserted);
075: }
076: }
077:
078: super .sort();
079:
080: oidLevels = new int[oidDepth[size - 1] + 1];
081: for (int i = 0; i < oidLevels.length; oidLevels[i++] = 0)
082: ;
083: oidLevels[0] = 0;
084:
085: for (int i = 0, j = 0; i < size; i++) {
086: if (j != oidDepth[i])
087: oidLevels[++j] = i;
088: }
089:
090: oidIndexMap.clear(); // no longer valid
091: }
092:
093: /**
094: * Do a full topological sort of the graph.
095: *
096: * @throws javax.jdo.JDOFatalUserException
097: * if there are cycles
098: */
099: private int topsort(int index, int[] oidEdges, int[] oidEdgeStart,
100: int[] oidEdgeCount, boolean[] isVisited,
101: boolean[] isInserted) throws JDOFatalUserException {
102: if (isVisited[index])
103: return 0;
104: int edgeCount = oidEdgeCount[index];
105: if (edgeCount == 0) { // aleaf
106: if (!isInserted[index]) {
107: oidDepth[index] = 0;
108: isInserted[index] = true;
109: }
110: return 0;
111: }
112: isVisited[index] = true; // push index on stack of current path
113: int depth = 0;
114: int t = 0;
115: while (edgeCount > 0) {
116: t = topsort(oidEdges[oidEdgeStart[index] + (--edgeCount)],
117: oidEdges, oidEdgeStart, oidEdgeCount, isVisited,
118: isInserted);
119: depth = t > depth ? t : depth;
120: }
121: depth = depth + 1; //Depth = max( depth of children) + 1
122: if (!isInserted[index]) {
123: oidDepth[index] = depth;
124: isInserted[index] = true;
125: }
126: isVisited[index] = false; // pop out index from the stack
127: return depth;
128: }
129:
130: /**
131: * Find all the edges in the graph. This also updates autoSet fields.
132: */
133: private int[] findEdges(int size, int[] oidEdgeStart,
134: int[] oidEdgeCount, boolean[] rootVertex) {
135: IntArray edges = new IntArray(size);
136: int start;
137: int fin;
138: Date now = new Date();
139: for (int i = 0; i < size; i++) {
140: start = oidEdgeStart[i] = edges.size();
141: State ns = newStates[i];
142: OID oid = oids[i];
143: if (oid.isNew()) {
144: ns.updateAutoSetFieldsCreated(now);
145: } else {
146: ns.updateAutoSetFieldsModified(now, oldStates[i]);
147: }
148: ns.findDirectEdges(this , edges);
149: fin = edges.size();
150: oidEdgeCount[i] = fin - start;
151: for (int j = start; j < fin; j++) {
152: rootVertex[edges.get(j)] = false;
153: }
154: }
155: return edges.toArray();
156: }
157:
158: /**
159: * Compare graph entries at and a and b. Return 0 if equal, less than 0
160: * if a is less than b or greater than 0 if a is greater than b. This
161: * orders entries by depth, by class index, by new objects first,
162: * by field numbers.
163: */
164: protected int compare(int a, int b) {
165: int diff = oidDepth[a] - oidDepth[b];
166: if (diff != 0)
167: return diff;
168: return super .compare(a, b);
169: }
170:
171: /**
172: * Swap entries.
173: */
174: protected void swap(int index1, int index2) {
175: super .swap(index1, index2);
176: int tempDepth = oidDepth[index1];
177: oidDepth[index1] = oidDepth[index2];
178: oidDepth[index2] = tempDepth;
179: }
180: }
|