basant307/AI_Governance_Project

1export default function(parent, x0, y0, x1, y1) {2  var nodes = parent.children,3      i, n = nodes.length,4      sum, sums = new Array(n + 1);5 6  for (sums[0] = sum = i = 0; i < n; ++i) {7    sums[i + 1] = sum += nodes[i].value;8  }9 10  partition(0, n, parent.value, x0, y0, x1, y1);11 12  function partition(i, j, value, x0, y0, x1, y1) {13    if (i >= j - 1) {14      var node = nodes[i];15      node.x0 = x0, node.y0 = y0;16      node.x1 = x1, node.y1 = y1;17      return;18    }19 20    var valueOffset = sums[i],21        valueTarget = (value / 2) + valueOffset,22        k = i + 1,23        hi = j - 1;24 25    while (k < hi) {26      var mid = k + hi >>> 1;27      if (sums[mid] < valueTarget) k = mid + 1;28      else hi = mid;29    }30 31    if ((valueTarget - sums[k - 1]) < (sums[k] - valueTarget) && i + 1 < k) --k;32 33    var valueLeft = sums[k] - valueOffset,34        valueRight = value - valueLeft;35 36    if ((x1 - x0) > (y1 - y0)) {37      var xk = value ? (x0 * valueRight + x1 * valueLeft) / value : x1;38      partition(i, k, valueLeft, x0, y0, xk, y1);39      partition(k, j, valueRight, xk, y0, x1, y1);40    } else {41      var yk = value ? (y0 * valueRight + y1 * valueLeft) / value : y1;42      partition(i, k, valueLeft, x0, y0, x1, yk);43      partition(k, j, valueRight, x0, yk, x1, y1);44    }45  }46}47