d3.layout.js 47 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882
  1. // See d3.LICENSE.txt for license.
  2. (function(){d3.layout = {};
  3. // Implements hierarchical edge bundling using Holten's algorithm. For each
  4. // input link, a path is computed that travels through the tree, up the parent
  5. // hierarchy to the least common ancestor, and then back down to the destination
  6. // node. Each path is simply an array of nodes.
  7. d3.layout.bundle = function() {
  8. return function(links) {
  9. var paths = [],
  10. i = -1,
  11. n = links.length;
  12. while (++i < n) paths.push(d3_layout_bundlePath(links[i]));
  13. return paths;
  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. function d3_layout_bundleAncestors(node) {
  33. var ancestors = [],
  34. parent = node.parent;
  35. while (parent != null) {
  36. ancestors.push(node);
  37. node = parent;
  38. parent = parent.parent;
  39. }
  40. ancestors.push(node);
  41. return ancestors;
  42. }
  43. function d3_layout_bundleLeastCommonAncestor(a, b) {
  44. if (a === b) return a;
  45. var aNodes = d3_layout_bundleAncestors(a),
  46. bNodes = d3_layout_bundleAncestors(b),
  47. aNode = aNodes.pop(),
  48. bNode = bNodes.pop(),
  49. sharedNode = null;
  50. while (aNode === bNode) {
  51. sharedNode = aNode;
  52. aNode = aNodes.pop();
  53. bNode = bNodes.pop();
  54. }
  55. return sharedNode;
  56. }
  57. d3.layout.chord = function() {
  58. var chord = {},
  59. chords,
  60. groups,
  61. matrix,
  62. n,
  63. padding = 0,
  64. sortGroups,
  65. sortSubgroups,
  66. sortChords;
  67. function relayout() {
  68. var subgroups = {},
  69. groupSums = [],
  70. groupIndex = d3.range(n),
  71. subgroupIndex = [],
  72. k,
  73. x,
  74. x0,
  75. i,
  76. j;
  77. chords = [];
  78. groups = [];
  79. // Compute the sum.
  80. k = 0, i = -1; while (++i < n) {
  81. x = 0, j = -1; while (++j < n) {
  82. x += matrix[i][j];
  83. }
  84. groupSums.push(x);
  85. subgroupIndex.push(d3.range(n));
  86. k += x;
  87. }
  88. // Sort groups…
  89. if (sortGroups) {
  90. groupIndex.sort(function(a, b) {
  91. return sortGroups(groupSums[a], groupSums[b]);
  92. });
  93. }
  94. // Sort subgroups…
  95. if (sortSubgroups) {
  96. subgroupIndex.forEach(function(d, i) {
  97. d.sort(function(a, b) {
  98. return sortSubgroups(matrix[i][a], matrix[i][b]);
  99. });
  100. });
  101. }
  102. // Convert the sum to scaling factor for [0, 2pi].
  103. // TODO Allow start and end angle to be specified.
  104. // TODO Allow padding to be specified as percentage?
  105. k = (2 * Math.PI - padding * n) / k;
  106. // Compute the start and end angle for each group and subgroup.
  107. // Note: Opera has a bug reordering object literal properties!
  108. x = 0, i = -1; while (++i < n) {
  109. x0 = x, j = -1; while (++j < n) {
  110. var di = groupIndex[i],
  111. dj = subgroupIndex[di][j],
  112. v = matrix[di][dj],
  113. a0 = x,
  114. a1 = x += v * k;
  115. subgroups[di + "-" + dj] = {
  116. index: di,
  117. subindex: dj,
  118. startAngle: a0,
  119. endAngle: a1,
  120. value: v
  121. };
  122. }
  123. groups.push({
  124. index: di,
  125. startAngle: x0,
  126. endAngle: x,
  127. value: (x - x0) / k
  128. });
  129. x += padding;
  130. }
  131. // Generate chords for each (non-empty) subgroup-subgroup link.
  132. i = -1; while (++i < n) {
  133. j = i - 1; while (++j < n) {
  134. var source = subgroups[i + "-" + j],
  135. target = subgroups[j + "-" + i];
  136. if (source.value || target.value) {
  137. chords.push(source.value < target.value
  138. ? {source: target, target: source}
  139. : {source: source, target: target});
  140. }
  141. }
  142. }
  143. if (sortChords) resort();
  144. }
  145. function resort() {
  146. chords.sort(function(a, b) {
  147. return sortChords(
  148. (a.source.value + a.target.value) / 2,
  149. (b.source.value + b.target.value) / 2);
  150. });
  151. }
  152. chord.matrix = function(x) {
  153. if (!arguments.length) return matrix;
  154. n = (matrix = x) && matrix.length;
  155. chords = groups = null;
  156. return chord;
  157. };
  158. chord.padding = function(x) {
  159. if (!arguments.length) return padding;
  160. padding = x;
  161. chords = groups = null;
  162. return chord;
  163. };
  164. chord.sortGroups = function(x) {
  165. if (!arguments.length) return sortGroups;
  166. sortGroups = x;
  167. chords = groups = null;
  168. return chord;
  169. };
  170. chord.sortSubgroups = function(x) {
  171. if (!arguments.length) return sortSubgroups;
  172. sortSubgroups = x;
  173. chords = null;
  174. return chord;
  175. };
  176. chord.sortChords = function(x) {
  177. if (!arguments.length) return sortChords;
  178. sortChords = x;
  179. if (chords) resort();
  180. return chord;
  181. };
  182. chord.chords = function() {
  183. if (!chords) relayout();
  184. return chords;
  185. };
  186. chord.groups = function() {
  187. if (!groups) relayout();
  188. return groups;
  189. };
  190. return chord;
  191. };
  192. // A rudimentary force layout using Gauss-Seidel.
  193. d3.layout.force = function() {
  194. var force = {},
  195. event = d3.dispatch("tick"),
  196. size = [1, 1],
  197. drag,
  198. alpha,
  199. friction = .9,
  200. linkDistance = d3_layout_forceLinkDistance,
  201. linkStrength = d3_layout_forceLinkStrength,
  202. charge = -30,
  203. gravity = .1,
  204. theta = .8,
  205. interval,
  206. nodes = [],
  207. links = [],
  208. distances,
  209. strengths,
  210. charges;
  211. function repulse(node) {
  212. return function(quad, x1, y1, x2, y2) {
  213. if (quad.point !== node) {
  214. var dx = quad.cx - node.x,
  215. dy = quad.cy - node.y,
  216. dn = 1 / Math.sqrt(dx * dx + dy * dy);
  217. /* Barnes-Hut criterion. */
  218. if ((x2 - x1) * dn < theta) {
  219. var k = quad.charge * dn * dn;
  220. node.px -= dx * k;
  221. node.py -= dy * k;
  222. return true;
  223. }
  224. if (quad.point && isFinite(dn)) {
  225. var k = quad.pointCharge * dn * dn;
  226. node.px -= dx * k;
  227. node.py -= dy * k;
  228. }
  229. }
  230. return !quad.charge;
  231. };
  232. }
  233. function tick() {
  234. var n = nodes.length,
  235. m = links.length,
  236. q,
  237. i, // current index
  238. o, // current object
  239. s, // current source
  240. t, // current target
  241. l, // current distance
  242. k, // current force
  243. x, // x-distance
  244. y; // y-distance
  245. // gauss-seidel relaxation for links
  246. for (i = 0; i < m; ++i) {
  247. o = links[i];
  248. s = o.source;
  249. t = o.target;
  250. x = t.x - s.x;
  251. y = t.y - s.y;
  252. if (l = (x * x + y * y)) {
  253. l = alpha * strengths[i] * ((l = Math.sqrt(l)) - distances[i]) / l;
  254. x *= l;
  255. y *= l;
  256. t.x -= x * (k = s.weight / (t.weight + s.weight));
  257. t.y -= y * k;
  258. s.x += x * (k = 1 - k);
  259. s.y += y * k;
  260. }
  261. }
  262. // apply gravity forces
  263. if (k = alpha * gravity) {
  264. x = size[0] / 2;
  265. y = size[1] / 2;
  266. i = -1; if (k) while (++i < n) {
  267. o = nodes[i];
  268. o.x += (x - o.x) * k;
  269. o.y += (y - o.y) * k;
  270. }
  271. }
  272. // compute quadtree center of mass and apply charge forces
  273. if (charge) {
  274. d3_layout_forceAccumulate(q = d3.geom.quadtree(nodes), alpha, charges);
  275. i = -1; while (++i < n) {
  276. if (!(o = nodes[i]).fixed) {
  277. q.visit(repulse(o));
  278. }
  279. }
  280. }
  281. // position verlet integration
  282. i = -1; while (++i < n) {
  283. o = nodes[i];
  284. if (o.fixed) {
  285. o.x = o.px;
  286. o.y = o.py;
  287. } else {
  288. o.x -= (o.px - (o.px = o.x)) * friction;
  289. o.y -= (o.py - (o.py = o.y)) * friction;
  290. }
  291. }
  292. event.tick({type: "tick", alpha: alpha});
  293. // simulated annealing, basically
  294. return (alpha *= .99) < .005;
  295. }
  296. force.nodes = function(x) {
  297. if (!arguments.length) return nodes;
  298. nodes = x;
  299. return force;
  300. };
  301. force.links = function(x) {
  302. if (!arguments.length) return links;
  303. links = x;
  304. return force;
  305. };
  306. force.size = function(x) {
  307. if (!arguments.length) return size;
  308. size = x;
  309. return force;
  310. };
  311. force.linkDistance = function(x) {
  312. if (!arguments.length) return linkDistance;
  313. linkDistance = d3.functor(x);
  314. return force;
  315. };
  316. // For backwards-compatibility.
  317. force.distance = force.linkDistance;
  318. force.linkStrength = function(x) {
  319. if (!arguments.length) return linkStrength;
  320. linkStrength = d3.functor(x);
  321. return force;
  322. };
  323. force.friction = function(x) {
  324. if (!arguments.length) return friction;
  325. friction = x;
  326. return force;
  327. };
  328. force.charge = function(x) {
  329. if (!arguments.length) return charge;
  330. charge = typeof x === "function" ? x : +x;
  331. return force;
  332. };
  333. force.gravity = function(x) {
  334. if (!arguments.length) return gravity;
  335. gravity = x;
  336. return force;
  337. };
  338. force.theta = function(x) {
  339. if (!arguments.length) return theta;
  340. theta = x;
  341. return force;
  342. };
  343. force.start = function() {
  344. var i,
  345. j,
  346. n = nodes.length,
  347. m = links.length,
  348. w = size[0],
  349. h = size[1],
  350. neighbors,
  351. o;
  352. for (i = 0; i < n; ++i) {
  353. (o = nodes[i]).index = i;
  354. o.weight = 0;
  355. }
  356. distances = [];
  357. strengths = [];
  358. for (i = 0; i < m; ++i) {
  359. o = links[i];
  360. if (typeof o.source == "number") o.source = nodes[o.source];
  361. if (typeof o.target == "number") o.target = nodes[o.target];
  362. distances[i] = linkDistance.call(this, o, i);
  363. strengths[i] = linkStrength.call(this, o, i);
  364. ++o.source.weight;
  365. ++o.target.weight;
  366. }
  367. for (i = 0; i < n; ++i) {
  368. o = nodes[i];
  369. if (isNaN(o.x)) o.x = position("x", w);
  370. if (isNaN(o.y)) o.y = position("y", h);
  371. if (isNaN(o.px)) o.px = o.x;
  372. if (isNaN(o.py)) o.py = o.y;
  373. }
  374. charges = [];
  375. if (typeof charge === "function") {
  376. for (i = 0; i < n; ++i) {
  377. charges[i] = +charge.call(this, nodes[i], i);
  378. }
  379. } else {
  380. for (i = 0; i < n; ++i) {
  381. charges[i] = charge;
  382. }
  383. }
  384. // initialize node position based on first neighbor
  385. function position(dimension, size) {
  386. var neighbors = neighbor(i),
  387. j = -1,
  388. m = neighbors.length,
  389. x;
  390. while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x;
  391. return Math.random() * size;
  392. }
  393. // initialize neighbors lazily
  394. function neighbor() {
  395. if (!neighbors) {
  396. neighbors = [];
  397. for (j = 0; j < n; ++j) {
  398. neighbors[j] = [];
  399. }
  400. for (j = 0; j < m; ++j) {
  401. var o = links[j];
  402. neighbors[o.source.index].push(o.target);
  403. neighbors[o.target.index].push(o.source);
  404. }
  405. }
  406. return neighbors[i];
  407. }
  408. return force.resume();
  409. };
  410. force.resume = function() {
  411. alpha = .1;
  412. d3.timer(tick);
  413. return force;
  414. };
  415. force.stop = function() {
  416. alpha = 0;
  417. return force;
  418. };
  419. // use `node.call(force.drag)` to make nodes draggable
  420. force.drag = function() {
  421. if (!drag) drag = d3.behavior.drag()
  422. .origin(Object)
  423. .on("dragstart", dragstart)
  424. .on("drag", d3_layout_forceDrag)
  425. .on("dragend", d3_layout_forceDragEnd);
  426. this.on("mouseover.force", d3_layout_forceDragOver)
  427. .on("mouseout.force", d3_layout_forceDragOut)
  428. .call(drag);
  429. };
  430. function dragstart(d) {
  431. d3_layout_forceDragOver(d3_layout_forceDragNode = d);
  432. d3_layout_forceDragForce = force;
  433. }
  434. return d3.rebind(force, event, "on");
  435. };
  436. var d3_layout_forceDragForce,
  437. d3_layout_forceDragNode;
  438. function d3_layout_forceDragOver(d) {
  439. d.fixed |= 2;
  440. }
  441. function d3_layout_forceDragOut(d) {
  442. if (d !== d3_layout_forceDragNode) d.fixed &= 1;
  443. }
  444. function d3_layout_forceDragEnd() {
  445. d3_layout_forceDrag();
  446. d3_layout_forceDragNode.fixed &= 1;
  447. d3_layout_forceDragForce = d3_layout_forceDragNode = null;
  448. }
  449. function d3_layout_forceDrag() {
  450. d3_layout_forceDragNode.px = d3.event.x;
  451. d3_layout_forceDragNode.py = d3.event.y;
  452. d3_layout_forceDragForce.resume(); // restart annealing
  453. }
  454. function d3_layout_forceAccumulate(quad, alpha, charges) {
  455. var cx = 0,
  456. cy = 0;
  457. quad.charge = 0;
  458. if (!quad.leaf) {
  459. var nodes = quad.nodes,
  460. n = nodes.length,
  461. i = -1,
  462. c;
  463. while (++i < n) {
  464. c = nodes[i];
  465. if (c == null) continue;
  466. d3_layout_forceAccumulate(c, alpha, charges);
  467. quad.charge += c.charge;
  468. cx += c.charge * c.cx;
  469. cy += c.charge * c.cy;
  470. }
  471. }
  472. if (quad.point) {
  473. // jitter internal nodes that are coincident
  474. if (!quad.leaf) {
  475. quad.point.x += Math.random() - .5;
  476. quad.point.y += Math.random() - .5;
  477. }
  478. var k = alpha * charges[quad.point.index];
  479. quad.charge += quad.pointCharge = k;
  480. cx += k * quad.point.x;
  481. cy += k * quad.point.y;
  482. }
  483. quad.cx = cx / quad.charge;
  484. quad.cy = cy / quad.charge;
  485. }
  486. function d3_layout_forceLinkDistance(link) {
  487. return 20;
  488. }
  489. function d3_layout_forceLinkStrength(link) {
  490. return 1;
  491. }
  492. d3.layout.partition = function() {
  493. var hierarchy = d3.layout.hierarchy(),
  494. size = [1, 1]; // width, height
  495. function position(node, x, dx, dy) {
  496. var children = node.children;
  497. node.x = x;
  498. node.y = node.depth * dy;
  499. node.dx = dx;
  500. node.dy = dy;
  501. if (children && (n = children.length)) {
  502. var i = -1,
  503. n,
  504. c,
  505. d;
  506. dx = node.value ? dx / node.value : 0;
  507. while (++i < n) {
  508. position(c = children[i], x, d = c.value * dx, dy);
  509. x += d;
  510. }
  511. }
  512. }
  513. function depth(node) {
  514. var children = node.children,
  515. d = 0;
  516. if (children && (n = children.length)) {
  517. var i = -1,
  518. n;
  519. while (++i < n) d = Math.max(d, depth(children[i]));
  520. }
  521. return 1 + d;
  522. }
  523. function partition(d, i) {
  524. var nodes = hierarchy.call(this, d, i);
  525. position(nodes[0], 0, size[0], size[1] / depth(nodes[0]));
  526. return nodes;
  527. }
  528. partition.size = function(x) {
  529. if (!arguments.length) return size;
  530. size = x;
  531. return partition;
  532. };
  533. return d3_layout_hierarchyRebind(partition, hierarchy);
  534. };
  535. d3.layout.pie = function() {
  536. var value = Number,
  537. sort = d3_layout_pieSortByValue,
  538. startAngle = 0,
  539. endAngle = 2 * Math.PI;
  540. function pie(data, i) {
  541. // Compute the numeric values for each data element.
  542. var values = data.map(function(d, i) { return +value.call(pie, d, i); });
  543. // Compute the start angle.
  544. var a = +(typeof startAngle === "function"
  545. ? startAngle.apply(this, arguments)
  546. : startAngle);
  547. // Compute the angular scale factor: from value to radians.
  548. var k = ((typeof endAngle === "function"
  549. ? endAngle.apply(this, arguments)
  550. : endAngle) - startAngle)
  551. / d3.sum(values);
  552. // Optionally sort the data.
  553. var index = d3.range(data.length);
  554. if (sort != null) index.sort(sort === d3_layout_pieSortByValue
  555. ? function(i, j) { return values[j] - values[i]; }
  556. : function(i, j) { return sort(data[i], data[j]); });
  557. // Compute the arcs!
  558. // They are stored in the original data's order.
  559. var arcs = [];
  560. index.forEach(function(i) {
  561. arcs[i] = {
  562. data: data[i],
  563. value: d = values[i],
  564. startAngle: a,
  565. endAngle: a += d * k
  566. };
  567. });
  568. return arcs;
  569. }
  570. /**
  571. * Specifies the value function *x*, which returns a nonnegative numeric value
  572. * for each datum. The default value function is `Number`. The value function
  573. * is passed two arguments: the current datum and the current index.
  574. */
  575. pie.value = function(x) {
  576. if (!arguments.length) return value;
  577. value = x;
  578. return pie;
  579. };
  580. /**
  581. * Specifies a sort comparison operator *x*. The comparator is passed two data
  582. * elements from the data array, a and b; it returns a negative value if a is
  583. * less than b, a positive value if a is greater than b, and zero if a equals
  584. * b.
  585. */
  586. pie.sort = function(x) {
  587. if (!arguments.length) return sort;
  588. sort = x;
  589. return pie;
  590. };
  591. /**
  592. * Specifies the overall start angle of the pie chart. Defaults to 0. The
  593. * start angle can be specified either as a constant or as a function; in the
  594. * case of a function, it is evaluated once per array (as opposed to per
  595. * element).
  596. */
  597. pie.startAngle = function(x) {
  598. if (!arguments.length) return startAngle;
  599. startAngle = x;
  600. return pie;
  601. };
  602. /**
  603. * Specifies the overall end angle of the pie chart. Defaults to 2π. The
  604. * end angle can be specified either as a constant or as a function; in the
  605. * case of a function, it is evaluated once per array (as opposed to per
  606. * element).
  607. */
  608. pie.endAngle = function(x) {
  609. if (!arguments.length) return endAngle;
  610. endAngle = x;
  611. return pie;
  612. };
  613. return pie;
  614. };
  615. var d3_layout_pieSortByValue = {};
  616. // data is two-dimensional array of x,y; we populate y0
  617. d3.layout.stack = function() {
  618. var values = Object,
  619. order = d3_layout_stackOrders["default"],
  620. offset = d3_layout_stackOffsets["zero"],
  621. out = d3_layout_stackOut,
  622. x = d3_layout_stackX,
  623. y = d3_layout_stackY;
  624. function stack(data, index) {
  625. // Convert series to canonical two-dimensional representation.
  626. var series = data.map(function(d, i) {
  627. return values.call(stack, d, i);
  628. });
  629. // Convert each series to canonical [[x,y]] representation.
  630. var points = series.map(function(d, i) {
  631. return d.map(function(v, i) {
  632. return [x.call(stack, v, i), y.call(stack, v, i)];
  633. });
  634. });
  635. // Compute the order of series, and permute them.
  636. var orders = order.call(stack, points, index);
  637. series = d3.permute(series, orders);
  638. points = d3.permute(points, orders);
  639. // Compute the baseline…
  640. var offsets = offset.call(stack, points, index);
  641. // And propagate it to other series.
  642. var n = series.length,
  643. m = series[0].length,
  644. i,
  645. j,
  646. o;
  647. for (j = 0; j < m; ++j) {
  648. out.call(stack, series[0][j], o = offsets[j], points[0][j][1]);
  649. for (i = 1; i < n; ++i) {
  650. out.call(stack, series[i][j], o += points[i - 1][j][1], points[i][j][1]);
  651. }
  652. }
  653. return data;
  654. }
  655. stack.values = function(x) {
  656. if (!arguments.length) return values;
  657. values = x;
  658. return stack;
  659. };
  660. stack.order = function(x) {
  661. if (!arguments.length) return order;
  662. order = typeof x === "function" ? x : d3_layout_stackOrders[x];
  663. return stack;
  664. };
  665. stack.offset = function(x) {
  666. if (!arguments.length) return offset;
  667. offset = typeof x === "function" ? x : d3_layout_stackOffsets[x];
  668. return stack;
  669. };
  670. stack.x = function(z) {
  671. if (!arguments.length) return x;
  672. x = z;
  673. return stack;
  674. };
  675. stack.y = function(z) {
  676. if (!arguments.length) return y;
  677. y = z;
  678. return stack;
  679. };
  680. stack.out = function(z) {
  681. if (!arguments.length) return out;
  682. out = z;
  683. return stack;
  684. };
  685. return stack;
  686. }
  687. function d3_layout_stackX(d) {
  688. return d.x;
  689. }
  690. function d3_layout_stackY(d) {
  691. return d.y;
  692. }
  693. function d3_layout_stackOut(d, y0, y) {
  694. d.y0 = y0;
  695. d.y = y;
  696. }
  697. var d3_layout_stackOrders = {
  698. "inside-out": function(data) {
  699. var n = data.length,
  700. i,
  701. j,
  702. max = data.map(d3_layout_stackMaxIndex),
  703. sums = data.map(d3_layout_stackReduceSum),
  704. index = d3.range(n).sort(function(a, b) { return max[a] - max[b]; }),
  705. top = 0,
  706. bottom = 0,
  707. tops = [],
  708. bottoms = [];
  709. for (i = 0; i < n; ++i) {
  710. j = index[i];
  711. if (top < bottom) {
  712. top += sums[j];
  713. tops.push(j);
  714. } else {
  715. bottom += sums[j];
  716. bottoms.push(j);
  717. }
  718. }
  719. return bottoms.reverse().concat(tops);
  720. },
  721. "reverse": function(data) {
  722. return d3.range(data.length).reverse();
  723. },
  724. "default": function(data) {
  725. return d3.range(data.length);
  726. }
  727. };
  728. var d3_layout_stackOffsets = {
  729. "silhouette": function(data) {
  730. var n = data.length,
  731. m = data[0].length,
  732. sums = [],
  733. max = 0,
  734. i,
  735. j,
  736. o,
  737. y0 = [];
  738. for (j = 0; j < m; ++j) {
  739. for (i = 0, o = 0; i < n; i++) o += data[i][j][1];
  740. if (o > max) max = o;
  741. sums.push(o);
  742. }
  743. for (j = 0; j < m; ++j) {
  744. y0[j] = (max - sums[j]) / 2;
  745. }
  746. return y0;
  747. },
  748. "wiggle": function(data) {
  749. var n = data.length,
  750. x = data[0],
  751. m = x.length,
  752. max = 0,
  753. i,
  754. j,
  755. k,
  756. s1,
  757. s2,
  758. s3,
  759. dx,
  760. o,
  761. o0,
  762. y0 = [];
  763. y0[0] = o = o0 = 0;
  764. for (j = 1; j < m; ++j) {
  765. for (i = 0, s1 = 0; i < n; ++i) s1 += data[i][j][1];
  766. for (i = 0, s2 = 0, dx = x[j][0] - x[j - 1][0]; i < n; ++i) {
  767. for (k = 0, s3 = (data[i][j][1] - data[i][j - 1][1]) / (2 * dx); k < i; ++k) {
  768. s3 += (data[k][j][1] - data[k][j - 1][1]) / dx;
  769. }
  770. s2 += s3 * data[i][j][1];
  771. }
  772. y0[j] = o -= s1 ? s2 / s1 * dx : 0;
  773. if (o < o0) o0 = o;
  774. }
  775. for (j = 0; j < m; ++j) y0[j] -= o0;
  776. return y0;
  777. },
  778. "expand": function(data) {
  779. var n = data.length,
  780. m = data[0].length,
  781. k = 1 / n,
  782. i,
  783. j,
  784. o,
  785. y0 = [];
  786. for (j = 0; j < m; ++j) {
  787. for (i = 0, o = 0; i < n; i++) o += data[i][j][1];
  788. if (o) for (i = 0; i < n; i++) data[i][j][1] /= o;
  789. else for (i = 0; i < n; i++) data[i][j][1] = k;
  790. }
  791. for (j = 0; j < m; ++j) y0[j] = 0;
  792. return y0;
  793. },
  794. "zero": function(data) {
  795. var j = -1,
  796. m = data[0].length,
  797. y0 = [];
  798. while (++j < m) y0[j] = 0;
  799. return y0;
  800. }
  801. };
  802. function d3_layout_stackMaxIndex(array) {
  803. var i = 1,
  804. j = 0,
  805. v = array[0][1],
  806. k,
  807. n = array.length;
  808. for (; i < n; ++i) {
  809. if ((k = array[i][1]) > v) {
  810. j = i;
  811. v = k;
  812. }
  813. }
  814. return j;
  815. }
  816. function d3_layout_stackReduceSum(d) {
  817. return d.reduce(d3_layout_stackSum, 0);
  818. }
  819. function d3_layout_stackSum(p, d) {
  820. return p + d[1];
  821. }
  822. d3.layout.histogram = function() {
  823. var frequency = true,
  824. valuer = Number,
  825. ranger = d3_layout_histogramRange,
  826. binner = d3_layout_histogramBinSturges;
  827. function histogram(data, i) {
  828. var bins = [],
  829. values = data.map(valuer, this),
  830. range = ranger.call(this, values, i),
  831. thresholds = binner.call(this, range, values, i),
  832. bin,
  833. i = -1,
  834. n = values.length,
  835. m = thresholds.length - 1,
  836. k = frequency ? 1 : 1 / n,
  837. x;
  838. // Initialize the bins.
  839. while (++i < m) {
  840. bin = bins[i] = [];
  841. bin.dx = thresholds[i + 1] - (bin.x = thresholds[i]);
  842. bin.y = 0;
  843. }
  844. // Fill the bins, ignoring values outside the range.
  845. i = -1; while(++i < n) {
  846. x = values[i];
  847. if ((x >= range[0]) && (x <= range[1])) {
  848. bin = bins[d3.bisect(thresholds, x, 1, m) - 1];
  849. bin.y += k;
  850. bin.push(data[i]);
  851. }
  852. }
  853. return bins;
  854. }
  855. // Specifies how to extract a value from the associated data. The default
  856. // value function is `Number`, which is equivalent to the identity function.
  857. histogram.value = function(x) {
  858. if (!arguments.length) return valuer;
  859. valuer = x;
  860. return histogram;
  861. };
  862. // Specifies the range of the histogram. Values outside the specified range
  863. // will be ignored. The argument `x` may be specified either as a two-element
  864. // array representing the minimum and maximum value of the range, or as a
  865. // function that returns the range given the array of values and the current
  866. // index `i`. The default range is the extent (minimum and maximum) of the
  867. // values.
  868. histogram.range = function(x) {
  869. if (!arguments.length) return ranger;
  870. ranger = d3.functor(x);
  871. return histogram;
  872. };
  873. // Specifies how to bin values in the histogram. The argument `x` may be
  874. // specified as a number, in which case the range of values will be split
  875. // uniformly into the given number of bins. Or, `x` may be an array of
  876. // threshold values, defining the bins; the specified array must contain the
  877. // rightmost (upper) value, thus specifying n + 1 values for n bins. Or, `x`
  878. // may be a function which is evaluated, being passed the range, the array of
  879. // values, and the current index `i`, returning an array of thresholds. The
  880. // default bin function will divide the values into uniform bins using
  881. // Sturges' formula.
  882. histogram.bins = function(x) {
  883. if (!arguments.length) return binner;
  884. binner = typeof x === "number"
  885. ? function(range) { return d3_layout_histogramBinFixed(range, x); }
  886. : d3.functor(x);
  887. return histogram;
  888. };
  889. // Specifies whether the histogram's `y` value is a count (frequency) or a
  890. // probability (density). The default value is true.
  891. histogram.frequency = function(x) {
  892. if (!arguments.length) return frequency;
  893. frequency = !!x;
  894. return histogram;
  895. };
  896. return histogram;
  897. };
  898. function d3_layout_histogramBinSturges(range, values) {
  899. return d3_layout_histogramBinFixed(range, Math.ceil(Math.log(values.length) / Math.LN2 + 1));
  900. }
  901. function d3_layout_histogramBinFixed(range, n) {
  902. var x = -1,
  903. b = +range[0],
  904. m = (range[1] - b) / n,
  905. f = [];
  906. while (++x <= n) f[x] = m * x + b;
  907. return f;
  908. }
  909. function d3_layout_histogramRange(values) {
  910. return [d3.min(values), d3.max(values)];
  911. }
  912. d3.layout.hierarchy = function() {
  913. var sort = d3_layout_hierarchySort,
  914. children = d3_layout_hierarchyChildren,
  915. value = d3_layout_hierarchyValue;
  916. // Recursively compute the node depth and value.
  917. // Also converts the data representation into a standard hierarchy structure.
  918. function recurse(data, depth, nodes) {
  919. var childs = children.call(hierarchy, data, depth),
  920. node = d3_layout_hierarchyInline ? data : {data: data};
  921. node.depth = depth;
  922. nodes.push(node);
  923. if (childs && (n = childs.length)) {
  924. var i = -1,
  925. n,
  926. c = node.children = [],
  927. v = 0,
  928. j = depth + 1;
  929. while (++i < n) {
  930. d = recurse(childs[i], j, nodes);
  931. d.parent = node;
  932. c.push(d);
  933. v += d.value;
  934. }
  935. if (sort) c.sort(sort);
  936. if (value) node.value = v;
  937. } else if (value) {
  938. node.value = +value.call(hierarchy, data, depth) || 0;
  939. }
  940. return node;
  941. }
  942. // Recursively re-evaluates the node value.
  943. function revalue(node, depth) {
  944. var children = node.children,
  945. v = 0;
  946. if (children && (n = children.length)) {
  947. var i = -1,
  948. n,
  949. j = depth + 1;
  950. while (++i < n) v += revalue(children[i], j);
  951. } else if (value) {
  952. v = +value.call(hierarchy, d3_layout_hierarchyInline ? node : node.data, depth) || 0;
  953. }
  954. if (value) node.value = v;
  955. return v;
  956. }
  957. function hierarchy(d) {
  958. var nodes = [];
  959. recurse(d, 0, nodes);
  960. return nodes;
  961. }
  962. hierarchy.sort = function(x) {
  963. if (!arguments.length) return sort;
  964. sort = x;
  965. return hierarchy;
  966. };
  967. hierarchy.children = function(x) {
  968. if (!arguments.length) return children;
  969. children = x;
  970. return hierarchy;
  971. };
  972. hierarchy.value = function(x) {
  973. if (!arguments.length) return value;
  974. value = x;
  975. return hierarchy;
  976. };
  977. // Re-evaluates the `value` property for the specified hierarchy.
  978. hierarchy.revalue = function(root) {
  979. revalue(root, 0);
  980. return root;
  981. };
  982. return hierarchy;
  983. };
  984. // A method assignment helper for hierarchy subclasses.
  985. function d3_layout_hierarchyRebind(object, hierarchy) {
  986. d3.rebind(object, hierarchy, "sort", "children", "value");
  987. // Add an alias for links, for convenience.
  988. object.links = d3_layout_hierarchyLinks;
  989. // If the new API is used, enabling inlining.
  990. object.nodes = function(d) {
  991. d3_layout_hierarchyInline = true;
  992. return (object.nodes = object)(d);
  993. };
  994. return object;
  995. }
  996. function d3_layout_hierarchyChildren(d) {
  997. return d.children;
  998. }
  999. function d3_layout_hierarchyValue(d) {
  1000. return d.value;
  1001. }
  1002. function d3_layout_hierarchySort(a, b) {
  1003. return b.value - a.value;
  1004. }
  1005. // Returns an array source+target objects for the specified nodes.
  1006. function d3_layout_hierarchyLinks(nodes) {
  1007. return d3.merge(nodes.map(function(parent) {
  1008. return (parent.children || []).map(function(child) {
  1009. return {source: parent, target: child};
  1010. });
  1011. }));
  1012. }
  1013. // For backwards-compatibility, don't enable inlining by default.
  1014. var d3_layout_hierarchyInline = false;
  1015. d3.layout.pack = function() {
  1016. var hierarchy = d3.layout.hierarchy().sort(d3_layout_packSort),
  1017. size = [1, 1];
  1018. function pack(d, i) {
  1019. var nodes = hierarchy.call(this, d, i),
  1020. root = nodes[0];
  1021. // Recursively compute the layout.
  1022. root.x = 0;
  1023. root.y = 0;
  1024. d3_layout_packTree(root);
  1025. // Scale the layout to fit the requested size.
  1026. var w = size[0],
  1027. h = size[1],
  1028. k = 1 / Math.max(2 * root.r / w, 2 * root.r / h);
  1029. d3_layout_packTransform(root, w / 2, h / 2, k);
  1030. return nodes;
  1031. }
  1032. pack.size = function(x) {
  1033. if (!arguments.length) return size;
  1034. size = x;
  1035. return pack;
  1036. };
  1037. return d3_layout_hierarchyRebind(pack, hierarchy);
  1038. };
  1039. function d3_layout_packSort(a, b) {
  1040. return a.value - b.value;
  1041. }
  1042. function d3_layout_packInsert(a, b) {
  1043. var c = a._pack_next;
  1044. a._pack_next = b;
  1045. b._pack_prev = a;
  1046. b._pack_next = c;
  1047. c._pack_prev = b;
  1048. }
  1049. function d3_layout_packSplice(a, b) {
  1050. a._pack_next = b;
  1051. b._pack_prev = a;
  1052. }
  1053. function d3_layout_packIntersects(a, b) {
  1054. var dx = b.x - a.x,
  1055. dy = b.y - a.y,
  1056. dr = a.r + b.r;
  1057. return dr * dr - dx * dx - dy * dy > .001; // within epsilon
  1058. }
  1059. function d3_layout_packCircle(nodes) {
  1060. var xMin = Infinity,
  1061. xMax = -Infinity,
  1062. yMin = Infinity,
  1063. yMax = -Infinity,
  1064. n = nodes.length,
  1065. a, b, c, j, k;
  1066. function bound(node) {
  1067. xMin = Math.min(node.x - node.r, xMin);
  1068. xMax = Math.max(node.x + node.r, xMax);
  1069. yMin = Math.min(node.y - node.r, yMin);
  1070. yMax = Math.max(node.y + node.r, yMax);
  1071. }
  1072. // Create node links.
  1073. nodes.forEach(d3_layout_packLink);
  1074. // Create first node.
  1075. a = nodes[0];
  1076. a.x = -a.r;
  1077. a.y = 0;
  1078. bound(a);
  1079. // Create second node.
  1080. if (n > 1) {
  1081. b = nodes[1];
  1082. b.x = b.r;
  1083. b.y = 0;
  1084. bound(b);
  1085. // Create third node and build chain.
  1086. if (n > 2) {
  1087. c = nodes[2];
  1088. d3_layout_packPlace(a, b, c);
  1089. bound(c);
  1090. d3_layout_packInsert(a, c);
  1091. a._pack_prev = c;
  1092. d3_layout_packInsert(c, b);
  1093. b = a._pack_next;
  1094. // Now iterate through the rest.
  1095. for (var i = 3; i < n; i++) {
  1096. d3_layout_packPlace(a, b, c = nodes[i]);
  1097. // Search for the closest intersection.
  1098. var isect = 0, s1 = 1, s2 = 1;
  1099. for (j = b._pack_next; j !== b; j = j._pack_next, s1++) {
  1100. if (d3_layout_packIntersects(j, c)) {
  1101. isect = 1;
  1102. break;
  1103. }
  1104. }
  1105. if (isect == 1) {
  1106. for (k = a._pack_prev; k !== j._pack_prev; k = k._pack_prev, s2++) {
  1107. if (d3_layout_packIntersects(k, c)) {
  1108. break;
  1109. }
  1110. }
  1111. }
  1112. // Update node chain.
  1113. if (isect) {
  1114. if (s1 < s2 || (s1 == s2 && b.r < a.r)) d3_layout_packSplice(a, b = j);
  1115. else d3_layout_packSplice(a = k, b);
  1116. i--;
  1117. } else {
  1118. d3_layout_packInsert(a, c);
  1119. b = c;
  1120. bound(c);
  1121. }
  1122. }
  1123. }
  1124. }
  1125. // Re-center the circles and return the encompassing radius.
  1126. var cx = (xMin + xMax) / 2,
  1127. cy = (yMin + yMax) / 2,
  1128. cr = 0;
  1129. for (var i = 0; i < n; i++) {
  1130. var node = nodes[i];
  1131. node.x -= cx;
  1132. node.y -= cy;
  1133. cr = Math.max(cr, node.r + Math.sqrt(node.x * node.x + node.y * node.y));
  1134. }
  1135. // Remove node links.
  1136. nodes.forEach(d3_layout_packUnlink);
  1137. return cr;
  1138. }
  1139. function d3_layout_packLink(node) {
  1140. node._pack_next = node._pack_prev = node;
  1141. }
  1142. function d3_layout_packUnlink(node) {
  1143. delete node._pack_next;
  1144. delete node._pack_prev;
  1145. }
  1146. function d3_layout_packTree(node) {
  1147. var children = node.children;
  1148. if (children && children.length) {
  1149. children.forEach(d3_layout_packTree);
  1150. node.r = d3_layout_packCircle(children);
  1151. } else {
  1152. node.r = Math.sqrt(node.value);
  1153. }
  1154. }
  1155. function d3_layout_packTransform(node, x, y, k) {
  1156. var children = node.children;
  1157. node.x = (x += k * node.x);
  1158. node.y = (y += k * node.y);
  1159. node.r *= k;
  1160. if (children) {
  1161. var i = -1, n = children.length;
  1162. while (++i < n) d3_layout_packTransform(children[i], x, y, k);
  1163. }
  1164. }
  1165. function d3_layout_packPlace(a, b, c) {
  1166. var db = a.r + c.r,
  1167. dx = b.x - a.x,
  1168. dy = b.y - a.y;
  1169. if (db && (dx || dy)) {
  1170. var da = b.r + c.r,
  1171. dc = Math.sqrt(dx * dx + dy * dy),
  1172. cos = Math.max(-1, Math.min(1, (db * db + dc * dc - da * da) / (2 * db * dc))),
  1173. theta = Math.acos(cos),
  1174. x = cos * (db /= dc),
  1175. y = Math.sin(theta) * db;
  1176. c.x = a.x + x * dx + y * dy;
  1177. c.y = a.y + x * dy - y * dx;
  1178. } else {
  1179. c.x = a.x + db;
  1180. c.y = a.y;
  1181. }
  1182. }
  1183. // Implements a hierarchical layout using the cluster (or dendogram) algorithm.
  1184. d3.layout.cluster = function() {
  1185. var hierarchy = d3.layout.hierarchy().sort(null).value(null),
  1186. separation = d3_layout_treeSeparation,
  1187. size = [1, 1]; // width, height
  1188. function cluster(d, i) {
  1189. var nodes = hierarchy.call(this, d, i),
  1190. root = nodes[0],
  1191. previousNode,
  1192. x = 0,
  1193. kx,
  1194. ky;
  1195. // First walk, computing the initial x & y values.
  1196. d3_layout_treeVisitAfter(root, function(node) {
  1197. var children = node.children;
  1198. if (children && children.length) {
  1199. node.x = d3_layout_clusterX(children);
  1200. node.y = d3_layout_clusterY(children);
  1201. } else {
  1202. node.x = previousNode ? x += separation(node, previousNode) : 0;
  1203. node.y = 0;
  1204. previousNode = node;
  1205. }
  1206. });
  1207. // Compute the left-most, right-most, and depth-most nodes for extents.
  1208. var left = d3_layout_clusterLeft(root),
  1209. right = d3_layout_clusterRight(root),
  1210. x0 = left.x - separation(left, right) / 2,
  1211. x1 = right.x + separation(right, left) / 2;
  1212. // Second walk, normalizing x & y to the desired size.
  1213. d3_layout_treeVisitAfter(root, function(node) {
  1214. node.x = (node.x - x0) / (x1 - x0) * size[0];
  1215. node.y = (1 - (root.y ? node.y / root.y : 1)) * size[1];
  1216. });
  1217. return nodes;
  1218. }
  1219. cluster.separation = function(x) {
  1220. if (!arguments.length) return separation;
  1221. separation = x;
  1222. return cluster;
  1223. };
  1224. cluster.size = function(x) {
  1225. if (!arguments.length) return size;
  1226. size = x;
  1227. return cluster;
  1228. };
  1229. return d3_layout_hierarchyRebind(cluster, hierarchy);
  1230. };
  1231. function d3_layout_clusterY(children) {
  1232. return 1 + d3.max(children, function(child) {
  1233. return child.y;
  1234. });
  1235. }
  1236. function d3_layout_clusterX(children) {
  1237. return children.reduce(function(x, child) {
  1238. return x + child.x;
  1239. }, 0) / children.length;
  1240. }
  1241. function d3_layout_clusterLeft(node) {
  1242. var children = node.children;
  1243. return children && children.length ? d3_layout_clusterLeft(children[0]) : node;
  1244. }
  1245. function d3_layout_clusterRight(node) {
  1246. var children = node.children, n;
  1247. return children && (n = children.length) ? d3_layout_clusterRight(children[n - 1]) : node;
  1248. }
  1249. // Node-link tree diagram using the Reingold-Tilford "tidy" algorithm
  1250. d3.layout.tree = function() {
  1251. var hierarchy = d3.layout.hierarchy().sort(null).value(null),
  1252. separation = d3_layout_treeSeparation,
  1253. size = [1, 1]; // width, height
  1254. function tree(d, i) {
  1255. var nodes = hierarchy.call(this, d, i),
  1256. root = nodes[0];
  1257. function firstWalk(node, previousSibling) {
  1258. var children = node.children,
  1259. layout = node._tree;
  1260. if (children && (n = children.length)) {
  1261. var n,
  1262. firstChild = children[0],
  1263. previousChild,
  1264. ancestor = firstChild,
  1265. child,
  1266. i = -1;
  1267. while (++i < n) {
  1268. child = children[i];
  1269. firstWalk(child, previousChild);
  1270. ancestor = apportion(child, previousChild, ancestor);
  1271. previousChild = child;
  1272. }
  1273. d3_layout_treeShift(node);
  1274. var midpoint = .5 * (firstChild._tree.prelim + child._tree.prelim);
  1275. if (previousSibling) {
  1276. layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling);
  1277. layout.mod = layout.prelim - midpoint;
  1278. } else {
  1279. layout.prelim = midpoint;
  1280. }
  1281. } else {
  1282. if (previousSibling) {
  1283. layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling);
  1284. }
  1285. }
  1286. }
  1287. function secondWalk(node, x) {
  1288. node.x = node._tree.prelim + x;
  1289. var children = node.children;
  1290. if (children && (n = children.length)) {
  1291. var i = -1,
  1292. n;
  1293. x += node._tree.mod;
  1294. while (++i < n) {
  1295. secondWalk(children[i], x);
  1296. }
  1297. }
  1298. }
  1299. function apportion(node, previousSibling, ancestor) {
  1300. if (previousSibling) {
  1301. var vip = node,
  1302. vop = node,
  1303. vim = previousSibling,
  1304. vom = node.parent.children[0],
  1305. sip = vip._tree.mod,
  1306. sop = vop._tree.mod,
  1307. sim = vim._tree.mod,
  1308. som = vom._tree.mod,
  1309. shift;
  1310. while (vim = d3_layout_treeRight(vim), vip = d3_layout_treeLeft(vip), vim && vip) {
  1311. vom = d3_layout_treeLeft(vom);
  1312. vop = d3_layout_treeRight(vop);
  1313. vop._tree.ancestor = node;
  1314. shift = vim._tree.prelim + sim - vip._tree.prelim - sip + separation(vim, vip);
  1315. if (shift > 0) {
  1316. d3_layout_treeMove(d3_layout_treeAncestor(vim, node, ancestor), node, shift);
  1317. sip += shift;
  1318. sop += shift;
  1319. }
  1320. sim += vim._tree.mod;
  1321. sip += vip._tree.mod;
  1322. som += vom._tree.mod;
  1323. sop += vop._tree.mod;
  1324. }
  1325. if (vim && !d3_layout_treeRight(vop)) {
  1326. vop._tree.thread = vim;
  1327. vop._tree.mod += sim - sop;
  1328. }
  1329. if (vip && !d3_layout_treeLeft(vom)) {
  1330. vom._tree.thread = vip;
  1331. vom._tree.mod += sip - som;
  1332. ancestor = node;
  1333. }
  1334. }
  1335. return ancestor;
  1336. }
  1337. // Initialize temporary layout variables.
  1338. d3_layout_treeVisitAfter(root, function(node, previousSibling) {
  1339. node._tree = {
  1340. ancestor: node,
  1341. prelim: 0,
  1342. mod: 0,
  1343. change: 0,
  1344. shift: 0,
  1345. number: previousSibling ? previousSibling._tree.number + 1 : 0
  1346. };
  1347. });
  1348. // Compute the layout using Buchheim et al.'s algorithm.
  1349. firstWalk(root);
  1350. secondWalk(root, -root._tree.prelim);
  1351. // Compute the left-most, right-most, and depth-most nodes for extents.
  1352. var left = d3_layout_treeSearch(root, d3_layout_treeLeftmost),
  1353. right = d3_layout_treeSearch(root, d3_layout_treeRightmost),
  1354. deep = d3_layout_treeSearch(root, d3_layout_treeDeepest),
  1355. x0 = left.x - separation(left, right) / 2,
  1356. x1 = right.x + separation(right, left) / 2,
  1357. y1 = deep.depth || 1;
  1358. // Clear temporary layout variables; transform x and y.
  1359. d3_layout_treeVisitAfter(root, function(node) {
  1360. node.x = (node.x - x0) / (x1 - x0) * size[0];
  1361. node.y = node.depth / y1 * size[1];
  1362. delete node._tree;
  1363. });
  1364. return nodes;
  1365. }
  1366. tree.separation = function(x) {
  1367. if (!arguments.length) return separation;
  1368. separation = x;
  1369. return tree;
  1370. };
  1371. tree.size = function(x) {
  1372. if (!arguments.length) return size;
  1373. size = x;
  1374. return tree;
  1375. };
  1376. return d3_layout_hierarchyRebind(tree, hierarchy);
  1377. };
  1378. function d3_layout_treeSeparation(a, b) {
  1379. return a.parent == b.parent ? 1 : 2;
  1380. }
  1381. // function d3_layout_treeSeparationRadial(a, b) {
  1382. // return (a.parent == b.parent ? 1 : 2) / a.depth;
  1383. // }
  1384. function d3_layout_treeLeft(node) {
  1385. var children = node.children;
  1386. return children && children.length ? children[0] : node._tree.thread;
  1387. }
  1388. function d3_layout_treeRight(node) {
  1389. var children = node.children,
  1390. n;
  1391. return children && (n = children.length) ? children[n - 1] : node._tree.thread;
  1392. }
  1393. function d3_layout_treeSearch(node, compare) {
  1394. var children = node.children;
  1395. if (children && (n = children.length)) {
  1396. var child,
  1397. n,
  1398. i = -1;
  1399. while (++i < n) {
  1400. if (compare(child = d3_layout_treeSearch(children[i], compare), node) > 0) {
  1401. node = child;
  1402. }
  1403. }
  1404. }
  1405. return node;
  1406. }
  1407. function d3_layout_treeRightmost(a, b) {
  1408. return a.x - b.x;
  1409. }
  1410. function d3_layout_treeLeftmost(a, b) {
  1411. return b.x - a.x;
  1412. }
  1413. function d3_layout_treeDeepest(a, b) {
  1414. return a.depth - b.depth;
  1415. }
  1416. function d3_layout_treeVisitAfter(node, callback) {
  1417. function visit(node, previousSibling) {
  1418. var children = node.children;
  1419. if (children && (n = children.length)) {
  1420. var child,
  1421. previousChild = null,
  1422. i = -1,
  1423. n;
  1424. while (++i < n) {
  1425. child = children[i];
  1426. visit(child, previousChild);
  1427. previousChild = child;
  1428. }
  1429. }
  1430. callback(node, previousSibling);
  1431. }
  1432. visit(node, null);
  1433. }
  1434. function d3_layout_treeShift(node) {
  1435. var shift = 0,
  1436. change = 0,
  1437. children = node.children,
  1438. i = children.length,
  1439. child;
  1440. while (--i >= 0) {
  1441. child = children[i]._tree;
  1442. child.prelim += shift;
  1443. child.mod += shift;
  1444. shift += child.shift + (change += child.change);
  1445. }
  1446. }
  1447. function d3_layout_treeMove(ancestor, node, shift) {
  1448. ancestor = ancestor._tree;
  1449. node = node._tree;
  1450. var change = shift / (node.number - ancestor.number);
  1451. ancestor.change += change;
  1452. node.change -= change;
  1453. node.shift += shift;
  1454. node.prelim += shift;
  1455. node.mod += shift;
  1456. }
  1457. function d3_layout_treeAncestor(vim, node, ancestor) {
  1458. return vim._tree.ancestor.parent == node.parent
  1459. ? vim._tree.ancestor
  1460. : ancestor;
  1461. }
  1462. // Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk
  1463. // Modified to support a target aspect ratio by Jeff Heer
  1464. d3.layout.treemap = function() {
  1465. var hierarchy = d3.layout.hierarchy(),
  1466. round = Math.round,
  1467. size = [1, 1], // width, height
  1468. padding = null,
  1469. pad = d3_layout_treemapPadNull,
  1470. sticky = false,
  1471. stickies,
  1472. ratio = 0.5 * (1 + Math.sqrt(5)); // golden ratio
  1473. // Compute the area for each child based on value & scale.
  1474. function scale(children, k) {
  1475. var i = -1,
  1476. n = children.length,
  1477. child,
  1478. area;
  1479. while (++i < n) {
  1480. area = (child = children[i]).value * (k < 0 ? 0 : k);
  1481. child.area = isNaN(area) || area <= 0 ? 0 : area;
  1482. }
  1483. }
  1484. // Recursively arranges the specified node's children into squarified rows.
  1485. function squarify(node) {
  1486. var children = node.children;
  1487. if (children && children.length) {
  1488. var rect = pad(node),
  1489. row = [],
  1490. remaining = children.slice(), // copy-on-write
  1491. child,
  1492. best = Infinity, // the best row score so far
  1493. score, // the current row score
  1494. u = Math.min(rect.dx, rect.dy), // initial orientation
  1495. n;
  1496. scale(remaining, rect.dx * rect.dy / node.value);
  1497. row.area = 0;
  1498. while ((n = remaining.length) > 0) {
  1499. row.push(child = remaining[n - 1]);
  1500. row.area += child.area;
  1501. if ((score = worst(row, u)) <= best) { // continue with this orientation
  1502. remaining.pop();
  1503. best = score;
  1504. } else { // abort, and try a different orientation
  1505. row.area -= row.pop().area;
  1506. position(row, u, rect, false);
  1507. u = Math.min(rect.dx, rect.dy);
  1508. row.length = row.area = 0;
  1509. best = Infinity;
  1510. }
  1511. }
  1512. if (row.length) {
  1513. position(row, u, rect, true);
  1514. row.length = row.area = 0;
  1515. }
  1516. children.forEach(squarify);
  1517. }
  1518. }
  1519. // Recursively resizes the specified node's children into existing rows.
  1520. // Preserves the existing layout!
  1521. function stickify(node) {
  1522. var children = node.children;
  1523. if (children && children.length) {
  1524. var rect = pad(node),
  1525. remaining = children.slice(), // copy-on-write
  1526. child,
  1527. row = [];
  1528. scale(remaining, rect.dx * rect.dy / node.value);
  1529. row.area = 0;
  1530. while (child = remaining.pop()) {
  1531. row.push(child);
  1532. row.area += child.area;
  1533. if (child.z != null) {
  1534. position(row, child.z ? rect.dx : rect.dy, rect, !remaining.length);
  1535. row.length = row.area = 0;
  1536. }
  1537. }
  1538. children.forEach(stickify);
  1539. }
  1540. }
  1541. // Computes the score for the specified row, as the worst aspect ratio.
  1542. function worst(row, u) {
  1543. var s = row.area,
  1544. r,
  1545. rmax = 0,
  1546. rmin = Infinity,
  1547. i = -1,
  1548. n = row.length;
  1549. while (++i < n) {
  1550. if (!(r = row[i].area)) continue;
  1551. if (r < rmin) rmin = r;
  1552. if (r > rmax) rmax = r;
  1553. }
  1554. s *= s;
  1555. u *= u;
  1556. return s
  1557. ? Math.max((u * rmax * ratio) / s, s / (u * rmin * ratio))
  1558. : Infinity;
  1559. }
  1560. // Positions the specified row of nodes. Modifies `rect`.
  1561. function position(row, u, rect, flush) {
  1562. var i = -1,
  1563. n = row.length,
  1564. x = rect.x,
  1565. y = rect.y,
  1566. v = u ? round(row.area / u) : 0,
  1567. o;
  1568. if (u == rect.dx) { // horizontal subdivision
  1569. if (flush || v > rect.dy) v = rect.dy; // over+underflow
  1570. while (++i < n) {
  1571. o = row[i];
  1572. o.x = x;
  1573. o.y = y;
  1574. o.dy = v;
  1575. x += o.dx = Math.min(rect.x + rect.dx - x, v ? round(o.area / v) : 0);
  1576. }
  1577. o.z = true;
  1578. o.dx += rect.x + rect.dx - x; // rounding error
  1579. rect.y += v;
  1580. rect.dy -= v;
  1581. } else { // vertical subdivision
  1582. if (flush || v > rect.dx) v = rect.dx; // over+underflow
  1583. while (++i < n) {
  1584. o = row[i];
  1585. o.x = x;
  1586. o.y = y;
  1587. o.dx = v;
  1588. y += o.dy = Math.min(rect.y + rect.dy - y, v ? round(o.area / v) : 0);
  1589. }
  1590. o.z = false;
  1591. o.dy += rect.y + rect.dy - y; // rounding error
  1592. rect.x += v;
  1593. rect.dx -= v;
  1594. }
  1595. }
  1596. function treemap(d) {
  1597. var nodes = stickies || hierarchy(d),
  1598. root = nodes[0];
  1599. root.x = 0;
  1600. root.y = 0;
  1601. root.dx = size[0];
  1602. root.dy = size[1];
  1603. if (stickies) hierarchy.revalue(root);
  1604. scale([root], root.dx * root.dy / root.value);
  1605. (stickies ? stickify : squarify)(root);
  1606. if (sticky) stickies = nodes;
  1607. return nodes;
  1608. }
  1609. treemap.size = function(x) {
  1610. if (!arguments.length) return size;
  1611. size = x;
  1612. return treemap;
  1613. };
  1614. treemap.padding = function(x) {
  1615. if (!arguments.length) return padding;
  1616. function padFunction(node) {
  1617. var p = x.call(treemap, node, node.depth);
  1618. return p == null
  1619. ? d3_layout_treemapPadNull(node)
  1620. : d3_layout_treemapPad(node, typeof p === "number" ? [p, p, p, p] : p);
  1621. }
  1622. function padConstant(node) {
  1623. return d3_layout_treemapPad(node, x);
  1624. }
  1625. var type;
  1626. pad = (padding = x) == null ? d3_layout_treemapPadNull
  1627. : (type = typeof x) === "function" ? padFunction
  1628. : type === "number" ? (x = [x, x, x, x], padConstant)
  1629. : padConstant;
  1630. return treemap;
  1631. };
  1632. treemap.round = function(x) {
  1633. if (!arguments.length) return round != Number;
  1634. round = x ? Math.round : Number;
  1635. return treemap;
  1636. };
  1637. treemap.sticky = function(x) {
  1638. if (!arguments.length) return sticky;
  1639. sticky = x;
  1640. stickies = null;
  1641. return treemap;
  1642. };
  1643. treemap.ratio = function(x) {
  1644. if (!arguments.length) return ratio;
  1645. ratio = x;
  1646. return treemap;
  1647. };
  1648. return d3_layout_hierarchyRebind(treemap, hierarchy);
  1649. };
  1650. function d3_layout_treemapPadNull(node) {
  1651. return {x: node.x, y: node.y, dx: node.dx, dy: node.dy};
  1652. }
  1653. function d3_layout_treemapPad(node, padding) {
  1654. var x = node.x + padding[3],
  1655. y = node.y + padding[0],
  1656. dx = node.dx - padding[1] - padding[3],
  1657. dy = node.dy - padding[0] - padding[2];
  1658. if (dx < 0) { x += dx / 2; dx = 0; }
  1659. if (dy < 0) { y += dy / 2; dy = 0; }
  1660. return {x: x, y: y, dx: dx, dy: dy};
  1661. }
  1662. })();