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.orgchart;
15  
16  import y.algo.Trees;
17  import y.base.DataProvider;
18  import y.base.EdgeCursor;
19  import y.base.ListCell;
20  import y.base.Node;
21  import y.base.NodeCursor;
22  import y.base.NodeMap;
23  import y.base.YList;
24  import y.geom.LineSegment;
25  import y.geom.YLineSegmentCursor;
26  import y.geom.YPoint;
27  import y.geom.YPointPath;
28  import y.layout.AbstractLayoutStage;
29  import y.layout.EdgeLayout;
30  import y.layout.LayoutGraph;
31  import y.layout.Layouter;
32  import y.layout.tree.AssistantPlacer;
33  import y.layout.tree.DefaultNodePlacer;
34  import y.layout.tree.GenericTreeLayouter;
35  import y.layout.tree.LeftRightPlacer;
36  import y.layout.tree.NodePlacer;
37  import y.util.Maps;
38  
39  /**
40   * A layout algorithm for tree-structured organization charts. It allows to specify different 
41   * layout strategies for the child nodes of a node. Furthermore, it supports special placement for
42   * nodes that are marked as assistants,
43   */
44  public class OrgChartLayouter implements Layouter {
45  
46    /**
47     * Child layout specifier. The children of a node shall be arranged left to right on the same layer.
48     */
49    public static final Object CHILD_LAYOUT_SAME_LAYER = "SAME_LAYER";
50    
51    /**
52     * Child layout specifier. The children of a node shall be arranged below each other and placed left of a common bus.
53     */
54    public static final Object CHILD_LAYOUT_LEFT_BELOW = "LEFT_BELOW";
55  
56    /**
57     * Child layout specifier. The children of a node shall be arranged below each other and placed right of a common bus.
58     */
59    public static final Object CHILD_LAYOUT_RIGHT_BELOW = "RIGHT_BELOW";
60    
61    /**
62     * Child layout specifier. The children of a node shall be arranged on both sides of a common vertical bus. Children on both sides
63     * are placed below each.    
64     */
65    public static final Object CHILD_LAYOUT_BELOW = "BELOW";
66    
67    /**
68     * DataProvider key used to register a DataProvider with the input graph. For each node in the graph 
69     * the registered DataProvider returns either of {@link #CHILD_LAYOUT_BELOW}, {@link #CHILD_LAYOUT_LEFT_BELOW}, 
70     * {@link #CHILD_LAYOUT_RIGHT_BELOW}, or {@link #CHILD_LAYOUT_SAME_LAYER}.
71     */
72    public static final Object CHILD_LAYOUT_DPKEY = "OrgChartLayouter#CHILD_LAYOUT_DPKEY";
73    
74    /**
75     * DataProvider key used to register a DataProvider with the input graph. For each node in the graph 
76     * the registered DataProvider returns a boolean value that signifies whether or not the
77     * node is to be considered an assistant to its parent node. Assistants are always placed along to the left or right of the
78     * the vertical bus leaving the parent node. For non-assistant child nodes the child layout specified for the
79     * parent node will be applied.
80     */
81    public static final Object ASSISTANT_DPKEY = "OrgChartLayouter#ASSISTANT_DPKEY";
82    
83    private boolean duplicateBendsOnSharedBus = false;
84  
85  
86    /**
87     * Sets whether or not to duplicate the control points of the returned edge paths 
88     * that are placed on an path segment of another edge. For example, if an edge
89     * has the control points, [a,b,c], and a and b are placed on a shared bus, then the
90     * resulting edge path is [a,a,b,b,c]. Duplicating control points on a shared bus,
91     * allows the edge rendering facility to treat such control points differently.
92     * By default this feature is disabled.
93     */
94    public void setDuplicateBendsOnSharedBus(boolean duplicateBendsOnSharedBus) {
95      this.duplicateBendsOnSharedBus = duplicateBendsOnSharedBus;
96    }
97  
98    /**
99     * Returns whether or not to duplicate the control points of the returned edge paths 
100    * that are placed on an path segment of another edge. For example, if an edge 
101    * has the control points, [a,b,c], and a and b are placed on a shared bus, then the
102    * resulting edge path is [a,a,b,b,c]. Duplicating control points on a shared bus,
103    * allows the edge rendering facility to treat such control points differently.
104    * By default this feature is disabled.
105    */
106   public boolean isDuplicateBendsOnSharedBus() {
107     return duplicateBendsOnSharedBus;
108   }
109 
110   /**
111    * Assigns coordinates to the elements of the input graph.
112    */
113   public void doLayout(LayoutGraph graph) {    
114     GenericTreeLayouter gtl = new GenericTreeLayouter();
115     gtl.setGroupingSupported(true);
116     configureNodePlacers(graph);    
117     gtl.doLayout(graph);
118     if(isDuplicateBendsOnSharedBus()) {
119       Layouter bendDuplicator = new BendDuplicatorStage(null);
120       bendDuplicator.doLayout(graph);
121     }
122   }
123   
124   /**
125    * Configures the layout algorithm using the information provided by the
126    * DataProviders registered with the keys {@link #ASSISTANT_DPKEY} and {@link #CHILD_LAYOUT_DPKEY}.   
127    */
128   protected void configureNodePlacers(LayoutGraph graph) {    
129     DataProvider childLayoutDP = graph.getDataProvider(CHILD_LAYOUT_DPKEY);
130     NodeMap nodePlacerMap = Maps.createHashedNodeMap();     
131     if(childLayoutDP != null) {
132       graph.addDataProvider(GenericTreeLayouter.NODE_PLACER_DPKEY, nodePlacerMap);
133       for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
134         Node n = nc.node();
135         nodePlacerMap.set(n, createNodePlacer(childLayoutDP.get(n)));        
136       }
137       graph.addDataProvider(GenericTreeLayouter.NODE_PLACER_DPKEY, nodePlacerMap);
138     }
139 
140     DataProvider assistDP = graph.getDataProvider(ASSISTANT_DPKEY);
141     for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
142       Node n = nc.node();        
143       if(assistDP != null && assistDP.getBool(n)) {
144         if(n.inDegree() > 0 && n.firstInEdge().source().outDegree() > 1) {
145           AssistantPlacer placer = new AssistantPlacer();           
146           NodePlacer parentPlacer = (NodePlacer) nodePlacerMap.get(n.firstInEdge().source());
147           placer.setChildNodePlacer(parentPlacer);
148           nodePlacerMap.set(n.firstInEdge().source(), placer);
149         }
150       }
151     }
152     graph.addDataProvider(AssistantPlacer.ASSISTANT_DPKEY, assistDP);     
153   }
154   
155   /**
156    * Creates a NodePlacer for the given child layout specifier.
157    */
158   protected NodePlacer createNodePlacer(Object childLayout) {    
159     if(childLayout == CHILD_LAYOUT_LEFT_BELOW) {      
160       DefaultNodePlacer placer = new DefaultNodePlacer(DefaultNodePlacer.PLACEMENT_HORIZONTAL_DOWNWARD, DefaultNodePlacer.ALIGNMENT_CENTER, DefaultNodePlacer.ROUTING_FORK, 20.0d, 80.d);
161       placer.setChildPlacement(DefaultNodePlacer.PLACEMENT_VERTICAL_TO_LEFT);
162       placer.setRootAlignment(DefaultNodePlacer.ALIGNMENT_LEADING_ON_BUS);
163       placer.setRoutingStyle(DefaultNodePlacer.ROUTING_FORK_AT_ROOT);
164       return placer;
165     }
166     else if(childLayout == CHILD_LAYOUT_RIGHT_BELOW) {
167       DefaultNodePlacer placer = new DefaultNodePlacer(DefaultNodePlacer.PLACEMENT_HORIZONTAL_DOWNWARD, DefaultNodePlacer.ALIGNMENT_CENTER, DefaultNodePlacer.ROUTING_FORK, 20.0d, 80.d);
168       placer.setChildPlacement(DefaultNodePlacer.PLACEMENT_VERTICAL_TO_RIGHT);
169       placer.setRootAlignment(DefaultNodePlacer.ALIGNMENT_LEADING_ON_BUS);
170       placer.setRoutingStyle(DefaultNodePlacer.ROUTING_FORK_AT_ROOT);
171       return placer;
172     }
173     else if(childLayout == CHILD_LAYOUT_BELOW) {
174       LeftRightPlacer placer = new LeftRightPlacer();
175       placer.setPlaceLastOnBottom(false);
176       return placer;
177     }
178     else { //default
179       DefaultNodePlacer placer = new DefaultNodePlacer();
180       placer.setChildPlacement(DefaultNodePlacer.PLACEMENT_HORIZONTAL_DOWNWARD);
181       placer.setRootAlignment(DefaultNodePlacer.ALIGNMENT_MEDIAN);
182       return placer;
183     }        
184   }
185     
186   /**
187    * The input graph needs to be a tree or a collection of trees.
188    */
189   public boolean canLayout(LayoutGraph graph) {    
190     return Trees.isForest(graph); //simplified
191   }
192   
193   /**
194    * LayoutStage that duplicates bends that share a common bus.
195    */
196   static class BendDuplicatorStage extends AbstractLayoutStage {
197 
198     public BendDuplicatorStage() {
199     }
200 
201     public BendDuplicatorStage(Layouter coreLayouter) {
202       super(coreLayouter);
203     }
204     
205     public boolean canLayout(LayoutGraph graph) {
206       return true;
207     }
208 
209     public void doLayout(LayoutGraph graph) {
210       doLayoutCore(graph);
211       
212       for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
213         Node n = nc.node();
214         for(EdgeCursor ec = n.outEdges(); ec.ok(); ec.next()) {
215           boolean lastSegmentOverlap = false;      
216           EdgeLayout er = graph.getEdgeLayout(ec.edge());
217           
218           if(er.pointCount() > 0) {
219             //last bend point
220             YPoint bendPoint = er.getPoint(er.pointCount()-1);
221             
222             loop:for(EdgeCursor ecc = n.outEdges(); ecc.ok(); ecc.next()) {
223               
224               if(ecc.edge() != ec.edge()) {
225                 YPointPath path = graph.getPath(ecc.edge());
226                 for(YLineSegmentCursor lc = path.lineSegments(); lc.ok(); lc.next()) {
227                   LineSegment seg = lc.lineSegment();
228                   if(seg.contains(bendPoint)) {
229                     lastSegmentOverlap = true;
230                     break loop;
231                   }
232                 }
233               }
234             }      
235           }
236           
237           YList points = graph.getPointList(ec.edge());
238           for(ListCell c = points.firstCell(); c != null; c = c.succ()) {
239             YPoint p = (YPoint) c.getInfo();
240             if(c.succ() == null && !lastSegmentOverlap) {
241               break;
242             }
243             points.insertBefore(new YPoint(p.x,p.y), c);
244           }
245           graph.setPoints(ec.edge(), points);
246         }
247       }    
248     }
249   }
250 }
251