Brunobkr/llama.cpp_AlgMor24_github

1// https://d3js.org/d3-quadtree/ v3.0.1 Copyright 2010-2021 Mike Bostock2(function (global, factory) {3typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :4typeof define === 'function' && define.amd ? define(['exports'], factory) :5(global = typeof globalThis !== 'undefined' ? globalThis : global || self, factory(global.d3 = global.d3 || {}));6}(this, (function (exports) { 'use strict';7 8function tree_add(d) {9  const x = +this._x.call(null, d),10      y = +this._y.call(null, d);11  return add(this.cover(x, y), x, y, d);12}13 14function add(tree, x, y, d) {15  if (isNaN(x) || isNaN(y)) return tree; // ignore invalid points16 17  var parent,18      node = tree._root,19      leaf = {data: d},20      x0 = tree._x0,21      y0 = tree._y0,22      x1 = tree._x1,23      y1 = tree._y1,24      xm,25      ym,26      xp,27      yp,28      right,29      bottom,30      i,31      j;32 33  // If the tree is empty, initialize the root as a leaf.34  if (!node) return tree._root = leaf, tree;35 36  // Find the existing leaf for the new point, or add it.37  while (node.length) {38    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;39    if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;40    if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = leaf, tree;41  }42 43  // Is the new point is exactly coincident with the existing point?44  xp = +tree._x.call(null, node.data);45  yp = +tree._y.call(null, node.data);46  if (x === xp && y === yp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree;47 48  // Otherwise, split the leaf node until the old and new point are separated.49  do {50    parent = parent ? parent[i] = new Array(4) : tree._root = new Array(4);51    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;52    if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;53  } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));54  return parent[j] = node, parent[i] = leaf, tree;55}56 57function addAll(data) {58  var d, i, n = data.length,59      x,60      y,61      xz = new Array(n),62      yz = new Array(n),63      x0 = Infinity,64      y0 = Infinity,65      x1 = -Infinity,66      y1 = -Infinity;67 68  // Compute the points and their extent.69  for (i = 0; i < n; ++i) {70    if (isNaN(x = +this._x.call(null, d = data[i])) || isNaN(y = +this._y.call(null, d))) continue;71    xz[i] = x;72    yz[i] = y;73    if (x < x0) x0 = x;74    if (x > x1) x1 = x;75    if (y < y0) y0 = y;76    if (y > y1) y1 = y;77  }78 79  // If there were no (valid) points, abort.80  if (x0 > x1 || y0 > y1) return this;81 82  // Expand the tree to cover the new points.83  this.cover(x0, y0).cover(x1, y1);84 85  // Add the new points.86  for (i = 0; i < n; ++i) {87    add(this, xz[i], yz[i], data[i]);88  }89 90  return this;91}92 93function tree_cover(x, y) {94  if (isNaN(x = +x) || isNaN(y = +y)) return this; // ignore invalid points95 96  var x0 = this._x0,97      y0 = this._y0,98      x1 = this._x1,99      y1 = this._y1;100 101  // If the quadtree has no extent, initialize them.102  // Integer extent are necessary so that if we later double the extent,103  // the existing quadrant boundaries don’t change due to floating point error!104  if (isNaN(x0)) {105    x1 = (x0 = Math.floor(x)) + 1;106    y1 = (y0 = Math.floor(y)) + 1;107  }108 109  // Otherwise, double repeatedly to cover.110  else {111    var z = x1 - x0 || 1,112        node = this._root,113        parent,114        i;115 116    while (x0 > x || x >= x1 || y0 > y || y >= y1) {117      i = (y < y0) << 1 | (x < x0);118      parent = new Array(4), parent[i] = node, node = parent, z *= 2;119      switch (i) {120        case 0: x1 = x0 + z, y1 = y0 + z; break;121        case 1: x0 = x1 - z, y1 = y0 + z; break;122        case 2: x1 = x0 + z, y0 = y1 - z; break;123        case 3: x0 = x1 - z, y0 = y1 - z; break;124      }125    }126 127    if (this._root && this._root.length) this._root = node;128  }129 130  this._x0 = x0;131  this._y0 = y0;132  this._x1 = x1;133  this._y1 = y1;134  return this;135}136 137function tree_data() {138  var data = [];139  this.visit(function(node) {140    if (!node.length) do data.push(node.data); while (node = node.next)141  });142  return data;143}144 145function tree_extent(_) {146  return arguments.length147      ? this.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1])148      : isNaN(this._x0) ? undefined : [[this._x0, this._y0], [this._x1, this._y1]];149}150 151function Quad(node, x0, y0, x1, y1) {152  this.node = node;153  this.x0 = x0;154  this.y0 = y0;155  this.x1 = x1;156  this.y1 = y1;157}158 159function tree_find(x, y, radius) {160  var data,161      x0 = this._x0,162      y0 = this._y0,163      x1,164      y1,165      x2,166      y2,167      x3 = this._x1,168      y3 = this._y1,169      quads = [],170      node = this._root,171      q,172      i;173 174  if (node) quads.push(new Quad(node, x0, y0, x3, y3));175  if (radius == null) radius = Infinity;176  else {177    x0 = x - radius, y0 = y - radius;178    x3 = x + radius, y3 = y + radius;179    radius *= radius;180  }181 182  while (q = quads.pop()) {183 184    // Stop searching if this quadrant can’t contain a closer node.185    if (!(node = q.node)186        || (x1 = q.x0) > x3187        || (y1 = q.y0) > y3188        || (x2 = q.x1) < x0189        || (y2 = q.y1) < y0) continue;190 191    // Bisect the current quadrant.192    if (node.length) {193      var xm = (x1 + x2) / 2,194          ym = (y1 + y2) / 2;195 196      quads.push(197        new Quad(node[3], xm, ym, x2, y2),198        new Quad(node[2], x1, ym, xm, y2),199        new Quad(node[1], xm, y1, x2, ym),200        new Quad(node[0], x1, y1, xm, ym)201      );202 203      // Visit the closest quadrant first.204      if (i = (y >= ym) << 1 | (x >= xm)) {205        q = quads[quads.length - 1];206        quads[quads.length - 1] = quads[quads.length - 1 - i];207        quads[quads.length - 1 - i] = q;208      }209    }210 211    // Visit this point. (Visiting coincident points isn’t necessary!)212    else {213      var dx = x - +this._x.call(null, node.data),214          dy = y - +this._y.call(null, node.data),215          d2 = dx * dx + dy * dy;216      if (d2 < radius) {217        var d = Math.sqrt(radius = d2);218        x0 = x - d, y0 = y - d;219        x3 = x + d, y3 = y + d;220        data = node.data;221      }222    }223  }224 225  return data;226}227 228function tree_remove(d) {229  if (isNaN(x = +this._x.call(null, d)) || isNaN(y = +this._y.call(null, d))) return this; // ignore invalid points230 231  var parent,232      node = this._root,233      retainer,234      previous,235      next,236      x0 = this._x0,237      y0 = this._y0,238      x1 = this._x1,239      y1 = this._y1,240      x,241      y,242      xm,243      ym,244      right,245      bottom,246      i,247      j;248 249  // If the tree is empty, initialize the root as a leaf.250  if (!node) return this;251 252  // Find the leaf node for the point.253  // While descending, also retain the deepest parent with a non-removed sibling.254  if (node.length) while (true) {255    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;256    if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;257    if (!(parent = node, node = node[i = bottom << 1 | right])) return this;258    if (!node.length) break;259    if (parent[(i + 1) & 3] || parent[(i + 2) & 3] || parent[(i + 3) & 3]) retainer = parent, j = i;260  }261 262  // Find the point to remove.263  while (node.data !== d) if (!(previous = node, node = node.next)) return this;264  if (next = node.next) delete node.next;265 266  // If there are multiple coincident points, remove just the point.267  if (previous) return (next ? previous.next = next : delete previous.next), this;268 269  // If this is the root point, remove it.270  if (!parent) return this._root = next, this;271 272  // Remove this leaf.273  next ? parent[i] = next : delete parent[i];274 275  // If the parent now contains exactly one leaf, collapse superfluous parents.276  if ((node = parent[0] || parent[1] || parent[2] || parent[3])277      && node === (parent[3] || parent[2] || parent[1] || parent[0])278      && !node.length) {279    if (retainer) retainer[j] = node;280    else this._root = node;281  }282 283  return this;284}285 286function removeAll(data) {287  for (var i = 0, n = data.length; i < n; ++i) this.remove(data[i]);288  return this;289}290 291function tree_root() {292  return this._root;293}294 295function tree_size() {296  var size = 0;297  this.visit(function(node) {298    if (!node.length) do ++size; while (node = node.next)299  });300  return size;301}302 303function tree_visit(callback) {304  var quads = [], q, node = this._root, child, x0, y0, x1, y1;305  if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1));306  while (q = quads.pop()) {307    if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1) && node.length) {308      var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;309      if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));310      if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));311      if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));312      if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));313    }314  }315  return this;316}317 318function tree_visitAfter(callback) {319  var quads = [], next = [], q;320  if (this._root) quads.push(new Quad(this._root, this._x0, this._y0, this._x1, this._y1));321  while (q = quads.pop()) {322    var node = q.node;323    if (node.length) {324      var child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;325      if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));326      if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));327      if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));328      if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));329    }330    next.push(q);331  }332  while (q = next.pop()) {333    callback(q.node, q.x0, q.y0, q.x1, q.y1);334  }335  return this;336}337 338function defaultX(d) {339  return d[0];340}341 342function tree_x(_) {343  return arguments.length ? (this._x = _, this) : this._x;344}345 346function defaultY(d) {347  return d[1];348}349 350function tree_y(_) {351  return arguments.length ? (this._y = _, this) : this._y;352}353 354function quadtree(nodes, x, y) {355  var tree = new Quadtree(x == null ? defaultX : x, y == null ? defaultY : y, NaN, NaN, NaN, NaN);356  return nodes == null ? tree : tree.addAll(nodes);357}358 359function Quadtree(x, y, x0, y0, x1, y1) {360  this._x = x;361  this._y = y;362  this._x0 = x0;363  this._y0 = y0;364  this._x1 = x1;365  this._y1 = y1;366  this._root = undefined;367}368 369function leaf_copy(leaf) {370  var copy = {data: leaf.data}, next = copy;371  while (leaf = leaf.next) next = next.next = {data: leaf.data};372  return copy;373}374 375var treeProto = quadtree.prototype = Quadtree.prototype;376 377treeProto.copy = function() {378  var copy = new Quadtree(this._x, this._y, this._x0, this._y0, this._x1, this._y1),379      node = this._root,380      nodes,381      child;382 383  if (!node) return copy;384 385  if (!node.length) return copy._root = leaf_copy(node), copy;386 387  nodes = [{source: node, target: copy._root = new Array(4)}];388  while (node = nodes.pop()) {389    for (var i = 0; i < 4; ++i) {390      if (child = node.source[i]) {391        if (child.length) nodes.push({source: child, target: node.target[i] = new Array(4)});392        else node.target[i] = leaf_copy(child);393      }394    }395  }396 397  return copy;398};399 400treeProto.add = tree_add;401treeProto.addAll = addAll;402treeProto.cover = tree_cover;403treeProto.data = tree_data;404treeProto.extent = tree_extent;405treeProto.find = tree_find;406treeProto.remove = tree_remove;407treeProto.removeAll = removeAll;408treeProto.root = tree_root;409treeProto.size = tree_size;410treeProto.visit = tree_visit;411treeProto.visitAfter = tree_visitAfter;412treeProto.x = tree_x;413treeProto.y = tree_y;414 415exports.quadtree = quadtree;416 417Object.defineProperty(exports, '__esModule', { value: true });418 419})));420