1 package org.apache.ojb.odmg;
2
3 /* Copyright 2002-2005 The Apache Software Foundation
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 import java.util.ArrayList;
19 import java.util.Iterator;
20 import java.util.List;
21 import java.util.Map;
22
23 import org.apache.commons.lang.ArrayUtils;
24 import org.apache.commons.lang.builder.ToStringBuilder;
25 import org.apache.ojb.broker.Identity;
26 import org.apache.ojb.broker.core.proxy.ProxyHelper;
27 import org.apache.ojb.broker.metadata.ClassDescriptor;
28 import org.apache.ojb.broker.metadata.CollectionDescriptor;
29 import org.apache.ojb.broker.metadata.ObjectReferenceDescriptor;
30 import org.apache.ojb.broker.util.BrokerHelper;
31 import org.apache.ojb.broker.util.logging.Logger;
32 import org.apache.ojb.broker.util.logging.LoggerFactory;
33 import org.apache.ojb.odmg.states.ModificationState;
34
35 /**
36 * <p>Implements an algorithm for reordering the object envelopes of a pending
37 * transaction to minimized the probability of foreign key constraint
38 * violations.</p>
39 *
40 * <p>The algorithm is based on a graph theoretical approach: Each object
41 * envelope is represented by a vertex in a graph. Each possible constraint
42 * on the order of database operations is represented by a directed edge
43 * in this graph, in which the initial vertex represents the object envelope
44 * to be sent to the database first and the terminal index represents the
45 * object envelope that might cause a FK violation if the initial vertex
46 * has not been sent to the database before.</p>
47 *
48 * <p>Additionally the edges in this graph are weighted. This is necessary
49 * because the object envelopes provide only information on the relation
50 * between objects <strong>after</strong> the transaction. FK violations,
51 * however, can also occur due to relations that existed <strong>before</strong>
52 * the transaction. Therefore the algorithm also considers potential relations
53 * between objects due to the fact that an object is of a class that is
54 * the item class of a object or collection reference of another object.
55 * Graph edges representing such potential relationships receive a lower
56 * weight than edges representing concrete relationships that exist in the
57 * current state of the object model.</p>
58 *
59 * <p>Once all graph edges have been established, the algorithm proceeds as
60 * follows:</p>
61 * <ol>
62 * <li>Iterate through all vertices and sum up the weight of all incoming
63 * edges (i.e. those edges whose terminal vertex is the current vertex).</li>
64 * <li>Find the minimum value of this weight sums (ideally this minimum is zero,
65 * meaning that there are object envelopes that can be sent to the
66 * database without risking FK violations)</li>
67 * <li>Add all vertices with a weight sum that is equal to this minimum to the
68 * reordered sequence of object envelopes and remove the vertices
69 * and all connected edges from the graph.</li>
70 * <li>If there are vertices left, repeat steps (1) through (3), otherwise
71 * we are done.
72 * </ol>
73 *
74 * @author Gerhard Grosse
75 * @version $Id: ObjectEnvelopeOrdering.java,v 1.1 2007-08-24 22:17:37 ewestfal Exp $
76 * @since Nov 15, 2004
77 */
78 class ObjectEnvelopeOrdering
79 {
80 private static final int CONCRETE_EDGE_WEIGHT = 3;
81 private static final int CONCRETE_EDGE_WEIGHT_WITH_FK = 4;
82 private static final int POTENTIAL_EDGE_WEIGHT = 1;
83 private static final int POTENTIAL_EDGE_WEIGHT_WITH_FK = 2;
84 private static final Object[] EMPTY_OBJECT_ARRAY = new Object[0];
85
86 private static Logger log = LoggerFactory.getLogger(ObjectEnvelopeOrdering.class);
87
88 private List originalOrder;
89 private Map envelopes;
90
91 private Vertex[] vertices;
92 private List edgeList;
93
94 private Identity[] newOrder;
95
96 /**
97 * Creates an object envelope ordering based on an original ordering
98 * of Identity objects and an Identity->ObjectEnvelope map
99 * @param originalOrder a list of Identity objects
100 * @param envelopes a map with ObjectEnvelope-s with their respective
101 * Identity-s as key
102 */
103 public ObjectEnvelopeOrdering(List originalOrder, Map envelopes)
104 {
105 this.originalOrder = originalOrder;
106 this.envelopes = envelopes;
107 }
108
109 /**
110 * Reorders the object envelopes. The new order is available from the
111 * <code>ordering</code> property.
112 * @see #getOrdering()
113 */
114 public void reorder()
115 {
116 int newOrderIndex = 0;
117 long t1 = 0, t2 = 0, t3;
118
119 if (log.isDebugEnabled())
120 {
121 t1 = System.currentTimeMillis();
122 }
123 newOrder = new Identity[originalOrder.size()];
124
125 if(log.isDebugEnabled()) log.debug("Orginal order: " + originalOrder);
126 // set up the vertex array in the order the envelopes were added
127 List vertexList = new ArrayList(originalOrder.size());
128 // int vertexIndex = 0;
129 for (Iterator it = originalOrder.iterator(); it.hasNext();)
130 {
131 ObjectEnvelope envelope = (ObjectEnvelope) envelopes.get(it.next());
132 if (envelope.needsUpdate() || envelope.needsInsert() || envelope.needsDelete())
133 {
134 Vertex vertex = new Vertex(envelope);
135 vertexList.add(vertex);
136 if (log.isDebugEnabled())
137 {
138 log.debug("Add new Vertex object "+envelope.getIdentity()+" to VertexList");
139 }
140 }
141 else
142 {
143 // envelope is clean - just add identity to new order
144 newOrder[newOrderIndex++] = envelope.getIdentity();
145 if (log.isDebugEnabled())
146 {
147 log.debug("Add unmodified object "+envelope.getIdentity()+" to new OrderList");
148 }
149 }
150 }
151 vertices = (Vertex[]) vertexList.toArray(new Vertex[vertexList.size()]);
152
153 // set up the edges
154 edgeList = new ArrayList(2 * vertices.length);
155 for (int i = 0; i < vertices.length; i++)
156 {
157 addEdgesForVertex(vertices[i]);
158 }
159
160 if (log.isDebugEnabled())
161 {
162 t2 = System.currentTimeMillis();
163 log.debug("Building object envelope graph took " + (t2 - t1) + " ms");
164 log.debug("Object envelope graph contains " + vertices.length + " vertices" + " and " + edgeList.size()
165 + " edges");
166 }
167
168 int remainingVertices = vertices.length;
169 int iterationCount = 0;
170 while (remainingVertices > 0)
171 {
172 // update iteration count
173 iterationCount++;
174
175 // update incoming edge counts
176 for (Iterator it = edgeList.iterator(); it.hasNext();)
177 {
178 Edge edge = (Edge) it.next();
179 if (!edge.isProcessed())
180 {
181 if(log.isDebugEnabled())
182 {
183 final String msg = "Add weight '"+edge.getWeight()+"' for terminal vertex " + edge.getTerminalVertex() + " of edge " + edge;
184 log.debug(msg);
185 }
186 edge.getTerminalVertex().incrementIncomingEdgeWeight(edge.getWeight());
187 }
188 }
189
190 // find minimum weight of incoming edges of a vertex
191 int minIncomingEdgeWeight = Integer.MAX_VALUE;
192 for (int i = 0; i < vertices.length; i++)
193 {
194 Vertex vertex = vertices[i];
195 if (!vertex.isProcessed() && minIncomingEdgeWeight > vertex.getIncomingEdgeWeight())
196 {
197 minIncomingEdgeWeight = vertex.getIncomingEdgeWeight();
198 if (minIncomingEdgeWeight == 0)
199 {
200 // we won't get any lower
201 break;
202 }
203 }
204 }
205
206 // process vertices having minimum incoming edge weight
207 int processCount = 0;
208 for (int i = 0; i < vertices.length; i++)
209 {
210 Vertex vertex = vertices[i];
211 if (!vertex.isProcessed() && vertex.getIncomingEdgeWeight() == minIncomingEdgeWeight)
212 {
213 newOrder[newOrderIndex++] = vertex.getEnvelope().getIdentity();
214 vertex.markProcessed();
215 processCount++;
216 if (log.isDebugEnabled())
217 {
218 log.debug("add minimum edge weight - "+minIncomingEdgeWeight
219 + ", newOrderList: " + ArrayUtils.toString(newOrder));
220 }
221 }
222 vertex.resetIncomingEdgeWeight();
223 }
224
225 if (log.isDebugEnabled())
226 {
227 log.debug("Processed " + processCount + " of " + remainingVertices
228 + " remaining vertices in iteration #" + iterationCount);
229 }
230 remainingVertices -= processCount;
231 }
232
233 if (log.isDebugEnabled())
234 {
235 t3 = System.currentTimeMillis();
236 log.debug("New ordering: " + ArrayUtils.toString(newOrder));
237 log.debug("Processing object envelope graph took " + (t3 - t2) + " ms");
238 }
239
240 }
241
242 /**
243 * Gets the reordered sequence of object envelopes
244 * @return an array of Identity objects representing the opimized sequence
245 * of database operations
246 */
247 public Identity[] getOrdering()
248 {
249 if (newOrder == null)
250 {
251 reorder();
252 }
253 return newOrder;
254 }
255
256 /**
257 * Adds all edges for a given object envelope vertex. All edges are
258 * added to the edgeList map.
259 * @param vertex the Vertex object to find edges for
260 */
261 private void addEdgesForVertex(Vertex vertex)
262 {
263 ClassDescriptor cld = vertex.getEnvelope().getClassDescriptor();
264 Iterator rdsIter = cld.getObjectReferenceDescriptors(true).iterator();
265 while (rdsIter.hasNext())
266 {
267 ObjectReferenceDescriptor rds = (ObjectReferenceDescriptor) rdsIter.next();
268 addObjectReferenceEdges(vertex, rds);
269 }
270 Iterator cdsIter = cld.getCollectionDescriptors(true).iterator();
271 while (cdsIter.hasNext())
272 {
273 CollectionDescriptor cds = (CollectionDescriptor) cdsIter.next();
274 addCollectionEdges(vertex, cds);
275 }
276 }
277
278 /**
279 * Finds edges based to a specific object reference descriptor and
280 * adds them to the edge map.
281 * @param vertex the object envelope vertex holding the object reference
282 * @param rds the object reference descriptor
283 */
284 private void addObjectReferenceEdges(Vertex vertex, ObjectReferenceDescriptor rds)
285 {
286 Object refObject = rds.getPersistentField().get(vertex.getEnvelope().getRealObject());
287 Class refClass = rds.getItemClass();
288 for (int i = 0; i < vertices.length; i++)
289 {
290 Edge edge = null;
291 // ObjectEnvelope envelope = vertex.getEnvelope();
292 Vertex refVertex = vertices[i];
293 ObjectEnvelope refEnvelope = refVertex.getEnvelope();
294 if (refObject == refEnvelope.getRealObject())
295 {
296 edge = buildConcrete11Edge(vertex, refVertex, rds.hasConstraint());
297 }
298 else if (refClass.isInstance(refVertex.getEnvelope().getRealObject()))
299 {
300 edge = buildPotential11Edge(vertex, refVertex, rds.hasConstraint());
301 }
302 if (edge != null)
303 {
304 if (!edgeList.contains(edge))
305 {
306 edgeList.add(edge);
307 }
308 else
309 {
310 edge.increaseWeightTo(edge.getWeight());
311 }
312 }
313 }
314 }
315
316 /**
317 * Finds edges base on a specific collection descriptor (1:n and m:n)
318 * and adds them to the edge map.
319 * @param vertex the object envelope vertex holding the collection
320 * @param cds the collection descriptor
321 */
322 private void addCollectionEdges(Vertex vertex, CollectionDescriptor cds)
323 {
324 ObjectEnvelope envelope = vertex.getEnvelope();
325 Object col = cds.getPersistentField().get(envelope.getRealObject());
326 Object[] refObjects;
327 if (col == null || (ProxyHelper.isCollectionProxy(col) && !ProxyHelper.getCollectionProxy(col).isLoaded()))
328 {
329 refObjects = EMPTY_OBJECT_ARRAY;
330 }
331 else
332 {
333 refObjects = BrokerHelper.getCollectionArray(col);
334 }
335 Class refClass = cds.getItemClass();
336
337 for (int i = 0; i < vertices.length; i++)
338 {
339 Edge edge = null;
340 Vertex refVertex = vertices[i];
341 ObjectEnvelope refEnvelope = refVertex.getEnvelope();
342
343 if (refClass.isInstance(refEnvelope.getRealObject()))
344 {
345 if (containsObject(refEnvelope.getRealObject(), refObjects))
346 {
347 if (cds.isMtoNRelation())
348 {
349 edge = buildConcreteMNEdge(vertex, refVertex);
350 }
351 else
352 {
353 edge = buildConcrete1NEdge(vertex, refVertex);
354 }
355 }
356 else
357 {
358 if (cds.isMtoNRelation())
359 {
360 edge = buildPotentialMNEdge(vertex, refVertex);
361 }
362 else
363 {
364 edge = buildPotential1NEdge(vertex, refVertex);
365 }
366 }
367 }
368 if (edge != null)
369 {
370 if (!edgeList.contains(edge))
371 {
372 edgeList.add(edge);
373 }
374 else
375 {
376 edge.increaseWeightTo(edge.getWeight());
377 }
378 }
379 }
380 }
381
382 /**
383 * Helper method that searches an object array for the occurence of a
384 * specific object based on reference equality
385 * @param searchFor the object to search for
386 * @param searchIn the array to search in
387 * @return true if the object is found, otherwise false
388 */
389 private static boolean containsObject(Object searchFor, Object[] searchIn)
390 {
391 for (int i = 0; i < searchIn.length; i++)
392 {
393 if (searchFor == searchIn[i])
394 {
395 return true;
396 }
397 }
398 return false;
399 }
400
401 /**
402 * Checks if the database operations associated with two object envelopes
403 * that are related via an 1:1 (or n:1) reference needs to be performed
404 * in a particular order and if so builds and returns a corresponding
405 * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
406 * The following cases are considered (* means object needs update, + means
407 * object needs insert, - means object needs to be deleted):
408 * <table>
409 * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
410 * <tr><td>(1)* -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
411 * <tr><td>(1)* -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
412 * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
413 * <tr><td>(1)+ -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
414 * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
415 * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
416 * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
417 * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
418 * <table>
419 * @param vertex1 object envelope vertex of the object holding the reference
420 * @param vertex2 object envelope vertex of the referenced object
421 * @return an Edge object or null if the two database operations can
422 * be performed in any order
423 */
424 protected Edge buildConcrete11Edge(Vertex vertex1, Vertex vertex2, boolean fkToRef)
425 {
426 ModificationState state1 = vertex1.getEnvelope().getModificationState();
427 ModificationState state2 = vertex2.getEnvelope().getModificationState();
428 if (state1.needsUpdate() || state1.needsInsert())
429 {
430 if (state2.needsInsert())
431 {
432 // (2) must be inserted before (1) can point to it
433 return new Edge(vertex2, vertex1, fkToRef ? CONCRETE_EDGE_WEIGHT_WITH_FK : CONCRETE_EDGE_WEIGHT);
434 }
435 }
436 else if (state1.needsDelete())
437 {
438 if (state2.needsDelete())
439 {
440 // (1) points to (2) and must be deleted first
441 return new Edge(vertex1, vertex2, fkToRef ? CONCRETE_EDGE_WEIGHT_WITH_FK : CONCRETE_EDGE_WEIGHT);
442 }
443 }
444 return null;
445 }
446
447 /**
448 * Checks if the database operations associated with two object envelopes
449 * that might have been related via an 1:1 (or n:1) reference before
450 * the current transaction needs to be performed
451 * in a particular order and if so builds and returns a corresponding
452 * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
453 * The following cases are considered (* means object needs update, + means
454 * object needs insert, - means object needs to be deleted):
455 * <table>
456 * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
457 * <tr><td>(1)* -(1:1)-> (2)+</td><td>no edge</td></tr>
458 * <tr><td>(1)* -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
459 * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
460 * <tr><td>(1)+ -(1:1)-> (2)+</td><td>no edge</td></tr>
461 * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge</td></tr>
462 * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
463 * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
464 * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
465 * <table>
466 * @param vertex1 object envelope vertex of the object that might have
467 * hold the reference
468 * @param vertex2 object envelope vertex of the potentially referenced
469 * object
470 * @return an Edge object or null if the two database operations can
471 * be performed in any order
472 */
473 protected Edge buildPotential11Edge(Vertex vertex1, Vertex vertex2, boolean fkToRef)
474 {
475 ModificationState state1 = vertex1.getEnvelope().getModificationState();
476 ModificationState state2 = vertex2.getEnvelope().getModificationState();
477 if (state1.needsUpdate() || state1.needsDelete())
478 {
479 if (state2.needsDelete())
480 {
481 // old version of (1) might point to (2)
482 return new Edge(vertex1, vertex2, fkToRef ? POTENTIAL_EDGE_WEIGHT_WITH_FK : POTENTIAL_EDGE_WEIGHT);
483 }
484 }
485 return null;
486 }
487
488 /**
489 * Checks if the database operations associated with two object envelopes
490 * that are related via an 1:n collection reference needs to be performed
491 * in a particular order and if so builds and returns a corresponding
492 * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
493 * The following cases are considered (* means object needs update, + means
494 * object needs insert, - means object needs to be deleted):
495 * <table>
496 * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
497 * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
498 * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
499 * <tr><td>(1)+ -(1:n)-> (2)*</td><td>(1)->(2) edge</td></tr>
500 * <tr><td>(1)+ -(1:n)-> (2)+</td><td>(1)->(2) edge</td></tr>
501 * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
502 * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
503 * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
504 * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
505 * <table>
506 * @param vertex1 object envelope vertex of the object holding the
507 * collection
508 * @param vertex2 object envelope vertex of the object contained in the
509 * collection
510 * @return an Edge object or null if the two database operations can
511 * be performed in any order
512 */
513 protected Edge buildConcrete1NEdge(Vertex vertex1, Vertex vertex2)
514 {
515 ModificationState state1 = vertex1.getEnvelope().getModificationState();
516 ModificationState state2 = vertex2.getEnvelope().getModificationState();
517 if (state1.needsInsert())
518 {
519 if (state2.needsUpdate() || state2.needsInsert())
520 {
521 // (2) now contains an FK to (1) thus (1) must be inserted first
522 return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
523 }
524 }
525 else if (state1.needsDelete())
526 {
527 if (state2.needsUpdate() || state2.needsDelete())
528 {
529 // Before deleting (1) give (2) a chance to drop its FK to it
530 return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
531 }
532 }
533 return null;
534 }
535
536 /**
537 * Checks if the database operations associated with two object envelopes
538 * that are might have been related via an 1:n collection reference before
539 * the current transaction needs to be performed
540 * in a particular order and if so builds and returns a corresponding
541 * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
542 * The following cases are considered (* means object needs update, + means
543 * object needs insert, - means object needs to be deleted):
544 * <table>
545 * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
546 * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
547 * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
548 * <tr><td>(1)+ -(1:n)-> (2)*</td><td>no edge</td></tr>
549 * <tr><td>(1)+ -(1:n)-> (2)+</td><td>no edge</td></tr>
550 * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge</td></tr>
551 * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
552 * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
553 * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
554 * <table>
555 * @param vertex1 object envelope vertex of the object holding the
556 * collection
557 * @param vertex2 object envelope vertex of the object that might have
558 * been contained in the collection
559 * @return an Edge object or null if the two database operations can
560 * be performed in any order
561 */
562 protected Edge buildPotential1NEdge(Vertex vertex1, Vertex vertex2)
563 {
564 ModificationState state1 = vertex1.getEnvelope().getModificationState();
565 ModificationState state2 = vertex2.getEnvelope().getModificationState();
566 if (state1.needsDelete())
567 {
568 if (state2.needsUpdate() || state2.needsDelete())
569 {
570 // Before deleting (1) give potential previous collection
571 // members a chance to drop their FKs to it
572 return new Edge(vertex2, vertex1, POTENTIAL_EDGE_WEIGHT);
573 }
574 }
575 return null;
576 }
577
578 /**
579 * Checks if the database operations associated with two object envelopes
580 * that are related via an m:n collection reference needs to be performed
581 * in a particular order and if so builds and returns a corresponding
582 * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
583 * The following cases are considered (* means object needs update, + means
584 * object needs insert, - means object needs to be deleted):
585 * <table>
586 * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
587 * <tr><td>(1)* -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
588 * <tr><td>(1)* -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
589 * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
590 * <tr><td>(1)+ -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
591 * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
592 * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
593 * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
594 * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
595 * <table>
596 * @param vertex1 object envelope vertex of the object holding the
597 * collection
598 * @param vertex2 object envelope vertex of the object contained in the
599 * collection
600 * @return an Edge object or null if the two database operations can
601 * be performed in any order
602 */
603 protected Edge buildConcreteMNEdge(Vertex vertex1, Vertex vertex2)
604 {
605 ModificationState state1 = vertex1.getEnvelope().getModificationState();
606 ModificationState state2 = vertex2.getEnvelope().getModificationState();
607 if (state1.needsUpdate() || state1.needsInsert())
608 {
609 if (state2.needsInsert())
610 {
611 // (2) must be inserted before we can create a link to it
612 return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
613 }
614 }
615 else if (state1.needsDelete())
616 {
617 if (state2.needsDelete())
618 {
619 // there is a link from (1) to (2) which must be deleted first,
620 // which will happen when deleting (1) - thus:
621 return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
622 }
623 }
624 return null;
625 }
626
627 /**
628 * Checks if the database operations associated with two object envelopes
629 * that might have been related via an m:n collection reference before
630 * the current transaction needs to be performed
631 * in a particular order and if so builds and returns a corresponding
632 * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
633 * The following cases are considered (* means object needs update, + means
634 * object needs insert, - means object needs to be deleted):
635 * <table>
636 * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
637 * <tr><td>(1)* -(m:n)-> (2)+</td><td>no edge</td></tr>
638 * <tr><td>(1)* -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
639 * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
640 * <tr><td>(1)+ -(m:n)-> (2)+</td><td>no edge</td></tr>
641 * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge</td></tr>
642 * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
643 * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
644 * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
645 * <table>
646 * @param vertex1 object envelope vertex of the object holding the
647 * collection
648 * @param vertex2 object envelope vertex of the object that might have
649 * been contained in the collection
650 * @return an Edge object or null if the two database operations can
651 * be performed in any order
652 */
653 protected Edge buildPotentialMNEdge(Vertex vertex1, Vertex vertex2)
654 {
655 ModificationState state1 = vertex1.getEnvelope().getModificationState();
656 ModificationState state2 = vertex2.getEnvelope().getModificationState();
657 if (state1.needsUpdate() || state1.needsDelete())
658 {
659 if (state2.needsDelete())
660 {
661 // old version of (1) might comprise a link to (2)
662 return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
663 }
664 }
665 return null;
666 }
667
668 /**
669 * Represents an edge in the object envelope graph
670 */
671 private static class Edge
672 {
673 private Vertex initial;
674 private Vertex terminal;
675 private Identity initialIdentity;
676 private Identity terminalIdentity;
677 private int weight;
678 private boolean knownToBeProcessed;
679 private int hashCode;
680
681 public Edge(Vertex initial, Vertex terminal, int weight)
682 {
683 this.initial = initial;
684 this.terminal = terminal;
685 this.initialIdentity = initial.getEnvelope().getIdentity();
686 this.terminalIdentity = terminal.getEnvelope().getIdentity();
687 this.weight = weight;
688 this.knownToBeProcessed = false;
689 this.hashCode = initialIdentity.hashCode() + 13 * terminalIdentity.hashCode();
690 }
691
692 public Vertex getInitialVertex()
693 {
694 return initial;
695 }
696
697 public Vertex getTerminalVertex()
698 {
699 return terminal;
700 }
701
702 public boolean connects(Vertex vertex)
703 {
704 return initial == vertex || terminal == vertex;
705 }
706
707 public void increaseWeightTo(int minWeight)
708 {
709 if (weight < minWeight)
710 {
711 weight = minWeight;
712 }
713 }
714
715 public int getWeight()
716 {
717 return weight;
718 }
719
720 public boolean isProcessed()
721 {
722 if (knownToBeProcessed)
723 {
724 return true;
725 }
726 else
727 {
728 boolean processed = initial.isProcessed() || terminal.isProcessed();
729 if (processed)
730 {
731 knownToBeProcessed = true;
732 }
733 return processed;
734 }
735 }
736
737 public boolean equals(Object obj)
738 {
739 if (obj instanceof Edge)
740 {
741 Edge other = (Edge) obj;
742 return this.initialIdentity.equals(other.initialIdentity)
743 && this.terminalIdentity.equals(other.terminalIdentity);
744 }
745 else
746 {
747 return false;
748 }
749 }
750
751 public int hashCode()
752 {
753 return hashCode;
754 }
755
756 public String toString()
757 {
758 return new ToStringBuilder(this)
759 .append("initial", initialIdentity)
760 .append("terminal", terminalIdentity)
761 .append("weight", weight)
762 .append("processed", knownToBeProcessed)
763 .toString();
764 }
765 }
766
767 /**
768 * Represents a vertex in the object envelope graph
769 */
770 private static class Vertex
771 {
772 private ObjectEnvelope envelope;
773 private boolean processed;
774 private int incomingEdgeWeight;
775
776 public Vertex(ObjectEnvelope envelope)
777 {
778 this.envelope = envelope;
779 this.incomingEdgeWeight = 0;
780 this.processed = false;
781 }
782
783 public ObjectEnvelope getEnvelope()
784 {
785 return envelope;
786 }
787
788 public void markProcessed()
789 {
790 processed = true;
791 }
792
793 public boolean isProcessed()
794 {
795 return processed;
796 }
797
798 public void resetIncomingEdgeWeight()
799 {
800 incomingEdgeWeight = 0;
801 }
802
803 public void incrementIncomingEdgeWeight(int weight)
804 {
805 incomingEdgeWeight += weight;
806 }
807
808 public int getIncomingEdgeWeight()
809 {
810 return incomingEdgeWeight;
811 }
812
813 public String toString()
814 {
815 return new ToStringBuilder(this)
816 .append("identity", envelope.getIdentity())
817 .append("processed", processed)
818 .append("incomingEdgeWeight", incomingEdgeWeight)
819 .toString();
820 }
821 }
822
823 }