1 // Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk

     2 // Modified to support a target aspect ratio by Jeff Heer

     3 d3.layout.treemap = function() {

     4   var hierarchy = d3.layout.hierarchy(),

     5       round = Math.round,

     6       size = [1, 1], // width, height

     7       padding = null,

     8       pad = d3_layout_treemapPadNull,

     9       sticky = false,

    10       stickies,

    11       ratio = 0.5 * (1 + Math.sqrt(5)); // golden ratio

    12 

    13   // Compute the area for each child based on value & scale.

    14   function scale(children, k) {

    15     var i = -1,

    16         n = children.length,

    17         child,

    18         area;

    19     while (++i < n) {

    20       area = (child = children[i]).value * (k < 0 ? 0 : k);

    21       child.area = isNaN(area) || area <= 0 ? 0 : area;

    22     }

    23   }

    24 

    25   // Recursively arranges the specified node's children into squarified rows.

    26   function squarify(node) {

    27     var children = node.children;

    28     if (children && children.length) {

    29       var rect = pad(node),

    30           row = [],

    31           remaining = children.slice(), // copy-on-write

    32           child,

    33           best = Infinity, // the best row score so far

    34           score, // the current row score

    35           u = Math.min(rect.dx, rect.dy), // initial orientation

    36           n;

    37       scale(remaining, rect.dx * rect.dy / node.value);

    38       row.area = 0;

    39       while ((n = remaining.length) > 0) {

    40         row.push(child = remaining[n - 1]);

    41         row.area += child.area;

    42         if ((score = worst(row, u)) <= best) { // continue with this orientation

    43           remaining.pop();

    44           best = score;

    45         } else { // abort, and try a different orientation

    46           row.area -= row.pop().area;

    47           position(row, u, rect, false);

    48           u = Math.min(rect.dx, rect.dy);

    49           row.length = row.area = 0;

    50           best = Infinity;

    51         }

    52       }

    53       if (row.length) {

    54         position(row, u, rect, true);

    55         row.length = row.area = 0;

    56       }

    57       children.forEach(squarify);

    58     }

    59   }

    60 

    61   // Recursively resizes the specified node's children into existing rows.

    62   // Preserves the existing layout!

    63   function stickify(node) {

    64     var children = node.children;

    65     if (children && children.length) {

    66       var rect = pad(node),

    67           remaining = children.slice(), // copy-on-write

    68           child,

    69           row = [];

    70       scale(remaining, rect.dx * rect.dy / node.value);

    71       row.area = 0;

    72       while (child = remaining.pop()) {

    73         row.push(child);

    74         row.area += child.area;

    75         if (child.z != null) {

    76           position(row, child.z ? rect.dx : rect.dy, rect, !remaining.length);

    77           row.length = row.area = 0;

    78         }

    79       }

    80       children.forEach(stickify);

    81     }

    82   }

    83 

    84   // Computes the score for the specified row, as the worst aspect ratio.

    85   function worst(row, u) {

    86     var s = row.area,

    87         r,

    88         rmax = 0,

    89         rmin = Infinity,

    90         i = -1,

    91         n = row.length;

    92     while (++i < n) {

    93       if (!(r = row[i].area)) continue;

    94       if (r < rmin) rmin = r;

    95       if (r > rmax) rmax = r;

    96     }

    97     s *= s;

    98     u *= u;

    99     return s

   100         ? Math.max((u * rmax * ratio) / s, s / (u * rmin * ratio))

   101         : Infinity;

   102   }

   103 

   104   // Positions the specified row of nodes. Modifies `rect`.

   105   function position(row, u, rect, flush) {

   106     var i = -1,

   107         n = row.length,

   108         x = rect.x,

   109         y = rect.y,

   110         v = u ? round(row.area / u) : 0,

   111         o;

   112     if (u == rect.dx) { // horizontal subdivision

   113       if (flush || v > rect.dy) v = v ? rect.dy : 0; // over+underflow

   114       while (++i < n) {

   115         o = row[i];

   116         o.x = x;

   117         o.y = y;

   118         o.dy = v;

   119         x += o.dx = v ? round(o.area / v) : 0;

   120       }

   121       o.z = true;

   122       o.dx += rect.x + rect.dx - x; // rounding error

   123       rect.y += v;

   124       rect.dy -= v;

   125     } else { // vertical subdivision

   126       if (flush || v > rect.dx) v = v ? rect.dx : 0; // over+underflow

   127       while (++i < n) {

   128         o = row[i];

   129         o.x = x;

   130         o.y = y;

   131         o.dx = v;

   132         y += o.dy = v ? round(o.area / v) : 0;

   133       }

   134       o.z = false;

   135       o.dy += rect.y + rect.dy - y; // rounding error

   136       rect.x += v;

   137       rect.dx -= v;

   138     }

   139   }

   140 

   141   function treemap(d) {

   142     var nodes = stickies || hierarchy(d),

   143         root = nodes[0];

   144     root.x = 0;

   145     root.y = 0;

   146     root.dx = size[0];

   147     root.dy = size[1];

   148     if (stickies) hierarchy.revalue(root);

   149     scale([root], root.dx * root.dy / root.value);

   150     (stickies ? stickify : squarify)(root);

   151     if (sticky) stickies = nodes;

   152     return nodes;

   153   }

   154 

   155   treemap.size = function(x) {

   156     if (!arguments.length) return size;

   157     size = x;

   158     return treemap;

   159   };

   160 

   161   treemap.padding = function(x) {

   162     if (!arguments.length) return padding;

   163 

   164     function padFunction(node) {

   165       var p = x.call(treemap, node, node.depth);

   166       return p == null

   167           ? d3_layout_treemapPadNull(node)

   168           : d3_layout_treemapPad(node, typeof p === "number" ? [p, p, p, p] : p);

   169     }

   170 

   171     function padConstant(node) {

   172       return d3_layout_treemapPad(node, x);

   173     }

   174 

   175     var type;

   176     pad = (padding = x) == null ? d3_layout_treemapPadNull

   177         : (type = typeof x) === "function" ? padFunction

   178         : type === "number" ? (x = [x, x, x, x], padConstant)

   179         : padConstant;

   180     return treemap;

   181   };

   182 

   183   treemap.round = function(x) {

   184     if (!arguments.length) return round != Number;

   185     round = x ? Math.round : Number;

   186     return treemap;

   187   };

   188 

   189   treemap.sticky = function(x) {

   190     if (!arguments.length) return sticky;

   191     sticky = x;

   192     stickies = null;

   193     return treemap;

   194   };

   195 

   196   treemap.ratio = function(x) {

   197     if (!arguments.length) return ratio;

   198     ratio = x;

   199     return treemap;

   200   };

   201 

   202   return d3_layout_hierarchyRebind(treemap, hierarchy);

   203 };

   204 

   205 function d3_layout_treemapPadNull(node) {

   206   return {x: node.x, y: node.y, dx: node.dx, dy: node.dy};

   207 }

   208 

   209 function d3_layout_treemapPad(node, padding) {

   210   var x = node.x + padding[3],

   211       y = node.y + padding[0],

   212       dx = node.dx - padding[1] - padding[3],

   213       dy = node.dy - padding[0] - padding[2];

   214   if (dx < 0) { x += dx / 2; dx = 0; }

   215   if (dy < 0) { y += dy / 2; dy = 0; }

   216   return {x: x, y: y, dx: dx, dy: dy};

   217 }