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 	if ((alpha *= .99) < .005) {

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

   323 		return true;

   324 	}

   325 	else {

   326 	    return false;

   327 	} 

   328 

   329     /*event.tick({type: "tick", alpha: alpha});

   330 

   331     // simulated annealing, basically

   332     return (alpha *= .99) < .005;*/

   333   }

   334 

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

   336     event.on(type, listener);

   337     return force;

   338   };

   339 

   340   force.nodes = function(x) {

   341     if (!arguments.length) return nodes;

   342     nodes = x;

   343     return force;

   344   };

   345 

   346   force.links = function(x) {

   347     if (!arguments.length) return links;

   348     links = x;

   349     return force;

   350   };

   351 

   352   force.size = function(x) {

   353     if (!arguments.length) return size;

   354     size = x;

   355     return force;

   356   };

   357 

   358   force.linkDistance = function(x) {

   359     if (!arguments.length) return linkDistance;

   360     linkDistance = d3.functor(x);

   361     return force;

   362   };

   363 

   364   // For backwards-compatibility.

   365   force.distance = force.linkDistance;

   366 

   367   force.linkStrength = function(x) {

   368     if (!arguments.length) return linkStrength;

   369     linkStrength = d3.functor(x);

   370     return force;

   371   };

   372 

   373   force.friction = function(x) {

   374     if (!arguments.length) return friction;

   375     friction = x;

   376     return force;

   377   };

   378 

   379   force.charge = function(x) {

   380     if (!arguments.length) return charge;

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

   382     return force;

   383   };

   384 

   385   force.gravity = function(x) {

   386     if (!arguments.length) return gravity;

   387     gravity = x;

   388     return force;

   389   };

   390 

   391   force.theta = function(x) {

   392     if (!arguments.length) return theta;

   393     theta = x;

   394     return force;

   395   };

   396 

   397   force.start = function() {

   398     var i,

   399         j,

   400         n = nodes.length,

   401         m = links.length,

   402         w = size[0],

   403         h = size[1],

   404         neighbors,

   405         o;

   406 

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

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

   409       o.weight = 0;

   410     }

   411 

   412     distances = [];

   413     strengths = [];

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

   415       o = links[i];

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

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

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

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

   420       ++o.source.weight;

   421       ++o.target.weight;

   422     }

   423 

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

   425       o = nodes[i];

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

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

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

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

   430     }

   431 

   432     charges = [];

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

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

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

   436       }

   437     } else {

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

   439         charges[i] = charge;

   440       }

   441     }

   442 

   443     // initialize node position based on first neighbor

   444     function position(dimension, size) {

   445       var neighbors = neighbor(i),

   446           j = -1,

   447           m = neighbors.length,

   448           x;

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

   450       return Math.random() * size;

   451     }

   452 

   453     // initialize neighbors lazily

   454     function neighbor() {

   455       if (!neighbors) {

   456         neighbors = [];

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

   458           neighbors[j] = [];

   459         }

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

   461           var o = links[j];

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

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

   464         }

   465       }

   466       return neighbors[i];

   467     }

   468 

   469     return force.resume();

   470   };

   471 

   472   force.resume = function() {

   473     alpha = .1;

   474     d3.timer(tick);

   475     return force;

   476   };

   477 

   478   force.stop = function() {

   479     alpha = 0;

   480     return force;

   481   };

   482 

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

   484   force.drag = function() {

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

   486         .on("dragstart", dragstart)

   487         .on("drag", d3_layout_forceDrag)

   488         .on("dragend", d3_layout_forceDragEnd);

   489 

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

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

   492         .call(drag);

   493   };

   494 

   495   function dragstart(d) {

   496     d3_layout_forceDragOver(d3_layout_forceDragNode = d);

   497     d3_layout_forceDragForce = force;

   498   }

   499 

   500   return force;

   501 };

   502 

   503 var d3_layout_forceDragForce,

   504     d3_layout_forceDragNode;

   505 

   506 function d3_layout_forceDragOver(d) {

   507   d.fixed |= 2;

   508 }

   509 

   510 function d3_layout_forceDragOut(d) {

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

   512 }

   513 

   514 function d3_layout_forceDragEnd() {

   515   d3_layout_forceDrag();

   516   d3_layout_forceDragNode.fixed &= 1;

   517   d3_layout_forceDragForce = d3_layout_forceDragNode = null;

   518 }

   519 

   520 function d3_layout_forceDrag() {

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

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

   523   d3_layout_forceDragForce.resume(); // restart annealing

   524 }

   525 

   526 function d3_layout_forceAccumulate(quad, alpha, charges) {

   527   var cx = 0,

   528       cy = 0;

   529   quad.charge = 0;

   530   if (!quad.leaf) {

   531     var nodes = quad.nodes,

   532         n = nodes.length,

   533         i = -1,

   534         c;

   535     while (++i < n) {

   536       c = nodes[i];

   537       if (c == null) continue;

   538       d3_layout_forceAccumulate(c, alpha, charges);

   539       quad.charge += c.charge;

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

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

   542     }

   543   }

   544   if (quad.point) {

   545     // jitter internal nodes that are coincident

   546     if (!quad.leaf) {

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

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

   549     }

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

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

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

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

   554   }

   555   quad.cx = cx / quad.charge;

   556   quad.cy = cy / quad.charge;

   557 }

   558 

   559 function d3_layout_forceLinkDistance(link) {

   560   return 20;

   561 }

   562 

   563 function d3_layout_forceLinkStrength(link) {

   564   return 1;

   565 }

   566 d3.layout.partition = function() {

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

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

   569 

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

   571     var children = node.children;

   572     node.x = x;

   573     node.y = node.depth * dy;

   574     node.dx = dx;

   575     node.dy = dy;

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

   577       var i = -1,

   578           n,

   579           c,

   580           d;

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

   582       while (++i < n) {

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

   584         x += d;

   585       }

   586     }

   587   }

   588 

   589   function depth(node) {

   590     var children = node.children,

   591         d = 0;

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

   593       var i = -1,

   594           n;

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

   596     }

   597     return 1 + d;

   598   }

   599 

   600   function partition(d, i) {

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

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

   603     return nodes;

   604   }

   605 

   606   partition.size = function(x) {

   607     if (!arguments.length) return size;

   608     size = x;

   609     return partition;

   610   };

   611 

   612   return d3_layout_hierarchyRebind(partition, hierarchy);

   613 };

   614 d3.layout.pie = function() {

   615   var value = Number,

   616       sort = d3_layout_pieSortByValue,

   617       startAngle = 0,

   618       endAngle = 2 * Math.PI;

   619 

   620   function pie(data, i) {

   621 

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

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

   624 

   625     // Compute the start angle.

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

   627         ? startAngle.apply(this, arguments)

   628         : startAngle);

   629 

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

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

   632         ? endAngle.apply(this, arguments)

   633         : endAngle) - startAngle)

   634         / d3.sum(values);

   635 

   636     // Optionally sort the data.

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

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

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

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

   641 

   642     // Compute the arcs!

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

   644       return {

   645         data: data[i],

   646         value: d = values[i],

   647         startAngle: a,

   648         endAngle: a += d * k

   649       };

   650     });

   651 

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

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

   654       return arcs[index[i]];

   655     });

   656   }

   657 

   658   /**

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

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

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

   662    */

   663   pie.value = function(x) {

   664     if (!arguments.length) return value;

   665     value = x;

   666     return pie;

   667   };

   668 

   669   /**

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

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

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

   673    * b.

   674    */

   675   pie.sort = function(x) {

   676     if (!arguments.length) return sort;

   677     sort = x;

   678     return pie;

   679   };

   680 

   681   /**

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

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

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

   685    * element).

   686    */

   687   pie.startAngle = function(x) {

   688     if (!arguments.length) return startAngle;

   689     startAngle = x;

   690     return pie;

   691   };

   692 

   693   /**

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

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

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

   697    * element).

   698    */

   699   pie.endAngle = function(x) {

   700     if (!arguments.length) return endAngle;

   701     endAngle = x;

   702     return pie;

   703   };

   704 

   705   return pie;

   706 };

   707 

   708 var d3_layout_pieSortByValue = {};

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

   710 d3.layout.stack = function() {

   711   var values = Object,

   712       order = d3_layout_stackOrders["default"],

   713       offset = d3_layout_stackOffsets["zero"],

   714       out = d3_layout_stackOut,

   715       x = d3_layout_stackX,

   716       y = d3_layout_stackY;

   717 

   718   function stack(data, index) {

   719 

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

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

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

   723     });

   724 

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

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

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

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

   729       });

   730     });

   731 

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

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

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

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

   736 

   737     // Compute the baseline…

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

   739 

   740     // And propagate it to other series.

   741     var n = series.length,

   742         m = series[0].length,

   743         i,

   744         j,

   745         o;

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

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

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

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

   750       }

   751     }

   752 

   753     return data;

   754   }

   755 

   756   stack.values = function(x) {

   757     if (!arguments.length) return values;

   758     values = x;

   759     return stack;

   760   };

   761 

   762   stack.order = function(x) {

   763     if (!arguments.length) return order;

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

   765     return stack;

   766   };

   767 

   768   stack.offset = function(x) {

   769     if (!arguments.length) return offset;

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

   771     return stack;

   772   };

   773 

   774   stack.x = function(z) {

   775     if (!arguments.length) return x;

   776     x = z;

   777     return stack;

   778   };

   779 

   780   stack.y = function(z) {

   781     if (!arguments.length) return y;

   782     y = z;

   783     return stack;

   784   };

   785 

   786   stack.out = function(z) {

   787     if (!arguments.length) return out;

   788     out = z;

   789     return stack;

   790   };

   791 

   792   return stack;

   793 }

   794 

   795 function d3_layout_stackX(d) {

   796   return d.x;

   797 }

   798 

   799 function d3_layout_stackY(d) {

   800   return d.y;

   801 }

   802 

   803 function d3_layout_stackOut(d, y0, y) {

   804   d.y0 = y0;

   805   d.y = y;

   806 }

   807 

   808 var d3_layout_stackOrders = {

   809 

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

   811     var n = data.length,

   812         i,

   813         j,

   814         max = data.map(d3_layout_stackMaxIndex),

   815         sums = data.map(d3_layout_stackReduceSum),

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

   817         top = 0,

   818         bottom = 0,

   819         tops = [],

   820         bottoms = [];

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

   822       j = index[i];

   823       if (top < bottom) {

   824         top += sums[j];

   825         tops.push(j);

   826       } else {

   827         bottom += sums[j];

   828         bottoms.push(j);

   829       }

   830     }

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

   832   },

   833 

   834   "reverse": function(data) {

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

   836   },

   837 

   838   "default": function(data) {

   839     return d3.range(data.length);

   840   }

   841 

   842 };

   843 

   844 var d3_layout_stackOffsets = {

   845 

   846   "silhouette": function(data) {

   847     var n = data.length,

   848         m = data[0].length,

   849         sums = [],

   850         max = 0,

   851         i,

   852         j,

   853         o,

   854         y0 = [];

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

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

   857       if (o > max) max = o;

   858       sums.push(o);

   859     }

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

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

   862     }

   863     return y0;

   864   },

   865 

   866   "wiggle": function(data) {

   867     var n = data.length,

   868         x = data[0],

   869         m = x.length,

   870         max = 0,

   871         i,

   872         j,

   873         k,

   874         s1,

   875         s2,

   876         s3,

   877         dx,

   878         o,

   879         o0,

   880         y0 = [];

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

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

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

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

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

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

   887         }

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

   889       }

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

   891       if (o < o0) o0 = o;

   892     }

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

   894     return y0;

   895   },

   896 

   897   "expand": function(data) {

   898     var n = data.length,

   899         m = data[0].length,

   900         k = 1 / n,

   901         i,

   902         j,

   903         o,

   904         y0 = [];

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

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

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

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

   909     }

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

   911     return y0;

   912   },

   913 

   914   "zero": function(data) {

   915     var j = -1,

   916         m = data[0].length,

   917         y0 = [];

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

   919     return y0;

   920   }

   921 

   922 };

   923 

   924 function d3_layout_stackMaxIndex(array) {

   925   var i = 1,

   926       j = 0,

   927       v = array[0][1],

   928       k,

   929       n = array.length;

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

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

   932       j = i;

   933       v = k;

   934     }

   935   }

   936   return j;

   937 }

   938 

   939 function d3_layout_stackReduceSum(d) {

   940   return d.reduce(d3_layout_stackSum, 0);

   941 }

   942 

   943 function d3_layout_stackSum(p, d) {

   944   return p + d[1];

   945 }

   946 d3.layout.histogram = function() {

   947   var frequency = true,

   948       valuer = Number,

   949       ranger = d3_layout_histogramRange,

   950       binner = d3_layout_histogramBinSturges;

   951 

   952   function histogram(data, i) {

   953     var bins = [],

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

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

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

   957         bin,

   958         i = -1,

   959         n = values.length,

   960         m = thresholds.length - 1,

   961         k = frequency ? 1 : 1 / n,

   962         x;

   963 

   964     // Initialize the bins.

   965     while (++i < m) {

   966       bin = bins[i] = [];

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

   968       bin.y = 0;

   969     }

   970 

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

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

   973       x = values[i];

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

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

   976         bin.y += k;

   977         bin.push(data[i]);

   978       }

   979     }

   980 

   981     return bins;

   982   }

   983 

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

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

   986   histogram.value = function(x) {

   987     if (!arguments.length) return valuer;

   988     valuer = x;

   989     return histogram;

   990   };

   991 

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

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

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

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

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

   997   // values.

   998   histogram.range = function(x) {

   999     if (!arguments.length) return ranger;

  1000     ranger = d3.functor(x);

  1001     return histogram;

  1002   };

  1003 

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

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

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

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

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

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

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

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

  1012   // Sturges' formula.

  1013   histogram.bins = function(x) {

  1014     if (!arguments.length) return binner;

  1015     binner = typeof x === "number"

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

  1017         : d3.functor(x);

  1018     return histogram;

  1019   };

  1020 

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

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

  1023   histogram.frequency = function(x) {

  1024     if (!arguments.length) return frequency;

  1025     frequency = !!x;

  1026     return histogram;

  1027   };

  1028 

  1029   return histogram;

  1030 };

  1031 

  1032 function d3_layout_histogramBinSturges(range, values) {

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

  1034 }

  1035 

  1036 function d3_layout_histogramBinFixed(range, n) {

  1037   var x = -1,

  1038       b = +range[0],

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

  1040       f = [];

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

  1042   return f;

  1043 }

  1044 

  1045 function d3_layout_histogramRange(values) {

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

  1047 }

  1048 d3.layout.hierarchy = function() {

  1049   var sort = d3_layout_hierarchySort,

  1050       children = d3_layout_hierarchyChildren,

  1051       value = d3_layout_hierarchyValue;

  1052 

  1053   // Recursively compute the node depth and value.

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

  1055   function recurse(data, depth, nodes) {

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

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

  1058     node.depth = depth;

  1059     nodes.push(node);

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

  1061       var i = -1,

  1062           n,

  1063           c = node.children = [],

  1064           v = 0,

  1065           j = depth + 1;

  1066       while (++i < n) {

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

  1068         d.parent = node;

  1069         c.push(d);

  1070         v += d.value;

  1071       }

  1072       if (sort) c.sort(sort);

  1073       if (value) node.value = v;

  1074     } else if (value) {

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

  1076     }

  1077     return node;

  1078   }

  1079 

  1080   // Recursively re-evaluates the node value.

  1081   function revalue(node, depth) {

  1082     var children = node.children,

  1083         v = 0;

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

  1085       var i = -1,

  1086           n,

  1087           j = depth + 1;

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

  1089     } else if (value) {

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

  1091     }

  1092     if (value) node.value = v;

  1093     return v;

  1094   }

  1095 

  1096   function hierarchy(d) {

  1097     var nodes = [];

  1098     recurse(d, 0, nodes);

  1099     return nodes;

  1100   }

  1101 

  1102   hierarchy.sort = function(x) {

  1103     if (!arguments.length) return sort;

  1104     sort = x;

  1105     return hierarchy;

  1106   };

  1107 

  1108   hierarchy.children = function(x) {

  1109     if (!arguments.length) return children;

  1110     children = x;

  1111     return hierarchy;

  1112   };

  1113 

  1114   hierarchy.value = function(x) {

  1115     if (!arguments.length) return value;

  1116     value = x;

  1117     return hierarchy;

  1118   };

  1119 

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

  1121   hierarchy.revalue = function(root) {

  1122     revalue(root, 0);

  1123     return root;

  1124   };

  1125 

  1126   return hierarchy;

  1127 };

  1128 

  1129 // A method assignment helper for hierarchy subclasses.

  1130 function d3_layout_hierarchyRebind(object, hierarchy) {

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

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

  1133   object.links = d3_layout_hierarchyLinks;

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

  1135 

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