KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > versant > core > jdbc > metadata > JdbcClassReferenceGraph


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.jdbc.metadata;
13
14 import com.versant.core.metadata.ClassMetaData;
15 import com.versant.core.metadata.FieldMetaData;
16
17 import com.versant.core.common.Debug;
18 import com.versant.core.common.BindingSupportImpl;
19
20 import java.util.*;
21
22 /**
23  * This does a topological sort of jdbc tables via its ClassMetaData. This
24  * ordering is necassary to prevent tripping relation constraints.
25  * This process also checks it the table is involved in circular references.
26  * <p/>
27  * References that lead to a cyclic depenency is ignored when the dependency
28  * ordering is done.
29  *
30  * A class hierarchy if viewed as a node. Firstly all the references from the
31  * node is collected. This is done by starting at the top most class and collecting all the
32  * references. Once this is done a indirect ref graph is build up from the direct reference graph.
33  * This indirect reference is build up by recursivly adding the references of
34  * the direct references until we reach the end or the original node is reached again.
35  * The nodes are now sorted by comparing there indirect reference graph.
36  * NodeA has NodeB as indirect reference:
37  * If NodeB has NodeA as indirect reference then they are equil.
38  * Else NodeA is dependent on NodeB.
39  *
40  * Create a graph of non-cyclic refs and then start adding weight at the leaf
41  * nodes working back.
42  *
43  * @see com.versant.core.metadata.ClassMetaData#referenceGraphIndex
44  */
45 public final class JdbcClassReferenceGraph implements Comparator {
46     private HashMap cmdToRefMap = new HashMap();
47     private HashMap cmdToIndirectMap = new HashMap();
48     private HashMap cmdToNonCyclicMap = new HashMap();
49
50     public int compare(Object JavaDoc o1, Object JavaDoc o2) {
51         ClassMetaData cmd1 = ((ClassMetaData) o1).top;
52         ClassMetaData cmd2 = ((ClassMetaData) o2).top;
53
54         if (cmd1.weight != cmd2.weight) {
55             return cmd2.weight - cmd1.weight;
56         } else {
57             return cmd2.qname.compareTo(cmd1.qname);
58         }
59     }
60
61     private final ClassMetaData[] classes;
62
63     /**
64      * Extract out only the topmost classes from a.
65      */
66     public JdbcClassReferenceGraph(ClassMetaData[] a) {
67         int n = a.length;
68         classes = new ClassMetaData[n];
69         for (int i = 0; i < n; i++) {
70             classes[i] = a[i];
71             classes[i].weight = 0;
72         }
73     }
74
75     private void addRefs(ClassMetaData cmd, HashSet set) {
76         FieldMetaData[] fields = cmd.fields;
77         if (fields == null) {
78             return;
79         }
80         for (int i = 0; i < fields.length; i++) {
81             FieldMetaData field = fields[i];
82             if (field.isDirectRef()) {
83                 set.add(field.typeMetaData.top);
84             }
85         }
86     }
87
88     private void addRefsRecursive(ClassMetaData cmd, HashSet set) {
89         addRefs(cmd, set);
90         ClassMetaData[] pcSubs = cmd.pcSubclasses;
91         if (pcSubs == null) return;
92         for (int i = 0; i < pcSubs.length; i++) {
93             addRefsRecursive(pcSubs[i], set);
94         }
95     }
96
97     private HashSet getDirectRefs(ClassMetaData cmd, HashMap refMap) {
98         return (HashSet) refMap.get(cmd.top);
99     }
100
101     private HashSet getIndirectRefs(ClassMetaData cmd, HashMap indirectRefMap) {
102         return (HashSet) indirectRefMap.get(cmd.top);
103     }
104
105     private void buildIndirectGraph() {
106         for (int i = 0; i < classes.length; i++) {
107             ClassMetaData cmd = classes[i];
108             if (cmd.pcSuperClass == null) {
109                 HashSet indirectRefSet = new HashSet();
110                 cmdToIndirectMap.put(cmd, indirectRefSet);
111                 buildIndirectGraph(cmd, cmd, indirectRefSet, cmdToRefMap);
112             }
113         }
114     }
115
116     private void buildIndirectGraph(ClassMetaData rootCmd, ClassMetaData cmd, Set indirectRefs, Map directRefMap) {
117         Set directRefs = (Set) directRefMap.get(cmd);
118         for (Iterator iterator = directRefs.iterator(); iterator.hasNext();) {
119             ClassMetaData dRef = (ClassMetaData) iterator.next();
120             if (dRef != dRef.top) BindingSupportImpl.getInstance().internal("Should be top most class");
121             if (dRef == rootCmd) continue;
122             if (indirectRefs.contains(dRef)) continue;
123             indirectRefs.add(dRef);
124             buildIndirectGraph(rootCmd, dRef, indirectRefs, directRefMap);
125         }
126     }
127
128     private int calculateWieght(ClassMetaData cmd) {
129         if (Debug.DEBUG) {
130             if (cmd.top != cmd) throw BindingSupportImpl.getInstance().internal(
131                     "Must be top of hierarchy");
132         }
133         if (cmd.weight != 0) {
134             //already done
135 return cmd.weight;
136         }
137
138         HashSet noncircularRefs = (HashSet) cmdToNonCyclicMap.get(cmd);
139         int maxWeight = 0;
140         for (Iterator iterator = noncircularRefs.iterator(); iterator.hasNext();) {
141             ClassMetaData classMetaData = (ClassMetaData) iterator.next();
142             int refWeight = calculateWieght(classMetaData);
143             if (refWeight > maxWeight) maxWeight = refWeight;
144         }
145         return cmd.weight = maxWeight + 1;
146     }
147
148     /**
149      * Sort the graph and set the referenceGraphIndex and referenceGraphCycle
150      * fields on each class.
151      *
152      * @see com.versant.core.metadata.ClassMetaData#referenceGraphIndex
153      * @see com.versant.core.metadata.ClassMetaData#referenceGraphCycle
154      */
155     public void sort() {
156         //build the direct refs graph
157 buildDirectRefGraph();
158
159         //build the indirect ref graph
160 buildIndirectGraph();
161
162         //build the non-cyclic ref graph
163 buildNonCyclicRefGraph();
164
165         //calculate weights for the nodes
166 calculateWieght();
167
168         List classList = Arrays.asList(this.classes);
169         Collections.sort(classList, this);
170         for (int i = 0; i < classList.size(); i++) {
171             ((ClassMetaData)classList.get(i)).setReferenceGraphIndex(i);
172         }
173     }
174
175     private void calculateWieght() {
176         for (int i = 0; i < classes.length; i++) {
177             ClassMetaData cmd = classes[i];
178             if (cmd.pcSuperClass == null) {
179                 calculateWieght(cmd);
180             }
181         }
182     }
183
184     private void buildNonCyclicRefGraph() {
185         for (int i = 0; i < classes.length; i++) {
186             ClassMetaData cmd = classes[i];
187             if (cmd.pcSuperClass == null) {
188                 HashSet indirectRefSet = (HashSet) cmdToIndirectMap.get(cmd);
189                 HashSet nonCircularRefs = new HashSet();
190                 cmdToNonCyclicMap.put(cmd, nonCircularRefs);
191
192                 for (Iterator iterator = indirectRefSet.iterator(); iterator.hasNext();) {
193                     ClassMetaData refNode = (ClassMetaData) iterator.next();
194                     if (!isCircularRef(cmd, refNode)) {
195                         nonCircularRefs.add(refNode);
196                     }
197                 }
198             }
199         }
200     }
201
202     private void buildDirectRefGraph() {
203         for (int i = 0; i < classes.length; i++) {
204             ClassMetaData cmd = classes[i];
205             if (cmd.pcSuperClass == null) {
206                 HashSet refSet = new HashSet();
207                 cmdToRefMap.put(cmd, refSet);
208                 addRefsRecursive(cmd, refSet);
209             }
210         }
211     }
212
213     public boolean isCircularRef(ClassMetaData cmd1, ClassMetaData cmd2) {
214         cmd1 = cmd1.top;
215         cmd2 = cmd2.top;
216         return (getIndirectRefs(cmd1, cmdToIndirectMap).contains(cmd2) && getIndirectRefs(cmd2, cmdToIndirectMap).contains(cmd1));
217     }
218
219     public void releaseMem() {
220         cmdToIndirectMap = null;
221         cmdToNonCyclicMap = null;
222         cmdToRefMap = null;
223     }
224 }
225
Popular Tags