001: /*
002: * This is free software, licensed under the Gnu Public License (GPL)
003: * get a copy from <http://www.gnu.org/licenses/gpl.html>
004: * @version $Id: DependencyResolver.java,v 1.3 2005/06/18 04:58:13 hzeller Exp $
005: * @author <a href="mailto:martin.grotzke@javakaffee.de">Martin Grotzke</a>
006: */
007: package henplus.util;
008:
009: import henplus.sqlmodel.ColumnFkInfo;
010: import henplus.sqlmodel.Table;
011:
012: import java.util.ArrayList;
013: import java.util.HashMap;
014: import java.util.HashSet;
015: import java.util.Iterator;
016: import java.util.List;
017: import java.util.Map;
018: import java.util.Set;
019:
020: /**
021: * Resolves dependencies between a given set of tables in respect to their foreign keys.<br>
022: * Created on: Sep 20, 2004<br>
023: *
024: * @author <a href="mailto:martin.grotzke@javakaffee.de">Martin Grotzke</a>
025: * @version $Id: DependencyResolver.java,v 1.3 2005/06/18 04:58:13 hzeller Exp $
026: */
027: public final class DependencyResolver {
028:
029: private final Iterator _tableIter;
030: private Set cyclicDependencies/*<List<Table>>*/;
031:
032: /**
033: * @param tableIter An <code>Iterator</code> over <code>Table</code>s.
034: */
035: public DependencyResolver(Iterator/*<Table>*/tableIter) {
036: _tableIter = tableIter;
037: };
038:
039: /**
040: * @param tables A <code>Set</code> of <code>Table</code> objects.
041: */
042: public DependencyResolver(Set/*<Table>*/tables) {
043: _tableIter = (tables != null) ? tables.iterator() : null;
044: }
045:
046: /**
047: * @return
048: *
049: */
050: public ResolverResult sortTables() {
051: ListMap resolved = new ListMap();
052: Map unresolved = null;
053:
054: // first run: separate tables with and without dependencies
055: while (_tableIter.hasNext()) {
056: Table t = (Table) _tableIter.next();
057: if (t == null) {
058: continue;
059: }
060: Set fks = t.getForeignKeys();
061:
062: // no dependency / foreign key?
063: if (fks == null) {
064: // System.out.println( "[sortTables] put " + t + " to resolved." );
065: resolved.put(t.getName(), t);
066: } else {
067: // dependency fulfilled?
068: boolean nodep = true;
069: Iterator iter2 = fks.iterator();
070: while (iter2.hasNext() && nodep) {
071: ColumnFkInfo fk = (ColumnFkInfo) iter2.next();
072: if (!resolved.containsKey(fk.getPkTable())) {
073: nodep = false;
074: }
075: }
076:
077: if (nodep) {
078: // System.out.println( "[sortTables] put " + t + " to resolved." );
079: resolved.put(t.getName(), t);
080: } else {
081: if (unresolved == null)
082: unresolved = new HashMap();
083: // System.out.println( "[sortTables] put " + t + " to unresolved." );
084: unresolved.put(t.getName(), t);
085: }
086: }
087: }
088:
089: // second run: we check remaining deps
090: if (unresolved != null) {
091: Iterator iter = unresolved.values().iterator();
092: while (iter.hasNext()) {
093: Table t = (Table) iter.next();
094: resolveDep(t, null, resolved, unresolved);
095: }
096: }
097:
098: // do we need a second run?
099: // unresolved = cleanUnresolved( resolved, unresolved );
100:
101: // add all unresolved/conflicting tables to the resulting list
102: List result = resolved.valuesList();
103: if (unresolved != null) {
104: Iterator iter = unresolved.values().iterator();
105: while (iter.hasNext()) {
106: Object table = iter.next();
107: if (!result.contains(table))
108: result.add(table);
109: }
110: }
111:
112: return new ResolverResult(result, cyclicDependencies);
113: }
114:
115: /**
116: * @return
117: *
118: */
119: /* Martin: needed ?
120: private Set restructureDeps() {
121: Set deps = null;
122: if ( cyclicDependencies != null ) {
123: deps = new HashSet();
124: Iterator iter = cyclicDependencies.iterator();
125: while ( iter.hasNext() )
126: deps.add( ((ListMap)iter.next()).valuesList() );
127: }
128: return deps;
129: }
130: */
131: /**
132: * @param resolved
133: * @param unresolved
134: * @return A Map which contains all yet unresolved Tables mapped to their names.
135: */
136: /* Martin: needed ?
137: private Map cleanUnresolved( Map resolved, Map unresolved ) {
138: Map result = null;
139:
140: if ( unresolved != null ) {
141: Iterator iter = unresolved.keySet().iterator();
142: while ( iter.hasNext() ) {
143: // type element = (type) iter.next();
144:
145: }
146: }
147:
148: return null;
149: }
150: */
151: /**
152: * @param t
153: * @param cyclePath The path of tables which have cyclic dependencies
154: * @param resolved
155: * @param unresolved
156: */
157: private void resolveDep(Table t, List/*<Table>*/cyclePath,
158: Map resolved, Map unresolved) {
159:
160: // System.out.println( "[resolveDep] >>> Starting for t: " + t + " and cyclePath: " + cyclePath );
161:
162: // if the current table is no more in the unresolved collection
163: if (t == null || resolved.containsKey(t.getName()))
164: return;
165:
166: boolean nodep = false;
167: boolean firstrun = true;
168: Set fks = t.getForeignKeys();
169: Iterator iter = fks.iterator();
170: while (iter.hasNext()) {
171: ColumnFkInfo fk = (ColumnFkInfo) iter.next();
172:
173: // System.out.println( "[resolveDep] FK -> " + fk.getPkTable() + ": " + resolved.containsKey( fk.getPkTable() ) );
174: if (!resolved.containsKey(fk.getPkTable())) {
175:
176: Table inner = (Table) unresolved.get(fk.getPkTable());
177:
178: // if there's yet a cycle with the two tables inner following t
179: // then proceed to the next FK and ignore this potential cycle
180: if (duplicateCycle(t, inner))
181: continue;
182:
183: if (cyclePath != null && cyclePath.contains(inner)) {
184:
185: cyclePath.add(t);
186:
187: // create a new list for the detected cycle to add to the
188: // cyclicDeps, the former one (cyclePath) is used further on
189: List cycle = new ArrayList(cyclePath);
190: cycle.add(inner);
191: if (cyclicDependencies == null)
192: cyclicDependencies = new HashSet();
193: // System.out.println("[resolveDep] +++ Putting cyclePath: " + cycle );
194: cyclicDependencies.add(cycle);
195: continue;
196:
197: } else {
198: if (cyclePath == null) {
199: // System.out.println("[resolveDep] Starting cyclePath with: " + t);
200: cyclePath = new ArrayList();
201: }
202: cyclePath.add(t);
203: }
204:
205: resolveDep(inner, cyclePath, resolved, unresolved);
206:
207: if (resolved.containsKey(fk.getPkTable())) {
208: nodep = (firstrun || nodep) && true;
209: firstrun = false;
210: }
211: } else {
212: nodep = (firstrun || nodep) && true;
213: firstrun = false;
214: }
215: }
216:
217: if (nodep && !resolved.containsKey(t.getName())) {
218: // System.out.println( "[resolveDep] put " + t + " to resolved." );
219: resolved.put(t.getName(), t);
220: }
221:
222: }
223:
224: /**
225: * Tests if there's yet a cycle (stored in cyclicDependencies) with
226: * the given tables t and inner, whith inner following t.
227: * @param t
228: * @param inner
229: * @return
230: */
231: private boolean duplicateCycle(Table t, Table inner) {
232: boolean result = false;
233: if (cyclicDependencies != null) {
234: Iterator iter = cyclicDependencies.iterator();
235: while (iter.hasNext() && !result) {
236: List path = (List) iter.next();
237: if (path.contains(t)) {
238: int tIdx = path.indexOf(t);
239: if (path.size() > tIdx + 1
240: && inner.equals(path.get(tIdx + 1))) {
241: result = true;
242: }
243: }
244: }
245: }
246: return result;
247: }
248:
249: public class ResolverResult {
250: private final List/*<Table>*/_tables;
251: private final Set/*<List<Table>>*/_cyclicDependencies;
252:
253: public ResolverResult(List tables, Set cyclicDependencies) {
254: _tables = tables;
255: _cyclicDependencies = cyclicDependencies;
256: }
257:
258: /**
259: * @return Returns the cyclicDependencies: a <code>Set</code> holding
260: * <code>List</code>s of <code>CycleEntry</code> objects, where each list
261: * represents the path of a cyclic dependency.
262: */
263: public Set/*<List<Table>>*/getCyclicDependencies() {
264: return _cyclicDependencies;
265: }
266:
267: /**
268: * @return Returns the tables.
269: */
270: public List/*<Table>*/getTables() {
271: return _tables;
272: }
273: }
274:
275: public class CycleEntry {
276: private Table _table;
277: private ColumnFkInfo _fk;
278:
279: public CycleEntry(Table table, ColumnFkInfo fk) {
280: _table = table;
281: _fk = fk;
282: }
283:
284: /**
285: * @return Returns the fk.
286: */
287: public ColumnFkInfo getFk() {
288: return _fk;
289: }
290:
291: /**
292: * @return Returns the table.
293: */
294: public Table getTable() {
295: return _table;
296: }
297:
298: public String toString() {
299: StringBuffer sb = new StringBuffer("CycleEntry [");
300: sb.append("table: ").append(_table.getName());
301: sb.append(", fk: ").append(_fk.toString());
302: sb.append("]");
303: return sb.toString();
304: }
305:
306: public boolean equals(Object other) {
307: boolean result = false;
308: if (other == this )
309: result = true;
310: else if (other instanceof CycleEntry) {
311: CycleEntry ce = (CycleEntry) other;
312: if (_table == null && ce.getTable() == null
313: && _fk == null && ce.getFk() == null)
314: result = true;
315: else if (_table.equals(ce.getTable())
316: && _fk.equals(ce.getFk()))
317: result = true;
318: }
319: return result;
320: }
321: }
322:
323: }
|