1   /****************************************************************************
2    **
3    ** This file is part of yFiles-2.9. 
4    ** 
5    ** yWorks proprietary/confidential. Use is subject to license terms.
6    **
7    ** Redistribution of this file or of an unauthorized byte-code version
8    ** of this file is strictly forbidden.
9    **
10   ** Copyright (c) 2000-2011 by yWorks GmbH, Vor dem Kreuzberg 28, 
11   ** 72070 Tuebingen, Germany. All rights reserved.
12   **
13   ***************************************************************************/
14  package demo.view.flowchart.layout;
15  
16  import y.base.DataProvider;
17  import y.base.Edge;
18  import y.base.EdgeCursor;
19  import y.base.EdgeList;
20  import y.base.EdgeMap;
21  import y.base.ListCell;
22  import y.base.Node;
23  import y.base.NodeCursor;
24  import y.base.NodeMap;
25  import y.layout.LayoutGraph;
26  import y.layout.PortCandidate;
27  import y.layout.PortConstraint;
28  import y.layout.hierarchic.incremental.AbstractPortConstraintOptimizer;
29  import y.layout.hierarchic.incremental.EdgeData;
30  import y.layout.hierarchic.incremental.ItemFactory;
31  import y.layout.hierarchic.incremental.Layers;
32  import y.layout.hierarchic.incremental.LayoutDataProvider;
33  import y.layout.hierarchic.incremental.NodeData;
34  import y.layout.hierarchic.incremental.PCListOptimizer;
35  import y.layout.hierarchic.incremental.SwimLaneDescriptor;
36  import y.util.Comparators;
37  import y.util.Maps;
38  
39  import java.util.Collection;
40  import java.util.Comparator;
41  import java.util.HashSet;
42  import java.util.Iterator;
43  
44  /**
45   * @noinspection ImplicitNumericConversion, ObjectEquality
46   */
47  class FlowchartPortOptimizer extends AbstractPortConstraintOptimizer {
48    static final byte LANE_ALIGNMENT_LEFT = 0;
49    static final byte LANE_ALIGNMENT_RIGHT = 1;
50  
51    static final int PRIORITY_LOW = 1;
52    static final int PRIORITY_BASIC = 3;
53    static final int PRIORITY_HIGH = 5000;
54  
55    static final String NODE_TO_ALIGN_DP_KEY = "y.layout.hierarchic.incremental.SimlexNodePlacer.NODE_TO_ALIGN_WITH";
56  
57    private final FlowchartAlignmentCalculator alignmentCalculator;
58    private final PCListOptimizer pcListOptimizer;
59  
60    FlowchartPortOptimizer(byte layoutOrientation) {
61      this.alignmentCalculator = new FlowchartAlignmentCalculator();
62      this.pcListOptimizer = new PCListOptimizer();
63  
64      setLayoutOrientation(layoutOrientation);
65    }
66  
67    public void setLayoutOrientation(final byte layoutOrientation) {
68      super.setLayoutOrientation(layoutOrientation);
69  
70      alignmentCalculator.setLayoutOrientation(layoutOrientation);
71      pcListOptimizer.setLayoutOrientation(layoutOrientation);
72    }
73  
74    public void optimizeAfterLayering(LayoutGraph graph, Layers layers, LayoutDataProvider ldp, ItemFactory itemFactory) {
75      pcListOptimizer.optimizeAfterLayering(graph, layers, ldp, itemFactory);
76    }
77  
78    public void optimizeAfterSequencing(LayoutGraph graph, Layers layers, LayoutDataProvider ldp,
79                                        ItemFactory itemFactory) {
80      super.optimizeAfterSequencing(graph, layers, ldp, itemFactory);
81  
82      final EdgeMap edgePriority = Maps.createHashedEdgeMap();
83      final NodeMap nodeAlignment = Maps.createHashedNodeMap();
84  
85      alignmentCalculator.determineAlignment(graph, ldp, nodeAlignment, edgePriority);
86  
87      optimizeForAlignment(graph, ldp, itemFactory, nodeAlignment, edgePriority);
88  
89      optimizeMessageNodes(graph, ldp, itemFactory);
90    }
91  
92    protected void optimizeAfterSequencing(Node node, Comparator inEdgeOrder, Comparator outEdgeOrder, LayoutGraph graph,
93                                           LayoutDataProvider ldp, ItemFactory itemFactory) {
94      // set EAST or WEST temporary constraints for the same layer edges
95      for (EdgeCursor ec = node.edges(); ec.ok(); ec.next()) {
96        final Edge edge = ec.edge();
97  
98        if (isTemporarySameLayerEdge(edge, ldp)) {
99          final byte preferredSide = getPreferredSideForTemporarySameLayerEdge(edge, ldp);
100         itemFactory.setTemporaryPortConstraint(edge, node.equals(edge.source()), PortConstraint.create(preferredSide));
101       }
102     }
103 
104     // choose final temporary constraint for all non-assigned flatwise edges
105     optimizeFlatwiseEdges(node, true, outEdgeOrder, ldp, itemFactory);
106     optimizeFlatwiseEdges(node, false, inEdgeOrder, ldp, itemFactory);
107   }
108 
109   /**
110    * Chooses the final port constraint for all non-assigned flatwise edges.
111    */
112   private void optimizeFlatwiseEdges(final Node node, final boolean source, final Comparator edgeOrder,
113                                      final LayoutDataProvider ldp, final ItemFactory itemFactory) {
114     final Collection flatwiseEdges = new HashSet();
115     final EdgeList centralEdges = new EdgeList();
116 
117     for (EdgeCursor ec = source ? node.outEdges() : node.inEdges(); ec.ok(); ec.next()) {
118       final Edge edge = ec.edge();
119       final EdgeData edgeData = ldp.getEdgeData(edge);
120       final PortConstraint constraint = source ? edgeData.getSPC() : edgeData.getTPC();
121       final Collection candidates = source ? edgeData.getSourceCandidates() : edgeData.getTargetCandidates();
122 
123       if (constraint != null && (constraint.isAtEast() || constraint.isAtWest())) {
124         continue;
125       }
126 
127       if (isFlatwiseCandidateCollection(candidates, getLayoutOrientation())) {
128         flatwiseEdges.add(edge);
129       } else {
130         centralEdges.add(edge);
131       }
132     }
133 
134     if (flatwiseEdges.isEmpty()) {
135       return;
136     }
137 
138     centralEdges.addAll(flatwiseEdges);
139     Comparators.sort(centralEdges, edgeOrder);
140 
141     int i = 0;
142     for (EdgeCursor edgeCursor = centralEdges.edges(); edgeCursor.ok(); edgeCursor.next(), i++) {
143       final Edge edge = edgeCursor.edge();
144       if (flatwiseEdges.contains(edge)) {
145         final byte side = i < centralEdges.size() / 2 ? PortConstraint.WEST : PortConstraint.EAST;
146         itemFactory.setTemporaryPortConstraint(edge, source, PortConstraint.create(side));
147       }
148     }
149   }
150 
151   static boolean isTemporarySameLayerEdge(Edge edge, LayoutDataProvider ldp) {
152     return isTemporarySameLayerNode(edge.target(), ldp);
153   }
154 
155   static boolean isTemporarySameLayerNode(Node node, LayoutDataProvider ldp) {
156     return node.inDegree() == 2 && node.outDegree() == 0 && ldp.getNodeData(node) == null;
157   }
158 
159   static byte getPreferredSideForTemporarySameLayerEdge(Edge edge, LayoutDataProvider ldp) {
160     final Edge originalEdge = ldp.getEdgeData(edge).getAssociatedEdge();
161     final boolean source = originalEdge.source().equals(edge.source());
162     final NodeData sData = ldp.getNodeData(originalEdge.source());
163     final NodeData tData = ldp.getNodeData(originalEdge.target());
164 
165     if (sData.getPosition() < tData.getPosition()) {
166       return source ? PortConstraint.EAST : PortConstraint.WEST;
167     } else {
168       return !source ? PortConstraint.EAST : PortConstraint.WEST;
169     }
170   }
171 
172   private static boolean isAtPreferredPort(Edge edge, boolean source, LayoutDataProvider ldp) {
173     final Edge e = getOriginalEdge(edge, ldp);
174     final EdgeData edgeData = ldp.getEdgeData(e);
175     final PortConstraint pc = source ? edgeData.getSPC() : edgeData.getTPC();
176     return pc != null && (pc.isStrong() || pc.isAtEast() || pc.isAtWest());
177   }
178 
179   private void optimizeForAlignment(LayoutGraph graph, LayoutDataProvider ldp, ItemFactory itemFactory,
180                                     DataProvider node2AlignWith, DataProvider edge2Length) {
181     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
182       final Node node = nc.node();
183       if (!alignmentCalculator.isSpecialNode(graph, node, ldp) || node.degree() < 2) {
184         continue;
185       }
186 
187       node.sortOutEdges(new PositionEdgeComparator(false, ldp));
188       node.sortInEdges(new PositionEdgeComparator(true, ldp));
189 
190       final Edge criticalInEdge = getCriticalInEdge(node, node2AlignWith, edge2Length);
191       final Edge criticalOutEdge = getCriticalOutEdge(node, node2AlignWith, edge2Length);
192 
193       if (criticalInEdge != null || criticalOutEdge != null) {
194         optimizeWithCriticalEdges(node, ldp, itemFactory, criticalInEdge, criticalOutEdge);
195       } else if (node.degree() > 2) {
196         optimizeWithoutCriticalEdges(node, ldp, itemFactory);
197       }
198 
199       // Parallel edges of the critical edges which have a port constraints at the left or right side must have a
200       // port constraint for the same side at the opposite end, too. Otherwise, such an edge gets many bends and
201       // may even destroy the alignment.
202       if (criticalInEdge != null) {
203         for (EdgeCursor ec = node.inEdges(); ec.ok(); ec.next()) {
204           final Edge edge = ec.edge();
205           if (criticalInEdge != edge && criticalInEdge.source() == edge.source()) {
206             final PortConstraint pc = ldp.getEdgeData(edge).getTPC();
207             if (isFlatwisePortConstraint(pc)) {
208               itemFactory.setTemporaryPortConstraint(edge, true, PortConstraint.create(pc.getSide()));
209             }
210           }
211         }
212       }
213       if (criticalOutEdge != null) {
214         for (EdgeCursor ec = node.outEdges(); ec.ok(); ec.next()) {
215           final Edge edge = ec.edge();
216           if (criticalOutEdge != edge && criticalOutEdge.target() == edge.target()) {
217             final PortConstraint pc = ldp.getEdgeData(edge).getSPC();
218             if (isFlatwisePortConstraint(pc)) {
219               itemFactory.setTemporaryPortConstraint(edge, true, PortConstraint.create(pc.getSide()));
220             }
221           }
222         }
223       }
224     }
225   }
226 
227   private static void optimizeWithoutCriticalEdges(Node node, LayoutDataProvider ldp, ItemFactory factory) {
228     if (node.outDegree() > node.inDegree()) {
229       final Edge firstOut = node.firstOutEdge();
230       final Edge lastOut = node.lastOutEdge();
231 
232       if (!hasSameLayerEdge(node, true, ldp) && !isAtPreferredPort(firstOut, true, ldp) &&
233           (node.outDegree() != 2 || !isToRightPartition(firstOut.source(), firstOut.target(), ldp)
234               || hasSameLayerEdge(node, false, ldp))) {
235         factory.setTemporaryPortConstraint(firstOut, true, PortConstraint.create(PortConstraint.WEST));
236 
237       } else if (!hasSameLayerEdge(node, false, ldp) && !isAtPreferredPort(lastOut, true, ldp) &&
238           (node.outDegree() != 2 || !isToLeftPartition(lastOut.source(), lastOut.target(), ldp))) {
239         factory.setTemporaryPortConstraint(lastOut, true, PortConstraint.create(PortConstraint.EAST));
240       }
241 
242     } else {
243       final Edge firstIn = node.firstInEdge();
244       final Edge lastIn = node.lastInEdge();
245 
246       if (!hasSameLayerEdge(node, true, ldp) && !isAtPreferredPort(firstIn, false, ldp) &&
247           (node.degree() != 3 || !isToRightPartition(firstIn.target(), firstIn.source(), ldp)
248               || hasSameLayerEdge(node, false, ldp))) {
249         factory.setTemporaryPortConstraint(firstIn, false, PortConstraint.create(PortConstraint.WEST));
250 
251       } else if (!hasSameLayerEdge(node, false, ldp) && !isAtPreferredPort(lastIn, false, ldp) &&
252           (node.degree() != 3 || !isToLeftPartition(lastIn.target(), lastIn.source(), ldp))) {
253         factory.setTemporaryPortConstraint(lastIn, false, PortConstraint.create(PortConstraint.EAST));
254       }
255     }
256   }
257 
258   private static void optimizeWithCriticalEdges(Node node, LayoutDataProvider ldp, ItemFactory factory,
259                                                 Edge criticalInEdge, Edge criticalOutEdge) {
260     final Edge firstIn = node.firstInEdge();
261     final Edge firstOut = node.firstOutEdge();
262     final Edge lastIn = node.lastInEdge();
263     final Edge lastOut = node.lastOutEdge();
264 
265     if (node.degree() == 3 && node.outDegree() == 2 && criticalOutEdge == null) {
266       // Special case: the only in-edge is critical and there are two free out-edges
267       if ((!isToRightPartition(firstOut.source(), firstOut.target(), ldp) && isBackEdge(firstOut, ldp))
268           || isToLeftPartition(firstOut.source(), firstOut.target(), ldp)) {
269         setOptimizedPortConstraint(firstOut, true, PortConstraint.WEST, ldp, factory);
270         if ((!isToLeftPartition(lastOut.source(), lastOut.target(), ldp) && isBackEdge(lastOut, ldp))
271             || isToRightPartition(lastOut.source(), lastOut.target(), ldp)) {
272           setOptimizedPortConstraint(lastOut, true, PortConstraint.EAST, ldp, factory);
273         }
274       } else {
275         setOptimizedPortConstraint(lastOut, true, PortConstraint.EAST, ldp, factory);
276       }
277 
278     } else {
279 
280       if (node.degree() == 3 && node.inDegree() == 2 && criticalInEdge == null) {
281         // Special case: the only out-edge is critical and there are two free in-edges
282         if ((!isToRightPartition(firstIn.target(), firstIn.source(), ldp) && isBackEdge(firstIn, ldp))
283             || isToLeftPartition(firstIn.target(), firstIn.source(), ldp)) {
284           setOptimizedPortConstraint(firstIn, false, PortConstraint.WEST, ldp, factory);
285           if ((!isToRightPartition(lastIn.target(), lastIn.source(), ldp) && isBackEdge(lastIn, ldp))
286               || isToLeftPartition(lastIn.target(), lastIn.source(), ldp)) {
287             setOptimizedPortConstraint(lastIn, true, PortConstraint.EAST, ldp, factory);
288           }
289         } else {
290           setOptimizedPortConstraint(lastIn, true, PortConstraint.EAST, ldp, factory);
291         }
292 
293       } else if (criticalInEdge == null || (node.outDegree() > node.inDegree() && criticalOutEdge != null)) {
294 
295         if (!hasSameLayerEdge(node, true, ldp)) {
296           if (firstOut != criticalOutEdge) {
297             setOptimizedPortConstraint(firstOut, true, PortConstraint.WEST, ldp, factory);
298           } else if (firstIn != null && firstIn != criticalInEdge && node.inDegree() > 1) {
299             setOptimizedPortConstraint(firstIn, false, PortConstraint.WEST, ldp, factory);
300           }
301         }
302 
303         if (!hasSameLayerEdge(node, false, ldp)) {
304           if (lastOut != criticalOutEdge) {
305             setOptimizedPortConstraint(lastOut, true, PortConstraint.EAST, ldp, factory);
306           } else if (lastIn != null && lastIn != criticalInEdge && node.inDegree() > 1) {
307             setOptimizedPortConstraint(lastIn, false, PortConstraint.EAST, ldp, factory);
308           }
309         }
310 
311       } else {
312         if (!hasSameLayerEdge(node, true, ldp)) {
313           if (firstIn != criticalInEdge) {
314             setOptimizedPortConstraint(firstIn, false, PortConstraint.WEST, ldp, factory);
315           } else if (firstOut != null && firstOut != criticalOutEdge && node.outDegree() > 1) {
316             setOptimizedPortConstraint(firstOut, true, PortConstraint.WEST, ldp, factory);
317           }
318         }
319         if (!hasSameLayerEdge(node, false, ldp)) {
320           if (lastIn != criticalInEdge) {
321             setOptimizedPortConstraint(lastIn, false, PortConstraint.EAST, ldp, factory);
322           } else if (lastOut != null && lastOut != criticalOutEdge && node.outDegree() > 1) {
323             setOptimizedPortConstraint(lastOut, true, PortConstraint.EAST, ldp, factory);
324           }
325         }
326       }
327     }
328   }
329 
330   private static void setOptimizedPortConstraint(Edge edge, boolean source, byte direction, LayoutDataProvider ldp,
331                                                  ItemFactory factory) {
332     if (!isAtPreferredPort(edge, source, ldp)) {
333       factory.setTemporaryPortConstraint(edge, source, PortConstraint.create(direction));
334     }
335   }
336 
337   /**
338    * Special handling for messages (always attach them to the side of nodes)
339    */
340   private static void optimizeMessageNodes(LayoutGraph graph, LayoutDataProvider ldp, ItemFactory factory) {
341     final EdgeList edges = new EdgeList(graph.edges());
342     edges.splice(getSameLayerEdges(graph, ldp));
343 
344     for (EdgeCursor ec = edges.edges(); ec.ok(); ec.next()) {
345       final Edge e = ec.edge();
346       final Edge original = getOriginalEdge(e, ldp);
347       final int sourceLaneId = getSwimlaneId(original.source(), ldp);
348       final int targetLaneId = getSwimlaneId(original.target(), ldp);
349 
350       if (FlowchartElements.isMessageFlow(graph, e) && sourceLaneId != targetLaneId) {
351         if (ldp.getNodeData(e.source()).getType() == NodeData.TYPE_NORMAL
352             && FlowchartElements.isActivity(graph, e.source())) {
353           factory.setTemporaryPortConstraint(e, true, PortConstraint.create(
354               sourceLaneId < targetLaneId ? PortConstraint.EAST : PortConstraint.WEST));
355         }
356 
357         if (ldp.getNodeData(e.target()).getType() == NodeData.TYPE_NORMAL
358             && FlowchartElements.isActivity(graph, e.target())) {
359           factory.setTemporaryPortConstraint(e, false, PortConstraint.create(
360               sourceLaneId < targetLaneId ? PortConstraint.WEST : PortConstraint.EAST));
361         }
362       }
363     }
364   }
365 
366   static EdgeList getSameLayerEdges(LayoutGraph graph, LayoutDataProvider ldp) {
367     EdgeList sameLayerEdges = new EdgeList();
368     EdgeMap edge2Seen = Maps.createHashedEdgeMap();
369     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
370       Node n = nc.node();
371       NodeData nData = ldp.getNodeData(n);
372       for (ListCell cell = nData.getFirstSameLayerEdgeCell(); cell != null; cell = cell.succ()) {
373         Edge sameLayerEdge = (Edge) cell.getInfo();
374         Node opposite = sameLayerEdge.opposite(n);
375         if (!edge2Seen.getBool(sameLayerEdge) && graph.contains(opposite)) {
376           sameLayerEdges.add(sameLayerEdge);
377           edge2Seen.setBool(sameLayerEdge, true);
378         }
379       }
380     }
381     return sameLayerEdges;
382   }
383 
384   static EdgeList getSameLayerEdges(Node n, boolean left, LayoutDataProvider ldp) {
385     NodeData nData = ldp.getNodeData(n);
386     int nPos = nData.getPosition();
387     EdgeList result = new EdgeList();
388     for (ListCell cell = nData.getFirstSameLayerEdgeCell(); cell != null; cell = cell.succ()) {
389       Edge sameLayerEdge = (Edge) cell.getInfo();
390       Node other = sameLayerEdge.opposite(n);
391       int otherPos = ldp.getNodeData(other).getPosition();
392       if ((left && otherPos < nPos) || (!left && otherPos > nPos)) {
393         result.add(sameLayerEdge);
394       }
395     }
396     return result;
397   }
398 
399   static boolean hasSameLayerEdge(Node n, boolean left, LayoutDataProvider ldp) {
400     return !getSameLayerEdges(n, left, ldp).isEmpty();
401   }
402 
403   static boolean isFlatwisePortConstraint(PortConstraint pc) {
404     return pc != null && (pc.isAtEast() || pc.isAtWest());
405   }
406 
407   static boolean isFlatwiseCandidateCollection(Collection pcs, byte layoutOrientation) {
408     if (pcs == null) {
409       return false;
410     }
411 
412     boolean containsEast = false;
413     boolean containsWest = false;
414     for (Iterator iterator = pcs.iterator(); iterator.hasNext(); ) {
415       final PortCandidate pc = (PortCandidate) iterator.next();
416       final int direction = pc.getDirectionForLayoutOrientation(layoutOrientation);
417       if (!containsEast && (PortCandidate.EAST & direction) != 0) {
418         containsEast = true;
419       }
420       if (!containsWest && (PortCandidate.WEST & direction) != 0) {
421         containsWest = true;
422       }
423     }
424 
425     return containsEast && containsWest;
426   }
427 
428   static boolean isBackEdge(Edge edge, LayoutDataProvider ldp) {
429     return ldp.getEdgeData(edge).isReversed();
430   }
431 
432   /**
433    * Returns an in-edge for the given node which comes from the node it is aligned with. If several such edges exist,
434    * the edge with the highest length is returned.
435    */
436   private static Edge getCriticalInEdge(Node node, DataProvider node2AlignWith, DataProvider edge2Length) {
437     Edge bestEdge = null;
438     for (EdgeCursor ec = node.inEdges(); ec.ok(); ec.next()) {
439       final Edge edge = ec.edge();
440       if (node2AlignWith.get(node) == edge.source() &&
441           (bestEdge == null || edge2Length.getDouble(bestEdge) < edge2Length.getInt(edge))) {
442         bestEdge = edge;
443       }
444     }
445 
446     return bestEdge;
447   }
448 
449   /**
450    * Returns an out-edge for the given node which goes to the node it is aligned with. If several such edges exist, the
451    * edge with the highest length is returned.
452    */
453   private static Edge getCriticalOutEdge(Node node, DataProvider node2AlignWith, DataProvider edge2Length) {
454     Edge bestEdge = null;
455     for (EdgeCursor ec = node.outEdges(); ec.ok(); ec.next()) {
456       final Edge edge = ec.edge();
457       if (node2AlignWith.get(edge.target()) == node &&
458           (bestEdge == null || edge2Length.getDouble(bestEdge) < edge2Length.getInt(edge))) {
459         bestEdge = edge;
460       }
461     }
462 
463     return bestEdge;
464   }
465 
466   static Edge getOriginalEdge(Edge e, LayoutDataProvider ldp) {
467     NodeData sData = ldp.getNodeData(e.source());
468     if (sData.getType() == NodeData.TYPE_BEND && sData.getAssociatedEdge() != null) {
469       return sData.getAssociatedEdge();
470     }
471     NodeData tData = ldp.getNodeData(e.target());
472     if (tData.getType() == NodeData.TYPE_BEND && tData.getAssociatedEdge() != null) {
473       return tData.getAssociatedEdge();
474     }
475 
476 //    final EdgeData edgeData = ldp.getEdgeData(e);
477 //    if (edgeData.getAssociatedEdge() != null) {
478 //      return edgeData.getAssociatedEdge();
479 //    }
480 
481     return e;
482   }
483 
484   static int getSwimlaneId(Node n, LayoutDataProvider ldp) {
485     SwimLaneDescriptor laneDesc = ldp.getNodeData(n).getSwimLaneDescriptor();
486     return laneDesc == null ? -1 : laneDesc.getComputedLaneIndex();
487   }
488 
489   static boolean isToLeftPartition(Node source, Node target, LayoutDataProvider layoutData) {
490     SwimLaneDescriptor sourceDesc = layoutData.getNodeData(source).getSwimLaneDescriptor();
491     SwimLaneDescriptor targetDesc = layoutData.getNodeData(target).getSwimLaneDescriptor();
492     return sourceDesc != targetDesc && sourceDesc != null && targetDesc != null
493         && sourceDesc.getComputedLaneIndex() > targetDesc.getComputedLaneIndex();
494   }
495 
496   static boolean isToRightPartition(Node source, Node target, LayoutDataProvider layoutData) {
497     SwimLaneDescriptor sourceDesc = layoutData.getNodeData(source).getSwimLaneDescriptor();
498     SwimLaneDescriptor targetDesc = layoutData.getNodeData(target).getSwimLaneDescriptor();
499     return sourceDesc != targetDesc && sourceDesc != null && targetDesc != null
500         && sourceDesc.getComputedLaneIndex() < targetDesc.getComputedLaneIndex();
501   }
502 
503   /**
504    * Compares edges between the same layers according to the position of the end nodes of the specified end. Ties are
505    * broken by the direction of the port constraints at the specified end, then at the opposite end, where WEST is first
506    * and EAST is last.
507    * <p/>
508    * Can be used, for example, to sort in- or out-edges of a specific node in the typical best way.
509    */
510   static class PositionEdgeComparator implements Comparator {
511     private final boolean source;
512     private final LayoutDataProvider ldp;
513     private final SameLayerNodePositionComparator sameLayerNodePositionComparator;
514     private final SingleSidePortConstraintComparator portConstraintComparator;
515 
516     PositionEdgeComparator(boolean source, LayoutDataProvider ldp) {
517       sameLayerNodePositionComparator = new SameLayerNodePositionComparator(ldp);
518       portConstraintComparator = new SingleSidePortConstraintComparator();
519       this.source = source;
520       this.ldp = ldp;
521     }
522 
523     public int compare(Object o1, Object o2) {
524       final Edge e1 = (Edge) o1;
525       final Edge e2 = (Edge) o2;
526 
527       // compare positions at specified end
528       final int comparePos = sameLayerNodePositionComparator.compare(
529           source ? e1.source() : e1.target(), source ? e2.source() : e2.target());
530       if (comparePos != 0) {
531         return comparePos;
532       }
533 
534       // compare constraints at specified end
535       final int compareConstraints = portConstraintComparator.compare(
536           source ? ldp.getEdgeData(e1).getSPC() : ldp.getEdgeData(e1).getTPC(),
537           source ? ldp.getEdgeData(e2).getSPC() : ldp.getEdgeData(e2).getTPC());
538       if (compareConstraints != 0) {
539         return compareConstraints;
540       }
541 
542       // compare constraints at opposite end
543       return portConstraintComparator.compare(
544           source ? ldp.getEdgeData(e1).getTPC() : ldp.getEdgeData(e1).getSPC(),
545           source ? ldp.getEdgeData(e2).getTPC() : ldp.getEdgeData(e2).getSPC());
546     }
547   }
548 
549   /**
550    * Compares port constraints with respect to the upper or lower side of a node, that is WEST is first, EAST is last,
551    * and NORTH and SOUTH are neutral elements in the middle.
552    */
553   static class SingleSidePortConstraintComparator implements Comparator {
554 
555     public int compare(Object o1, Object o2) {
556       final PortConstraint pc1 = (PortConstraint) o1;
557       final PortConstraint pc2 = (PortConstraint) o2;
558 
559       // we use NORTH as neutral element since we care only about EST and WEST
560       final byte b1 = pc1 != null ? pc1.getSide() : PortConstraint.NORTH;
561       final byte b2 = pc2 != null ? pc2.getSide() : PortConstraint.NORTH;
562       if (b1 == b2) {
563         return 0;
564       } else if (b1 == PortConstraint.WEST || b2 == PortConstraint.EAST) {
565         return -1;
566       } else {
567         return 1;
568       }
569     }
570   }
571 
572   /**
573    * Compares nodes in the same layer according to their positions.
574    */
575   static class SameLayerNodePositionComparator implements Comparator {
576     private final LayoutDataProvider ldp;
577 
578     SameLayerNodePositionComparator(LayoutDataProvider ldp) {
579       this.ldp = ldp;
580     }
581 
582     public int compare(Object o1, Object o2) {
583       return Comparators.compare(ldp.getNodeData((Node) o1).getPosition(), ldp.getNodeData((Node) o2).getPosition());
584     }
585   }
586 
587 }
588