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