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.GraphInterface;
22  import y.base.ListCell;
23  import y.base.Node;
24  import y.base.NodeCursor;
25  import y.base.NodeList;
26  import y.base.NodeMap;
27  import y.base.YList;
28  import y.geom.YPoint;
29  import y.layout.AbstractLayoutStage;
30  import y.layout.LayoutGraph;
31  import y.layout.LayoutOrientation;
32  import y.layout.LayoutStage;
33  import y.layout.Layouter;
34  import y.layout.NodeLayout;
35  import y.layout.PortCandidate;
36  import y.layout.PortCandidateSet;
37  import y.layout.PortConstraintKeys;
38  import y.layout.RemoveColinearBendsStage;
39  import y.layout.grouping.Grouping;
40  import y.layout.grouping.GroupingKeys;
41  import y.layout.hierarchic.IncrementalHierarchicLayouter;
42  import y.util.Comparators;
43  import y.util.DataProviderAdapter;
44  import y.util.GraphHider;
45  import y.util.Maps;
46  import y.util.WrappedObjectDataProvider;
47  
48  import java.util.ArrayList;
49  import java.util.Collection;
50  import java.util.Collections;
51  import java.util.Comparator;
52  import java.util.HashMap;
53  import java.util.Iterator;
54  import java.util.List;
55  import java.util.Map;
56  
57  /**
58   * Transforms the graph for the flowchart layout algorithm and creates related port candidates and edge groupings.
59   * <p/>
60   * This class expects to find an IncrementalHierarchicLayouter in its core layouters. It does its transformation,
61   * invokes the core layout and finally restores the original graph.
62   */
63  class FlowchartTransformerStage extends AbstractLayoutStage {
64    static final Object LAYER_ID_DP_KEY = "FlowchartTransformerStage.LAYER_ID_DP_KEY";
65    static final Object GROUPING_NODES_DP_KEY = "FlowchartTransformerStage.GROUPING_NODES_DP_KEY";
66  
67    static final int NODE_TYPE_PRECEDING_LAYER = 1;
68    static final int NODE_TYPE_SUCCEEDING_LAYER = 2;
69  
70    private static final double DUMMY_NODE_SIZE = 2.0;
71  
72    private byte layoutOrientation;
73  
74    private EdgeMap sourceGroupIds;
75    private EdgeMap targetGroupIds;
76    private EdgeMap sourceCandidates;
77    private EdgeMap targetCandidates;
78    private NodeMap groupingDummiesMap;
79    private NodeMap dummyLayerIds;
80    private HashedDataProviderWrapper groupNodeIdWrapper;
81    private final PortCandidate northCandidate;
82    private final PortCandidate eastCandidate;
83    private final PortCandidate southCandidate;
84    private final PortCandidate westCandidate;
85  
86    /**
87     * Creates a new FlowchartTransformerStage.
88     */
89    FlowchartTransformerStage() {
90      northCandidate = PortCandidate.createCandidate(PortCandidate.NORTH, 0.0);
91      eastCandidate = PortCandidate.createCandidate(PortCandidate.EAST, 0.0);
92      southCandidate = PortCandidate.createCandidate(PortCandidate.SOUTH, 0.0);
93      westCandidate = PortCandidate.createCandidate(PortCandidate.WEST, 0.0);
94    }
95  
96    /**
97     * Returns {@link #canLayoutCore(y.layout.LayoutGraph)}.
98     *
99     * @param graph the graph.
100    * @return {@link #canLayoutCore(y.layout.LayoutGraph)}.
101    */
102   public boolean canLayout(LayoutGraph graph) {
103     return canLayoutCore(graph);
104   }
105 
106   /**
107    * Runs this layout algorithm on the given graph.
108    *
109    * @param graph the graph.
110    */
111   public void doLayout(LayoutGraph graph) {
112     final IncrementalHierarchicLayouter ihl = getIHLCoreLayouter(this);
113     if (ihl == null) {
114       return;
115     }
116 
117     layoutOrientation = ihl.getLayoutOrientation();
118 
119     if (Grouping.isGrouped(graph)) {
120       groupNodeIdWrapper = new HashedDataProviderWrapper(new HashMap(),
121           graph.getDataProvider(GroupingKeys.NODE_ID_DPKEY));
122       graph.addDataProvider(GroupingKeys.NODE_ID_DPKEY, groupNodeIdWrapper);
123     }
124 
125     // Backup all data provide this class may overwrite
126     final DataProvider backupNodeIdDP = graph.getDataProvider(Layouter.NODE_ID_DPKEY);
127     final DataProvider backupNodePcDP = graph.getDataProvider(PortCandidateSet.NODE_DP_KEY);
128     final DataProvider backupSourcePcDP = graph.getDataProvider(PortCandidate.SOURCE_PCLIST_DPKEY);
129     final DataProvider backupTargetPcDP = graph.getDataProvider(PortCandidate.TARGET_PCLIST_DPKEY);
130     final DataProvider backupSourceGroupDP = graph.getDataProvider(PortConstraintKeys.SOURCE_GROUPID_KEY);
131     final DataProvider backupTargetGroupDP = graph.getDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY);
132     final DataProvider backupSourceConstraintsDP = graph.getDataProvider(PortConstraintKeys.SOURCE_PORT_CONSTRAINT_KEY);
133     final DataProvider backupTargetConstraintsDP = graph.getDataProvider(PortConstraintKeys.TARGET_PORT_CONSTRAINT_KEY);
134     graph.removeDataProvider(PortConstraintKeys.SOURCE_PORT_CONSTRAINT_KEY);
135     graph.removeDataProvider(PortConstraintKeys.TARGET_PORT_CONSTRAINT_KEY);
136 
137     final DataProviderAdapter provider = new DataProviderAdapter() {
138       public Object get(Object dataHolder) {
139         return dataHolder;
140       }
141     };
142     graph.addDataProvider(Layouter.NODE_ID_DPKEY, backupNodeIdDP != null ?
143         (DataProvider) new WrappedObjectDataProvider(backupNodeIdDP, provider) : provider);
144 
145     try {
146       // Don't register the new data providers before the configuration is done
147       // since the old data might be needed
148       sourceCandidates = Maps.createHashedEdgeMap();
149       targetCandidates = Maps.createHashedEdgeMap();
150 
151       configurePreferredEdgeDirections(graph);
152 
153       if (graph.getDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY) != null) {
154         dummyLayerIds = Maps.createHashedNodeMap();
155         groupingDummiesMap = Maps.createHashedNodeMap();
156         sourceGroupIds = Maps.createHashedEdgeMap();
157         targetGroupIds = Maps.createHashedEdgeMap();
158 
159         configureInEdgeGrouping(graph);
160 
161         graph.addDataProvider(GROUPING_NODES_DP_KEY, groupingDummiesMap);
162         graph.addDataProvider(PortConstraintKeys.SOURCE_GROUPID_KEY, sourceGroupIds);
163         graph.addDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY, targetGroupIds);
164       }
165 
166       graph.removeDataProvider(PortCandidateSet.NODE_DP_KEY);
167       graph.addDataProvider(PortCandidate.SOURCE_PCLIST_DPKEY, sourceCandidates);
168       graph.addDataProvider(PortCandidate.TARGET_PCLIST_DPKEY, targetCandidates);
169 
170       doLayoutCore(graph);
171 
172     } finally {
173       dummyLayerIds = null;
174       groupingDummiesMap = null;
175       sourceCandidates = null;
176       targetCandidates = null;
177       sourceGroupIds = null;
178       targetGroupIds = null;
179 
180       FlowchartLayouter.restoreDataProvider(graph, backupSourceConstraintsDP,
181           PortConstraintKeys.SOURCE_PORT_CONSTRAINT_KEY);
182       FlowchartLayouter.restoreDataProvider(graph, backupTargetConstraintsDP,
183           PortConstraintKeys.TARGET_PORT_CONSTRAINT_KEY);
184       FlowchartLayouter.restoreDataProvider(graph, backupNodePcDP, PortCandidateSet.NODE_DP_KEY);
185       FlowchartLayouter.restoreDataProvider(graph, backupSourcePcDP, PortCandidate.SOURCE_PCLIST_DPKEY);
186       FlowchartLayouter.restoreDataProvider(graph, backupTargetPcDP, PortCandidate.TARGET_PCLIST_DPKEY);
187       FlowchartLayouter.restoreDataProvider(graph, backupSourceGroupDP, PortConstraintKeys.SOURCE_GROUPID_KEY);
188       FlowchartLayouter.restoreDataProvider(graph, backupTargetGroupDP, PortConstraintKeys.TARGET_GROUPID_KEY);
189       FlowchartLayouter.restoreDataProvider(graph, backupNodeIdDP, Layouter.NODE_ID_DPKEY);
190       if (groupNodeIdWrapper != null) {
191         FlowchartLayouter.restoreDataProvider(graph, groupNodeIdWrapper.getFallback(), GroupingKeys.NODE_ID_DPKEY);
192       }
193 
194       restoreOriginalGraph(graph);
195       removeCollinearBends(graph);
196     }
197   }
198 
199   /**
200    * Configures the in-edge grouping.
201    *
202    * @see InEdgeGroupingConfigurator
203    */
204   private void configureInEdgeGrouping(LayoutGraph graph) {
205     final boolean hasLayerIds = graph.getDataProvider(LAYER_ID_DP_KEY) != null;
206 
207     final InEdgeGroupingConfigurator precedingGroupingConfigurator = new InEdgeGroupingConfigurator();
208     final SucceedingLayersInEdgeGroupingConfigurator succeedingGroupingConfigurator =
209         new SucceedingLayersInEdgeGroupingConfigurator();
210 
211     final EdgeList edgesToReverse = new EdgeList();
212     final EdgeList[] groupingLists = getGroupingLists(graph);
213 
214     for (int i = 0; i < groupingLists.length; i++) {
215       final EdgeList groupingList = groupingLists[i];
216 
217       if (groupingList == null || groupingList.isEmpty()) {
218         continue;
219       }
220 
221       if (hasLayerIds) {
222         final EdgeList[][] layers = getInEdgesByLayer(graph, groupingList);
223         precedingGroupingConfigurator.doGrouping(layers[0], graph);
224         succeedingGroupingConfigurator.doGrouping(layers[1], graph, edgesToReverse);
225       } else {
226         final Node target = groupingList.firstEdge().target();
227         for (EdgeCursor ec = groupingList.edges(); ec.ok(); ec.next()) {
228           targetGroupIds.set(ec.edge(), target);
229         }
230       }
231     }
232 
233     for (EdgeCursor ec = edgesToReverse.edges(); ec.ok(); ec.next()) {
234       final Edge edge = ec.edge();
235       graph.reverseEdge(edge);
236 
237       // Reverse the port candidate data if an original edge was reversed
238       if (groupingDummiesMap.getInt(edge.source()) == 0 || groupingDummiesMap.getInt(edge.target()) == 0) {
239         final Object spc = sourceCandidates.get(edge);
240         sourceCandidates.set(edge, targetCandidates.get(edge));
241         targetCandidates.set(edge, spc);
242       }
243     }
244   }
245 
246   /**
247    * Creates the configuration for the preferred edge directions. This method creates source port candidates according
248    * to the directions defined by the data provider for the key {@link FlowchartLayouter#PREFERRED_DIRECTION_KEY}.
249    */
250   void configurePreferredEdgeDirections(final LayoutGraph graph) {
251     final DataProvider directions = graph.getDataProvider(FlowchartLayouter.PREFERRED_DIRECTION_KEY);
252 
253     if (directions == null) {
254       return;
255     }
256 
257     for (NodeCursor nodeCursor = graph.nodes(); nodeCursor.ok(); nodeCursor.next()) {
258       final Node node = nodeCursor.node();
259 
260       int leftCount = 0;
261       int rightCount = 0;
262       for (Edge edge = node.firstOutEdge(); edge != null; edge = edge.nextOutEdge()) {
263         final int dir = directions.getInt(edge);
264         if (dir == FlowchartLayouter.DIRECTION_LEFT_IN_FLOW) {
265           leftCount++;
266         } else if (dir == FlowchartLayouter.DIRECTION_RIGHT_IN_FLOW) {
267           rightCount++;
268         }
269         sourceCandidates.set(edge, getPortCandidateCollection(dir));
270       }
271 
272       if (leftCount <= 1 && rightCount <= 1) {
273         continue;
274       }
275 
276       // If there is more than one edge to the left or right side,
277       // set less restrictive candidates to allow nicer images.
278       for (Edge edge = node.firstOutEdge(); edge != null; edge = edge.nextOutEdge()) {
279         final int dir = directions.getInt(edge);
280         if (dir == FlowchartLayouter.DIRECTION_LEFT_IN_FLOW || dir == FlowchartLayouter.DIRECTION_RIGHT_IN_FLOW) {
281           sourceCandidates.set(edge, getPortCandidateCollection(FlowchartLayouter.DIRECTION_FLATWISE));
282         }
283       }
284     }
285   }
286 
287   /**
288    * Returns an array of edge lists, each of which contains all edges with the same group Id and the same target node.
289    */
290   private static EdgeList[] getGroupingLists(LayoutGraph graph) {
291     final DataProvider groupIdDP = graph.getDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY);
292 
293     // Partition edges according to group Id
294     final Map idToListsMap = new HashMap();
295     for (EdgeCursor edgeCursor = graph.edges(); edgeCursor.ok(); edgeCursor.next()) {
296       final Edge edge = edgeCursor.edge();
297       final Object id = groupIdDP.get(edge);
298 
299       if (id != null) {
300         if (idToListsMap.containsKey(id)) {
301           ((Collection) idToListsMap.get(id)).add(edge);
302         } else {
303           final EdgeList list = new EdgeList(edge);
304           idToListsMap.put(id, list);
305         }
306       }
307     }
308 
309     // Divide the group Id partitions according to edge target nodes
310     final Collection targetGroupLists = new ArrayList();
311     for (Iterator iterator = idToListsMap.values().iterator(); iterator.hasNext(); ) {
312       final EdgeList groupList = (EdgeList) iterator.next();
313 
314       // Sort the edges according to target nodes such that edges with the same target have consecutive indices
315       groupList.sort(new Comparator() {
316         public int compare(Object o1, Object o2) {
317           return Comparators.compare(((Edge) o1).target().index(), ((Edge) o2).target().index());
318         }
319       });
320 
321       // Add edges to lists and start a new list whenever a new target is found
322       EdgeList targetGroupList = null;
323       for (EdgeCursor edgeCursor = groupList.edges(); edgeCursor.ok(); edgeCursor.next()) {
324         final Edge edge = edgeCursor.edge();
325 
326         if (targetGroupList == null || !edge.target().equals(targetGroupList.firstEdge().target())) {
327           targetGroupList = new EdgeList();
328           targetGroupLists.add(targetGroupList);
329         }
330 
331         targetGroupList.add(edge);
332       }
333     }
334 
335     return (EdgeList[]) targetGroupLists.toArray(new EdgeList[targetGroupLists.size()]);
336   }
337 
338   /**
339    * Returns the in-edges of the given node grouped by layer.
340    *
341    * @return the in-edges of the given node grouped by layer. the first array contains edges from preceding layers, the
342    *         second array edges from succeeding layers.
343    */
344   private EdgeList[][] getInEdgesByLayer(LayoutGraph graph, final EdgeList groupedInEdges) {
345     final boolean hasLayerIds = graph.getDataProvider(LAYER_ID_DP_KEY) != null;
346 
347     final Comparator layerComparator = new Comparator() {
348       public int compare(Object o1, Object o2) {
349         final Node n1 = ((Edge) o1).source();
350         final Node n2 = ((Edge) o2).source();
351         return hasLayerIds ? Comparators.compare(getLayerId(n1), getLayerId(n2)) : 0;
352       }
353     };
354 
355     groupedInEdges.sort(layerComparator);
356 
357     final int referenceLayer = getLayerId(groupedInEdges.firstEdge().target());
358     final List precedingLayers = new ArrayList();
359     final List succeedingLayers = new ArrayList();
360 
361     int previousLayer = -1;
362     for (EdgeCursor ec = groupedInEdges.edges(); ec.ok(); ec.next()) {
363       final Edge edge = ec.edge();
364       final int layer = getLayerId(edge.source());
365       final List layers = layer <= referenceLayer ? precedingLayers : succeedingLayers;
366       if (layer != previousLayer) {
367         layers.add(new EdgeList());
368         previousLayer = layer;
369       }
370       ((Collection) layers.get(layers.size() - 1)).add(edge);
371     }
372 
373     Collections.reverse(succeedingLayers);
374     final EdgeList[][] separatedLayers = new EdgeList[2][];
375     separatedLayers[0] = (EdgeList[]) precedingLayers.toArray(new EdgeList[precedingLayers.size()]);
376     separatedLayers[1] = (EdgeList[]) succeedingLayers.toArray(new EdgeList[succeedingLayers.size()]);
377 
378     return separatedLayers;
379   }
380 
381   /**
382    * Restores the original graph by changing all edges to their original nodes and removing all dummy nodes.
383    */
384   private static void restoreOriginalGraph(LayoutGraph graph) {
385     final DataProvider groupingDummiesDP = graph.getDataProvider(GROUPING_NODES_DP_KEY);
386 
387     if (groupingDummiesDP == null) {
388       return;
389     }
390 
391     graph.removeDataProvider(GROUPING_NODES_DP_KEY);
392 
393     for (NodeCursor nc = new NodeList(graph.nodes()).nodes(); nc.ok(); nc.next()) {
394       final Node node = nc.node();
395 
396       final int groupingDummyId = groupingDummiesDP.getInt(node);
397 
398       if (groupingDummyId == NODE_TYPE_PRECEDING_LAYER) {
399         final Edge outEdge = node.firstOutEdge();
400         final YList outPath = graph.getPathList(outEdge);
401         outPath.set(0, graph.getCenter(node));
402 
403         for (EdgeCursor ec = new EdgeList(node.inEdges()).edges(); ec.ok(); ec.next()) {
404           final Edge edge = ec.edge();
405           final YList inPath = graph.getPathList(edge);
406           inPath.popLast();
407 
408           graph.changeEdge(edge, edge.source(), outEdge.target());
409           graph.setPath(edge, createCombinedList(inPath, outPath));
410         }
411 
412         graph.removeNode(node);
413       } else if (groupingDummyId == NODE_TYPE_SUCCEEDING_LAYER) {
414         final Edge inEdge = node.firstInEdge();
415         final boolean inEdgeFromOriginal = groupingDummiesDP.getInt(inEdge.source()) == 0;
416         final YList inPath = graph.getPathList(inEdge);
417         inPath.set(inPath.size() - 1, graph.getCenter(node));
418 
419         for (EdgeCursor ec = new EdgeList(node.outEdges()).edges(); ec.ok(); ec.next()) {
420           final Edge edge = ec.edge();
421           final boolean outEdgeFromOriginal = groupingDummiesDP.getInt(edge.target()) == 0;
422           final YList outPath = graph.getPathList(edge);
423           outPath.pop();
424 
425           graph.changeEdge(edge, inEdge.source(), edge.target());
426           final YList combinedPath = createCombinedList(inPath, outPath);
427 
428           if (inEdgeFromOriginal && outEdgeFromOriginal) {
429             // change the edge to its original targets -> reverse the edge direction
430             graph.reverseEdge(edge);
431             combinedPath.reverse();
432           }
433 
434           makeOrthogonal(combinedPath);
435           graph.setPath(edge, combinedPath);
436         }
437 
438         graph.removeNode(node);
439       }
440     }
441   }
442 
443   /**
444    * Fixes the orthogonality first and last segment of the edge path.
445    */
446   private static void makeOrthogonal(final YList combinedPath) {
447     if (combinedPath.size() < 2) {
448       return;
449     }
450 
451     final ListCell firstCell = combinedPath.firstCell();
452     final YPoint p1 = (YPoint) firstCell.getInfo();
453     final YPoint p2 = (YPoint) firstCell.succ().getInfo();
454     if (!isOrthogonal(p1, p2)) {
455       final YPoint p3 = makeOrthogonal(p2, p1);
456       combinedPath.insertAfter(p3, firstCell);
457     }
458 
459     final ListCell lastCell = combinedPath.lastCell();
460     final YPoint q1 = (YPoint) lastCell.pred().getInfo();
461     final YPoint q2 = (YPoint) lastCell.getInfo();
462     if (!isOrthogonal(q1, q2)) {
463       final YPoint q3 = makeOrthogonal(q1, q2);
464       combinedPath.insertBefore(q3, lastCell);
465     }
466   }
467 
468   private static YPoint makeOrthogonal(final YPoint p1, final YPoint p2) {
469     return Math.abs(p1.getX() - p2.getX()) < Math.abs(p1.getY() - p2.getY()) ?
470         new YPoint(p2.getX(), p1.getY()) :
471         new YPoint(p1.getX(), p2.getY());
472   }
473 
474   private static boolean isOrthogonal(final YPoint p1, final YPoint p2) {
475     return Math.abs(p1.getX() - p2.getX()) < 0.01 || Math.abs(p1.getY() - p2.getY()) < 0.01;
476   }
477 
478   /**
479    * Removes all collinear bends.
480    */
481   private static void removeCollinearBends(final LayoutGraph graph) {
482     // do not remove bends of self-loops
483     GraphHider selfLoopHider = new GraphHider(graph);
484     selfLoopHider.hideSelfLoops();
485 
486     final RemoveColinearBendsStage collinearBendsStage = new RemoveColinearBendsStage();
487     collinearBendsStage.setRemoveStraightOnly(false);
488     collinearBendsStage.doLayout(graph);
489 
490     selfLoopHider.unhideAll();
491   }
492 
493   /**
494    * Returns the layer Id for the given node, either from the registered data provider or from the internal dummy node
495    * layer Id map.
496    */
497   private int getLayerId(Node node) {
498     return groupingDummiesMap.getInt(node) != 0 ?
499         dummyLayerIds.getInt(node) :
500         node.getGraph().getDataProvider(LAYER_ID_DP_KEY).getInt(node);
501   }
502 
503   /**
504    * Returns whether or not the given node is a grouping dummy created by this class.
505    */
506   static boolean isGroupingDummy(GraphInterface graph, Node node) {
507     final DataProvider provider = graph.getDataProvider(GROUPING_NODES_DP_KEY);
508     return provider != null && provider.getInt(node) > 0;
509   }
510 
511   /**
512    * Returns a collection of port candidate for the given direction.
513    *
514    * @param direction one of hte direction constants in {@FlowchartLayouter}.
515    * @return a collection of port candidate for the given direction.
516    */
517   private Collection getPortCandidateCollection(final int direction) {
518     final Collection collection = new ArrayList(4);
519 
520     if ((direction & FlowchartLayouter.DIRECTION_WITH_THE_FLOW) != 0) {
521       collection.add(getPortCandidateSingleton(PortCandidate.WITH_THE_FLOW));
522     }
523     if ((direction & FlowchartLayouter.DIRECTION_AGAINST_THE_FLOW) != 0) {
524       collection.add(getPortCandidateSingleton(PortCandidate.AGAINST_THE_FLOW));
525     }
526     if ((direction & FlowchartLayouter.DIRECTION_LEFT_IN_FLOW) != 0) {
527       collection.add(getPortCandidateSingleton(PortCandidate.LEFT_IN_FLOW));
528     }
529     if ((direction & FlowchartLayouter.DIRECTION_RIGHT_IN_FLOW) != 0) {
530       collection.add(getPortCandidateSingleton(PortCandidate.RIGHT_IN_FLOW));
531     }
532     return collection;
533   }
534 
535   private PortCandidate getPortCandidateSingleton(final int direction) {
536     switch (getDirectionForLayoutOrientation(layoutOrientation, direction)) {
537       case PortCandidate.NORTH:
538         return northCandidate;
539       case PortCandidate.SOUTH:
540         return southCandidate;
541       case PortCandidate.EAST:
542         return eastCandidate;
543       case PortCandidate.WEST:
544         return westCandidate;
545       default:
546         return null;
547     }
548   }
549 
550   /**
551    * Returns the absolute port candidate direction for the given direction with respect to the layout orientation of
552    * this layout stage.
553    */
554   static int getDirectionForLayoutOrientation(final byte layoutOrientation, final int direction) {
555     if ((int) layoutOrientation == (int) LayoutOrientation.TOP_TO_BOTTOM) {
556       switch (direction) {
557         case PortCandidate.AGAINST_THE_FLOW:
558           return PortCandidate.NORTH;
559         case PortCandidate.WITH_THE_FLOW:
560           return PortCandidate.SOUTH;
561         case PortCandidate.LEFT_IN_FLOW:
562           return PortCandidate.EAST;
563         case PortCandidate.RIGHT_IN_FLOW:
564           return PortCandidate.WEST;
565         default:
566           return -1;
567       }
568     } else {
569       switch (direction) {
570         case PortCandidate.AGAINST_THE_FLOW:
571           return PortCandidate.WEST;
572         case PortCandidate.WITH_THE_FLOW:
573           return PortCandidate.EAST;
574         case PortCandidate.LEFT_IN_FLOW:
575           return PortCandidate.NORTH;
576         case PortCandidate.RIGHT_IN_FLOW:
577           return PortCandidate.SOUTH;
578         default:
579           return -1;
580       }
581     }
582   }
583 
584   /**
585    * Returns the IHL that is set as core layouter of the given layout stage or <code>null</code> if none is set.
586    */
587   private static IncrementalHierarchicLayouter getIHLCoreLayouter(final LayoutStage stage) {
588     final Layouter coreLayouter = stage.getCoreLayouter();
589     if (coreLayouter instanceof IncrementalHierarchicLayouter) {
590       return (IncrementalHierarchicLayouter) coreLayouter;
591     } else if (coreLayouter instanceof LayoutStage) {
592       return getIHLCoreLayouter((LayoutStage) coreLayouter);
593     } else {
594       return null;
595     }
596   }
597 
598   /**
599    * Returns the last element of the given array.
600    */
601   static EdgeList getLast(final EdgeList[] edgeLists) {
602     return edgeLists[edgeLists.length - 1];
603   }
604 
605   /**
606    * Returns a new list that contains the elements of <code>c1.addAll(c2)</code>.
607    */
608   static YList createCombinedList(Collection c1, Collection c2) {
609     final YList yList = new YList(c1);
610     yList.addAll(c2);
611     return yList;
612   }
613 
614   /**
615    * Creates the grouping dummy structure.
616    */
617   class InEdgeGroupingConfigurator {
618 
619     /**
620      * Creates the complete grouping dummy structure.
621      *
622      * @see #createBus(y.layout.LayoutGraph, y.base.EdgeList[])
623      * @see #createGrouping(y.base.EdgeList, y.base.Node, y.layout.LayoutGraph)
624      */
625     public void doGrouping(EdgeList[] layers, LayoutGraph graph) {
626       if (layers.length > 0) {
627         final Node neighborLayerNode = getLast(layers).firstEdge().source();
628         final EdgeList nonBusEdges = createBus(graph, layers);
629 
630         if (nonBusEdges.size() == 1) {
631           handleSingleEdgeGrouping(nonBusEdges.firstEdge(), graph);
632         } else if (nonBusEdges.size() > 1) {
633           createGrouping(nonBusEdges, neighborLayerNode, graph);
634         }
635       }
636     }
637 
638     /**
639      * Returns the grouping type of this class.
640      *
641      * @return {@link #NODE_TYPE_PRECEDING_LAYER}.
642      */
643     int getGroupingType() {
644       return NODE_TYPE_PRECEDING_LAYER;
645     }
646 
647     /**
648      * Changes the given edge to the given nodes, and allows subclasses to reverses its direction if required.
649      */
650     void changeEdge(LayoutGraph graph, Edge edge, Node source, Node target) {
651       graph.changeEdge(edge, source, target);
652     }
653 
654     /**
655      * Sets the grouping Id of the given edge to the appropriate grouping Id data acceptor. By default, this are target
656      * group Ids.
657      */
658     void setGroupId(Edge edge, Object id) {
659       targetGroupIds.set(edge, id);
660     }
661 
662     /**
663      * Creates a port candidates for an edge connecting two bus dummy nodes.
664      */
665     void createBusPortCandidate(Edge edge, LayoutGraph graph) {
666       sourceCandidates.set(edge, createStrongPortCandidate(edge, true, PortCandidate.WITH_THE_FLOW, graph));
667     }
668 
669     /**
670      * Creates a bus structure to group incoming edges of a single node <code>t</code>. These edges have to come from
671      * different layers which are all either in preceding layers or succeeding layers.
672      * <p/>
673      * The bus is created iteratively from the most distant to the nearest layer as long as there is at most one
674      * neighbor in the layer. For edges from preceding layers, in each layer except the most distant one, the bus
675      * consists of a new dummy node <code>d</code>, the original edge which is changed from <code>(v, t)</code> to
676      * <code>(v, d)</code>, one incoming edge from the previous more distant layer and a new dummy edge to the next less
677      * layer or <code>t</code>. For succeeding layers, the direction of the dummy edges is reversed, that is, the edge
678      * direction is always from lower layer index to higher layer index.
679      *
680      * @param graph  the graph.
681      * @param layers all relevant edges grouped by source layer and sorted from distant layer to near.
682      */
683     EdgeList createBus(LayoutGraph graph, EdgeList[] layers) {
684       final Node target = layers[0].firstEdge().target();
685       final EdgeList nonSingletonLayerEdges = new EdgeList();
686 
687       EdgeList unfinishedEdges = new EdgeList();
688       for (int i = 0; i < layers.length; i++) {
689         final EdgeList layer = layers[i];
690 
691         // maybe we should also check if a singleton node is connected to too many such buses
692         if (nonSingletonLayerEdges.isEmpty() && layer.size() == 1) {
693           final Edge edge = layer.firstEdge();
694 
695           if (unfinishedEdges.isEmpty()) {
696             unfinishedEdges.add(edge);
697           } else {
698             final Node layerDummy = createDummyNode(graph, getGroupingType(), getLayerId(edge.source()));
699 
700             // Change unfinished edges to the dummy node
701             for (EdgeCursor ec = unfinishedEdges.edges(); ec.ok(); ec.next()) {
702               final Edge e = ec.edge();
703               changeEdge(graph, e, e.source(), layerDummy);
704               if (unfinishedEdges.size() > 1) {
705                 setGroupId(e, layerDummy);
706               }
707 
708             }
709             unfinishedEdges.clear();
710 
711             // Create a new edge from the dummy to the target
712             final Edge e = graph.createEdge(layerDummy, target);
713             unfinishedEdges.add(e);
714             createBusPortCandidate(e, graph);
715 
716             // Handle this layer's edge
717             if (FlowchartLayouter.isStraightBranch(graph, edge)) {
718               unfinishedEdges.add(edge);
719             } else {
720               changeEdge(graph, edge, edge.source(), layerDummy);
721             }
722           }
723 
724         } else {
725           nonSingletonLayerEdges.addAll(layer);
726         }
727       }
728 
729       if (!unfinishedEdges.isEmpty()) {
730         nonSingletonLayerEdges.addAll(unfinishedEdges);
731       }
732 
733       return nonSingletonLayerEdges;
734     }
735 
736     /**
737      * Handles the grouping of only one edge.
738      */
739     void handleSingleEdgeGrouping(Edge edge, LayoutGraph graph) {
740       targetCandidates.set(edge, createStrongPortCandidate(edge, false, PortCandidate.AGAINST_THE_FLOW, graph));
741     }
742 
743     /**
744      * Creates an edge grouping for the given <code>nonBusEdges</code>. Since grouping works best if the sources of all
745      * nonBusEdges are in the neighboring layer, this method splits edges from more distant layers by adding dummy nodes
746      * in the neighboring layer.
747      */
748     void createGrouping(EdgeList nonBusEdges, Node neighborLayerNode, LayoutGraph graph) {
749       final DataProvider nodeIds = graph.getDataProvider(Layouter.NODE_ID_DPKEY);
750       final Object groupId = nodeIds.get(nonBusEdges.firstEdge().target());
751 
752       for (EdgeCursor ec = nonBusEdges.edges(); ec.ok(); ec.next()) {
753         final Edge edge = ec.edge();
754         setGroupId(edge, groupId);
755         targetCandidates.set(edge, createStrongPortCandidate(edge, false, PortCandidate.AGAINST_THE_FLOW, graph));
756       }
757     }
758 
759     /**
760      * Creates a dummy node, sets its layer Id and registers it in the dummy marker map.
761      */
762     Node createDummyNode(final LayoutGraph graph, int groupingType, int layerId) {
763       final Node dummyNode = graph.createNode();
764       groupingDummiesMap.setInt(dummyNode, groupingType);
765       dummyLayerIds.setInt(dummyNode, layerId);
766 
767       if (groupNodeIdWrapper != null) {
768         groupNodeIdWrapper.getMap().put(dummyNode, dummyNode);
769       }
770 
771       graph.setSize(dummyNode, DUMMY_NODE_SIZE, DUMMY_NODE_SIZE);
772 
773       return dummyNode;
774     }
775 
776     /**
777      * Creates a singleton collection containing one port candidate for the specified end node of the given edge.
778      */
779     Collection createStrongPortCandidate(final Edge edge, final boolean source, final int dir, LayoutGraph graph) {
780       NodeLayout nl = graph.getLayout(source ? edge.source() : edge.target());
781       final int direction = getDirectionForLayoutOrientation(layoutOrientation, dir);
782       final YPoint p;
783       switch (direction) {
784         case PortCandidate.NORTH:
785         default:
786           p = new YPoint(0.0, -0.5 * nl.getHeight());
787           break;
788         case PortCandidate.SOUTH:
789           p = new YPoint(0.0, 0.5 * nl.getHeight());
790           break;
791         case PortCandidate.EAST:
792           p = new YPoint(0.5 * nl.getWidth(), 0.0);
793           break;
794         case PortCandidate.WEST:
795           p = new YPoint(-0.5 * nl.getWidth(), 0.0);
796           break;
797       }
798 
799       return Collections.singleton(PortCandidate.createCandidate(p.getX(), p.getY(), direction));
800     }
801   }
802 
803   /**
804    * An {@link InEdgeGroupingConfigurator} for edges to succeeding layers. Its main difference is the creation of a same
805    * layer dummy node. Apart from that, this class has to set other port candidate directions and reverses some edges.
806    */
807   class SucceedingLayersInEdgeGroupingConfigurator extends InEdgeGroupingConfigurator {
808     private EdgeList edgesToReverse;
809 
810     SucceedingLayersInEdgeGroupingConfigurator() {
811     }
812 
813     /**
814      * Creates the complete grouping dummy structure. This class stores all edges that must be reversed after the
815      * creation of all dummy structures in the given list.
816      * <p/>
817      * Use this method instead of {@link #doGrouping(y.base.EdgeList[], y.layout.LayoutGraph)}.
818      *
819      * @see #createBus(y.layout.LayoutGraph, y.base.EdgeList[])
820      * @see #createGrouping(y.base.EdgeList, y.base.Node, y.layout.LayoutGraph)
821      */
822     public void doGrouping(EdgeList[] layers, LayoutGraph graph, EdgeList edgesToReverse) {
823       try {
824         this.edgesToReverse = edgesToReverse;
825         super.doGrouping(layers, graph);
826       } finally {
827         this.edgesToReverse = null;
828       }
829     }
830 
831     /**
832      * This method must not be called directly since it omits the required list for edges to reverse.
833      */
834     public void doGrouping(EdgeList[] layers, LayoutGraph graph) {
835       if (edgesToReverse == null) {
836         throw new IllegalStateException("Collection of edges to reverse is not set.");
837       }
838       super.doGrouping(layers, graph);
839     }
840 
841     /**
842      * Returns the grouping type of this class.
843      *
844      * @return {@link #NODE_TYPE_SUCCEEDING_LAYER}.
845      */
846     int getGroupingType() {
847       return NODE_TYPE_SUCCEEDING_LAYER;
848     }
849 
850     /**
851      * Changes the given edge to the given nodes and reverses its direction.
852      */
853     void changeEdge(LayoutGraph graph, Edge edge, Node source, Node target) {
854       super.changeEdge(graph, edge, source, target);
855       edgesToReverse.add(edge);
856     }
857 
858     /**
859      * Sets the grouping Id of the given edge to the appropriate grouping Id data acceptor. This are source group Ids.
860      */
861     void setGroupId(Edge edge, Object id) {
862       sourceGroupIds.set(edge, id);
863     }
864 
865     /**
866      * Creates a port candidate for an edge connecting two bus dummy nodes.
867      */
868     void createBusPortCandidate(Edge edge, LayoutGraph graph) {
869       targetCandidates.set(edge, createStrongPortCandidate(edge, true, PortCandidate.AGAINST_THE_FLOW, graph));
870     }
871 
872     /**
873      * Creates a strong North candidate and reverses the edge if it comes from a dummy.
874      */
875     void handleSingleEdgeGrouping(Edge edge, LayoutGraph graph) {
876       if (groupingDummiesMap.getInt(edge.source()) > 0) {
877         edgesToReverse.add(edge);
878       }
879       targetCandidates.set(edge, createStrongPortCandidate(edge, false, PortCandidate.AGAINST_THE_FLOW, graph));
880     }
881 
882     /**
883      * Creates an edge grouping for the given <code>nonBusEdges</code>. Since grouping works best if the sources of all
884      * nonBusEdges are in the neighboring layer, this method splits edges from more distant layers by adding dummy nodes
885      * in the neighboring layer.
886      */
887     void createGrouping(EdgeList nonBusEdges, Node neighborLayerNode, LayoutGraph graph) {
888       prepareForGrouping(nonBusEdges, graph);
889 
890       final Node target = nonBusEdges.firstEdge().target();
891       final Object groupId = graph.getDataProvider(Layouter.NODE_ID_DPKEY).get(target);
892       final int neighborLayerIndex = getLayerId(neighborLayerNode);
893 
894       for (EdgeCursor ec = nonBusEdges.edges(); ec.ok(); ec.next()) {
895         final Edge edge = ec.edge();
896 
897         final Edge groupingEdge;
898         if (neighborLayerIndex == getLayerId(edge.source())) {
899           groupingEdge = edge;
900         } else {
901           final Node layerDummy = createDummyNode(graph, getGroupingType(), neighborLayerIndex);
902           changeEdge(graph, edge, edge.source(), layerDummy);
903 
904           groupingEdge = graph.createEdge(layerDummy, target);
905         }
906 
907         edgesToReverse.add(groupingEdge);
908         setGroupId(groupingEdge, groupId);
909         sourceCandidates.set(groupingEdge,
910             createStrongPortCandidate(groupingEdge, false, PortCandidate.WITH_THE_FLOW, graph));
911       }
912     }
913 
914     /**
915      * Creates a same layer dummy node for nicer grouping.
916      */
917     void prepareForGrouping(EdgeList nonBusEdges, LayoutGraph graph) {
918       final Node originalTarget = nonBusEdges.firstEdge().target();
919       final Node target = createDummyNode(graph, getGroupingType(), getLayerId(originalTarget));
920 
921       final Edge sameLayerEdge = graph.createEdge(originalTarget, target);
922       sourceCandidates.set(sameLayerEdge,
923           createStrongPortCandidate(sameLayerEdge, true, PortCandidate.AGAINST_THE_FLOW, graph));
924 
925       for (EdgeCursor ec = nonBusEdges.edges(); ec.ok(); ec.next()) {
926         final Edge edge = ec.edge();
927         graph.changeEdge(edge, edge.source(), target);
928       }
929     }
930 
931   }
932 
933   /**
934    * A two-stage data provider which returns the value of <code>map.get(key)</code> if the key is contained in the given
935    * map, and <code>fallback.get(key)</code> otherwise.
936    */
937   static class HashedDataProviderWrapper implements DataProvider {
938     private final Map map;
939     private final DataProvider fallback;
940 
941     HashedDataProviderWrapper(Map map, DataProvider fallback) {
942       this.map = map;
943       this.fallback = fallback;
944     }
945 
946     Map getMap() {
947       return map;
948     }
949 
950     public DataProvider getFallback() {
951       return fallback;
952     }
953 
954     public Object get(Object dataHolder) {
955       return map.containsKey(dataHolder) ? map.get(dataHolder) : fallback.get(dataHolder);
956     }
957 
958     public int getInt(Object dataHolder) {
959       return map.containsKey(dataHolder) ?
960           ((Number) map.get(dataHolder)).intValue() :
961           fallback.getInt(dataHolder);
962     }
963 
964     public double getDouble(Object dataHolder) {
965       return map.containsKey(dataHolder) ?
966           ((Number) map.get(dataHolder)).doubleValue() :
967           fallback.getDouble(dataHolder);
968     }
969 
970     public boolean getBool(Object dataHolder) {
971       return map.containsKey(dataHolder) ?
972           ((Boolean) map.get(dataHolder)).booleanValue() :
973           fallback.getBool(dataHolder);
974     }
975   }
976 }
977