KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > versant > core > metadata > ClassReferenceGraph


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.metadata;
13
14 import com.versant.core.common.SortableBase;
15 import com.versant.core.util.IntArray;
16
17 import javax.jdo.JDOFatalUserException;
18
19 /**
20  * This does a topological sort of a graph of ClassMetaData using direct
21  * references between the classes as edges. Each class has its
22  * referenceClassDepth field filled by sort. Cycles are detected and all
23  * classes involved in a cycle have their referenceGraphCycle flags set. This
24  * is used to not generate constraints for these fields. The
25  * referenceClassDepth is used to order deletes to avoid tripping
26  * constraints.<p>
27  *
28  * Only top level classes are actually sorted and the results are applied to
29  * all subclasses. This is because heirachies are mapped into the table for
30  * the base class. References in subclasses are considered as edges of the
31  * base class in the graph.<p>
32  *
33  * @see ClassMetaData#referenceGraphIndex
34  * @see ClassMetaData#referenceGraphCycle
35  */
36 public final class ClassReferenceGraph extends SortableBase {
37
38     /**
39      * Fill in the referenceGraphIndex and referenceGraphCycle fields for all
40      * classes in jmd.
41      * @see ClassMetaData#referenceGraphIndex
42      * @see ClassMetaData#referenceGraphCycle
43      */
44     public static void sort(ClassMetaData[] classes) {
45         new ClassReferenceGraph(classes).sort();
46     }
47
48     private final ClassMetaData[] classes; // top level only
49 private final int[] depth;
50     private final int[] edgeStart;
51     private final int[] edgeCount;
52
53     /**
54      * Extract out only the topmost classes from a.
55      */
56     private ClassReferenceGraph(ClassMetaData[] a) {
57         int n = a.length;
58         classes = new ClassMetaData[n];
59         for (int i = 0; i < n; i++) {
60             ClassMetaData cmd = a[i];
61             if (cmd.pcSuperMetaData == null) classes[size++] = cmd;
62         }
63         depth = new int[size];
64         edgeStart = new int[size];
65         edgeCount = new int[size];
66     }
67
68     /**
69      * Compare entries at and a and b. Return 0 if equal, less than 0
70      * if a is less than b or greater than 0 if a is greater than b.
71      */
72     protected int compare(int a, int b) {
73         int diff = depth[b] - depth[a];
74         if (diff != 0) return diff;
75         return classes[a].index - classes[b].index;
76     }
77
78     /**
79      * Swap entries.
80      */
81     protected void swap(int i1, int i2) {
82         int t = depth[i1];
83         depth[i1] = depth[i2];
84         depth[i2] = t;
85         ClassMetaData cmd = classes[i1];
86         classes[i1] = classes[i2];
87         classes[i2] = cmd;
88     }
89
90     /**
91      * Sort the graph and set the referenceGraphIndex and referenceGraphCycle
92      * fields on each class.
93      * @see ClassMetaData#referenceGraphIndex
94      * @see ClassMetaData#referenceGraphCycle
95      */
96     public void sort() {
97         for (int i = size - 1; i >= 0; i--) {
98             classes[i].setReferenceGraphCycle(false);
99         }
100         int[] visited = new int[size];
101         int[] edges = findEdges();
102 // if (Debug.DEBUG) dumpEdges(edges);
103 for (int i = 0; i < size; i++) {
104             topsort(i, edges, visited, 0);
105         }
106         super.sort();
107         for (int i = size - 1; i >= 0; i--) {
108             classes[i].setReferenceGraphIndex(i);
109         }
110 // if (Debug.DEBUG) dumpGraph();
111 }
112
113     private void dumpGraph() {
114         for (int i = 0; i < size; i++) {
115             ClassMetaData cmd = classes[i];
116             System.out.println("[" + i + "] = " + cmd.qname +
117                 " depth " + depth[i] +
118                 " 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 JavaDoc s = new StringBuffer JavaDoc();
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) classes[i].setReferenceGraphCycle(true);
146             }
147             return 0;
148         }
149         int ec = edgeCount[index];
150         if (ec == 0) return 0; // a leaf
151 visited[index] = ++pathlen; // push index on stack of current path
152 int d = 0;
153         int t = 0;
154         while (ec > 0) {
155             t = topsort(edges[edgeStart[index] + (--ec)],
156                     edges, visited, pathlen);
157             d = t > d ? t : d;
158         }
159         d = d + 1; //Depth = max( depth of children) + 1
160 if (depth[index] < d) depth[index] = d;
161         visited[index] = 0; // pop out index from the stack
162 return d;
163     }
164
165     /**
166      * Find all the edges in the graph.
167      */
168     private int[] findEdges() {
169         IntArray edges = new IntArray(size);
170         for (int i = 0; i < size; i++) {
171             int start = edgeStart[i] = edges.size();
172             findEdges(classes[i], edges);
173             edgeCount[i] = edges.size() - start;
174         }
175         return edges.toArray();
176     }
177
178     /**
179      * Find all direct references from cmd and its subclasses to other
180      * classes and add them to edges.
181      */
182     private void findEdges(ClassMetaData cmd, IntArray edges) {
183         FieldMetaData[] a = cmd.fields;
184         for (int j = a.length - 1; j >= 0; j--) {
185             FieldMetaData f = a[j];
186             if (!f.isDirectRef()) continue;
187             edges.add(indexOf(f.typeMetaData));
188         }
189         if (cmd.pcSubclasses != null) {
190             for (int i = cmd.pcSubclasses.length - 1; i >= 0; i--) {
191                 findEdges(cmd.pcSubclasses[i], edges);
192             }
193         }
194     }
195
196     private int indexOf(ClassMetaData cmd) {
197         for (; cmd.pcSuperMetaData != null; ) cmd = cmd.pcSuperMetaData;
198         for (int i = size - 1; i >= 0; i--) {
199             if (classes[i] == cmd) return i;
200         }
201         return -1;
202     }
203
204 }
205
Popular Tags