1 /** 2 * Constructs a new, empty treemap layout. Layouts are not typically 3 * constructed directly; instead, they are added to an existing panel via 4 * {@link pv.Mark#add}. 5 * 6 * @class Implements a space-filling rectangular layout, with the hierarchy 7 * represented via containment. Treemaps represent nodes as boxes, with child 8 * nodes placed within parent boxes. The size of each box is proportional to the 9 * size of the node in the tree. This particular algorithm is taken from Bruls, 10 * D.M., C. Huizing, and J.J. van Wijk, <a 11 * href="http://www.win.tue.nl/~vanwijk/stm.pdf">"Squarified Treemaps"</a> in 12 * <i>Data Visualization 2000, Proceedings of the Joint Eurographics and IEEE 13 * TCVG Sumposium on Visualization</i>, 2000, pp. 33-42. 14 * 15 * <p>The meaning of the exported mark prototypes changes slightly in the 16 * space-filling implementation:<ul> 17 * 18 * <li><tt>node</tt> - for rendering nodes; typically a {@link pv.Bar}. The node 19 * data is populated with <tt>dx</tt> and <tt>dy</tt> attributes, in addition to 20 * the standard <tt>x</tt> and <tt>y</tt> position attributes. 21 * 22 * <p><li><tt>leaf</tt> - for rendering leaf nodes only, with no fill or stroke 23 * style by default; typically a {@link pv.Panel} or another layout! 24 * 25 * <p><li><tt>link</tt> - unsupported; undefined. Links are encoded implicitly 26 * in the arrangement of the space-filling nodes. 27 * 28 * <p><li><tt>label</tt> - for rendering node labels; typically a 29 * {@link pv.Label}. 30 * 31 * </ul>For more details on how to use this layout, see 32 * {@link pv.Layout.Hierarchy}. 33 * 34 * @extends pv.Layout.Hierarchy 35 */ 36 pv.Layout.Treemap = function() { 37 pv.Layout.Hierarchy.call(this); 38 39 this.node 40 .strokeStyle("#fff") 41 .fillStyle("rgba(31, 119, 180, .25)") 42 .width(function(n) { return n.dx; }) 43 .height(function(n) { return n.dy; }); 44 45 this.label 46 .visible(function(n) { return !n.firstChild; }) 47 .left(function(n) { return n.x + (n.dx / 2); }) 48 .top(function(n) { return n.y + (n.dy / 2); }) 49 .textAlign("center") 50 .textAngle(function(n) { return n.dx > n.dy ? 0 : -Math.PI / 2; }); 51 52 (this.leaf = new pv.Mark() 53 .extend(this.node) 54 .fillStyle(null) 55 .strokeStyle(null) 56 .visible(function(n) { return !n.firstChild; })).parent = this; 57 58 /* Hide unsupported link. */ 59 delete this.link; 60 }; 61 62 pv.Layout.Treemap.prototype = pv.extend(pv.Layout.Hierarchy) 63 .property("round", Boolean) 64 .property("paddingLeft", Number) 65 .property("paddingRight", Number) 66 .property("paddingTop", Number) 67 .property("paddingBottom", Number) 68 .property("mode", String) 69 .property("order", String); 70 71 /** 72 * Default propertiess for treemap layouts. The default mode is "squarify" and 73 * the default order is "ascending". 74 * 75 * @type pv.Layout.Treemap 76 */ 77 pv.Layout.Treemap.prototype.defaults = new pv.Layout.Treemap() 78 .extend(pv.Layout.Hierarchy.prototype.defaults) 79 .mode("squarify") // squarify, slice-and-dice, slice, dice 80 .order("ascending"); // ascending, descending, reverse, null 81 82 /** 83 * Whether node sizes should be rounded to integer values. This has a similar 84 * effect to setting <tt>antialias(false)</tt> for node values, but allows the 85 * treemap algorithm to accumulate error related to pixel rounding. 86 * 87 * @type boolean 88 * @name pv.Layout.Treemap.prototype.round 89 */ 90 91 /** 92 * The left inset between parent add child in pixels. Defaults to 0. 93 * 94 * @type number 95 * @name pv.Layout.Treemap.prototype.paddingLeft 96 * @see #padding 97 */ 98 99 /** 100 * The right inset between parent add child in pixels. Defaults to 0. 101 * 102 * @type number 103 * @name pv.Layout.Treemap.prototype.paddingRight 104 * @see #padding 105 */ 106 107 /** 108 * The top inset between parent and child in pixels. Defaults to 0. 109 * 110 * @type number 111 * @name pv.Layout.Treemap.prototype.paddingTop 112 * @see #padding 113 */ 114 115 /** 116 * The bottom inset between parent and child in pixels. Defaults to 0. 117 * 118 * @type number 119 * @name pv.Layout.Treemap.prototype.paddingBottom 120 * @see #padding 121 */ 122 123 /** 124 * The treemap algorithm. The default value is "squarify". The "slice-and-dice" 125 * algorithm may also be used, which alternates between horizontal and vertical 126 * slices for different depths. In addition, the "slice" and "dice" algorithms 127 * may be specified explicitly to control whether horizontal or vertical slices 128 * are used, which may be useful for nested treemap layouts. 129 * 130 * @type string 131 * @name pv.Layout.Treemap.prototype.mode 132 * @see <a 133 * href="ftp://ftp.cs.umd.edu/pub/hcil/Reports-Abstracts-Bibliography/2001-06html/2001-06.pdf" 134 * >"Ordered Treemap Layouts"</a> by B. Shneiderman & M. Wattenberg, IEEE 135 * InfoVis 2001. 136 */ 137 138 /** 139 * The sibling node order. A <tt>null</tt> value means to use the sibling order 140 * specified by the nodes property as-is; "reverse" will reverse the given 141 * order. The default value "ascending" will sort siblings in ascending order of 142 * size, while "descending" will do the reverse. For sorting based on data 143 * attributes other than size, use the default <tt>null</tt> for the order 144 * property, and sort the nodes beforehand using the {@link pv.Dom} operator. 145 * 146 * @type string 147 * @name pv.Layout.Treemap.prototype.order 148 */ 149 150 /** 151 * Alias for setting the left, right, top and bottom padding properties 152 * simultaneously. 153 * 154 * @see #paddingLeft 155 * @see #paddingRight 156 * @see #paddingTop 157 * @see #paddingBottom 158 * @returns {pv.Layout.Treemap} this. 159 */ 160 pv.Layout.Treemap.prototype.padding = function(n) { 161 return this.paddingLeft(n).paddingRight(n).paddingTop(n).paddingBottom(n); 162 }; 163 164 /** @private The default size function. */ 165 pv.Layout.Treemap.prototype.$size = function(d) { 166 return Number(d.nodeValue); 167 }; 168 169 /** 170 * Specifies the sizing function. By default, the size function uses the 171 * <tt>nodeValue</tt> attribute of nodes as a numeric value: <tt>function(d) 172 * Number(d.nodeValue)</tt>. 173 * 174 * <p>The sizing function is invoked for each leaf node in the tree, per the 175 * <tt>nodes</tt> property. For example, if the tree data structure represents a 176 * file system, with files as leaf nodes, and each file has a <tt>bytes</tt> 177 * attribute, you can specify a size function as: 178 * 179 * <pre> .size(function(d) d.bytes)</pre> 180 * 181 * @param {function} f the new sizing function. 182 * @returns {pv.Layout.Treemap} this. 183 */ 184 pv.Layout.Treemap.prototype.size = function(f) { 185 this.$size = pv.functor(f); 186 return this; 187 }; 188 189 /** @private */ 190 pv.Layout.Treemap.prototype.buildImplied = function(s) { 191 if (pv.Layout.Hierarchy.prototype.buildImplied.call(this, s)) return; 192 193 var that = this, 194 nodes = s.nodes, 195 root = nodes[0], 196 stack = pv.Mark.stack, 197 left = s.paddingLeft, 198 right = s.paddingRight, 199 top = s.paddingTop, 200 bottom = s.paddingBottom, 201 /** @ignore */ size = function(n) { return n.size; }, 202 round = s.round ? Math.round : Number, 203 mode = s.mode; 204 205 /** @private */ 206 function slice(row, sum, horizontal, x, y, w, h) { 207 for (var i = 0, d = 0; i < row.length; i++) { 208 var n = row[i]; 209 if (horizontal) { 210 n.x = x + d; 211 n.y = y; 212 d += n.dx = round(w * n.size / sum); 213 n.dy = h; 214 } else { 215 n.x = x; 216 n.y = y + d; 217 n.dx = w; 218 d += n.dy = round(h * n.size / sum); 219 } 220 } 221 if (n) { // correct on-axis rounding error 222 if (horizontal) { 223 n.dx += w - d; 224 } else { 225 n.dy += h - d; 226 } 227 } 228 } 229 230 /** @private */ 231 function ratio(row, l) { 232 var rmax = -Infinity, rmin = Infinity, s = 0; 233 for (var i = 0; i < row.length; i++) { 234 var r = row[i].size; 235 if (r < rmin) rmin = r; 236 if (r > rmax) rmax = r; 237 s += r; 238 } 239 s = s * s; 240 l = l * l; 241 return Math.max(l * rmax / s, s / (l * rmin)); 242 } 243 244 /** @private */ 245 function layout(n, i) { 246 var x = n.x + left, 247 y = n.y + top, 248 w = n.dx - left - right, 249 h = n.dy - top - bottom; 250 251 /* Assume squarify by default. */ 252 if (mode != "squarify") { 253 slice(n.childNodes, n.size, 254 mode == "slice" ? true 255 : mode == "dice" ? false 256 : i & 1, x, y, w, h); 257 return; 258 } 259 260 var row = [], 261 mink = Infinity, 262 l = Math.min(w, h), 263 k = w * h / n.size; 264 265 /* Abort if the size is nonpositive. */ 266 if (n.size <= 0) return; 267 268 /* Scale the sizes to fill the current subregion. */ 269 n.visitBefore(function(n) { n.size *= k; }); 270 271 /** @private Position the specified nodes along one dimension. */ 272 function position(row) { 273 var horizontal = w == l, 274 sum = pv.sum(row, size), 275 r = l ? round(sum / l) : 0; 276 slice(row, sum, horizontal, x, y, horizontal ? w : r, horizontal ? r : h); 277 if (horizontal) { 278 y += r; 279 h -= r; 280 } else { 281 x += r; 282 w -= r; 283 } 284 l = Math.min(w, h); 285 return horizontal; 286 } 287 288 var children = n.childNodes.slice(); // copy 289 while (children.length) { 290 var child = children[children.length - 1]; 291 if (!child.size) { 292 children.pop(); 293 continue; 294 } 295 row.push(child); 296 297 var k = ratio(row, l); 298 if (k <= mink) { 299 children.pop(); 300 mink = k; 301 } else { 302 row.pop(); 303 position(row); 304 row.length = 0; 305 mink = Infinity; 306 } 307 } 308 309 /* correct off-axis rounding error */ 310 if (position(row)) for (var i = 0; i < row.length; i++) { 311 row[i].dy += h; 312 } else for (var i = 0; i < row.length; i++) { 313 row[i].dx += w; 314 } 315 } 316 317 /* Recursively compute the node depth and size. */ 318 stack.unshift(null); 319 root.visitAfter(function(n, i) { 320 n.depth = i; 321 n.x = n.y = n.dx = n.dy = 0; 322 n.size = n.firstChild 323 ? pv.sum(n.childNodes, function(n) { return n.size; }) 324 : that.$size.apply(that, (stack[0] = n, stack)); 325 }); 326 stack.shift(); 327 328 /* Sort. */ 329 switch (s.order) { 330 case "ascending": { 331 root.sort(function(a, b) { return a.size - b.size; }); 332 break; 333 } 334 case "descending": { 335 root.sort(function(a, b) { return b.size - a.size; }); 336 break; 337 } 338 case "reverse": root.reverse(); break; 339 } 340 341 /* Recursively compute the layout. */ 342 root.x = 0; 343 root.y = 0; 344 root.dx = s.width; 345 root.dy = s.height; 346 root.visitBefore(layout); 347 }; 348