text: /**
   * Copyright (c) 2006-2015, JGraph Ltd
   * Copyright (c) 2006-2015, Gaudenz Alder
   */
  /**
   * Class: mxMedianHybridCrossingReduction
   * 
   * 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.
   * 
   * Constructor: mxMedianHybridCrossingReduction
   *
   * Creates a coordinate assignment.
   * 
   * Arguments:
   * 
   * intraCellSpacing - the minimum buffer between cells on the same rank
   * interRankCellSpacing - the minimum distance between cells on adjacent ranks
   * orientation - the position of the root node(s) relative to the graph
   * initialX - the leftmost coordinate node placement starts at
   */
  function mxMedianHybridCrossingReduction(layout)
  {
  	this.layout = layout;
  };
  
  /**
   * Extends mxMedianHybridCrossingReduction.
   */
  mxMedianHybridCrossingReduction.prototype = new mxHierarchicalLayoutStage();
  mxMedianHybridCrossingReduction.prototype.constructor = mxMedianHybridCrossingReduction;
  
  /**
   * Variable: layout
   * 
   * Reference to the enclosing <mxHierarchicalLayout>.
   */
  mxMedianHybridCrossingReduction.prototype.layout = null;
  
  /**
   * Variable: maxIterations
   * 
   * The maximum number of iterations to perform whilst reducing edge
   * crossings. Default is 24.
   */
  mxMedianHybridCrossingReduction.prototype.maxIterations = 24;
  
  /**
   * Variable: nestedBestRanks
   * 
   * Stores each rank as a collection of cells in the best order found for
   * each layer so far
   */
  mxMedianHybridCrossingReduction.prototype.nestedBestRanks = null;
  
  /**
   * Variable: currentBestCrossings
   * 
   * The total number of crossings found in the best configuration so far
   */
  mxMedianHybridCrossingReduction.prototype.currentBestCrossings = 0;
  
  /**
   * Variable: iterationsWithoutImprovement
   * 
   * The total number of crossings found in the best configuration so far
   */
  mxMedianHybridCrossingReduction.prototype.iterationsWithoutImprovement = 0;
  
  /**
   * Variable: maxNoImprovementIterations
   * 
   * The total number of crossings found in the best configuration so far
   */
  mxMedianHybridCrossingReduction.prototype.maxNoImprovementIterations = 2;
  
  /**
   * Function: execute
   * 
   * Performs a vertex ordering within ranks as described by Gansner et al
   * 1993
   */
  mxMedianHybridCrossingReduction.prototype.execute = function(parent)
  {
  	var model = this.layout.getModel();
  
  	// Stores initial ordering as being the best one found so far
  	this.nestedBestRanks = [];
  	
  	for (var i = 0; i < model.ranks.length; i++)
  	{
  		this.nestedBestRanks[i] = model.ranks[i].slice();
  	}
  
  	var iterationsWithoutImprovement = 0;
  	var currentBestCrossings = this.calculateCrossings(model);
  
  	for (var i = 0; i < this.maxIterations &&
  		iterationsWithoutImprovement < this.maxNoImprovementIterations; i++)
  	{
  		this.weightedMedian(i, model);
  		this.transpose(i, model);
  		var candidateCrossings = this.calculateCrossings(model);
  
  		if (candidateCrossings < currentBestCrossings)
  		{
  			currentBestCrossings = candidateCrossings;
  			iterationsWithoutImprovement = 0;
  
  			// Store the current rankings as the best ones
  			for (var j = 0; j < this.nestedBestRanks.length; j++)
  			{
  				var rank = model.ranks[j];
  
  				for (var k = 0; k < rank.length; k++)
  				{
  					var cell = rank[k];
  					this.nestedBestRanks[j][cell.getGeneralPurposeVariable(j)] = cell;
  				}
  			}
  		}
  		else
  		{
  			// Increase count of iterations where we haven't improved the
  			// layout
  			iterationsWithoutImprovement++;
  
  			// Restore the best values to the cells
  			for (var j = 0; j < this.nestedBestRanks.length; j++)
  			{
  				var rank = model.ranks[j];
  				
  				for (var k = 0; k < rank.length; k++)
  				{
  					var cell = rank[k];
  					cell.setGeneralPurposeVariable(j, k);
  				}
  			}
  		}
  		
  		if (currentBestCrossings == 0)
  		{
  			// Do nothing further
  			break;
  		}
  	}
  
  	// Store the best rankings but in the model
  	var ranks = [];
  	var rankList = [];
  
  	for (var i = 0; i < model.maxRank + 1; i++)
  	{
  		rankList[i] = [];
  		ranks[i] = rankList[i];
  	}
  
  	for (var i = 0; i < this.nestedBestRanks.length; i++)
  	{
  		for (var j = 0; j < this.nestedBestRanks[i].length; j++)
  		{
  			rankList[i].push(this.nestedBestRanks[i][j]);
  		}
  	}
  
  	model.ranks = ranks;
  };
  
  
  /**
   * Function: calculateCrossings
   * 
   * Calculates the total number of edge crossing in the current graph.
   * Returns the current number of edge crossings in the hierarchy graph
   * model in the current candidate layout
   * 
   * Parameters:
   * 
   * model - the internal model describing the hierarchy
   */
  mxMedianHybridCrossingReduction.prototype.calculateCrossings = function(model)
  {
  	var numRanks = model.ranks.length;
  	var totalCrossings = 0;
  
  	for (var i = 1; i < numRanks; i++)
  	{
  		totalCrossings += this.calculateRankCrossing(i, model);
  	}
  	
  	return totalCrossings;
  };
  
  /**
   * Function: calculateRankCrossing
   * 
   * Calculates the number of edges crossings between the specified rank and
   * the rank below it. Returns the number of edges crossings with the rank
   * beneath
   * 
   * Parameters:
   * 
   * i -  the topmost rank of the pair ( higher rank value )
   * model - the internal model describing the hierarchy
   */
  mxMedianHybridCrossingReduction.prototype.calculateRankCrossing = function(i, model)
  {
  	var totalCrossings = 0;
  	var rank = model.ranks[i];
  	var previousRank = model.ranks[i - 1];
  
  	var tmpIndices = [];
  
  	// Iterate over the top rank and fill in the connection information
  	for (var j = 0; j < rank.length; j++)
  	{
  		var node = rank[j];
  		var rankPosition = node.getGeneralPurposeVariable(i);
  		var connectedCells = node.getPreviousLayerConnectedCells(i);
  		var nodeIndices = [];
  
  		for (var k = 0; k < connectedCells.length; k++)
  		{
  			var connectedNode = connectedCells[k];
  			var otherCellRankPosition = connectedNode.getGeneralPurposeVariable(i - 1);
  			nodeIndices.push(otherCellRankPosition);
  		}
  		
  		nodeIndices.sort(function(x, y) { return x - y; });
  		tmpIndices[rankPosition] = nodeIndices;
  	}
  	
  	var indices = [];
  
  	for (var j = 0; j < tmpIndices.length; j++)
  	{
  		indices = indices.concat(tmpIndices[j]);
  	}
  
  	var firstIndex = 1;
  	
  	while (firstIndex < previousRank.length)
  	{
  		firstIndex <<= 1;
  	}
  
  	var treeSize = 2 * firstIndex - 1;
  	firstIndex -= 1;
  
  	var tree = [];
  	
  	for (var j = 0; j < treeSize; ++j)
  	{
  		tree[j] = 0;
  	}
  
  	for (var j = 0; j < indices.length; j++)
  	{
  		var index = indices[j];
  	    var treeIndex = index + firstIndex;
  	    ++tree[treeIndex];
  	    
  	    while (treeIndex > 0)
  	    {
  	    	if (treeIndex % 2)
  	    	{
  	    		totalCrossings += tree[treeIndex + 1];
  	    	}
  	      
  	    	treeIndex = (treeIndex - 1) >> 1;
  	    	++tree[treeIndex];
  	    }
  	}
  
  	return totalCrossings;
  };
  
  /**
   * Function: transpose
   * 
   * Takes each possible adjacent cell pair on each rank and checks if
   * swapping them around reduces the number of crossing
   * 
   * Parameters:
   * 
   * mainLoopIteration - the iteration number of the main loop
   * model - the internal model describing the hierarchy
   */
  mxMedianHybridCrossingReduction.prototype.transpose = function(mainLoopIteration, model)
  {
  	var improved = true;
  
  	// Track the number of iterations in case of looping
  	var count = 0;
  	var maxCount = 10;
  	while (improved && count++ < maxCount)
  	{
  		// On certain iterations allow allow swapping of cell pairs with
  		// equal edge crossings switched or not switched. This help to
  		// nudge a stuck layout into a lower crossing total.
  		var nudge = mainLoopIteration % 2 == 1 && count % 2 == 1;
  		improved = false;
  		
  		for (var i = 0; i < model.ranks.length; i++)
  		{
  			var rank = model.ranks[i];
  			var orderedCells = [];
  			
  			for (var j = 0; j < rank.length; j++)
  			{
  				var cell = rank[j];
  				var tempRank = cell.getGeneralPurposeVariable(i);
  				
  				// FIXME: Workaround to avoid negative tempRanks
  				if (tempRank < 0)
  				{
  					tempRank = j;
  				}
  				orderedCells[tempRank] = cell;
  			}
  			
  			var leftCellAboveConnections = null;
  			var leftCellBelowConnections = null;
  			var rightCellAboveConnections = null;
  			var rightCellBelowConnections = null;
  			
  			var leftAbovePositions = null;
  			var leftBelowPositions = null;
  			var rightAbovePositions = null;
  			var rightBelowPositions = null;
  			
  			var leftCell = null;
  			var rightCell = null;
  
  			for (var j = 0; j < (rank.length - 1); j++)
  			{
  				// For each intra-rank adjacent pair of cells
  				// see if swapping them around would reduce the
  				// number of edges crossing they cause in total
  				// On every cell pair except the first on each rank, we
  				// can save processing using the previous values for the
  				// right cell on the new left cell
  				if (j == 0)
  				{
  					leftCell = orderedCells[j];
  					leftCellAboveConnections = leftCell
  							.getNextLayerConnectedCells(i);
  					leftCellBelowConnections = leftCell
  							.getPreviousLayerConnectedCells(i);
  					leftAbovePositions = [];
  					leftBelowPositions = [];
  					
  					for (var k = 0; k < leftCellAboveConnections.length; k++)
  					{
  						leftAbovePositions[k] = leftCellAboveConnections[k].getGeneralPurposeVariable(i + 1);
  					}
  					
  					for (var k = 0; k < leftCellBelowConnections.length; k++)
  					{
  						leftBelowPositions[k] = leftCellBelowConnections[k].getGeneralPurposeVariable(i - 1);
  					}
  				}
  				else
  				{
  					leftCellAboveConnections = rightCellAboveConnections;
  					leftCellBelowConnections = rightCellBelowConnections;
  					leftAbovePositions = rightAbovePositions;
  					leftBelowPositions = rightBelowPositions;
  					leftCell = rightCell;
  				}
  				
  				rightCell = orderedCells[j + 1];
  				rightCellAboveConnections = rightCell
  						.getNextLayerConnectedCells(i);
  				rightCellBelowConnections = rightCell
  						.getPreviousLayerConnectedCells(i);
  
  				rightAbovePositions = [];
  				rightBelowPositions = [];
  
  				for (var k = 0; k < rightCellAboveConnections.length; k++)
  				{
  					rightAbovePositions[k] = rightCellAboveConnections[k].getGeneralPurposeVariable(i + 1);
  				}
  				
  				for (var k = 0; k < rightCellBelowConnections.length; k++)
  				{
  					rightBelowPositions[k] = rightCellBelowConnections[k].getGeneralPurposeVariable(i - 1);
  				}
  
  				var totalCurrentCrossings = 0;
  				var totalSwitchedCrossings = 0;
  				
  				for (var k = 0; k < leftAbovePositions.length; k++)
  				{
  					for (var ik = 0; ik < rightAbovePositions.length; ik++)
  					{
  						if (leftAbovePositions[k] > rightAbovePositions[ik])
  						{
  							totalCurrentCrossings++;
  						}
  
  						if (leftAbovePositions[k] < rightAbovePositions[ik])
  						{
  							totalSwitchedCrossings++;
  						}
  					}
  				}
  				
  				for (var k = 0; k < leftBelowPositions.length; k++)
  				{
  					for (var ik = 0; ik < rightBelowPositions.length; ik++)
  					{
  						if (leftBelowPositions[k] > rightBelowPositions[ik])
  						{
  							totalCurrentCrossings++;
  						}
  
  						if (leftBelowPositions[k] < rightBelowPositions[ik])
  						{
  							totalSwitchedCrossings++;
  						}
  					}
  				}
  				
  				if ((totalSwitchedCrossings < totalCurrentCrossings) ||
  					(totalSwitchedCrossings == totalCurrentCrossings &&
  					nudge))
  				{
  					var temp = leftCell.getGeneralPurposeVariable(i);
  					leftCell.setGeneralPurposeVariable(i, rightCell
  							.getGeneralPurposeVariable(i));
  					rightCell.setGeneralPurposeVariable(i, temp);
  
  					// With this pair exchanged we have to switch all of
  					// values for the left cell to the right cell so the
  					// next iteration for this rank uses it as the left
  					// cell again
  					rightCellAboveConnections = leftCellAboveConnections;
  					rightCellBelowConnections = leftCellBelowConnections;
  					rightAbovePositions = leftAbovePositions;
  					rightBelowPositions = leftBelowPositions;
  					rightCell = leftCell;
  					
  					if (!nudge)
  					{
  						// Don't count nudges as improvement or we'll end
  						// up stuck in two combinations and not finishing
  						// as early as we should
  						improved = true;
  					}
  				}
  			}
  		}
  	}
  };
  
  /**
   * Function: weightedMedian
   * 
   * Sweeps up or down the layout attempting to minimise the median placement
   * of connected cells on adjacent ranks
   * 
   * Parameters:
   * 
   * iteration - the iteration number of the main loop
   * model - the internal model describing the hierarchy
   */
  mxMedianHybridCrossingReduction.prototype.weightedMedian = function(iteration, model)
  {
  	// Reverse sweep direction each time through this method
  	var downwardSweep = (iteration % 2 == 0);
  	if (downwardSweep)
  	{
  		for (var j = model.maxRank - 1; j >= 0; j--)
  		{
  			this.medianRank(j, downwardSweep);
  		}
  	}
  	else
  	{
  		for (var j = 1; j < model.maxRank; j++)
  		{
  			this.medianRank(j, downwardSweep);
  		}
  	}
  };
  
  /**
   * Function: medianRank
   * 
   * Attempts to minimise the median placement of connected cells on this rank
   * and one of the adjacent ranks
   * 
   * Parameters:
   * 
   * rankValue - the layer number of this rank
   * downwardSweep - whether or not this is a downward sweep through the graph
   */
  mxMedianHybridCrossingReduction.prototype.medianRank = function(rankValue, downwardSweep)
  {
  	var numCellsForRank = this.nestedBestRanks[rankValue].length;
  	var medianValues = [];
  	var reservedPositions = [];
  
  	for (var i = 0; i < numCellsForRank; i++)
  	{
  		var cell = this.nestedBestRanks[rankValue][i];
  		var sorterEntry = new MedianCellSorter();
  		sorterEntry.cell = cell;
  
  		// Flip whether or not equal medians are flipped on up and down
  		// sweeps
  		// TODO re-implement some kind of nudge
  		// medianValues[i].nudge = !downwardSweep;
  		var nextLevelConnectedCells;
  		
  		if (downwardSweep)
  		{
  			nextLevelConnectedCells = cell
  					.getNextLayerConnectedCells(rankValue);
  		}
  		else
  		{
  			nextLevelConnectedCells = cell
  					.getPreviousLayerConnectedCells(rankValue);
  		}
  		
  		var nextRankValue;
  		
  		if (downwardSweep)
  		{
  			nextRankValue = rankValue + 1;
  		}
  		else
  		{
  			nextRankValue = rankValue - 1;
  		}
  
  		if (nextLevelConnectedCells != null
  				&& nextLevelConnectedCells.length != 0)
  		{
  			sorterEntry.medianValue = this.medianValue(
  					nextLevelConnectedCells, nextRankValue);
  			medianValues.push(sorterEntry);
  		}
  		else
  		{
  			// Nodes with no adjacent vertices are flagged in the reserved array
  			// to indicate they should be left in their current position.
  			reservedPositions[cell.getGeneralPurposeVariable(rankValue)] = true;
  		}
  	}
  	
  	medianValues.sort(MedianCellSorter.prototype.compare);
  	
  	// Set the new position of each node within the rank using
  	// its temp variable
  	for (var i = 0; i < numCellsForRank; i++)
  	{
  		if (reservedPositions[i] == null)
  		{
  			var cell = medianValues.shift().cell;
  			cell.setGeneralPurposeVariable(rankValue, i);
  		}
  	}
  };
  
  /**
   * Function: medianValue
   * 
   * Calculates the median rank order positioning for the specified cell using
   * the connected cells on the specified rank. Returns the median rank
   * ordering value of the connected cells
   * 
   * Parameters:
   * 
   * connectedCells - the cells on the specified rank connected to the
   * specified cell
   * rankValue - the rank that the connected cell lie upon
   */
  mxMedianHybridCrossingReduction.prototype.medianValue = function(connectedCells, rankValue)
  {
  	var medianValues = [];
  	var arrayCount = 0;
  	
  	for (var i = 0; i < connectedCells.length; i++)
  	{
  		var cell = connectedCells[i];
  		medianValues[arrayCount++] = cell.getGeneralPurposeVariable(rankValue);
  	}
  
  	// Sort() sorts lexicographically by default (i.e. 11 before 9) so force
  	// numerical order sort
  	medianValues.sort(function(a,b){return a - b;});
  	
  	if (arrayCount % 2 == 1)
  	{
  		// For odd numbers of adjacent vertices return the median
  		return medianValues[Math.floor(arrayCount / 2)];
  	}
  	else if (arrayCount == 2)
  	{
  		return ((medianValues[0] + medianValues[1]) / 2.0);
  	}
  	else
  	{
  		var medianPoint = arrayCount / 2;
  		var leftMedian = medianValues[medianPoint - 1] - medianValues[0];
  		var rightMedian = medianValues[arrayCount - 1]
  				- medianValues[medianPoint];
  
  		return (medianValues[medianPoint - 1] * rightMedian + medianValues[medianPoint]* leftMedian) / (leftMedian + rightMedian);
  	}
  };
  
  /**
   * Class: MedianCellSorter
   * 
   * A utility class used to track cells whilst sorting occurs on the median
   * values. Does not violate (x.compareTo(y)==0) == (x.equals(y))
   *
   * Constructor: MedianCellSorter
   * 
   * Constructs a new median cell sorter.
   */
  function MedianCellSorter()
  {
  	// empty
  };
  
  /**
   * Variable: medianValue
   * 
   * The weighted value of the cell stored.
   */
  MedianCellSorter.prototype.medianValue = 0;
  
  /**
   * Variable: cell
   * 
   * The cell whose median value is being calculated
   */
  MedianCellSorter.prototype.cell = false;
  
  /**
   * Function: compare
   * 
   * Compares two MedianCellSorters.
   */
  MedianCellSorter.prototype.compare = function(a, b)
  {
  	if (a != null && b != null)
  	{
  		if (b.medianValue > a.medianValue)
  		{
  			return -1;
  		}
  		else if (b.medianValue < a.medianValue)
  		{
  			return 1;
  		}
  		else
  		{
  			return 0;
  		}
  	}
  	else
  	{
  		return 0;
  	}
  };
  
  exports.mxMedianHybridCrossingReduction = mxMedianHybridCrossingReduction;
  