1 d3.layout.pack = function() {

     2   var hierarchy = d3.layout.hierarchy().sort(d3_layout_packSort),

     3       size = [1, 1];

     4 

     5   function pack(d, i) {

     6     var nodes = hierarchy.call(this, d, i),

     7         root = nodes[0];

     8 

     9     // Recursively compute the layout.

    10     root.x = 0;

    11     root.y = 0;

    12     d3_layout_packTree(root);

    13 

    14     // Scale the layout to fit the requested size.

    15     var w = size[0],

    16         h = size[1],

    17         k = 1 / Math.max(2 * root.r / w, 2 * root.r / h);

    18     d3_layout_packTransform(root, w / 2, h / 2, k);

    19 

    20     return nodes;

    21   }

    22 

    23   pack.size = function(x) {

    24     if (!arguments.length) return size;

    25     size = x;

    26     return pack;

    27   };

    28 

    29   return d3_layout_hierarchyRebind(pack, hierarchy);

    30 };

    31 

    32 function d3_layout_packSort(a, b) {

    33   return a.value - b.value;

    34 }

    35 

    36 function d3_layout_packInsert(a, b) {

    37   var c = a._pack_next;

    38   a._pack_next = b;

    39   b._pack_prev = a;

    40   b._pack_next = c;

    41   c._pack_prev = b;

    42 }

    43 

    44 function d3_layout_packSplice(a, b) {

    45   a._pack_next = b;

    46   b._pack_prev = a;

    47 }

    48 

    49 function d3_layout_packIntersects(a, b) {

    50   var dx = b.x - a.x,

    51       dy = b.y - a.y,

    52       dr = a.r + b.r;

    53   return (dr * dr - dx * dx - dy * dy) > .001; // within epsilon

    54 }

    55 

    56 function d3_layout_packCircle(nodes) {

    57   var xMin = Infinity,

    58       xMax = -Infinity,

    59       yMin = Infinity,

    60       yMax = -Infinity,

    61       n = nodes.length,

    62       a, b, c, j, k;

    63 

    64   function bound(node) {

    65     xMin = Math.min(node.x - node.r, xMin);

    66     xMax = Math.max(node.x + node.r, xMax);

    67     yMin = Math.min(node.y - node.r, yMin);

    68     yMax = Math.max(node.y + node.r, yMax);

    69   }

    70 

    71   // Create node links.

    72   nodes.forEach(d3_layout_packLink);

    73 

    74   // Create first node.

    75   a = nodes[0];

    76   a.x = -a.r;

    77   a.y = 0;

    78   bound(a);

    79 

    80   // Create second node.

    81   if (n > 1) {

    82     b = nodes[1];

    83     b.x = b.r;

    84     b.y = 0;

    85     bound(b);

    86 

    87     // Create third node and build chain.

    88     if (n > 2) {

    89       c = nodes[2];

    90       d3_layout_packPlace(a, b, c);

    91       bound(c);

    92       d3_layout_packInsert(a, c);

    93       a._pack_prev = c;

    94       d3_layout_packInsert(c, b);

    95       b = a._pack_next;

    96 

    97       // Now iterate through the rest.

    98       for (var i = 3; i < n; i++) {

    99         d3_layout_packPlace(a, b, c = nodes[i]);

   100 

   101         // Search for the closest intersection.

   102         var isect = 0, s1 = 1, s2 = 1;

   103         for (j = b._pack_next; j !== b; j = j._pack_next, s1++) {

   104           if (d3_layout_packIntersects(j, c)) {

   105             isect = 1;

   106             break;

   107           }

   108         }

   109         if (isect == 1) {

   110           for (k = a._pack_prev; k !== j._pack_prev; k = k._pack_prev, s2++) {

   111             if (d3_layout_packIntersects(k, c)) {

   112               if (s2 < s1) {

   113                 isect = -1;

   114                 j = k;

   115               }

   116               break;

   117             }

   118           }

   119         }

   120 

   121         // Update node chain.

   122         if (isect == 0) {

   123           d3_layout_packInsert(a, c);

   124           b = c;

   125           bound(c);

   126         } else if (isect > 0) {

   127           d3_layout_packSplice(a, j);

   128           b = j;

   129           i--;

   130         } else { // isect < 0

   131           d3_layout_packSplice(j, b);

   132           a = j;

   133           i--;

   134         }

   135       }

   136     }

   137   }

   138 

   139   // Re-center the circles and return the encompassing radius.

   140   var cx = (xMin + xMax) / 2,

   141       cy = (yMin + yMax) / 2,

   142       cr = 0;

   143   for (var i = 0; i < n; i++) {

   144     var node = nodes[i];

   145     node.x -= cx;

   146     node.y -= cy;

   147     cr = Math.max(cr, node.r + Math.sqrt(node.x * node.x + node.y * node.y));

   148   }

   149 

   150   // Remove node links.

   151   nodes.forEach(d3_layout_packUnlink);

   152 

   153   return cr;

   154 }

   155 

   156 function d3_layout_packLink(node) {

   157   node._pack_next = node._pack_prev = node;

   158 }

   159 

   160 function d3_layout_packUnlink(node) {

   161   delete node._pack_next;

   162   delete node._pack_prev;

   163 }

   164 

   165 function d3_layout_packTree(node) {

   166   var children = node.children;

   167   if (children && children.length) {

   168     children.forEach(d3_layout_packTree);

   169     node.r = d3_layout_packCircle(children);

   170   } else {

   171     node.r = Math.sqrt(node.value);

   172   }

   173 }

   174 

   175 function d3_layout_packTransform(node, x, y, k) {

   176   var children = node.children;

   177   node.x = (x += k * node.x);

   178   node.y = (y += k * node.y);

   179   node.r *= k;

   180   if (children) {

   181     var i = -1, n = children.length;

   182     while (++i < n) d3_layout_packTransform(children[i], x, y, k);

   183   }

   184 }

   185 

   186 function d3_layout_packPlace(a, b, c) {

   187   var db = a.r + c.r,

   188       dx = b.x - a.x,

   189       dy = b.y - a.y;

   190   if (db && (dx || dy)) {

   191     var da = b.r + c.r,

   192         dc = Math.sqrt(dx * dx + dy * dy),

   193         cos = Math.max(-1, Math.min(1, (db * db + dc * dc - da * da) / (2 * db * dc))),

   194         theta = Math.acos(cos),

   195         x = cos * (db /= dc),

   196         y = Math.sin(theta) * db;

   197     c.x = a.x + x * dx + y * dy;

   198     c.y = a.y + x * dy - y * dx;

   199   } else {

   200     c.x = a.x + db;

   201     c.y = a.y;

   202   }

   203 }