/*
 * Copyright (c) 2005, David Benson
 *
 * All rights reserved.
 *
 * This file is licensed under the JGraph software license, a copy of which
 * will have been provided to you in the file LICENSE at the root of your
 * installation directory. If you are unable to locate this file please
 * contact JGraph sales for another copy.
 */

package com.mxgraph.layout.hierarchical.stage;

import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

import javax.swing.SwingConstants;

import com.mxgraph.layout.hierarchical.mxHierarchicalLayout;
import com.mxgraph.layout.hierarchical.model.mxGraphAbstractHierarchyCell;
import com.mxgraph.layout.hierarchical.model.mxGraphHierarchyEdge;
import com.mxgraph.layout.hierarchical.model.mxGraphHierarchyModel;
import com.mxgraph.layout.hierarchical.model.mxGraphHierarchyNode;
import com.mxgraph.layout.hierarchical.model.mxGraphHierarchyRank;
import com.mxgraph.util.mxPoint;
import com.mxgraph.util.mxRectangle;
import com.mxgraph.view.mxGraph;

/**
 * Sets the horizontal locations of node and edge dummy nodes on each layer.
 * Uses median down and up weighings as well heuristic to straighten edges as
 * far as possible.
 */
public class mxCoordinateAssignment implements mxHierarchicalLayoutStage
{

	/**
	 * Reference to the enclosing layout algorithm
	 */
	protected mxHierarchicalLayout layout;

	/**
	 * The minimum buffer between cells on the same rank
	 */
	protected double intraCellSpacing = 30.0;

	/**
	 * The minimum distance between cells on adjacent ranks
	 */
	protected double interRankCellSpacing = 30.0;

	/**
	 * The distance between each parallel edge on each ranks for long edges
	 */
	protected double parallelEdgeSpacing = 10.0;

	/**
	 * The number of heuristic iterations to run
	 */
	protected int maxIterations = 8;

	/**
	 * The position of the root ( start ) node(s) relative to the rest of the
	 * laid out graph
	 */
	protected int orientation = SwingConstants.NORTH;

	/**
	 * The minimum x position node placement starts at
	 */
	protected double initialX;

	/**
	 * The maximum x value this positioning lays up to
	 */
	protected double limitX;

	/**
	 * The sum of x-displacements for the current iteration
	 */
	protected double currentXDelta;

	/**
	 * The rank that has the widest x position
	 */
	protected int widestRank;

	/**
	 * The X-coordinate of the edge of the widest rank
	 */
	protected double widestRankValue;

	/**
	 * The width of all the ranks
	 */
	protected double[] rankWidths;

	/**
	 * The Y-coordinate of all the ranks
	 */
	protected double[] rankY;

	/**
	 * Whether or not to perform local optimisations and iterate multiple times
	 * through the algorithm
	 */
	protected boolean fineTuning = true;

	/**
	 * Specifies if the STYLE_NOEDGESTYLE flag should be set on edges that are
	 * modified by the result. Default is true.
	 */
	protected boolean disableEdgeStyle = true;

	/**
	 * A store of connections to the layer above for speed
	 */
	protected mxGraphAbstractHierarchyCell[][] nextLayerConnectedCache;

	/**
	 * A store of connections to the layer below for speed
	 */
	protected mxGraphAbstractHierarchyCell[][] previousLayerConnectedCache;

	/** The logger for this class */
	private static Logger logger = Logger
			.getLogger("com.jgraph.layout.hierarchical.JGraphCoordinateAssignment");

	/**
	 * Creates a coordinate assignment.
	 * 
	 * @param intraCellSpacing
	 *            the minimum buffer between cells on the same rank
	 * @param interRankCellSpacing
	 *            the minimum distance between cells on adjacent ranks
	 * @param orientation
	 *            the position of the root node(s) relative to the graph
	 * @param initialX
	 *            the leftmost coordinate node placement starts at
	 */
	public mxCoordinateAssignment(mxHierarchicalLayout layout,
			double intraCellSpacing, double interRankCellSpacing,
			int orientation, double initialX, double parallelEdgeSpacing)
	{
		this.layout = layout;
		this.intraCellSpacing = intraCellSpacing;
		this.interRankCellSpacing = interRankCellSpacing;
		this.orientation = orientation;
		this.initialX = initialX;
		this.parallelEdgeSpacing = parallelEdgeSpacing;
		setLoggerLevel(Level.OFF);
	}

	/**
	 * A basic horizontal coordinate assignment algorithm
	 */
	public void execute(Object parent)
	{
		mxGraphHierarchyModel model = layout.getModel();
		currentXDelta = 0.0;

		initialCoords(layout.getGraph(), model);

		if (fineTuning)
		{
			minNode(model);
		}

		double bestXDelta = 100000000.0;

		if (fineTuning)
		{
			for (int i = 0; i < maxIterations; i++)
			{
				// Median Heuristic
				if (i != 0)
				{
					medianPos(i, model);
					minNode(model);
				}

				// if the total offset is less for the current positioning,
				// there are less heavily angled edges and so the current
				// positioning is used
				if (currentXDelta < bestXDelta)
				{
					for (int j = 0; j < model.ranks.size(); j++)
					{
						mxGraphHierarchyRank rank = model.ranks
								.get(new Integer(j));
						Iterator<mxGraphAbstractHierarchyCell> iter = rank
								.iterator();

						while (iter.hasNext())
						{
							mxGraphAbstractHierarchyCell cell = (mxGraphAbstractHierarchyCell) iter
									.next();
							cell.setX(j, cell.getGeneralPurposeVariable(j));
						}
					}

					bestXDelta = currentXDelta;
				}
				else
				{
					// Restore the best positions
					for (int j = 0; j < model.ranks.size(); j++)
					{
						mxGraphHierarchyRank rank = model.ranks
								.get(new Integer(j));
						Iterator<mxGraphAbstractHierarchyCell> iter = rank
								.iterator();

						while (iter.hasNext())
						{
							mxGraphAbstractHierarchyCell cell = (mxGraphAbstractHierarchyCell) iter
									.next();
							cell.setGeneralPurposeVariable(j, (int) cell
									.getX(j));
						}
					}
				}

				currentXDelta = 0;
			}
		}

		setCellLocations(layout.getGraph(), model);
	}

	/**
	 * Performs one median positioning sweep in both directions
	 * 
	 * @param model
	 *            an internal model of the hierarchical layout
	 */
	private void minNode(mxGraphHierarchyModel model)
	{
		// Queue all nodes
		LinkedList<WeightedCellSorter> nodeList = new LinkedList<WeightedCellSorter>();

		// Need to be able to map from cell to cellWrapper
		Map<mxGraphAbstractHierarchyCell, WeightedCellSorter> map = new Hashtable<mxGraphAbstractHierarchyCell, WeightedCellSorter>();
		Object[][] rank = new Object[model.maxRank + 1][];

		for (int i = 0; i <= model.maxRank; i++)
		{
			mxGraphHierarchyRank rankSet = (mxGraphHierarchyRank) model.ranks
					.get(new Integer(i));
			rank[i] = rankSet.toArray();

			for (int j = 0; j < rank[i].length; j++)
			{
				// Use the weight to store the rank and visited to store whether
				// or not the cell is in the list
				mxGraphAbstractHierarchyCell cell = (mxGraphAbstractHierarchyCell) rank[i][j];
				WeightedCellSorter cellWrapper = new WeightedCellSorter(cell, i);
				cellWrapper.rankIndex = j;
				cellWrapper.visited = true;
				nodeList.add(cellWrapper);
				map.put(cell, cellWrapper);
			}
		}

		// Set a limit of the maximum number of times we will access the queue
		// in case a loop appears
		int maxTries = nodeList.size() * 10;
		int count = 0;

		// Don't move cell within this value of their median
		int tolerance = 1;

		while (!nodeList.isEmpty() && count <= maxTries)
		{
			WeightedCellSorter cellWrapper = (WeightedCellSorter) nodeList
					.getFirst();
			mxGraphAbstractHierarchyCell cell = cellWrapper.cell;

			int rankValue = cellWrapper.weightedValue;
			int rankIndex = cellWrapper.rankIndex;

			Object[] nextLayerConnectedCells = cell.getNextLayerConnectedCells(
					rankValue).toArray();
			Object[] previousLayerConnectedCells = cell
					.getPreviousLayerConnectedCells(rankValue).toArray();

			int numNextLayerConnected = nextLayerConnectedCells.length;
			int numPreviousLayerConnected = previousLayerConnectedCells.length;

			int medianNextLevel = medianXValue(nextLayerConnectedCells,
					rankValue + 1);
			int medianPreviousLevel = medianXValue(previousLayerConnectedCells,
					rankValue - 1);

			int numConnectedNeighbours = numNextLayerConnected
					+ numPreviousLayerConnected;
			int currentPosition = cell.getGeneralPurposeVariable(rankValue);
			double cellMedian = currentPosition;

			if (numConnectedNeighbours > 0)
			{
				cellMedian = (medianNextLevel * numNextLayerConnected + medianPreviousLevel
						* numPreviousLayerConnected)
						/ numConnectedNeighbours;
			}

			// Flag storing whether or not position has changed
			boolean positionChanged = false;

			if (cellMedian < currentPosition - tolerance)
			{
				if (rankIndex == 0)
				{
					cell.setGeneralPurposeVariable(rankValue, (int) cellMedian);
					positionChanged = true;
				}
				else
				{
					mxGraphAbstractHierarchyCell leftCell = (mxGraphAbstractHierarchyCell) rank[rankValue][rankIndex - 1];
					int leftLimit = leftCell
							.getGeneralPurposeVariable(rankValue);
					leftLimit = leftLimit + (int) leftCell.width / 2
							+ (int) intraCellSpacing + (int) cell.width / 2;

					if (leftLimit < cellMedian)
					{
						cell.setGeneralPurposeVariable(rankValue,
								(int) cellMedian);
						positionChanged = true;
					}
					else if (leftLimit < cell
							.getGeneralPurposeVariable(rankValue)
							- tolerance)
					{
						cell.setGeneralPurposeVariable(rankValue, leftLimit);
						positionChanged = true;
					}
				}
			}
			else if (cellMedian > currentPosition + tolerance)
			{
				int rankSize = rank[rankValue].length;

				if (rankIndex == rankSize - 1)
				{
					cell.setGeneralPurposeVariable(rankValue, (int) cellMedian);
					positionChanged = true;
				}
				else
				{
					mxGraphAbstractHierarchyCell rightCell = (mxGraphAbstractHierarchyCell) rank[rankValue][rankIndex + 1];
					int rightLimit = rightCell
							.getGeneralPurposeVariable(rankValue);
					rightLimit = rightLimit - (int) rightCell.width / 2
							- (int) intraCellSpacing - (int) cell.width / 2;

					if (rightLimit > cellMedian)
					{
						cell.setGeneralPurposeVariable(rankValue,
								(int) cellMedian);
						positionChanged = true;
					}
					else if (rightLimit > cell
							.getGeneralPurposeVariable(rankValue)
							+ tolerance)
					{
						cell.setGeneralPurposeVariable(rankValue, rightLimit);
						positionChanged = true;
					}
				}
			}

			if (positionChanged)
			{
				// Add connected nodes to map and list
				for (int i = 0; i < nextLayerConnectedCells.length; i++)
				{
					mxGraphAbstractHierarchyCell connectedCell = (mxGraphAbstractHierarchyCell) nextLayerConnectedCells[i];
					WeightedCellSorter connectedCellWrapper = (WeightedCellSorter) map
							.get(connectedCell);

					if (connectedCellWrapper != null)
					{
						if (connectedCellWrapper.visited == false)
						{
							connectedCellWrapper.visited = true;
							nodeList.add(connectedCellWrapper);
						}
					}
				}

				// Add connected nodes to map and list
				for (int i = 0; i < previousLayerConnectedCells.length; i++)
				{
					mxGraphAbstractHierarchyCell connectedCell = (mxGraphAbstractHierarchyCell) previousLayerConnectedCells[i];
					WeightedCellSorter connectedCellWrapper = (WeightedCellSorter) map
							.get(connectedCell);

					if (connectedCellWrapper != null)
					{
						if (connectedCellWrapper.visited == false)
						{
							connectedCellWrapper.visited = true;
							nodeList.add(connectedCellWrapper);
						}
					}
				}
			}

			nodeList.removeFirst();
			cellWrapper.visited = false;
			count++;
		}
	}

	/**
	 * Performs one median positioning sweep in one direction
	 * 
	 * @param i
	 *            the iteration of the whole process
	 * @param model
	 *            an internal model of the hierarchical layout
	 */
	private void medianPos(int i, mxGraphHierarchyModel model)
	{
		// Reverse sweep direction each time through this method
		boolean downwardSweep = (i % 2 == 0);

		if (downwardSweep)
		{
			for (int j = model.maxRank; j > 0; j--)
			{
				rankMedianPosition(j - 1, model, j);
			}
		}
		else
		{
			for (int j = 0; j < model.maxRank - 1; j++)
			{
				rankMedianPosition(j + 1, model, j);
			}
		}
	}

	/**
	 * Performs median minimisation over one rank.
	 * 
	 * @param rankValue
	 *            the layer number of this rank
	 * @param model
	 *            an internal model of the hierarchical layout
	 * @param nextRankValue
	 *            the layer number whose connected cels are to be laid out
	 *            relative to
	 */
	protected void rankMedianPosition(int rankValue,
			mxGraphHierarchyModel model, int nextRankValue)
	{
		mxGraphHierarchyRank rankSet = (mxGraphHierarchyRank) model.ranks
				.get(new Integer(rankValue));
		Object[] rank = rankSet.toArray();
		// Form an array of the order in which the cell are to be processed
		// , the order is given by the weighted sum of the in or out edges,
		// depending on whether we're travelling up or down the hierarchy.
		WeightedCellSorter[] weightedValues = new WeightedCellSorter[rank.length];
		Map<mxGraphAbstractHierarchyCell, WeightedCellSorter> cellMap = new Hashtable<mxGraphAbstractHierarchyCell, WeightedCellSorter>(
				rank.length);

		for (int i = 0; i < rank.length; i++)
		{
			mxGraphAbstractHierarchyCell currentCell = (mxGraphAbstractHierarchyCell) rank[i];
			weightedValues[i] = new WeightedCellSorter();
			weightedValues[i].cell = currentCell;
			weightedValues[i].rankIndex = i;
			cellMap.put(currentCell, weightedValues[i]);
			Collection<mxGraphAbstractHierarchyCell> nextLayerConnectedCells = null;

			if (nextRankValue < rankValue)
			{
				nextLayerConnectedCells = currentCell
						.getPreviousLayerConnectedCells(rankValue);
			}
			else
			{
				nextLayerConnectedCells = currentCell
						.getNextLayerConnectedCells(rankValue);
			}

			// Calcuate the weighing based on this node type and those this
			// node is connected to on the next layer
			weightedValues[i].weightedValue = calculatedWeightedValue(
					currentCell, nextLayerConnectedCells);
		}

		Arrays.sort(weightedValues);
		// Set the new position of each node within the rank using
		// its temp variable

		for (int i = 0; i < weightedValues.length; i++)
		{
			int numConnectionsNextLevel = 0;
			mxGraphAbstractHierarchyCell cell = weightedValues[i].cell;
			Object[] nextLayerConnectedCells = null;
			int medianNextLevel = 0;

			if (nextRankValue < rankValue)
			{
				nextLayerConnectedCells = cell.getPreviousLayerConnectedCells(
						rankValue).toArray();
			}
			else
			{
				nextLayerConnectedCells = cell.getNextLayerConnectedCells(
						rankValue).toArray();
			}

			if (nextLayerConnectedCells != null)
			{
				numConnectionsNextLevel = nextLayerConnectedCells.length;

				if (numConnectionsNextLevel > 0)
				{
					medianNextLevel = medianXValue(nextLayerConnectedCells,
							nextRankValue);
				}
				else
				{
					// For case of no connections on the next level set the
					// median to be the current position and try to be
					// positioned there
					medianNextLevel = cell.getGeneralPurposeVariable(rankValue);
				}
			}

			double leftBuffer = 0.0;
			double leftLimit = -100000000.0;

			for (int j = weightedValues[i].rankIndex - 1; j >= 0;)
			{
				WeightedCellSorter weightedValue = (WeightedCellSorter) cellMap
						.get(rank[j]);

				if (weightedValue != null)
				{
					mxGraphAbstractHierarchyCell leftCell = weightedValue.cell;

					if (weightedValue.visited)
					{
						// The left limit is the right hand limit of that
						// cell plus any allowance for unallocated cells
						// in-between
						leftLimit = leftCell
								.getGeneralPurposeVariable(rankValue)
								+ leftCell.width
								/ 2.0
								+ intraCellSpacing
								+ leftBuffer + cell.width / 2.0;
						j = -1;
					}
					else
					{
						leftBuffer += leftCell.width + intraCellSpacing;
						j--;
					}
				}
			}

			double rightBuffer = 0.0;
			double rightLimit = 100000000.0;

			for (int j = weightedValues[i].rankIndex + 1; j < weightedValues.length;)
			{
				WeightedCellSorter weightedValue = (WeightedCellSorter) cellMap
						.get(rank[j]);

				if (weightedValue != null)
				{
					mxGraphAbstractHierarchyCell rightCell = weightedValue.cell;

					if (weightedValue.visited)
					{
						// The left limit is the right hand limit of that
						// cell plus any allowance for unallocated cells
						// in-between
						rightLimit = rightCell
								.getGeneralPurposeVariable(rankValue)
								- rightCell.width
								/ 2.0
								- intraCellSpacing
								- rightBuffer - cell.width / 2.0;
						j = weightedValues.length;
					}
					else
					{
						rightBuffer += rightCell.width + intraCellSpacing;
						j++;
					}
				}
			}

			if (medianNextLevel >= leftLimit && medianNextLevel <= rightLimit)
			{
				cell
						.setGeneralPurposeVariable(rankValue,
								(int) medianNextLevel);
			}
			else if (medianNextLevel < leftLimit)
			{
				// Couldn't place at median value, place as close to that
				// value as possible
				cell.setGeneralPurposeVariable(rankValue, (int) leftLimit);
				currentXDelta += leftLimit - medianNextLevel;
			}
			else if (medianNextLevel > rightLimit)
			{
				// Couldn't place at median value, place as close to that
				// value as possible
				cell.setGeneralPurposeVariable(rankValue, (int) rightLimit);
				currentXDelta += medianNextLevel - rightLimit;
			}

			weightedValues[i].visited = true;
		}
	}

	/**
	 * Calculates the priority the specified cell has based on the type of its
	 * cell and the cells it is connected to on the next layer
	 * 
	 * @param currentCell
	 *            the cell whose weight is to be calculated
	 * @param collection
	 *            the cells the specified cell is connected to
	 * @return the total weighted of the edges between these cells
	 */
	private int calculatedWeightedValue(
			mxGraphAbstractHierarchyCell currentCell,
			Collection<mxGraphAbstractHierarchyCell> collection)
	{
		int totalWeight = 0;
		Iterator<mxGraphAbstractHierarchyCell> iter = collection.iterator();

		while (iter.hasNext())
		{
			mxGraphAbstractHierarchyCell cell = iter.next();

			if (currentCell.isVertex() && cell.isVertex())
			{
				totalWeight++;
			}
			else if (currentCell.isEdge() && cell.isEdge())
			{
				totalWeight += 8;
			}
			else
			{
				totalWeight += 2;
			}
		}

		return totalWeight;
	}

	/**
	 * Calculates the median position of the connected cell on the specified
	 * rank
	 * 
	 * @param connectedCells
	 *            the cells the candidate connects to on this level
	 * @param rankValue
	 *            the layer number of this rank
	 * @return the median rank order ( not x position ) of the connected cells
	 */
	private int medianXValue(Object[] connectedCells, int rankValue)
	{
		if (connectedCells.length == 0)
		{
			return 0;
		}

		int[] medianValues = new int[connectedCells.length];

		for (int i = 0; i < connectedCells.length; i++)
		{
			medianValues[i] = ((mxGraphAbstractHierarchyCell) connectedCells[i])
					.getGeneralPurposeVariable(rankValue);
		}

		Arrays.sort(medianValues);

		if (connectedCells.length % 2 == 1)
		{
			// For odd numbers of adjacent vertices return the median
			return medianValues[connectedCells.length / 2];
		}
		else
		{
			int medianPoint = connectedCells.length / 2;
			int leftMedian = medianValues[medianPoint - 1];
			int rightMedian = medianValues[medianPoint];

			return ((leftMedian + rightMedian) / 2);
		}
	}

	/**
	 * Sets up the layout in an initial positioning. The ranks are all centered
	 * as much as possible along the middle vertex in each rank. The other cells
	 * are then placed as close as possible on either side.
	 * 
	 * @param facade
	 *            the facade describing the input graph
	 * @param model
	 *            an internal model of the hierarchical layout
	 */
	private void initialCoords(mxGraph facade, mxGraphHierarchyModel model)
	{
		calculateWidestRank(facade, model);

		// Sweep up and down from the widest rank
		for (int i = widestRank; i >= 0; i--)
		{
			if (i < model.maxRank)
			{
				rankCoordinates(i, facade, model);
			}
		}

		for (int i = widestRank + 1; i <= model.maxRank; i++)
		{
			if (i > 0)
			{
				rankCoordinates(i, facade, model);
			}
		}
	}

	/**
	 * Sets up the layout in an initial positioning. All the first cells in each
	 * rank are moved to the left and the rest of the rank inserted as close
	 * together as their size and buffering permits. This method works on just
	 * the specified rank.
	 * 
	 * @param rankValue
	 *            the current rank being processed
	 * @param graph
	 *            the facade describing the input graph
	 * @param model
	 *            an internal model of the hierarchical layout
	 */
	protected void rankCoordinates(int rankValue, mxGraph graph,
			mxGraphHierarchyModel model)
	{
		mxGraphHierarchyRank rank = model.ranks.get(new Integer(rankValue));
		double maxY = 0.0;
		double localX = initialX + (widestRankValue - rankWidths[rankValue])
				/ 2;

		// Store whether or not any of the cells' bounds were unavailable so
		// to only issue the warning once for all cells
		boolean boundsWarning = false;
		Iterator<mxGraphAbstractHierarchyCell> iter = rank.iterator();

		while (iter.hasNext())
		{
			mxGraphAbstractHierarchyCell cell = (mxGraphAbstractHierarchyCell) iter
					.next();
			if (cell.isVertex())
			{
				mxGraphHierarchyNode node = (mxGraphHierarchyNode) cell;
				mxRectangle bounds = layout.getVertexBounds(node.cell);

				if (bounds != null)
				{
					if (orientation == SwingConstants.NORTH
							|| orientation == SwingConstants.SOUTH)
					{
						cell.width = bounds.getWidth();
						cell.height = bounds.getHeight();
					}
					else
					{
						cell.width = bounds.getHeight();
						cell.height = bounds.getWidth();
					}
				}
				else
				{
					boundsWarning = true;
				}

				maxY = Math.max(maxY, cell.height);
			}
			else if (cell.isEdge())
			{
				mxGraphHierarchyEdge edge = (mxGraphHierarchyEdge) cell;
				// The width is the number of additional parallel edges
				// time the parallel edge spacing
				int numEdges = 1;

				if (edge.edges != null)
				{
					numEdges = edge.edges.size();
				}
				else
				{
					logger.info("edge.edges is null");
				}

				cell.width = (numEdges - 1) * parallelEdgeSpacing;
			}

			// Set the initial x-value as being the best result so far
			localX += cell.width / 2.0;
			cell.setX(rankValue, localX);
			cell.setGeneralPurposeVariable(rankValue, (int) localX);
			localX += cell.width / 2.0;
			localX += intraCellSpacing;
		}

		if (boundsWarning == true)
		{
			logger.info("At least one cell has no bounds");
		}
	}

	/**
	 * Calculates the width rank in the hierarchy. Also set the y value of each
	 * rank whilst performing the calculation
	 * 
	 * @param graph
	 *            the facade describing the input graph
	 * @param model
	 *            an internal model of the hierarchical layout
	 */
	protected void calculateWidestRank(mxGraph graph,
			mxGraphHierarchyModel model)
	{
		// Starting y co-ordinate
		double y = -interRankCellSpacing;

		// Track the widest cell on the last rank since the y
		// difference depends on it
		double lastRankMaxCellHeight = 0.0;
		rankWidths = new double[model.maxRank + 1];
		rankY = new double[model.maxRank + 1];

		for (int rankValue = model.maxRank; rankValue >= 0; rankValue--)
		{
			// Keep track of the widest cell on this rank
			double maxCellHeight = 0.0;
			mxGraphHierarchyRank rank = model.ranks.get(new Integer(rankValue));
			double localX = initialX;

			// Store whether or not any of the cells' bounds were unavailable so
			// to only issue the warning once for all cells
			boolean boundsWarning = false;
			Iterator<mxGraphAbstractHierarchyCell> iter = rank.iterator();

			while (iter.hasNext())
			{
				mxGraphAbstractHierarchyCell cell = (mxGraphAbstractHierarchyCell) iter
						.next();

				if (cell.isVertex())
				{
					mxGraphHierarchyNode node = (mxGraphHierarchyNode) cell;
					mxRectangle bounds = layout.getVertexBounds(node.cell);

					if (bounds != null)
					{
						if (orientation == SwingConstants.NORTH
								|| orientation == SwingConstants.SOUTH)
						{
							cell.width = bounds.getWidth();
							cell.height = bounds.getHeight();
						}
						else
						{
							cell.width = bounds.getHeight();
							cell.height = bounds.getWidth();
						}
					}
					else
					{
						boundsWarning = true;
					}

					maxCellHeight = Math.max(maxCellHeight, cell.height);
				}
				else if (cell.isEdge())
				{
					mxGraphHierarchyEdge edge = (mxGraphHierarchyEdge) cell;
					// The width is the number of additional parallel edges
					// time the parallel edge spacing
					int numEdges = 1;

					if (edge.edges != null)
					{
						numEdges = edge.edges.size();
					}
					else
					{
						logger.info("edge.edges is null");
					}

					cell.width = (numEdges - 1) * parallelEdgeSpacing;
				}

				// Set the initial x-value as being the best result so far
				localX += cell.width / 2.0;
				cell.setX(rankValue, localX);
				cell.setGeneralPurposeVariable(rankValue, (int) localX);
				localX += cell.width / 2.0;
				localX += intraCellSpacing;

				if (localX > widestRankValue)
				{
					widestRankValue = localX;
					widestRank = rankValue;
				}

				rankWidths[rankValue] = localX;
			}

			if (boundsWarning == true)
			{
				logger.info("At least one cell has no bounds");
			}

			rankY[rankValue] = y;
			double distanceToNextRank = maxCellHeight / 2.0
					+ lastRankMaxCellHeight / 2.0 + interRankCellSpacing;
			lastRankMaxCellHeight = maxCellHeight;

			if (orientation == SwingConstants.NORTH
					|| orientation == SwingConstants.WEST)
			{
				y += distanceToNextRank;
			}
			else
			{
				y -= distanceToNextRank;
			}

			iter = rank.iterator();

			while (iter.hasNext())
			{
				mxGraphAbstractHierarchyCell cell = (mxGraphAbstractHierarchyCell) iter
						.next();
				cell.setY(rankValue, y);
			}
		}
	}

	/**
	 * Sets the cell locations in the facade to those stored after this layout
	 * processing step has completed.
	 * 
	 * @param graph
	 *            the facade describing the input graph
	 * @param model
	 *            an internal model of the hierarchical layout
	 */
	private void setCellLocations(mxGraph graph, mxGraphHierarchyModel model)
	{
		for (int i = 0; i < model.ranks.size(); i++)
		{
			mxGraphHierarchyRank rank = model.ranks.get(new Integer(i));

			Iterator<mxGraphAbstractHierarchyCell> iter = rank.iterator();
			while (iter.hasNext())
			{
				mxGraphAbstractHierarchyCell cell = (mxGraphAbstractHierarchyCell) iter
						.next();

				if (cell.isVertex())
				{
					mxGraphHierarchyNode node = (mxGraphHierarchyNode) cell;
					Object realCell = node.cell;
					double positionX = node.x[0] - node.width / 2;
					double positionY = node.y[0] - node.height / 2;

					if (orientation == SwingConstants.NORTH
							|| orientation == SwingConstants.SOUTH)
					{
						layout
								.setVertexLocation(realCell, positionX,
										positionY);
					}
					else
					{
						layout
								.setVertexLocation(realCell, positionY,
										positionX);
					}

					limitX = Math.max(limitX, positionX + node.width);
				}
				else if (cell.isEdge())
				{
					mxGraphHierarchyEdge edge = (mxGraphHierarchyEdge) cell;
					// For parallel edges we need to seperate out the points a
					// little
					double offsetX = 0.0;
					// Only set the edge control points once

					if (edge.temp[0] != 101207)
					{
						Iterator<Object> parallelEdges = edge.edges.iterator();

						while (parallelEdges.hasNext())
						{
							Object realEdge = parallelEdges.next();
							//List oldPoints = graph.getPoints(realEdge);
							List<mxPoint> newPoints = new ArrayList<mxPoint>(edge.x.length);

							if (edge.isReversed())
							{
								// Reversed edges need the points inserted in
								// reverse order
								for (int j = 0; j < edge.x.length; j++)
								{
									double positionX = edge.x[j] + offsetX;

									if (orientation == SwingConstants.NORTH
											|| orientation == SwingConstants.SOUTH)
									{
										newPoints.add(new mxPoint(positionX,
												edge.y[j]));
									}
									else
									{
										newPoints.add(new mxPoint(edge.y[j],
												positionX));
									}

									limitX = Math.max(limitX, positionX);
								}

								processReversedEdge(edge, realEdge);
							}
							else
							{
								for (int j = edge.x.length - 1; j >= 0; j--)
								{
									double positionX = edge.x[j] + offsetX;

									if (orientation == SwingConstants.NORTH
											|| orientation == SwingConstants.SOUTH)
									{
										newPoints.add(new mxPoint(positionX,
												edge.y[j]));
									}
									else
									{
										newPoints.add(new mxPoint(edge.y[j],
												positionX));
									}

									limitX = Math.max(limitX, positionX);
								}
							}

							layout.setEdgePoints(realEdge, newPoints);

							// Increase offset so next edge is drawn next to
							// this one
							if (offsetX == 0.0)
							{
								offsetX = parallelEdgeSpacing;
							}
							else if (offsetX > 0)
							{
								offsetX = -offsetX;
							}
							else
							{
								offsetX = -offsetX + parallelEdgeSpacing;
							}
						}

						edge.temp[0] = 101207;
					}
				}
			}
		}
	}

	/**
	 * Hook to add additional processing
	 * 
	 * @param edge
	 *            The hierarchical model edge
	 * @param realEdge
	 *            The real edge in the graph
	 */
	private void processReversedEdge(mxGraphHierarchyEdge edge, Object realEdge)
	{
		// Added as hook for customer
	}

	/**
	 * A utility class used to track cells whilst sorting occurs on the weighted
	 * sum of their connected edges. Does not violate (x.compareTo(y)==0) ==
	 * (x.equals(y))
	 */
	protected class WeightedCellSorter implements Comparable<Object>
	{

		/**
		 * The weighted value of the cell stored
		 */
		public int weightedValue = 0;

		/**
		 * Whether or not to flip equal weight values.
		 */
		public boolean nudge = false;

		/**
		 * Whether or not this cell has been visited in the current assignment
		 */
		public boolean visited = false;

		/**
		 * The index this cell is in the model rank
		 */
		public int rankIndex;

		/**
		 * The cell whose median value is being calculated
		 */
		public mxGraphAbstractHierarchyCell cell = null;

		public WeightedCellSorter()
		{
			this(null, 0);
		}

		public WeightedCellSorter(mxGraphAbstractHierarchyCell cell,
				int weightedValue)
		{
			this.cell = cell;
			this.weightedValue = weightedValue;
		}

		/**
		 * comparator on the medianValue
		 * 
		 * @param arg0
		 *            the object to be compared to
		 * @return the standard return you would expect when comparing two
		 *         double
		 */
		public int compareTo(Object arg0)
		{
			if (arg0 instanceof WeightedCellSorter)
			{
				if (weightedValue > ((WeightedCellSorter) arg0).weightedValue)
				{
					return -1;
				}
				else if (weightedValue < ((WeightedCellSorter) arg0).weightedValue)
				{
					return 1;
				}
				else
				{
					if (nudge)
					{
						return -1;
					}
					else
					{
						return 1;
					}
				}
			}
			else
			{
				return 0;
			}
		}

	}

	/**
	 * Utility class that stores a collection of vertices and edge points within
	 * a certain area. This area includes the buffer lengths of cells.
	 */
	@SuppressWarnings("serial")
	protected class AreaSpatialCache extends Rectangle2D.Double
	{
		public Set<Object> cells = new HashSet<Object>();
	}

	/**
	 * @return Returns the interRankCellSpacing.
	 */
	public double getInterRankCellSpacing()
	{
		return interRankCellSpacing;
	}

	/**
	 * @param interRankCellSpacing
	 *            The interRankCellSpacing to set.
	 */
	public void setInterRankCellSpacing(double interRankCellSpacing)
	{
		this.interRankCellSpacing = interRankCellSpacing;
	}

	/**
	 * @return Returns the intraCellSpacing.
	 */
	public double getIntraCellSpacing()
	{
		return intraCellSpacing;
	}

	/**
	 * @param intraCellSpacing
	 *            The intraCellSpacing to set.
	 */
	public void setIntraCellSpacing(double intraCellSpacing)
	{
		this.intraCellSpacing = intraCellSpacing;
	}

	/**
	 * @return Returns the orientation.
	 */
	public int getOrientation()
	{
		return orientation;
	}

	/**
	 * @param orientation
	 *            The orientation to set.
	 */
	public void setOrientation(int orientation)
	{
		this.orientation = orientation;
	}

	/**
	 * @return Returns the limitX.
	 */
	public double getLimitX()
	{
		return limitX;
	}

	/**
	 * @param limitX
	 *            The limitX to set.
	 */
	public void setLimitX(double limitX)
	{
		this.limitX = limitX;
	}

	/**
	 * @return Returns the fineTuning.
	 */
	public boolean isFineTuning()
	{
		return fineTuning;
	}

	/**
	 * @param fineTuning
	 *            The fineTuning to set.
	 */
	public void setFineTuning(boolean fineTuning)
	{
		this.fineTuning = fineTuning;
	}

	/**
	 * Sets the logging level of this class
	 * 
	 * @param level
	 *            the logging level to set
	 */
	public void setLoggerLevel(Level level)
	{
		try
		{
			logger.setLevel(level);
		}
		catch (SecurityException e)
		{
			// Probably running in an applet
		}
	}
}
