@liqd-js/heap - npm Package Compare versions

Comparing version 1.0.1 to 1.1.0

dist/heap.d.ts

 type Comparator<T> = (a: T, b: T) => number;
-export default class Heap<T> {
+export default class Heap<T, I = T> {
     private data;
     private index;
     private compare;
-    constructor(comparator?: Comparator<T>);
-    static from<T>(container: Array<T> | Set<T> | Map<any, T>, comparator: Comparator<T>): Heap<T>;
+    private get_id;
+    private sorted;
+    private updated;
+    constructor(comparator?: Comparator<T>, id_getter?: (item: T) => I);
+    static from<T, I>(container: Array<T> | Set<T> | Map<any, T>, comparator?: Comparator<T>, id_getter?: (item: T) => I): Heap<T, I>;
     private sift_up;
@@ -14,8 +17,11 @@ private sift_down;
     get size(): number;
-    top(): T | undefined;
+    top(): T | void;
     push(item: T): this;
-    pop(): T | undefined;
+    pop(): T | void;
+    get(id: I): T | void;
+    values(): IterableIterator<T>;
     update(item: T): boolean;
     delete(item: T): boolean;
     clear(): this;
+    private sort_updated;
     sort(): this;
@@ -22,0 +28,0 @@ }

dist/heap.js

@@ -5,8 +5,13 @@ export default class Heap {
     compare;
-    constructor(comparator) {
+    get_id;
+    sorted = true;
+    updated = new Set();
+    constructor(comparator, id_getter) {
         this.data = new Array();
         this.compare = comparator ? comparator : (a, b) => a < b ? -1 : 1;
+        //@ts-ignore
+        this.get_id = id_getter ?? (item => item);
     }
-    static from(container, comparator) {
-        let heap = new Heap(comparator);
+    static from(container, comparator, id_getter) {
+        let heap = new Heap(comparator, id_getter);
         for (const item of container.values()) {
@@ -24,4 +29,4 @@ heap.push(item);
             if (this.index) {
-                this.index.set(this.data[i], i);
-                this.index.set(this.data[pi], pi);
+                this.index.set(this.get_id(this.data[i]), i);
+                this.index.set(this.get_id(this.data[pi]), pi);
             }
@@ -41,4 +46,4 @@ i = pi;
                 if (this.index) {
-                    this.index.set(this.data[i], i);
-                    this.index.set(this.data[ci], ci);
+                    this.index.set(this.get_id(this.data[i]), i);
+                    this.index.set(this.get_id(this.data[ci]), ci);
                 }
@@ -64,3 +69,3 @@ i = ci;
         for (let i = 0; i < this.data.length; ++i) {
-            this.index.set(this.data[i], i);
+            this.index.set(this.get_id(this.data[i]), i);
         }
@@ -77,6 +82,5 @@ }
                 }
-                return this.index.get(item);
+                return this.index.get(this.get_id(item));
             }
         }
-        return undefined;
     }
@@ -87,3 +91,8 @@ get size() {
     top() {
-        return this.data.length ? this.data[0] : undefined;
+        if (this.data.length) {
+            if (!this.sorted) {
+                this.sort_updated();
+            }
+            return this.data[0];
+        }
     }
@@ -93,3 +102,3 @@ push(item) {
         if (this.index) {
-            this.index.set(item, this.data.length - 1);
+            this.index.set(this.get_id(item), this.data.length - 1);
         }
@@ -101,2 +110,5 @@ this.sift_up(this.data.length - 1);
         if (this.data.length) {
+            if (!this.sorted) {
+                this.sort_updated();
+            }
             let last = this.data.pop();
@@ -107,4 +119,4 @@ if (this.data.length) {
                 if (this.index) {
-                    this.index.delete(top);
-                    this.index.set(last, 0);
+                    this.index.delete(this.get_id(top));
+                    this.index.set(this.get_id(last), 0);
                 }
@@ -116,3 +128,3 @@ this.sift_down(0);
                 if (this.index) {
-                    this.index.delete(last);
+                    this.index.delete(this.get_id(last));
                 }
@@ -122,10 +134,25 @@ return last;
         }
-        else {
-            return undefined;
+    }
+    get(id) {
+        if (this.data.length) {
+            if (!this.index) {
+                this.reindex();
+            }
+            const index = this.index.get(id);
+            if (index !== undefined) {
+                return this.data[index];
+            }
         }
     }
+    values() {
+        return this.data.values();
+    }
     update(item) {
         let i = this.get_item_index(item);
         if (i !== undefined) {
-            this.sift(i);
+            this.sorted = false;
+            this.updated.add(item);
+            if (this.updated.size > Math.max(10, this.data.length * 0.1)) {
+                this.sort_updated();
+            }
             return true;
@@ -144,6 +171,6 @@ }
                     let last = this.data.pop();
-                    this.index.delete(item);
+                    this.index.delete(this.get_id(item));
                     if (i < this.data.length) {
                         this.data[i] = last;
-                        this.index.set(last, i);
+                        this.index.set(this.get_id(last), i);
                         this.sift(i);
@@ -160,15 +187,19 @@ }
         this.index = undefined;
+        this.sorted = true;
         return this;
     }
+    sort_updated() {
+        for (let item of this.updated) {
+            this.sift(this.get_item_index(item));
+        }
+    }
     sort() {
-        let data = this.data;
-        this.data = new Array();
-        if (this.index) {
-            this.index = new Map();
+        for (let i = 0; i < this.data.length; ++i) {
+            this.sift_up(i);
         }
-        for (const item of data) {
-            this.push(item);
-        }
+        this.index && (this.index = new Map());
+        this.updated = new Set();
+        this.sorted = true;
         return this;
     }
 }

package.json

 {
   "name": "@liqd-js/heap",
-  "version": "1.0.1",
+  "version": "1.1.0",
   "description": "",
@@ -20,4 +20,4 @@ "author": "radixxko",
   "devDependencies": {
-    "typescript": "^5.4.2"
+    "typescript": "^5.4.4"
   }
 }

No alert changes

Improved metrics

Total package byte prevSize

9077

increased by21.46%

Lines of code

220

increased by20.22%

No dependency changes