@thi.ng/geom-accel - npm Package Compare versions

Comparing version 1.2.6 to 1.2.7

CHANGELOG.md

@@ -6,2 +6,10 @@ # Change Log
 
+## [1.2.7](https://github.com/thi-ng/umbrella/compare/@thi.ng/geom-accel@[e-mail]/geom-accel@1.2.7) (2019-08-21)
+
+**Note:** Version bump only for package @thi.ng/geom-accel
+
+
+
+
+
 ## [1.2.6](https://github.com/thi-ng/umbrella/compare/@thi.ng/geom-accel@[e-mail]/geom-accel@1.2.6) (2019-08-17)
@@ -8,0 +16,0 @@

kdtree.d.ts

@@ -1,2 +0,2 @@
-import { ICopy, Pair } from "@thi.ng/api";
+import { Fn, ICopy, Pair } from "@thi.ng/api";
 import { ISpatialAccel } from "@thi.ng/geom-api";
@@ -44,4 +44,5 @@ import { ReadonlyVec } from "@thi.ng/vectors";
     protected buildSelection(q: Readonly<K>, maxNum: number, maxDist?: number): [number, KdNode<K, V> | null][];
+    protected doSelect<T>(q: Readonly<K>, f: Fn<KdNode<K, V>, T>, maxNum: number, maxDist?: number): T[];
     protected buildTree(points: Pair<K, V>[], depth: number, parent: KdNode<K, V> | null): KdNode<K, V> | null;
 }
 export {};

kdtree.js

@@ -71,3 +71,3 @@ import { ensureArray } from "@thi.ng/arrays";
         if (this.root) {
-            parent = nearest1(p, [eps * eps, null], [], this.dim, this.root)[1];
+            parent = nearest1(p, [eps * eps, null], this.dim, this.root)[1];
             if (parent) {
@@ -114,54 +114,12 @@ return false;
         return (!!this.root &&
-            !!nearest1(k, [eps * eps, null], [], this.dim, this.root)[1]);
+            !!nearest1(k, [eps * eps, null], this.dim, this.root)[1]);
     }
     select(q, maxNum, maxDist) {
-        if (!this.root)
-            return [];
-        const res = [];
-        if (maxNum === 1) {
-            const sel = nearest1(q, [maxDist != null ? maxDist * maxDist : Infinity, null], [], this.dim, this.root)[1];
-            sel && res.push([sel.k, sel.v]);
-        }
-        else {
-            const sel = this.buildSelection(q, maxNum, maxDist);
-            for (let n = sel.length; --n >= 0;) {
-                const nn = sel[n][1];
-                nn && res.push([nn.k, nn.v]);
-            }
-        }
-        return res;
+        return this.doSelect(q, (x) => [x.k, x.v], maxNum, maxDist);
     }
     selectKeys(q, maxNum, maxDist) {
-        if (!this.root)
-            return [];
-        const res = [];
-        if (maxNum === 1) {
-            const sel = nearest1(q, [maxDist != null ? maxDist * maxDist : Infinity, null], [], this.dim, this.root)[1];
-            sel && res.push(sel.k);
-        }
-        else {
-            const src = this.buildSelection(q, maxNum, maxDist);
-            for (let n = src.length; --n >= 0;) {
-                const nn = src[n][1];
-                nn && res.push(nn.k);
-            }
-        }
-        return res;
+        return this.doSelect(q, (x) => x.k, maxNum, maxDist);
     }
     selectVals(q, maxNum, maxDist) {
-        if (!this.root)
-            return [];
-        const res = [];
-        if (maxNum === 1) {
-            const sel = nearest1(q, [maxDist != null ? maxDist * maxDist : Infinity, null], [], this.dim, this.root)[1];
-            sel && res.push(sel.v);
-        }
-        else {
-            const src = this.buildSelection(q, maxNum, maxDist);
-            for (let n = src.length; --n >= 0;) {
-                const nn = src[n][1];
-                nn && res.push(nn.v);
-            }
-        }
-        return res;
+        return this.doSelect(q, (x) => x.v, maxNum, maxDist);
     }
@@ -182,5 +140,22 @@ balanceRatio() {
         }
-        nearest(q, nodes, [], this.dim, maxNum, this.root);
+        nearest(q, nodes, this.dim, maxNum, this.root);
         return nodes.values.sort(CMP);
     }
+    doSelect(q, f, maxNum, maxDist) {
+        if (!this.root)
+            return [];
+        const res = [];
+        if (maxNum === 1) {
+            const sel = nearest1(q, [maxDist != null ? maxDist * maxDist : Infinity, null], this.dim, this.root)[1];
+            sel && res.push(f(sel));
+        }
+        else {
+            const sel = this.buildSelection(q, maxNum, maxDist);
+            for (let n = sel.length; --n >= 0;) {
+                const s = sel[n][1];
+                s && res.push(f(s));
+            }
+        }
+        return res;
+    }
     buildTree(points, depth, parent) {
@@ -268,40 +243,16 @@ const n = points.length;
 };
-const nearest = (q, acc, tmp, dims, maxNum, node) => {
+const nearest = (q, acc, dims, maxNum, node) => {
     const p = node.k;
     const ndist = distSq(p, q);
     if (!node.l && !node.r) {
-        if (!acc.length || ndist < acc.peek()[0]) {
-            if (acc.length >= maxNum) {
-                acc.pushPop([ndist, node]);
-            }
-            else {
-                acc.push([ndist, node]);
-            }
-        }
+        collect(acc, node, maxNum, ndist);
         return;
     }
-    const ndim = node.d;
-    for (let i = dims; --i >= 0;) {
-        tmp[i] = i === ndim ? q[i] : p[i];
-    }
-    const tdist = distSq(p, tmp);
-    let best = !node.r
-        ? node.l
-        : !node.l
-            ? node.r
-            : q[ndim] < p[ndim]
-                ? node.l
-                : node.r;
-    nearest(q, acc, tmp, dims, maxNum, best);
-    if (!acc.length || ndist < acc.peek()[0]) {
-        if (acc.length >= maxNum) {
-            acc.pushPop([ndist, node]);
-        }
-        else {
-            acc.push([ndist, node]);
-        }
-    }
+    const tdist = nodeDist(node, dims, q, p);
+    let best = bestChild(node, q);
+    nearest(q, acc, dims, maxNum, best);
+    collect(acc, node, maxNum, ndist);
     if (!acc.length || tdist < acc.peek()[0]) {
         best = best === node.l ? node.r : node.l;
-        best && nearest(q, acc, tmp, dims, maxNum, best);
+        best && nearest(q, acc, dims, maxNum, best);
     }
@@ -317,34 +268,40 @@ };
  */
-const nearest1 = (q, acc, tmp, dims, node) => {
+const nearest1 = (q, acc, dims, node) => {
     const p = node.k;
     const ndist = distSq(p, q);
     if (!node.l && !node.r) {
-        if (ndist < acc[0]) {
-            acc[0] = ndist;
-            acc[1] = node;
-        }
+        collect1(acc, node, ndist);
         return acc;
     }
-    const ndim = node.d;
-    for (let i = dims; --i >= 0;) {
-        tmp[i] = i === ndim ? q[i] : p[i];
+    const tdist = nodeDist(node, dims, q, p);
+    let best = bestChild(node, q);
+    nearest1(q, acc, dims, best);
+    collect1(acc, node, ndist);
+    if (tdist < acc[0]) {
+        best = best === node.l ? node.r : node.l;
+        best && nearest1(q, acc, dims, best);
     }
-    const tdist = distSq(p, tmp);
-    let best = !node.r
+    return acc;
+};
+const bestChild = (node, q) => {
+    const d = node.d;
+    return !node.r
         ? node.l
         : !node.l
             ? node.r
-            : q[ndim] < p[ndim]
+            : q[d] < node.k[d]
                 ? node.l
                 : node.r;
-    nearest1(q, acc, tmp, dims, best);
-    if (ndist < acc[0]) {
-        acc[0] = ndist;
-        acc[1] = node;
+};
+const collect = (acc, node, maxNum, ndist) => (!acc.length || ndist < acc.peek()[0]) &&
+    (acc.length >= maxNum
+        ? acc.pushPop([ndist, node])
+        : acc.push([ndist, node]));
+const collect1 = (acc, node, ndist) => ndist < acc[0] && ((acc[0] = ndist), (acc[1] = node));
+const TMP = [];
+const nodeDist = (node, dims, q, p) => {
+    for (let i = dims, d = node.d; --i >= 0;) {
+        TMP[i] = i === d ? q[i] : p[i];
     }
-    if (tdist < acc[0]) {
-        best = best === node.l ? node.r : node.l;
-        best && nearest1(q, acc, tmp, dims, best);
-    }
-    return acc;
+    return distSq(TMP, p);
 };

lib/index.js

@@ -69,3 +69,3 @@ 'use strict';
         if (this.root) {
-            parent = nearest1(p, [eps * eps, null], [], this.dim, this.root)[1];
+            parent = nearest1(p, [eps * eps, null], this.dim, this.root)[1];
             if (parent) {
@@ -112,54 +112,12 @@ return false;
         return (!!this.root &&
-            !!nearest1(k, [eps * eps, null], [], this.dim, this.root)[1]);
+            !!nearest1(k, [eps * eps, null], this.dim, this.root)[1]);
     }
     select(q, maxNum, maxDist) {
-        if (!this.root)
-            return [];
-        const res = [];
-        if (maxNum === 1) {
-            const sel = nearest1(q, [maxDist != null ? maxDist * maxDist : Infinity, null], [], this.dim, this.root)[1];
-            sel && res.push([sel.k, sel.v]);
-        }
-        else {
-            const sel = this.buildSelection(q, maxNum, maxDist);
-            for (let n = sel.length; --n >= 0;) {
-                const nn = sel[n][1];
-                nn && res.push([nn.k, nn.v]);
-            }
-        }
-        return res;
+        return this.doSelect(q, (x) => [x.k, x.v], maxNum, maxDist);
     }
     selectKeys(q, maxNum, maxDist) {
-        if (!this.root)
-            return [];
-        const res = [];
-        if (maxNum === 1) {
-            const sel = nearest1(q, [maxDist != null ? maxDist * maxDist : Infinity, null], [], this.dim, this.root)[1];
-            sel && res.push(sel.k);
-        }
-        else {
-            const src = this.buildSelection(q, maxNum, maxDist);
-            for (let n = src.length; --n >= 0;) {
-                const nn = src[n][1];
-                nn && res.push(nn.k);
-            }
-        }
-        return res;
+        return this.doSelect(q, (x) => x.k, maxNum, maxDist);
     }
     selectVals(q, maxNum, maxDist) {
-        if (!this.root)
-            return [];
-        const res = [];
-        if (maxNum === 1) {
-            const sel = nearest1(q, [maxDist != null ? maxDist * maxDist : Infinity, null], [], this.dim, this.root)[1];
-            sel && res.push(sel.v);
-        }
-        else {
-            const src = this.buildSelection(q, maxNum, maxDist);
-            for (let n = src.length; --n >= 0;) {
-                const nn = src[n][1];
-                nn && res.push(nn.v);
-            }
-        }
-        return res;
+        return this.doSelect(q, (x) => x.v, maxNum, maxDist);
     }
@@ -180,5 +138,22 @@ balanceRatio() {
         }
-        nearest(q, nodes, [], this.dim, maxNum, this.root);
+        nearest(q, nodes, this.dim, maxNum, this.root);
         return nodes.values.sort(CMP);
     }
+    doSelect(q, f, maxNum, maxDist) {
+        if (!this.root)
+            return [];
+        const res = [];
+        if (maxNum === 1) {
+            const sel = nearest1(q, [maxDist != null ? maxDist * maxDist : Infinity, null], this.dim, this.root)[1];
+            sel && res.push(f(sel));
+        }
+        else {
+            const sel = this.buildSelection(q, maxNum, maxDist);
+            for (let n = sel.length; --n >= 0;) {
+                const s = sel[n][1];
+                s && res.push(f(s));
+            }
+        }
+        return res;
+    }
     buildTree(points, depth, parent) {
@@ -254,74 +229,56 @@ const n = points.length;
 };
-const nearest = (q, acc, tmp, dims, maxNum, node) => {
+const nearest = (q, acc, dims, maxNum, node) => {
     const p = node.k;
     const ndist = vectors.distSq(p, q);
     if (!node.l && !node.r) {
-        if (!acc.length || ndist < acc.peek()[0]) {
-            if (acc.length >= maxNum) {
-                acc.pushPop([ndist, node]);
-            }
-            else {
-                acc.push([ndist, node]);
-            }
-        }
+        collect(acc, node, maxNum, ndist);
         return;
     }
-    const ndim = node.d;
-    for (let i = dims; --i >= 0;) {
-        tmp[i] = i === ndim ? q[i] : p[i];
-    }
-    const tdist = vectors.distSq(p, tmp);
-    let best = !node.r
-        ? node.l
-        : !node.l
-            ? node.r
-            : q[ndim] < p[ndim]
-                ? node.l
-                : node.r;
-    nearest(q, acc, tmp, dims, maxNum, best);
-    if (!acc.length || ndist < acc.peek()[0]) {
-        if (acc.length >= maxNum) {
-            acc.pushPop([ndist, node]);
-        }
-        else {
-            acc.push([ndist, node]);
-        }
-    }
+    const tdist = nodeDist(node, dims, q, p);
+    let best = bestChild(node, q);
+    nearest(q, acc, dims, maxNum, best);
+    collect(acc, node, maxNum, ndist);
     if (!acc.length || tdist < acc.peek()[0]) {
         best = best === node.l ? node.r : node.l;
-        best && nearest(q, acc, tmp, dims, maxNum, best);
+        best && nearest(q, acc, dims, maxNum, best);
     }
 };
-const nearest1 = (q, acc, tmp, dims, node) => {
+const nearest1 = (q, acc, dims, node) => {
     const p = node.k;
     const ndist = vectors.distSq(p, q);
     if (!node.l && !node.r) {
-        if (ndist < acc[0]) {
-            acc[0] = ndist;
-            acc[1] = node;
-        }
+        collect1(acc, node, ndist);
         return acc;
     }
-    const ndim = node.d;
-    for (let i = dims; --i >= 0;) {
-        tmp[i] = i === ndim ? q[i] : p[i];
+    const tdist = nodeDist(node, dims, q, p);
+    let best = bestChild(node, q);
+    nearest1(q, acc, dims, best);
+    collect1(acc, node, ndist);
+    if (tdist < acc[0]) {
+        best = best === node.l ? node.r : node.l;
+        best && nearest1(q, acc, dims, best);
     }
-    const tdist = vectors.distSq(p, tmp);
-    let best = !node.r
+    return acc;
+};
+const bestChild = (node, q) => {
+    const d = node.d;
+    return !node.r
         ? node.l
         : !node.l
             ? node.r
-            : q[ndim] < p[ndim]
+            : q[d] < node.k[d]
                 ? node.l
                 : node.r;
-    nearest1(q, acc, tmp, dims, best);
-    if (ndist < acc[0]) {
-        acc[0] = ndist;
-        acc[1] = node;
+};
+const collect = (acc, node, maxNum, ndist) => (!acc.length || ndist < acc.peek()[0]) &&
+    (acc.length >= maxNum
+        ? acc.pushPop([ndist, node])
+        : acc.push([ndist, node]));
+const collect1 = (acc, node, ndist) => ndist < acc[0] && ((acc[0] = ndist), (acc[1] = node));
+const TMP = [];
+const nodeDist = (node, dims, q, p) => {
+    for (let i = dims, d = node.d; --i >= 0;) {
+        TMP[i] = i === d ? q[i] : p[i];
     }
-    if (tdist < acc[0]) {
-        best = best === node.l ? node.r : node.l;
-        best && nearest1(q, acc, tmp, dims, best);
-    }
-    return acc;
+    return vectors.distSq(TMP, p);
 };
@@ -328,0 +285,0 @@

lib/index.umd.js

@@ -1,1 +0,1 @@
-!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports,require("@thi.ng/arrays"),require("@thi.ng/heaps"),require("@thi.ng/math"),require("@thi.ng/vectors")):"function"==typeof define&&define.amd?define(["exports","@thi.ng/arrays","@thi.ng/heaps","@thi.ng/math","@thi.ng/vectors"],e):e(((t=t||self).thi=t.thi||{},t.thi.ng=t.thi.ng||{},t.thi.ng.geomAccel={}),t.thi.ng.arrays,t.thi.ng.heaps,t.thi.ng.math,t.thi.ng.vectors)}(this,function(t,e,r,l,s){"use strict";const i=(t,e)=>e[0]-t[0];class n{constructor(t,e,r,l){this.parent=t,this.d=e,this.k=r,this.v=l,this.l=this.r=null}*[Symbol.iterator](){let t=[this];for(;t.length;){const e=t.pop();e&&(yield[e.k,e.v],t.push(e.r,e.l))}}*keys(){let t=[this];for(;t.length;){const e=t.pop();e&&(yield e.k,t.push(e.r,e.l))}}height(){return 1+Math.max(this.l?this.l.height():0,this.r?this.r.height():0)}}class o{constructor(t,r){this.dim=t,this._length=0,this.root=r?this.buildTree(e.ensureArray(r),0,null):null}[Symbol.iterator](){return(this.root||[])[Symbol.iterator]()}keys(){return this.root?this.root.keys():[][Symbol.iterator]()}get length(){return this._length}copy(){return new o(this.dim,this)}add(t,e,r=l.EPS){r*=r;const s=(e,r)=>e?s(t[e.d]<e.k[e.d]?e.l:e.r,e):r;let i;if(this.root){if(i=a(t,[r*r,null],[],this.dim,this.root)[1])return!1;const l=(i=s(this.root,null)).d;i[t[l]<i.k[l]?"l":"r"]=new n(i,(l+1)%this.dim,t,e)}else this.root=new n(null,0,t,e);return this._length++,!0}addAll(t,e=l.EPS){let r=!0;for(let[l,s]of t)r=this.add(l,s,e)&&r;return r}addKey(t,e=l.EPS){return this.add(t,null,e)}addKeys(t,e=l.EPS){let r=!0;for(let l of t)r=this.add(l,null,e)&&r;return r}remove(t){const e=h(t,this.root,0);return!!e&&(d(e)&&(this.root=null),this._length--,!0)}has(t,e=l.EPS){return!!this.root&&!!a(t,[e*e,null],[],this.dim,this.root)[1]}select(t,e,r){if(!this.root)return[];const l=[];if(1===e){const e=a(t,[null!=r?r*r:1/0,null],[],this.dim,this.root)[1];e&&l.push([e.k,e.v])}else{const s=this.buildSelection(t,e,r);for(let t=s.length;--t>=0;){const e=s[t][1];e&&l.push([e.k,e.v])}}return l}selectKeys(t,e,r){if(!this.root)return[];const l=[];if(1===e){const e=a(t,[null!=r?r*r:1/0,null],[],this.dim,this.root)[1];e&&l.push(e.k)}else{const s=this.buildSelection(t,e,r);for(let t=s.length;--t>=0;){const e=s[t][1];e&&l.push(e.k)}}return l}selectVals(t,e,r){if(!this.root)return[];const l=[];if(1===e){const e=a(t,[null!=r?r*r:1/0,null],[],this.dim,this.root)[1];e&&l.push(e.v)}else{const s=this.buildSelection(t,e,r);for(let t=s.length;--t>=0;){const e=s[t][1];e&&l.push(e.v)}}return l}balanceRatio(){return this._length?this.root.height()/(Math.log(this._length)/Math.LN2):0}buildSelection(t,e,l=1/0){const s=new r.Heap(null,{compare:i}),n=[l*=l,null];for(let t=e;--t>=0;)s.push(n);return c(t,s,[],this.dim,e,this.root),s.values.sort(i)}buildTree(t,e,r){const l=t.length;if(0===l)return null;this._length++;let s=e%this.dim;if(1===l)return new n(r,s,...t[0]);t.sort((t,e)=>t[0][s]-e[0][s]);const i=l>>>1,o=new n(r,s,...t[i]);return o.l=this.buildTree(t.slice(0,i),e+1,o),o.r=this.buildTree(t.slice(i+1),e+1,o),o}}const h=(t,e,r)=>{if(e)return s.distSq(t,e.k)<=r?e:h(t,t[e.d]<e.k[e.d]?e.l:e.r,r)},u=(t,e)=>{if(!t)return null;if(t.d===e)return t.l?u(t.l,e):t;const r=t.k[e],l=u(t.l,e),s=u(t.r,e);let i=t;return l&&l.k[e]<r&&(i=l),s&&s.k[e]<i.k[e]&&(i=s),i},d=t=>{if(!t.l&&!t.r){if(!t.parent)return!0;const e=t.parent,r=e.d;return void(e[t.k[r]<e.k[r]?"l":"r"]=null)}let e,r;t.r?(r=(e=u(t.r,t.d)).k,d(e),t.k=r):(r=(e=u(t.l,t.d)).k,d(e),t.r=t.l,t.l=null,t.k=r)},c=(t,e,r,l,i,n)=>{const o=n.k,h=s.distSq(o,t);if(!n.l&&!n.r)return void((!e.length||h<e.peek()[0])&&(e.length>=i?e.pushPop([h,n]):e.push([h,n])));const u=n.d;for(let e=l;--e>=0;)r[e]=e===u?t[e]:o[e];const d=s.distSq(o,r);let a=n.r?n.l&&t[u]<o[u]?n.l:n.r:n.l;c(t,e,r,l,i,a),(!e.length||h<e.peek()[0])&&(e.length>=i?e.pushPop([h,n]):e.push([h,n])),(!e.length||d<e.peek()[0])&&(a=a===n.l?n.r:n.l)&&c(t,e,r,l,i,a)},a=(t,e,r,l,i)=>{const n=i.k,o=s.distSq(n,t);if(!i.l&&!i.r)return o<e[0]&&(e[0]=o,e[1]=i),e;const h=i.d;for(let e=l;--e>=0;)r[e]=e===h?t[e]:n[e];const u=s.distSq(n,r);let d=i.r?i.l&&t[h]<n[h]?i.l:i.r:i.l;return a(t,e,r,l,d),o<e[0]&&(e[0]=o,e[1]=i),u<e[0]&&(d=d===i.l?i.r:i.l)&&a(t,e,r,l,d),e};t.KdNode=n,t.KdTree=o,Object.defineProperty(t,"__esModule",{value:!0})});
+!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports,require("@thi.ng/arrays"),require("@thi.ng/heaps"),require("@thi.ng/math"),require("@thi.ng/vectors")):"function"==typeof define&&define.amd?define(["exports","@thi.ng/arrays","@thi.ng/heaps","@thi.ng/math","@thi.ng/vectors"],e):e(((t=t||self).thi=t.thi||{},t.thi.ng=t.thi.ng||{},t.thi.ng.geomAccel={}),t.thi.ng.arrays,t.thi.ng.heaps,t.thi.ng.math,t.thi.ng.vectors)}(this,function(t,e,r,i,l){"use strict";const n=(t,e)=>e[0]-t[0];class s{constructor(t,e,r,i){this.parent=t,this.d=e,this.k=r,this.v=i,this.l=this.r=null}*[Symbol.iterator](){let t=[this];for(;t.length;){const e=t.pop();e&&(yield[e.k,e.v],t.push(e.r,e.l))}}*keys(){let t=[this];for(;t.length;){const e=t.pop();e&&(yield e.k,t.push(e.r,e.l))}}height(){return 1+Math.max(this.l?this.l.height():0,this.r?this.r.height():0)}}class h{constructor(t,r){this.dim=t,this._length=0,this.root=r?this.buildTree(e.ensureArray(r),0,null):null}[Symbol.iterator](){return(this.root||[])[Symbol.iterator]()}keys(){return this.root?this.root.keys():[][Symbol.iterator]()}get length(){return this._length}copy(){return new h(this.dim,this)}add(t,e,r=i.EPS){r*=r;const l=(e,r)=>e?l(t[e.d]<e.k[e.d]?e.l:e.r,e):r;let n;if(this.root){if(n=a(t,[r*r,null],this.dim,this.root)[1])return!1;const i=(n=l(this.root,null)).d;n[t[i]<n.k[i]?"l":"r"]=new s(n,(i+1)%this.dim,t,e)}else this.root=new s(null,0,t,e);return this._length++,!0}addAll(t,e=i.EPS){let r=!0;for(let[i,l]of t)r=this.add(i,l,e)&&r;return r}addKey(t,e=i.EPS){return this.add(t,null,e)}addKeys(t,e=i.EPS){let r=!0;for(let i of t)r=this.add(i,null,e)&&r;return r}remove(t){const e=o(t,this.root,0);return!!e&&(d(e)&&(this.root=null),this._length--,!0)}has(t,e=i.EPS){return!!this.root&&!!a(t,[e*e,null],this.dim,this.root)[1]}select(t,e,r){return this.doSelect(t,t=>[t.k,t.v],e,r)}selectKeys(t,e,r){return this.doSelect(t,t=>t.k,e,r)}selectVals(t,e,r){return this.doSelect(t,t=>t.v,e,r)}balanceRatio(){return this._length?this.root.height()/(Math.log(this._length)/Math.LN2):0}buildSelection(t,e,i=1/0){const l=new r.Heap(null,{compare:n}),s=[i*=i,null];for(let t=e;--t>=0;)l.push(s);return c(t,l,this.dim,e,this.root),l.values.sort(n)}doSelect(t,e,r,i){if(!this.root)return[];const l=[];if(1===r){const r=a(t,[null!=i?i*i:1/0,null],this.dim,this.root)[1];r&&l.push(e(r))}else{const n=this.buildSelection(t,r,i);for(let t=n.length;--t>=0;){const r=n[t][1];r&&l.push(e(r))}}return l}buildTree(t,e,r){const i=t.length;if(0===i)return null;this._length++;let l=e%this.dim;if(1===i)return new s(r,l,...t[0]);t.sort((t,e)=>t[0][l]-e[0][l]);const n=i>>>1,h=new s(r,l,...t[n]);return h.l=this.buildTree(t.slice(0,n),e+1,h),h.r=this.buildTree(t.slice(n+1),e+1,h),h}}const o=(t,e,r)=>{if(e)return l.distSq(t,e.k)<=r?e:o(t,t[e.d]<e.k[e.d]?e.l:e.r,r)},u=(t,e)=>{if(!t)return null;if(t.d===e)return t.l?u(t.l,e):t;const r=t.k[e],i=u(t.l,e),l=u(t.r,e);let n=t;return i&&i.k[e]<r&&(n=i),l&&l.k[e]<n.k[e]&&(n=l),n},d=t=>{if(!t.l&&!t.r){if(!t.parent)return!0;const e=t.parent,r=e.d;return void(e[t.k[r]<e.k[r]?"l":"r"]=null)}let e,r;t.r?(r=(e=u(t.r,t.d)).k,d(e),t.k=r):(r=(e=u(t.l,t.d)).k,d(e),t.r=t.l,t.l=null,t.k=r)},c=(t,e,r,i,n)=>{const s=n.k,h=l.distSq(s,t);if(!n.l&&!n.r)return void f(e,n,i,h);const o=m(n,r,t,s);let u=g(n,t);c(t,e,r,i,u),f(e,n,i,h),(!e.length||o<e.peek()[0])&&(u=u===n.l?n.r:n.l)&&c(t,e,r,i,u)},a=(t,e,r,i)=>{const n=i.k,s=l.distSq(n,t);if(!i.l&&!i.r)return p(e,i,s),e;const h=m(i,r,t,n);let o=g(i,t);return a(t,e,r,o),p(e,i,s),h<e[0]&&(o=o===i.l?i.r:i.l)&&a(t,e,r,o),e},g=(t,e)=>{const r=t.d;return t.r?t.l&&e[r]<t.k[r]?t.l:t.r:t.l},f=(t,e,r,i)=>(!t.length||i<t.peek()[0])&&(t.length>=r?t.pushPop([i,e]):t.push([i,e])),p=(t,e,r)=>r<t[0]&&(t[0]=r,t[1]=e),k=[],m=(t,e,r,i)=>{for(let l=e,n=t.d;--l>=0;)k[l]=l===n?r[l]:i[l];return l.distSq(k,i)};t.KdNode=s,t.KdTree=h,Object.defineProperty(t,"__esModule",{value:!0})});

package.json

 {
     "name": "@thi.ng/geom-accel",
-    "version": "1.2.6",
+    "version": "1.2.7",
     "description": "nD spatial indexing data structures",
@@ -36,9 +36,9 @@ "module": "./index.js",
     "dependencies": {
-        "@thi.ng/api": "^6.3.2",
-        "@thi.ng/arrays": "^0.2.3",
-        "@thi.ng/geom-api": "^0.3.4",
-        "@thi.ng/heaps": "^1.1.2",
+        "@thi.ng/api": "^6.3.3",
+        "@thi.ng/arrays": "^0.2.4",
+        "@thi.ng/geom-api": "^0.3.5",
+        "@thi.ng/heaps": "^1.1.3",
         "@thi.ng/math": "^1.4.2",
-        "@thi.ng/transducers": "^5.4.3",
-        "@thi.ng/vectors": "^3.2.0"
+        "@thi.ng/transducers": "^5.4.4",
+        "@thi.ng/vectors": "^3.3.0"
     },
@@ -62,3 +62,3 @@ "keywords": [
     "sideEffects": false,
-    "gitHead": "4b74159d35209356ce8f44929599b45ba64277be"
+    "gitHead": "161b4f8afaef0df742a8e2c7776993b828662589"
 }

No alert changes

Worsened metrics

Total package byte prevSize

67029

decreased by-6.94%

Lines of code

630

decreased by-11.89%

Dependency changes

• [e-mail]/api@^6.3.3

• [e-mail]/arrays@^0.2.4

• [e-mail]/geom-api@^0.3.5

• [e-mail]/heaps@^1.1.3

• [e-mail]/transducers@^5.4.4

• [e-mail]/vectors@^3.3.0