import java.awt.*;

import java.util.ArrayList;

import java.util.*;

import java.util.Collection;

import java.util.HashMap;

import java.util.HashSet;

import java.util.List;

import java.util.Map;

public final class TreeGraphLayout<N,E> extends GraphLayout<N,E> {

public final class TreeGraphLayout<N, E> extends GraphLayout<N, E> {

    private N rootNode;

    public TreeGraphLayout(int originX, int originY, int verticalGap,

            int horizontalGap, boolean vertical, boolean minimizeGap) {

    public TreeGraphLayout (int originX, int originY, int verticalGap, int horizontalGap, boolean vertical) {

        if (vertical) {

        this.originX = originX;

            this.originX = originX;

        this.originY = originY;

            this.originY = originY;

        this.verticalGap = verticalGap;

            this.verticalGap = verticalGap;

        this.horizontalGap = horizontalGap;

            this.horizontalGap = horizontalGap;

        } else {

            this.originX = originY;

            this.originY = originX;

            this.verticalGap = horizontalGap;

            this.horizontalGap = verticalGap;

        }

    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, minimizeGap);

        this.alignment = alignment;

    }

    public void setRootNode(N rootNode) {

    public void setProperties (int originX, int originY, int verticalGap, int horizontalGap, boolean vertical) {

    public void setProperties(int originX, int originY, int verticalGap,

        this.originX = originX;

            int horizontalGap, boolean vertical, boolean minimizeGap) {

        this.originY = originY;

        if (vertical) {

        this.verticalGap = verticalGap;

            this.originX = originX;

        this.horizontalGap = horizontalGap;

            this.originY = originY;

            this.verticalGap = verticalGap;

            this.horizontalGap = horizontalGap;

        } else {

            this.originX = originY;

            this.originY = originX;

            this.verticalGap = horizontalGap;

            this.horizontalGap = verticalGap;

        }

    protected void performGraphLayout (UniversalGraph<N, E> graph) {

    public void setProperties(int originX, int originY, int verticalGap,

        if (rootNode == null)

            int horizontalGap, boolean vertical, boolean minimizeGap,

            Alignment alignment) {

        this.setProperties(originX, originY, verticalGap, horizontalGap, vertical, minimizeGap);

        this.alignment = alignment;

    }

    protected void performGraphLayout(UniversalGraph<N, E> graph) {

        if (rootNode == null) {

        Collection<N> allNodes = graph.getNodes ();

        }

        if (! allNodes.contains (rootNode))

        Collection<N> allNodes = graph.getNodes();

        if (!allNodes.contains(rootNode)) {

        ArrayList<N> nodesToResolve = new ArrayList<N> (allNodes);

        }

        ArrayList<N> nodesToResolve = new ArrayList<N>(allNodes);

        HashSet<N> loadedSet = new HashSet<N> ();

        HashSet<N> loadedSet = new HashSet<N>();

        Node root = new Node (graph, rootNode, loadedSet);

        Node root = new Node(graph, rootNode, loadedSet);

        nodesToResolve.removeAll (loadedSet);

        nodesToResolve.removeAll(loadedSet);

        if (vertical) {

            root.allocateHorizontally (graph);

        Map<Integer, Integer> map = root.getMaxSpaceForEveryLevel(graph);

            root.resolveVertically (originX, originY);

        } else {

        List<Node.LeftRight> envelope = root.layout(originX, originY, map, 0);

            root.allocateVertically (graph);

            root.resolveHorizontally (originX, originY);

        // 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<N, Point> resultPosition = new HashMap<N, Point> ();

        if (moveDistance == Integer.MIN_VALUE) {

        root.upload (resultPosition);

            moveDistance = 0;

        }

        if (!vertical) {

            root.invert(moveDistance);

        } else {

            root.relativeBoundsCorrectionX(moveDistance);

        }

        final HashMap<N, Point> resultPosition = new HashMap<N, Point>();

        root.upload(resultPosition);

            Point position = new Point ();

            Point position = new Point();

            resultPosition.put (node, position);

            resultPosition.put(node, position);

        for (Map.Entry<N, Point> entry : resultPosition.entrySet ())

        for (Map.Entry<N, Point> entry : resultPosition.entrySet()) {

            setResolvedNodeLocation (graph, entry.getKey (), entry.getValue ());

            setResolvedNodeLocation(graph, entry.getKey(), entry.getValue());

        }

    protected void performNodesLayout (UniversalGraph<N, E> universalGraph, Collection<N> nodes) {

    protected void performNodesLayout(UniversalGraph<N, E> universalGraph,

        throw new UnsupportedOperationException (); // TODO

            Collection<N> nodes) {

        throw new UnsupportedOperationException(); // TODO

    }

    public enum Alignment {

        TOP, CENTER, BOTTOM

        private Rectangle relativeBounds;

        private Node(UniversalGraph<N, E> graph, N node, HashSet<N> loadedSet) {

        private int space;

            this.node = node;

        private int totalSpace;

            loadedSet.add(node);

        private Point point;

        private Node (UniversalGraph<N, E> graph, N node, HashSet<N> loadedSet) {

            children = new ArrayList<Node>();

            this.node = node;

            for (E edge : graph.findNodeEdges(node, true, false)) {

            loadedSet.add (node);

                N child = graph.getEdgeTarget(edge);

                if (child != null && !loadedSet.contains(child)) {

            children = new ArrayList<Node> ();

                    children.add(new Node(graph, child, loadedSet));

            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<N, E> graph) {

        /**

            Widget widget = graph.getScene ().findWidget (node);

         * This class represents an element of the envelope of a (sub)tree.

            widget.getLayout ().layout (widget);

         */

            relativeBounds = widget.getPreferredBounds ();

        private class LeftRight {

            space = 0;

            for (int i = 0; i < children.size (); i++) {

            /** the most left coordinate of this element of the envelope. */

                if (i > 0)

            private int left;

                    space += horizontalGap;

            /** hte most right coordinate of this element of the envelope. */

                space += children.get (i).allocateHorizontally (graph);

            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;

        private void resolveVertically (int x, int y) {

            /**

            point = new Point (x + totalSpace / 2, y - relativeBounds.y);

             * Getter of the most left coordinate of this {@link LeftRight}.

            x += (totalSpace - space) / 2;

             * @return the most left coordinate of this {@link LeftRight}.

            y += relativeBounds.height + verticalGap;

             */

            for (Node child : children) {

            public int getLeft() {

                child.resolveVertically (x, y);

                return left;

                x += child.totalSpace + horizontalGap;

            }

            /**

             * 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<N, E> graph) {

        private Map<Integer, Integer> getMaxSpaceForEveryLevel(UniversalGraph<N, E> graph) {

            Widget widget = graph.getScene ().findWidget (node);

            Map<Integer, Integer> map = new HashMap<Integer, Integer>();

            widget.getLayout ().layout (widget);

            calculateMaxSpace(graph, map, 0);

            relativeBounds = widget.getPreferredBounds ();

            return map;

            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 void resolveHorizontally (int x, int y) {

        /**

            point = new Point (x - relativeBounds.x, y + totalSpace / 2);

         * Method to determine the maximal space (horizontaly or verticaly) of each level in the tree.

            x += relativeBounds.width + horizontalGap;

         * @param map

            y += (totalSpace - space) / 2;

         * @param lvl

            for (Node child : children) {

         * @return

                child.resolveHorizontally (x, y);

         */

                y += child.totalSpace + verticalGap;

        private Map<Integer, Integer> calculateMaxSpace(UniversalGraph<N, E> graph, Map<Integer, Integer> 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<LeftRight> layout(int x, int y, Map<Integer, Integer> map, int lvl) {

            List<LeftRight> 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<LeftRight>();

                // 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<LeftRight> 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<N, Point> result) {

        /**

            result.put (node, point);

         *

            for (Node child : children)

         * @param y

                child.upload (result);

         * @param map

         * @param lvl

         * @return

         */

        private int doHorizontalPlacementInLevel(int y, Map<Integer, Integer> 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<N, Point> result) {

            result.put(node, point);

            for (Node child : children) {

                child.upload(result);

            }