import “layout”; import “hierarchy”;

// 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
    nodeSize = false;

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 && (n = children.length)) {
      var i = -1,
          n;
      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, nodeSize ? function(node) {
    node.x *= size[0];
    node.y = node.depth * size[1];
    delete node._tree;
  } : 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 nodeSize ? null : size;
  nodeSize = (size = x) == null;
  return tree;
};

tree.nodeSize = function(x) {
  if (!arguments.length) return nodeSize ? size : null;
  nodeSize = (size = x) != null;
  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) {

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

}

function d3_layout_treeRight(node) {

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

}

function d3_layout_treeSearch(node, compare) {

var children = node.children;
if (children && (n = children.length)) {
  var child,
      n,
      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 && (n = children.length)) {
    var child,
        previousChild = null,
        i = -1,
        n;
    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;

}