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.metadata;
012:
013: import com.versant.core.common.SortableBase;
014: import com.versant.core.util.IntArray;
015:
016: import javax.jdo.JDOFatalUserException;
017:
018: /**
019: * This does a topological sort of a graph of ClassMetaData using direct
020: * references between the classes as edges. Each class has its
021: * referenceClassDepth field filled by sort. Cycles are detected and all
022: * classes involved in a cycle have their referenceGraphCycle flags set. This
023: * is used to not generate constraints for these fields. The
024: * referenceClassDepth is used to order deletes to avoid tripping
025: * constraints.<p>
026: *
027: * Only top level classes are actually sorted and the results are applied to
028: * all subclasses. This is because heirachies are mapped into the table for
029: * the base class. References in subclasses are considered as edges of the
030: * base class in the graph.<p>
031: *
032: * @see ClassMetaData#referenceGraphIndex
033: * @see ClassMetaData#referenceGraphCycle
034: */
035: public final class ClassReferenceGraph extends SortableBase {
036:
037: /**
038: * Fill in the referenceGraphIndex and referenceGraphCycle fields for all
039: * classes in jmd.
040: * @see ClassMetaData#referenceGraphIndex
041: * @see ClassMetaData#referenceGraphCycle
042: */
043: public static void sort(ClassMetaData[] classes) {
044: new ClassReferenceGraph(classes).sort();
045: }
046:
047: private final ClassMetaData[] classes; // top level only
048: private final int[] depth;
049: private final int[] edgeStart;
050: private final int[] edgeCount;
051:
052: /**
053: * Extract out only the topmost classes from a.
054: */
055: private ClassReferenceGraph(ClassMetaData[] a) {
056: int n = a.length;
057: classes = new ClassMetaData[n];
058: for (int i = 0; i < n; i++) {
059: ClassMetaData cmd = a[i];
060: if (cmd.pcSuperMetaData == null)
061: classes[size++] = cmd;
062: }
063: depth = new int[size];
064: edgeStart = new int[size];
065: edgeCount = new int[size];
066: }
067:
068: /**
069: * Compare entries at and a and b. Return 0 if equal, less than 0
070: * if a is less than b or greater than 0 if a is greater than b.
071: */
072: protected int compare(int a, int b) {
073: int diff = depth[b] - depth[a];
074: if (diff != 0)
075: return diff;
076: return classes[a].index - classes[b].index;
077: }
078:
079: /**
080: * Swap entries.
081: */
082: protected void swap(int i1, int i2) {
083: int t = depth[i1];
084: depth[i1] = depth[i2];
085: depth[i2] = t;
086: ClassMetaData cmd = classes[i1];
087: classes[i1] = classes[i2];
088: classes[i2] = cmd;
089: }
090:
091: /**
092: * Sort the graph and set the referenceGraphIndex and referenceGraphCycle
093: * fields on each class.
094: * @see ClassMetaData#referenceGraphIndex
095: * @see ClassMetaData#referenceGraphCycle
096: */
097: public void sort() {
098: for (int i = size - 1; i >= 0; i--) {
099: classes[i].setReferenceGraphCycle(false);
100: }
101: int[] visited = new int[size];
102: int[] edges = findEdges();
103: // if (Debug.DEBUG) dumpEdges(edges);
104: for (int i = 0; i < size; i++) {
105: topsort(i, edges, visited, 0);
106: }
107: super .sort();
108: for (int i = size - 1; i >= 0; i--) {
109: classes[i].setReferenceGraphIndex(i);
110: }
111: // if (Debug.DEBUG) dumpGraph();
112: }
113:
114: private void dumpGraph() {
115: for (int i = 0; i < size; i++) {
116: ClassMetaData cmd = classes[i];
117: System.out.println("[" + i + "] = " + cmd.qname + " depth "
118: + depth[i] + " cycle " + cmd.referenceGraphCycle);
119: }
120: System.out.println("---");
121: }
122:
123: private void dumpEdges(int[] edges) {
124: for (int i = 0; i < size; i++) {
125: StringBuffer s = new StringBuffer();
126: s.append("[" + i + "] = " + classes[i].qname + " edges");
127: for (int j = 0; j < edgeCount[i]; j++) {
128: s.append(' ');
129: s.append(edges[edgeStart[i] + j]);
130: }
131: System.out.println(s);
132: }
133: System.out.println("---");
134: }
135:
136: /**
137: * Do a topological sort of the graph.
138: */
139: private int topsort(int index, int[] edges, int[] visited,
140: int pathlen) throws JDOFatalUserException {
141: if (visited[index] > 0) {
142: // us and all classes visited after our first visit form a cycle
143: int v = visited[index];
144: for (int i = size - 1; i >= 0; i--) {
145: if (visited[i] >= v)
146: classes[i].setReferenceGraphCycle(true);
147: }
148: return 0;
149: }
150: int ec = edgeCount[index];
151: if (ec == 0)
152: return 0; // a leaf
153: visited[index] = ++pathlen; // push index on stack of current path
154: int d = 0;
155: int t = 0;
156: while (ec > 0) {
157: t = topsort(edges[edgeStart[index] + (--ec)], edges,
158: visited, pathlen);
159: d = t > d ? t : d;
160: }
161: d = d + 1; //Depth = max( depth of children) + 1
162: if (depth[index] < d)
163: depth[index] = d;
164: visited[index] = 0; // pop out index from the stack
165: return d;
166: }
167:
168: /**
169: * Find all the edges in the graph.
170: */
171: private int[] findEdges() {
172: IntArray edges = new IntArray(size);
173: for (int i = 0; i < size; i++) {
174: int start = edgeStart[i] = edges.size();
175: findEdges(classes[i], edges);
176: edgeCount[i] = edges.size() - start;
177: }
178: return edges.toArray();
179: }
180:
181: /**
182: * Find all direct references from cmd and its subclasses to other
183: * classes and add them to edges.
184: */
185: private void findEdges(ClassMetaData cmd, IntArray edges) {
186: FieldMetaData[] a = cmd.fields;
187: for (int j = a.length - 1; j >= 0; j--) {
188: FieldMetaData f = a[j];
189: if (!f.isDirectRef())
190: continue;
191: edges.add(indexOf(f.typeMetaData));
192: }
193: if (cmd.pcSubclasses != null) {
194: for (int i = cmd.pcSubclasses.length - 1; i >= 0; i--) {
195: findEdges(cmd.pcSubclasses[i], edges);
196: }
197: }
198: }
199:
200: private int indexOf(ClassMetaData cmd) {
201: for (; cmd.pcSuperMetaData != null;)
202: cmd = cmd.pcSuperMetaData;
203: for (int i = size - 1; i >= 0; i--) {
204: if (classes[i] == cmd)
205: return i;
206: }
207: return -1;
208: }
209:
210: }
|