|
1 package org.apache.ojb.odmg;
2
3
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
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
103 public ObjectEnvelopeOrdering(List originalOrder, Map envelopes)
104 {
105 this.originalOrder = originalOrder;
106 this.envelopes = envelopes;
107 }
108
109
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 List vertexList = new ArrayList (originalOrder.size());
128 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 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 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 iterationCount++;
174
175 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 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 break;
202 }
203 }
204 }
205
206 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
247 public Identity[] getOrdering()
248 {
249 if (newOrder == null)
250 {
251 reorder();
252 }
253 return newOrder;
254 }
255
256
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
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 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
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
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
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 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 return new Edge(vertex1, vertex2, fkToRef ? CONCRETE_EDGE_WEIGHT_WITH_FK : CONCRETE_EDGE_WEIGHT);
442 }
443 }
444 return null;
445 }
446
447
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 return new Edge(vertex1, vertex2, fkToRef ? POTENTIAL_EDGE_WEIGHT_WITH_FK : POTENTIAL_EDGE_WEIGHT);
483 }
484 }
485 return null;
486 }
487
488
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 return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
523 }
524 }
525 else if (state1.needsDelete())
526 {
527 if (state2.needsUpdate() || state2.needsDelete())
528 {
529 return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
531 }
532 }
533 return null;
534 }
535
536
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 return new Edge(vertex2, vertex1, POTENTIAL_EDGE_WEIGHT);
573 }
574 }
575 return null;
576 }
577
578
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 return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
613 }
614 }
615 else if (state1.needsDelete())
616 {
617 if (state2.needsDelete())
618 {
619 return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
622 }
623 }
624 return null;
625 }
626
627
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 return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
663 }
664 }
665 return null;
666 }
667
668
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
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 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.