function firstPass(node) {
		// Recursively apply to children
		node.children.forEach(child => firstPass(child));

		// We'll set Y on the second pass, since it's best set as a pre-order
		// traversal.

		// Set X position relative to the parent node. If you're the left-most
		// child, start at zero, otherwise, +1 from previous sibling.
		var siblings = node.getLeftSiblings();
		if (siblings.length !== 0) {
			var prevSibling = siblings[siblings.length - 1];
			node.targetX = prevSibling.targetX + NODE_SPACING;
		} else {
			node.targetX = 0;
		}

		// If we're a parent node, center our children under ourselves
		if (!node.isLeaf()) {
			var firstChild = node.children[0];
			var lastChild = node.children[node.children.length - 1];
			var center = (firstChild.targetX + lastChild.targetX) / 2;
			node.offsetX = node.targetX - center;
		}

		// Check for conflicts with earlier subtrees. Find the right contours of
		// our siblings, and the left contour of ourselves. Confusingly enough,
		// the right contours are physically to the left of the left contour.
		// We iterate in reverse so we consider the closest siblings first.
		var leftContour = findContour(node, Math.min);
		for (var idx = siblings.length - 1; idx >= 0; idx--) {
			// Grab the sibling and its contour
			var sibling = siblings[idx];
			var rightContour = findContour(sibling, Math.max);
			
			// Find the minimum gap (maybe negative) between the contours
			var gap = NODE_SPACING;
			var contourLength = Math.min(rightContour.length, leftContour.length);
			for (var i = 0; i < contourLength; i++) {
				gap = Math.min(gap, leftContour[i] - rightContour[i]);
			}

			// If the gap is big enough, we're done with this sibling
			if (gap >= NODE_SPACING) {
				continue;
			}
			
			// Otherwise, we'll have to move ourselves a total of
			// (NODE_SPACING - gap) away. But we distribute it across all
			// the siblings between us.
			var numGaps = siblings.length - idx;
			var totalShift = (NODE_SPACING - gap);

			// Move our siblings
			for (var i = 1; i < numGaps; i++) {
				siblings[idx + i].targetX += totalShift * i / numGaps;
				siblings[idx + i].offsetX += totalShift * i / numGaps;
			}
			
			// Move ourselves, and also update our contour
			node.targetX += totalShift;
			node.offsetX += totalShift;
			leftContour = leftContour.map(x => x + totalShift);
		}
	}
// X positions for the nodes.
X positions for the nodes.
X positions for the nodes .
function firstPass(node) {
		node.children.forEach(child => firstPass(child));
		var siblings = node.getLeftSiblings();
		if (siblings.length !== 0) {
			var prevSibling = siblings[siblings.length - 1];
			node.targetX = prevSibling.targetX + NODE_SPACING;
		} else {
			node.targetX = 0;
		}
		if (!node.isLeaf()) {
			var firstChild = node.children[0];
			var lastChild = node.children[node.children.length - 1];
			var center = (firstChild.targetX + lastChild.targetX) / 2;
			node.offsetX = node.targetX - center;
		}
		var leftContour = findContour(node, Math.min);
		for (var idx = siblings.length - 1; idx >= 0; idx--) {
			var sibling = siblings[idx];
			var rightContour = findContour(sibling, Math.max);
			var gap = NODE_SPACING;
			var contourLength = Math.min(rightContour.length, leftContour.length);
			for (var i = 0; i < contourLength; i++) {
				gap = Math.min(gap, leftContour[i] - rightContour[i]);
			}
			if (gap >= NODE_SPACING) {
				continue;
			}
			var numGaps = siblings.length - idx;
			var totalShift = (NODE_SPACING - gap);
			for (var i = 1; i < numGaps; i++) {
				siblings[idx + i].targetX += totalShift * i / numGaps;
				siblings[idx + i].offsetX += totalShift * i / numGaps;
			}
			node.targetX += totalShift;
			node.offsetX += totalShift;
			leftContour = leftContour.map(x => x + totalShift);
		}
	}
function firstPass ( node ) { node . children . forEach ( child => firstPass ( child ) ) ; var siblings = node . getLeftSiblings ( ) ; if ( siblings . length !== 0 ) { var prevSibling = siblings [ siblings . length - 1 ] ; node . targetX = prevSibling . targetX + NODE_SPACING ; } else { node . targetX = 0 ; } if ( ! node . isLeaf ( ) ) { var firstChild = node . children [ 0 ] ; var lastChild = node . children [ node . children . length - 1 ] ; var center = ( firstChild . targetX + lastChild . targetX ) / 2 ; node . offsetX = node . targetX - center ; } var leftContour = findContour ( node , Math . min ) ; for ( var idx = siblings . length - 1 ; idx >= 0 ; idx -- ) { var sibling = siblings [ idx ] ; var rightContour = findContour ( sibling , Math . max ) ; var gap = NODE_SPACING ; var contourLength = Math . min ( rightContour . length , leftContour . length ) ; for ( var i = 0 ; i < contourLength ; i ++ ) { gap = Math . min ( gap , leftContour [ i ] - rightContour [ i ] ) ; } if ( gap >= NODE_SPACING ) { continue ; } var numGaps = siblings . length - idx ; var totalShift = ( NODE_SPACING - gap ) ; for ( var i = 1 ; i < numGaps ; i ++ ) { siblings [ idx + i ] . targetX += totalShift * i / numGaps ; siblings [ idx + i ] . offsetX += totalShift * i / numGaps ; } node . targetX += totalShift ; node . offsetX += totalShift ; leftContour = leftContour . map ( x => x + totalShift ) ; } }
X positions for the nodes.
X positions for the nodes .
// Recursively apply to children // We'll set Y on the second pass, since it's best set as a pre-order // traversal. // Set X position relative to the parent node. If you're the left-most // child, start at zero, otherwise, +1 from previous sibling. // If we're a parent node, center our children under ourselves // Check for conflicts with earlier subtrees. Find the right contours of // our siblings, and the left contour of ourselves. Confusingly enough, // the right contours are physically to the left of the left contour. // We iterate in reverse so we consider the closest siblings first. // Grab the sibling and its contour // Find the minimum gap (maybe negative) between the contours // If the gap is big enough, we're done with this sibling // Otherwise, we'll have to move ourselves a total of // (NODE_SPACING - gap) away. But we distribute it across all // the siblings between us. // Move our siblings // Move ourselves, and also update our contour