import “../arrays/max”; import “layout”; import “hierarchy”; import “tree”;

// Implements a hierarchical layout using the cluster (or dendrogram) // algorithm. d3.layout.cluster = function() {

var hierarchy = d3.layout.hierarchy().sort(null).value(null),
    separation = d3_layout_treeSeparation,
    size = [1, 1], // width, height
    nodeSize = false;

function cluster(d, i) {
  var nodes = hierarchy.call(this, d, i),
      root = nodes[0],
      previousNode,
      x = 0;

  // First walk, computing the initial x & y values.
  d3_layout_treeVisitAfter(root, function(node) {
    var children = node.children;
    if (children && children.length) {
      node.x = d3_layout_clusterX(children);
      node.y = d3_layout_clusterY(children);
    } else {
      node.x = previousNode ? x += separation(node, previousNode) : 0;
      node.y = 0;
      previousNode = node;
    }
  });

  // Compute the left-most, right-most, and depth-most nodes for extents.
  var left = d3_layout_clusterLeft(root),
      right = d3_layout_clusterRight(root),
      x0 = left.x - separation(left, right) / 2,
      x1 = right.x + separation(right, left) / 2;

  // Second walk, normalizing x & y to the desired size.
  d3_layout_treeVisitAfter(root, nodeSize ? function(node) {
    node.x = (node.x - root.x) * size[0];
    node.y = (root.y - node.y) * size[1];
  } : function(node) {
    node.x = (node.x - x0) / (x1 - x0) * size[0];
    node.y = (1 - (root.y ? node.y / root.y : 1)) * size[1];
  });

  return nodes;
}

cluster.separation = function(x) {
  if (!arguments.length) return separation;
  separation = x;
  return cluster;
};

cluster.size = function(x) {
  if (!arguments.length) return nodeSize ? null : size;
  nodeSize = (size = x) == null;
  return cluster;
};

cluster.nodeSize = function(x) {
  if (!arguments.length) return nodeSize ? size : null;
  nodeSize = (size = x) != null;
  return cluster;
};

return d3_layout_hierarchyRebind(cluster, hierarchy);

};

function d3_layout_clusterY(children) {

return 1 + d3.max(children, function(child) {
  return child.y;
});

}

function d3_layout_clusterX(children) {

return children.reduce(function(x, child) {
  return x + child.x;
}, 0) / children.length;

}

function d3_layout_clusterLeft(node) {

var children = node.children;
return children && children.length ? d3_layout_clusterLeft(children[0]) : node;

}

function d3_layout_clusterRight(node) {

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

}