Source code: org/objectstyle/cayenne/access/util/DefaultSorter.java
1 /* ====================================================================
2 *
3 * The ObjectStyle Group Software License, Version 1.0
4 *
5 * Copyright (c) 2002-2003 The ObjectStyle Group
6 * and individual authors of the software. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * 3. The end-user documentation included with the redistribution, if
21 * any, must include the following acknowlegement:
22 * "This product includes software developed by the
23 * ObjectStyle Group (http://objectstyle.org/)."
24 * Alternately, this acknowlegement may appear in the software itself,
25 * if and wherever such third-party acknowlegements normally appear.
26 *
27 * 4. The names "ObjectStyle Group" and "Cayenne"
28 * must not be used to endorse or promote products derived
29 * from this software without prior written permission. For written
30 * permission, please contact andrus@objectstyle.org.
31 *
32 * 5. Products derived from this software may not be called "ObjectStyle"
33 * nor may "ObjectStyle" appear in their names without prior written
34 * permission of the ObjectStyle Group.
35 *
36 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39 * DISCLAIMED. IN NO EVENT SHALL THE OBJECTSTYLE GROUP OR
40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47 * SUCH DAMAGE.
48 * ====================================================================
49 *
50 * This software consists of voluntary contributions made by many
51 * individuals on behalf of the ObjectStyle Group. For more
52 * information on the ObjectStyle Group, please see
53 * <http://objectstyle.org/>.
54 *
55 */
56
57 package org.objectstyle.cayenne.access.util;
58
59 import java.util.ArrayList;
60 import java.util.Collection;
61 import java.util.Collections;
62 import java.util.Comparator;
63 import java.util.HashMap;
64 import java.util.Iterator;
65 import java.util.List;
66 import java.util.Map;
67
68 import org.apache.commons.collections.comparators.ReverseComparator;
69 import org.objectstyle.ashwood.dbutil.DbUtils;
70 import org.objectstyle.ashwood.dbutil.ForeignKey;
71 import org.objectstyle.ashwood.dbutil.Table;
72 import org.objectstyle.ashwood.graph.CollectionFactory;
73 import org.objectstyle.ashwood.graph.Digraph;
74 import org.objectstyle.ashwood.graph.IndegreeTopologicalSort;
75 import org.objectstyle.ashwood.graph.MapDigraph;
76 import org.objectstyle.ashwood.graph.StrongConnection;
77 import org.objectstyle.cayenne.CayenneRuntimeException;
78 import org.objectstyle.cayenne.DataObject;
79 import org.objectstyle.cayenne.ObjectId;
80 import org.objectstyle.cayenne.access.QueryEngine;
81 import org.objectstyle.cayenne.map.DataMap;
82 import org.objectstyle.cayenne.map.DbAttribute;
83 import org.objectstyle.cayenne.map.DbAttributePair;
84 import org.objectstyle.cayenne.map.DbEntity;
85 import org.objectstyle.cayenne.map.DbRelationship;
86 import org.objectstyle.cayenne.map.ObjEntity;
87 import org.objectstyle.cayenne.map.ObjRelationship;
88
89 /**
90 * DefaultSorter is a default implementation of DependencySorter based on
91 * ASHWOOD library. Presently it works for acyclic database schemas with
92 * possible multi-reflexive tables. The class uses topological sorting from
93 * ASHWOOD.
94 *
95 * @author Andriy Shapochka
96 */
97 public class DefaultSorter implements DependencySorter {
98
99 protected QueryEngine queryEngine;
100 protected Map dbEntityToTableMap;
101 protected Digraph referentialDigraph;
102 protected Digraph contractedReferentialDigraph;
103 protected Map components;
104 protected Map reflexiveDbEntities;
105
106 protected TableComparator tableComparator;
107 protected DbEntityComparator dbEntityComparator;
108 protected ObjEntityComparator objEntityComparator;
109
110 // used for lazy initialization
111 protected boolean dirty;
112
113 public DefaultSorter(QueryEngine queryEngine) {
114 indexSorter(queryEngine);
115 }
116
117 /**
118 * Marks this instance as "dirty", so that it will be indexed lazily on
119 * the next invocation.
120 */
121 public void indexSorter(QueryEngine queryEngine) {
122 this.dirty = true;
123 this.queryEngine = queryEngine;
124 }
125
126 /**
127 * Reindexes internal sorter.
128 */
129 protected synchronized void _indexSorter() {
130 if (!dirty) {
131 return;
132 }
133
134 Collection tables = new ArrayList(64);
135 dbEntityToTableMap = new HashMap(64);
136 reflexiveDbEntities = new HashMap(32);
137 for (Iterator i = queryEngine.getDataMaps().iterator(); i.hasNext();) {
138 DataMap map = (DataMap) i.next();
139 Iterator entitiesToConvert = map.getDbEntities().iterator();
140 while (entitiesToConvert.hasNext()) {
141 DbEntity entity = (DbEntity)entitiesToConvert.next();
142 Table table = new Table(entity.getCatalog(),
143 entity.getSchema(),
144 entity.getName());
145 fillInMetadata(table, entity);
146 dbEntityToTableMap.put(entity, table);
147 tables.add(table);
148 }
149 }
150 referentialDigraph = new MapDigraph(MapDigraph.HASHMAP_FACTORY);
151 DbUtils.buildReferentialDigraph(referentialDigraph, tables);
152 StrongConnection contractor =
153 new StrongConnection(
154 referentialDigraph,
155 CollectionFactory.ARRAYLIST_FACTORY);
156 contractedReferentialDigraph =
157 new MapDigraph(MapDigraph.HASHMAP_FACTORY);
158 contractor.contract(
159 contractedReferentialDigraph,
160 CollectionFactory.ARRAYLIST_FACTORY);
161 IndegreeTopologicalSort sorter =
162 new IndegreeTopologicalSort(contractedReferentialDigraph);
163 components = new HashMap(contractedReferentialDigraph.order());
164 int componentIndex = 0;
165 while (sorter.hasNext()) {
166 Collection component = (Collection) sorter.next();
167 ComponentRecord rec =
168 new ComponentRecord(componentIndex++, component);
169 for (Iterator i = component.iterator(); i.hasNext();) {
170 components.put(i.next(), rec);
171 }
172 }
173
174 tableComparator = new TableComparator();
175 dbEntityComparator = new DbEntityComparator();
176 objEntityComparator = new ObjEntityComparator();
177
178 // clear dirty flag
179 this.dirty = false;
180 }
181
182 public void sortDbEntities(List dbEntities, boolean deleteOrder) {
183 _indexSorter();
184 Collections.sort(dbEntities, getDbEntityComparator(deleteOrder));
185 }
186
187 public void sortObjEntities(List objEntities, boolean deleteOrder) {
188 _indexSorter();
189 Collections.sort(objEntities, getObjEntityComparator(deleteOrder));
190 }
191
192 public void sortObjectsForEntity(
193 ObjEntity objEntity,
194 List objects,
195 boolean deleteOrder) {
196
197 DbEntity dbEntity = objEntity.getDbEntity();
198
199 // if no sorting is required
200 if (!isReflexive(dbEntity)) {
201 return;
202 }
203
204 // don't forget to index the sorter
205 _indexSorter();
206
207 int size = objects.size();
208 List reflexiveRels = (List) reflexiveDbEntities.get(dbEntity);
209 String[] objRelNames = new String[reflexiveRels.size()];
210 for (int i = 0; i < objRelNames.length; i++) {
211 DbRelationship dbRel = (DbRelationship) reflexiveRels.get(i);
212 ObjRelationship objRel =
213 (dbRel != null
214 ? objEntity.getRelationshipForDbRelationship(dbRel)
215 : null);
216 objRelNames[i] = (objRel != null ? objRel.getName() : null);
217 }
218
219 List sorted = new ArrayList(size);
220
221 Digraph objectDependencyGraph =
222 new MapDigraph(MapDigraph.HASHMAP_FACTORY);
223 DataObject[] masters = new DataObject[objRelNames.length];
224 for (int i = 0; i < size; i++) {
225 DataObject current = (DataObject) objects.get(i);
226 objectDependencyGraph.addVertex(current);
227 int actualMasterCount = 0;
228 for (int k = 0; k < objRelNames.length; k++) {
229 String objRelName = objRelNames[k];
230 if (objRelName == null)
231 continue;
232 masters[k] =
233 (objRelName != null
234 ? (DataObject) current.readPropertyDirectly(objRelName)
235 : null);
236 if (masters[k] == null) {
237 masters[k] =
238 findReflexiveMaster(
239 current,
240 (ObjRelationship) objEntity.getRelationship(
241 objRelName),
242 current.getObjectId().getObjClass());
243 }
244
245 if (masters[k] != null) {
246 actualMasterCount++;
247 }
248 }
249 int mastersFound = 0;
250
251 for (int j = 0;
252 j < size && mastersFound < actualMasterCount;
253 j++) {
254
255 if (i == j) {
256 continue;
257 }
258
259 DataObject masterCandidate = (DataObject) objects.get(j);
260 for (int k = 0; k < masters.length; k++) {
261 if (masterCandidate.equals(masters[k])) {
262 objectDependencyGraph.putArc(
263 masterCandidate,
264 current,
265 Boolean.TRUE);
266 mastersFound++;
267 }
268 }
269 }
270 }
271
272 IndegreeTopologicalSort sorter =
273 new IndegreeTopologicalSort(objectDependencyGraph);
274
275 while (sorter.hasNext()) {
276 DataObject o = (DataObject) sorter.next();
277 if (o == null)
278 throw new CayenneRuntimeException(
279 "Sorting objects for "
280 + objEntity.getClassName()
281 + " failed. Cycles found.");
282 sorted.add(o);
283 }
284
285 // since API requires sorting within the same array,
286 // simply replace all objects with objects in the right order...
287 // may come up with something cleaner later
288 objects.clear();
289 objects.addAll(sorted);
290
291 if (deleteOrder) {
292 Collections.reverse(objects);
293 }
294 }
295
296 protected void fillInMetadata(Table table, DbEntity entity) {
297 //in this case quite a dummy
298 short keySequence = 1;
299 Iterator i = entity.getRelationshipMap().values().iterator();
300
301 while (i.hasNext()) {
302 DbRelationship candidate = (DbRelationship) i.next();
303 if ((!candidate.isToMany() && !candidate.isToDependentPK())
304 || candidate.isToMasterPK()) {
305 DbEntity target = (DbEntity) candidate.getTargetEntity();
306 boolean newReflexive = entity.equals(target);
307 Iterator j = candidate.getJoins().iterator();
308 while (j.hasNext()) {
309 DbAttributePair join = (DbAttributePair) j.next();
310 DbAttribute targetAttribute = join.getTarget();
311 if (targetAttribute.isPrimaryKey()) {
312 ForeignKey fk = new ForeignKey();
313 fk.setPkTableCatalog(target.getCatalog());
314 fk.setPkTableSchema(target.getSchema());
315 fk.setPkTableName(target.getName());
316 fk.setPkColumnName(targetAttribute.getName());
317 fk.setColumnName(join.getSource().getName());
318 fk.setKeySequence(keySequence++);
319 table.addForeignKey(fk);
320
321 if (newReflexive) {
322 List reflexiveRels =
323 (List) reflexiveDbEntities.get(entity);
324 if (reflexiveRels == null) {
325 reflexiveRels = new ArrayList(1);
326 reflexiveDbEntities.put(entity, reflexiveRels);
327 }
328 reflexiveRels.add(candidate);
329 newReflexive = false;
330 }
331 }
332 }
333 }
334 }
335 }
336
337 protected DataObject findReflexiveMaster(
338 DataObject obj,
339 ObjRelationship toOneRel,
340 Class targetClass) {
341 DbRelationship finalRel = (DbRelationship) toOneRel.getDbRelationships().get(0);
342 Map snapshot = obj.getCommittedSnapshot();
343 if (snapshot == null) {
344 snapshot = obj.getCurrentSnapshot();
345 }
346
347 Map pksnapshot = finalRel.targetPkSnapshotWithSrcSnapshot(snapshot);
348 if (pksnapshot != null) {
349 ObjectId destId = new ObjectId(targetClass, pksnapshot);
350 return obj.getDataContext().registeredObject(destId);
351 }
352
353 return null;
354 }
355
356 protected Comparator getDbEntityComparator(boolean dependantFirst) {
357 Comparator c = dbEntityComparator;
358 if (dependantFirst) {
359 c = new ReverseComparator(c);
360 }
361 return c;
362 }
363
364 protected Comparator getObjEntityComparator(boolean dependantFirst) {
365 Comparator c = objEntityComparator;
366 if (dependantFirst) {
367 c = new ReverseComparator(c);
368 }
369 return c;
370 }
371
372 protected Table getTable(DbEntity dbEntity) {
373 return (dbEntity != null)
374 ? (Table) dbEntityToTableMap.get(dbEntity)
375 : null;
376 }
377
378 protected Table getTable(ObjEntity objEntity) {
379 return getTable(objEntity.getDbEntity());
380 }
381
382 protected boolean isReflexive(DbEntity metadata) {
383 return reflexiveDbEntities.containsKey(metadata);
384 }
385
386 private class DbEntityComparator implements Comparator {
387 public int compare(Object o1, Object o2) {
388 if (o1 == o2)
389 return 0;
390 Table t1 = getTable((DbEntity) o1);
391 Table t2 = getTable((DbEntity) o2);
392 return tableComparator.compare(t1, t2);
393 }
394 }
395
396 private class ObjEntityComparator implements Comparator {
397 public int compare(Object o1, Object o2) {
398 if (o1 == o2)
399 return 0;
400 Table t1 = getTable((ObjEntity) o1);
401 Table t2 = getTable((ObjEntity) o2);
402 return tableComparator.compare(t1, t2);
403 }
404 }
405
406 private class TableComparator implements Comparator {
407 public int compare(Object o1, Object o2) {
408 int result = 0;
409 Table t1 = (Table) o1;
410 Table t2 = (Table) o2;
411 if (t1 == t2)
412 return 0;
413 if (t1 == null)
414 result = -1;
415 else if (t2 == null)
416 result = 1;
417 else {
418 ComponentRecord rec1 = (ComponentRecord) components.get(t1);
419 ComponentRecord rec2 = (ComponentRecord) components.get(t2);
420 int index1 = rec1.index;
421 int index2 = rec2.index;
422 result = (index1 > index2 ? 1 : (index1 < index2 ? -1 : 0));
423 if (result != 0 && rec1.component == rec2.component)
424 result = 0;
425 }
426 return result;
427 }
428 }
429
430 private static class ComponentRecord {
431 ComponentRecord(int index, Collection component) {
432 this.index = index;
433 this.component = component;
434 }
435 int index;
436 Collection component;
437 }
438 }