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