Skip to content

Commit 9d0bbef

Browse files
mbostockmbostock
committed
Non-recursive tree layout.
1 parent 082c959 commit 9d0bbef

4 files changed

Lines changed: 261 additions & 232 deletions

File tree

‎d3.js‎

Lines changed: 97 additions & 103 deletions
Original file line numberDiff line numberDiff line change
@@ -6715,104 +6715,91 @@
67156715
var hierarchy = d3.layout.hierarchy().sort(null).value(null), separation = d3_layout_treeSeparation, size = [ 1, 1 ], nodeSize = false;
67166716
function tree(d, i) {
67176717
var nodes = hierarchy.call(this, d, i), root0 = nodes[0], root1 = wrapTree(root0);
6718-
firstWalk(root1);
6719-
secondWalk(root1, -root1.z);
6718+
d3_layout_treeVisitAfter(root1, firstWalk), root1.parent.mod = -root1.prelim;
6719+
d3_layout_treeVisitBefore(root1, secondWalk);
67206720
if (nodeSize) {
6721-
d3_layout_treeVisitAfter(root0, function(node) {
6722-
node.x *= size[0];
6723-
node.y = node.depth * size[1];
6721+
d3_layout_treeVisitBefore(root1, function(node) {
6722+
node.node.x *= size[0];
6723+
node.node.y = node.node.depth * size[1];
67246724
});
67256725
} else {
67266726
var left = d3_layout_treeSearch(root0, d3_layout_treeLeftmost), right = d3_layout_treeSearch(root0, d3_layout_treeRightmost), x0 = left.x - separation(left, right) / 2, x1 = right.x + separation(right, left) / 2, y1 = d3_layout_treeSearch(root0, d3_layout_treeDeepest).depth || 1;
6727-
d3_layout_treeVisitAfter(root0, function(node) {
6728-
node.x = (node.x - x0) / (x1 - x0) * size[0];
6729-
node.y = node.depth / y1 * size[1];
6727+
d3_layout_treeVisitBefore(root1, function(node) {
6728+
node.node.x = (node.node.x - x0) / (x1 - x0) * size[0];
6729+
node.node.y = node.node.depth / y1 * size[1];
67306730
});
67316731
}
67326732
return nodes;
67336733
}
67346734
function wrapTree(root0) {
67356735
var root1 = {
6736-
c: [ root0 ]
6736+
defaultAncestor: null,
6737+
children: [ root0 ]
67376738
}, queue = [ root1 ], node1;
67386739
while ((node1 = queue.pop()) != null) {
6739-
for (var children = node1.c, child, i = 0, n = children.length; i < n; ++i) {
6740+
for (var children = node1.children, child, i = 0, n = children.length; i < n; ++i) {
67406741
queue.push((children[i] = child = {
6741-
_: children[i],
6742-
p: node1,
6743-
c: (child = children[i].children) && child.slice() || [],
6744-
a: null,
6745-
z: 0,
6746-
m: 0,
6747-
d: 0,
6748-
s: 0,
6749-
i: i
6750-
}).a = child);
6751-
}
6752-
}
6753-
root1 = root1.c[0];
6754-
root1.p = null;
6755-
return root1;
6756-
}
6757-
function firstWalk(node, previousSibling) {
6758-
var children = node.c;
6759-
if (n = children.length) {
6760-
var n, firstChild = children[0], previousChild, ancestor = firstChild, child, i = -1;
6761-
while (++i < n) {
6762-
child = children[i];
6763-
firstWalk(child, previousChild);
6764-
ancestor = apportion(child, previousChild, ancestor);
6765-
previousChild = child;
6766-
}
6767-
d3_layout_treeShift(node);
6768-
var midpoint = .5 * (firstChild.z + child.z);
6769-
if (previousSibling) {
6770-
node.z = previousSibling.z + separation(node._, previousSibling._);
6771-
node.m = node.z - midpoint;
6742+
node: children[i],
6743+
parent: node1,
6744+
children: (child = children[i].children) && child.slice() || [],
6745+
defaultAncestor: null,
6746+
ancestor: null,
6747+
prelim: 0,
6748+
mod: 0,
6749+
change: 0,
6750+
shift: 0,
6751+
number: i
6752+
}).ancestor = child);
6753+
}
6754+
}
6755+
return root1.children[0];
6756+
}
6757+
function firstWalk(v) {
6758+
var children = v.children, siblings = v.parent.children, w = v.number ? siblings[v.number - 1] : null;
6759+
if (children.length) {
6760+
d3_layout_treeShift(v);
6761+
var midpoint = (children[0].prelim + children[children.length - 1].prelim) / 2;
6762+
if (w) {
6763+
v.prelim = w.prelim + separation(v.node, w.node);
6764+
v.mod = v.prelim - midpoint;
67726765
} else {
6773-
node.z = midpoint;
6766+
v.prelim = midpoint;
67746767
}
6775-
} else if (previousSibling) {
6776-
node.z = previousSibling.z + separation(node._, previousSibling._);
6768+
} else if (w) {
6769+
v.prelim = w.prelim + separation(v.node, w.node);
67776770
}
6771+
v.parent.defaultAncestor = apportion(v, w, v.parent.defaultAncestor || siblings[0]);
67786772
}
6779-
function secondWalk(node, x) {
6780-
node._.x = node.z + x;
6781-
var children = node.c;
6782-
if (n = children.length) {
6783-
var i = -1, n;
6784-
x += node.m;
6785-
while (++i < n) {
6786-
secondWalk(children[i], x);
6787-
}
6788-
}
6773+
function secondWalk(v) {
6774+
v.node.x = v.prelim + v.parent.mod;
6775+
v.mod += v.parent.mod;
67896776
}
6790-
function apportion(node, previousSibling, ancestor) {
6791-
if (previousSibling) {
6792-
var vip = node, vop = node, vim = previousSibling, vom = node.p.c[0], sip = vip.m, sop = vop.m, sim = vim.m, som = vom.m, shift;
6777+
function apportion(v, w, ancestor) {
6778+
if (w) {
6779+
var vip = v, vop = v, vim = w, vom = vip.parent.children[0], sip = vip.mod, sop = vop.mod, sim = vim.mod, som = vom.mod, shift;
67936780
while (vim = d3_layout_treeRight(vim), vip = d3_layout_treeLeft(vip), vim && vip) {
67946781
vom = d3_layout_treeLeft(vom);
67956782
vop = d3_layout_treeRight(vop);
6796-
vop.a = node;
6797-
shift = vim.z + sim - vip.z - sip + separation(vim._, vip._);
6783+
vop.ancestor = v;
6784+
shift = vim.prelim + sim - vip.prelim - sip + separation(vim.node, vip.node);
67986785
if (shift > 0) {
6799-
d3_layout_treeMove(d3_layout_treeAncestor(vim, node, ancestor), node, shift);
6786+
d3_layout_treeMove(d3_layout_treeAncestor(vim, v, ancestor), v, shift);
68006787
sip += shift;
68016788
sop += shift;
68026789
}
6803-
sim += vim.m;
6804-
sip += vip.m;
6805-
som += vom.m;
6806-
sop += vop.m;
6790+
sim += vim.mod;
6791+
sip += vip.mod;
6792+
som += vom.mod;
6793+
sop += vop.mod;
68076794
}
68086795
if (vim && !d3_layout_treeRight(vop)) {
6809-
vop.t = vim;
6810-
vop.m += sim - sop;
6796+
vop.thread = vim;
6797+
vop.mod += sim - sop;
68116798
}
68126799
if (vip && !d3_layout_treeLeft(vom)) {
6813-
vom.t = vip;
6814-
vom.m += sip - som;
6815-
ancestor = node;
6800+
vom.thread = vip;
6801+
vom.mod += sip - som;
6802+
ancestor = v;
68166803
}
68176804
}
68186805
return ancestor;
@@ -6837,14 +6824,6 @@
68376824
function d3_layout_treeSeparation(a, b) {
68386825
return a.parent == b.parent ? 1 : 2;
68396826
}
6840-
function d3_layout_treeLeft(node) {
6841-
var children = node.c;
6842-
return children.length ? children[0] : node.t;
6843-
}
6844-
function d3_layout_treeRight(node) {
6845-
var children = node.c, n;
6846-
return (n = children.length) ? children[n - 1] : node.t;
6847-
}
68486827
function d3_layout_treeSearch(node, compare) {
68496828
var children = node.children;
68506829
if (children && (n = children.length)) {
@@ -6866,35 +6845,50 @@
68666845
function d3_layout_treeDeepest(a, b) {
68676846
return a.depth - b.depth;
68686847
}
6869-
function d3_layout_treeVisitAfter(node, callback) {
6870-
(function visit(node) {
6871-
var children = node.children;
6872-
if (children && (n = children.length)) {
6873-
var i = -1, n;
6874-
while (++i < n) visit(children[i]);
6875-
}
6848+
function d3_layout_treeVisitBefore(node, callback) {
6849+
var nodes = [ node ];
6850+
while ((node = nodes.pop()) != null) {
68766851
callback(node);
6877-
})(node);
6852+
if ((children = node.children) && (n = children.length)) {
6853+
var i = -1, n, children;
6854+
while (++i < n) nodes.push(children[i]);
6855+
}
6856+
}
68786857
}
6879-
function d3_layout_treeShift(node) {
6880-
var shift = 0, change = 0, children = node.c, i = children.length, child;
6858+
function d3_layout_treeVisitAfter(node, callback) {
6859+
var nodes = [];
6860+
d3_layout_treeVisitBefore(node, function(node) {
6861+
nodes.push(node);
6862+
});
6863+
while ((node = nodes.pop()) != null) callback(node);
6864+
}
6865+
function d3_layout_treeLeft(v) {
6866+
var children = v.children;
6867+
return children.length ? children[0] : v.thread;
6868+
}
6869+
function d3_layout_treeRight(v) {
6870+
var children = v.children, n;
6871+
return (n = children.length) ? children[n - 1] : v.thread;
6872+
}
6873+
function d3_layout_treeMove(wm, wp, shift) {
6874+
var change = shift / (wp.number - wm.number);
6875+
wp.change -= change;
6876+
wp.shift += shift;
6877+
wm.change += change;
6878+
wp.prelim += shift;
6879+
wp.mod += shift;
6880+
}
6881+
function d3_layout_treeShift(v) {
6882+
var shift = 0, change = 0, children = v.children, i = children.length, w;
68816883
while (--i >= 0) {
6882-
child = children[i];
6883-
child.z += shift;
6884-
child.m += shift;
6885-
shift += child.s + (change += child.d);
6886-
}
6887-
}
6888-
function d3_layout_treeMove(ancestor, node, shift) {
6889-
var change = shift / (node.i - ancestor.i);
6890-
ancestor.d += change;
6891-
node.d -= change;
6892-
node.s += shift;
6893-
node.z += shift;
6894-
node.m += shift;
6895-
}
6896-
function d3_layout_treeAncestor(vim, node, ancestor) {
6897-
return vim.a.p === node.p ? vim.a : ancestor;
6884+
w = children[i];
6885+
w.prelim += shift;
6886+
w.mod += shift;
6887+
shift += w.shift + (change += w.change);
6888+
}
6889+
}
6890+
function d3_layout_treeAncestor(vim, v, ancestor) {
6891+
return vim.ancestor.parent === v.parent ? vim.ancestor : ancestor;
68986892
}
68996893
d3.layout.pack = function() {
69006894
var hierarchy = d3.layout.hierarchy().sort(d3_layout_packSort), padding = 0, size = [ 1, 1 ], radius;

‎d3.min.js‎

Lines changed: 5 additions & 5 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

0 commit comments

Comments
 (0)