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.mindmap;
29  
30  import y.base.DataProvider;
31  import y.base.Edge;
32  import y.base.EdgeCursor;
33  import y.base.EdgeMap;
34  import y.base.Node;
35  import y.base.NodeCursor;
36  import y.base.NodeList;
37  import y.base.NodeMap;
38  import y.geom.YPoint;
39  import y.layout.AbstractLayoutStage;
40  import y.layout.FixNodeLayoutStage;
41  import y.layout.LayoutGraph;
42  import y.layout.Layouter;
43  import y.layout.PortConstraint;
44  import y.layout.PortConstraintKeys;
45  import y.layout.tree.AbstractRotatableNodePlacer;
46  import y.layout.tree.DefaultPortAssignment;
47  import y.layout.tree.DelegatingNodePlacer;
48  import y.layout.tree.GenericTreeLayouter;
49  import y.layout.tree.LayeredNodePlacer;
50  import y.layout.tree.TreeReductionStage;
51  import y.util.DataProviderAdapter;
52  import y.util.GraphHider;
53  import y.view.Graph2D;
54  import y.view.Graph2DLayoutExecutor;
55  import y.view.Graph2DView;
56  import y.view.NodeRealizer;
57  
58  import java.util.Comparator;
59  
60  /**
61   * Provides utility methods for automatically arranging a mind map.
62   */
63  class LayoutUtil {
64    /**
65     * Prevent instantiation of utility class.
66     */
67    private LayoutUtil() {
68    }
69  
70    /**
71     * Registers the data providers for node placer and child comparators
72     * necessary for arranging the specified mind map in a tree-like fashion.
73     * @param graph the mind map.
74     */
75    static void addPlacersAndComparators( final Graph2D graph ) {
76      final DataProvider nodePlacers = new NodePlacerProvider();
77      graph.addDataProvider(GenericTreeLayouter.NODE_PLACER_DPKEY, nodePlacers);
78      graph.addDataProvider(
79              GenericTreeLayouter.CHILD_COMPARATOR_DPKEY,
80              new ChildComparatorProvider());
81    }
82  
83    /**
84     * Registers the data map that determines if a mind map item is
85     * placed to the left or to the right of the root item.
86     * @param graph the mind map.
87     * @see #getLeftRightMap(y.view.Graph2D)
88     */
89    static void addLeftRightMap( final Graph2D graph, final NodeMap map ) {
90      graph.addDataProvider(DelegatingNodePlacer.LEFT_RIGHT_DPKEY, map);
91    }
92  
93    /**
94     * Returns the data map that determines if a mind map item is
95     * placed to the left or to the right of the root item.
96     * @param graph the mind map.
97     */
98    static NodeMap getLeftRightMap( final Graph2D graph ) {
99      return (NodeMap) graph.getDataProvider(DelegatingNodePlacer.LEFT_RIGHT_DPKEY);
100   }
101 
102   /**
103    * Registers the data map that determines whether or not a connection is
104    * a cross-reference.
105    * @param graph the mind map.
106    * @see #getCrossReferencesMap(y.view.Graph2D)
107    */
108   static void addCrossReferencesMap( final Graph2D graph, final EdgeMap map ) {
109     graph.addDataProvider(TreeReductionStage.NON_TREE_EDGES_DPKEY, map);
110   }
111 
112   /**
113    * Returns the data map that determines whether or not a connection is
114    * a cross-reference.
115    * @param graph the mind map.
116    */
117   static EdgeMap getCrossReferencesMap( final Graph2D graph ) {
118     return (EdgeMap) graph.getDataProvider(TreeReductionStage.NON_TREE_EDGES_DPKEY);
119   }
120 
121   /**
122    * Arranges the specified mind map.
123    * @param graph the mind map that is arranged.
124    */
125   static void layout( final Graph2D graph ) {
126     layout(graph, null);
127   }
128 
129   /**
130    * Arranges the subtree rooted a the specified node.
131    * @param graph the mind map that is arranged.
132    * @param node the root item of the subtree that is arranged.
133    */
134   static void layoutSubtree( final Graph2D graph, final Node node ) {
135     layout(graph, node);
136     graph.updateViews();
137   }
138 
139 
140   /**
141    * Arranges the specified mind map in a tree-like fashion.
142    * @param graph the mind map that is arranged.
143    * @param node if <code>null</code>, the mind map is arranged from scratch;
144    * otherwise only the subtree rooted at the given node is arranged.
145    */
146   private static void layout( final Graph2D graph, final Node node ) {
147     //to make the graph look like a mind map, the edges have to connect at the underline of the items.
148     //Therefor we have to put the source and target points to the bottom corners.
149     final ViewModel model = ViewModel.instance;
150     for (EdgeCursor edgeCursor = graph.edges(); edgeCursor.ok(); edgeCursor.next()) {
151       final Edge edge = edgeCursor.edge();
152       //cross edges should start and end at the item center
153       if (model.isCrossReference(edge)) {
154         graph.setSourcePointRel(edge, new YPoint(0, 0));
155         graph.setTargetPointRel(edge, new YPoint(0, 0));
156       } else {
157         final Node source = edge.source();
158         final Node target = edge.target();
159         final NodeRealizer sourceRealizer = graph.getRealizer(source);
160         final NodeRealizer targetRealizer = graph.getRealizer(target);
161         final YPoint p;
162         final YPoint p2;
163         //when an item is on the left side, the bottom right corner is a target port,
164         //on the right side it is a source port
165         if (model.isLeft(target)) {
166           p = new YPoint(-sourceRealizer.getWidth() * 0.5, sourceRealizer.getHeight() * 0.5);
167           p2 = new YPoint(targetRealizer.getWidth() * 0.5, targetRealizer.getHeight() * 0.5);
168         } else {
169           p = new YPoint(sourceRealizer.getWidth() * 0.5, sourceRealizer.getHeight() * 0.5);
170           p2 = new YPoint(-targetRealizer.getWidth() * 0.5, targetRealizer.getHeight() * 0.5);
171         }
172         //when edges start at the bottom corner at the center item, it would look weired,
173         //so we exclude the center item here
174         if (!model.isRoot(source)) {
175           graph.setSourcePointRel(edge, p);
176         } else {
177           graph.setSourcePointRel(edge, YPoint.ORIGIN);
178         }
179         graph.setTargetPointRel(edge, p2);
180       }
181     }
182 
183     //Force the edges to connect to the source ports, coming from the right side
184     graph.addDataProvider(PortConstraintKeys.SOURCE_PORT_CONSTRAINT_KEY, new DataProviderAdapter() {
185       public Object get( Object dataHolder ) {
186         if (dataHolder instanceof Edge) {
187           //again, exclude cross edges as they should come from any side
188           if (ViewModel.instance.isCrossReference((Edge) dataHolder)) {
189             return PortConstraint.create(PortConstraint.ANY_SIDE, true);
190             //the right direction depends on the side an item is placed
191           } else {
192             final boolean isLeftSide = ViewModel.instance.isLeft(((Edge) dataHolder).target());
193             if (isLeftSide) {
194               return PortConstraint.create(PortConstraint.WEST, true);
195             } else {
196               return PortConstraint.create(PortConstraint.EAST, true);
197             }
198           }
199         }
200         return null;
201       }
202     });
203     //the same for target ports
204     graph.addDataProvider(PortConstraintKeys.TARGET_PORT_CONSTRAINT_KEY, new DataProviderAdapter() {
205       public Object get( Object dataHolder ) {
206         if (dataHolder instanceof Edge) {
207           if (ViewModel.instance.isCrossReference((Edge) dataHolder)) {
208             return PortConstraint.create(PortConstraint.ANY_SIDE, true);
209           } else {
210             boolean isLeftSide = ViewModel.instance.isLeft(((Edge) dataHolder).target());
211             if (isLeftSide) {
212               return PortConstraint.create(PortConstraint.EAST, true);
213             } else {
214               return PortConstraint.create(PortConstraint.WEST, true);
215             }
216           }
217         }
218         return null;
219       }
220     });
221     GenericTreeLayouter treeLayouter = new GenericTreeLayouter();
222     treeLayouter.setDefaultPortAssignment(new DefaultPortAssignment(DefaultPortAssignment.MODE_PORT_CONSTRAINTS));
223 
224     //Cross Edges do not belong to the tree structure
225     TreeReductionStage trs = new TreeReductionStage();
226     treeLayouter.appendStage(trs);
227 
228     Layouter layouter = treeLayouter;
229 
230     final DataProviderAdapter rootDp = new DataProviderAdapter() {
231       final ViewModel model = ViewModel.instance;
232       public boolean getBool( final Object dataHolder ) {
233         return model.isRoot((Node) dataHolder);
234       }
235     };
236 
237     final Graph2DLayoutExecutor layoutExecutor = new Graph2DLayoutExecutor();
238     layoutExecutor.getLayoutMorpher().setKeepZoomFactor(true);
239     layoutExecutor.getLayoutMorpher().setPreferredDuration(300);
240     layoutExecutor.getLayoutMorpher().setEasedExecution(true);
241 
242     if (node != null) {
243       layouter = new SubtreeLayoutStage(layouter);
244       layoutExecutor.setMode(Graph2DLayoutExecutor.BUFFERED);
245       graph.addDataProvider(SubtreeLayoutStage.GLOBAL_ROOT_DPKEY, rootDp);
246       graph.addDataProvider(SubtreeLayoutStage.SUBTREE_ROOT_DPKEY, new DataProviderAdapter() {
247         public boolean getBool( final Object dataHolder ) {
248           return dataHolder == node;
249         }
250       });
251     } else {
252       layouter = new FixNodeLayoutStage(treeLayouter);
253       layoutExecutor.setMode(Graph2DLayoutExecutor.ANIMATED);
254       graph.addDataProvider(FixNodeLayoutStage.FIXED_NODE_DPKEY, rootDp);
255     }
256 
257     final Object view = graph.getCurrentView();
258     if (view instanceof Graph2DView) {
259       layoutExecutor.doLayout((Graph2DView) view, layouter);
260     } else {
261       layoutExecutor.doLayout(graph, layouter);
262     }
263 
264     if (node != null) {
265       graph.removeDataProvider(SubtreeLayoutStage.SUBTREE_ROOT_DPKEY);
266       graph.removeDataProvider(SubtreeLayoutStage.GLOBAL_ROOT_DPKEY);
267     } else {
268       graph.removeDataProvider(FixNodeLayoutStage.FIXED_NODE_DPKEY);
269     }
270   }
271 
272 
273   /**
274    * Applies the core layout algorithm to a subtree of the given min map.
275    * The subtree that is arranged is specified by the data providers
276    * {@link #SUBTREE_ROOT_DPKEY} and
277    * {@link TreeReductionStage#NON_TREE_EDGES_DPKEY}.
278    */
279   private static class SubtreeLayoutStage extends AbstractLayoutStage {
280     /**
281      * Data provider key to register a data provider that identifies the
282      * global root item of the mind map.
283      */
284     static final Object GLOBAL_ROOT_DPKEY =
285             "demo.view.mindmap.MindMapUtil.GLOBAL_ROOT_DPKEY";
286     /**
287      * Data provider key to register a data provider that identifies the
288      * root item of the subtree that has to be arranged.
289      */
290     static final Object SUBTREE_ROOT_DPKEY =
291             "demo.view.mindmap.MindMapUtil.SUBTREE_ROOT_DPKEY";
292 
293     /**
294      * Initializes a new <code>SubtreeLayoutStage</code> for the given
295      * core layout algorithm.
296      * @param core the core layout algorithm that actually calculates
297      * the layout.
298      */
299     SubtreeLayoutStage( final Layouter core ) {
300       super(new FixNodeLayoutStage(core));
301     }
302 
303     public boolean canLayout( final LayoutGraph graph ) {
304       return canLayoutCore(graph);
305     }
306 
307     public void doLayout( final LayoutGraph graph ) {
308       GraphHider hider = new GraphHider(graph);
309 
310       // remove all non-tree edges
311       final DataProvider crossEdges = graph.getDataProvider(TreeReductionStage.NON_TREE_EDGES_DPKEY);
312       if (crossEdges != null) {
313         for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
314           final Edge edge = ec.edge();
315           if (crossEdges.getBool(edge)) {
316             hider.hide(edge);
317           }
318         }
319       }
320 
321       // determine the root of the tree
322       final DataProvider isRootNodeProvider = graph.getDataProvider(GLOBAL_ROOT_DPKEY);
323       Node root = null;
324       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
325         final Node node = nc.node();
326         if (isRootNodeProvider.getBool(node)) {
327           root = node;
328           break;
329         }
330       }
331 
332       // remove all elements that do not belong to the subtree that has to be
333       // arranged
334       NodeList stack = new NodeList(root);
335       final DataProvider subtreeRootProvider = graph.getDataProvider(SUBTREE_ROOT_DPKEY);
336       while (!stack.isEmpty()) {
337         Node currentNode = stack.popNode();
338         if (!subtreeRootProvider.getBool(currentNode)) {
339           for (EdgeCursor ec = currentNode.outEdges(); ec.ok(); ec.next()) {
340             stack.push(ec.edge().target());
341           }
342           hider.hide(currentNode);
343         }
344       }
345 
346 
347       // ensure that the subtree root keeps its current location
348       graph.addDataProvider(FixNodeLayoutStage.FIXED_NODE_DPKEY, subtreeRootProvider);
349 
350       // arrange the remaining subtree
351       doLayoutCore(graph);
352 
353       graph.removeDataProvider(FixNodeLayoutStage.FIXED_NODE_DPKEY);
354 
355 
356       // re-insert all previous hidden elements
357       hider.unhideAll();
358     }
359   }
360 
361   /**
362    * Provides different {@link y.layout.tree.NodePlacer} instances for the items
363    * in a main map.
364    * For the root item, {@link DelegatingNodePlacer} is used to place the root
365    * item's children to the left and to the right of the root item.
366    * For all other items, {@link LayeredNodePlacer} is used.
367    */
368   private static final class NodePlacerProvider extends DataProviderAdapter {
369     private final DelegatingNodePlacer rootPlacer;
370 
371     NodePlacerProvider() {
372       rootPlacer = new DelegatingNodePlacer(
373               AbstractRotatableNodePlacer.Matrix.DEFAULT,
374               newPlacer(AbstractRotatableNodePlacer.Matrix.ROT270),
375               newPlacer(AbstractRotatableNodePlacer.Matrix.ROT90));
376       rootPlacer.setSpacing(1);
377     }
378 
379     public Object get( final Object dataHolder ) {
380       final Node node = (Node) dataHolder;
381       if (ViewModel.instance.isRoot(node)) {
382         return rootPlacer;
383       } else {
384         if (ViewModel.instance.isLeft(node)) {
385           return rootPlacer.getPlacerUpperLeft();
386         } else {
387           return rootPlacer.getPlacerLowerRight();
388         }
389       }
390     }
391 
392     private static LayeredNodePlacer newPlacer(
393             final AbstractRotatableNodePlacer.Matrix matrix
394     ) {
395       final LayeredNodePlacer placer = new LayeredNodePlacer(matrix, matrix);
396       placer.setRoutingStyle(LayeredNodePlacer.ORTHOGONAL_STYLE);
397       placer.setRootAlignment(AbstractRotatableNodePlacer.RootAlignment.CENTER);
398       placer.setSpacing(10);
399       placer.setLayerSpacing(45);
400       placer.setVerticalAlignment(0);
401       return placer;
402     }
403   }
404 
405   /**
406    * Provides {@link java.util.Comparator} instances used by the
407    * {@link LayeredNodePlacer} instances to determine the order of the
408    * items in each layer.
409    */
410   private static final class ChildComparatorProvider extends DataProviderAdapter {
411     public Object get( final Object dataHolder ) {
412       return new YCoordComparator(true);
413     }
414   }
415   
416   /**
417    * Sorts edges depending on the y-coordinates of their target nodes.
418    * <p>
419    *   By default, edges are sorted from top to bottom. However, in case sides are taken into consideration, edges with
420    *   target nodes to the right are sorted bottom up and edges with target nodes to the left are sorted top down.
421    *   This is important when this comparator is used to determine the order of children for layout.
422    * </p>
423    */
424   static final class YCoordComparator implements Comparator {
425     private final boolean considerSides;
426 
427     public YCoordComparator() {
428       this(false);
429     }
430 
431     public YCoordComparator(boolean considerSides) {
432       this.considerSides = considerSides;
433     }
434 
435     public int compare( final Object o1, final Object o2 ) {
436       final Edge edge1 = (Edge) o1;
437       final Edge edge2 = (Edge) o2;
438       final double y1 = getY(edge1);
439       final double y2 = getY(edge2);
440 
441       if (!considerSides || isLeft(edge1.target())) {
442         return Double.compare(y1, y2);
443       } else {
444         return Double.compare(y2, y1);
445       }
446     }
447 
448     private boolean isLeft(Node node) {
449       return Boolean.TRUE.equals(node.getGraph().getDataProvider(DelegatingNodePlacer.LEFT_RIGHT_DPKEY).get(node));
450     }
451 
452     private double getY( final Edge edge ) {
453       return ((LayoutGraph) edge.getGraph()).getY(edge.target());
454     }
455   }
456 }
457