package com.mxgraph.layout;

import java.util.HashSet;
import java.util.Set;

import com.mxgraph.model.mxGeometry;
import com.mxgraph.model.mxIGraphModel;
import com.mxgraph.util.mxRectangle;
import com.mxgraph.view.mxGraph;

public class mxCompactTreeLayout extends mxGraphLayout
{

	/**
	 * Specifies the orientation of the layout. Default is true.
	 */
	protected boolean horizontal;

	/**
	 * Specifies if edge directions should be inverted. Default is false.
	 */
	protected boolean invert;

	/**
	 * If the parent should be resized to match the width/height of the
	 * tree. Default is true.
	 */
	protected boolean resizeParent = true;

	/**
	 * Specifies if the tree should be moved to the top, left corner
	 * if it is inside a top-level layer. Default is true.
	 */
	protected boolean moveTree = true;

	/**
	 * Specifies if all edge points of traversed edges should be removed.
	 * Default is true.
	 */
	protected boolean resetEdges = true;

	/**
	 * Holds the levelDistance. Default is 10.
	 */
	protected int levelDistance = 10;

	/**
	 * Holds the nodeDistance. Default is 20.
	 */
	protected int nodeDistance = 20;

	/**
	 * 
	 * @param graph
	 */
	public mxCompactTreeLayout(mxGraph graph)
	{
		this(graph, true);
	}

	/**
	 * 
	 * @param graph
	 * @param horizontal
	 */
	public mxCompactTreeLayout(mxGraph graph, boolean horizontal)
	{
		this(graph, horizontal, false);
	}

	/**
	 * 
	 * @param graph
	 * @param horizontal
	 * @param invert
	 */
	public mxCompactTreeLayout(mxGraph graph, boolean horizontal, boolean invert)
	{
		super(graph);
		this.horizontal = horizontal;
		this.invert = invert;
	}

	/**
	 * Returns a boolean indicating if the given <mxCell> should be ignored as a
	 * vertex. This returns true if the cell has no connections.
	 * 
	 * @param vertex Object that represents the vertex to be tested.
	 * @return Returns true if the vertex should be ignored.
	 */
	public boolean isVertexIgnored(Object vertex)
	{
		return super.isVertexIgnored(vertex)
				|| graph.getConnections(vertex).length == 0;
	}

	/**
	 * @return the horizontal
	 */
	public boolean isHorizontal()
	{
		return horizontal;
	}

	/**
	 * @param horizontal the horizontal to set
	 */
	public void setHorizontal(boolean horizontal)
	{
		this.horizontal = horizontal;
	}

	/**
	 * @return the invert
	 */
	public boolean isInvert()
	{
		return invert;
	}

	/**
	 * @param invert the invert to set
	 */
	public void setInvert(boolean invert)
	{
		this.invert = invert;
	}

	/**
	 * @return the resizeParent
	 */
	public boolean isResizeParent()
	{
		return resizeParent;
	}

	/**
	 * @param resizeParent the resizeParent to set
	 */
	public void setResizeParent(boolean resizeParent)
	{
		this.resizeParent = resizeParent;
	}

	/**
	 * @return the moveTree
	 */
	public boolean isMoveTree()
	{
		return moveTree;
	}

	/**
	 * @param moveTree the moveTree to set
	 */
	public void setMoveTree(boolean moveTree)
	{
		this.moveTree = moveTree;
	}

	/**
	 * @return the resetEdges
	 */
	public boolean isResetEdges()
	{
		return resetEdges;
	}

	/**
	 * @param resetEdges the resetEdges to set
	 */
	public void setResetEdges(boolean resetEdges)
	{
		this.resetEdges = resetEdges;
	}

	/**
	 * @return the levelDistance
	 */
	public int getLevelDistance()
	{
		return levelDistance;
	}

	/**
	 * @param levelDistance the levelDistance to set
	 */
	public void setLevelDistance(int levelDistance)
	{
		this.levelDistance = levelDistance;
	}

	/**
	 * @return the nodeDistance
	 */
	public int getNodeDistance()
	{
		return nodeDistance;
	}

	/**
	 * @param nodeDistance the nodeDistance to set
	 */
	public void setNodeDistance(int nodeDistance)
	{
		this.nodeDistance = nodeDistance;
	}

	/*
	 * (non-Javadoc)
	 * @see com.mxgraph.layout.mxIGraphLayout#execute(java.lang.Object)
	 */
	public void execute(Object parent)
	{
		execute(parent, null);
	}

	/**
	 * Implements <mxGraphLayout.execute>.
	 * 
	 * If the parent has any connected edges, then it is used as the root of
	 * the tree. Else, <mxGraph.findTreeRoots> will be used to find a suitable
	 * root node within the set of children of the given parent.
	 */
	public void execute(Object parent, Object root)
	{
		mxIGraphModel model = graph.getModel();

		if (root == null)
		{
			// Takes the parent as the root if it has outgoing edges
			if (graph.getEdges(parent, model.getParent(parent), invert,
					!invert, false).length > 0)
			{
				root = parent;
			}

			// Tries to find a suitable root in the parent's
			// children
			else
			{
				Object[] roots = graph.findTreeRoots(parent, true, invert);

				if (roots.length > 0)
				{
					for (int i = 0; i < roots.length; i++)
					{
						if (!isVertexIgnored(roots[i])
								&& graph.getEdges(roots[i], null, invert,
										!invert, false).length > 0)
						{
							root = roots[i];
							break;
						}
					}
				}
			}
		}

		if (root != null)
		{
			parent = model.getParent(root);
			model.beginUpdate();

			try
			{
				TreeNode node = dfs(root, parent, null);

				if (node != null)
				{
					layout(node);

					double x0 = graph.getGridSize();
					double y0 = x0;

					if (!moveTree || model.getParent(parent) == model.getRoot())
					{
						mxGeometry g = model.getGeometry(root);

						if (g != null)
						{
							x0 = g.getX();
							y0 = g.getY();
						}
					}

					mxRectangle bounds = null;

					if (horizontal)
					{
						bounds = horizontalLayout(node, x0, y0, null);
					}
					else
					{
						bounds = verticalLayout(node, null, x0, y0, null);
					}

					if (bounds != null)
					{
						double dx = 0;
						double dy = 0;

						if (bounds.getX() < 0)
						{
							dx = Math.abs(x0 - bounds.getX());
						}

						if (bounds.getY() < 0)
						{
							dy = Math.abs(y0 - bounds.getY());
						}

						if (parent != null)
						{
							mxRectangle size = graph.getStartSize(parent);
							dx += size.getWidth();
							dy += size.getHeight();

							// Resize parent swimlane
							if (resizeParent && !graph.isCellCollapsed(parent))
							{
								mxGeometry g = model.getGeometry(parent);

								if (g != null)
								{
									double width = bounds.getWidth()
											+ size.getWidth() - bounds.getX()
											+ 2 * x0;
									double height = bounds.getHeight()
											+ size.getHeight() - bounds.getY()
											+ 2 * y0;

									g = (mxGeometry) g.clone();

									if (g.getWidth() > width)
									{
										dx += (g.getWidth() - width) / 2;
									}
									else
									{
										g.setWidth(width);
									}

									if (g.getHeight() > height)
									{
										if (horizontal)
										{
											dy += (g.getHeight() - height) / 2;
										}
									}
									else
									{
										g.setHeight(height);
									}

									model.setGeometry(parent, g);
								}
							}
						}

						moveNode(node, dx, dy);
					}
				}
			}
			finally
			{
				model.endUpdate();
			}
		}
	}

	/**
	 * Moves the specified node and all of its children by the given amount.
	 */
	protected void moveNode(TreeNode node, double dx, double dy)
	{
		node.x += dx;
		node.y += dy;
		apply(node, null);

		TreeNode child = node.child;

		while (child != null)
		{
			moveNode(child, dx, dy);
			child = child.next;
		}
	}

	/**
	 * Does a depth first search starting at the specified cell.
	 * Makes sure the specified swimlane is never left by the
	 * algorithm.
	 */
	protected TreeNode dfs(Object cell, Object parent, Set<Object> visited)
	{
		if (visited == null)
		{
			visited = new HashSet<Object>();
		}

		TreeNode node = null;

		if (cell != null && !visited.contains(cell) && !isVertexIgnored(cell))
		{
			visited.add(cell);
			node = createNode(cell);

			mxIGraphModel model = graph.getModel();
			TreeNode prev = null;
			Object[] out = graph.getEdges(cell, parent, invert, !invert, false);

			for (int i = 0; i < out.length; i++)
			{
				Object edge = out[i];

				if (!isEdgeIgnored(edge))
				{
					// Resets the points on the traversed edge
					if (resetEdges)
					{
						setEdgePoints(edge, null);
					}

					// Checks if terminal in same swimlane
					Object target = graph.getView().getVisibleTerminal(edge,
							invert);
					TreeNode tmp = dfs(target, parent, visited);

					if (tmp != null && model.getGeometry(target) != null)
					{
						if (prev == null)
						{
							node.child = tmp;
						}
						else
						{
							prev.next = tmp;
						}

						prev = tmp;
					}
				}
			}
		}

		return node;
	}

	/**
	 * Starts the actual compact tree layout algorithm
	 * at the given node.
	 */
	protected void layout(TreeNode node)
	{
		if (node != null)
		{
			TreeNode child = node.child;

			while (child != null)
			{
				layout(child);
				child = child.next;
			}

			if (node.child != null)
			{
				attachParent(node, join(node));
			}
			else
			{
				layoutLeaf(node);
			}
		}
	}

	/**
	 * 
	 */
	protected mxRectangle horizontalLayout(TreeNode node, double x0, double y0,
			mxRectangle bounds)
	{
		node.x += x0 + node.offsetX;
		node.y += y0 + node.offsetY;
		bounds = apply(node, bounds);
		TreeNode child = node.child;

		if (child != null)
		{
			bounds = horizontalLayout(child, node.x, node.y, bounds);
			double siblingOffset = node.y + child.offsetY;
			TreeNode s = child.next;

			while (s != null)
			{
				bounds = horizontalLayout(s, node.x + child.offsetX,
						siblingOffset, bounds);
				siblingOffset += s.offsetY;
				s = s.next;
			}
		}

		return bounds;
	}

	/**
	 * 
	 */
	protected mxRectangle verticalLayout(TreeNode node, Object parent,
			double x0, double y0, mxRectangle bounds)
	{
		node.x += x0 + node.offsetY;
		node.y += y0 + node.offsetX;
		bounds = apply(node, bounds);
		TreeNode child = node.child;

		if (child != null)
		{
			bounds = verticalLayout(child, node, node.x, node.y, bounds);
			double siblingOffset = node.x + child.offsetY;
			TreeNode s = child.next;

			while (s != null)
			{
				bounds = verticalLayout(s, node, siblingOffset, node.y
						+ child.offsetX, bounds);
				siblingOffset += s.offsetY;
				s = s.next;
			}
		}

		return bounds;
	}

	/**
	 * 
	 */
	protected void attachParent(TreeNode node, double height)
	{
		double x = nodeDistance + levelDistance;
		double y2 = (height - node.width) / 2 - nodeDistance;
		double y1 = y2 + node.width + 2 * nodeDistance - height;

		node.child.offsetX = x + node.height;
		node.child.offsetY = y1;

		node.contour.upperHead = createLine(node.height, 0, createLine(x, y1,
				node.contour.upperHead));
		node.contour.lowerHead = createLine(node.height, 0, createLine(x, y2,
				node.contour.lowerHead));
	}

	/**
	 * 
	 */
	protected void layoutLeaf(TreeNode node)
	{
		double dist = 2 * nodeDistance;

		node.contour.upperTail = createLine(node.height + dist, 0, null);
		node.contour.upperHead = node.contour.upperTail;
		node.contour.lowerTail = createLine(0, -node.width - dist, null);
		node.contour.lowerHead = createLine(node.height + dist, 0,
				node.contour.lowerTail);
	}

	/**
	 * 
	 */
	protected double join(TreeNode node)
	{
		double dist = 2 * nodeDistance;

		TreeNode child = node.child;
		node.contour = child.contour;
		double h = child.width + dist;
		double sum = h;
		child = child.next;

		while (child != null)
		{
			double d = merge(node.contour, child.contour);
			child.offsetY = d + h;
			child.offsetX = 0;
			h = child.width + dist;
			sum += d + h;
			child = child.next;
		}

		return sum;
	}

	/**
	 * 
	 */
	protected double merge(Polygon p1, Polygon p2)
	{
		double x = 0;
		double y = 0;
		double total = 0;

		Polyline upper = p1.lowerHead;
		Polyline lower = p2.upperHead;

		while (lower != null && upper != null)
		{
			double d = offset(x, y, lower.dx, lower.dy, upper.dx, upper.dy);
			y += d;
			total += d;

			if (x + lower.dx <= upper.dx)
			{
				x += lower.dx;
				y += lower.dy;
				lower = lower.next;
			}
			else
			{
				x -= upper.dx;
				y -= upper.dy;
				upper = upper.next;
			}
		}

		if (lower != null)
		{
			Polyline b = bridge(p1.upperTail, 0, 0, lower, x, y);
			p1.upperTail = (b.next != null) ? p2.upperTail : b;
			p1.lowerTail = p2.lowerTail;
		}
		else
		{
			Polyline b = bridge(p2.lowerTail, x, y, upper, 0, 0);

			if (b.next == null)
			{
				p1.lowerTail = b;
			}
		}

		p1.lowerHead = p2.lowerHead;

		return total;
	}

	/**
	 * 
	 */
	protected double offset(double p1, double p2, double a1, double a2,
			double b1, double b2)
	{
		double d = 0;

		if (b1 <= p1 || p1 + a1 <= 0)
		{
			return 0;
		}

		double t = b1 * a2 - a1 * b2;

		if (t > 0)
		{
			if (p1 < 0)
			{
				double s = p1 * a2;
				d = s / a1 - p2;
			}
			else if (p1 > 0)
			{
				double s = p1 * b2;
				d = s / b1 - p2;
			}
			else
			{
				d = -p2;
			}
		}
		else if (b1 < p1 + a1)
		{
			double s = (b1 - p1) * a2;
			d = b2 - (p2 + s / a1);
		}
		else if (b1 > p1 + a1)
		{
			double s = (a1 + p1) * b2;
			d = s / b1 - (p2 + a2);
		}
		else
		{
			d = b2 - (p2 + a2);
		}

		if (d > 0)
		{
			return d;
		}

		return 0;
	}

	/**
	 * 
	 */
	protected Polyline bridge(Polyline line1, double x1, double y1,
			Polyline line2, double x2, double y2)
	{
		double dx = x2 + line2.dx - x1;
		double dy = 0;
		double s = 0;

		if (line2.dx == 0)
		{
			dy = line2.dy;
		}
		else
		{
			s = dx * line2.dy;
			dy = s / line2.dx;
		}

		Polyline r = createLine(dx, dy, line2.next);
		line1.next = createLine(0, y2 + line2.dy - dy - y1, r);

		return r;
	}

	/**
	 * 
	 */
	protected TreeNode createNode(Object cell)
	{
		TreeNode node = new TreeNode(cell);

		mxRectangle geo = getVertexBounds(cell);

		if (geo != null)
		{
			if (horizontal)
			{
				node.width = geo.getHeight();
				node.height = geo.getWidth();
			}
			else
			{
				node.width = geo.getWidth();
				node.height = geo.getHeight();
			}
		}

		return node;
	}

	/**
	 * 
	 */
	protected mxRectangle apply(TreeNode node, mxRectangle bounds)
	{
		mxRectangle g = graph.getModel().getGeometry(node.cell);

		if (node.cell != null && g != null)
		{
			if (isVertexMovable(node.cell))
			{
				g = setVertexLocation(node.cell, node.x, node.y);
			}

			if (bounds == null)
			{
				bounds = new mxRectangle(g.getX(), g.getY(), g.getWidth(), g
						.getHeight());
			}
			else
			{
				bounds = new mxRectangle(Math.min(bounds.getX(), g.getX()),
						Math.min(bounds.getY(), g.getY()), Math.max(bounds
								.getX()
								+ bounds.getWidth(), g.getX() + g.getWidth()),
						Math.max(bounds.getY() + bounds.getHeight(), g.getY()
								+ g.getHeight()));
			}
		}

		return bounds;
	}

	/**
	 * 
	 */
	protected Polyline createLine(double dx, double dy, Polyline next)
	{
		return new Polyline(dx, dy, next);
	}

	/**
	 * 
	 */
	protected static class TreeNode
	{
		/**
		 * 
		 */
		protected Object cell;

		/**
		 * 
		 */
		protected double x, y, width, height, offsetX, offsetY;

		/**
		 * 
		 */
		protected TreeNode child, next; // parent, sibling

		/**
		 * 
		 */
		protected Polygon contour = new Polygon();

		/**
		 * 
		 */
		public TreeNode(Object cell)
		{
			this.cell = cell;
		}

	}

	/**
	 * 
	 */
	protected static class Polygon
	{

		/**
		 * 
		 */
		protected Polyline lowerHead, lowerTail, upperHead, upperTail;

	}

	/**
	 * 
	 */
	protected static class Polyline
	{

		/**
		 * 
		 */
		protected double dx, dy;

		/**
		 * 
		 */
		protected Polyline next;

		/**
		 * 
		 */
		protected Polyline(double dx, double dy, Polyline next)
		{
			this.dx = dx;
			this.dy = dy;
			this.next = next;
		}

	}

}