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