text: // https://d3js.org/d3-hierarchy/ Version 1.0.2. Copyright 2016 Mike Bostock.
  (function (global, factory) {
    typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
    typeof define === 'function' && define.amd ? define(['exports'], factory) :
    (factory((global.d3 = global.d3 || {})));
  }(this, function (exports) { 'use strict';
  
    function defaultSeparation(a, b) {
      return a.parent === b.parent ? 1 : 2;
    }
  
    function meanX(children) {
      return children.reduce(meanXReduce, 0) / children.length;
    }
  
    function meanXReduce(x, c) {
      return x + c.x;
    }
  
    function maxY(children) {
      return 1 + children.reduce(maxYReduce, 0);
    }
  
    function maxYReduce(y, c) {
      return Math.max(y, c.y);
    }
  
    function leafLeft(node) {
      var children;
      while (children = node.children) node = children[0];
      return node;
    }
  
    function leafRight(node) {
      var children;
      while (children = node.children) node = children[children.length - 1];
      return node;
    }
  
    function cluster() {
      var separation = defaultSeparation,
          dx = 1,
          dy = 1,
          nodeSize = false;
  
      function cluster(root) {
        var previousNode,
            x = 0;
  
        // First walk, computing the initial x & y values.
        root.eachAfter(function(node) {
          var children = node.children;
          if (children) {
            node.x = meanX(children);
            node.y = maxY(children);
          } else {
            node.x = previousNode ? x += separation(node, previousNode) : 0;
            node.y = 0;
            previousNode = node;
          }
        });
  
        var left = leafLeft(root),
            right = leafRight(root),
            x0 = left.x - separation(left, right) / 2,
            x1 = right.x + separation(right, left) / 2;
  
        // Second walk, normalizing x & y to the desired size.
        return root.eachAfter(nodeSize ? function(node) {
          node.x = (node.x - root.x) * dx;
          node.y = (root.y - node.y) * dy;
        } : function(node) {
          node.x = (node.x - x0) / (x1 - x0) * dx;
          node.y = (1 - (root.y ? node.y / root.y : 1)) * dy;
        });
      }
  
      cluster.separation = function(x) {
        return arguments.length ? (separation = x, cluster) : separation;
      };
  
      cluster.size = function(x) {
        return arguments.length ? (nodeSize = false, dx = +x[0], dy = +x[1], cluster) : (nodeSize ? null : [dx, dy]);
      };
  
      cluster.nodeSize = function(x) {
        return arguments.length ? (nodeSize = true, dx = +x[0], dy = +x[1], cluster) : (nodeSize ? [dx, dy] : null);
      };
  
      return cluster;
    }
  
    function node_each(callback) {
      var node = this, current, next = [node], children, i, n;
      do {
        current = next.reverse(), next = [];
        while (node = current.pop()) {
          callback(node), children = node.children;
          if (children) for (i = 0, n = children.length; i < n; ++i) {
            next.push(children[i]);
          }
        }
      } while (next.length);
      return this;
    }
  
    function node_eachBefore(callback) {
      var node = this, nodes = [node], children, i;
      while (node = nodes.pop()) {
        callback(node), children = node.children;
        if (children) for (i = children.length - 1; i >= 0; --i) {
          nodes.push(children[i]);
        }
      }
      return this;
    }
  
    function node_eachAfter(callback) {
      var node = this, nodes = [node], next = [], children, i, n;
      while (node = nodes.pop()) {
        next.push(node), children = node.children;
        if (children) for (i = 0, n = children.length; i < n; ++i) {
          nodes.push(children[i]);
        }
      }
      while (node = next.pop()) {
        callback(node);
      }
      return this;
    }
  
    function node_sum(value) {
      return this.eachAfter(function(node) {
        var sum = +value(node.data) || 0,
            children = node.children,
            i = children && children.length;
        while (--i >= 0) sum += children[i].value;
        node.value = sum;
      });
    }
  
    function node_sort(compare) {
      return this.eachBefore(function(node) {
        if (node.children) {
          node.children.sort(compare);
        }
      });
    }
  
    function node_path(end) {
      var start = this,
          ancestor = leastCommonAncestor(start, end),
          nodes = [start];
      while (start !== ancestor) {
        start = start.parent;
        nodes.push(start);
      }
      var k = nodes.length;
      while (end !== ancestor) {
        nodes.splice(k, 0, end);
        end = end.parent;
      }
      return nodes;
    }
  
    function leastCommonAncestor(a, b) {
      if (a === b) return a;
      var aNodes = a.ancestors(),
          bNodes = b.ancestors(),
          c = null;
      a = aNodes.pop();
      b = bNodes.pop();
      while (a === b) {
        c = a;
        a = aNodes.pop();
        b = bNodes.pop();
      }
      return c;
    }
  
    function node_ancestors() {
      var node = this, nodes = [node];
      while (node = node.parent) {
        nodes.push(node);
      }
      return nodes;
    }
  
    function node_descendants() {
      var nodes = [];
      this.each(function(node) {
        nodes.push(node);
      });
      return nodes;
    }
  
    function node_leaves() {
      var leaves = [];
      this.eachBefore(function(node) {
        if (!node.children) {
          leaves.push(node);
        }
      });
      return leaves;
    }
  
    function node_links() {
      var root = this, links = [];
      root.each(function(node) {
        if (node !== root) { // Don’t include the root’s parent, if any.
          links.push({source: node.parent, target: node});
        }
      });
      return links;
    }
  
    function hierarchy(data, children) {
      var root = new Node(data),
          valued = +data.value && (root.value = data.value),
          node,
          nodes = [root],
          child,
          childs,
          i,
          n;
  
      if (children == null) children = defaultChildren;
  
      while (node = nodes.pop()) {
        if (valued) node.value = +node.data.value;
        if ((childs = children(node.data)) && (n = childs.length)) {
          node.children = new Array(n);
          for (i = n - 1; i >= 0; --i) {
            nodes.push(child = node.children[i] = new Node(childs[i]));
            child.parent = node;
            child.depth = node.depth + 1;
          }
        }
      }
  
      return root.eachBefore(computeHeight);
    }
  
    function node_copy() {
      return hierarchy(this).eachBefore(copyData);
    }
  
    function defaultChildren(d) {
      return d.children;
    }
  
    function copyData(node) {
      node.data = node.data.data;
    }
  
    function computeHeight(node) {
      var height = 0;
      do node.height = height;
      while ((node = node.parent) && (node.height < ++height));
    }
  
    function Node(data) {
      this.data = data;
      this.depth =
      this.height = 0;
      this.parent = null;
    }
  
    Node.prototype = hierarchy.prototype = {
      constructor: Node,
      each: node_each,
      eachAfter: node_eachAfter,
      eachBefore: node_eachBefore,
      sum: node_sum,
      sort: node_sort,
      path: node_path,
      ancestors: node_ancestors,
      descendants: node_descendants,
      leaves: node_leaves,
      links: node_links,
      copy: node_copy
    };
  
    function Node$2(value) {
      this._ = value;
      this.next = null;
    }
  
    function shuffle(array) {
      var i,
          n = (array = array.slice()).length,
          head = null,
          node = head;
  
      while (n) {
        var next = new Node$2(array[n - 1]);
        if (node) node = node.next = next;
        else node = head = next;
        array[i] = array[--n];
      }
  
      return {
        head: head,
        tail: node
      };
    }
  
    function enclose(circles) {
      return encloseN(shuffle(circles), []);
    }
  
    function encloses(a, b) {
      var dx = b.x - a.x,
          dy = b.y - a.y,
          dr = a.r - b.r;
      return dr * dr + 1e-6 > dx * dx + dy * dy;
    }
  
    // Returns the smallest circle that contains circles L and intersects circles B.
    function encloseN(L, B) {
      var circle,
          l0 = null,
          l1 = L.head,
          l2,
          p1;
  
      switch (B.length) {
        case 1: circle = enclose1(B[0]); break;
        case 2: circle = enclose2(B[0], B[1]); break;
        case 3: circle = enclose3(B[0], B[1], B[2]); break;
      }
  
      while (l1) {
        p1 = l1._, l2 = l1.next;
        if (!circle || !encloses(circle, p1)) {
  
          // Temporarily truncate L before l1.
          if (l0) L.tail = l0, l0.next = null;
          else L.head = L.tail = null;
  
          B.push(p1);
          circle = encloseN(L, B); // Note: reorders L!
          B.pop();
  
          // Move l1 to the front of L and reconnect the truncated list L.
          if (L.head) l1.next = L.head, L.head = l1;
          else l1.next = null, L.head = L.tail = l1;
          l0 = L.tail, l0.next = l2;
  
        } else {
          l0 = l1;
        }
        l1 = l2;
      }
  
      L.tail = l0;
      return circle;
    }
  
    function enclose1(a) {
      return {
        x: a.x,
        y: a.y,
        r: a.r
      };
    }
  
    function enclose2(a, b) {
      var x1 = a.x, y1 = a.y, r1 = a.r,
          x2 = b.x, y2 = b.y, r2 = b.r,
          x21 = x2 - x1, y21 = y2 - y1, r21 = r2 - r1,
          l = Math.sqrt(x21 * x21 + y21 * y21);
      return {
        x: (x1 + x2 + x21 / l * r21) / 2,
        y: (y1 + y2 + y21 / l * r21) / 2,
        r: (l + r1 + r2) / 2
      };
    }
  
    function enclose3(a, b, c) {
      var x1 = a.x, y1 = a.y, r1 = a.r,
          x2 = b.x, y2 = b.y, r2 = b.r,
          x3 = c.x, y3 = c.y, r3 = c.r,
          a2 = 2 * (x1 - x2),
          b2 = 2 * (y1 - y2),
          c2 = 2 * (r2 - r1),
          d2 = x1 * x1 + y1 * y1 - r1 * r1 - x2 * x2 - y2 * y2 + r2 * r2,
          a3 = 2 * (x1 - x3),
          b3 = 2 * (y1 - y3),
          c3 = 2 * (r3 - r1),
          d3 = x1 * x1 + y1 * y1 - r1 * r1 - x3 * x3 - y3 * y3 + r3 * r3,
          ab = a3 * b2 - a2 * b3,
          xa = (b2 * d3 - b3 * d2) / ab - x1,
          xb = (b3 * c2 - b2 * c3) / ab,
          ya = (a3 * d2 - a2 * d3) / ab - y1,
          yb = (a2 * c3 - a3 * c2) / ab,
          A = xb * xb + yb * yb - 1,
          B = 2 * (xa * xb + ya * yb + r1),
          C = xa * xa + ya * ya - r1 * r1,
          r = (-B - Math.sqrt(B * B - 4 * A * C)) / (2 * A);
      return {
        x: xa + xb * r + x1,
        y: ya + yb * r + y1,
        r: r
      };
    }
  
    function place(a, b, c) {
      var ax = a.x,
          ay = a.y,
          da = b.r + c.r,
          db = a.r + c.r,
          dx = b.x - ax,
          dy = b.y - ay,
          dc = dx * dx + dy * dy;
      if (dc) {
        var x = 0.5 + ((db *= db) - (da *= da)) / (2 * dc),
            y = Math.sqrt(Math.max(0, 2 * da * (db + dc) - (db -= dc) * db - da * da)) / (2 * dc);
        c.x = ax + x * dx + y * dy;
        c.y = ay + x * dy - y * dx;
      } else {
        c.x = ax + db;
        c.y = ay;
      }
    }
  
    function intersects(a, b) {
      var dx = b.x - a.x,
          dy = b.y - a.y,
          dr = a.r + b.r;
      return dr * dr > dx * dx + dy * dy;
    }
  
    function distance2(circle, x, y) {
      var dx = circle.x - x,
          dy = circle.y - y;
      return dx * dx + dy * dy;
    }
  
    function Node$1(circle) {
      this._ = circle;
      this.next = null;
      this.previous = null;
    }
  
    function packEnclose(circles) {
      if (!(n = circles.length)) return 0;
  
      var a, b, c, n;
  
      // Place the first circle.
      a = circles[0], a.x = 0, a.y = 0;
      if (!(n > 1)) return a.r;
  
      // Place the second circle.
      b = circles[1], a.x = -b.r, b.x = a.r, b.y = 0;
      if (!(n > 2)) return a.r + b.r;
  
      // Place the third circle.
      place(b, a, c = circles[2]);
  
      // Initialize the weighted centroid.
      var aa = a.r * a.r,
          ba = b.r * b.r,
          ca = c.r * c.r,
          oa = aa + ba + ca,
          ox = aa * a.x + ba * b.x + ca * c.x,
          oy = aa * a.y + ba * b.y + ca * c.y,
          cx, cy, i, j, k, sj, sk;
  
      // Initialize the front-chain using the first three circles a, b and c.
      a = new Node$1(a), b = new Node$1(b), c = new Node$1(c);
      a.next = c.previous = b;
      b.next = a.previous = c;
      c.next = b.previous = a;
  
      // Attempt to place each remaining circle…
      pack: for (i = 3; i < n; ++i) {
        place(a._, b._, c = circles[i]), c = new Node$1(c);
  
        // If there are only three elements in the front-chain…
        if ((k = a.previous) === (j = b.next)) {
          // If the new circle intersects the third circle,
          // rotate the front chain to try the next position.
          if (intersects(j._, c._)) {
            a = b, b = j, --i;
            continue pack;
          }
        }
  
        // Find the closest intersecting circle on the front-chain, if any.
        else {
          sj = j._.r, sk = k._.r;
          do {
            if (sj <= sk) {
              if (intersects(j._, c._)) {
                b = j, a.next = b, b.previous = a, --i;
                continue pack;
              }
              j = j.next, sj += j._.r;
            } else {
              if (intersects(k._, c._)) {
                a = k, a.next = b, b.previous = a, --i;
                continue pack;
              }
              k = k.previous, sk += k._.r;
            }
          } while (j !== k.next);
        }
  
        // Success! Insert the new circle c between a and b.
        c.previous = a, c.next = b, a.next = b.previous = b = c;
  
        // Update the weighted centroid.
        oa += ca = c._.r * c._.r;
        ox += ca * c._.x;
        oy += ca * c._.y;
  
        // Compute the new closest circle a to centroid.
        aa = distance2(a._, cx = ox / oa, cy = oy / oa);
        while ((c = c.next) !== b) {
          if ((ca = distance2(c._, cx, cy)) < aa) {
            a = c, aa = ca;
          }
        }
        b = a.next;
      }
  
      // Compute the enclosing circle of the front chain.
      a = [b._], c = b; while ((c = c.next) !== b) a.push(c._); c = enclose(a);
  
      // Translate the circles to put the enclosing circle around the origin.
      for (i = 0; i < n; ++i) a = circles[i], a.x -= c.x, a.y -= c.y;
  
      return c.r;
    }
  
    function siblings(circles) {
      packEnclose(circles);
      return circles;
    }
  
    function optional(f) {
      return f == null ? null : required(f);
    }
  
    function required(f) {
      if (typeof f !== "function") throw new Error;
      return f;
    }
  
    function constantZero() {
      return 0;
    }
  
    function constant(x) {
      return function() {
        return x;
      };
    }
  
    function defaultRadius(d) {
      return Math.sqrt(d.value);
    }
  
    function index() {
      var radius = null,
          dx = 1,
          dy = 1,
          padding = constantZero;
  
      function pack(root) {
        root.x = dx / 2, root.y = dy / 2;
        if (radius) {
          root.eachBefore(radiusLeaf(radius))
              .eachAfter(packChildren(padding, 0.5))
              .eachBefore(translateChild(1));
        } else {
          root.eachBefore(radiusLeaf(defaultRadius))
              .eachAfter(packChildren(constantZero, 1))
              .eachAfter(packChildren(padding, root.r / Math.min(dx, dy)))
              .eachBefore(translateChild(Math.min(dx, dy) / (2 * root.r)));
        }
        return root;
      }
  
      pack.radius = function(x) {
        return arguments.length ? (radius = optional(x), pack) : radius;
      };
  
      pack.size = function(x) {
        return arguments.length ? (dx = +x[0], dy = +x[1], pack) : [dx, dy];
      };
  
      pack.padding = function(x) {
        return arguments.length ? (padding = typeof x === "function" ? x : constant(+x), pack) : padding;
      };
  
      return pack;
    }
  
    function radiusLeaf(radius) {
      return function(node) {
        if (!node.children) {
          node.r = Math.max(0, +radius(node) || 0);
        }
      };
    }
  
    function packChildren(padding, k) {
      return function(node) {
        if (children = node.children) {
          var children,
              i,
              n = children.length,
              r = padding(node) * k || 0,
              e;
  
          if (r) for (i = 0; i < n; ++i) children[i].r += r;
          e = packEnclose(children);
          if (r) for (i = 0; i < n; ++i) children[i].r -= r;
          node.r = e + r;
        }
      };
    }
  
    function translateChild(k) {
      return function(node) {
        var parent = node.parent;
        node.r *= k;
        if (parent) {
          node.x = parent.x + k * node.x;
          node.y = parent.y + k * node.y;
        }
      };
    }
  
    function roundNode(node) {
      node.x0 = Math.round(node.x0);
      node.y0 = Math.round(node.y0);
      node.x1 = Math.round(node.x1);
      node.y1 = Math.round(node.y1);
    }
  
    function treemapDice(parent, x0, y0, x1, y1) {
      var nodes = parent.children,
          node,
          i = -1,
          n = nodes.length,
          k = parent.value && (x1 - x0) / parent.value;
  
      while (++i < n) {
        node = nodes[i], node.y0 = y0, node.y1 = y1;
        node.x0 = x0, node.x1 = x0 += node.value * k;
      }
    }
  
    function partition() {
      var dx = 1,
          dy = 1,
          padding = 0,
          round = false;
  
      function partition(root) {
        var n = root.height + 1;
        root.x0 =
        root.y0 = padding;
        root.x1 = dx;
        root.y1 = dy / n;
        root.eachBefore(positionNode(dy, n));
        if (round) root.eachBefore(roundNode);
        return root;
      }
  
      function positionNode(dy, n) {
        return function(node) {
          if (node.children) {
            treemapDice(node, node.x0, dy * (node.depth + 1) / n, node.x1, dy * (node.depth + 2) / n);
          }
          var x0 = node.x0,
              y0 = node.y0,
              x1 = node.x1 - padding,
              y1 = node.y1 - padding;
          if (x1 < x0) x0 = x1 = (x0 + x1) / 2;
          if (y1 < y0) y0 = y1 = (y0 + y1) / 2;
          node.x0 = x0;
          node.y0 = y0;
          node.x1 = x1;
          node.y1 = y1;
        };
      }
  
      partition.round = function(x) {
        return arguments.length ? (round = !!x, partition) : round;
      };
  
      partition.size = function(x) {
        return arguments.length ? (dx = +x[0], dy = +x[1], partition) : [dx, dy];
      };
  
      partition.padding = function(x) {
        return arguments.length ? (padding = +x, partition) : padding;
      };
  
      return partition;
    }
  
    var keyPrefix = "$";
    var preroot = {depth: -1};
    var ambiguous = {};
    function defaultId(d) {
      return d.id;
    }
  
    function defaultParentId(d) {
      return d.parentId;
    }
  
    function stratify() {
      var id = defaultId,
          parentId = defaultParentId;
  
      function stratify(data) {
        var d,
            i,
            n = data.length,
            root,
            parent,
            node,
            nodes = new Array(n),
            nodeId,
            nodeKey,
            nodeByKey = {};
  
        for (i = 0; i < n; ++i) {
          d = data[i], node = nodes[i] = new Node(d);
          if ((nodeId = id(d, i, data)) != null && (nodeId += "")) {
            nodeKey = keyPrefix + (node.id = nodeId);
            nodeByKey[nodeKey] = nodeKey in nodeByKey ? ambiguous : node;
          }
        }
  
        for (i = 0; i < n; ++i) {
          node = nodes[i], nodeId = parentId(data[i], i, data);
          if (nodeId == null || !(nodeId += "")) {
            if (root) throw new Error("multiple roots");
            root = node;
          } else {
            parent = nodeByKey[keyPrefix + nodeId];
            if (!parent) throw new Error("missing: " + nodeId);
            if (parent === ambiguous) throw new Error("ambiguous: " + nodeId);
            if (parent.children) parent.children.push(node);
            else parent.children = [node];
            node.parent = parent;
          }
        }
  
        if (!root) throw new Error("no root");
        root.parent = preroot;
        root.eachBefore(function(node) { node.depth = node.parent.depth + 1; --n; }).eachBefore(computeHeight);
        root.parent = null;
        if (n > 0) throw new Error("cycle");
  
        return root;
      }
  
      stratify.id = function(x) {
        return arguments.length ? (id = required(x), stratify) : id;
      };
  
      stratify.parentId = function(x) {
        return arguments.length ? (parentId = required(x), stratify) : parentId;
      };
  
      return stratify;
    }
  
    function defaultSeparation$1(a, b) {
      return a.parent === b.parent ? 1 : 2;
    }
  
    // function radialSeparation(a, b) {
    //   return (a.parent === b.parent ? 1 : 2) / a.depth;
    // }
  
    // This function is used to traverse the left contour of a subtree (or
    // subforest). It returns the successor of v on this contour. This successor is
    // either given by the leftmost child of v or by the thread of v. The function
    // returns null if and only if v is on the highest level of its subtree.
    function nextLeft(v) {
      var children = v.children;
      return children ? children[0] : v.t;
    }
  
    // This function works analogously to nextLeft.
    function nextRight(v) {
      var children = v.children;
      return children ? children[children.length - 1] : v.t;
    }
  
    // Shifts the current subtree rooted at w+. This is done by increasing
    // prelim(w+) and mod(w+) by shift.
    function moveSubtree(wm, wp, shift) {
      var change = shift / (wp.i - wm.i);
      wp.c -= change;
      wp.s += shift;
      wm.c += change;
      wp.z += shift;
      wp.m += shift;
    }
  
    // All other shifts, applied to the smaller subtrees between w- and w+, are
    // performed by this function. To prepare the shifts, we have to adjust
    // change(w+), shift(w+), and change(w-).
    function executeShifts(v) {
      var shift = 0,
          change = 0,
          children = v.children,
          i = children.length,
          w;
      while (--i >= 0) {
        w = children[i];
        w.z += shift;
        w.m += shift;
        shift += w.s + (change += w.c);
      }
    }
  
    // If vi-’s ancestor is a sibling of v, returns vi-’s ancestor. Otherwise,
    // returns the specified (default) ancestor.
    function nextAncestor(vim, v, ancestor) {
      return vim.a.parent === v.parent ? vim.a : ancestor;
    }
  
    function TreeNode(node, i) {
      this._ = node;
      this.parent = null;
      this.children = null;
      this.A = null; // default ancestor
      this.a = this; // ancestor
      this.z = 0; // prelim
      this.m = 0; // mod
      this.c = 0; // change
      this.s = 0; // shift
      this.t = null; // thread
      this.i = i; // number
    }
  
    TreeNode.prototype = Object.create(Node.prototype);
  
    function treeRoot(root) {
      var tree = new TreeNode(root, 0),
          node,
          nodes = [tree],
          child,
          children,
          i,
          n;
  
      while (node = nodes.pop()) {
        if (children = node._.children) {
          node.children = new Array(n = children.length);
          for (i = n - 1; i >= 0; --i) {
            nodes.push(child = node.children[i] = new TreeNode(children[i], i));
            child.parent = node;
          }
        }
      }
  
      (tree.parent = new TreeNode(null, 0)).children = [tree];
      return tree;
    }
  
    // Node-link tree diagram using the Reingold-Tilford "tidy" algorithm
    function tree() {
      var separation = defaultSeparation$1,
          dx = 1,
          dy = 1,
          nodeSize = null;
  
      function tree(root) {
        var t = treeRoot(root);
  
        // Compute the layout using Buchheim et al.’s algorithm.
        t.eachAfter(firstWalk), t.parent.m = -t.z;
        t.eachBefore(secondWalk);
  
        // If a fixed node size is specified, scale x and y.
        if (nodeSize) root.eachBefore(sizeNode);
  
        // If a fixed tree size is specified, scale x and y based on the extent.
        // Compute the left-most, right-most, and depth-most nodes for extents.
        else {
          var left = root,
              right = root,
              bottom = root;
          root.eachBefore(function(node) {
            if (node.x < left.x) left = node;
            if (node.x > right.x) right = node;
            if (node.depth > bottom.depth) bottom = node;
          });
          var s = left === right ? 1 : separation(left, right) / 2,
              tx = s - left.x,
              kx = dx / (right.x + s + tx),
              ky = dy / (bottom.depth || 1);
          root.eachBefore(function(node) {
            node.x = (node.x + tx) * kx;
            node.y = node.depth * ky;
          });
        }
  
        return root;
      }
  
      // Computes a preliminary x-coordinate for v. Before that, FIRST WALK is
      // applied recursively to the children of v, as well as the function
      // APPORTION. After spacing out the children by calling EXECUTE SHIFTS, the
      // node v is placed to the midpoint of its outermost children.
      function firstWalk(v) {
        var children = v.children,
            siblings = v.parent.children,
            w = v.i ? siblings[v.i - 1] : null;
        if (children) {
          executeShifts(v);
          var midpoint = (children[0].z + children[children.length - 1].z) / 2;
          if (w) {
            v.z = w.z + separation(v._, w._);
            v.m = v.z - midpoint;
          } else {
            v.z = midpoint;
          }
        } else if (w) {
          v.z = w.z + separation(v._, w._);
        }
        v.parent.A = apportion(v, w, v.parent.A || siblings[0]);
      }
  
      // Computes all real x-coordinates by summing up the modifiers recursively.
      function secondWalk(v) {
        v._.x = v.z + v.parent.m;
        v.m += v.parent.m;
      }
  
      // The core of the algorithm. Here, a new subtree is combined with the
      // previous subtrees. Threads are used to traverse the inside and outside
      // contours of the left and right subtree up to the highest common level. The
      // vertices used for the traversals are vi+, vi-, vo-, and vo+, where the
      // superscript o means outside and i means inside, the subscript - means left
      // subtree and + means right subtree. For summing up the modifiers along the
      // contour, we use respective variables si+, si-, so-, and so+. Whenever two
      // nodes of the inside contours conflict, we compute the left one of the
      // greatest uncommon ancestors using the function ANCESTOR and call MOVE
      // SUBTREE to shift the subtree and prepare the shifts of smaller subtrees.
      // Finally, we add a new thread (if necessary).
      function apportion(v, w, ancestor) {
        if (w) {
          var vip = v,
              vop = v,
              vim = w,
              vom = vip.parent.children[0],
              sip = vip.m,
              sop = vop.m,
              sim = vim.m,
              som = vom.m,
              shift;
          while (vim = nextRight(vim), vip = nextLeft(vip), vim && vip) {
            vom = nextLeft(vom);
            vop = nextRight(vop);
            vop.a = v;
            shift = vim.z + sim - vip.z - sip + separation(vim._, vip._);
            if (shift > 0) {
              moveSubtree(nextAncestor(vim, v, ancestor), v, shift);
              sip += shift;
              sop += shift;
            }
            sim += vim.m;
            sip += vip.m;
            som += vom.m;
            sop += vop.m;
          }
          if (vim && !nextRight(vop)) {
            vop.t = vim;
            vop.m += sim - sop;
          }
          if (vip && !nextLeft(vom)) {
            vom.t = vip;
            vom.m += sip - som;
            ancestor = v;
          }
        }
        return ancestor;
      }
  
      function sizeNode(node) {
        node.x *= dx;
        node.y = node.depth * dy;
      }
  
      tree.separation = function(x) {
        return arguments.length ? (separation = x, tree) : separation;
      };
  
      tree.size = function(x) {
        return arguments.length ? (nodeSize = false, dx = +x[0], dy = +x[1], tree) : (nodeSize ? null : [dx, dy]);
      };
  
      tree.nodeSize = function(x) {
        return arguments.length ? (nodeSize = true, dx = +x[0], dy = +x[1], tree) : (nodeSize ? [dx, dy] : null);
      };
  
      return tree;
    }
  
    function treemapSlice(parent, x0, y0, x1, y1) {
      var nodes = parent.children,
          node,
          i = -1,
          n = nodes.length,
          k = parent.value && (y1 - y0) / parent.value;
  
      while (++i < n) {
        node = nodes[i], node.x0 = x0, node.x1 = x1;
        node.y0 = y0, node.y1 = y0 += node.value * k;
      }
    }
  
    var phi = (1 + Math.sqrt(5)) / 2;
  
    function squarifyRatio(ratio, parent, x0, y0, x1, y1) {
      var rows = [],
          nodes = parent.children,
          row,
          nodeValue,
          i0 = 0,
          i1,
          n = nodes.length,
          dx, dy,
          value = parent.value,
          sumValue,
          minValue,
          maxValue,
          newRatio,
          minRatio,
          alpha,
          beta;
  
      while (i0 < n) {
        dx = x1 - x0, dy = y1 - y0;
        minValue = maxValue = sumValue = nodes[i0].value;
        alpha = Math.max(dy / dx, dx / dy) / (value * ratio);
        beta = sumValue * sumValue * alpha;
        minRatio = Math.max(maxValue / beta, beta / minValue);
  
        // Keep adding nodes while the aspect ratio maintains or improves.
        for (i1 = i0 + 1; i1 < n; ++i1) {
          sumValue += nodeValue = nodes[i1].value;
          if (nodeValue < minValue) minValue = nodeValue;
          if (nodeValue > maxValue) maxValue = nodeValue;
          beta = sumValue * sumValue * alpha;
          newRatio = Math.max(maxValue / beta, beta / minValue);
          if (newRatio > minRatio) { sumValue -= nodeValue; break; }
          minRatio = newRatio;
        }
  
        // Position and record the row orientation.
        rows.push(row = {value: sumValue, dice: dx < dy, children: nodes.slice(i0, i1)});
        if (row.dice) treemapDice(row, x0, y0, x1, value ? y0 += dy * sumValue / value : y1);
        else treemapSlice(row, x0, y0, value ? x0 += dx * sumValue / value : x1, y1);
        value -= sumValue, i0 = i1;
      }
  
      return rows;
    }
  
    var squarify = (function custom(ratio) {
  
      function squarify(parent, x0, y0, x1, y1) {
        squarifyRatio(ratio, parent, x0, y0, x1, y1);
      }
  
      squarify.ratio = function(x) {
        return custom((x = +x) > 1 ? x : 1);
      };
  
      return squarify;
    })(phi);
  
    function index$1() {
      var tile = squarify,
          round = false,
          dx = 1,
          dy = 1,
          paddingStack = [0],
          paddingInner = constantZero,
          paddingTop = constantZero,
          paddingRight = constantZero,
          paddingBottom = constantZero,
          paddingLeft = constantZero;
  
      function treemap(root) {
        root.x0 =
        root.y0 = 0;
        root.x1 = dx;
        root.y1 = dy;
        root.eachBefore(positionNode);
        paddingStack = [0];
        if (round) root.eachBefore(roundNode);
        return root;
      }
  
      function positionNode(node) {
        var p = paddingStack[node.depth],
            x0 = node.x0 + p,
            y0 = node.y0 + p,
            x1 = node.x1 - p,
            y1 = node.y1 - p;
        if (x1 < x0) x0 = x1 = (x0 + x1) / 2;
        if (y1 < y0) y0 = y1 = (y0 + y1) / 2;
        node.x0 = x0;
        node.y0 = y0;
        node.x1 = x1;
        node.y1 = y1;
        if (node.children) {
          p = paddingStack[node.depth + 1] = paddingInner(node) / 2;
          x0 += paddingLeft(node) - p;
          y0 += paddingTop(node) - p;
          x1 -= paddingRight(node) - p;
          y1 -= paddingBottom(node) - p;
          if (x1 < x0) x0 = x1 = (x0 + x1) / 2;
          if (y1 < y0) y0 = y1 = (y0 + y1) / 2;
          tile(node, x0, y0, x1, y1);
        }
      }
  
      treemap.round = function(x) {
        return arguments.length ? (round = !!x, treemap) : round;
      };
  
      treemap.size = function(x) {
        return arguments.length ? (dx = +x[0], dy = +x[1], treemap) : [dx, dy];
      };
  
      treemap.tile = function(x) {
        return arguments.length ? (tile = required(x), treemap) : tile;
      };
  
      treemap.padding = function(x) {
        return arguments.length ? treemap.paddingInner(x).paddingOuter(x) : treemap.paddingInner();
      };
  
      treemap.paddingInner = function(x) {
        return arguments.length ? (paddingInner = typeof x === "function" ? x : constant(+x), treemap) : paddingInner;
      };
  
      treemap.paddingOuter = function(x) {
        return arguments.length ? treemap.paddingTop(x).paddingRight(x).paddingBottom(x).paddingLeft(x) : treemap.paddingTop();
      };
  
      treemap.paddingTop = function(x) {
        return arguments.length ? (paddingTop = typeof x === "function" ? x : constant(+x), treemap) : paddingTop;
      };
  
      treemap.paddingRight = function(x) {
        return arguments.length ? (paddingRight = typeof x === "function" ? x : constant(+x), treemap) : paddingRight;
      };
  
      treemap.paddingBottom = function(x) {
        return arguments.length ? (paddingBottom = typeof x === "function" ? x : constant(+x), treemap) : paddingBottom;
      };
  
      treemap.paddingLeft = function(x) {
        return arguments.length ? (paddingLeft = typeof x === "function" ? x : constant(+x), treemap) : paddingLeft;
      };
  
      return treemap;
    }
  
    function binary(parent, x0, y0, x1, y1) {
      var nodes = parent.children,
          i, n = nodes.length,
          sum, sums = new Array(n + 1);
  
      for (sums[0] = sum = i = 0; i < n; ++i) {
        sums[i + 1] = sum += nodes[i].value;
      }
  
      partition(0, n, parent.value, x0, y0, x1, y1);
  
      function partition(i, j, value, x0, y0, x1, y1) {
        if (i >= j - 1) {
          var node = nodes[i];
          node.x0 = x0, node.y0 = y0;
          node.x1 = x1, node.y1 = y1;
          return;
        }
  
        var valueOffset = sums[i],
            valueTarget = (value / 2) + valueOffset,
            k = i + 1,
            hi = j - 1;
  
        while (k < hi) {
          var mid = k + hi >>> 1;
          if (sums[mid] < valueTarget) k = mid + 1;
          else hi = mid;
        }
  
        var valueLeft = sums[k] - valueOffset,
            valueRight = value - valueLeft;
  
        if ((y1 - y0) > (x1 - x0)) {
          var yk = (y0 * valueRight + y1 * valueLeft) / value;
          partition(i, k, valueLeft, x0, y0, x1, yk);
          partition(k, j, valueRight, x0, yk, x1, y1);
        } else {
          var xk = (x0 * valueRight + x1 * valueLeft) / value;
          partition(i, k, valueLeft, x0, y0, xk, y1);
          partition(k, j, valueRight, xk, y0, x1, y1);
        }
      }
    }
  
    function sliceDice(parent, x0, y0, x1, y1) {
      (parent.depth & 1 ? treemapSlice : treemapDice)(parent, x0, y0, x1, y1);
    }
  
    var resquarify = (function custom(ratio) {
  
      function resquarify(parent, x0, y0, x1, y1) {
        if ((rows = parent._squarify) && (rows.ratio === ratio)) {
          var rows,
              row,
              nodes,
              i,
              j = -1,
              n,
              m = rows.length,
              value = parent.value;
  
          while (++j < m) {
            row = rows[j], nodes = row.children;
            for (i = row.value = 0, n = nodes.length; i < n; ++i) row.value += nodes[i].value;
            if (row.dice) treemapDice(row, x0, y0, x1, y0 += (y1 - y0) * row.value / value);
            else treemapSlice(row, x0, y0, x0 += (x1 - x0) * row.value / value, y1);
            value -= row.value;
          }
        } else {
          parent._squarify = rows = squarifyRatio(ratio, parent, x0, y0, x1, y1);
          rows.ratio = ratio;
        }
      }
  
      resquarify.ratio = function(x) {
        return custom((x = +x) > 1 ? x : 1);
      };
  
      return resquarify;
    })(phi);
  
    exports.cluster = cluster;
    exports.hierarchy = hierarchy;
    exports.pack = index;
    exports.packSiblings = siblings;
    exports.packEnclose = enclose;
    exports.partition = partition;
    exports.stratify = stratify;
    exports.tree = tree;
    exports.treemap = index$1;
    exports.treemapBinary = binary;
    exports.treemapDice = treemapDice;
    exports.treemapSlice = treemapSlice;
    exports.treemapSliceDice = sliceDice;
    exports.treemapSquarify = squarify;
    exports.treemapResquarify = resquarify;
  
    Object.defineProperty(exports, '__esModule', { value: true });
  
  }));