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.isometry;
29  
30  import y.algo.NodeOrders;
31  import y.base.Edge;
32  import y.base.EdgeCursor;
33  import y.base.Graph;
34  import y.base.ListCell;
35  import y.base.Node;
36  import y.base.NodeCursor;
37  import y.base.NodeList;
38  import y.base.NodeMap;
39  import y.base.YList;
40  import y.view.Bend;
41  import y.view.EdgeLabel;
42  import y.view.EdgeRealizer;
43  import y.view.GenericNodeRealizer;
44  import y.view.Graph2D;
45  import y.view.Graph2DTraversal;
46  import y.view.NodeLabel;
47  import y.view.NodePort;
48  import y.view.NodeRealizer;
49  import y.view.Port;
50  import y.view.hierarchy.HierarchyManager;
51  
52  import java.awt.geom.Point2D;
53  import java.awt.geom.Rectangle2D;
54  import java.util.ArrayList;
55  import java.util.Collections;
56  import java.util.Iterator;
57  import java.util.List;
58  
59  /**
60   * A {@link Graph2DTraversal} for isometric graphs.
61   *
62   * As isometric (3-dimensional) objects can overlap with each other, it is important to paint objects that are behind
63   * other objects first. That way, the objects in front are painted above and seem to be in front of the others.
64   * <p>
65   *   To get the right order for all graph elements, this <code>Graph2DTraversal</code> holds the following order:
66   *   <ul>
67   *     <li>Group and folder nodes (with their labels and node ports)</li>
68   *     <li>Edges (with their bends and ports)</li>
69   *     <li>
70   *       Normal nodes (with their labels and node ports) and edge labels, where nodes/labels with a lower y-coordinate
71   *       come first
72   *     </li>
73   *   </ul>
74   * </p>
75   */
76  public class IsometryGraphTraversal implements Graph2DTraversal {
77    public Iterator firstToLast(Graph2D graph, int elementTypes) {
78      final List allElements = collectAllGraphElements(graph);
79      final List filteredElements = filterGraphElements(allElements, elementTypes);
80      return filteredElements.iterator();
81    }
82  
83    public Iterator lastToFirst(Graph2D graph, int elementTypes) {
84      final List allElements = collectAllGraphElements(graph);
85      final List filteredElements = filterGraphElements(allElements, elementTypes);
86      Collections.reverse(filteredElements);
87      return filteredElements.iterator();
88    }
89  
90    /**
91     * Collects all elements in the given graph in the order they will be traversed.
92     */
93    private static List collectAllGraphElements(final Graph2D graph) {
94      final ArrayList graphElements = new ArrayList();
95      final ArrayList normalNodesAndEdgeLabels = new ArrayList();
96  
97      // add group/folder nodes with their labels and node ports
98      // and collect normal nodes to add them later
99      final HierarchyManager hierarchyManager = graph.getHierarchyManager();
100     if (hierarchyManager != null) {
101       for (Iterator it = hierarchyManager.preTraversal(); it.hasNext(); ) {
102         final Node node = (Node) it.next();
103         if (hierarchyManager.isNormalNode(node)) {
104           normalNodesAndEdgeLabels.add(node);
105         } else {
106           graphElements.add(node);
107           final NodeRealizer realizer = graph.getRealizer(node);
108           for (int i = 0; i < realizer.portCount(); i++) {
109             graphElements.add(realizer.getPort(i));
110           }
111           for (int i = 0; i < realizer.labelCount(); i++) {
112             graphElements.add(realizer.getLabel(i));
113           }
114         }
115       }
116     }
117 
118     // add edges with their bends, ports and labels
119     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
120       final Edge edge = ec.edge();
121       graphElements.add(edge);
122       final EdgeRealizer realizer = graph.getRealizer(edge);
123       for (int i = 0; i < realizer.bendCount(); i++) {
124         graphElements.add(realizer.getBend(i));
125       }
126       graphElements.add(realizer.getSourcePort());
127       graphElements.add(realizer.getTargetPort());
128       for (int i = 0; i < realizer.labelCount(); i++) {
129         normalNodesAndEdgeLabels.add(realizer.getLabel(i));
130       }
131     }
132 
133     // sort normal nodes and edge labels according to their position in layout space
134     sort(normalNodesAndEdgeLabels);
135 
136     // add edge labels and normal nodes with their labels and node ports
137     for (Iterator it = normalNodesAndEdgeLabels.iterator(); it.hasNext(); ) {
138       final Object element = it.next();
139       graphElements.add(element);
140       if (element instanceof Node) {
141         final NodeRealizer realizer = graph.getRealizer((Node) element);
142         for (int i = 0; i < realizer.portCount(); i++) {
143           graphElements.add(realizer.getPort(i));
144         }
145         for (int i = 0; i < realizer.labelCount(); i++) {
146           graphElements.add(realizer.getLabel(i));
147         }
148       }
149     }
150 
151     return graphElements;
152   }
153 
154   /**
155    * Filters the given list of graph elements so it contains only elements of the allowed types.
156    */
157   private static List filterGraphElements(final List graphElements, final int elementTypes) {
158     if (elementTypes == ALL) {
159       // all types of elements are allowed, so we don't have to filter
160       return new ArrayList(graphElements);
161     }
162 
163     final ArrayList filteredElements = new ArrayList();
164     for (Iterator it = graphElements.iterator(); it.hasNext(); ) {
165       final Object element = it.next();
166 
167       // only add element if its type is allowed
168       if ((element instanceof Node && (elementTypes & NODES) != 0)
169           || (element instanceof Edge && (elementTypes & EDGES) != 0)
170           || (element instanceof NodeLabel && (elementTypes & NODE_LABELS) != 0)
171           || (element instanceof EdgeLabel && (elementTypes & EDGE_LABELS) != 0)
172           || (element instanceof Bend && (elementTypes & BENDS) != 0)
173           || (element instanceof Port && (elementTypes & PORTS) != 0)
174           || (element instanceof NodePort && (elementTypes & NODE_PORTS) != 0)) {
175         filteredElements.add(element);
176       }
177     }
178     return filteredElements;
179   }
180 
181   /**
182    * Sorts the given elements according to their positions in layout space.
183    * <p>
184    *   This implementation uses a sweepline (slope -1) to build a constraint graph. An edge will be created in this
185    *   graph, when the source is behind the target. After that the graph nodes get a topological order that is assigned
186    *   to the given elements.
187    * </p>
188    */
189   private static void sort(List elements) {
190     final Graph constraintsGraph = new Graph();
191     final NodeMap constraints2graph = constraintsGraph.createNodeMap();
192     final NodeMap node2rectangle = constraintsGraph.createNodeMap();
193     final ArrayList events = new ArrayList();
194 
195     // create constraint graph and events
196     for (Iterator it = elements.iterator(); it.hasNext(); ) {
197       final Object element = it.next();
198       final Rectangle2D bounds = getBounds(element);
199       final Node constraintsNode = constraintsGraph.createNode();
200       constraints2graph.set(constraintsNode, element);
201       node2rectangle.set(constraintsNode, bounds);
202       final double boundsX = bounds.getX();
203       final double boundsY = bounds.getY();
204       events.add(new SweeplineEvent(boundsX, boundsY, constraintsNode, true));
205       events.add(new SweeplineEvent(boundsX + bounds.getWidth(), boundsY + bounds.getHeight(), constraintsNode, false));
206     }
207 
208     // events have to be sorted according to their distance orthogonal to the sweepline
209     Collections.sort(events);
210 
211     // sweep through the events
212     final YList currentElements = new YList();
213     for (Iterator it = events.iterator(); it.hasNext(); ) {
214       final SweeplineEvent event = (SweeplineEvent) it.next();
215       if (event.open) {
216         // an element is opened and must be inserted into the list of currently opened elements
217         // its position is in front of the first element where the sweepline hits above the event coordinates
218         final ListCell successor = findSuccessor(currentElements, event.coordX, event.coordY, node2rectangle);
219         ListCell cell;
220         if (successor != null) {
221           cell = currentElements.insertBefore(event.node, successor);
222           constraintsGraph.createEdge((Node) successor.getInfo(), event.node);
223         } else {
224           cell = currentElements.addLast(event.node);
225         }
226         if (cell.pred() != null) {
227           constraintsGraph.createEdge(event.node, (Node) cell.pred().getInfo());
228         }
229       } else {
230         // an element is closed and must be removed from the list of currently opened elements
231         // its neighbors get updated as they become direct neighbors now
232         final ListCell cell = currentElements.findCell(event.node);
233         if (cell.pred() != null && cell.succ() != null) {
234           constraintsGraph.createEdge((Node) cell.succ().getInfo(), (Node) cell.pred().getInfo());
235         }
236         currentElements.removeCell(cell);
237       }
238     }
239 
240     // sort the nodes of the constraint graph topologically and assign the new order to the given elements
241     elements.clear();
242     final NodeList topological = NodeOrders.topological(constraintsGraph);
243     for (NodeCursor nc = topological.nodes(); nc.ok(); nc.next()) {
244       final Node constraintNode = nc.node();
245       if (constraints2graph.get(constraintNode) != null) {
246         elements.add(constraints2graph.get(constraintNode));
247       }
248     }
249 
250     // clean up the node maps
251     constraintsGraph.disposeNodeMap(constraints2graph);
252     constraintsGraph.disposeNodeMap(node2rectangle);
253   }
254 
255   /**
256    * Returns the first list cell that contains the node that is hit by the sweepline above the given coordinates.
257    */
258   private static ListCell findSuccessor(YList list, double coordX, double coordY, NodeMap node2rectangle) {
259     if (!list.isEmpty()) {
260       for (ListCell cell = list.firstCell(); cell != null; cell = cell.succ()) {
261         final Node node = (Node) cell.getInfo();
262         final Rectangle2D rect = (Rectangle2D) node2rectangle.get(node);
263 
264         // calculate intersection of sweepline with extended right rect border (rect.getX() + rect.getWidth()),
265         // where coordX + coordY == (rect.getX() + rect.getWidth()) + rect.getY()
266         final double intersectionY = coordX + coordY - (rect.getX() + rect.getWidth());
267 
268         double refY;
269         if (intersectionY < rect.getY()) {
270           // intersection is outside rect
271           // --> rectangle intersects the sweepline with its upper side
272           refY = rect.getY();
273         } else {
274           // rectangle intersects the sweepline with its right side
275           // --> take intersection as reference
276           refY = intersectionY;
277         }
278 
279         if (refY < coordY) {
280           // reference is behind coordY
281           return cell;
282         }
283       }
284     }
285     return null;
286   }
287 
288   /**
289    * Returns the element's bounds in layout space.
290    */
291   private static Rectangle2D getBounds(Object element) {
292     if (element instanceof Node) {
293       final Node node = (Node) element;
294       final Graph2D graph = (Graph2D) node.getGraph();
295       final NodeRealizer realizer = graph.getRealizer(node);
296       if (realizer instanceof GenericNodeRealizer) {
297         final IsometryData isometryData = (IsometryData) ((GenericNodeRealizer) realizer).getUserData();
298 
299         final double[] corners = new double[16];
300         isometryData.calculateCorners(corners);
301         IsometryData.moveTo(realizer.getX(), realizer.getY(), corners);
302         final double x = IsometryData.toLayoutX(corners[IsometryData.C0_X], corners[IsometryData.C0_Y]);
303         final double y = IsometryData.toLayoutY(corners[IsometryData.C0_X], corners[IsometryData.C0_Y]);
304         final double w = isometryData.getWidth();
305         final double h = isometryData.getDepth();
306         return new Rectangle2D.Double(x, y, w, h);
307       }
308     } else if (element instanceof EdgeLabel) {
309       final EdgeLabel label = (EdgeLabel) element;
310       final Graph2D graph = (Graph2D) label.getEdge().getGraph();
311       final Point2D sourceIntersection = graph.getRealizer(label.getEdge()).getSourceIntersection();
312       final IsometryData isometryData = (IsometryData) label.getUserData();
313       final double[] corners = new double[16];
314       isometryData.calculateCorners(corners);
315       IsometryData.moveTo(label.getOffsetX() + sourceIntersection.getX(),
316           label.getOffsetY() + sourceIntersection.getY(), corners);
317 
318       double x, y, w, h;
319       if (isometryData.isHorizontal()) {
320         x = IsometryData.toLayoutX(corners[IsometryData.C0_X], corners[IsometryData.C0_Y]);
321         y = IsometryData.toLayoutY(corners[IsometryData.C0_X], corners[IsometryData.C0_Y]);
322         w = isometryData.getWidth();
323         h = 0;
324       } else {
325         x = IsometryData.toLayoutX(corners[IsometryData.C1_X], corners[IsometryData.C1_Y]);
326         y = IsometryData.toLayoutY(corners[IsometryData.C1_X], corners[IsometryData.C1_Y]);
327         w = 0;
328         h = isometryData.getDepth();
329       }
330       return new Rectangle2D.Double(x, y, w, h);
331     }
332 
333     return null;
334   }
335 
336   /**
337    * Event for a sweepline with slope -1.
338    */
339   private static class SweeplineEvent implements Comparable {
340     double coordX;
341     double coordY;
342     Node node;
343     boolean open;
344 
345     private SweeplineEvent(double coordX, double coordY, Node node, boolean open) {
346       this.coordX = coordX;
347       this.coordY = coordY;
348       this.node = node;
349       this.open = open;
350     }
351 
352     public int compareTo(Object o) {
353       final SweeplineEvent other = (SweeplineEvent) o;
354 
355       final double thisCoord = coordX + coordY;
356       final double otherCoord = other.coordX + other.coordY;
357 
358       if (thisCoord < otherCoord) {
359         return -1;
360       } else if (thisCoord > otherCoord) {
361         return 1;
362       } else {
363         return 0;
364       }
365     }
366   }
367 }
368