Brunobkr/llama.cpp_AlgMor24_github

1export default function(d) {2  const x = +this._x.call(null, d),3      y = +this._y.call(null, d);4  return add(this.cover(x, y), x, y, d);5}6 7function add(tree, x, y, d) {8  if (isNaN(x) || isNaN(y)) return tree; // ignore invalid points9 10  var parent,11      node = tree._root,12      leaf = {data: d},13      x0 = tree._x0,14      y0 = tree._y0,15      x1 = tree._x1,16      y1 = tree._y1,17      xm,18      ym,19      xp,20      yp,21      right,22      bottom,23      i,24      j;25 26  // If the tree is empty, initialize the root as a leaf.27  if (!node) return tree._root = leaf, tree;28 29  // Find the existing leaf for the new point, or add it.30  while (node.length) {31    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;32    if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;33    if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = leaf, tree;34  }35 36  // Is the new point is exactly coincident with the existing point?37  xp = +tree._x.call(null, node.data);38  yp = +tree._y.call(null, node.data);39  if (x === xp && y === yp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree;40 41  // Otherwise, split the leaf node until the old and new point are separated.42  do {43    parent = parent ? parent[i] = new Array(4) : tree._root = new Array(4);44    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;45    if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;46  } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));47  return parent[j] = node, parent[i] = leaf, tree;48}49 50export function addAll(data) {51  var d, i, n = data.length,52      x,53      y,54      xz = new Array(n),55      yz = new Array(n),56      x0 = Infinity,57      y0 = Infinity,58      x1 = -Infinity,59      y1 = -Infinity;60 61  // Compute the points and their extent.62  for (i = 0; i < n; ++i) {63    if (isNaN(x = +this._x.call(null, d = data[i])) || isNaN(y = +this._y.call(null, d))) continue;64    xz[i] = x;65    yz[i] = y;66    if (x < x0) x0 = x;67    if (x > x1) x1 = x;68    if (y < y0) y0 = y;69    if (y > y1) y1 = y;70  }71 72  // If there were no (valid) points, abort.73  if (x0 > x1 || y0 > y1) return this;74 75  // Expand the tree to cover the new points.76  this.cover(x0, y0).cover(x1, y1);77 78  // Add the new points.79  for (i = 0; i < n; ++i) {80    add(this, xz[i], yz[i], data[i]);81  }82 83  return this;84}85