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.jdbc.metadata;
012:
013: import com.versant.core.metadata.ClassMetaData;
014: import com.versant.core.metadata.FieldMetaData;
015:
016: import com.versant.core.common.Debug;
017: import com.versant.core.common.BindingSupportImpl;
018:
019: import java.util.*;
020:
021: /**
022: * This does a topological sort of jdbc tables via its ClassMetaData. This
023: * ordering is necassary to prevent tripping relation constraints.
024: * This process also checks it the table is involved in circular references.
025: * <p/>
026: * References that lead to a cyclic depenency is ignored when the dependency
027: * ordering is done.
028: *
029: * A class hierarchy if viewed as a node. Firstly all the references from the
030: * node is collected. This is done by starting at the top most class and collecting all the
031: * references. Once this is done a indirect ref graph is build up from the direct reference graph.
032: * This indirect reference is build up by recursivly adding the references of
033: * the direct references until we reach the end or the original node is reached again.
034: * The nodes are now sorted by comparing there indirect reference graph.
035: * NodeA has NodeB as indirect reference:
036: * If NodeB has NodeA as indirect reference then they are equil.
037: * Else NodeA is dependent on NodeB.
038: *
039: * Create a graph of non-cyclic refs and then start adding weight at the leaf
040: * nodes working back.
041: *
042: * @see com.versant.core.metadata.ClassMetaData#referenceGraphIndex
043: */
044: public final class JdbcClassReferenceGraph implements Comparator {
045: private HashMap cmdToRefMap = new HashMap();
046: private HashMap cmdToIndirectMap = new HashMap();
047: private HashMap cmdToNonCyclicMap = new HashMap();
048:
049: public int compare(Object o1, Object o2) {
050: ClassMetaData cmd1 = ((ClassMetaData) o1).top;
051: ClassMetaData cmd2 = ((ClassMetaData) o2).top;
052:
053: if (cmd1.weight != cmd2.weight) {
054: return cmd2.weight - cmd1.weight;
055: } else {
056: return cmd2.qname.compareTo(cmd1.qname);
057: }
058: }
059:
060: private final ClassMetaData[] classes;
061:
062: /**
063: * Extract out only the topmost classes from a.
064: */
065: public JdbcClassReferenceGraph(ClassMetaData[] a) {
066: int n = a.length;
067: classes = new ClassMetaData[n];
068: for (int i = 0; i < n; i++) {
069: classes[i] = a[i];
070: classes[i].weight = 0;
071: }
072: }
073:
074: private void addRefs(ClassMetaData cmd, HashSet set) {
075: FieldMetaData[] fields = cmd.fields;
076: if (fields == null) {
077: return;
078: }
079: for (int i = 0; i < fields.length; i++) {
080: FieldMetaData field = fields[i];
081: if (field.isDirectRef()) {
082: set.add(field.typeMetaData.top);
083: }
084: }
085: }
086:
087: private void addRefsRecursive(ClassMetaData cmd, HashSet set) {
088: addRefs(cmd, set);
089: ClassMetaData[] pcSubs = cmd.pcSubclasses;
090: if (pcSubs == null)
091: return;
092: for (int i = 0; i < pcSubs.length; i++) {
093: addRefsRecursive(pcSubs[i], set);
094: }
095: }
096:
097: private HashSet getDirectRefs(ClassMetaData cmd, HashMap refMap) {
098: return (HashSet) refMap.get(cmd.top);
099: }
100:
101: private HashSet getIndirectRefs(ClassMetaData cmd,
102: HashMap indirectRefMap) {
103: return (HashSet) indirectRefMap.get(cmd.top);
104: }
105:
106: private void buildIndirectGraph() {
107: for (int i = 0; i < classes.length; i++) {
108: ClassMetaData cmd = classes[i];
109: if (cmd.pcSuperClass == null) {
110: HashSet indirectRefSet = new HashSet();
111: cmdToIndirectMap.put(cmd, indirectRefSet);
112: buildIndirectGraph(cmd, cmd, indirectRefSet,
113: cmdToRefMap);
114: }
115: }
116: }
117:
118: private void buildIndirectGraph(ClassMetaData rootCmd,
119: ClassMetaData cmd, Set indirectRefs, Map directRefMap) {
120: Set directRefs = (Set) directRefMap.get(cmd);
121: for (Iterator iterator = directRefs.iterator(); iterator
122: .hasNext();) {
123: ClassMetaData dRef = (ClassMetaData) iterator.next();
124: if (dRef != dRef.top)
125: BindingSupportImpl.getInstance().internal(
126: "Should be top most class");
127: if (dRef == rootCmd)
128: continue;
129: if (indirectRefs.contains(dRef))
130: continue;
131: indirectRefs.add(dRef);
132: buildIndirectGraph(rootCmd, dRef, indirectRefs,
133: directRefMap);
134: }
135: }
136:
137: private int calculateWieght(ClassMetaData cmd) {
138: if (Debug.DEBUG) {
139: if (cmd.top != cmd)
140: throw BindingSupportImpl.getInstance().internal(
141: "Must be top of hierarchy");
142: }
143: if (cmd.weight != 0) {
144: //already done
145: return cmd.weight;
146: }
147:
148: HashSet noncircularRefs = (HashSet) cmdToNonCyclicMap.get(cmd);
149: int maxWeight = 0;
150: for (Iterator iterator = noncircularRefs.iterator(); iterator
151: .hasNext();) {
152: ClassMetaData classMetaData = (ClassMetaData) iterator
153: .next();
154: int refWeight = calculateWieght(classMetaData);
155: if (refWeight > maxWeight)
156: maxWeight = refWeight;
157: }
158: return cmd.weight = maxWeight + 1;
159: }
160:
161: /**
162: * Sort the graph and set the referenceGraphIndex and referenceGraphCycle
163: * fields on each class.
164: *
165: * @see com.versant.core.metadata.ClassMetaData#referenceGraphIndex
166: * @see com.versant.core.metadata.ClassMetaData#referenceGraphCycle
167: */
168: public void sort() {
169: //build the direct refs graph
170: buildDirectRefGraph();
171:
172: //build the indirect ref graph
173: buildIndirectGraph();
174:
175: //build the non-cyclic ref graph
176: buildNonCyclicRefGraph();
177:
178: //calculate weights for the nodes
179: calculateWieght();
180:
181: List classList = Arrays.asList(this .classes);
182: Collections.sort(classList, this );
183: for (int i = 0; i < classList.size(); i++) {
184: ((ClassMetaData) classList.get(i))
185: .setReferenceGraphIndex(i);
186: }
187: }
188:
189: private void calculateWieght() {
190: for (int i = 0; i < classes.length; i++) {
191: ClassMetaData cmd = classes[i];
192: if (cmd.pcSuperClass == null) {
193: calculateWieght(cmd);
194: }
195: }
196: }
197:
198: private void buildNonCyclicRefGraph() {
199: for (int i = 0; i < classes.length; i++) {
200: ClassMetaData cmd = classes[i];
201: if (cmd.pcSuperClass == null) {
202: HashSet indirectRefSet = (HashSet) cmdToIndirectMap
203: .get(cmd);
204: HashSet nonCircularRefs = new HashSet();
205: cmdToNonCyclicMap.put(cmd, nonCircularRefs);
206:
207: for (Iterator iterator = indirectRefSet.iterator(); iterator
208: .hasNext();) {
209: ClassMetaData refNode = (ClassMetaData) iterator
210: .next();
211: if (!isCircularRef(cmd, refNode)) {
212: nonCircularRefs.add(refNode);
213: }
214: }
215: }
216: }
217: }
218:
219: private void buildDirectRefGraph() {
220: for (int i = 0; i < classes.length; i++) {
221: ClassMetaData cmd = classes[i];
222: if (cmd.pcSuperClass == null) {
223: HashSet refSet = new HashSet();
224: cmdToRefMap.put(cmd, refSet);
225: addRefsRecursive(cmd, refSet);
226: }
227: }
228: }
229:
230: public boolean isCircularRef(ClassMetaData cmd1, ClassMetaData cmd2) {
231: cmd1 = cmd1.top;
232: cmd2 = cmd2.top;
233: return (getIndirectRefs(cmd1, cmdToIndirectMap).contains(cmd2) && getIndirectRefs(
234: cmd2, cmdToIndirectMap).contains(cmd1));
235: }
236:
237: public void releaseMem() {
238: cmdToIndirectMap = null;
239: cmdToNonCyclicMap = null;
240: cmdToRefMap = null;
241: }
242: }
|