import “layout”;

// Implements hierarchical edge bundling using Holten's algorithm. For each // input link, a path is computed that travels through the tree, up the parent // hierarchy to the least common ancestor, and then back down to the destination // node. Each path is simply an array of nodes. d3.layout.bundle = function() {

return function(links) {
  var paths = [],
      i = -1,
      n = links.length;
  while (++i < n) paths.push(d3_layout_bundlePath(links[i]));
  return paths;
};

};

function d3_layout_bundlePath(link) {

var start = link.source,
    end = link.target,
    lca = d3_layout_bundleLeastCommonAncestor(start, end),
    points = [start];
while (start !== lca) {
  start = start.parent;
  points.push(start);
}
var k = points.length;
while (end !== lca) {
  points.splice(k, 0, end);
  end = end.parent;
}
return points;

}

function d3_layout_bundleAncestors(node) {

var ancestors = [],
    parent = node.parent;
while (parent != null) {
  ancestors.push(node);
  node = parent;
  parent = parent.parent;
}
ancestors.push(node);
return ancestors;

}

function d3_layout_bundleLeastCommonAncestor(a, b) {

if (a === b) return a;
var aNodes = d3_layout_bundleAncestors(a),
    bNodes = d3_layout_bundleAncestors(b),
    aNode = aNodes.pop(),
    bNode = bNodes.pop(),
    sharedNode = null;
while (aNode === bNode) {
  sharedNode = aNode;
  aNode = aNodes.pop();
  bNode = bNodes.pop();
}
return sharedNode;

}