--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/toolkit/javascript/d3/src/layout/treemap.js Thu Apr 10 14:20:23 2014 +0200
@@ -0,0 +1,217 @@
+// 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};
+}