2 * Copyright (C) 2011 Google Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
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
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.
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.
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.
36 // Padding around contents.
37 // TODO: do this with a nested div to allow it to be CSS-styleable.
42 // Callback for embedding page to update after a focus.
43 function handleFocus(tree) {}
45 function focus(tree) {
48 // Hide all visible siblings of all our ancestors by lowering them.
54 for (var i = 0, sibling; sibling = root.children[i]; ++i) {
56 sibling.dom.style.zIndex = 0;
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;
68 // And layout into the topmost box.
69 layout(tree, level, width, height);
73 function makeDom(tree, level) {
74 var dom = document.createElement('div');
76 dom.className = 'webtreemap-node webtreemap-level' + Math.min(level, 4);
78 dom.onmousedown = function(e) {
80 if (focused && tree == focused && focused.parent) {
81 focus(focused.parent);
90 var caption = document.createElement('div');
91 caption.className = 'webtreemap-caption';
92 caption.innerHTML = tree.name;
93 dom.appendChild(caption);
99 function position(dom, x, y, width, height) {
100 // CSS width/height does not include border.
101 width -= kBorderWidth*2;
102 height -= kBorderWidth*2;
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';
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.
114 // Returns [end, sum], where end is one past the last rectangle and sum is the
115 // 2-d sum of the rectangles' areas.
116 function 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'];
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.
148 function layout(tree, level, width, height) {
149 if (!('children' in tree))
152 var total = tree.data['$area'];
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
160 var pixels_to_units = Math.sqrt(total / ((x2 - x1) * (y2 - y1)));
162 for (var start = 0, child; child = tree.children[start]; ++start) {
163 if (x2 - x1 < 60 || y2 - y1 < 40) {
165 child.dom.style.zIndex = 0;
166 position(child.dom, -2, -2, 0, 0);
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);
177 var space; // Space available along layout axis.
179 space = (y2 - y1) * pixels_to_units;
181 space = (x2 - x1) * pixels_to_units;
183 var span = selectSpan(tree.children, space, start);
184 var end = span[0], rsum = span[1];
186 // Now that we've selected a span, lay out rectangles [start,end) in our
189 for (var i = start; i < end; ++i) {
190 child = tree.children[i];
193 child.dom = makeDom(child, level + 1);
194 tree.dom.appendChild(child.dom);
196 child.dom.style.zIndex = 1;
198 var size = child.data['$area'];
199 var frac = size / rsum;
201 width = rsum / space;
202 height = size / width;
204 height = rsum / space;
205 width = size / height;
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);
221 // Shrink our available space based on the amount we used.
223 x1 += Math.round((rsum / space) / pixels_to_units);
225 y1 += Math.round((rsum / space) / pixels_to_units);
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
234 function appendTreemap(dom, data) {
235 var style = getComputedStyle(dom, null);
236 var width = parseInt(style.width);
237 var height = parseInt(style.height);
240 dom.appendChild(data.dom);
241 position(data.dom, 0, 0, width, height);
242 layout(data, 0, width, height);