feat(heaps): update all Heap impls, opts, add factories

- add HeapOpts.equiv predicate - add thi.ng/equiv dependency - add Heap.remove(), .find(), .findWith() - add defHeap/defDHeap/defPairingHeap() factory fns
thi-ng · Aug 16, 2021 · fbfb7bb · fbfb7bb
1 parent 1fcc3ea
commit fbfb7bb
Show file tree

Hide file tree

Showing 6 changed files with 90 additions and 20 deletions.
diff --git a/packages/heaps/package.json b/packages/heaps/package.json
@@ -40,7 +40,8 @@
     },
     "dependencies": {
         "@thi.ng/api": "^7.1.9",
-        "@thi.ng/compare": "^1.3.33"
+        "@thi.ng/compare": "^1.3.33",
+        "@thi.ng/equiv": "^1.0.45"
     },
     "files": [
         "*.js",

diff --git a/packages/heaps/src/api.ts b/packages/heaps/src/api.ts
@@ -1,7 +1,8 @@
-import type { Comparator } from "@thi.ng/api";
+import type { Comparator, Predicate2 } from "@thi.ng/api";
 
 export interface HeapOpts<T> {
     compare: Comparator<T>;
+    equiv: Predicate2<T>;
 }
 
 export interface DHeapOpts<T> extends HeapOpts<T> {

diff --git a/packages/heaps/src/dheap.ts b/packages/heaps/src/dheap.ts
@@ -1,8 +1,12 @@
 import type { ICopy, IEmpty, IStack } from "@thi.ng/api";
-import { compare } from "@thi.ng/compare";
 import type { DHeapOpts } from "./api";
 import { Heap } from "./heap";
 
+export const defDHeap = <T>(
+    values?: Iterable<T> | null,
+    opts?: Partial<DHeapOpts<T>>
+) => new DHeap(values, opts);
+
 /**
  * Generic d-ary heap / priority queue with configurable arity (default
  * = 4) and ordering via user-supplied comparator.
@@ -17,7 +21,8 @@ import { Heap } from "./heap";
  */
 export class DHeap<T>
     extends Heap<T>
-    implements ICopy<DHeap<T>>, IEmpty<DHeap<T>>, IStack<T, T, DHeap<T>> {
+    implements ICopy<DHeap<T>>, IEmpty<DHeap<T>>, IStack<T, T, DHeap<T>>
+{
     /**
      * Returns index of parent node or -1 if `idx < 1`.
      *
@@ -41,12 +46,10 @@ export class DHeap<T>
     protected d: number;
 
     constructor(values?: Iterable<T> | null, opts?: Partial<DHeapOpts<T>>) {
-        super(undefined, { compare, ...opts });
+        super(undefined, opts);
         this.d = (opts && opts.d) || 4;
         this.values = [];
-        if (values) {
-            this.into(values);
-        }
+        values && this.into(values);
     }
 
     copy(): DHeap<T> {
@@ -78,7 +81,7 @@ export class DHeap<T>
     }
 
     heapify(vals = this.values) {
-        for (var i = ((vals.length - 1) / this.d) | 0; i >= 0; i--) {
+        for (let i = ((vals.length - 1) / this.d) | 0; i >= 0; i--) {
             this.percolateDown(i, vals);
         }
     }

diff --git a/packages/heaps/src/heap.ts b/packages/heaps/src/heap.ts
@@ -1,14 +1,23 @@
-import { compare } from "@thi.ng/compare";
 import type {
     Comparator,
     IClear,
     ICopy,
     IEmpty,
+    IInto,
     ILength,
     IStack,
+    Predicate,
+    Predicate2,
 } from "@thi.ng/api";
+import { compare } from "@thi.ng/compare";
+import { equiv } from "@thi.ng/equiv";
 import type { HeapOpts } from "./api";
 
+export const defHeap = <T>(
+    values?: Iterable<T> | null,
+    opts?: Partial<HeapOpts<T>>
+) => new Heap(values, opts);
+
 /**
  * Generic binary heap / priority queue with customizable ordering via
  * user-supplied comparator. By default, implements min-heap ordering
@@ -32,8 +41,10 @@ export class Heap<T>
         IClear,
         ICopy<Heap<T>>,
         IEmpty<Heap<T>>,
+        IInto<T, Heap<T>>,
         ILength,
-        IStack<T, T, Heap<T>> {
+        IStack<T, T, Heap<T>>
+{
     static parentIndex(idx: number) {
         return idx > 0 ? (idx - 1) >> 1 : -1;
     }
@@ -44,10 +55,12 @@ export class Heap<T>
 
     values: T[];
     compare: Comparator<T>;
+    equiv: Predicate2<T>;
 
-    constructor(values?: Iterable<T> | null, opts?: HeapOpts<T>) {
-        opts = Object.assign({ compare: compare }, opts);
-        this.compare = opts.compare;
+    constructor(values?: Iterable<T> | null, opts?: Partial<HeapOpts<T>>) {
+        opts = { compare, equiv, ...opts };
+        this.compare = opts.compare!;
+        this.equiv = opts.equiv!;
         this.values = [];
         if (values) {
             this.into(values);
@@ -139,8 +152,36 @@ export class Heap<T>
         return res;
     }
 
+    remove(val: T) {
+        const { values, equiv } = this;
+        for (let i = values.length; --i >= 0; ) {
+            if (equiv(values[i], val)) {
+                this.values.splice(i, 1);
+                this.heapify();
+                return true;
+            }
+        }
+        return false;
+    }
+
+    find(val: T) {
+        const { values, equiv } = this;
+        for (let i = values.length; --i >= 0; ) {
+            if (equiv(values[i], val)) {
+                return values[i];
+            }
+        }
+    }
+
+    findWith(pred: Predicate<T>) {
+        const values = this.values;
+        for (let i = values.length; --i >= 0; ) {
+            if (pred(values[i])) return values[i];
+        }
+    }
+
     heapify(vals = this.values) {
-        for (var i = (vals.length - 1) >> 1; i >= 0; i--) {
+        for (let i = (vals.length - 1) >> 1; i >= 0; i--) {
             this.percolateDown(i, vals);
         }
     }

diff --git a/packages/heaps/src/index.ts b/packages/heaps/src/index.ts
@@ -2,3 +2,4 @@ export * from "./api";
 export * from "./heap";
 export * from "./dheap";
 export * from "./pairing";
+export * from "./priority-queue";
diff --git a/packages/heaps/src/pairing.ts b/packages/heaps/src/pairing.ts
@@ -6,8 +6,11 @@ import type {
     IEmpty,
     ILength,
     IStack,
+    Predicate,
+    Predicate2,
 } from "@thi.ng/api";
 import { compare } from "@thi.ng/compare";
+import { equiv } from "@thi.ng/equiv";
 import type { HeapOpts } from "./api";
 
 interface Node<T> {
@@ -16,21 +19,29 @@ interface Node<T> {
     p?: Node<T>;
 }
 
+export const defPairingHeap = <T>(
+    values?: Iterable<T> | null,
+    opts?: Partial<HeapOpts<T>>
+) => new PairingHeap(values, opts);
+
 export class PairingHeap<T>
     implements
         Iterable<T>,
         IClear,
         ICopy<PairingHeap<T>>,
         IEmpty<PairingHeap<T>>,
         ILength,
-        IStack<T, T, PairingHeap<T>> {
+        IStack<T, T, PairingHeap<T>>
+{
     protected compare: Comparator<T>;
+    protected equiv: Predicate2<T>;
     protected root!: Node<T>;
     protected _size!: number;
 
-    constructor(vals?: Iterable<T>, opts?: HeapOpts<T>) {
-        opts = Object.assign({ compare: compare }, opts);
-        this.compare = opts.compare;
+    constructor(vals?: Iterable<T> | null, opts?: Partial<HeapOpts<T>>) {
+        opts = { compare, equiv, ...opts };
+        this.compare = opts.compare!;
+        this.equiv = opts.equiv!;
         this.clear();
         vals && this.into(vals);
     }
@@ -51,7 +62,7 @@ export class PairingHeap<T>
     }
 
     empty() {
-        return new PairingHeap<T>(undefined, { compare });
+        return new PairingHeap<T>(null, { compare, equiv });
     }
 
     copy() {
@@ -103,6 +114,18 @@ export class PairingHeap<T>
         return this;
     }
 
+    find(val: T) {
+        let found: T | undefined;
+        this.visit((x) => (this.equiv(x, val) ? ((found = x), false) : true));
+        return found;
+    }
+
+    findWith(fn: Predicate<T>) {
+        let found: T | undefined;
+        this.visit((x) => (fn(x) ? ((found = x), false) : true));
+        return found;
+    }
+
     /**
      * Computes union with given heap and clears `heap`, i.e. this heap
      * will take ownership of `heap`'s items (if any).