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

     2 d3.layout.tree = function() {

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

     4       separation = d3_layout_treeSeparation,

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

     6 

     7   function tree(d, i) {

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

     9         root = nodes[0];

    10 

    11     function firstWalk(node, previousSibling) {

    12       var children = node.children,

    13           layout = node._tree;

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

    15         var n,

    16             firstChild = children[0],

    17             previousChild,

    18             ancestor = firstChild,

    19             child,

    20             i = -1;

    21         while (++i < n) {

    22           child = children[i];

    23           firstWalk(child, previousChild);

    24           ancestor = apportion(child, previousChild, ancestor);

    25           previousChild = child;

    26         }

    27         d3_layout_treeShift(node);

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

    29         if (previousSibling) {

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

    31           layout.mod = layout.prelim - midpoint;

    32         } else {

    33           layout.prelim = midpoint;

    34         }

    35       } else {

    36         if (previousSibling) {

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

    38         }

    39       }

    40     }

    41 

    42     function secondWalk(node, x) {

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

    44       var children = node.children;

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

    46         var i = -1,

    47             n;

    48         x += node._tree.mod;

    49         while (++i < n) {

    50           secondWalk(children[i], x);

    51         }

    52       }

    53     }

    54 

    55     function apportion(node, previousSibling, ancestor) {

    56       if (previousSibling) {

    57         var vip = node,

    58             vop = node,

    59             vim = previousSibling,

    60             vom = node.parent.children[0],

    61             sip = vip._tree.mod,

    62             sop = vop._tree.mod,

    63             sim = vim._tree.mod,

    64             som = vom._tree.mod,

    65             shift;

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

    67           vom = d3_layout_treeLeft(vom);

    68           vop = d3_layout_treeRight(vop);

    69           vop._tree.ancestor = node;

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

    71           if (shift > 0) {

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

    73             sip += shift;

    74             sop += shift;

    75           }

    76           sim += vim._tree.mod;

    77           sip += vip._tree.mod;

    78           som += vom._tree.mod;

    79           sop += vop._tree.mod;

    80         }

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

    82           vop._tree.thread = vim;

    83           vop._tree.mod += sim - sop;

    84         }

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

    86           vom._tree.thread = vip;

    87           vom._tree.mod += sip - som;

    88           ancestor = node;

    89         }

    90       }

    91       return ancestor;

    92     }

    93 

    94     // Initialize temporary layout variables.

    95     d3_layout_treeVisitAfter(root, function(node, previousSibling) {

    96       node._tree = {

    97         ancestor: node,

    98         prelim: 0,

    99         mod: 0,

   100         change: 0,

   101         shift: 0,

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

   103       };

   104     });

   105 

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

   107     firstWalk(root);

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

   109 

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

   111     var left = d3_layout_treeSearch(root, d3_layout_treeLeftmost),

   112         right = d3_layout_treeSearch(root, d3_layout_treeRightmost),

   113         deep = d3_layout_treeSearch(root, d3_layout_treeDeepest),

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

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

   116         y1 = deep.depth || 1;

   117 

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

   119     d3_layout_treeVisitAfter(root, function(node) {

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

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

   122       delete node._tree;

   123     });

   124 

   125     return nodes;

   126   }

   127 

   128   tree.separation = function(x) {

   129     if (!arguments.length) return separation;

   130     separation = x;

   131     return tree;

   132   };

   133 

   134   tree.size = function(x) {

   135     if (!arguments.length) return size;

   136     size = x;

   137     return tree;

   138   };

   139 

   140   return d3_layout_hierarchyRebind(tree, hierarchy);

   141 };

   142 

   143 function d3_layout_treeSeparation(a, b) {

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

   145 }

   146 

   147 // function d3_layout_treeSeparationRadial(a, b) {

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

   149 // }

   150 

   151 function d3_layout_treeLeft(node) {

   152   var children = node.children;

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

   154 }

   155 

   156 function d3_layout_treeRight(node) {

   157   var children = node.children,

   158       n;

   159   return children && (n = children.length) ? children[n - 1] : node._tree.thread;

   160 }

   161 

   162 function d3_layout_treeSearch(node, compare) {

   163   var children = node.children;

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

   165     var child,

   166         n,

   167         i = -1;

   168     while (++i < n) {

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

   170         node = child;

   171       }

   172     }

   173   }

   174   return node;

   175 }

   176 

   177 function d3_layout_treeRightmost(a, b) {

   178   return a.x - b.x;

   179 }

   180 

   181 function d3_layout_treeLeftmost(a, b) {

   182   return b.x - a.x;

   183 }

   184 

   185 function d3_layout_treeDeepest(a, b) {

   186   return a.depth - b.depth;

   187 }

   188 

   189 function d3_layout_treeVisitAfter(node, callback) {

   190   function visit(node, previousSibling) {

   191     var children = node.children;

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

   193       var child,

   194           previousChild = null,

   195           i = -1,

   196           n;

   197       while (++i < n) {

   198         child = children[i];

   199         visit(child, previousChild);

   200         previousChild = child;

   201       }

   202     }

   203     callback(node, previousSibling);

   204   }

   205   visit(node, null);

   206 }

   207 

   208 function d3_layout_treeShift(node) {

   209   var shift = 0,

   210       change = 0,

   211       children = node.children,

   212       i = children.length,

   213       child;

   214   while (--i >= 0) {

   215     child = children[i]._tree;

   216     child.prelim += shift;

   217     child.mod += shift;

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

   219   }

   220 }

   221 

   222 function d3_layout_treeMove(ancestor, node, shift) {

   223   ancestor = ancestor._tree;

   224   node = node._tree;

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

   226   ancestor.change += change;

   227   node.change -= change;

   228   node.shift += shift;

   229   node.prelim += shift;

   230   node.mod += shift;

   231 }

   232 

   233 function d3_layout_treeAncestor(vim, node, ancestor) {

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

   235       ? vim._tree.ancestor

   236       : ancestor;

   237 }