third_party/webtreemap/src/webtreemap.js

   1 // Copyright 2013 Google Inc. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 // Size of border around nodes.
  16 // We could support arbitrary borders using getComputedStyle(), but I am
  17 // skeptical the extra complexity (and performance hit) is worth it.
  18 var kBorderWidth = 1;
  19
  20 // Padding around contents.
  21 // TODO: do this with a nested div to allow it to be CSS-styleable.
  22 var kPadding = 4;
  23
  24 var focused = null;
  25
  26 function focus(tree) {
  27   focused = tree;
  28
  29   // Hide all visible siblings of all our ancestors by lowering them.
  30   var level = 0;
  31   var root = tree;
  32   while (root.parent) {
  33     root = root.parent;
  34     level += 1;
  35     for (var i = 0, sibling; sibling = root.children[i]; ++i) {
  36       if (sibling.dom)
  37         sibling.dom.style.zIndex = 0;
  38     }
  39   }
  40   var width = root.dom.offsetWidth;
  41   var height = root.dom.offsetHeight;
  42   // Unhide (raise) and maximize us and our ancestors.
  43   for (var t = tree; t.parent; t = t.parent) {
  44     // Shift off by border so we don't get nested borders.
  45     // TODO: actually make nested borders work (need to adjust width/height).
  46     position(t.dom, -kBorderWidth, -kBorderWidth, width, height);
  47     t.dom.style.zIndex = 1;
  48   }
  49   // And layout into the topmost box.
  50   layout(tree, level, width, height);
  51 }
  52
  53 function makeDom(tree, level) {
  54   var dom = document.createElement('div');
  55   dom.style.zIndex = 1;
  56   dom.className = 'webtreemap-node webtreemap-level' + Math.min(level, 4);
  57   if (tree.data['$symbol']) {
  58     dom.className += (' webtreemap-symbol-' +
  59         tree.data['$symbol'].replace(' ', '_'));
  60   }
  61   if (tree.data['$dominant_symbol']) {
  62     dom.className += (' webtreemap-symbol-' +
  63         tree.data['$dominant_symbol'].replace(' ', '_'));
  64     dom.className += (' webtreemap-aggregate');
  65   }
  66
  67   dom.onmousedown = function(e) {
  68     if (e.button == 0) {
  69       if (focused && tree == focused && focused.parent) {
  70         focus(focused.parent);
  71       } else {
  72         focus(tree);
  73       }
  74     }
  75     e.stopPropagation();
  76     return true;
  77   };
  78
  79   var caption = document.createElement('div');
  80   caption.className = 'webtreemap-caption';
  81   caption.innerHTML = tree.name;
  82   dom.appendChild(caption);
  83
  84   tree.dom = dom;
  85   return dom;
  86 }
  87
  88 function position(dom, x, y, width, height) {
  89   // CSS width/height does not include border.
  90   width -= kBorderWidth*2;
  91   height -= kBorderWidth*2;
  92
  93   dom.style.left   = x + 'px';
  94   dom.style.top    = y + 'px';
  95   dom.style.width  = Math.max(width, 0) + 'px';
  96   dom.style.height = Math.max(height, 0) + 'px';
  97 }
  98
  99 // Given a list of rectangles |nodes|, the 1-d space available
 100 // |space|, and a starting rectangle index |start|, compute an span of
 101 // rectangles that optimizes a pleasant aspect ratio.
 102 //
 103 // Returns [end, sum], where end is one past the last rectangle and sum is the
 104 // 2-d sum of the rectangles' areas.
 105 function selectSpan(nodes, space, start) {
 106   // Add rectangle one by one, stopping when aspect ratios begin to go
 107   // bad.  Result is [start,end) covering the best run for this span.
 108   // http://scholar.google.com/scholar?cluster=5972512107845615474
 109   var node = nodes[start];
 110   var rmin = node.data['$area'];  // Smallest seen child so far.
 111   var rmax = rmin;                // Largest child.
 112   var rsum = 0;                   // Sum of children in this span.
 113   var last_score = 0;             // Best score yet found.
 114   for (var end = start; node = nodes[end]; ++end) {
 115     var size = node.data['$area'];
 116     if (size < rmin)
 117       rmin = size;
 118     if (size > rmax)
 119       rmax = size;
 120     rsum += size;
 121
 122     // This formula is from the paper, but you can easily prove to
 123     // yourself it's taking the larger of the x/y aspect ratio or the
 124     // y/x aspect ratio.  The additional magic fudge constant of 5
 125     // makes us prefer wider rectangles to taller ones.
 126     var score = Math.max(5*space*space*rmax / (rsum*rsum),
 127                          1*rsum*rsum / (space*space*rmin));
 128     if (last_score && score > last_score) {
 129       rsum -= size;  // Undo size addition from just above.
 130       break;
 131     }
 132     last_score = score;
 133   }
 134   return [end, rsum];
 135 }
 136
 137 function layout(tree, level, width, height) {
 138   if (!('children' in tree))
 139     return;
 140
 141   var total = tree.data['$area'];
 142
 143   // XXX why do I need an extra -1/-2 here for width/height to look right?
 144   var x1 = 0, y1 = 0, x2 = width - 1, y2 = height - 2;
 145   x1 += kPadding; y1 += kPadding;
 146   x2 -= kPadding; y2 -= kPadding;
 147   y1 += 14;  // XXX get first child height for caption spacing
 148
 149   var pixels_to_units = Math.sqrt(total / ((x2 - x1) * (y2 - y1)));
 150
 151   for (var start = 0, child; child = tree.children[start]; ++start) {
 152     if (x2 - x1 < 60 || y2 - y1 < 40) {
 153       if (child.dom) {
 154         child.dom.style.zIndex = 0;
 155         position(child.dom, -2, -2, 0, 0);
 156       }
 157       continue;
 158     }
 159
 160     // In theory we can dynamically decide whether to split in x or y based
 161     // on aspect ratio.  In practice, changing split direction with this
 162     // layout doesn't look very good.
 163     //   var ysplit = (y2 - y1) > (x2 - x1);
 164     var ysplit = true;
 165
 166     var space;  // Space available along layout axis.
 167     if (ysplit)
 168       space = (y2 - y1) * pixels_to_units;
 169     else
 170       space = (x2 - x1) * pixels_to_units;
 171
 172     var span = selectSpan(tree.children, space, start);
 173     var end = span[0], rsum = span[1];
 174
 175     // Now that we've selected a span, lay out rectangles [start,end) in our
 176     // available space.
 177     var x = x1, y = y1;
 178     for (var i = start; i < end; ++i) {
 179       child = tree.children[i];
 180       if (!child.dom) {
 181         child.parent = tree;
 182         child.dom = makeDom(child, level + 1);
 183         tree.dom.appendChild(child.dom);
 184       } else {
 185         child.dom.style.zIndex = 1;
 186       }
 187       var size = child.data['$area'];
 188       var frac = size / rsum;
 189       if (ysplit) {
 190         width = rsum / space;
 191         height = size / width;
 192       } else {
 193         height = rsum / space;
 194         width = size / height;
 195       }
 196       width /= pixels_to_units;
 197       height /= pixels_to_units;
 198       width = Math.round(width);
 199       height = Math.round(height);
 200       position(child.dom, x, y, width, height);
 201       if ('children' in child) {
 202         layout(child, level + 1, width, height);
 203       }
 204       if (ysplit)
 205         y += height;
 206       else
 207         x += width;
 208     }
 209
 210     // Shrink our available space based on the amount we used.
 211     if (ysplit)
 212       x1 += Math.round((rsum / space) / pixels_to_units);
 213     else
 214       y1 += Math.round((rsum / space) / pixels_to_units);
 215
 216     // end points one past where we ended, which is where we want to
 217     // begin the next iteration, but subtract one to balance the ++ in
 218     // the loop.
 219     start = end - 1;
 220   }
 221 }
 222
 223 function appendTreemap(dom, data) {
 224   var style = getComputedStyle(dom, null);
 225   var width = parseInt(style.width);
 226   var height = parseInt(style.height);
 227   if (!data.dom)
 228     makeDom(data, 0);
 229   dom.appendChild(data.dom);
 230   position(data.dom, 0, 0, width, height);
 231   layout(data, 0, width, height);
 232 }