// Node-link tree diagram using the Reingold-Tilford "tidy" algorithm

d3.layout.tree = function() {

var hierarchy = d3.layout.hierarchy().sort(null).value(null),

separation = d3_layout_treeSeparation,

size = [1, 1]; // width, height

function tree(d, i) {

var nodes = hierarchy.call(this, d, i),

root = nodes[0];

function firstWalk(node, previousSibling) {

var children = node.children,

layout = node._tree;

if (children && (n = children.length)) {

var n,

firstChild = children[0],

previousChild,

ancestor = firstChild,

child,

i = -1;

while (++i < n) {

child = children[i];

firstWalk(child, previousChild);

ancestor = apportion(child, previousChild, ancestor);

previousChild = child;

}

d3_layout_treeShift(node);

var midpoint = .5 * (firstChild._tree.prelim + child._tree.prelim);

if (previousSibling) {

layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling);

layout.mod = layout.prelim - midpoint;

} else {

layout.prelim = midpoint;

}

} else {

if (previousSibling) {

layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling);

}

}

}

function secondWalk(node, x) {

node.x = node._tree.prelim + x;

var children = node.children;

if (children) {

var i = -1,

n = children.length;

x += node._tree.mod;

while (++i < n) {

secondWalk(children[i], x);

}

}

}

function apportion(node, previousSibling, ancestor) {

if (previousSibling) {

var vip = node,

vop = node,

vim = previousSibling,

vom = node.parent.children[0],

sip = vip._tree.mod,

sop = vop._tree.mod,

sim = vim._tree.mod,

som = vom._tree.mod,

shift;

while (vim = d3_layout_treeRight(vim), vip = d3_layout_treeLeft(vip), vim && vip) {

vom = d3_layout_treeLeft(vom);

vop = d3_layout_treeRight(vop);

vop._tree.ancestor = node;

shift = vim._tree.prelim + sim - vip._tree.prelim - sip + separation(vim, vip);

if (shift > 0) {

d3_layout_treeMove(d3_layout_treeAncestor(vim, node, ancestor), node, shift);

sip += shift;

sop += shift;

}

sim += vim._tree.mod;

sip += vip._tree.mod;

som += vom._tree.mod;

sop += vop._tree.mod;

}

if (vim && !d3_layout_treeRight(vop)) {

vop._tree.thread = vim;

vop._tree.mod += sim - sop;

}

if (vip && !d3_layout_treeLeft(vom)) {

vom._tree.thread = vip;

vom._tree.mod += sip - som;

ancestor = node;

}

}

return ancestor;

}

// Initialize temporary layout variables.

d3_layout_treeVisitAfter(root, function(node, previousSibling) {

node._tree = {

ancestor: node,

prelim: 0,

mod: 0,

change: 0,

shift: 0,

number: previousSibling ? previousSibling._tree.number + 1 : 0

};

});

// Compute the layout using Buchheim et al.'s algorithm.

firstWalk(root);

secondWalk(root, -root._tree.prelim);

// Compute the left-most, right-most, and depth-most nodes for extents.

var left = d3_layout_treeSearch(root, d3_layout_treeLeftmost),

right = d3_layout_treeSearch(root, d3_layout_treeRightmost),

deep = d3_layout_treeSearch(root, d3_layout_treeDeepest),

x0 = left.x - separation(left, right) / 2,

x1 = right.x + separation(right, left) / 2,

y1 = deep.depth || 1;

// Clear temporary layout variables; transform x and y.

d3_layout_treeVisitAfter(root, function(node) {

node.x = (node.x - x0) / (x1 - x0) * size[0];

node.y = node.depth / y1 * size[1];

delete node._tree;

});

return nodes;

}

tree.separation = function(x) {

if (!arguments.length) return separation;

separation = x;

return tree;

};

tree.size = function(x) {

if (!arguments.length) return size;

size = x;

return tree;

};

return d3_layout_hierarchyRebind(tree, hierarchy);

};

function d3_layout_treeSeparation(a, b) {

return a.parent == b.parent ? 1 : 2;

}

// function d3_layout_treeSeparationRadial(a, b) {

// return (a.parent == b.parent ? 1 : 2) / a.depth;

// }

function d3_layout_treeLeft(node) {

return node.children ? node.children[0] : node._tree.thread;

}

function d3_layout_treeRight(node) {

return node.children ? node.children[node.children.length - 1] : node._tree.thread;

}

function d3_layout_treeSearch(node, compare) {

var children = node.children;

if (children) {

var child,

n = children.length,

i = -1;

while (++i < n) {

if (compare(child = d3_layout_treeSearch(children[i], compare), node) > 0) {

node = child;

}

}

}

return node;

}

function d3_layout_treeRightmost(a, b) {

return a.x - b.x;

}

function d3_layout_treeLeftmost(a, b) {

return b.x - a.x;

}

function d3_layout_treeDeepest(a, b) {

return a.depth - b.depth;

}

function d3_layout_treeVisitAfter(node, callback) {

function visit(node, previousSibling) {

var children = node.children;

if (children) {

var child,

previousChild = null,

i = -1,

n = children.length;

while (++i < n) {

child = children[i];

visit(child, previousChild);

previousChild = child;

}

}

callback(node, previousSibling);

}

visit(node, null);

}

function d3_layout_treeShift(node) {

var shift = 0,

change = 0,

children = node.children,

i = children.length,

child;

while (--i >= 0) {

child = children[i]._tree;

child.prelim += shift;

child.mod += shift;

shift += child.shift + (change += child.change);

}

}

function d3_layout_treeMove(ancestor, node, shift) {

ancestor = ancestor._tree;

node = node._tree;

var change = shift / (node.number - ancestor.number);

ancestor.change += change;

node.change -= change;

node.shift += shift;

node.prelim += shift;

node.mod += shift;

}

function d3_layout_treeAncestor(vim, node, ancestor) {

return vim._tree.ancestor.parent == node.parent

? vim._tree.ancestor

: ancestor;

}