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