MWLayout.js #1

function ModifiedWalkerLayout(streamUtilities)
{
	var mStreamUtilities = streamUtilities;
    var mLayoutDir = mStreamUtilities.Direction.unknown;

    // metadata per node
    function LayoutMetadata(stream)
    {
        this.thread = null;
        this.ancestor = stream;
        this.mod = 0;
        this.prelim = 0;
        this.change = 0;
        this.shift = 0;
    }

	var metaUp = new Array();
	var metaDown = new Array();

    // define some accessor functions to make metadata creation seamless
    function getMD( s, /*Direction*/ dir)
    {
        var md = (dir != mStreamUtilities.Direction.up) ? metaDown : metaUp;
        var ret = md[s];
        
		if (!ret)
        {
            ret = new LayoutMetadata(s);
            md[s] = ret;
        }

        return ret;
    }

    function thread(v)    { return getMD(v, mLayoutDir).thread;   }
    function ancestor(v)  { return getMD(v, mLayoutDir).ancestor; }
    function mod(v)       { return getMD(v, mLayoutDir).mod;      }
    function prelim(v)    { return getMD(v, mLayoutDir).prelim;   }
    function change(v)    { return getMD(v, mLayoutDir).change;   }
    function shift(v)     { return getMD(v, mLayoutDir).shift;    }
    function distance(s)  { return s.width() + 12;               }
    function x(s)         { return s.mX;                        }
    function subtreeIndex(s) { return s.subtreeIndex();          }


	this.treeLayout = function( root)
	{
		//console.log('treeLayout(' + root.mName + ')');
		
		// firstwalk each tree and create separate metadata for the directions (up vs. down)
		mLayoutDir = mStreamUtilities.Direction.down;
		firstWalk( root );
		
		//console.log('after firstWalk down///////////////////////////////////////////');

		mLayoutDir = mStreamUtilities.Direction.up;
		firstWalk( root );

		// the Walker algorithm works on trees with a root, so faking a root requires
		// a little more layout after the first walk
		layoutMainline( root );

		// second walk both directions, sets the final positions of all nodes
		mLayoutDir = mStreamUtilities.Direction.down;
		secondWalk(root, -1 * prelim(root));

		mLayoutDir = mStreamUtilities.Direction.up;
		secondWalk(root, -1 * prelim(root));
	}

	function midpointof(  root,  l,  r, /*Direction*/ dir )
	{
		//console.log( 'midpointof(root:' + root.mName + ' l:' + l.mName + ' r:' + r.mName + ' dir:' + dir + ')');
		
		// l.prelim + (r.prelim + r.w) - root.w
		// ----------------------------------
		//                 2
		var lMD    = getMD(l, dir);
		var rMD    = getMD(r, dir);
		
		var rWidth = 0;
		if( r != null )
			rWidth = r.width();
		
		//console.log( 'midpointof details:  ' + l.mName + ".prelim: " + lMD.prelim +  " " + r.mName + ".prelim: " + rMD.prelim + " r.Width(): " + rWidth + " " + root.mName + ".width()" + root.width());
		
		return (lMD.prelim + rMD.prelim + rWidth - root.width())*0.5;
	}

	function layoutMainline(  root )
	{
		//console.log( 'layoutMainline(root:' + root.mName );
		// maintain the maximum gap between each mainline node, and adjust the prelim
		// of either the upper or lower metadata as we go.  once complete, the gaps
		// for upper and lower should be the same (the prelim coords will not be),
		// so copy the prelims from one to the other and set prelim(root) to the midpoint
		// as mod() stores the data on how much the children of a node should adjust their
		// prelim value, track any changes to prelim in mod

		 var prevT = null;
		
		// as we shift the upper or lower nodes around, track by how much as we go
		var shiftUpper = 0;
		var shiftLower = 0;
	 
		// this root had should be a container, so no direction for children is needed
		//foreach(T* s, root->children(unknown))
		for(var i = 0; i < root.children(mStreamUtilities.Direction.unknown).length; i++)
		{
			var s = root.children(mStreamUtilities.Direction.unknown)[i];
			
			if (prevT == null)
			{
				prevT = s;
				continue;
			}

			// first apply the shifts to this node
			getMD(s, mStreamUtilities.Direction.up).prelim     += shiftUpper;
			getMD(s, mStreamUtilities.Direction.up).mod        += shiftUpper;
			getMD(s, mStreamUtilities.Direction.down).prelim   += shiftLower;
			getMD(s, mStreamUtilities.Direction.down).mod      += shiftLower;

			// calculate the gap difference from upper and lower
			 var gapUpper = getMD(s, mStreamUtilities.Direction.up).prelim - getMD(prevT, mStreamUtilities.Direction.up).prelim;
			 var gapLower = getMD(s, mStreamUtilities.Direction.down).prelim - getMD(prevT, mStreamUtilities.Direction.down).prelim;
			 var diff     = gapLower - gapUpper;

			// if the lower gap is bigger, adjust the upper node's gap
			if (diff > 0)
			{
				getMD(s, mStreamUtilities.Direction.up).prelim += diff;
				getMD(s, mStreamUtilities.Direction.up).mod += diff;
				shiftUpper += diff;
			}           
			else 
			{
				// upper gap is bigger, adjust the lower gap
				getMD(s, mStreamUtilities.Direction.down).prelim -= diff;
				getMD(s, mStreamUtilities.Direction.down).mod -= diff;
				shiftLower -= diff;
			}
		}

		// copy prelim and adjust mod from one to the other
		// the gaps are the same, so we arbitrarily copy from the lower to the upper
		//foreach(T* s, root->children(unknown))
		for(var i = 0; i < root.children(mStreamUtilities.Direction.unknown).length; i++)
		{
			var s = root.children(mStreamUtilities.Direction.unknown)[i];
			
			 var diff = getMD(s, mStreamUtilities.Direction.down).prelim - getMD(s, mStreamUtilities.Direction.up).prelim;
			getMD(s, mStreamUtilities.Direction.up).prelim = getMD(s, mStreamUtilities.Direction.down).prelim;
			getMD(s, mStreamUtilities.Direction.up).mod += diff;
		}

		// recenter the container's "position"
		 var midpoint = midpointof(root, root.leftmostChild(mStreamUtilities.Direction.down), root.rightmostChild(mStreamUtilities.Direction.down), mStreamUtilities.Direction.down);
		getMD(root, mStreamUtilities.Direction.down).prelim = midpoint;
		getMD(root, mStreamUtilities.Direction.up).prelim = midpoint;
	}

	/* FIRSTWALK(v)
		if (v is a leaf)
			let prelim(v) = 0
			if (v has a left sibling w)
				let prelim(v) = prelim(w) + distance
		else
			let defaultAncestor be the leftmost child of v
			for all children w of v from left to right
				FIRSTWALK(w)
				APPORTION(w, defaultAncestor)
			EXECUTESHIFTS(v)
			let midpoint = 0.5*(prelim(leftmost child of v) + prelim(rightmost child of v)
			if (v has a left sibling w)
				let prelim(v) = prelim(w) + distance
				let mod(v) = prelim(v) - midpoint
			else
				let prelim(v) = midpoint
	*/

	function firstWalk( node)
	{
		//console.log('firstWalk(' + node.mName + ')' + ' dir:' + mLayoutDir);

		var children = node.children(mLayoutDir);
		var nodeMD = getMD(node, mLayoutDir);

		if (children.length == 0)	// leaf
		{
			nodeMD.prelim = 0;
			if (node.leftSibling())
				nodeMD.prelim = prelim(node.leftSibling()) + distance(node.leftSibling());
		}
		else
		{
			// firstwalk should operate in both directions (only applies to mainline)
			 var leftmost    = children[0];
			 var rightmost   = children[children.length - 1];
			 var defaultAncestor = leftmost;

			for(var i = 0; i < children.length; i++)
			{
				var child = children[i];
				firstWalk(child);
				defaultAncestor = apportion(child, defaultAncestor);
			}
			// execute shifts should operate on the up and down layer
			executeShifts(node);
			// take the bigger of the midpoints from upper and lower (?)
			 var midPoint = midpointof(node, leftmost, rightmost, mLayoutDir);
			
			//console.log("firstWalk midpoint: " + midPoint + " node: " + node.mName + " leftmost: " + leftmost.mName + " rightmost: " + rightmost.mName);
			
			if (node.leftSibling())
			{
				nodeMD.prelim = prelim(node.leftSibling()) + distance(node.leftSibling());
				nodeMD.mod = prelim(node) - midPoint;
			}
			else
			{
				nodeMD.prelim = midPoint;
			}
		}
	}

	/* APPORTION(v, defaultAncestor)
		if (v has a left sibling w)
			let vi+ = vo+ = v
			let vi- = w
			let vo- be the leftmost sibling of vi+
			let si+ = mod(vi+)
			let so+ = mod(vo+)
			let si- = mod(vi-)
			let so- = mod(vo-)
			while (NEXTRIGHT(vi-) != 0 and NEXTLEFT(vi+) != 0)
				let vi- = NEXTRIGHT(vi-)
				let vi+ = NEXTLEFT(vi+)
				let vo- = NEXTLEFT(vo-)
				let vo+ - NEXTRIGHT(vo+)
				let ancestor(vo+) = v
				let shift = (prelim(vi-) + si-) - (prelim(vi+) + si+) + distance
				if (shift > 0)
					MOVESUBTREE(ANCESTOR(vi-,v,defaultAncestor),v,shift)
					let si+ = si+ + shift
					let so+ = so+ + shift
				let si- = si- + mod(vi-)
				let si+ = si+ + mod(vi+)
				let so- = so- + mod(vo-)
				let so+ - so+ + mod(vo+)
		if (NEXTRIGHT(vi-) != 0 and NEXTRIGHT(vo+) == 0)
			let thread(vo+) = NEXTRIGHT(vi-)
			let mod(vo+) = mod(vo+) + si- - so+
		if (NEXTLEFT(vi+) != 0 and NEXTLEFT(vo-) == 0)
			let thread(vo-) = NEXTLEFT(vi+)
			let mod(vo-) = mod(vo-) + si+ - so-
			let defaultAncestor = v
	*/

	// return the new default ancestor
	function apportion( node,  defaultAncestor)
	{
		//console.log('apportion(' + node.mName + ', ' + defaultAncestor.mName + ')');
		if (node.leftSibling())
		{
			var node_inner_right = node;
			var node_outer_right = node;
			var node_inner_left  = node.leftSibling();
			var node_outer_left  = node_inner_right.leftmostSibling(mLayoutDir);
			var sum_inner_right  = mod(node_inner_right);
			var sum_outer_right  = mod(node_outer_right);
			var sum_inner_left 	 = mod(node_inner_left);
			var sum_outer_left	 = mod(node_outer_left);
			
			
			while (nextRight(node_inner_left) != null && nextLeft(node_inner_right)  != null)
			{
			//console.log('apportion while loop: ' + 'nextRight(node_inner_left): ' + nextRight(node_inner_left) + ' nextLeft(node_inner_right): ' + nextLeft(node_inner_right));
				node_inner_left  = nextRight(node_inner_left);
				node_inner_right = nextLeft(node_inner_right);
				node_outer_left  = nextLeft(node_outer_left);
				node_outer_right = nextRight(node_outer_right);
				getMD(node_outer_right, mLayoutDir).ancestor = node;
				var shift = (prelim(node_inner_left) + sum_inner_left) - (prelim(node_inner_right) + sum_inner_right) + distance(node_inner_left);   // TODO: verify this

				if (shift > 0)
				{
					moveSubTree(ancestor3(node_inner_left, node, defaultAncestor), node, shift);
					sum_inner_right = sum_inner_right + shift;
					sum_outer_right = sum_outer_right + shift;
				}
				
				sum_inner_left  = sum_inner_left + mod(node_inner_left);
				sum_inner_right = sum_inner_right + mod(node_inner_right);
				sum_outer_left = sum_outer_left + mod(node_outer_left);
				sum_outer_right = sum_outer_right + mod(node_outer_right);
			}
			
			if (nextRight(node_inner_left) && nextRight(node_outer_right) == null)
			{
				getMD(node_outer_right, mLayoutDir).thread = nextRight(node_inner_left);
				getMD(node_outer_right, mLayoutDir).mod = mod(node_outer_right) + sum_inner_left - sum_outer_right;
			}
			
			if (nextLeft(node_inner_right) && nextLeft(node_outer_left) == null)
			{
				getMD(node_outer_left, mLayoutDir).thread = nextLeft(node_inner_right);
				getMD(node_outer_left, mLayoutDir).mod = mod(node_outer_left) + sum_inner_right - sum_outer_left;
				defaultAncestor = node;
			}
		}
		
		//console.log('apportion returns ' + defaultAncestor.mName);

		return defaultAncestor;
	}

	/* NEXTLEFT(v)
		if (v has a child)
			return the leftmost child of v
		else
			return thread(v)
	*/

	function nextLeft( node)
	{
		//console.log('nextLeft(' + node.mName + ')');
		
		var ret;

		if (!node.isLeaf(mLayoutDir))
			ret = node.leftmostChild(mLayoutDir);
		else
			ret = thread(node);
			
		/*
		if( ret )	
			//console.log('nextLeft returns ' + ret.mName);
		else
			//console.log('nextLeft returns null');
		*/
		return ret;
	}

	/* NEXTRIGHT(v)
		if (v has a child)
			return the rightmost child of v
		else
			return thread(v)
	*/

	function nextRight( node)
	{
		//console.log('nextRight(' + node.mName + ')');
		
		var ret;
		
		if (!node.isLeaf(mLayoutDir))
			ret = node.rightmostChild(mLayoutDir);
		else
			ret = thread(node);
		/*	
		if( ret )
			//console.log('nextRight returns ' + ret.mName);
		else
			//console.log('nextRight returns null');
		*/
		return ret;
	}

	/* 
		number(x) is the basically the index of x in the child list of its parent

	  MOVESUBTREE(w-,w+,shift)
		let subtrees 	= number(w+) - number(w-)
		let change(w+) 	= change(w+)  - shift/subtrees
		let shift(w+) 	= shift(w+) + shift
		let change(w-) 	= change(w-) + shift/subtrees
		let prelim(w+) 	= prelim(w+) + shift
		let mod(w+) 	= mod(w+) + shift
	*/

	function moveSubTree( left,  right,  inShift)
	{
		//console.log( 'moveSubTree(' + left.mName + ', ' + right.mName + ', ' + inShift);
		var subtrees    = subtreeIndex(right) - subtreeIndex(left); 
		var subtreesShift = inShift/subtrees;
		var rightMD = getMD(right, mLayoutDir);
		rightMD.change   = change(right)- subtreesShift;
		rightMD.shift    = shift(right) + inShift;
		getMD(left, mLayoutDir).change    = change(left) + subtreesShift;
		rightMD.prelim   = prelim(right) + inShift;
		rightMD.mod      = mod(right) + inShift;
	}

	/* EXECUTESHIFTS(v)
		let shift = 0
		let change = 0
		for all children w of v from right to left
			let prelim(w) = prelim(w) + shift
			let mod(w) = mod(w) + shift
			let change = change + change(w)
			let shift = shift + shift(w) + change
	*/

	function executeShifts( node)
	{
		//console.log('executeShifts(' + node.mName + ')');
		 var curShift = 0;
		 var curChange = 0;
		var children = node.children(mLayoutDir);
		
		for (var i = children.length - 1; i >= 0; --i)
		{
			 var child = children[i];
			getMD(child, mLayoutDir).prelim = prelim(child) + curShift;
			getMD(child, mLayoutDir).mod = mod(child) + curShift;
			curChange = curChange + change(child);
			curShift = curShift + shift(child) + curChange;
		}
	}

	/* ANCESTOR(vi-,v,defaultAncestor)
		if (ancestor(vi-) is a sibling of v)
			return ancestor(vi-)
		else
			return defaultAncestor
	*/

	function ancestor3( node_inner_left,  node,  defaultAncestor)
	{
		//console.log('ancestor3(' + node_inner_left.mName + ', ' + node.mName + ', ' + defaultAncestor.mName +')')
		 var ret = ancestor(node_inner_left);
		if (ret.isSibling(node, mLayoutDir))
		{
			//console.log('ancestor3 isSibling is true, returns: ' + ret.mName);
			return ret;
		}
		else
		{
			//console.log('ancestor3 isSibling is false, returns: ' + defaultAncestor.mName);
			return defaultAncestor;
		}
	}

	/* SECONDWALK(v,m)
		let x(v) = prelim(v) + m
		let y(v) be the level of v
		for all children w of v
			SECONDWALK(w, m + mod(v))
	*/

	function secondWalk( node,  offset)
	{
		//console.log('secondWalk: ' + node.mName + " prelim: " + prelim(node) + " offset: " + offset);
		node.mX = prelim(node) + offset;
		// y calc is straight-forward
		var children = node.children(mLayoutDir);

		for(var i = 0; i < children.length; i++)
			secondWalk(children[i], offset + mod(node));
	}

}