@practicaljs/priority-queue - npm Package Compare versions

Comparing version 1.1.0 to 1.1.1

dist/priority-queue.js

@@ -1,12 +0,14 @@
-var r = Object.defineProperty;
-var d = (s, e, h) => e in s ? r(s, e, { enumerable: !0, configurable: !0, writable: !0, value: h }) : s[e] = h;
-var p = (s, e, h) => (d(s, typeof e != "symbol" ? e + "" : e, h), h);
-class u {
-  constructor(e) {
-    p(this, "parentIndex", (e) => Math.ceil(e / 2) - 1);
-    p(this, "leftIndex", (e) => e * 2 + 1);
-    p(this, "rightIndex", (e) => e * 2 + 2);
-    p(this, "heap", []);
-    p(this, "compare");
-    this.compare = e, this.enqueue = this.enqueue.bind(this), this.dequeue = this.dequeue.bind(this), this.clear = this.clear.bind(this);
+var y = Object.defineProperty;
+var d = (r, e, t) => e in r ? y(r, e, { enumerable: !0, configurable: !0, writable: !0, value: t }) : r[e] = t;
+var a = (r, e, t) => (d(r, typeof e != "symbol" ? e + "" : e, t), t);
+class g {
+  constructor(e, t) {
+    a(this, "parentIndex", (e) => Math.ceil(e / 2) - 1);
+    a(this, "leftIndex", (e) => e * 2 + 1);
+    a(this, "rightIndex", (e) => e * 2 + 2);
+    a(this, "heap", []);
+    a(this, "getKey");
+    a(this, "keyTrack", /* @__PURE__ */ new Map());
+    a(this, "compare");
+    this.compare = e, this.enqueue = this.enqueue.bind(this), this.dequeue = this.dequeue.bind(this), this.clear = this.clear.bind(this), this.hasItem = this.hasItem.bind(this), this.dequeueByIndex = this.dequeueByIndex.bind(this), this.dequeueItem = this.dequeueItem.bind(this), this.getKey = t;
   }
@@ -19,22 +21,48 @@ get peek() {
   }
+  hasItem(e) {
+    return this.getKey ? this.keyTrack.has(this.getKey(e)) : !1;
+  }
   enqueue(e) {
+    if (this.getKey && this.hasItem(e)) {
+      const i = this.heap[this.keyTrack.get(this.getKey(e))];
+      if (this.compare(e, i) === 0)
+        return;
+      this.dequeueItem(e);
+    }
     this.heap.push(e);
-    let h = this.heap.length - 1, t = this.parentIndex(h);
-    for (; t > -1 && this.compare(this.heap[t], this.heap[h]) > 0; )
-      [this.heap[t], this.heap[h]] = [this.heap[h], this.heap[t]], [h, t] = [t, this.parentIndex(t)];
+    let t = this.heap.length - 1;
+    this.getKey && this.keyTrack.set(this.getKey(e), t);
+    let h = this.parentIndex(t);
+    for (; h > -1 && this.compare(this.heap[h], this.heap[t]) > 0; ) {
+      if ([this.heap[h], this.heap[t]] = [this.heap[t], this.heap[h]], this.getKey) {
+        const i = this.getKey(this.heap[h]);
+        this.keyTrack.set(i, h), this.keyTrack.set(this.getKey(this.heap[t]), t);
+      }
+      [t, h] = [h, this.parentIndex(h)];
+    }
   }
-  dequeue() {
-    const e = this.heap.length - 1;
-    [this.heap[0], this.heap[e]] = [this.heap[e], this.heap[0]];
-    let h = 0, t = this.leftIndex(h), a = this.rightIndex(h);
-    for (; t < e || a < e; ) {
-      let i = -1;
-      t < e && a < e ? i = this.compare(this.heap[t], this.heap[a]) > 0 ? a : t : t < e ? i = t : i = a;
-      const n = this.compare(this.heap[i], this.heap[h]);
-      if (n > 0)
+  dequeueByIndex(e) {
+    const t = this.heap.length - 1;
+    [this.heap[e], this.heap[t]] = [this.heap[t], this.heap[e]], this.getKey && (this.keyTrack.set(this.getKey(this.heap[e]), e), this.keyTrack.set(this.getKey(this.heap[t]), t));
+    let h = e, i = this.leftIndex(h), n = this.rightIndex(h);
+    for (; i < t || n < t; ) {
+      let s = -1;
+      i < t && n < t ? s = this.compare(this.heap[i], this.heap[n]) > 0 ? n : i : i < t ? s = i : s = n;
+      const u = this.compare(this.heap[s], this.heap[h]);
+      if (u > 0)
         break;
-      n < 1 && ([this.heap[h], this.heap[i]] = [this.heap[i], this.heap[h]], [h, t, a] = [i, this.leftIndex(i), this.rightIndex(i)]);
+      u < 1 && ([this.heap[h], this.heap[s]] = [this.heap[s], this.heap[h]], this.getKey && (this.keyTrack.set(this.getKey(this.heap[h]), h), this.keyTrack.set(this.getKey(this.heap[s]), s)), [h, i, n] = [s, this.leftIndex(s), this.rightIndex(s)]);
     }
-    return this.heap.pop();
+    const p = this.heap.pop();
+    return this.getKey && p && this.keyTrack.delete(this.getKey(p)), p;
   }
+  dequeueItem(e) {
+    if (!this.getKey || !this.hasItem(e))
+      return null;
+    const t = this.keyTrack.get(this.getKey(e));
+    return this.dequeueByIndex(t);
+  }
+  dequeue() {
+    return this.dequeueByIndex(0);
+  }
   clear() {
@@ -45,3 +73,3 @@ this.heap = [];
 export {
-  u as PriorityQueue
+  g as PriorityQueue
 };

dist/priority-queue.umd.cjs

@@ -1,1 +0,1 @@
-(function(i,h){typeof exports=="object"&&typeof module<"u"?h(exports):typeof define=="function"&&define.amd?define(["exports"],h):(i=typeof globalThis<"u"?globalThis:i||self,h(i.PriorityQueue={}))})(this,function(i){"use strict";var d=Object.defineProperty;var l=(i,h,p)=>h in i?d(i,h,{enumerable:!0,configurable:!0,writable:!0,value:p}):i[h]=p;var a=(i,h,p)=>(l(i,typeof h!="symbol"?h+"":h,p),p);class h{constructor(e){a(this,"parentIndex",e=>Math.ceil(e/2)-1);a(this,"leftIndex",e=>e*2+1);a(this,"rightIndex",e=>e*2+2);a(this,"heap",[]);a(this,"compare");this.compare=e,this.enqueue=this.enqueue.bind(this),this.dequeue=this.dequeue.bind(this),this.clear=this.clear.bind(this)}get peek(){return this.heap[0]}get length(){return this.heap.length}enqueue(e){this.heap.push(e);let s=this.heap.length-1,t=this.parentIndex(s);for(;t>-1&&this.compare(this.heap[t],this.heap[s])>0;)[this.heap[t],this.heap[s]]=[this.heap[s],this.heap[t]],[s,t]=[t,this.parentIndex(t)]}dequeue(){const e=this.heap.length-1;[this.heap[0],this.heap[e]]=[this.heap[e],this.heap[0]];let s=0,t=this.leftIndex(s),r=this.rightIndex(s);for(;t<e||r<e;){let n=-1;t<e&&r<e?n=this.compare(this.heap[t],this.heap[r])>0?r:t:t<e?n=t:n=r;const u=this.compare(this.heap[n],this.heap[s]);if(u>0)break;u<1&&([this.heap[s],this.heap[n]]=[this.heap[n],this.heap[s]],[s,t,r]=[n,this.leftIndex(n),this.rightIndex(n)])}return this.heap.pop()}clear(){this.heap=[]}}i.PriorityQueue=h,Object.defineProperty(i,Symbol.toStringTag,{value:"Module"})});
+(function(s,i){typeof exports=="object"&&typeof module<"u"?i(exports):typeof define=="function"&&define.amd?define(["exports"],i):(s=typeof globalThis<"u"?globalThis:s||self,i(s.PriorityQueue={}))})(this,function(s){"use strict";var c=Object.defineProperty;var g=(s,i,u)=>i in s?c(s,i,{enumerable:!0,configurable:!0,writable:!0,value:u}):s[i]=u;var r=(s,i,u)=>(g(s,typeof i!="symbol"?i+"":i,u),u);class i{constructor(e,t){r(this,"parentIndex",e=>Math.ceil(e/2)-1);r(this,"leftIndex",e=>e*2+1);r(this,"rightIndex",e=>e*2+2);r(this,"heap",[]);r(this,"getKey");r(this,"keyTrack",new Map);r(this,"compare");this.compare=e,this.enqueue=this.enqueue.bind(this),this.dequeue=this.dequeue.bind(this),this.clear=this.clear.bind(this),this.hasItem=this.hasItem.bind(this),this.dequeueByIndex=this.dequeueByIndex.bind(this),this.dequeueItem=this.dequeueItem.bind(this),this.getKey=t}get peek(){return this.heap[0]}get length(){return this.heap.length}hasItem(e){return this.getKey?this.keyTrack.has(this.getKey(e)):!1}enqueue(e){if(this.getKey&&this.hasItem(e)){const n=this.heap[this.keyTrack.get(this.getKey(e))];if(this.compare(e,n)===0)return;this.dequeueItem(e)}this.heap.push(e);let t=this.heap.length-1;this.getKey&&this.keyTrack.set(this.getKey(e),t);let h=this.parentIndex(t);for(;h>-1&&this.compare(this.heap[h],this.heap[t])>0;){if([this.heap[h],this.heap[t]]=[this.heap[t],this.heap[h]],this.getKey){const n=this.getKey(this.heap[h]);this.keyTrack.set(n,h),this.keyTrack.set(this.getKey(this.heap[t]),t)}[t,h]=[h,this.parentIndex(h)]}}dequeueByIndex(e){const t=this.heap.length-1;[this.heap[e],this.heap[t]]=[this.heap[t],this.heap[e]],this.getKey&&(this.keyTrack.set(this.getKey(this.heap[e]),e),this.keyTrack.set(this.getKey(this.heap[t]),t));let h=e,n=this.leftIndex(h),p=this.rightIndex(h);for(;n<t||p<t;){let a=-1;n<t&&p<t?a=this.compare(this.heap[n],this.heap[p])>0?p:n:n<t?a=n:a=p;const y=this.compare(this.heap[a],this.heap[h]);if(y>0)break;y<1&&([this.heap[h],this.heap[a]]=[this.heap[a],this.heap[h]],this.getKey&&(this.keyTrack.set(this.getKey(this.heap[h]),h),this.keyTrack.set(this.getKey(this.heap[a]),a)),[h,n,p]=[a,this.leftIndex(a),this.rightIndex(a)])}const d=this.heap.pop();return this.getKey&&d&&this.keyTrack.delete(this.getKey(d)),d}dequeueItem(e){if(!this.getKey||!this.hasItem(e))return null;const t=this.keyTrack.get(this.getKey(e));return this.dequeueByIndex(t)}dequeue(){return this.dequeueByIndex(0)}clear(){this.heap=[]}}s.PriorityQueue=i,Object.defineProperty(s,Symbol.toStringTag,{value:"Module"})});

dist/PriorityQueue.d.ts

@@ -6,2 +6,3 @@ /**
 export declare type CompareTo<T> = (a: T, b: T) => number;
+export declare type Key<T> = (item: T) => string;
 export declare class PriorityQueue<T> {
@@ -12,9 +13,14 @@ private parentIndex;
     private heap;
+    private getKey?;
+    private keyTrack;
     compare: CompareTo<T>;
-    constructor(compareCbk: CompareTo<T>);
+    constructor(compareCbk: CompareTo<T>, key?: Key<T>);
     get peek(): T;
     get length(): number;
+    hasItem(item: T): boolean;
     enqueue(obj: T): void;
+    private dequeueByIndex;
+    dequeueItem(item: T): T | null | undefined;
     dequeue(): T | undefined;
     clear(): void;
 }

package.json

 {
   "name": "@practicaljs/priority-queue",
-  "version": "1.1.0",
+  "version": "1.1.1",
   "license": "MIT",
@@ -37,3 +37,3 @@ "type": "module",
     "build": "tsc && vite build",
-    "prepack": "json -f package.json -I -e \"delete this.devDependencies; delete this.dependencies\"",
+    "prepack": "npm run build && json -f package.json -I -e \"delete this.devDependencies; delete this.dependencies\"",
     "postpublish": "git checkout ./package.json",
@@ -40,0 +40,0 @@ "test": "vitest run",

No alert changes

Improved metrics

Total package byte prevSize

13017

24.28%

Lines of code

109

55.71%

No dependency changes