AncestorLayout.js #1

/*
The ancestor layout takes a set of related streams and lays them out on a grid.  The grid is made up
of sets of rows, each set which represent a stream's stability, and columns, which represent a stream's ancestry (i.e. the farther
away a stream is from the mainline in terms of ancestry, the further to the right on the grid it will be positioned.

Here is a graph of how it works.  Main is 0 stability, and each number below represents a single node's stability:

			<----------------------Ancestry (distance from main)-------------------------->
			|			
			|			2
			|			2
	 level 2------------------------------------------------------------------------------
			|		1	
			|		1
			|		1		1(this would be a dev stream branched off a 2 release stream)
	 level 1------------------------------------------------------------------------------
Stability	|	0
	level -1------------------------------------------------------------------------------
			|		-1
	level -2------------------------------------------------------------------------------
			|			-2		-2(this would be a release stream branched off a -3 dev stream)
			|			-2
	level -3------------------------------------------------------------------------------
			|				-3

*/
function AncestorLayout(streamUtilities)
{
	var mStreamUtilities = streamUtilities;
	
	var mStabilityLevel = {};
	var mAncestorColumns = {};
	var mHighestAncestor = 0;
	var mHighestStability = 0;
	var mLowestStability = 0;
	var columnWidth = 240;
	
	function sortNodeByFirmerThanParent(nodeA, nodeB)
	{
		if( nodeA.stream.mFirmerThanParent && nodeB.stream.mFirmerThanParent )
			return 0;
		else if ( !nodeA.stream.mFirmerThanParent )
			return 1;
		return -1;
	}

	this.treeLayout = function(rootNode)
	{
		//set stability
		//the root node is not visible, get it's children (the mainlines) and start from there.
		//TODO: only works with depots with one mainline
		var stability = 0;
		var ancestorColumn = 0;
		var children = rootNode.children();
		for(var i = 0; i < children.length; i++)
		{
			var mainlineNode = children[i];
			layoutStability(mainlineNode, stability);
			layoutAncestory(mainlineNode, ancestorColumn);
			layoutFromMainline(mainlineNode)
			
			mStabilityLevel = {};
			mAncestorColumns = {};
			mHighestAncestor = 0;
			mHighestStability = 0;
			mLowestStability = 0;
	
		}
	}
	
	var mX = 0;
	function layoutFromMainline(mainlineNode)
	{
		mainlineNode.mX = mX;

		//set the x values for each node
		for( var i = 0; i < mHighestAncestor + 1; i++ )
		{
			mX += columnWidth;
			
			var ancestorColumn = mAncestorColumns[i];
			for( node in ancestorColumn )
			{
				//console.log('setting X for ' + ancestorColumn[node].stream.mName + ' to ' + columnWidth * i);
				ancestorColumn[node].mX = mX;
			}
		}
		
		mainlineNode.graphWidth = columnWidth + (mX - mainlineNode.getX());//this will be used to help draw stability rows behind the graph
		
		//for each stability level, establish the height of that level (which is based upon the number of nodes in the column 
		//with the highest number of streams for that level).  Now re-read that sentence five times to understand it.
		var stabilityLevelHeight = {};
		for( var column = 0; column < mHighestAncestor + 1; column++ )
		{
			for( var level = 0; level < mHighestStability + 1; level++ )
			{
				var rows = 0;
				for( node in mStabilityLevel[level] )
					if( mStabilityLevel[level][node].ancestorColumn == column ) 
						rows++;

				if( !stabilityLevelHeight[level] )
					stabilityLevelHeight[level] = 0;
				
				if( rows > stabilityLevelHeight[level] )
					stabilityLevelHeight[level] = rows;
			}

			for( var level = -1; level > mLowestStability - 1; level-- )
			{
				var rows = 0;
				for( node in mStabilityLevel[level] )
					if( mStabilityLevel[level][node].ancestorColumn == column ) 
						rows++;

				if( !stabilityLevelHeight[level] )
					stabilityLevelHeight[level] = 0;
					
				if( rows > stabilityLevelHeight[level] )
					stabilityLevelHeight[level] = rows;
			}
		}
		
		mainlineNode.stabilityLevelHeights = stabilityLevelHeight;//this is going to be used to draw stability rows behind the graph
		
		//sort levels to minimize overlapping lines
		for( var level = 0; level < mHighestStability + 1; level++ )
			mStabilityLevel[level].sort(sortNodeByFirmerThanParent);

		for( var level = -1; level > mLowestStability - 1; level-- )
			mStabilityLevel[level].sort(sortNodeByFirmerThanParent);
		
		//finally assign a row number to each node, moving to the right one column at a time
		for( var column = 0; column < mHighestAncestor + 1; column++ )
		{
			var previousRowsAccumulated = 0;
			
			//starting with mainline at 0, moving up
			for( var level = 0; level < mHighestStability + 1; level++ )
			{
				var row = 0;
				for( node in mStabilityLevel[level] )
				{
					if( mStabilityLevel[level][node].ancestorColumn == column ) 
					{
						//console.log('setting ' + mStabilityLevel[level][node].stream.mName + ' to row: ' + (previousRowsAccumulated + row) + ' previousRowsAccumulated: ' + previousRowsAccumulated); 
						mStabilityLevel[level][node].mRow = previousRowsAccumulated + row;
						row++;
					}
					
				}
				
				previousRowsAccumulated += stabilityLevelHeight[level];
			}

			previousRowsAccumulated = 0;
			
			//starting with row below mainline, then moving down
			for( var level = -1; level > mLowestStability - 1; level-- )
			{
				var row = -1;//start at the row below mainline
				for( node in mStabilityLevel[level] )
				{
					if( mStabilityLevel[level][node].ancestorColumn == column ) 
					{
						//console.log('setting ' + mStabilityLevel[level][node].stream.mName + ' to row ' + (previousRowsAccumulated + row)); 
						mStabilityLevel[level][node].mRow = previousRowsAccumulated + row;
						row--;
					}
					
				}
				
				previousRowsAccumulated -= stabilityLevelHeight[level];
			}
		}
	}
	
	function layoutStability(node, stability)
	{
		//console.log('setting stability for ' + node.stream.mName + ' to ' + stability);
		
		if( stability > mHighestStability )
			mHighestStability = stability;
		else if( stability < mLowestStability )
			mLowestStability = stability;
		
		if(!mStabilityLevel[stability])
			mStabilityLevel[stability] = new Array();
			
		mStabilityLevel[stability].push(node);
		
		var children = node.children();
		for( var i = 0; i < children.length; i++ )
		{
			var child = children[i];
			
			if( child.stream.mFirmerThanParent )
				layoutStability(child, stability + 1);
			else
				layoutStability(child, stability - 1);
		}
	}

	function layoutAncestory(node, ancestorColumn)
	{
		//console.log('setting ancestory level for ' + node.stream.mName + ' to ' + ancestorColumn);
		if( ancestorColumn > mHighestAncestor )
			mHighestAncestor = ancestorColumn;
		
		if(!mAncestorColumns[ancestorColumn])
			mAncestorColumns[ancestorColumn] = new Array();
			
		node.ancestorColumn = ancestorColumn;
			
		mAncestorColumns[ancestorColumn].push(node);
		
		var children = node.children();
		for( var i = 0; i < children.length; i++ )
		{
			var child = children[i];
			layoutAncestory(child, ancestorColumn + 1);
		}
	}
}