import “layout”; import “hierarchy”;

// Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk // Modified to support a target aspect ratio by Jeff Heer d3.layout.treemap = function() {

var hierarchy = d3.layout.hierarchy(),
    round = Math.round,
    size = [1, 1], // width, height
    padding = null,
    pad = d3_layout_treemapPadNull,
    sticky = false,
    stickies,
    mode = "squarify",
    ratio = 0.5 * (1 + Math.sqrt(5)); // golden ratio

// Compute the area for each child based on value & scale.
function scale(children, k) {
  var i = -1,
      n = children.length,
      child,
      area;
  while (++i < n) {
    area = (child = children[i]).value * (k < 0 ? 0 : k);
    child.area = isNaN(area) || area <= 0 ? 0 : area;
  }
}

// Recursively arranges the specified node's children into squarified rows.
function squarify(node) {
  var children = node.children;
  if (children && children.length) {
    var rect = pad(node),
        row = [],
        remaining = children.slice(), // copy-on-write
        child,
        best = Infinity, // the best row score so far
        score, // the current row score
        u = mode === "slice" ? rect.dx
          : mode === "dice" ? rect.dy
          : mode === "slice-dice" ? node.depth & 1 ? rect.dy : rect.dx
          : Math.min(rect.dx, rect.dy), // initial orientation
        n;
    scale(remaining, rect.dx * rect.dy / node.value);
    row.area = 0;
    while ((n = remaining.length) > 0) {
      row.push(child = remaining[n - 1]);
      row.area += child.area;
      if (mode !== "squarify" || (score = worst(row, u)) <= best) { // continue with this orientation
        remaining.pop();
        best = score;
      } else { // abort, and try a different orientation
        row.area -= row.pop().area;
        position(row, u, rect, false);
        u = Math.min(rect.dx, rect.dy);
        row.length = row.area = 0;
        best = Infinity;
      }
    }
    if (row.length) {
      position(row, u, rect, true);
      row.length = row.area = 0;
    }
    children.forEach(squarify);
  }
}

// Recursively resizes the specified node's children into existing rows.
// Preserves the existing layout!
function stickify(node) {
  var children = node.children;
  if (children && children.length) {
    var rect = pad(node),
        remaining = children.slice(), // copy-on-write
        child,
        row = [];
    scale(remaining, rect.dx * rect.dy / node.value);
    row.area = 0;
    while (child = remaining.pop()) {
      row.push(child);
      row.area += child.area;
      if (child.z != null) {
        position(row, child.z ? rect.dx : rect.dy, rect, !remaining.length);
        row.length = row.area = 0;
      }
    }
    children.forEach(stickify);
  }
}

// Computes the score for the specified row, as the worst aspect ratio.
function worst(row, u) {
  var s = row.area,
      r,
      rmax = 0,
      rmin = Infinity,
      i = -1,
      n = row.length;
  while (++i < n) {
    if (!(r = row[i].area)) continue;
    if (r < rmin) rmin = r;
    if (r > rmax) rmax = r;
  }
  s *= s;
  u *= u;
  return s
      ? Math.max((u * rmax * ratio) / s, s / (u * rmin * ratio))
      : Infinity;
}

// Positions the specified row of nodes. Modifies `rect`.
function position(row, u, rect, flush) {
  var i = -1,
      n = row.length,
      x = rect.x,
      y = rect.y,
      v = u ? round(row.area / u) : 0,
      o;
  if (u == rect.dx) { // horizontal subdivision
    if (flush || v > rect.dy) v = rect.dy; // over+underflow
    while (++i < n) {
      o = row[i];
      o.x = x;
      o.y = y;
      o.dy = v;
      x += o.dx = Math.min(rect.x + rect.dx - x, v ? round(o.area / v) : 0);
    }
    o.z = true;
    o.dx += rect.x + rect.dx - x; // rounding error
    rect.y += v;
    rect.dy -= v;
  } else { // vertical subdivision
    if (flush || v > rect.dx) v = rect.dx; // over+underflow
    while (++i < n) {
      o = row[i];
      o.x = x;
      o.y = y;
      o.dx = v;
      y += o.dy = Math.min(rect.y + rect.dy - y, v ? round(o.area / v) : 0);
    }
    o.z = false;
    o.dy += rect.y + rect.dy - y; // rounding error
    rect.x += v;
    rect.dx -= v;
  }
}

function treemap(d) {
  var nodes = stickies || hierarchy(d),
      root = nodes[0];
  root.x = 0;
  root.y = 0;
  root.dx = size[0];
  root.dy = size[1];
  if (stickies) hierarchy.revalue(root);
  scale([root], root.dx * root.dy / root.value);
  (stickies ? stickify : squarify)(root);
  if (sticky) stickies = nodes;
  return nodes;
}

treemap.size = function(x) {
  if (!arguments.length) return size;
  size = x;
  return treemap;
};

treemap.padding = function(x) {
  if (!arguments.length) return padding;

  function padFunction(node) {
    var p = x.call(treemap, node, node.depth);
    return p == null
        ? d3_layout_treemapPadNull(node)
        : d3_layout_treemapPad(node, typeof p === "number" ? [p, p, p, p] : p);
  }

  function padConstant(node) {
    return d3_layout_treemapPad(node, x);
  }

  var type;
  pad = (padding = x) == null ? d3_layout_treemapPadNull
      : (type = typeof x) === "function" ? padFunction
      : type === "number" ? (x = [x, x, x, x], padConstant)
      : padConstant;
  return treemap;
};

treemap.round = function(x) {
  if (!arguments.length) return round != Number;
  round = x ? Math.round : Number;
  return treemap;
};

treemap.sticky = function(x) {
  if (!arguments.length) return sticky;
  sticky = x;
  stickies = null;
  return treemap;
};

treemap.ratio = function(x) {
  if (!arguments.length) return ratio;
  ratio = x;
  return treemap;
};

treemap.mode = function(x) {
  if (!arguments.length) return mode;
  mode = x + "";
  return treemap;
};

return d3_layout_hierarchyRebind(treemap, hierarchy);

};

function d3_layout_treemapPadNull(node) {

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

}

function d3_layout_treemapPad(node, padding) {

var x = node.x + padding[3],
    y = node.y + padding[0],
    dx = node.dx - padding[1] - padding[3],
    dy = node.dy - padding[0] - padding[2];
if (dx < 0) { x += dx / 2; dx = 0; }
if (dy < 0) { y += dy / 2; dy = 0; }
return {x: x, y: y, dx: dx, dy: dy};

}