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