summaryrefslogtreecommitdiffstats
path: root/visualize/static/d3.layout.js
diff options
context:
space:
mode:
Diffstat (limited to 'visualize/static/d3.layout.js')
-rw-r--r--visualize/static/d3.layout.js1891
1 files changed, 1891 insertions, 0 deletions
diff --git a/visualize/static/d3.layout.js b/visualize/static/d3.layout.js
new file mode 100644
index 0000000..30ba791
--- /dev/null
+++ b/visualize/static/d3.layout.js
@@ -0,0 +1,1891 @@
+(function(){d3.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;
+}
+d3.layout.chord = function() {
+ var chord = {},
+ chords,
+ groups,
+ matrix,
+ n,
+ padding = 0,
+ sortGroups,
+ sortSubgroups,
+ sortChords;
+
+ function relayout() {
+ var subgroups = {},
+ groupSums = [],
+ groupIndex = d3.range(n),
+ subgroupIndex = [],
+ k,
+ x,
+ x0,
+ i,
+ j;
+
+ chords = [];
+ groups = [];
+
+ // Compute the sum.
+ k = 0, i = -1; while (++i < n) {
+ x = 0, j = -1; while (++j < n) {
+ x += matrix[i][j];
+ }
+ groupSums.push(x);
+ subgroupIndex.push(d3.range(n));
+ k += x;
+ }
+
+ // Sort groups…
+ if (sortGroups) {
+ groupIndex.sort(function(a, b) {
+ return sortGroups(groupSums[a], groupSums[b]);
+ });
+ }
+
+ // Sort subgroups…
+ if (sortSubgroups) {
+ subgroupIndex.forEach(function(d, i) {
+ d.sort(function(a, b) {
+ return sortSubgroups(matrix[i][a], matrix[i][b]);
+ });
+ });
+ }
+
+ // Convert the sum to scaling factor for [0, 2pi].
+ // TODO Allow start and end angle to be specified.
+ // TODO Allow padding to be specified as percentage?
+ k = (2 * Math.PI - padding * n) / k;
+
+ // Compute the start and end angle for each group and subgroup.
+ // Note: Opera has a bug reordering object literal properties!
+ x = 0, i = -1; while (++i < n) {
+ x0 = x, j = -1; while (++j < n) {
+ var di = groupIndex[i],
+ dj = subgroupIndex[di][j],
+ v = matrix[di][dj],
+ a0 = x,
+ a1 = x += v * k;
+ subgroups[di + "-" + dj] = {
+ index: di,
+ subindex: dj,
+ startAngle: a0,
+ endAngle: a1,
+ value: v
+ };
+ }
+ groups.push({
+ index: di,
+ startAngle: x0,
+ endAngle: x,
+ value: (x - x0) / k
+ });
+ x += padding;
+ }
+
+ // Generate chords for each (non-empty) subgroup-subgroup link.
+ i = -1; while (++i < n) {
+ j = i - 1; while (++j < n) {
+ var source = subgroups[i + "-" + j],
+ target = subgroups[j + "-" + i];
+ if (source.value || target.value) {
+ chords.push(source.value < target.value
+ ? {source: target, target: source}
+ : {source: source, target: target});
+ }
+ }
+ }
+
+ if (sortChords) resort();
+ }
+
+ function resort() {
+ chords.sort(function(a, b) {
+ return sortChords(
+ (a.source.value + a.target.value) / 2,
+ (b.source.value + b.target.value) / 2);
+ });
+ }
+
+ chord.matrix = function(x) {
+ if (!arguments.length) return matrix;
+ n = (matrix = x) && matrix.length;
+ chords = groups = null;
+ return chord;
+ };
+
+ chord.padding = function(x) {
+ if (!arguments.length) return padding;
+ padding = x;
+ chords = groups = null;
+ return chord;
+ };
+
+ chord.sortGroups = function(x) {
+ if (!arguments.length) return sortGroups;
+ sortGroups = x;
+ chords = groups = null;
+ return chord;
+ };
+
+ chord.sortSubgroups = function(x) {
+ if (!arguments.length) return sortSubgroups;
+ sortSubgroups = x;
+ chords = null;
+ return chord;
+ };
+
+ chord.sortChords = function(x) {
+ if (!arguments.length) return sortChords;
+ sortChords = x;
+ if (chords) resort();
+ return chord;
+ };
+
+ chord.chords = function() {
+ if (!chords) relayout();
+ return chords;
+ };
+
+ chord.groups = function() {
+ if (!groups) relayout();
+ return groups;
+ };
+
+ return chord;
+};
+// A rudimentary force layout using Gauss-Seidel.
+d3.layout.force = function() {
+ var force = {},
+ event = d3.dispatch("tick"),
+ size = [1, 1],
+ drag,
+ alpha,
+ friction = .9,
+ linkDistance = d3_layout_forceLinkDistance,
+ linkStrength = d3_layout_forceLinkStrength,
+ charge = -30,
+ gravity = .1,
+ theta = .8,
+ interval,
+ nodes = [],
+ links = [],
+ distances,
+ strengths,
+ charges;
+
+ function repulse(node) {
+ return function(quad, x1, y1, x2, y2) {
+ if (quad.point !== node) {
+ var dx = quad.cx - node.x,
+ dy = quad.cy - node.y,
+ dn = 1 / Math.sqrt(dx * dx + dy * dy);
+
+ /* Barnes-Hut criterion. */
+ if ((x2 - x1) * dn < theta) {
+ var k = quad.charge * dn * dn;
+ node.px -= dx * k;
+ node.py -= dy * k;
+ return true;
+ }
+
+ if (quad.point && isFinite(dn)) {
+ var k = quad.pointCharge * dn * dn;
+ node.px -= dx * k;
+ node.py -= dy * k;
+ }
+ }
+ return !quad.charge;
+ };
+ }
+
+ function tick() {
+ var n = nodes.length,
+ m = links.length,
+ q,
+ i, // current index
+ o, // current object
+ s, // current source
+ t, // current target
+ l, // current distance
+ k, // current force
+ x, // x-distance
+ y; // y-distance
+
+ // gauss-seidel relaxation for links
+ for (i = 0; i < m; ++i) {
+ o = links[i];
+ s = o.source;
+ t = o.target;
+ x = t.x - s.x;
+ y = t.y - s.y;
+ if (l = (x * x + y * y)) {
+ l = alpha * strengths[i] * ((l = Math.sqrt(l)) - distances[i]) / l;
+ x *= l;
+ y *= l;
+ t.x -= x * (k = s.weight / (t.weight + s.weight));
+ t.y -= y * k;
+ s.x += x * (k = 1 - k);
+ s.y += y * k;
+ }
+ }
+
+ // apply gravity forces
+ if (k = alpha * gravity) {
+ x = size[0] / 2;
+ y = size[1] / 2;
+ i = -1; if (k) while (++i < n) {
+ o = nodes[i];
+ o.x += (x - o.x) * k;
+ o.y += (y - o.y) * k;
+ }
+ }
+
+ // compute quadtree center of mass and apply charge forces
+ if (charge) {
+ d3_layout_forceAccumulate(q = d3.geom.quadtree(nodes), alpha, charges);
+ i = -1; while (++i < n) {
+ if (!(o = nodes[i]).fixed) {
+ q.visit(repulse(o));
+ }
+ }
+ }
+
+ // position verlet integration
+ i = -1; while (++i < n) {
+ o = nodes[i];
+ if (o.fixed) {
+ o.x = o.px;
+ o.y = o.py;
+ } else {
+ o.x -= (o.px - (o.px = o.x)) * friction;
+ o.y -= (o.py - (o.py = o.y)) * friction;
+ }
+ }
+
+ event.tick({type: "tick", alpha: alpha});
+
+ // simulated annealing, basically
+ return (alpha *= .99) < .005;
+ }
+
+ force.nodes = function(x) {
+ if (!arguments.length) return nodes;
+ nodes = x;
+ return force;
+ };
+
+ force.links = function(x) {
+ if (!arguments.length) return links;
+ links = x;
+ return force;
+ };
+
+ force.size = function(x) {
+ if (!arguments.length) return size;
+ size = x;
+ return force;
+ };
+
+ force.linkDistance = function(x) {
+ if (!arguments.length) return linkDistance;
+ linkDistance = d3.functor(x);
+ return force;
+ };
+
+ // For backwards-compatibility.
+ force.distance = force.linkDistance;
+
+ force.linkStrength = function(x) {
+ if (!arguments.length) return linkStrength;
+ linkStrength = d3.functor(x);
+ return force;
+ };
+
+ force.friction = function(x) {
+ if (!arguments.length) return friction;
+ friction = x;
+ return force;
+ };
+
+ force.charge = function(x) {
+ if (!arguments.length) return charge;
+ charge = typeof x === "function" ? x : +x;
+ return force;
+ };
+
+ force.gravity = function(x) {
+ if (!arguments.length) return gravity;
+ gravity = x;
+ return force;
+ };
+
+ force.theta = function(x) {
+ if (!arguments.length) return theta;
+ theta = x;
+ return force;
+ };
+
+ force.start = function() {
+ var i,
+ j,
+ n = nodes.length,
+ m = links.length,
+ w = size[0],
+ h = size[1],
+ neighbors,
+ o;
+
+ for (i = 0; i < n; ++i) {
+ (o = nodes[i]).index = i;
+ o.weight = 0;
+ }
+
+ distances = [];
+ strengths = [];
+ for (i = 0; i < m; ++i) {
+ o = links[i];
+ if (typeof o.source == "number") o.source = nodes[o.source];
+ if (typeof o.target == "number") o.target = nodes[o.target];
+ distances[i] = linkDistance.call(this, o, i);
+ strengths[i] = linkStrength.call(this, o, i);
+ ++o.source.weight;
+ ++o.target.weight;
+ }
+
+ for (i = 0; i < n; ++i) {
+ o = nodes[i];
+ if (isNaN(o.x)) o.x = position("x", w);
+ if (isNaN(o.y)) o.y = position("y", h);
+ if (isNaN(o.px)) o.px = o.x;
+ if (isNaN(o.py)) o.py = o.y;
+ }
+
+ charges = [];
+ if (typeof charge === "function") {
+ for (i = 0; i < n; ++i) {
+ charges[i] = +charge.call(this, nodes[i], i);
+ }
+ } else {
+ for (i = 0; i < n; ++i) {
+ charges[i] = charge;
+ }
+ }
+
+ // initialize node position based on first neighbor
+ function position(dimension, size) {
+ var neighbors = neighbor(i),
+ j = -1,
+ m = neighbors.length,
+ x;
+ while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x;
+ return Math.random() * size;
+ }
+
+ // initialize neighbors lazily
+ function neighbor() {
+ if (!neighbors) {
+ neighbors = [];
+ for (j = 0; j < n; ++j) {
+ neighbors[j] = [];
+ }
+ for (j = 0; j < m; ++j) {
+ var o = links[j];
+ neighbors[o.source.index].push(o.target);
+ neighbors[o.target.index].push(o.source);
+ }
+ }
+ return neighbors[i];
+ }
+
+ return force.resume();
+ };
+
+ force.resume = function() {
+ alpha = .1;
+ d3.timer(tick);
+ return force;
+ };
+
+ force.stop = function() {
+ alpha = 0;
+ return force;
+ };
+
+ // use `node.call(force.drag)` to make nodes draggable
+ force.drag = function() {
+ if (!drag) drag = d3.behavior.drag()
+ .origin(Object)
+ .on("dragstart", dragstart)
+ .on("drag", d3_layout_forceDrag)
+ .on("dragend", d3_layout_forceDragEnd);
+
+ this.on("mouseover.force", d3_layout_forceDragOver)
+ .on("mouseout.force", d3_layout_forceDragOut)
+ .call(drag);
+ };
+
+ function dragstart(d) {
+ d3_layout_forceDragOver(d3_layout_forceDragNode = d);
+ d3_layout_forceDragForce = force;
+ }
+
+ return d3.rebind(force, event, "on");
+};
+
+var d3_layout_forceDragForce,
+ d3_layout_forceDragNode;
+
+function d3_layout_forceDragOver(d) {
+ d.fixed |= 2;
+}
+
+function d3_layout_forceDragOut(d) {
+ if (d !== d3_layout_forceDragNode) d.fixed &= 1;
+}
+
+function d3_layout_forceDragEnd() {
+ d3_layout_forceDrag();
+ d3_layout_forceDragNode.fixed &= 1;
+ d3_layout_forceDragForce = d3_layout_forceDragNode = null;
+}
+
+function d3_layout_forceDrag() {
+ d3_layout_forceDragNode.px = d3.event.x;
+ d3_layout_forceDragNode.py = d3.event.y;
+ d3_layout_forceDragForce.resume(); // restart annealing
+}
+
+function d3_layout_forceAccumulate(quad, alpha, charges) {
+ var cx = 0,
+ cy = 0;
+ quad.charge = 0;
+ if (!quad.leaf) {
+ var nodes = quad.nodes,
+ n = nodes.length,
+ i = -1,
+ c;
+ while (++i < n) {
+ c = nodes[i];
+ if (c == null) continue;
+ d3_layout_forceAccumulate(c, alpha, charges);
+ quad.charge += c.charge;
+ cx += c.charge * c.cx;
+ cy += c.charge * c.cy;
+ }
+ }
+ if (quad.point) {
+ // jitter internal nodes that are coincident
+ if (!quad.leaf) {
+ quad.point.x += Math.random() - .5;
+ quad.point.y += Math.random() - .5;
+ }
+ var k = alpha * charges[quad.point.index];
+ quad.charge += quad.pointCharge = k;
+ cx += k * quad.point.x;
+ cy += k * quad.point.y;
+ }
+ quad.cx = cx / quad.charge;
+ quad.cy = cy / quad.charge;
+}
+
+function d3_layout_forceLinkDistance(link) {
+ return 20;
+}
+
+function d3_layout_forceLinkStrength(link) {
+ return 1;
+}
+d3.layout.partition = function() {
+ var hierarchy = d3.layout.hierarchy(),
+ size = [1, 1]; // width, height
+
+ function position(node, x, dx, dy) {
+ var children = node.children;
+ node.x = x;
+ node.y = node.depth * dy;
+ node.dx = dx;
+ node.dy = dy;
+ if (children && (n = children.length)) {
+ var i = -1,
+ n,
+ c,
+ d;
+ dx = node.value ? dx / node.value : 0;
+ while (++i < n) {
+ position(c = children[i], x, d = c.value * dx, dy);
+ x += d;
+ }
+ }
+ }
+
+ function depth(node) {
+ var children = node.children,
+ d = 0;
+ if (children && (n = children.length)) {
+ var i = -1,
+ n;
+ while (++i < n) d = Math.max(d, depth(children[i]));
+ }
+ return 1 + d;
+ }
+
+ function partition(d, i) {
+ var nodes = hierarchy.call(this, d, i);
+ position(nodes[0], 0, size[0], size[1] / depth(nodes[0]));
+ return nodes;
+ }
+
+ partition.size = function(x) {
+ if (!arguments.length) return size;
+ size = x;
+ return partition;
+ };
+
+ return d3_layout_hierarchyRebind(partition, hierarchy);
+};
+d3.layout.pie = function() {
+ var value = Number,
+ sort = d3_layout_pieSortByValue,
+ startAngle = 0,
+ endAngle = 2 * Math.PI;
+
+ function pie(data, i) {
+
+ // Compute the numeric values for each data element.
+ var values = data.map(function(d, i) { return +value.call(pie, d, i); });
+
+ // Compute the start angle.
+ var a = +(typeof startAngle === "function"
+ ? startAngle.apply(this, arguments)
+ : startAngle);
+
+ // Compute the angular scale factor: from value to radians.
+ var k = ((typeof endAngle === "function"
+ ? endAngle.apply(this, arguments)
+ : endAngle) - startAngle)
+ / d3.sum(values);
+
+ // Optionally sort the data.
+ var index = d3.range(data.length);
+ if (sort != null) index.sort(sort === d3_layout_pieSortByValue
+ ? function(i, j) { return values[j] - values[i]; }
+ : function(i, j) { return sort(data[i], data[j]); });
+
+ // Compute the arcs!
+ var arcs = index.map(function(i) {
+ return {
+ data: data[i],
+ value: d = values[i],
+ startAngle: a,
+ endAngle: a += d * k
+ };
+ });
+
+ // Return the arcs in the original data's order.
+ return data.map(function(d, i) {
+ return arcs[index[i]];
+ });
+ }
+
+ /**
+ * Specifies the value function *x*, which returns a nonnegative numeric value
+ * for each datum. The default value function is `Number`. The value function
+ * is passed two arguments: the current datum and the current index.
+ */
+ pie.value = function(x) {
+ if (!arguments.length) return value;
+ value = x;
+ return pie;
+ };
+
+ /**
+ * Specifies a sort comparison operator *x*. The comparator is passed two data
+ * elements from the data array, a and b; it returns a negative value if a is
+ * less than b, a positive value if a is greater than b, and zero if a equals
+ * b.
+ */
+ pie.sort = function(x) {
+ if (!arguments.length) return sort;
+ sort = x;
+ return pie;
+ };
+
+ /**
+ * Specifies the overall start angle of the pie chart. Defaults to 0. The
+ * start angle can be specified either as a constant or as a function; in the
+ * case of a function, it is evaluated once per array (as opposed to per
+ * element).
+ */
+ pie.startAngle = function(x) {
+ if (!arguments.length) return startAngle;
+ startAngle = x;
+ return pie;
+ };
+
+ /**
+ * Specifies the overall end angle of the pie chart. Defaults to 2π. The
+ * end angle can be specified either as a constant or as a function; in the
+ * case of a function, it is evaluated once per array (as opposed to per
+ * element).
+ */
+ pie.endAngle = function(x) {
+ if (!arguments.length) return endAngle;
+ endAngle = x;
+ return pie;
+ };
+
+ return pie;
+};
+
+var d3_layout_pieSortByValue = {};
+// data is two-dimensional array of x,y; we populate y0
+d3.layout.stack = function() {
+ var values = Object,
+ order = d3_layout_stackOrders["default"],
+ offset = d3_layout_stackOffsets["zero"],
+ out = d3_layout_stackOut,
+ x = d3_layout_stackX,
+ y = d3_layout_stackY;
+
+ function stack(data, index) {
+
+ // Convert series to canonical two-dimensional representation.
+ var series = data.map(function(d, i) {
+ return values.call(stack, d, i);
+ });
+
+ // Convert each series to canonical [[x,y]] representation.
+ var points = series.map(function(d, i) {
+ return d.map(function(v, i) {
+ return [x.call(stack, v, i), y.call(stack, v, i)];
+ });
+ });
+
+ // Compute the order of series, and permute them.
+ var orders = order.call(stack, points, index);
+ series = d3.permute(series, orders);
+ points = d3.permute(points, orders);
+
+ // Compute the baseline…
+ var offsets = offset.call(stack, points, index);
+
+ // And propagate it to other series.
+ var n = series.length,
+ m = series[0].length,
+ i,
+ j,
+ o;
+ for (j = 0; j < m; ++j) {
+ out.call(stack, series[0][j], o = offsets[j], points[0][j][1]);
+ for (i = 1; i < n; ++i) {
+ out.call(stack, series[i][j], o += points[i - 1][j][1], points[i][j][1]);
+ }
+ }
+
+ return data;
+ }
+
+ stack.values = function(x) {
+ if (!arguments.length) return values;
+ values = x;
+ return stack;
+ };
+
+ stack.order = function(x) {
+ if (!arguments.length) return order;
+ order = typeof x === "function" ? x : d3_layout_stackOrders[x];
+ return stack;
+ };
+
+ stack.offset = function(x) {
+ if (!arguments.length) return offset;
+ offset = typeof x === "function" ? x : d3_layout_stackOffsets[x];
+ return stack;
+ };
+
+ stack.x = function(z) {
+ if (!arguments.length) return x;
+ x = z;
+ return stack;
+ };
+
+ stack.y = function(z) {
+ if (!arguments.length) return y;
+ y = z;
+ return stack;
+ };
+
+ stack.out = function(z) {
+ if (!arguments.length) return out;
+ out = z;
+ return stack;
+ };
+
+ return stack;
+}
+
+function d3_layout_stackX(d) {
+ return d.x;
+}
+
+function d3_layout_stackY(d) {
+ return d.y;
+}
+
+function d3_layout_stackOut(d, y0, y) {
+ d.y0 = y0;
+ d.y = y;
+}
+
+var d3_layout_stackOrders = {
+
+ "inside-out": function(data) {
+ var n = data.length,
+ i,
+ j,
+ max = data.map(d3_layout_stackMaxIndex),
+ sums = data.map(d3_layout_stackReduceSum),
+ index = d3.range(n).sort(function(a, b) { return max[a] - max[b]; }),
+ top = 0,
+ bottom = 0,
+ tops = [],
+ bottoms = [];
+ for (i = 0; i < n; ++i) {
+ j = index[i];
+ if (top < bottom) {
+ top += sums[j];
+ tops.push(j);
+ } else {
+ bottom += sums[j];
+ bottoms.push(j);
+ }
+ }
+ return bottoms.reverse().concat(tops);
+ },
+
+ "reverse": function(data) {
+ return d3.range(data.length).reverse();
+ },
+
+ "default": function(data) {
+ return d3.range(data.length);
+ }
+
+};
+
+var d3_layout_stackOffsets = {
+
+ "silhouette": function(data) {
+ var n = data.length,
+ m = data[0].length,
+ sums = [],
+ max = 0,
+ i,
+ j,
+ o,
+ y0 = [];
+ for (j = 0; j < m; ++j) {
+ for (i = 0, o = 0; i < n; i++) o += data[i][j][1];
+ if (o > max) max = o;
+ sums.push(o);
+ }
+ for (j = 0; j < m; ++j) {
+ y0[j] = (max - sums[j]) / 2;
+ }
+ return y0;
+ },
+
+ "wiggle": function(data) {
+ var n = data.length,
+ x = data[0],
+ m = x.length,
+ max = 0,
+ i,
+ j,
+ k,
+ s1,
+ s2,
+ s3,
+ dx,
+ o,
+ o0,
+ y0 = [];
+ y0[0] = o = o0 = 0;
+ for (j = 1; j < m; ++j) {
+ for (i = 0, s1 = 0; i < n; ++i) s1 += data[i][j][1];
+ for (i = 0, s2 = 0, dx = x[j][0] - x[j - 1][0]; i < n; ++i) {
+ for (k = 0, s3 = (data[i][j][1] - data[i][j - 1][1]) / (2 * dx); k < i; ++k) {
+ s3 += (data[k][j][1] - data[k][j - 1][1]) / dx;
+ }
+ s2 += s3 * data[i][j][1];
+ }
+ y0[j] = o -= s1 ? s2 / s1 * dx : 0;
+ if (o < o0) o0 = o;
+ }
+ for (j = 0; j < m; ++j) y0[j] -= o0;
+ return y0;
+ },
+
+ "expand": function(data) {
+ var n = data.length,
+ m = data[0].length,
+ k = 1 / n,
+ i,
+ j,
+ o,
+ y0 = [];
+ for (j = 0; j < m; ++j) {
+ for (i = 0, o = 0; i < n; i++) o += data[i][j][1];
+ if (o) for (i = 0; i < n; i++) data[i][j][1] /= o;
+ else for (i = 0; i < n; i++) data[i][j][1] = k;
+ }
+ for (j = 0; j < m; ++j) y0[j] = 0;
+ return y0;
+ },
+
+ "zero": function(data) {
+ var j = -1,
+ m = data[0].length,
+ y0 = [];
+ while (++j < m) y0[j] = 0;
+ return y0;
+ }
+
+};
+
+function d3_layout_stackMaxIndex(array) {
+ var i = 1,
+ j = 0,
+ v = array[0][1],
+ k,
+ n = array.length;
+ for (; i < n; ++i) {
+ if ((k = array[i][1]) > v) {
+ j = i;
+ v = k;
+ }
+ }
+ return j;
+}
+
+function d3_layout_stackReduceSum(d) {
+ return d.reduce(d3_layout_stackSum, 0);
+}
+
+function d3_layout_stackSum(p, d) {
+ return p + d[1];
+}
+d3.layout.histogram = function() {
+ var frequency = true,
+ valuer = Number,
+ ranger = d3_layout_histogramRange,
+ binner = d3_layout_histogramBinSturges;
+
+ function histogram(data, i) {
+ var bins = [],
+ values = data.map(valuer, this),
+ range = ranger.call(this, values, i),
+ thresholds = binner.call(this, range, values, i),
+ bin,
+ i = -1,
+ n = values.length,
+ m = thresholds.length - 1,
+ k = frequency ? 1 : 1 / n,
+ x;
+
+ // Initialize the bins.
+ while (++i < m) {
+ bin = bins[i] = [];
+ bin.dx = thresholds[i + 1] - (bin.x = thresholds[i]);
+ bin.y = 0;
+ }
+
+ // Fill the bins, ignoring values outside the range.
+ i = -1; while(++i < n) {
+ x = values[i];
+ if ((x >= range[0]) && (x <= range[1])) {
+ bin = bins[d3.bisect(thresholds, x, 1, m) - 1];
+ bin.y += k;
+ bin.push(data[i]);
+ }
+ }
+
+ return bins;
+ }
+
+ // Specifies how to extract a value from the associated data. The default
+ // value function is `Number`, which is equivalent to the identity function.
+ histogram.value = function(x) {
+ if (!arguments.length) return valuer;
+ valuer = x;
+ return histogram;
+ };
+
+ // Specifies the range of the histogram. Values outside the specified range
+ // will be ignored. The argument `x` may be specified either as a two-element
+ // array representing the minimum and maximum value of the range, or as a
+ // function that returns the range given the array of values and the current
+ // index `i`. The default range is the extent (minimum and maximum) of the
+ // values.
+ histogram.range = function(x) {
+ if (!arguments.length) return ranger;
+ ranger = d3.functor(x);
+ return histogram;
+ };
+
+ // Specifies how to bin values in the histogram. The argument `x` may be
+ // specified as a number, in which case the range of values will be split
+ // uniformly into the given number of bins. Or, `x` may be an array of
+ // threshold values, defining the bins; the specified array must contain the
+ // rightmost (upper) value, thus specifying n + 1 values for n bins. Or, `x`
+ // may be a function which is evaluated, being passed the range, the array of
+ // values, and the current index `i`, returning an array of thresholds. The
+ // default bin function will divide the values into uniform bins using
+ // Sturges' formula.
+ histogram.bins = function(x) {
+ if (!arguments.length) return binner;
+ binner = typeof x === "number"
+ ? function(range) { return d3_layout_histogramBinFixed(range, x); }
+ : d3.functor(x);
+ return histogram;
+ };
+
+ // Specifies whether the histogram's `y` value is a count (frequency) or a
+ // probability (density). The default value is true.
+ histogram.frequency = function(x) {
+ if (!arguments.length) return frequency;
+ frequency = !!x;
+ return histogram;
+ };
+
+ return histogram;
+};
+
+function d3_layout_histogramBinSturges(range, values) {
+ return d3_layout_histogramBinFixed(range, Math.ceil(Math.log(values.length) / Math.LN2 + 1));
+}
+
+function d3_layout_histogramBinFixed(range, n) {
+ var x = -1,
+ b = +range[0],
+ m = (range[1] - b) / n,
+ f = [];
+ while (++x <= n) f[x] = m * x + b;
+ return f;
+}
+
+function d3_layout_histogramRange(values) {
+ return [d3.min(values), d3.max(values)];
+}
+d3.layout.hierarchy = function() {
+ var sort = d3_layout_hierarchySort,
+ children = d3_layout_hierarchyChildren,
+ value = d3_layout_hierarchyValue;
+
+ // Recursively compute the node depth and value.
+ // Also converts the data representation into a standard hierarchy structure.
+ function recurse(data, depth, nodes) {
+ var childs = children.call(hierarchy, data, depth),
+ node = d3_layout_hierarchyInline ? data : {data: data};
+ node.depth = depth;
+ nodes.push(node);
+ if (childs && (n = childs.length)) {
+ var i = -1,
+ n,
+ c = node.children = [],
+ v = 0,
+ j = depth + 1;
+ while (++i < n) {
+ d = recurse(childs[i], j, nodes);
+ d.parent = node;
+ c.push(d);
+ v += d.value;
+ }
+ if (sort) c.sort(sort);
+ if (value) node.value = v;
+ } else if (value) {
+ node.value = +value.call(hierarchy, data, depth) || 0;
+ }
+ return node;
+ }
+
+ // Recursively re-evaluates the node value.
+ function revalue(node, depth) {
+ var children = node.children,
+ v = 0;
+ if (children && (n = children.length)) {
+ var i = -1,
+ n,
+ j = depth + 1;
+ while (++i < n) v += revalue(children[i], j);
+ } else if (value) {
+ v = +value.call(hierarchy, d3_layout_hierarchyInline ? node : node.data, depth) || 0;
+ }
+ if (value) node.value = v;
+ return v;
+ }
+
+ function hierarchy(d) {
+ var nodes = [];
+ recurse(d, 0, nodes);
+ return nodes;
+ }
+
+ hierarchy.sort = function(x) {
+ if (!arguments.length) return sort;
+ sort = x;
+ return hierarchy;
+ };
+
+ hierarchy.children = function(x) {
+ if (!arguments.length) return children;
+ children = x;
+ return hierarchy;
+ };
+
+ hierarchy.value = function(x) {
+ if (!arguments.length) return value;
+ value = x;
+ return hierarchy;
+ };
+
+ // Re-evaluates the `value` property for the specified hierarchy.
+ hierarchy.revalue = function(root) {
+ revalue(root, 0);
+ return root;
+ };
+
+ return hierarchy;
+};
+
+// A method assignment helper for hierarchy subclasses.
+function d3_layout_hierarchyRebind(object, hierarchy) {
+ d3.rebind(object, hierarchy, "sort", "children", "value");
+
+ // Add an alias for links, for convenience.
+ object.links = d3_layout_hierarchyLinks;
+
+ // If the new API is used, enabling inlining.
+ object.nodes = function(d) {
+ d3_layout_hierarchyInline = true;
+ return (object.nodes = object)(d);
+ };
+
+ return object;
+}
+
+function d3_layout_hierarchyChildren(d) {
+ return d.children;
+}
+
+function d3_layout_hierarchyValue(d) {
+ return d.value;
+}
+
+function d3_layout_hierarchySort(a, b) {
+ return b.value - a.value;
+}
+
+// Returns an array source+target objects for the specified nodes.
+function d3_layout_hierarchyLinks(nodes) {
+ return d3.merge(nodes.map(function(parent) {
+ return (parent.children || []).map(function(child) {
+ return {source: parent, target: child};
+ });
+ }));
+}
+
+// For backwards-compatibility, don't enable inlining by default.
+var d3_layout_hierarchyInline = false;
+d3.layout.pack = function() {
+ var hierarchy = d3.layout.hierarchy().sort(d3_layout_packSort),
+ size = [1, 1];
+
+ function pack(d, i) {
+ var nodes = hierarchy.call(this, d, i),
+ root = nodes[0];
+
+ // Recursively compute the layout.
+ root.x = 0;
+ root.y = 0;
+ d3_layout_packTree(root);
+
+ // Scale the layout to fit the requested size.
+ var w = size[0],
+ h = size[1],
+ k = 1 / Math.max(2 * root.r / w, 2 * root.r / h);
+ d3_layout_packTransform(root, w / 2, h / 2, k);
+
+ return nodes;
+ }
+
+ pack.size = function(x) {
+ if (!arguments.length) return size;
+ size = x;
+ return pack;
+ };
+
+ return d3_layout_hierarchyRebind(pack, hierarchy);
+};
+
+function d3_layout_packSort(a, b) {
+ return a.value - b.value;
+}
+
+function d3_layout_packInsert(a, b) {
+ var c = a._pack_next;
+ a._pack_next = b;
+ b._pack_prev = a;
+ b._pack_next = c;
+ c._pack_prev = b;
+}
+
+function d3_layout_packSplice(a, b) {
+ a._pack_next = b;
+ b._pack_prev = a;
+}
+
+function d3_layout_packIntersects(a, b) {
+ var dx = b.x - a.x,
+ dy = b.y - a.y,
+ dr = a.r + b.r;
+ return (dr * dr - dx * dx - dy * dy) > .001; // within epsilon
+}
+
+function d3_layout_packCircle(nodes) {
+ var xMin = Infinity,
+ xMax = -Infinity,
+ yMin = Infinity,
+ yMax = -Infinity,
+ n = nodes.length,
+ a, b, c, j, k;
+
+ function bound(node) {
+ xMin = Math.min(node.x - node.r, xMin);
+ xMax = Math.max(node.x + node.r, xMax);
+ yMin = Math.min(node.y - node.r, yMin);
+ yMax = Math.max(node.y + node.r, yMax);
+ }
+
+ // Create node links.
+ nodes.forEach(d3_layout_packLink);
+
+ // Create first node.
+ a = nodes[0];
+ a.x = -a.r;
+ a.y = 0;
+ bound(a);
+
+ // Create second node.
+ if (n > 1) {
+ b = nodes[1];
+ b.x = b.r;
+ b.y = 0;
+ bound(b);
+
+ // Create third node and build chain.
+ if (n > 2) {
+ c = nodes[2];
+ d3_layout_packPlace(a, b, c);
+ bound(c);
+ d3_layout_packInsert(a, c);
+ a._pack_prev = c;
+ d3_layout_packInsert(c, b);
+ b = a._pack_next;
+
+ // Now iterate through the rest.
+ for (var i = 3; i < n; i++) {
+ d3_layout_packPlace(a, b, c = nodes[i]);
+
+ // Search for the closest intersection.
+ var isect = 0, s1 = 1, s2 = 1;
+ for (j = b._pack_next; j !== b; j = j._pack_next, s1++) {
+ if (d3_layout_packIntersects(j, c)) {
+ isect = 1;
+ break;
+ }
+ }
+ if (isect == 1) {
+ for (k = a._pack_prev; k !== j._pack_prev; k = k._pack_prev, s2++) {
+ if (d3_layout_packIntersects(k, c)) {
+ if (s2 < s1) {
+ isect = -1;
+ j = k;
+ }
+ break;
+ }
+ }
+ }
+
+ // Update node chain.
+ if (isect == 0) {
+ d3_layout_packInsert(a, c);
+ b = c;
+ bound(c);
+ } else if (isect > 0) {
+ d3_layout_packSplice(a, j);
+ b = j;
+ i--;
+ } else { // isect < 0
+ d3_layout_packSplice(j, b);
+ a = j;
+ i--;
+ }
+ }
+ }
+ }
+
+ // Re-center the circles and return the encompassing radius.
+ var cx = (xMin + xMax) / 2,
+ cy = (yMin + yMax) / 2,
+ cr = 0;
+ for (var i = 0; i < n; i++) {
+ var node = nodes[i];
+ node.x -= cx;
+ node.y -= cy;
+ cr = Math.max(cr, node.r + Math.sqrt(node.x * node.x + node.y * node.y));
+ }
+
+ // Remove node links.
+ nodes.forEach(d3_layout_packUnlink);
+
+ return cr;
+}
+
+function d3_layout_packLink(node) {
+ node._pack_next = node._pack_prev = node;
+}
+
+function d3_layout_packUnlink(node) {
+ delete node._pack_next;
+ delete node._pack_prev;
+}
+
+function d3_layout_packTree(node) {
+ var children = node.children;
+ if (children && children.length) {
+ children.forEach(d3_layout_packTree);
+ node.r = d3_layout_packCircle(children);
+ } else {
+ node.r = Math.sqrt(node.value);
+ }
+}
+
+function d3_layout_packTransform(node, x, y, k) {
+ var children = node.children;
+ node.x = (x += k * node.x);
+ node.y = (y += k * node.y);
+ node.r *= k;
+ if (children) {
+ var i = -1, n = children.length;
+ while (++i < n) d3_layout_packTransform(children[i], x, y, k);
+ }
+}
+
+function d3_layout_packPlace(a, b, c) {
+ var db = a.r + c.r,
+ dx = b.x - a.x,
+ dy = b.y - a.y;
+ if (db && (dx || dy)) {
+ var da = b.r + c.r,
+ dc = Math.sqrt(dx * dx + dy * dy),
+ cos = Math.max(-1, Math.min(1, (db * db + dc * dc - da * da) / (2 * db * dc))),
+ theta = Math.acos(cos),
+ x = cos * (db /= dc),
+ y = Math.sin(theta) * db;
+ c.x = a.x + x * dx + y * dy;
+ c.y = a.y + x * dy - y * dx;
+ } else {
+ c.x = a.x + db;
+ c.y = a.y;
+ }
+}
+// Implements a hierarchical layout using the cluster (or dendogram) algorithm.
+d3.layout.cluster = function() {
+ var hierarchy = d3.layout.hierarchy().sort(null).value(null),
+ separation = d3_layout_treeSeparation,
+ size = [1, 1]; // width, height
+
+ function cluster(d, i) {
+ var nodes = hierarchy.call(this, d, i),
+ root = nodes[0],
+ previousNode,
+ x = 0,
+ kx,
+ ky;
+
+ // 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, function(node) {
+ node.x = (node.x - x0) / (x1 - x0) * size[0];
+ node.y = (1 - node.y / root.y) * 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 size;
+ size = x;
+ 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;
+}
+// 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
+
+ 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, 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 size;
+ size = x;
+ 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;
+}
+// Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk
+// Modified to support a target aspect ratio by Jeff Heer
+d3.layout.treemap = function() {
+ var hierarchy = d3.layout.hierarchy(),
+ round = Math.round,
+ size = [1, 1], // width, height
+ padding = null,
+ pad = d3_layout_treemapPadNull,
+ sticky = false,
+ stickies,
+ ratio = 0.5 * (1 + Math.sqrt(5)); // golden ratio
+
+ // Compute the area for each child based on value & scale.
+ function scale(children, k) {
+ var i = -1,
+ n = children.length,
+ child,
+ area;
+ while (++i < n) {
+ area = (child = children[i]).value * (k < 0 ? 0 : k);
+ child.area = isNaN(area) || area <= 0 ? 0 : area;
+ }
+ }
+
+ // Recursively arranges the specified node's children into squarified rows.
+ function squarify(node) {
+ var children = node.children;
+ if (children && children.length) {
+ var rect = pad(node),
+ row = [],
+ remaining = children.slice(), // copy-on-write
+ child,
+ best = Infinity, // the best row score so far
+ score, // the current row score
+ u = Math.min(rect.dx, rect.dy), // initial orientation
+ n;
+ scale(remaining, rect.dx * rect.dy / node.value);
+ row.area = 0;
+ while ((n = remaining.length) > 0) {
+ row.push(child = remaining[n - 1]);
+ row.area += child.area;
+ if ((score = worst(row, u)) <= best) { // continue with this orientation
+ remaining.pop();
+ best = score;
+ } else { // abort, and try a different orientation
+ row.area -= row.pop().area;
+ position(row, u, rect, false);
+ u = Math.min(rect.dx, rect.dy);
+ row.length = row.area = 0;
+ best = Infinity;
+ }
+ }
+ if (row.length) {
+ position(row, u, rect, true);
+ row.length = row.area = 0;
+ }
+ children.forEach(squarify);
+ }
+ }
+
+ // Recursively resizes the specified node's children into existing rows.
+ // Preserves the existing layout!
+ function stickify(node) {
+ var children = node.children;
+ if (children && children.length) {
+ var rect = pad(node),
+ remaining = children.slice(), // copy-on-write
+ child,
+ row = [];
+ scale(remaining, rect.dx * rect.dy / node.value);
+ row.area = 0;
+ while (child = remaining.pop()) {
+ row.push(child);
+ row.area += child.area;
+ if (child.z != null) {
+ position(row, child.z ? rect.dx : rect.dy, rect, !remaining.length);
+ row.length = row.area = 0;
+ }
+ }
+ children.forEach(stickify);
+ }
+ }
+
+ // Computes the score for the specified row, as the worst aspect ratio.
+ function worst(row, u) {
+ var s = row.area,
+ r,
+ rmax = 0,
+ rmin = Infinity,
+ i = -1,
+ n = row.length;
+ while (++i < n) {
+ if (!(r = row[i].area)) continue;
+ if (r < rmin) rmin = r;
+ if (r > rmax) rmax = r;
+ }
+ s *= s;
+ u *= u;
+ return s
+ ? Math.max((u * rmax * ratio) / s, s / (u * rmin * ratio))
+ : Infinity;
+ }
+
+ // Positions the specified row of nodes. Modifies `rect`.
+ function position(row, u, rect, flush) {
+ var i = -1,
+ n = row.length,
+ x = rect.x,
+ y = rect.y,
+ v = u ? round(row.area / u) : 0,
+ o;
+ if (u == rect.dx) { // horizontal subdivision
+ if (flush || v > rect.dy) v = v ? rect.dy : 0; // over+underflow
+ while (++i < n) {
+ o = row[i];
+ o.x = x;
+ o.y = y;
+ o.dy = v;
+ x += o.dx = v ? round(o.area / v) : 0;
+ }
+ o.z = true;
+ o.dx += rect.x + rect.dx - x; // rounding error
+ rect.y += v;
+ rect.dy -= v;
+ } else { // vertical subdivision
+ if (flush || v > rect.dx) v = v ? rect.dx : 0; // over+underflow
+ while (++i < n) {
+ o = row[i];
+ o.x = x;
+ o.y = y;
+ o.dx = v;
+ y += o.dy = v ? round(o.area / v) : 0;
+ }
+ o.z = false;
+ o.dy += rect.y + rect.dy - y; // rounding error
+ rect.x += v;
+ rect.dx -= v;
+ }
+ }
+
+ function treemap(d) {
+ var nodes = stickies || hierarchy(d),
+ root = nodes[0];
+ root.x = 0;
+ root.y = 0;
+ root.dx = size[0];
+ root.dy = size[1];
+ if (stickies) hierarchy.revalue(root);
+ scale([root], root.dx * root.dy / root.value);
+ (stickies ? stickify : squarify)(root);
+ if (sticky) stickies = nodes;
+ return nodes;
+ }
+
+ treemap.size = function(x) {
+ if (!arguments.length) return size;
+ size = x;
+ return treemap;
+ };
+
+ treemap.padding = function(x) {
+ if (!arguments.length) return padding;
+
+ function padFunction(node) {
+ var p = x.call(treemap, node, node.depth);
+ return p == null
+ ? d3_layout_treemapPadNull(node)
+ : d3_layout_treemapPad(node, typeof p === "number" ? [p, p, p, p] : p);
+ }
+
+ function padConstant(node) {
+ return d3_layout_treemapPad(node, x);
+ }
+
+ var type;
+ pad = (padding = x) == null ? d3_layout_treemapPadNull
+ : (type = typeof x) === "function" ? padFunction
+ : type === "number" ? (x = [x, x, x, x], padConstant)
+ : padConstant;
+ return treemap;
+ };
+
+ treemap.round = function(x) {
+ if (!arguments.length) return round != Number;
+ round = x ? Math.round : Number;
+ return treemap;
+ };
+
+ treemap.sticky = function(x) {
+ if (!arguments.length) return sticky;
+ sticky = x;
+ stickies = null;
+ return treemap;
+ };
+
+ treemap.ratio = function(x) {
+ if (!arguments.length) return ratio;
+ ratio = x;
+ return treemap;
+ };
+
+ return d3_layout_hierarchyRebind(treemap, hierarchy);
+};
+
+function d3_layout_treemapPadNull(node) {
+ return {x: node.x, y: node.y, dx: node.dx, dy: node.dy};
+}
+
+function d3_layout_treemapPad(node, padding) {
+ var x = node.x + padding[3],
+ y = node.y + padding[0],
+ dx = node.dx - padding[1] - padding[3],
+ dy = node.dy - padding[0] - padding[2];
+ if (dx < 0) { x += dx / 2; dx = 0; }
+ if (dy < 0) { y += dy / 2; dy = 0; }
+ return {x: x, y: y, dx: dx, dy: dy};
+}
+})();
generated by cgit v1.2.3-24-g4f1b (git 2.32.0) at 2024-04-28 11:56:05 +0200