1/*
2 * Copyright (C) 2011 Google Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 *     * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *     * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 *     * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31// Size of border around nodes.
32// We could support arbitrary borders using getComputedStyle(), but I am
33// skeptical the extra complexity (and performance hit) is worth it.
34var kBorderWidth = 1;
35
36// Padding around contents.
37// TODO: do this with a nested div to allow it to be CSS-styleable.
38var kPadding = 4;
39
40var focused = null;
41
42// Callback for embedding page to update after a focus.
43function handleFocus(tree) {}
44
45function focus(tree) {
46  focused = tree;
47
48  // Hide all visible siblings of all our ancestors by lowering them.
49  var level = 0;
50  var root = tree;
51  while (root.parent) {
52    root = root.parent;
53    level += 1;
54    for (var i = 0, sibling; sibling = root.children[i]; ++i) {
55      if (sibling.dom)
56        sibling.dom.style.zIndex = 0;
57    }
58  }
59  var width = root.dom.offsetWidth;
60  var height = root.dom.offsetHeight;
61  // Unhide (raise) and maximize us and our ancestors.
62  for (var t = tree; t.parent; t = t.parent) {
63    // Shift off by border so we don't get nested borders.
64    // TODO: actually make nested borders work (need to adjust width/height).
65    position(t.dom, -kBorderWidth, -kBorderWidth, width, height);
66    t.dom.style.zIndex = 1;
67  }
68  // And layout into the topmost box.
69  layout(tree, level, width, height);
70  handleFocus(tree);
71}
72
73function makeDom(tree, level) {
74  var dom = document.createElement('div');
75  dom.style.zIndex = 1;
76  dom.className = 'webtreemap-node webtreemap-level' + Math.min(level, 4);
77
78  dom.onmousedown = function(e) {
79    if (e.button == 0) {
80      if (focused && tree == focused && focused.parent) {
81        focus(focused.parent);
82      } else {
83        focus(tree);
84      }
85    }
86    e.stopPropagation();
87    return true;
88  };
89
90  var caption = document.createElement('div');
91  caption.className = 'webtreemap-caption';
92  caption.innerHTML = tree.name;
93  dom.appendChild(caption);
94
95  tree.dom = dom;
96  return dom;
97}
98
99function position(dom, x, y, width, height) {
100  // CSS width/height does not include border.
101  width -= kBorderWidth*2;
102  height -= kBorderWidth*2;
103
104  dom.style.left   = x + 'px';
105  dom.style.top    = y + 'px';
106  dom.style.width  = Math.max(width, 0) + 'px';
107  dom.style.height = Math.max(height, 0) + 'px';
108}
109
110// Given a list of rectangles |nodes|, the 1-d space available
111// |space|, and a starting rectangle index |start|, compute an span of
112// rectangles that optimizes a pleasant aspect ratio.
113//
114// Returns [end, sum], where end is one past the last rectangle and sum is the
115// 2-d sum of the rectangles' areas.
116function selectSpan(nodes, space, start) {
117  // Add rectangle one by one, stopping when aspect ratios begin to go
118  // bad.  Result is [start,end) covering the best run for this span.
119  // http://scholar.google.com/scholar?cluster=5972512107845615474
120  var node = nodes[start];
121  var rmin = node.data['$area'];  // Smallest seen child so far.
122  var rmax = rmin;                // Largest child.
123  var rsum = 0;                   // Sum of children in this span.
124  var last_score = 0;             // Best score yet found.
125  for (var end = start; node = nodes[end]; ++end) {
126    var size = node.data['$area'];
127    if (size < rmin)
128      rmin = size;
129    if (size > rmax)
130      rmax = size;
131    rsum += size;
132
133    // This formula is from the paper, but you can easily prove to
134    // yourself it's taking the larger of the x/y aspect ratio or the
135    // y/x aspect ratio.  The additional magic fudge constant of 5
136    // makes us prefer wider rectangles to taller ones.
137    var score = Math.max(5*space*space*rmax / (rsum*rsum),
138                         1*rsum*rsum / (space*space*rmin));
139    if (last_score && score > last_score) {
140      rsum -= size;  // Undo size addition from just above.
141      break;
142    }
143    last_score = score;
144  }
145  return [end, rsum];
146}
147
148function layout(tree, level, width, height) {
149  if (!('children' in tree))
150    return;
151
152  var total = tree.data['$area'];
153
154  // XXX why do I need an extra -1/-2 here for width/height to look right?
155  var x1 = 0, y1 = 0, x2 = width - 1, y2 = height - 2;
156  x1 += kPadding; y1 += kPadding;
157  x2 -= kPadding; y2 -= kPadding;
158  y1 += 14;  // XXX get first child height for caption spacing
159
160  var pixels_to_units = Math.sqrt(total / ((x2 - x1) * (y2 - y1)));
161
162  for (var start = 0, child; child = tree.children[start]; ++start) {
163    if (x2 - x1 < 60 || y2 - y1 < 40) {
164      if (child.dom) {
165        child.dom.style.zIndex = 0;
166        position(child.dom, -2, -2, 0, 0);
167      }
168      continue;
169    }
170
171    // In theory we can dynamically decide whether to split in x or y based
172    // on aspect ratio.  In practice, changing split direction with this
173    // layout doesn't look very good.
174    //   var ysplit = (y2 - y1) > (x2 - x1);
175    var ysplit = true;
176
177    var space;  // Space available along layout axis.
178    if (ysplit)
179      space = (y2 - y1) * pixels_to_units;
180    else
181      space = (x2 - x1) * pixels_to_units;
182
183    var span = selectSpan(tree.children, space, start);
184    var end = span[0], rsum = span[1];
185
186    // Now that we've selected a span, lay out rectangles [start,end) in our
187    // available space.
188    var x = x1, y = y1;
189    for (var i = start; i < end; ++i) {
190      child = tree.children[i];
191      if (!child.dom) {
192        child.parent = tree;
193        child.dom = makeDom(child, level + 1);
194        tree.dom.appendChild(child.dom);
195      } else {
196        child.dom.style.zIndex = 1;
197      }
198      var size = child.data['$area'];
199      var frac = size / rsum;
200      if (ysplit) {
201        width = rsum / space;
202        height = size / width;
203      } else {
204        height = rsum / space;
205        width = size / height;
206      }
207      width /= pixels_to_units;
208      height /= pixels_to_units;
209      width = Math.round(width);
210      height = Math.round(height);
211      position(child.dom, x, y, width, height);
212      if ('children' in child) {
213        layout(child, level + 1, width, height);
214      }
215      if (ysplit)
216        y += height;
217      else
218        x += width;
219    }
220
221    // Shrink our available space based on the amount we used.
222    if (ysplit)
223      x1 += Math.round((rsum / space) / pixels_to_units);
224    else
225      y1 += Math.round((rsum / space) / pixels_to_units);
226
227    // end points one past where we ended, which is where we want to
228    // begin the next iteration, but subtract one to balance the ++ in
229    // the loop.
230    start = end - 1;
231  }
232}
233
234function appendTreemap(dom, data) {
235  var style = getComputedStyle(dom, null);
236  var width = parseInt(style.width);
237  var height = parseInt(style.height);
238  if (!data.dom)
239    makeDom(data, 0);
240  dom.appendChild(data.dom);
241  position(data.dom, 0, 0, width, height);
242  layout(data, 0, width, height);
243}