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