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;

  }

}