// https://github.com/vasturiano/d3-binarytree v0.2.0 Copyright 2021 Vasco Asturiano
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
typeof define === 'function' && define.amd ? define(['exports'], factory) :
(global = typeof globalThis !== 'undefined' ? globalThis : global || self, factory(global.d3 = global.d3 || {}));
}(this, (function (exports) { 'use strict';

function tree_add(d) {
  var x = +this._x.call(null, d);
  return add(this.cover(x), x, d);
}

function add(tree, x, d) {
  if (isNaN(x)) return tree; // ignore invalid points

  var parent,
      node = tree._root,
      leaf = {data: d},
      x0 = tree._x0,
      x1 = tree._x1,
      xm,
      xp,
      right,
      i,
      j;

  // If the tree is empty, initialize the root as a leaf.
  if (!node) return tree._root = leaf, tree;

  // Find the existing leaf for the new point, or add it.
  while (node.length) {
    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
    if (parent = node, !(node = node[i = +right])) return parent[i] = leaf, tree;
  }

  // Is the new point is exactly coincident with the existing point?
  xp = +tree._x.call(null, node.data);
  if (x === xp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree;

  // Otherwise, split the leaf node until the old and new point are separated.
  do {
    parent = parent ? parent[i] = new Array(2) : tree._root = new Array(2);
    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
  } while ((i = +right) === (j = +(xp >= xm)));
  return parent[j] = node, parent[i] = leaf, tree;
}

function addAll(data) {
  var i, n = data.length,
      x,
      xz = new Array(n),
      x0 = Infinity,
      x1 = -Infinity;

  // Compute the points and their extent.
  for (i = 0; i < n; ++i) {
    if (isNaN(x = +this._x.call(null, data[i]))) continue;
    xz[i] = x;
    if (x < x0) x0 = x;
    if (x > x1) x1 = x;
  }

  // If there were no (valid) points, abort.
  if (x0 > x1) return this;

  // Expand the tree to cover the new points.
  this.cover(x0).cover(x1);

  // Add the new points.
  for (i = 0; i < n; ++i) {
    add(this, xz[i], data[i]);
  }

  return this;
}

function tree_cover(x) {
  if (isNaN(x = +x)) return this; // ignore invalid points

  var x0 = this._x0,
      x1 = this._x1;

  // If the binarytree has no extent, initialize them.
  // Integer extent are necessary so that if we later double the extent,
  // the existing half boundaries don’t change due to floating point error!
  if (isNaN(x0)) {
    x1 = (x0 = Math.floor(x)) + 1;
  }

  // Otherwise, double repeatedly to cover.
  else {
    var z = x1 - x0 || 1,
        node = this._root,
        parent,
        i;

    while (x0 > x || x >= x1) {
      i = +(x < x0);
      parent = new Array(2), parent[i] = node, node = parent, z *= 2;
      switch (i) {
        case 0: x1 = x0 + z; break;
        case 1: x0 = x1 - z; break;
      }
    }

    if (this._root && this._root.length) this._root = node;
  }

  this._x0 = x0;
  this._x1 = x1;
  return this;
}

function tree_data() {
  var data = [];
  this.visit(function(node) {
    if (!node.length) do data.push(node.data); while (node = node.next)
  });
  return data;
}

function tree_extent(_) {
  return arguments.length
      ? this.cover(+_[0][0]).cover(+_[1][0])
      : isNaN(this._x0) ? undefined : [[this._x0], [this._x1]];
}

function Half(node, x0, x1) {
  this.node = node;
  this.x0 = x0;
  this.x1 = x1;
}

function tree_find(x, radius) {
  var data,
      x0 = this._x0,
      x1,
      x2,
      x3 = this._x1,
      halves = [],
      node = this._root,
      q,
      i;

  if (node) halves.push(new Half(node, x0, x3));
  if (radius == null) radius = Infinity;
  else {
    x0 = x - radius;
    x3 = x + radius;
  }

  while (q = halves.pop()) {

    // Stop searching if this half can’t contain a closer node.
    if (!(node = q.node)
        || (x1 = q.x0) > x3
        || (x2 = q.x1) < x0) continue;

    // Bisect the current half.
    if (node.length) {
      var xm = (x1 + x2) / 2;

      halves.push(
        new Half(node[1], xm, x2),
        new Half(node[0], x1, xm)
      );

      // Visit the closest half first.
      if (i = +(x >= xm)) {
        q = halves[halves.length - 1];
        halves[halves.length - 1] = halves[halves.length - 1 - i];
        halves[halves.length - 1 - i] = q;
      }
    }

    // Visit this point. (Visiting coincident points isn’t necessary!)
    else {
      var d = Math.abs(x - +this._x.call(null, node.data));
      if (d < radius) {
        radius = d;
        x0 = x - d;
        x3 = x + d;
        data = node.data;
      }
    }
  }

  return data;
}

function tree_remove(d) {
  if (isNaN(x = +this._x.call(null, d))) return this; // ignore invalid points

  var parent,
      node = this._root,
      retainer,
      previous,
      next,
      x0 = this._x0,
      x1 = this._x1,
      x,
      xm,
      right,
      i,
      j;

  // If the tree is empty, initialize the root as a leaf.
  if (!node) return this;

  // Find the leaf node for the point.
  // While descending, also retain the deepest parent with a non-removed sibling.
  if (node.length) while (true) {
    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
    if (!(parent = node, node = node[i = +right])) return this;
    if (!node.length) break;
    if (parent[(i + 1) & 1]) retainer = parent, j = i;
  }

  // Find the point to remove.
  while (node.data !== d) if (!(previous = node, node = node.next)) return this;
  if (next = node.next) delete node.next;

  // If there are multiple coincident points, remove just the point.
  if (previous) return (next ? previous.next = next : delete previous.next), this;

  // If this is the root point, remove it.
  if (!parent) return this._root = next, this;

  // Remove this leaf.
  next ? parent[i] = next : delete parent[i];

  // If the parent now contains exactly one leaf, collapse superfluous parents.
  if ((node = parent[0] || parent[1])
      && node === (parent[1] || parent[0])
      && !node.length) {
    if (retainer) retainer[j] = node;
    else this._root = node;
  }

  return this;
}

function removeAll(data) {
  for (var i = 0, n = data.length; i < n; ++i) this.remove(data[i]);
  return this;
}

function tree_root() {
  return this._root;
}

function tree_size() {
  var size = 0;
  this.visit(function(node) {
    if (!node.length) do ++size; while (node = node.next)
  });
  return size;
}

function tree_visit(callback) {
  var halves = [], q, node = this._root, child, x0, x1;
  if (node) halves.push(new Half(node, this._x0, this._x1));
  while (q = halves.pop()) {
    if (!callback(node = q.node, x0 = q.x0, x1 = q.x1) && node.length) {
      var xm = (x0 + x1) / 2;
      if (child = node[1]) halves.push(new Half(child, xm, x1));
      if (child = node[0]) halves.push(new Half(child, x0, xm));
    }
  }
  return this;
}

function tree_visitAfter(callback) {
  var halves = [], next = [], q;
  if (this._root) halves.push(new Half(this._root, this._x0, this._x1));
  while (q = halves.pop()) {
    var node = q.node;
    if (node.length) {
      var child, x0 = q.x0, x1 = q.x1, xm = (x0 + x1) / 2;
      if (child = node[0]) halves.push(new Half(child, x0, xm));
      if (child = node[1]) halves.push(new Half(child, xm, x1));
    }
    next.push(q);
  }
  while (q = next.pop()) {
    callback(q.node, q.x0, q.x1);
  }
  return this;
}

function defaultX(d) {
  return d[0];
}

function tree_x(_) {
  return arguments.length ? (this._x = _, this) : this._x;
}

function binarytree(nodes, x) {
  var tree = new Binarytree(x == null ? defaultX : x, NaN, NaN);
  return nodes == null ? tree : tree.addAll(nodes);
}

function Binarytree(x, x0, x1) {
  this._x = x;
  this._x0 = x0;
  this._x1 = x1;
  this._root = undefined;
}

function leaf_copy(leaf) {
  var copy = {data: leaf.data}, next = copy;
  while (leaf = leaf.next) next = next.next = {data: leaf.data};
  return copy;
}

var treeProto = binarytree.prototype = Binarytree.prototype;

treeProto.copy = function() {
  var copy = new Binarytree(this._x, this._x0, this._x1),
      node = this._root,
      nodes,
      child;

  if (!node) return copy;

  if (!node.length) return copy._root = leaf_copy(node), copy;

  nodes = [{source: node, target: copy._root = new Array(2)}];
  while (node = nodes.pop()) {
    for (var i = 0; i < 2; ++i) {
      if (child = node.source[i]) {
        if (child.length) nodes.push({source: child, target: node.target[i] = new Array(2)});
        else node.target[i] = leaf_copy(child);
      }
    }
  }

  return copy;
};

treeProto.add = tree_add;
treeProto.addAll = addAll;
treeProto.cover = tree_cover;
treeProto.data = tree_data;
treeProto.extent = tree_extent;
treeProto.find = tree_find;
treeProto.remove = tree_remove;
treeProto.removeAll = removeAll;
treeProto.root = tree_root;
treeProto.size = tree_size;
treeProto.visit = tree_visit;
treeProto.visitAfter = tree_visitAfter;
treeProto.x = tree_x;

exports.binarytree = binarytree;

Object.defineProperty(exports, '__esModule', { value: true });

})));