Icicle.js 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
  1. // TODO share code with Treemap
  2. // TODO vertical / horizontal orientation?
  3. /**
  4. * Returns a new icicle tree layout.
  5. *
  6. * @class A tree layout in the form of an icicle. <img src="../icicle.png"
  7. * width="160" height="160" align="right"> The first row corresponds to the root
  8. * of the tree; subsequent rows correspond to each tier. Rows are subdivided
  9. * into cells based on the size of nodes, per {@link #size}. Within a row, cells
  10. * are sorted by size.
  11. *
  12. * <p>This tree layout is intended to be extended (see {@link pv.Mark#extend})
  13. * by a {@link pv.Bar}. The data property returns an array of nodes for use by
  14. * other property functions. The following node attributes are supported:
  15. *
  16. * <ul>
  17. * <li><tt>left</tt> - the cell left position.
  18. * <li><tt>top</tt> - the cell top position.
  19. * <li><tt>width</tt> - the cell width.
  20. * <li><tt>height</tt> - the cell height.
  21. * <li><tt>depth</tt> - the node depth (tier; the root is 0).
  22. * <li><tt>keys</tt> - an array of string keys for the node.
  23. * <li><tt>size</tt> - the aggregate node size.
  24. * <li><tt>children</tt> - child nodes, if any.
  25. * <li><tt>data</tt> - the associated tree element, for leaf nodes.
  26. * </ul>
  27. *
  28. * To produce a default icicle layout, say:
  29. *
  30. * <pre>.add(pv.Bar)
  31. * .extend(pv.Layout.icicle(tree))</pre>
  32. *
  33. * To customize the tree to highlight leaf nodes bigger than 10,000 (1E4), you
  34. * might say:
  35. *
  36. * <pre>.add(pv.Bar)
  37. * .extend(pv.Layout.icicle(tree))
  38. * .fillStyle(function(n) n.data > 1e4 ? "#ff0" : "#fff")</pre>
  39. *
  40. * The format of the <tt>tree</tt> argument is any hierarchical object whose
  41. * leaf nodes are numbers corresponding to their size. For an example, and
  42. * information on how to convert tabular data into such a tree, see
  43. * {@link pv.Tree}. If the leaf nodes are not numbers, a {@link #size} function
  44. * can be specified to override how the tree is interpreted. This size function
  45. * can also be used to transform the data.
  46. *
  47. * <p>By default, the icicle fills the full width and height of the parent
  48. * panel. An optional root key can be specified using {@link #root} for
  49. * convenience.
  50. *
  51. * @param tree a tree (an object) who leaf attributes have sizes.
  52. * @returns {pv.Layout.icicle} a tree layout.
  53. */
  54. pv.Layout.icicle = function(tree) {
  55. var keys = [], sizeof = Number;
  56. /** @private */
  57. function accumulate(map) {
  58. var node = {size: 0, children: [], keys: keys.slice()};
  59. for (var key in map) {
  60. var child = map[key], size = sizeof(child);
  61. keys.push(key);
  62. if (isNaN(size)) {
  63. child = accumulate(child);
  64. } else {
  65. child = {size: size, data: child, keys: keys.slice()};
  66. }
  67. node.children.push(child);
  68. node.size += child.size;
  69. keys.pop();
  70. }
  71. node.children.sort(function(a, b) { return b.size - a.size; });
  72. return node;
  73. }
  74. /** @private */
  75. function scale(node, k) {
  76. node.size *= k;
  77. if (node.children) {
  78. for (var i = 0; i < node.children.length; i++) {
  79. scale(node.children[i], k);
  80. }
  81. }
  82. }
  83. /** @private */
  84. function depth(node, i) {
  85. i = i ? (i + 1) : 1;
  86. return node.children
  87. ? pv.max(node.children, function(n) { return depth(n, i); })
  88. : i;
  89. }
  90. /** @private */
  91. function layout(node) {
  92. if (node.children) {
  93. icify(node);
  94. for (var i = 0; i < node.children.length; i++) {
  95. layout(node.children[i]);
  96. }
  97. }
  98. }
  99. /** @private */
  100. function icify(node) {
  101. var left = node.left;
  102. for (var i = 0; i < node.children.length; i++) {
  103. var child = node.children[i], width = (child.size / node.size) * node.width;
  104. child.left = left;
  105. child.top = node.top + node.height;
  106. child.width = width;
  107. child.height = node.height;
  108. child.depth = node.depth + 1;
  109. left += width;
  110. if (child.children) {
  111. icify(child);
  112. }
  113. }
  114. }
  115. /** @private */
  116. function flatten(node, array) {
  117. if (node.children) {
  118. for (var i = 0; i < node.children.length; i++) {
  119. flatten(node.children[i], array);
  120. }
  121. }
  122. array.push(node)
  123. return array;
  124. }
  125. /** @private */
  126. function data() {
  127. var root = accumulate(tree);
  128. root.top = 0;
  129. root.left = 0;
  130. root.width = this.parent.width();
  131. root.height = this.parent.height() / depth(root);
  132. root.depth = 0;
  133. layout(root);
  134. return flatten(root, []).reverse();
  135. }
  136. /* A dummy mark, like an anchor, which the caller extends. */
  137. var mark = new pv.Mark()
  138. .data(data)
  139. .left(function(n) { return n.left; })
  140. .top(function(n) { return n.top; })
  141. .width(function(n) { return n.width; })
  142. .height(function(n) { return n.height; });
  143. /**
  144. * Specifies the root key; optional. The root key is prepended to the
  145. * <tt>keys</tt> attribute for all generated nodes. This method is provided
  146. * for convenience and does not affect layout.
  147. *
  148. * @param {string} v the root key.
  149. * @function
  150. * @name pv.Layout.icicle.prototype.root
  151. * @returns {pv.Layout.icicle} this.
  152. */
  153. mark.root = function(v) {
  154. keys = [v];
  155. return this;
  156. };
  157. /**
  158. * Specifies the sizing function. By default, the sizing function is
  159. * <tt>Number</tt>. The sizing function is invoked for each node in the tree
  160. * (passed to the constructor): the sizing function must return
  161. * <tt>undefined</tt> or <tt>NaN</tt> for internal nodes, and a number for
  162. * leaf nodes. The aggregate sizes of internal nodes will be automatically
  163. * computed by the layout.
  164. *
  165. * <p>For example, if the tree data structure represents a file system, with
  166. * files as leaf nodes, and each file has a <tt>bytes</tt> attribute, you can
  167. * specify a size function as:
  168. *
  169. * <pre>.size(function(d) d.bytes)</pre>
  170. *
  171. * This function will return <tt>undefined</tt> for internal nodes (since
  172. * these do not have a <tt>bytes</tt> attribute), and a number for leaf nodes.
  173. *
  174. * <p>Note that the built-in <tt>Math.sqrt</tt> and <tt>Math.log</tt> methods
  175. * can also be used as sizing functions. These function similarly to
  176. * <tt>Number</tt>, except perform a root and log scale, respectively.
  177. *
  178. * @param {function} f the new sizing function.
  179. * @function
  180. * @name pv.Layout.icicle.prototype.size
  181. * @returns {pv.Layout.icicle} this.
  182. */
  183. mark.size = function(f) {
  184. sizeof = f;
  185. return this;
  186. };
  187. return mark;
  188. };