diff --git a/api.visual/src/org/netbeans/api/visual/graph/layout/GraphLayoutFactory.java b/api.visual/src/org/netbeans/api/visual/graph/layout/GraphLayoutFactory.java --- a/api.visual/src/org/netbeans/api/visual/graph/layout/GraphLayoutFactory.java +++ b/api.visual/src/org/netbeans/api/visual/graph/layout/GraphLayoutFactory.java @@ -70,6 +70,14 @@ return new TreeGraphLayout(originX, originY, verticalGap, horizontalGap, vertical); } + public static GraphLayout createTreeGraphLayout(int originX, int originY, int verticalGap, int horizontalGap, boolean vertical, boolean minimizeGap) { + return createTreeGraphLayout(originX, originY, verticalGap, horizontalGap, vertical, minimizeGap, TreeGraphLayout.Alignment.TOP); + } + + public static GraphLayout createTreeGraphLayout(int originX, int originY, int verticalGap, int horizontalGap, boolean vertical, boolean minimizeGap, TreeGraphLayout.Alignment alignment) { + return new TreeGraphLayout(originX, originY, verticalGap, horizontalGap, vertical, minimizeGap, alignment); + } + /** * * @param the node class for the nodes in the graph. @@ -110,7 +118,7 @@ public static GraphLayout createHierarchicalGraphLayout(GraphScene graphScene, boolean animate, boolean inverted) { return new HierarchicalLayout(graphScene, animate, inverted); } - + /** * * @param the node class for the nodes in the graph. @@ -128,6 +136,4 @@ int xOffset, int layerOffset) { return new HierarchicalLayout(graphScene, animate, inverted, xOffset, layerOffset); } - - } diff --git a/api.visual/src/org/netbeans/api/visual/graph/layout/GraphLayoutSupport.java b/api.visual/src/org/netbeans/api/visual/graph/layout/GraphLayoutSupport.java --- a/api.visual/src/org/netbeans/api/visual/graph/layout/GraphLayoutSupport.java +++ b/api.visual/src/org/netbeans/api/visual/graph/layout/GraphLayoutSupport.java @@ -54,9 +54,10 @@ * @param rootNode the root node * @since 2.4 */ - public static void setTreeGraphLayoutRootNode (GraphLayout graph, N rootNode) { - if (graph instanceof TreeGraphLayout) - ((TreeGraphLayout) graph).setRootNode (rootNode); + public static void setTreeGraphLayoutRootNode(GraphLayout graph, N rootNode) { + if (graph instanceof TreeGraphLayout) { + ((TreeGraphLayout) graph).setRootNode(rootNode); + } } /** @@ -69,9 +70,21 @@ * @param vertical if true, then layout organizes the graph vertically; if false, then horizontally * @since 2.7 */ - public static void setTreeGraphLayoutProperties (GraphLayout graph, int originX, int originY, int verticalGap, int horizontalGap, boolean vertical) { - if (graph instanceof TreeGraphLayout) - ((TreeGraphLayout) graph).setProperties (originX, originY, verticalGap, horizontalGap, vertical); + public static void setTreeGraphLayoutProperties(GraphLayout graph, int originX, int originY, int verticalGap, int horizontalGap, boolean vertical) { + if (graph instanceof TreeGraphLayout) { + ((TreeGraphLayout) graph).setProperties(originX, originY, verticalGap, horizontalGap, vertical); + } } + public static void setTreeGraphLayoutProperties(GraphLayout graph, int originX, int originY, int verticalGap, int horizontalGap, boolean vertical, boolean minimizeGap) { + if (graph instanceof TreeGraphLayout) { + setTreeGraphLayoutProperties(graph, originX, originY, verticalGap, horizontalGap, vertical, minimizeGap, TreeGraphLayout.Alignment.TOP); + } + } + + public static void setTreeGraphLayoutProperties(GraphLayout graph, int originX, int originY, int verticalGap, int horizontalGap, boolean vertical, boolean minimizeGap, TreeGraphLayout.Alignment alignment) { + if (graph instanceof TreeGraphLayout) { + ((TreeGraphLayout) graph).setProperties(originX, originY, verticalGap, horizontalGap, vertical,minimizeGap, alignment); + } + } } diff --git a/api.visual/src/org/netbeans/modules/visual/graph/layout/TreeGraphLayout.java b/api.visual/src/org/netbeans/modules/visual/graph/layout/TreeGraphLayout.java --- a/api.visual/src/org/netbeans/modules/visual/graph/layout/TreeGraphLayout.java +++ b/api.visual/src/org/netbeans/modules/visual/graph/layout/TreeGraphLayout.java @@ -40,157 +40,475 @@ */ package org.netbeans.modules.visual.graph.layout; +import java.awt.Point; +import java.awt.Rectangle; import org.netbeans.api.visual.graph.layout.GraphLayout; import org.netbeans.api.visual.graph.layout.UniversalGraph; import org.netbeans.api.visual.widget.Widget; -import java.awt.*; -import java.util.*; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; /** * @author David Kaspar */ -public final class TreeGraphLayout extends GraphLayout { +public final class TreeGraphLayout extends GraphLayout { private int originX; private int originY; private int verticalGap; private int horizontalGap; private boolean vertical; + private boolean minimizeGap; + private N rootNode; + private Alignment alignment; - private N rootNode; - - public TreeGraphLayout (int originX, int originY, int verticalGap, int horizontalGap, boolean vertical) { - this.originX = originX; - this.originY = originY; - this.verticalGap = verticalGap; - this.horizontalGap = horizontalGap; + public TreeGraphLayout(int originX, int originY, int verticalGap, + int horizontalGap, boolean vertical) { + if (vertical) { + this.originX = originX; + this.originY = originY; + this.verticalGap = verticalGap; + this.horizontalGap = horizontalGap; + } else { + this.originX = originY; + this.originY = originX; + this.verticalGap = horizontalGap; + this.horizontalGap = verticalGap; + } this.vertical = vertical; + this.minimizeGap = false; + this.alignment = Alignment.TOP; } - public void setRootNode (N rootNode) { + public TreeGraphLayout(int originX, int originY, int verticalGap, + int horizontalGap, boolean vertical, boolean minimizeGap, + Alignment alignment) { + this(originX, originY, verticalGap, horizontalGap, vertical); + this.minimizeGap = minimizeGap; + this.alignment = alignment; + } + + public void setRootNode(N rootNode) { this.rootNode = rootNode; } - public void setProperties (int originX, int originY, int verticalGap, int horizontalGap, boolean vertical) { - this.originX = originX; - this.originY = originY; - this.verticalGap = verticalGap; - this.horizontalGap = horizontalGap; + public void setProperties(int originX, int originY, int verticalGap, + int horizontalGap, boolean vertical) { + if (vertical) { + this.originX = originX; + this.originY = originY; + this.verticalGap = verticalGap; + this.horizontalGap = horizontalGap; + } else { + this.originX = originY; + this.originY = originX; + this.verticalGap = horizontalGap; + this.horizontalGap = verticalGap; + } this.vertical = vertical; + this.minimizeGap = false; + this.alignment = Alignment.TOP; } - protected void performGraphLayout (UniversalGraph graph) { - if (rootNode == null) + public void setProperties(int originX, int originY, int verticalGap, + int horizontalGap, boolean vertical, boolean minimizeGap, + Alignment alignment) { + this.setProperties(originX, originY, verticalGap, horizontalGap, vertical); + this.minimizeGap = minimizeGap; + this.alignment = alignment; + } + + protected void performGraphLayout(UniversalGraph graph) { + if (rootNode == null) { return; - Collection allNodes = graph.getNodes (); - if (! allNodes.contains (rootNode)) + } + Collection allNodes = graph.getNodes(); + if (!allNodes.contains(rootNode)) { return; - ArrayList nodesToResolve = new ArrayList (allNodes); + } + ArrayList nodesToResolve = new ArrayList(allNodes); - HashSet loadedSet = new HashSet (); - Node root = new Node (graph, rootNode, loadedSet); - nodesToResolve.removeAll (loadedSet); - if (vertical) { - root.allocateHorizontally (graph); - root.resolveVertically (originX, originY); - } else { - root.allocateVertically (graph); - root.resolveHorizontally (originX, originY); + HashSet loadedSet = new HashSet(); + Node root = new Node(graph, rootNode, loadedSet); + nodesToResolve.removeAll(loadedSet); + + Map map = root.getMaxSpaceForEveryLevel(graph); + + List envelope = root.layout(originX, originY, map, 0); + + // correction of originX, if needed + int moveDistance = Integer.MIN_VALUE; + // get the most left position and determine the distance to move + for (Node.LeftRight leftRight : envelope) { + if (leftRight.getLeft() < originX && originX - leftRight.getLeft() > moveDistance) { + moveDistance = originX - leftRight.getLeft(); + } } - final HashMap resultPosition = new HashMap (); - root.upload (resultPosition); + if (moveDistance == Integer.MIN_VALUE) { + moveDistance = 0; + } + + if (!vertical) { + root.invert(moveDistance); + } else { + root.relativeBoundsCorrectionX(moveDistance); + } + + final HashMap resultPosition = new HashMap(); + root.upload(resultPosition); for (N node : nodesToResolve) { - Point position = new Point (); + Point position = new Point(); // TODO - resolve others - resultPosition.put (node, position); + resultPosition.put(node, position); } - for (Map.Entry entry : resultPosition.entrySet ()) - setResolvedNodeLocation (graph, entry.getKey (), entry.getValue ()); + for (Map.Entry entry : resultPosition.entrySet()) { + setResolvedNodeLocation(graph, entry.getKey(), entry.getValue()); + } } - protected void performNodesLayout (UniversalGraph universalGraph, Collection nodes) { - throw new UnsupportedOperationException (); // TODO + protected void performNodesLayout(UniversalGraph universalGraph, + Collection nodes) { + throw new UnsupportedOperationException(); // TODO + } + + public enum Alignment { + + TOP, CENTER, BOTTOM } private class Node { private N node; private ArrayList children; + private Rectangle relativeBounds; + private Point point; + private int space; - private Rectangle relativeBounds; - private int space; - private int totalSpace; - private Point point; + private Node(UniversalGraph graph, N node, HashSet loadedSet) { + this.node = node; + loadedSet.add(node); - private Node (UniversalGraph graph, N node, HashSet loadedSet) { - this.node = node; - loadedSet.add (node); - - children = new ArrayList (); - for (E edge: graph.findNodeEdges (node, true, false)) { - N child = graph.getEdgeTarget (edge); - if (child != null && ! loadedSet.contains (child)) - children.add (new Node (graph, child, loadedSet)); + children = new ArrayList(); + for (E edge : graph.findNodeEdges(node, true, false)) { + N child = graph.getEdgeTarget(edge); + if (child != null && !loadedSet.contains(child)) { + children.add(new Node(graph, child, loadedSet)); + } } } - private int allocateHorizontally (UniversalGraph graph) { - Widget widget = graph.getScene ().findWidget (node); - widget.getLayout ().layout (widget); - relativeBounds = widget.getPreferredBounds (); - space = 0; - for (int i = 0; i < children.size (); i++) { - if (i > 0) - space += horizontalGap; - space += children.get (i).allocateHorizontally (graph); + /** + * This class represents an element of the envelope of a (sub)tree. + */ + private class LeftRight { + + /** the most left coordinate of this element of the envelope. */ + private int left; + /** hte most right coordinate of this element of the envelope. */ + private int right; + + /** + * Constructor + * + * @param left the most left coordinate of this {@link LeftRight}. + * @param right the most right coordinate of this {@link LeftRight}. + */ + public LeftRight(int left, int right) { + this.left = left; + this.right = right; } - totalSpace = Math.max (space, relativeBounds.width); - return totalSpace; - } - private void resolveVertically (int x, int y) { - point = new Point (x + totalSpace / 2, y - relativeBounds.y); - x += (totalSpace - space) / 2; - y += relativeBounds.height + verticalGap; - for (Node child : children) { - child.resolveVertically (x, y); - x += child.totalSpace + horizontalGap; + /** + * Getter of the most left coordinate of this {@link LeftRight}. + * @return the most left coordinate of this {@link LeftRight}. + */ + public int getLeft() { + return left; + } + + /** + * Getter of the most right coordinate of this {@link LeftRight}. + * @return the most right coordinate of this {@link LeftRight}. + */ + public int getRight() { + return right; + } + + /** + * Setter of the most left coordinate of this {@link LeftRight}. + * @param left the most left coordinate to set. + */ + public void setLeft(int left) { + this.left = left; + } + + /** + * Setter of the most right coordinate of this {@link LeftRight}. + * @param left the most right coordinate to set. + */ + public void setRight(int right) { + this.right = right; } } - private int allocateVertically (UniversalGraph graph) { - Widget widget = graph.getScene ().findWidget (node); - widget.getLayout ().layout (widget); - relativeBounds = widget.getPreferredBounds (); - space = 0; - for (int i = 0; i < children.size (); i++) { - if (i > 0) - space += verticalGap; - space += children.get (i).allocateVertically (graph); - } - totalSpace = Math.max (space, relativeBounds.height); - return totalSpace; + private Map getMaxSpaceForEveryLevel(UniversalGraph graph) { + Map map = new HashMap(); + calculateMaxSpace(graph, map, 0); + return map; } - private void resolveHorizontally (int x, int y) { - point = new Point (x - relativeBounds.x, y + totalSpace / 2); - x += relativeBounds.width + horizontalGap; - y += (totalSpace - space) / 2; - for (Node child : children) { - child.resolveHorizontally (x, y); - y += child.totalSpace + verticalGap; + /** + * Method to determine the maximal space (horizontaly or verticaly) of each level in the tree. + * @param map + * @param lvl + * @return + */ + private Map calculateMaxSpace(UniversalGraph graph, Map map, int lvl) { + + Widget widget = graph.getScene().findWidget(node); + widget.getLayout().layout(widget); + relativeBounds = widget.getPreferredBounds(); + + if (vertical) { + space = relativeBounds.height; + } else { + space = relativeBounds.width; + } + + if (map.get(lvl) != null) { + // lvl is in list, but height is greater than the old one. + if (map.get(lvl) < space) { + map.put(lvl, space); + } + } else { + // lvl isn't in the map right now. + map.put(lvl, space); + } + + lvl++; + + // do iteration over all children of the current node and calculate + // the maxSpace + for (Node n : children) { + n.calculateMaxSpace(graph, map, lvl); + } + return map; + } + + /** + * + * @param graph + * @param x + * @param y + * @return + */ + private List layout(int x, int y, Map map, int lvl) { + + List leftright = null; + + // if this node is a leaf (has no childs) ==> place the node at x,y and x and x + width to the envelope. + if (children.size() == 0) { + leftright = new ArrayList(); + + // do the horizontal alignment + y = doHorizontalPlacementInLevel(y, map, lvl); + + if (vertical) { + y = y - relativeBounds.y; + leftright.add(new LeftRight(x, x + relativeBounds.width)); + } else { + y = y - relativeBounds.x; + leftright.add(new LeftRight(x, x + relativeBounds.height)); + } + + point = new Point(x, y); + return leftright; + } + + lvl++; + + for (int i = 0; i < children.size(); i++) { + if (i == 0) { + leftright = children.get(i).layout(x, (int) (y + map.get(lvl - 1) + verticalGap), map, lvl); + } else { + List secound = children.get(i).layout(x, (int) (y + map.get(lvl - 1) + verticalGap), map, lvl); + + int leftlength = leftright.size(); + int rightlength = secound.size(); + + int diff = rightlength - leftlength; + + // Variable used for calculation of the distance to move the right subtree. + int moveDist = Integer.MIN_VALUE; + + // Try to minimize the gap and move subtrees as close as possible to each other. + if (minimizeGap) { + // Caluculate the max distance to move + for (int k = leftlength - 1; k >= 0; k--) { + if (k + diff >= 0 && k >= 0) { + int tmpmaxoverlap = leftright.get(k).right - secound.get(k + diff).left; + if (tmpmaxoverlap > moveDist) { + moveDist = tmpmaxoverlap; + } + } + } + } else { + int maxRight = Integer.MIN_VALUE; + + for (LeftRight l : leftright) { + maxRight = Math.max(maxRight, l.right); + } + + int minLeft = Integer.MAX_VALUE; + + for (LeftRight s : secound) { + minLeft = Math.min(minLeft, s.left); + } + moveDist = maxRight - minLeft; + } + + if (moveDist > Integer.MIN_VALUE) { + int dx = moveDist + horizontalGap; + children.get(i).point.x += dx; + children.get(i).moveChildrenHorizontally(dx); + } + + // update moved tree envelope + for (LeftRight lr : secound) { + lr.setLeft(lr.getLeft() + moveDist + horizontalGap); + lr.setRight(lr.getRight() + moveDist + horizontalGap); + } + + // store the overall envelope of leftright and secound in leftright + for (int j = rightlength - 1; j >= 0; j--) { + // leftright wasn't as long as secound, so these elements have to be added to the envelope + if (j < secound.size() - leftright.size()) { + leftright.add(0, secound.get(j)); + } else if ((j - diff) >= 0 && j >= 0) { + // if the left envelope of secound is smaller than the left envelope of leftright, might never happen. + if (leftright.get(j - diff).left > secound.get(j).left) { + leftright.get(j - diff).setLeft(secound.get(j).left); + } + // if the right envelope of secound is greater than the right envelope of leftright, might happen every time when a subtree was added by a move to the right. + if (leftright.get(j - diff).right < secound.get(j).right) { + leftright.get(j - diff).setRight(secound.get(j).right); + } + } + } + } + } + + lvl--; + + // do the horizontal alignment + int yAlignment = doHorizontalPlacementInLevel(y, map, lvl); + + if (minimizeGap) { + if (vertical) { + point = new Point(((leftright.get(leftright.size() - 1).right + leftright.get(leftright.size() - 1).left) / 2) - (relativeBounds.width / 2), yAlignment - relativeBounds.y); + leftright.add(new LeftRight(point.x, point.x + relativeBounds.width)); + } else { + point = new Point(((leftright.get(leftright.size() - 1).right + leftright.get(leftright.size() - 1).left) / 2) - (relativeBounds.height / 2), yAlignment - relativeBounds.x); + leftright.add(new LeftRight(point.x, point.x + relativeBounds.height)); + } + } else { + int leftMin = Integer.MAX_VALUE; + int rightMax = Integer.MIN_VALUE; + for (LeftRight l : leftright) { + leftMin = Math.min(leftMin, l.left); + rightMax = Math.max(rightMax, l.right); + } + + assert leftMin != Integer.MAX_VALUE; + assert rightMax != Integer.MIN_VALUE; + + if (vertical) { + point = new Point(((leftMin + rightMax) / 2) - (relativeBounds.width / 2), yAlignment - relativeBounds.y); + leftright.add(new LeftRight(point.x, point.x + relativeBounds.width)); + } else { + point = new Point(((leftMin + rightMax) / 2) - (relativeBounds.height / 2), yAlignment - relativeBounds.x); + leftright.add(new LeftRight(point.x, point.x + relativeBounds.height)); + } + } + + return leftright; + } + + /** + * Method to move the children of the actual {@link Node} horizontally + * by the given distance dx. + * + * @param dx the distance to move the children horizontally. + */ + private void moveChildrenHorizontally(int dx) { + for (Node n : children) { + n.point.x += dx; + n.moveChildrenHorizontally(dx); } } - private void upload (HashMap result) { - result.put (node, point); - for (Node child : children) - child.upload (result); + /** + * + * @param y + * @param map + * @param lvl + * @return + */ + private int doHorizontalPlacementInLevel(int y, Map map, int lvl) { + int yAlignment = 0; + + // do the alignment + if (alignment == Alignment.TOP) { + // nothing to do + yAlignment = y; + } else if (alignment == Alignment.CENTER) { + // place the widget in the center of the max. + yAlignment = y + ((map.get(lvl) - space) / 2); + } else if (alignment == Alignment.BOTTOM) { + yAlignment = y + (map.get(lvl) - space); + } + return yAlignment; + } + + /** + * Method to invert x and y. Also relativeBounds correction is done and + * a moveDistance (x-axis) can be given. + * @param moveDistance the distance to move the subtree (x-axis). + */ + private void invert(int moveDistance) { + int tmpx = point.x + moveDistance; + point.x = point.y; + point.y = tmpx - relativeBounds.y; + for (Node n : children) { + n.invert(moveDistance); + } + } + + /** + * Method to do a relativeBoundsCorrection (x-axis) and also to move the + * Node for a given distance (also x-axis). + * @param moveDistance the distance to move the subtree (x-axis). + */ + private void relativeBoundsCorrectionX(int moveDistance) { + point.x = point.x - relativeBounds.x + moveDistance; + for (Node n : children) { + n.relativeBoundsCorrectionX(moveDistance); + } + } + + private void upload(HashMap result) { + result.put(node, point); + for (Node child : children) { + child.upload(result); + } } } - }