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_hierarchyVisitAfter(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_hierarchyVisitAfter(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;

}