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

Comparing version 3.6.4 to 4.0.0

aspatial-grid.d.ts

 import type { Fn, Nullable, Pair } from "@thi.ng/api";
-import type { IRegionQuery, ISpatialMap } from "@thi.ng/geom-api";
 import type { Heap } from "@thi.ng/heaps";
 import type { ReadonlyVec, VecOpRoVV } from "@thi.ng/vectors";
+import type { IRegionQuery, ISpatialMap } from "./api.js";
 /**
@@ -6,0 +6,0 @@ * Common base class for {@link SpatialGrid2} and {@link SpatialGrid3}.

CHANGELOG.md

 # Change Log
 
-- **Last updated**: 2024-05-08T18:24:31Z
+- **Last updated**: 2024-06-21T19:34:38Z
 - **Generator**: [thi.ng/monopub](https://thi.ng/monopub)
@@ -12,2 +12,17 @@
 
+# [4.0.0](https://github.com/thi-ng/umbrella/tree/@thi.ng/geom-accel@4.0.0) (2024-06-21)
+
+#### 🛑 Breaking changes
+
+- migrate types from [@thi.ng/geom-api](https://github.com/thi-ng/umbrella/tree/main/packages/geom-api) ([6882260](https://github.com/thi-ng/umbrella/commit/6882260))
+- BREAKING CHANGE: migrate/internalize types from [@thi.ng/geom-api](https://github.com/thi-ng/umbrella/tree/main/packages/geom-api)
+  - add/migrate ISpatialMap, ISpatialSet, IRegionQuery
+  - update imports
+  - update deps
+
+#### ♻️ Refactoring
+
+- minor internal update NdQtNode.doQuery() ([b95ca8e](https://github.com/thi-ng/umbrella/commit/b95ca8e))
+- enforce uniform naming convention of internal functions ([56992b2](https://github.com/thi-ng/umbrella/commit/56992b2))
+
 ## [3.6.0](https://github.com/thi-ng/umbrella/tree/@thi.ng/geom-accel@3.6.0) (2024-04-20)
@@ -14,0 +29,0 @@

hash-grid.d.ts

@@ -78,3 +78,3 @@ import type { Fn, IEmpty, Predicate2 } from "@thi.ng/api";
      * @example
-     * ```ts
+     * ```ts tangle:../export/query-neighborhood.ts
      * import { knearest2 } from "@thi.ng/distance";
@@ -93,8 +93,12 @@ * import { HashGrid2 } from "@thi.ng/geom-accel";
      * // perform k-nearest neighbor search around origin (k=5, radius=200)
-     * grid.queryNeighborhood(knearest2([0, 0], 5, 200)).values();
-     * // [-12.65, 26.19]
-     * // [1.94, 28.09]
-     * // [-17.49, -8.76]
-     * // [-14.55, 8.17]
-     * // [8.09, 17.47]
+     * console.log(
+     *   grid.queryNeighborhood(knearest2([0, 0], 5, 200)).values()
+     * );
+     * // [
+     * //   [-12.65, 26.19]
+     * //   [1.94, 28.09]
+     * //   [-17.49, -8.76]
+     * //   [-14.55, 8.17]
+     * //   [8.09, 17.47]
+     * // ]
      * ```
@@ -101,0 +105,0 @@ *

index.d.ts

@@ -0,1 +1,2 @@
+export * from "./api.js";
 export * from "./aspatial-grid.js";
@@ -2,0 +3,0 @@ export * from "./hash-grid.js";

index.js

@@ -0,1 +1,2 @@
+export * from "./api.js";
 export * from "./aspatial-grid.js";
@@ -2,0 +3,0 @@ export * from "./hash-grid.js";

kd-tree-map.d.ts

 import type { Fn, ICopy, IEmpty, Maybe, Pair } from "@thi.ng/api";
-import type { IRegionQuery, ISpatialMap } from "@thi.ng/geom-api";
 import type { DistanceFn, ReadonlyVec } from "@thi.ng/vectors";
+import type { IRegionQuery, ISpatialMap } from "./api.js";
 type MaybeKdNode<K extends ReadonlyVec, V> = Maybe<KdNode<K, V>>;
@@ -5,0 +5,0 @@ export declare class KdNode<K extends ReadonlyVec, V> {

kd-tree-map.js

@@ -82,3 +82,3 @@ import { ensureArray } from "@thi.ng/arrays/ensure-array";
     if (this.root) {
-      parent = nearest1(
+      parent = __nearest1(
         key,
@@ -112,5 +112,5 @@ [eps, void 0],
   remove(key) {
-    const node = find(key, this.root, 0);
+    const node = __find(key, this.root, 0);
     if (node) {
-      remove(node) && (this.root = void 0);
+      __remove(node) && (this.root = void 0);
       this._size--;
@@ -122,3 +122,3 @@ return true;
   has(key, eps = EPS) {
-    return !!this.root && !!nearest1(
+    return !!this.root && !!__nearest1(
       key,
@@ -133,3 +133,3 @@ [eps * eps, void 0],
     if (this.root) {
-      const node = nearest1(
+      const node = __nearest1(
         key,
@@ -157,3 +157,3 @@ [eps * eps, void 0],
     if (maxNum === 1) {
-      const sel = nearest1(
+      const sel = __nearest1(
         q,
@@ -173,3 +173,3 @@ [maxDist, void 0],
       );
-      nearest(q, nodes, this.dim, maxNum, this.root, this.distanceFn);
+      __nearest(q, nodes, this.dim, maxNum, this.root, this.distanceFn);
       return __addResults(f, nodes.values, acc);
@@ -197,14 +197,14 @@ }
 }
-const find = (p, node, epsSq) => {
+const __find = (p, node, epsSq) => {
   if (!node) return;
-  return distSq(p, node.k) <= epsSq ? node : find(p, p[node.d] < node.k[node.d] ? node.l : node.r, epsSq);
+  return distSq(p, node.k) <= epsSq ? node : __find(p, p[node.d] < node.k[node.d] ? node.l : node.r, epsSq);
 };
-const findMin = (node, dim) => {
+const __findMin = (node, dim) => {
   if (!node) return;
   if (node.d === dim) {
-    return node.l ? findMin(node.l, dim) : node;
+    return node.l ? __findMin(node.l, dim) : node;
   }
   const q = node.k[dim];
-  const l = findMin(node.l, dim);
-  const r = findMin(node.r, dim);
+  const l = __findMin(node.l, dim);
+  const r = __findMin(node.r, dim);
   let min = node;
@@ -219,3 +219,3 @@ if (l && l.k[dim] < q) {
 };
-const remove = (node) => {
+const __remove = (node) => {
   if (!node.l && !node.r) {
@@ -233,10 +233,10 @@ if (!node.parent) {
   if (node.r) {
-    next = findMin(node.r, node.d);
+    next = __findMin(node.r, node.d);
     nextP = next.k;
-    remove(next);
+    __remove(next);
     node.k = nextP;
   } else {
-    next = findMin(node.l, node.d);
+    next = __findMin(node.l, node.d);
     nextP = next.k;
-    remove(next);
+    __remove(next);
     node.r = node.l;
@@ -247,43 +247,43 @@ node.l = void 0;
 };
-const nearest = (q, acc, dims, maxNum, node, distFn) => {
+const __nearest = (q, acc, dims, maxNum, node, distFn) => {
   const p = node.k;
   const ndist = distSq(p, q);
   if (!node.l && !node.r) {
-    collect(acc, maxNum, node, ndist);
+    __collect(acc, maxNum, node, ndist);
     return;
   }
-  const tdist = nodeDist(node, dims, q, p, distFn);
-  let best = bestChild(node, q);
-  nearest(q, acc, dims, maxNum, best, distFn);
-  collect(acc, maxNum, node, ndist);
+  const tdist = __nodeDist(node, dims, q, p, distFn);
+  let best = __bestChild(node, q);
+  __nearest(q, acc, dims, maxNum, best, distFn);
+  __collect(acc, maxNum, node, ndist);
   if (tdist < acc.values[0][0]) {
     best = best === node.l ? node.r : node.l;
-    best && nearest(q, acc, dims, maxNum, best, distFn);
+    best && __nearest(q, acc, dims, maxNum, best, distFn);
   }
 };
-const nearest1 = (q, acc, dims, node, distFn) => {
+const __nearest1 = (q, acc, dims, node, distFn) => {
   const p = node.k;
   const ndist = distFn(p, q);
   if (!node.l && !node.r) {
-    collect1(acc, node, ndist);
+    __collect1(acc, node, ndist);
     return acc;
   }
-  const tdist = nodeDist(node, dims, q, p, distFn);
-  let best = bestChild(node, q);
-  nearest1(q, acc, dims, best, distFn);
-  collect1(acc, node, ndist);
+  const tdist = __nodeDist(node, dims, q, p, distFn);
+  let best = __bestChild(node, q);
+  __nearest1(q, acc, dims, best, distFn);
+  __collect1(acc, node, ndist);
   if (tdist < acc[0]) {
     best = best === node.l ? node.r : node.l;
-    best && nearest1(q, acc, dims, best, distFn);
+    best && __nearest1(q, acc, dims, best, distFn);
   }
   return acc;
 };
-const bestChild = (node, q) => {
+const __bestChild = (node, q) => {
   const d = node.d;
   return !node.r ? node.l : !node.l ? node.r : q[d] < node.k[d] ? node.l : node.r;
 };
-const collect = (acc, maxNum, node, 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 __collect = (acc, maxNum, node, 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, distFn) => {
+const __nodeDist = (node, dims, q, p, distFn) => {
   for (let i = dims, d = node.d; i-- > 0; ) {
@@ -290,0 +290,0 @@ TMP[i] = i === d ? q[i] : p[i];

kd-tree-set.d.ts

 import type { ICopy, IEmpty, Pair } from "@thi.ng/api";
-import type { IRegionQuery, ISpatialSet } from "@thi.ng/geom-api";
 import type { DistanceFn, ReadonlyVec } from "@thi.ng/vectors";
+import type { IRegionQuery, ISpatialSet } from "./api.js";
 import { KdTreeMap } from "./kd-tree-map.js";
@@ -5,0 +5,0 @@ export declare class KdTreeSet<K extends ReadonlyVec> implements ICopy<KdTreeSet<K>>, IEmpty<KdTreeSet<K>>, IRegionQuery<K, K, number>, ISpatialSet<K> {

nd-quadtree-map.d.ts

 import type { Fn, ICopy, IEmpty, Maybe, Pair } from "@thi.ng/api";
-import type { IRegionQuery, ISpatialMap } from "@thi.ng/geom-api";
 import { Heap } from "@thi.ng/heaps/heap";
 import type { DistanceFn, ReadonlyVec } from "@thi.ng/vectors";
+import type { IRegionQuery, ISpatialMap } from "./api.js";
 type MaybeNdQtNode<K extends ReadonlyVec, V> = Maybe<NdQtNode<K, V>>;
@@ -6,0 +6,0 @@ export declare class NdQtNode<K extends ReadonlyVec, V> {

nd-quadtree-map.js

@@ -48,3 +48,3 @@ import { equivArrayLike } from "@thi.ng/equiv";
       }
-      this.ensureChild(childID(this.k, this.pos)).setUnsafe(
+      this.ensureChild(__childID(this.k, this.pos)).setUnsafe(
         this.k,
@@ -57,3 +57,3 @@ this.v
     if (this.children) {
-      return this.ensureChild(childID(p, this.pos)).setUnsafe(p, val);
+      return this.ensureChild(__childID(p, this.pos)).setUnsafe(p, val);
     } else {
@@ -94,3 +94,3 @@ this.k = p;
     if (this.children) {
-      const child = this.children[childID(p, this.pos)];
+      const child = this.children[__childID(p, this.pos)];
       return child ? child.nodeForPoint(p) : void 0;
@@ -100,15 +100,14 @@ }
   doQuery(p, r, max, acc, distFn) {
-    if (testCenteredBoxSphere(this.pos, this.ext, p, r)) {
-      if (this.k) {
-        const d = distFn(this.k, p);
-        if (d <= acc.values[0][0]) {
-          acc.length >= max ? acc.pushPop([d, this]) : acc.push([d, this]);
+    if (!testCenteredBoxSphere(this.pos, this.ext, p, r)) return acc;
+    if (this.k) {
+      const d = distFn(this.k, p);
+      if (d <= acc.values[0][0]) {
+        acc.length >= max ? acc.pushPop([d, this]) : acc.push([d, this]);
+      }
+    } else if (this.children) {
+      for (let i = MAX_CHILDREN[this.pos.length], j = this.numC; i-- > 0 && j > 0; ) {
+        if (this.children[i]) {
+          this.children[i].doQuery(p, r, max, acc, distFn);
+          j--;
         }
-      } else if (this.children) {
-        for (let i = MAX_CHILDREN[this.pos.length], j = this.numC; i-- > 0 && j > 0; ) {
-          if (this.children[i]) {
-            this.children[i].doQuery(p, r, max, acc, distFn);
-            j--;
-          }
-        }
       }
@@ -142,3 +141,3 @@ }
     assert(ext.length === dim, `pos/ext dimensions must be equal`);
-    initChildOffsets(dim);
+    __initChildOffsets(dim);
     this.root = new NdQtNode(void 0, pos, ext);
@@ -229,3 +228,3 @@ this._size = 0;
       node = node.parent;
-      delete node.children[childID(p, node.pos)];
+      delete node.children[__childID(p, node.pos)];
       doPrune = --node.numC === 0;
@@ -277,15 +276,15 @@ if (doPrune) delete node.children;
 const CHILD_OFFSETS = [];
-const initChildOffsets = (dim) => CHILD_OFFSETS[dim] || (CHILD_OFFSETS[dim] = [...permutations(...repeat([-1, 1], dim))]);
-const childID = vop(0);
-childID.add(1, (p, q) => p[0] >= q[0] ? 1 : 0);
-childID.add(2, (p, q) => (p[0] >= q[0] ? 2 : 0) | (p[1] >= q[1] ? 1 : 0));
-childID.add(
+const __initChildOffsets = (dim) => CHILD_OFFSETS[dim] || (CHILD_OFFSETS[dim] = [...permutations(...repeat([-1, 1], dim))]);
+const __childID = vop(0);
+__childID.add(1, (p, q) => p[0] >= q[0] ? 1 : 0);
+__childID.add(2, (p, q) => (p[0] >= q[0] ? 2 : 0) | (p[1] >= q[1] ? 1 : 0));
+__childID.add(
   3,
   (p, q) => (p[0] >= q[0] ? 4 : 0) | (p[1] >= q[1] ? 2 : 0) | (p[2] >= q[2] ? 1 : 0)
 );
-childID.add(
+__childID.add(
   4,
   (p, q) => (p[0] >= q[0] ? 8 : 0) | (p[1] >= q[1] ? 4 : 0) | (p[2] >= q[2] ? 2 : 0) | (p[3] >= q[3] ? 1 : 0)
 );
-childID.default((p, q) => {
+__childID.default((p, q) => {
   let id = 0;
@@ -292,0 +291,0 @@ for (let i = 0, n = p.length - 1, bit = 1 << n; i <= n; i++, bit >>>= 1) {

nd-quadtree-set.d.ts

 import type { ICopy, IEmpty, Pair } from "@thi.ng/api";
-import type { IRegionQuery, ISpatialSet } from "@thi.ng/geom-api";
 import type { DistanceFn, ReadonlyVec } from "@thi.ng/vectors";
+import type { IRegionQuery, ISpatialSet } from "./api.js";
 import { NdQuadtreeMap } from "./nd-quadtree-map.js";
@@ -5,0 +5,0 @@ export declare class NdQuadtreeSet<K extends ReadonlyVec> implements ICopy<NdQuadtreeSet<K>>, IEmpty<NdQuadtreeSet<K>>, IRegionQuery<K, K, number>, ISpatialSet<K> {

package.json

 {
   "name": "@thi.ng/geom-accel",
-  "version": "3.6.4",
+  "version": "4.0.0",
   "description": "n-D spatial indexing data structures with a shared ES6 Map/Set-like API",
@@ -13,3 +13,3 @@ "type": "module",
   },
-  "homepage": "https://github.com/thi-ng/umbrella/tree/develop/packages/geom-accel#readme",
+  "homepage": "https://thi.ng/geom-accel",
   "funding": [
@@ -41,20 +41,19 @@ {
   "dependencies": {
-    "@thi.ng/api": "^8.11.2",
-    "@thi.ng/arrays": "^2.9.6",
-    "@thi.ng/checks": "^3.6.4",
-    "@thi.ng/distance": "^2.4.73",
-    "@thi.ng/equiv": "^2.1.58",
-    "@thi.ng/errors": "^2.5.7",
-    "@thi.ng/geom-api": "^4.0.10",
-    "@thi.ng/geom-isec": "^3.1.0",
-    "@thi.ng/heaps": "^2.1.74",
-    "@thi.ng/math": "^5.10.13",
-    "@thi.ng/transducers": "^9.0.5",
-    "@thi.ng/vectors": "^7.10.31"
+    "@thi.ng/api": "^8.11.3",
+    "@thi.ng/arrays": "^2.9.7",
+    "@thi.ng/checks": "^3.6.5",
+    "@thi.ng/distance": "^2.4.74",
+    "@thi.ng/equiv": "^2.1.59",
+    "@thi.ng/errors": "^2.5.8",
+    "@thi.ng/geom-isec": "^4.0.0",
+    "@thi.ng/heaps": "^2.1.75",
+    "@thi.ng/math": "^5.11.0",
+    "@thi.ng/transducers": "^9.0.6",
+    "@thi.ng/vectors": "^7.11.0"
   },
   "devDependencies": {
-    "@microsoft/api-extractor": "^7.43.2",
-    "esbuild": "^0.21.1",
+    "@microsoft/api-extractor": "^7.47.0",
+    "esbuild": "^0.21.5",
     "typedoc": "^0.25.13",
-    "typescript": "^5.4.5"
+    "typescript": "^5.5.2"
   },
@@ -94,2 +93,5 @@ "keywords": [
     },
+    "./api": {
+      "default": "./api.js"
+    },
     "./aspatial-grid": {
@@ -124,3 +126,3 @@ "default": "./aspatial-grid.js"
   },
-  "gitHead": "df34b4a9e650cc7323575356de207d78933bdcf3\n"
+  "gitHead": "154c95cf9d6bab32174498ec3b5b5d87e42be7f9\n"
 }

README.md

@@ -10,3 +10,3 @@ <!-- This file is generated - DO NOT EDIT! -->
 > [!NOTE]
-> This is one of 192 standalone projects, maintained as part
+> This is one of 193 standalone projects, maintained as part
 > of the [@thi.ng/umbrella](https://github.com/thi-ng/umbrella/) monorepo
@@ -86,3 +86,2 @@ > and anti-framework.
 - [@thi.ng/errors](https://github.com/thi-ng/umbrella/tree/develop/packages/errors)
-- [@thi.ng/geom-api](https://github.com/thi-ng/umbrella/tree/develop/packages/geom-api)
 - [@thi.ng/geom-isec](https://github.com/thi-ng/umbrella/tree/develop/packages/geom-isec)
@@ -89,0 +88,0 @@ - [@thi.ng/heaps](https://github.com/thi-ng/umbrella/tree/develop/packages/heaps)

No alert changes

Improved metrics

Total package byte prevSize

85277

increased by2.45%

Dependency count

11

decreased by-8.33%

Number of package files

26

increased by8.33%

Lines of code

1685

increased by1.87%

Worsened metrics

Number of lines in readme file

130

decreased by-0.76%

Dependency changes

• + [e-mail]/geom-isec@4.0.30(transitive)

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

• - [e-mail]/geom-api@4.0.10(transitive)

• - [e-mail]/geom-isec@3.1.0(transitive)

• [e-mail]/api@^8.11.3

• [e-mail]/arrays@^2.9.7

• [e-mail]/checks@^3.6.5

• [e-mail]/distance@^2.4.74

• [e-mail]/equiv@^2.1.59

• [e-mail]/errors@^2.5.8

• [e-mail]/geom-isec@^4.0.0

• [e-mail]/heaps@^2.1.75

• [e-mail]/math@^5.11.0

• [e-mail]/transducers@^9.0.6

• [e-mail]/vectors@^7.11.0