/**
 * Copyright (c) 2006-2015, JGraph Ltd
 * Copyright (c) 2006-2015, Gaudenz Alder
 */
/**
 * Class: mxRadialTreeLayout
 * 
 * Extends <mxGraphLayout> to implement a radial tree algorithm. This
 * layout is suitable for graphs that have no cycles (trees). Vertices that are
 * not connected to the tree will be ignored by this layout.
 * 
 * Example:
 * 
 * (code)
 * var layout = new mxRadialTreeLayout(graph);
 * layout.execute(graph.getDefaultParent());
 * (end)
 * 
 * Constructor: mxRadialTreeLayout
 * 
 * Constructs a new radial tree layout for the specified graph
 */
function mxRadialTreeLayout(graph)
{
	mxCompactTreeLayout.call(this, graph , false);
};

/**
 * Extends mxGraphLayout.
 */
mxUtils.extend(mxRadialTreeLayout, mxCompactTreeLayout);

/**
 * Variable: angleOffset
 *
 * The initial offset to compute the angle position.
 */
mxRadialTreeLayout.prototype.angleOffset = 0.5;

/**
 * Variable: rootx
 *
 * The X co-ordinate of the root cell
 */
mxRadialTreeLayout.prototype.rootx = 0;

/**
 * Variable: rooty
 *
 * The Y co-ordinate of the root cell
 */
mxRadialTreeLayout.prototype.rooty = 0;

/**
 * Variable: levelDistance
 *
 * Holds the levelDistance. Default is 120.
 */
mxRadialTreeLayout.prototype.levelDistance = 120;

/**
 * Variable: nodeDistance
 *
 * Holds the nodeDistance. Default is 10.
 */
mxRadialTreeLayout.prototype.nodeDistance = 10;

/**
 * Variable: autoRadius
 * 
 * Specifies if the radios should be computed automatically
 */
mxRadialTreeLayout.prototype.autoRadius = false;

/**
 * Variable: sortEdges
 * 
 * Specifies if edges should be sorted according to the order of their
 * opposite terminal cell in the model.
 */
mxRadialTreeLayout.prototype.sortEdges = false;

/**
 * Variable: rowMinX
 * 
 * Array of leftmost x coordinate of each row
 */
mxRadialTreeLayout.prototype.rowMinX = [];

/**
 * Variable: rowMaxX
 * 
 * Array of rightmost x coordinate of each row
 */
mxRadialTreeLayout.prototype.rowMaxX = [];

/**
 * Variable: rowMinCenX
 * 
 * Array of x coordinate of leftmost vertex of each row
 */
mxRadialTreeLayout.prototype.rowMinCenX = [];

/**
 * Variable: rowMaxCenX
 * 
 * Array of x coordinate of rightmost vertex of each row
 */
mxRadialTreeLayout.prototype.rowMaxCenX = [];

/**
 * Variable: rowRadi
 * 
 * Array of y deltas of each row behind root vertex, also the radius in the tree
 */
mxRadialTreeLayout.prototype.rowRadi = [];

/**
 * Variable: row
 * 
 * Array of vertices on each row
 */
mxRadialTreeLayout.prototype.row = [];

/**
 * Function: isVertexIgnored
 * 
 * Returns a boolean indicating if the given <mxCell> should be ignored as a
 * vertex. This returns true if the cell has no connections.
 * 
 * Parameters:
 * 
 * vertex - <mxCell> whose ignored state should be returned.
 */
mxRadialTreeLayout.prototype.isVertexIgnored = function(vertex)
{
	return mxGraphLayout.prototype.isVertexIgnored.apply(this, arguments) ||
		this.graph.getConnections(vertex).length == 0;
};

/**
 * Function: execute
 * 
 * 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.
 * 
 * Parameters:
 * 
 * parent - <mxCell> whose children should be laid out.
 * root - Optional <mxCell> that will be used as the root of the tree.
 */
mxRadialTreeLayout.prototype.execute = function(parent, root)
{
	this.parent = parent;
	
	this.useBoundingBox = false;
	this.edgeRouting = false;
	//this.horizontal = false;

	mxCompactTreeLayout.prototype.execute.apply(this, arguments);
	
	var bounds = null;
	var rootBounds = this.getVertexBounds(this.root);
	this.centerX = rootBounds.x + rootBounds.width / 2;
	this.centerY = rootBounds.y + rootBounds.height / 2;

	// Calculate the bounds of the involved vertices directly from the values set in the compact tree
	for (var vertex in this.visited)
	{
		var vertexBounds = this.getVertexBounds(this.visited[vertex]);
		bounds = (bounds != null) ? bounds : vertexBounds.clone();
		bounds.add(vertexBounds);
	}
	
	this.calcRowDims([this.node], 0);
	
	var maxLeftGrad = 0;
	var maxRightGrad = 0;

	// Find the steepest left and right gradients
	for (var i = 0; i < this.row.length; i++)
	{
		var leftGrad = (this.centerX - this.rowMinX[i] - this.nodeDistance) / this.rowRadi[i];
		var rightGrad = (this.rowMaxX[i] - this.centerX - this.nodeDistance) / this.rowRadi[i];
		
		maxLeftGrad = Math.max (maxLeftGrad, leftGrad);
		maxRightGrad = Math.max (maxRightGrad, rightGrad);
	}
	
	// Extend out row so they meet the maximum gradient and convert to polar co-ords
	for (var i = 0; i < this.row.length; i++)
	{
		var xLeftLimit = this.centerX - this.nodeDistance - maxLeftGrad * this.rowRadi[i];
		var xRightLimit = this.centerX + this.nodeDistance + maxRightGrad * this.rowRadi[i];
		var fullWidth = xRightLimit - xLeftLimit;
		
		for (var j = 0; j < this.row[i].length; j ++)
		{
			var row = this.row[i];
			var node = row[j];
			var vertexBounds = this.getVertexBounds(node.cell);
			var xProportion = (vertexBounds.x + vertexBounds.width / 2 - xLeftLimit) / (fullWidth);
			var theta =  2 * Math.PI * xProportion;
			node.theta = theta;
		}
	}

	// Post-process from outside inwards to try to align parents with children
	for (var i = this.row.length - 2; i >= 0; i--)
	{
		var row = this.row[i];
		
		for (var j = 0; j < row.length; j++)
		{
			var node = row[j];
			var child = node.child;
			var counter = 0;
			var totalTheta = 0;
			
			while (child != null)
			{
				totalTheta += child.theta;
				counter++;
				child = child.next;
			}
			
			if (counter > 0)
			{
				var averTheta = totalTheta / counter;
				
				if (averTheta > node.theta && j < row.length - 1)
				{
					var nextTheta = row[j+1].theta;
					node.theta = Math.min (averTheta, nextTheta - Math.PI/10);
				}
				else if (averTheta < node.theta && j > 0 )
				{
					var lastTheta = row[j-1].theta;
					node.theta = Math.max (averTheta, lastTheta + Math.PI/10);
				}
			}
		}
	}
	
	// Set locations
	for (var i = 0; i < this.row.length; i++)
	{
		for (var j = 0; j < this.row[i].length; j ++)
		{
			var row = this.row[i];
			var node = row[j];
			var vertexBounds = this.getVertexBounds(node.cell);
			this.setVertexLocation(node.cell,
									this.centerX - vertexBounds.width / 2 + this.rowRadi[i] * Math.cos(node.theta),
									this.centerY - vertexBounds.height / 2 + this.rowRadi[i] * Math.sin(node.theta));
		}
	}
};

/**
 * Function: calcRowDims
 * 
 * Recursive function to calculate the dimensions of each row
 * 
 * Parameters:
 * 
 * row - Array of internal nodes, the children of which are to be processed.
 * rowNum - Integer indicating which row is being processed.
 */
mxRadialTreeLayout.prototype.calcRowDims = function(row, rowNum)
{
	if (row == null || row.length == 0)
	{
		return;
	}

	// Place root's children proportionally around the first level
	this.rowMinX[rowNum] = this.centerX;
	this.rowMaxX[rowNum] = this.centerX;
	this.rowMinCenX[rowNum] = this.centerX;
	this.rowMaxCenX[rowNum] = this.centerX;
	this.row[rowNum] = [];

	var rowHasChildren = false;

	for (var i = 0; i < row.length; i++)
	{
		var child = row[i] != null ? row[i].child : null;

		while (child != null)
		{
			var cell = child.cell;
			vertexBounds = this.getVertexBounds(cell);
			
			this.rowMinX[rowNum] = Math.min(vertexBounds.x, this.rowMinX[rowNum]);
			this.rowMaxX[rowNum] = Math.max(vertexBounds.x + vertexBounds.width, this.rowMaxX[rowNum]);
			this.rowMinCenX[rowNum] = Math.min(vertexBounds.x + vertexBounds.width / 2, this.rowMinCenX[rowNum]);
			this.rowMaxCenX[rowNum] = Math.max(vertexBounds.x + vertexBounds.width / 2, this.rowMaxCenX[rowNum]);
			this.rowRadi[rowNum] = vertexBounds.y - this.getVertexBounds(this.root).y;
	
			if (child.child != null)
			{
				rowHasChildren = true;
			}
			this.row[rowNum].push(child);
			child = child.next;
		}
	}
	
	if (rowHasChildren)
	{
		this.calcRowDims(this.row[rowNum], rowNum + 1);
	}
};