1 (function(){d3.layout = {};

     2 // Implements hierarchical edge bundling using Holten's algorithm. For each

     3 // input link, a path is computed that travels through the tree, up the parent

     4 // hierarchy to the least common ancestor, and then back down to the destination

     5 // node. Each path is simply an array of nodes.

     6 d3.layout.bundle = function() {

     7   return function(links) {

     8     var paths = [],

     9         i = -1,

    10         n = links.length;

    11     while (++i < n) paths.push(d3_layout_bundlePath(links[i]));

    12     return paths;

    13   };

    14 };

    15 

    16 function d3_layout_bundlePath(link) {

    17   var start = link.source,

    18       end = link.target,

    19       lca = d3_layout_bundleLeastCommonAncestor(start, end),

    20       points = [start];

    21   while (start !== lca) {

    22     start = start.parent;

    23     points.push(start);

    24   }

    25   var k = points.length;

    26   while (end !== lca) {

    27     points.splice(k, 0, end);

    28     end = end.parent;

    29   }

    30   return points;

    31 }

    32 

    33 function d3_layout_bundleAncestors(node) {

    34   var ancestors = [],

    35       parent = node.parent;

    36   while (parent != null) {

    37     ancestors.push(node);

    38     node = parent;

    39     parent = parent.parent;

    40   }

    41   ancestors.push(node);

    42   return ancestors;

    43 }

    44 

    45 function d3_layout_bundleLeastCommonAncestor(a, b) {

    46   if (a === b) return a;

    47   var aNodes = d3_layout_bundleAncestors(a),

    48       bNodes = d3_layout_bundleAncestors(b),

    49       aNode = aNodes.pop(),

    50       bNode = bNodes.pop(),

    51       sharedNode = null;

    52   while (aNode === bNode) {

    53     sharedNode = aNode;

    54     aNode = aNodes.pop();

    55     bNode = bNodes.pop();

    56   }

    57   return sharedNode;

    58 }

    59 d3.layout.chord = function() {

    60   var chord = {},

    61       chords,

    62       groups,

    63       matrix,

    64       n,

    65       padding = 0,

    66       sortGroups,

    67       sortSubgroups,

    68       sortChords;

    69 

    70   function relayout() {

    71     var subgroups = {},

    72         groupSums = [],

    73         groupIndex = d3.range(n),

    74         subgroupIndex = [],

    75         k,

    76         x,

    77         x0,

    78         i,

    79         j;

    80 

    81     chords = [];

    82     groups = [];

    83 

    84     // Compute the sum.

    85     k = 0, i = -1; while (++i < n) {

    86       x = 0, j = -1; while (++j < n) {

    87         x += matrix[i][j];

    88       }

    89       groupSums.push(x);

    90       subgroupIndex.push(d3.range(n));

    91       k += x;

    92     }

    93 

    94     // Sort groups…

    95     if (sortGroups) {

    96       groupIndex.sort(function(a, b) {

    97         return sortGroups(groupSums[a], groupSums[b]);

    98       });

    99     }

   100 

   101     // Sort subgroups…

   102     if (sortSubgroups) {

   103       subgroupIndex.forEach(function(d, i) {

   104         d.sort(function(a, b) {

   105           return sortSubgroups(matrix[i][a], matrix[i][b]);

   106         });

   107       });

   108     }

   109 

   110     // Convert the sum to scaling factor for [0, 2pi].

   111     // TODO Allow start and end angle to be specified.

   112     // TODO Allow padding to be specified as percentage?

   113     k = (2 * Math.PI - padding * n) / k;

   114 

   115     // Compute the start and end angle for each group and subgroup.

   116     // Note: Opera has a bug reordering object literal properties!

   117     x = 0, i = -1; while (++i < n) {

   118       x0 = x, j = -1; while (++j < n) {

   119         var di = groupIndex[i],

   120             dj = subgroupIndex[di][j],

   121             v = matrix[di][dj],

   122             a0 = x,

   123             a1 = x += v * k;

   124         subgroups[di + "-" + dj] = {

   125           index: di,

   126           subindex: dj,

   127           startAngle: a0,

   128           endAngle: a1,

   129           value: v

   130         };

   131       }

   132       groups.push({

   133         index: di,

   134         startAngle: x0,

   135         endAngle: x,

   136         value: (x - x0) / k

   137       });

   138       x += padding;

   139     }

   140 

   141     // Generate chords for each (non-empty) subgroup-subgroup link.

   142     i = -1; while (++i < n) {

   143       j = i - 1; while (++j < n) {

   144         var source = subgroups[i + "-" + j],

   145             target = subgroups[j + "-" + i];

   146         if (source.value || target.value) {

   147           chords.push(source.value < target.value

   148               ? {source: target, target: source}

   149               : {source: source, target: target});

   150         }

   151       }

   152     }

   153 

   154     if (sortChords) resort();

   155   }

   156 

   157   function resort() {

   158     chords.sort(function(a, b) {

   159       return sortChords(

   160           (a.source.value + a.target.value) / 2,

   161           (b.source.value + b.target.value) / 2);

   162     });

   163   }

   164 

   165   chord.matrix = function(x) {

   166     if (!arguments.length) return matrix;

   167     n = (matrix = x) && matrix.length;

   168     chords = groups = null;

   169     return chord;

   170   };

   171 

   172   chord.padding = function(x) {

   173     if (!arguments.length) return padding;

   174     padding = x;

   175     chords = groups = null;

   176     return chord;

   177   };

   178 

   179   chord.sortGroups = function(x) {

   180     if (!arguments.length) return sortGroups;

   181     sortGroups = x;

   182     chords = groups = null;

   183     return chord;

   184   };

   185 

   186   chord.sortSubgroups = function(x) {

   187     if (!arguments.length) return sortSubgroups;

   188     sortSubgroups = x;

   189     chords = null;

   190     return chord;

   191   };

   192 

   193   chord.sortChords = function(x) {

   194     if (!arguments.length) return sortChords;

   195     sortChords = x;

   196     if (chords) resort();

   197     return chord;

   198   };

   199 

   200   chord.chords = function() {

   201     if (!chords) relayout();

   202     return chords;

   203   };

   204 

   205   chord.groups = function() {

   206     if (!groups) relayout();

   207     return groups;

   208   };

   209 

   210   return chord;

   211 };

   212 // A rudimentary force layout using Gauss-Seidel.

   213 d3.layout.force = function() {

   214   var force = {},

   215       event = d3.dispatch("tick"),

   216       size = [1, 1],

   217       drag,

   218       alpha,

   219       friction = .9,

   220       linkDistance = d3_layout_forceLinkDistance,

   221       linkStrength = d3_layout_forceLinkStrength,

   222       charge = -30,

   223       gravity = .1,

   224       theta = .8,

   225       interval,

   226       nodes = [],

   227       links = [],

   228       distances,

   229       strengths,

   230       charges;

   231 

   232   function repulse(node) {

   233     return function(quad, x1, y1, x2, y2) {

   234       if (quad.point !== node) {

   235         var dx = quad.cx - node.x,

   236             dy = quad.cy - node.y,

   237             dn = 1 / Math.sqrt(dx * dx + dy * dy);

   238 

   239         /* Barnes-Hut criterion. */

   240         if ((x2 - x1) * dn < theta) {

   241           var k = quad.charge * dn * dn;

   242           node.px -= dx * k;

   243           node.py -= dy * k;

   244           return true;

   245         }

   246 

   247         if (quad.point && isFinite(dn)) {

   248           var k = quad.pointCharge * dn * dn;

   249           node.px -= dx * k;

   250           node.py -= dy * k;

   251         }

   252       }

   253       return !quad.charge;

   254     };

   255   }

   256 

   257   function tick() {

   258     var n = nodes.length,

   259         m = links.length,

   260         q,

   261         i, // current index

   262         o, // current object

   263         s, // current source

   264         t, // current target

   265         l, // current distance

   266         k, // current force

   267         x, // x-distance

   268         y; // y-distance

   269 

   270     // gauss-seidel relaxation for links

   271     for (i = 0; i < m; ++i) {

   272       o = links[i];

   273       s = o.source;

   274       t = o.target;

   275       x = t.x - s.x;

   276       y = t.y - s.y;

   277       if (l = (x * x + y * y)) {

   278         l = alpha * strengths[i] * ((l = Math.sqrt(l)) - distances[i]) / l;

   279         x *= l;

   280         y *= l;

   281         t.x -= x * (k = s.weight / (t.weight + s.weight));

   282         t.y -= y * k;

   283         s.x += x * (k = 1 - k);

   284         s.y += y * k;

   285       }

   286     }

   287 

   288     // apply gravity forces

   289     if (k = alpha * gravity) {

   290       x = size[0] / 2;

   291       y = size[1] / 2;

   292       i = -1; if (k) while (++i < n) {

   293         o = nodes[i];

   294         o.x += (x - o.x) * k;

   295         o.y += (y - o.y) * k;

   296       }

   297     }

   298 

   299     // compute quadtree center of mass and apply charge forces

   300     if (charge) {

   301       d3_layout_forceAccumulate(q = d3.geom.quadtree(nodes), alpha, charges);

   302       i = -1; while (++i < n) {

   303         if (!(o = nodes[i]).fixed) {

   304           q.visit(repulse(o));

   305         }

   306       }

   307     }

   308 

   309     // position verlet integration

   310     i = -1; while (++i < n) {

   311       o = nodes[i];

   312       if (o.fixed) {

   313         o.x = o.px;

   314         o.y = o.py;

   315       } else {

   316         o.x -= (o.px - (o.px = o.x)) * friction;

   317         o.y -= (o.py - (o.py = o.y)) * friction;

   318       }

   319     }

   320 

   321     event.tick({type: "tick", alpha: alpha});

   322 

   323     // simulated annealing, basically

   324     return (alpha *= .99) < .005;

   325   }

   326 

   327   force.on = function(type, listener) {

   328     event.on(type, listener);

   329     return force;

   330   };

   331 

   332   force.nodes = function(x) {

   333     if (!arguments.length) return nodes;

   334     nodes = x;

   335     return force;

   336   };

   337 

   338   force.links = function(x) {

   339     if (!arguments.length) return links;

   340     links = x;

   341     return force;

   342   };

   343 

   344   force.size = function(x) {

   345     if (!arguments.length) return size;

   346     size = x;

   347     return force;

   348   };

   349 

   350   force.linkDistance = function(x) {

   351     if (!arguments.length) return linkDistance;

   352     linkDistance = d3.functor(x);

   353     return force;

   354   };

   355 

   356   // For backwards-compatibility.

   357   force.distance = force.linkDistance;

   358 

   359   force.linkStrength = function(x) {

   360     if (!arguments.length) return linkStrength;

   361     linkStrength = d3.functor(x);

   362     return force;

   363   };

   364 

   365   force.friction = function(x) {

   366     if (!arguments.length) return friction;

   367     friction = x;

   368     return force;

   369   };

   370 

   371   force.charge = function(x) {

   372     if (!arguments.length) return charge;

   373     charge = typeof x === "function" ? x : +x;

   374     return force;

   375   };

   376 

   377   force.gravity = function(x) {

   378     if (!arguments.length) return gravity;

   379     gravity = x;

   380     return force;

   381   };

   382 

   383   force.theta = function(x) {

   384     if (!arguments.length) return theta;

   385     theta = x;

   386     return force;

   387   };

   388 

   389   force.start = function() {

   390     var i,

   391         j,

   392         n = nodes.length,

   393         m = links.length,

   394         w = size[0],

   395         h = size[1],

   396         neighbors,

   397         o;

   398 

   399     for (i = 0; i < n; ++i) {

   400       (o = nodes[i]).index = i;

   401       o.weight = 0;

   402     }

   403 

   404     distances = [];

   405     strengths = [];

   406     for (i = 0; i < m; ++i) {

   407       o = links[i];

   408       if (typeof o.source == "number") o.source = nodes[o.source];

   409       if (typeof o.target == "number") o.target = nodes[o.target];

   410       distances[i] = linkDistance.call(this, o, i);

   411       strengths[i] = linkStrength.call(this, o, i);

   412       ++o.source.weight;

   413       ++o.target.weight;

   414     }

   415 

   416     for (i = 0; i < n; ++i) {

   417       o = nodes[i];

   418       if (isNaN(o.x)) o.x = position("x", w);

   419       if (isNaN(o.y)) o.y = position("y", h);

   420       if (isNaN(o.px)) o.px = o.x;

   421       if (isNaN(o.py)) o.py = o.y;

   422     }

   423 

   424     charges = [];

   425     if (typeof charge === "function") {

   426       for (i = 0; i < n; ++i) {

   427         charges[i] = +charge.call(this, nodes[i], i);

   428       }

   429     } else {

   430       for (i = 0; i < n; ++i) {

   431         charges[i] = charge;

   432       }

   433     }

   434 

   435     // initialize node position based on first neighbor

   436     function position(dimension, size) {

   437       var neighbors = neighbor(i),

   438           j = -1,

   439           m = neighbors.length,

   440           x;

   441       while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x;

   442       return Math.random() * size;

   443     }

   444 

   445     // initialize neighbors lazily

   446     function neighbor() {

   447       if (!neighbors) {

   448         neighbors = [];

   449         for (j = 0; j < n; ++j) {

   450           neighbors[j] = [];

   451         }

   452         for (j = 0; j < m; ++j) {

   453           var o = links[j];

   454           neighbors[o.source.index].push(o.target);

   455           neighbors[o.target.index].push(o.source);

   456         }

   457       }

   458       return neighbors[i];

   459     }

   460 

   461     return force.resume();

   462   };

   463 

   464   force.resume = function() {

   465     alpha = .1;

   466     d3.timer(tick);

   467     return force;

   468   };

   469 

   470   force.stop = function() {

   471     alpha = 0;

   472     return force;

   473   };

   474 

   475   // use `node.call(force.drag)` to make nodes draggable

   476   force.drag = function() {

   477     if (!drag) drag = d3.behavior.drag()

   478         .on("dragstart", dragstart)

   479         .on("drag", d3_layout_forceDrag)

   480         .on("dragend", d3_layout_forceDragEnd);

   481 

   482     this.on("mouseover.force", d3_layout_forceDragOver)

   483         .on("mouseout.force", d3_layout_forceDragOut)

   484         .call(drag);

   485   };

   486 

   487   function dragstart(d) {

   488     d3_layout_forceDragOver(d3_layout_forceDragNode = d);

   489     d3_layout_forceDragForce = force;

   490   }

   491 

   492   return force;

   493 };

   494 

   495 var d3_layout_forceDragForce,

   496     d3_layout_forceDragNode;

   497 

   498 function d3_layout_forceDragOver(d) {

   499   d.fixed |= 2;

   500 }

   501 

   502 function d3_layout_forceDragOut(d) {

   503   if (d !== d3_layout_forceDragNode) d.fixed &= 1;

   504 }

   505 

   506 function d3_layout_forceDragEnd() {

   507   d3_layout_forceDrag();

   508   d3_layout_forceDragNode.fixed &= 1;

   509   d3_layout_forceDragForce = d3_layout_forceDragNode = null;

   510 }

   511 

   512 function d3_layout_forceDrag() {

   513   d3_layout_forceDragNode.px += d3.event.dx;

   514   d3_layout_forceDragNode.py += d3.event.dy;

   515   d3_layout_forceDragForce.resume(); // restart annealing

   516 }

   517 

   518 function d3_layout_forceAccumulate(quad, alpha, charges) {

   519   var cx = 0,

   520       cy = 0;

   521   quad.charge = 0;

   522   if (!quad.leaf) {

   523     var nodes = quad.nodes,

   524         n = nodes.length,

   525         i = -1,

   526         c;

   527     while (++i < n) {

   528       c = nodes[i];

   529       if (c == null) continue;

   530       d3_layout_forceAccumulate(c, alpha, charges);

   531       quad.charge += c.charge;

   532       cx += c.charge * c.cx;

   533       cy += c.charge * c.cy;

   534     }

   535   }

   536   if (quad.point) {

   537     // jitter internal nodes that are coincident

   538     if (!quad.leaf) {

   539       quad.point.x += Math.random() - .5;

   540       quad.point.y += Math.random() - .5;

   541     }

   542     var k = alpha * charges[quad.point.index];

   543     quad.charge += quad.pointCharge = k;

   544     cx += k * quad.point.x;

   545     cy += k * quad.point.y;

   546   }

   547   quad.cx = cx / quad.charge;

   548   quad.cy = cy / quad.charge;

   549 }

   550 

   551 function d3_layout_forceLinkDistance(link) {

   552   return 20;

   553 }

   554 

   555 function d3_layout_forceLinkStrength(link) {

   556   return 1;

   557 }

   558 d3.layout.partition = function() {

   559   var hierarchy = d3.layout.hierarchy(),

   560       size = [1, 1]; // width, height

   561 

   562   function position(node, x, dx, dy) {

   563     var children = node.children;

   564     node.x = x;

   565     node.y = node.depth * dy;

   566     node.dx = dx;

   567     node.dy = dy;

   568     if (children && (n = children.length)) {

   569       var i = -1,

   570           n,

   571           c,

   572           d;

   573       dx = node.value ? dx / node.value : 0;

   574       while (++i < n) {

   575         position(c = children[i], x, d = c.value * dx, dy);

   576         x += d;

   577       }

   578     }

   579   }

   580 

   581   function depth(node) {

   582     var children = node.children,

   583         d = 0;

   584     if (children && (n = children.length)) {

   585       var i = -1,

   586           n;

   587       while (++i < n) d = Math.max(d, depth(children[i]));

   588     }

   589     return 1 + d;

   590   }

   591 

   592   function partition(d, i) {

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

   594     position(nodes[0], 0, size[0], size[1] / depth(nodes[0]));

   595     return nodes;

   596   }

   597 

   598   partition.size = function(x) {

   599     if (!arguments.length) return size;

   600     size = x;

   601     return partition;

   602   };

   603 

   604   return d3_layout_hierarchyRebind(partition, hierarchy);

   605 };

   606 d3.layout.pie = function() {

   607   var value = Number,

   608       sort = d3_layout_pieSortByValue,

   609       startAngle = 0,

   610       endAngle = 2 * Math.PI;

   611 

   612   function pie(data, i) {

   613 

   614     // Compute the numeric values for each data element.

   615     var values = data.map(function(d, i) { return +value.call(pie, d, i); });

   616 

   617     // Compute the start angle.

   618     var a = +(typeof startAngle === "function"

   619         ? startAngle.apply(this, arguments)

   620         : startAngle);

   621 

   622     // Compute the angular scale factor: from value to radians.

   623     var k = ((typeof endAngle === "function"

   624         ? endAngle.apply(this, arguments)

   625         : endAngle) - startAngle)

   626         / d3.sum(values);

   627 

   628     // Optionally sort the data.

   629     var index = d3.range(data.length);

   630     if (sort != null) index.sort(sort === d3_layout_pieSortByValue

   631         ? function(i, j) { return values[j] - values[i]; }

   632         : function(i, j) { return sort(data[i], data[j]); });

   633 

   634     // Compute the arcs!

   635     var arcs = index.map(function(i) {

   636       return {

   637         data: data[i],

   638         value: d = values[i],

   639         startAngle: a,

   640         endAngle: a += d * k

   641       };

   642     });

   643 

   644     // Return the arcs in the original data's order.

   645     return data.map(function(d, i) {

   646       return arcs[index[i]];

   647     });

   648   }

   649 

   650   /**

   651    * Specifies the value function *x*, which returns a nonnegative numeric value

   652    * for each datum. The default value function is `Number`. The value function

   653    * is passed two arguments: the current datum and the current index.

   654    */

   655   pie.value = function(x) {

   656     if (!arguments.length) return value;

   657     value = x;

   658     return pie;

   659   };

   660 

   661   /**

   662    * Specifies a sort comparison operator *x*. The comparator is passed two data

   663    * elements from the data array, a and b; it returns a negative value if a is

   664    * less than b, a positive value if a is greater than b, and zero if a equals

   665    * b.

   666    */

   667   pie.sort = function(x) {

   668     if (!arguments.length) return sort;

   669     sort = x;

   670     return pie;

   671   };

   672 

   673   /**

   674    * Specifies the overall start angle of the pie chart. Defaults to 0. The

   675    * start angle can be specified either as a constant or as a function; in the

   676    * case of a function, it is evaluated once per array (as opposed to per

   677    * element).

   678    */

   679   pie.startAngle = function(x) {

   680     if (!arguments.length) return startAngle;

   681     startAngle = x;

   682     return pie;

   683   };

   684 

   685   /**

   686    * Specifies the overall end angle of the pie chart. Defaults to 2π. The

   687    * end angle can be specified either as a constant or as a function; in the

   688    * case of a function, it is evaluated once per array (as opposed to per

   689    * element).

   690    */

   691   pie.endAngle = function(x) {

   692     if (!arguments.length) return endAngle;

   693     endAngle = x;

   694     return pie;

   695   };

   696 

   697   return pie;

   698 };

   699 

   700 var d3_layout_pieSortByValue = {};

   701 // data is two-dimensional array of x,y; we populate y0

   702 d3.layout.stack = function() {

   703   var values = Object,

   704       order = d3_layout_stackOrders["default"],

   705       offset = d3_layout_stackOffsets["zero"],

   706       out = d3_layout_stackOut,

   707       x = d3_layout_stackX,

   708       y = d3_layout_stackY;

   709 

   710   function stack(data, index) {

   711 

   712     // Convert series to canonical two-dimensional representation.

   713     var series = data.map(function(d, i) {

   714       return values.call(stack, d, i);

   715     });

   716 

   717     // Convert each series to canonical [[x,y]] representation.

   718     var points = series.map(function(d, i) {

   719       return d.map(function(v, i) {

   720         return [x.call(stack, v, i), y.call(stack, v, i)];

   721       });

   722     });

   723 

   724     // Compute the order of series, and permute them.

   725     var orders = order.call(stack, points, index);

   726     series = d3.permute(series, orders);

   727     points = d3.permute(points, orders);

   728 

   729     // Compute the baseline…

   730     var offsets = offset.call(stack, points, index);

   731 

   732     // And propagate it to other series.

   733     var n = series.length,

   734         m = series[0].length,

   735         i,

   736         j,

   737         o;

   738     for (j = 0; j < m; ++j) {

   739       out.call(stack, series[0][j], o = offsets[j], points[0][j][1]);

   740       for (i = 1; i < n; ++i) {

   741         out.call(stack, series[i][j], o += points[i - 1][j][1], points[i][j][1]);

   742       }

   743     }

   744 

   745     return data;

   746   }

   747 

   748   stack.values = function(x) {

   749     if (!arguments.length) return values;

   750     values = x;

   751     return stack;

   752   };

   753 

   754   stack.order = function(x) {

   755     if (!arguments.length) return order;

   756     order = typeof x === "function" ? x : d3_layout_stackOrders[x];

   757     return stack;

   758   };

   759 

   760   stack.offset = function(x) {

   761     if (!arguments.length) return offset;

   762     offset = typeof x === "function" ? x : d3_layout_stackOffsets[x];

   763     return stack;

   764   };

   765 

   766   stack.x = function(z) {

   767     if (!arguments.length) return x;

   768     x = z;

   769     return stack;

   770   };

   771 

   772   stack.y = function(z) {

   773     if (!arguments.length) return y;

   774     y = z;

   775     return stack;

   776   };

   777 

   778   stack.out = function(z) {

   779     if (!arguments.length) return out;

   780     out = z;

   781     return stack;

   782   };

   783 

   784   return stack;

   785 }

   786 

   787 function d3_layout_stackX(d) {

   788   return d.x;

   789 }

   790 

   791 function d3_layout_stackY(d) {

   792   return d.y;

   793 }

   794 

   795 function d3_layout_stackOut(d, y0, y) {

   796   d.y0 = y0;

   797   d.y = y;

   798 }

   799 

   800 var d3_layout_stackOrders = {

   801 

   802   "inside-out": function(data) {

   803     var n = data.length,

   804         i,

   805         j,

   806         max = data.map(d3_layout_stackMaxIndex),

   807         sums = data.map(d3_layout_stackReduceSum),

   808         index = d3.range(n).sort(function(a, b) { return max[a] - max[b]; }),

   809         top = 0,

   810         bottom = 0,

   811         tops = [],

   812         bottoms = [];

   813     for (i = 0; i < n; ++i) {

   814       j = index[i];

   815       if (top < bottom) {

   816         top += sums[j];

   817         tops.push(j);

   818       } else {

   819         bottom += sums[j];

   820         bottoms.push(j);

   821       }

   822     }

   823     return bottoms.reverse().concat(tops);

   824   },

   825 

   826   "reverse": function(data) {

   827     return d3.range(data.length).reverse();

   828   },

   829 

   830   "default": function(data) {

   831     return d3.range(data.length);

   832   }

   833 

   834 };

   835 

   836 var d3_layout_stackOffsets = {

   837 

   838   "silhouette": function(data) {

   839     var n = data.length,

   840         m = data[0].length,

   841         sums = [],

   842         max = 0,

   843         i,

   844         j,

   845         o,

   846         y0 = [];

   847     for (j = 0; j < m; ++j) {

   848       for (i = 0, o = 0; i < n; i++) o += data[i][j][1];

   849       if (o > max) max = o;

   850       sums.push(o);

   851     }

   852     for (j = 0; j < m; ++j) {

   853       y0[j] = (max - sums[j]) / 2;

   854     }

   855     return y0;

   856   },

   857 

   858   "wiggle": function(data) {

   859     var n = data.length,

   860         x = data[0],

   861         m = x.length,

   862         max = 0,

   863         i,

   864         j,

   865         k,

   866         s1,

   867         s2,

   868         s3,

   869         dx,

   870         o,

   871         o0,

   872         y0 = [];

   873     y0[0] = o = o0 = 0;

   874     for (j = 1; j < m; ++j) {

   875       for (i = 0, s1 = 0; i < n; ++i) s1 += data[i][j][1];

   876       for (i = 0, s2 = 0, dx = x[j][0] - x[j - 1][0]; i < n; ++i) {

   877         for (k = 0, s3 = (data[i][j][1] - data[i][j - 1][1]) / (2 * dx); k < i; ++k) {

   878           s3 += (data[k][j][1] - data[k][j - 1][1]) / dx;

   879         }

   880         s2 += s3 * data[i][j][1];

   881       }

   882       y0[j] = o -= s1 ? s2 / s1 * dx : 0;

   883       if (o < o0) o0 = o;

   884     }

   885     for (j = 0; j < m; ++j) y0[j] -= o0;

   886     return y0;

   887   },

   888 

   889   "expand": function(data) {

   890     var n = data.length,

   891         m = data[0].length,

   892         k = 1 / n,

   893         i,

   894         j,

   895         o,

   896         y0 = [];

   897     for (j = 0; j < m; ++j) {

   898       for (i = 0, o = 0; i < n; i++) o += data[i][j][1];

   899       if (o) for (i = 0; i < n; i++) data[i][j][1] /= o;

   900       else for (i = 0; i < n; i++) data[i][j][1] = k;

   901     }

   902     for (j = 0; j < m; ++j) y0[j] = 0;

   903     return y0;

   904   },

   905 

   906   "zero": function(data) {

   907     var j = -1,

   908         m = data[0].length,

   909         y0 = [];

   910     while (++j < m) y0[j] = 0;

   911     return y0;

   912   }

   913 

   914 };

   915 

   916 function d3_layout_stackMaxIndex(array) {

   917   var i = 1,

   918       j = 0,

   919       v = array[0][1],

   920       k,

   921       n = array.length;

   922   for (; i < n; ++i) {

   923     if ((k = array[i][1]) > v) {

   924       j = i;

   925       v = k;

   926     }

   927   }

   928   return j;

   929 }

   930 

   931 function d3_layout_stackReduceSum(d) {

   932   return d.reduce(d3_layout_stackSum, 0);

   933 }

   934 

   935 function d3_layout_stackSum(p, d) {

   936   return p + d[1];

   937 }

   938 d3.layout.histogram = function() {

   939   var frequency = true,

   940       valuer = Number,

   941       ranger = d3_layout_histogramRange,

   942       binner = d3_layout_histogramBinSturges;

   943 

   944   function histogram(data, i) {

   945     var bins = [],

   946         values = data.map(valuer, this),

   947         range = ranger.call(this, values, i),

   948         thresholds = binner.call(this, range, values, i),

   949         bin,

   950         i = -1,

   951         n = values.length,

   952         m = thresholds.length - 1,

   953         k = frequency ? 1 : 1 / n,

   954         x;

   955 

   956     // Initialize the bins.

   957     while (++i < m) {

   958       bin = bins[i] = [];

   959       bin.dx = thresholds[i + 1] - (bin.x = thresholds[i]);

   960       bin.y = 0;

   961     }

   962 

   963     // Fill the bins, ignoring values outside the range.

   964     i = -1; while(++i < n) {

   965       x = values[i];

   966       if ((x >= range[0]) && (x <= range[1])) {

   967         bin = bins[d3.bisect(thresholds, x, 1, m) - 1];

   968         bin.y += k;

   969         bin.push(data[i]);

   970       }

   971     }

   972 

   973     return bins;

   974   }

   975 

   976   // Specifies how to extract a value from the associated data. The default

   977   // value function is `Number`, which is equivalent to the identity function.

   978   histogram.value = function(x) {

   979     if (!arguments.length) return valuer;

   980     valuer = x;

   981     return histogram;

   982   };

   983 

   984   // Specifies the range of the histogram. Values outside the specified range

   985   // will be ignored. The argument `x` may be specified either as a two-element

   986   // array representing the minimum and maximum value of the range, or as a

   987   // function that returns the range given the array of values and the current

   988   // index `i`. The default range is the extent (minimum and maximum) of the

   989   // values.

   990   histogram.range = function(x) {

   991     if (!arguments.length) return ranger;

   992     ranger = d3.functor(x);

   993     return histogram;

   994   };

   995 

   996   // Specifies how to bin values in the histogram. The argument `x` may be

   997   // specified as a number, in which case the range of values will be split

   998   // uniformly into the given number of bins. Or, `x` may be an array of

   999   // threshold values, defining the bins; the specified array must contain the

  1000   // rightmost (upper) value, thus specifying n + 1 values for n bins. Or, `x`

  1001   // may be a function which is evaluated, being passed the range, the array of

  1002   // values, and the current index `i`, returning an array of thresholds. The

  1003   // default bin function will divide the values into uniform bins using

  1004   // Sturges' formula.

  1005   histogram.bins = function(x) {

  1006     if (!arguments.length) return binner;

  1007     binner = typeof x === "number"

  1008         ? function(range) { return d3_layout_histogramBinFixed(range, x); }

  1009         : d3.functor(x);

  1010     return histogram;

  1011   };

  1012 

  1013   // Specifies whether the histogram's `y` value is a count (frequency) or a

  1014   // probability (density). The default value is true.

  1015   histogram.frequency = function(x) {

  1016     if (!arguments.length) return frequency;

  1017     frequency = !!x;

  1018     return histogram;

  1019   };

  1020 

  1021   return histogram;

  1022 };

  1023 

  1024 function d3_layout_histogramBinSturges(range, values) {

  1025   return d3_layout_histogramBinFixed(range, Math.ceil(Math.log(values.length) / Math.LN2 + 1));

  1026 }

  1027 

  1028 function d3_layout_histogramBinFixed(range, n) {

  1029   var x = -1,

  1030       b = +range[0],

  1031       m = (range[1] - b) / n,

  1032       f = [];

  1033   while (++x <= n) f[x] = m * x + b;

  1034   return f;

  1035 }

  1036 

  1037 function d3_layout_histogramRange(values) {

  1038   return [d3.min(values), d3.max(values)];

  1039 }

  1040 d3.layout.hierarchy = function() {

  1041   var sort = d3_layout_hierarchySort,

  1042       children = d3_layout_hierarchyChildren,

  1043       value = d3_layout_hierarchyValue;

  1044 

  1045   // Recursively compute the node depth and value.

  1046   // Also converts the data representation into a standard hierarchy structure.

  1047   function recurse(data, depth, nodes) {

  1048     var childs = children.call(hierarchy, data, depth),

  1049         node = d3_layout_hierarchyInline ? data : {data: data};

  1050     node.depth = depth;

  1051     nodes.push(node);

  1052     if (childs && (n = childs.length)) {

  1053       var i = -1,

  1054           n,

  1055           c = node.children = [],

  1056           v = 0,

  1057           j = depth + 1;

  1058       while (++i < n) {

  1059         d = recurse(childs[i], j, nodes);

  1060         d.parent = node;

  1061         c.push(d);

  1062         v += d.value;

  1063       }

  1064       if (sort) c.sort(sort);

  1065       if (value) node.value = v;

  1066     } else if (value) {

  1067       node.value = +value.call(hierarchy, data, depth) || 0;

  1068     }

  1069     return node;

  1070   }

  1071 

  1072   // Recursively re-evaluates the node value.

  1073   function revalue(node, depth) {

  1074     var children = node.children,

  1075         v = 0;

  1076     if (children && (n = children.length)) {

  1077       var i = -1,

  1078           n,

  1079           j = depth + 1;

  1080       while (++i < n) v += revalue(children[i], j);

  1081     } else if (value) {

  1082       v = +value.call(hierarchy, d3_layout_hierarchyInline ? node : node.data, depth) || 0;

  1083     }

  1084     if (value) node.value = v;

  1085     return v;

  1086   }

  1087 

  1088   function hierarchy(d) {

  1089     var nodes = [];

  1090     recurse(d, 0, nodes);

  1091     return nodes;

  1092   }

  1093 

  1094   hierarchy.sort = function(x) {

  1095     if (!arguments.length) return sort;

  1096     sort = x;

  1097     return hierarchy;

  1098   };

  1099 

  1100   hierarchy.children = function(x) {

  1101     if (!arguments.length) return children;

  1102     children = x;

  1103     return hierarchy;

  1104   };

  1105 

  1106   hierarchy.value = function(x) {

  1107     if (!arguments.length) return value;

  1108     value = x;

  1109     return hierarchy;

  1110   };

  1111 

  1112   // Re-evaluates the `value` property for the specified hierarchy.

  1113   hierarchy.revalue = function(root) {

  1114     revalue(root, 0);

  1115     return root;

  1116   };

  1117 

  1118   return hierarchy;

  1119 };

  1120 

  1121 // A method assignment helper for hierarchy subclasses.

  1122 function d3_layout_hierarchyRebind(object, hierarchy) {

  1123   object.sort = d3.rebind(object, hierarchy.sort);

  1124   object.children = d3.rebind(object, hierarchy.children);

  1125   object.links = d3_layout_hierarchyLinks;

  1126   object.value = d3.rebind(object, hierarchy.value);

  1127 

  1128   // If the new API is used, enabling inlining.

  1129   object.nodes = function(d) {

  1130     d3_layout_hierarchyInline = true;

  1131     return (object.nodes = object)(d);

  1132   };

  1133 

  1134   return object;

  1135 }

  1136