sorted-queue - npm Package Compare versions

Comparing version 0.3.2 to 0.3.3

dist/index.d.ts

@@ -9,2 +9,3 @@ declare type Cmp<T> = (a: T, b: T) => number;
     pop(): SortedQueueItem<T> | undefined;
+    empty(): boolean;
 }
@@ -11,0 +12,0 @@ declare class _SortedQueueItem<T> {

dist/index.js

@@ -1,2 +0,2 @@
-var r=function(r){void 0===r&&(r=n),this._cmp=r,this._array=[]};r.prototype.push=function(r){var t=new e(r,this,this._array.length);return this._array.push(t),u(this._array,t,this._cmp),t},r.prototype.peek=function(){return this._array.length>0?this._array[0]:void 0},r.prototype.pop=function(){var r=this.peek();return r?(r.pop(),r):r};var e=function(r,e,t){this.value=r,this._queue=e,this._index=t};e.prototype.pop=function(){var r=this._queue;if(!r)return!1;var e=r._array.pop();return e&&e!==this&&(e._index=this._index,r._array[this._index]=e,u(r._array,e,r._cmp),function(r,e,t){for(;;){var n=2*e._index+1;if(n>=r.length)return;var u=n+1,a=u<r.length&&t(r[u].value,r[n].value)<0?r[u]:r[n];if(!(t(a.value,e.value)<=0))return;i(r,a,e)}}(r._array,e,r._cmp)),this._queue=null,!0};var t=e;function n(r,e){return r===e?0:r!=r?e!=e?0:-1:e<r||e!=e?1:-1}function i(r,e,t){var n=e._index,i=t._index;r[n]=t,r[i]=e,e._index=i,t._index=n}function u(r,e,t){for(;e._index>0;){var n=r[e._index-1>>>1];if(t(n.value,e.value)<=0)return;i(r,n,e)}}exports.SortedQueue=r,exports.SortedQueueItem=t;
+var t=/*#__PURE__*/function(){function t(t){void 0===t&&(t=n),this._cmp=void 0,this._array=void 0,this._cmp=t,this._array=[]}var i=t.prototype;return i.push=function(t){var i=new r(t,this._array,this._array.length,this._cmp);return this._array.push(i),a(this._array,i,this._cmp),i},i.peek=function(){return this._array.length>0?this._array[0]:void 0},i.pop=function(){var t=this.peek();return t?(t.pop(),t):t},i.empty=function(){return 0===this._array.length},t}(),r=/*#__PURE__*/function(){function t(t,r,i,n){this.value=void 0,this._array=void 0,this._index=void 0,this._cmp=void 0,this.value=t,this._array=r,this._index=i,this._cmp=n}return t.prototype.pop=function(){var t=this._array;if(!t)return!1;var r=t.pop();return r&&r!==this&&(r._index=this._index,t[this._index]=r,a(t,r,this._cmp),function(t,r,i){for(;;){var n=2*r._index+1;if(n>=t.length)return;var a=n+1,u=a<t.length&&i(t[a].value,t[n].value)<0?t[a]:t[n];if(i(u.value,r.value)>0)return;e(t,u,r)}}(t,r,this._cmp)),this._array=null,!0},t}(),i=r;function n(t,r){return t===r?0:t!=t?r!=r?0:-1:r<t||r!=r?1:-1}function e(t,r,i){var n=r._index,e=i._index;t[n]=i,t[e]=r,r._index=e,i._index=n}function a(t,r,i){for(;r._index>0;){var n=t[r._index-1>>>1];if(i(n.value,r.value)<=0)return;e(t,n,r)}}exports.SortedQueue=t,exports.SortedQueueItem=i;
 //# sourceMappingURL=index.js.map

dist/index.umd.js

@@ -1,2 +0,2 @@
-!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports):"function"==typeof define&&define.amd?define(["exports"],t):t(e.sortedQueue={})}(this,function(e){var t=function(e){void 0===e&&(e=i),this._cmp=e,this._array=[]};t.prototype.push=function(e){var t=new r(e,this,this._array.length);return this._array.push(t),o(this._array,t,this._cmp),t},t.prototype.peek=function(){return this._array.length>0?this._array[0]:void 0},t.prototype.pop=function(){var e=this.peek();return e?(e.pop(),e):e};var r=function(e,t,r){this.value=e,this._queue=t,this._index=r};r.prototype.pop=function(){var e=this._queue;if(!e)return!1;var t=e._array.pop();return t&&t!==this&&(t._index=this._index,e._array[this._index]=t,o(e._array,t,e._cmp),function(e,t,r){for(;;){var n=2*t._index+1;if(n>=e.length)return;var i=n+1,o=i<e.length&&r(e[i].value,e[n].value)<0?e[i]:e[n];if(!(r(o.value,t.value)<=0))return;u(e,o,t)}}(e._array,t,e._cmp)),this._queue=null,!0};var n=r;function i(e,t){return e===t?0:e!=e?t!=t?0:-1:t<e||t!=t?1:-1}function u(e,t,r){var n=t._index,i=r._index;e[n]=r,e[i]=t,t._index=i,r._index=n}function o(e,t,r){for(;t._index>0;){var n=e[t._index-1>>>1];if(r(n.value,t.value)<=0)return;u(e,n,t)}}e.SortedQueue=t,e.SortedQueueItem=n});
+!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i((t||self).sortedQueue={})}(this,function(t){var i=/*#__PURE__*/function(){function t(t){void 0===t&&(t=r),this._cmp=void 0,this._array=void 0,this._cmp=t,this._array=[]}var i=t.prototype;return i.push=function(t){var i=new e(t,this._array,this._array.length,this._cmp);return this._array.push(i),u(this._array,i,this._cmp),i},i.peek=function(){return this._array.length>0?this._array[0]:void 0},i.pop=function(){var t=this.peek();return t?(t.pop(),t):t},i.empty=function(){return 0===this._array.length},t}(),e=/*#__PURE__*/function(){function t(t,i,e,n){this.value=void 0,this._array=void 0,this._index=void 0,this._cmp=void 0,this.value=t,this._array=i,this._index=e,this._cmp=n}return t.prototype.pop=function(){var t=this._array;if(!t)return!1;var i=t.pop();return i&&i!==this&&(i._index=this._index,t[this._index]=i,u(t,i,this._cmp),function(t,i,e){for(;;){var n=2*i._index+1;if(n>=t.length)return;var r=n+1,u=r<t.length&&e(t[r].value,t[n].value)<0?t[r]:t[n];if(e(u.value,i.value)>0)return;o(t,u,i)}}(t,i,this._cmp)),this._array=null,!0},t}(),n=e;function r(t,i){return t===i?0:t!=t?i!=i?0:-1:i<t||i!=i?1:-1}function o(t,i,e){var n=i._index,r=e._index;t[n]=e,t[r]=i,i._index=r,e._index=n}function u(t,i,e){for(;i._index>0;){var n=t[i._index-1>>>1];if(e(n.value,i.value)<=0)return;o(t,n,i)}}t.SortedQueue=i,t.SortedQueueItem=n});
 //# sourceMappingURL=index.umd.js.map

index.ts

@@ -5,3 +5,3 @@ type Cmp<T> = (a: T, b: T) => number;
   private _cmp: Cmp<T>;
-  private _array: Array<Item<T>>;
+  private _array: Item<T>[];
 
@@ -14,8 +14,4 @@ constructor(cmp: Cmp<T> = defaultCmp) {
   push(value: T): SortedQueueItem<T> {
-    const item = new Item(
-      value,
-      (this as unknown) as InternalQueue<T>,
-      this._array.length
-    );
-    const index = this._array.push(item);
+    const item = new Item(value, this._array, this._array.length, this._cmp);
+    this._array.push(item);
     siftUp(this._array, item, this._cmp);
@@ -37,7 +33,6 @@ return item;
   }
-}
 
-interface InternalQueue<T> {
-  _cmp: Cmp<T>;
-  _array: Array<Item<T>>;
+  empty(): boolean {
+    return this._array.length === 0;
+  }
 }
@@ -47,24 +42,26 @@
   readonly value: T;
-  _queue: InternalQueue<T> | null;
+  _array: Item<T>[] | null;
   _index: number;
+  _cmp: Cmp<T>;
 
-  constructor(value: T, queue: InternalQueue<T>, index: number) {
+  constructor(value: T, array: Item<T>[], index: number, cmp: Cmp<T>) {
     this.value = value;
-    this._queue = queue;
+    this._array = array;
     this._index = index;
+    this._cmp = cmp;
   }
 
   pop(): boolean {
-    const queue = this._queue;
-    if (!queue) {
+    const array = this._array;
+    if (!array) {
       return false;
     }
-    const last = queue._array.pop();
+    const last = array.pop();
     if (last && last !== this) {
       last._index = this._index;
-      queue._array[this._index] = last;
-      siftUp(queue._array, last, queue._cmp);
-      siftDown(queue._array, last, queue._cmp);
+      array[this._index] = last;
+      siftUp(array, last, this._cmp);
+      siftDown(array, last, this._cmp);
     }
-    this._queue = null;
+    this._array = null;
     return true;
@@ -103,4 +100,8 @@ }
   while (item._index > 0) {
+    // `item._index - 1` is cast to uint32 in by the `>>> 1`, which could make
+    // the value wrap around if `item._index` were larger than `2**32`.
+    // But `item._index` is initialized from `Array#length` and according to
     // ECMA-262, 7ᵗʰ Edition / June 2016:
-    // "Every Array object has a length property whose value is always a nonnegative integer less than 2**32."
+    //   "Every Array object has a length property whose value is always a
+    //    nonnegative integer less than 2**32."
     const parent = array[(item._index - 1) >>> 1];
@@ -125,8 +126,7 @@ if (cmp(parent.value, item.value) <= 0) {
         : array[left];
-    if (cmp(child.value, item.value) <= 0) {
-      swap(array, child, item);
-    } else {
+    if (cmp(child.value, item.value) > 0) {
       return;
     }
+    swap(array, child, item);
   }
 }

package.json

 {
   "name": "sorted-queue",
-  "version": "0.3.2",
+  "version": "0.3.3",
   "description": "A sorted queue, based on an array-backed binary heap",
@@ -14,15 +14,15 @@ "main": "dist/index.js",
     "typecheck": "tsc --noEmit --skipLibCheck",
-    "build": "rm -rf dist && microbundle",
+    "build": "rm -rf dist/* && microbundle",
     "prepublishOnly": "npm run build"
   },
   "devDependencies": {
-    "@types/chai": "^4.2.5",
-    "@types/mocha": "^5.2.7",
-    "chai": "^4.2.0",
-    "eslint": "^6.7.1",
-    "microbundle": "^0.11.0",
-    "mocha": "^6.2.2",
-    "prettier": "^1.19.1",
-    "ts-node": "^8.5.2",
-    "typescript": "^3.7.2"
+    "@types/chai": "^4.3.1",
+    "@types/mocha": "^9.1.1",
+    "chai": "^4.3.6",
+    "eslint": "^8.17.0",
+    "microbundle": "^0.15.0",
+    "mocha": "^10.0.0",
+    "prettier": "^2.6.2",
+    "ts-node": "^10.8.1",
+    "typescript": "^4.7.3"
   },
@@ -29,0 +29,0 @@ "keywords": [

README.md

@@ -1,2 +0,2 @@
-# sorted-queue [![npm](https://img.shields.io/npm/v/sorted-queue.svg)](https://www.npmjs.com/package/sorted-queue)
+# sorted-queue ![](https://github.com/jviide/sorted-queue/workflows/tests/badge.svg) [![npm](https://img.shields.io/npm/v/sorted-queue.svg)](https://www.npmjs.com/package/sorted-queue)
 
@@ -8,3 +8,3 @@ A sorted queue, based on an array-backed binary heap.
 ```sh
-$ npm install --save sorted-queue
+$ npm i sorted-queue
 ```
@@ -21,19 +21,22 @@
 // `item` with the `item.value` set to the pushed value.
-queue.push(1);        // { value: 1, ... }
-queue.push(-1);       // { value: -1, ... }
-queue.push(0);        // { value: 0, ... }
+queue.push(1); // { value: 1, ... }
+queue.push(-1); // { value: -1, ... }
+queue.push(0); // { value: 0, ... }
 
 // `queue.peek()` returns the item with the smallest value.
-queue.peek().value;   // -1
+queue.peek().value; // -1
 
 // `queue.pop()` returns the item with the smallest value
 // and also removes it from the queue.
-queue.pop().value;    // -1
-queue.pop().value;    // 0
-queue.pop().value;    // 1
+queue.pop().value; // -1
+queue.pop().value; // 0
+queue.pop().value; // 1
 
 // `pop()` and `peek()` return `undefined` when the queue is empty
-queue.pop();          // undefined
-queue.peek();         // undefined
+queue.pop(); // undefined
+queue.peek(); // undefined
 
+// `empty()` returns `true` when the queue is empty, `false` otherwise
+queue.empty(); // true
+
 // Items returned by push() can also be removed using `item.pop()`.
@@ -46,20 +49,22 @@ const first = queue.push(0);
 // `false` if the item has already been removed previously.
-middle.pop();         // true
-middle.pop();         // false
+middle.pop(); // true
+middle.pop(); // false
 
 // The order is preserved no matter from which position the item got
 // removed from.
-first.pop();          // true
-queue.pop().value;    // 2
-queue.pop();          // undefined
+first.pop(); // true
+queue.pop().value; // 2
+queue.pop(); // undefined
 
 // For more complex sortings you can defined a custom comparison function
 // (with the same signature as the comparison function Array#sort takes).
-const custom = new SortedQueue<{ name: string }>((a, b) => a.name.localeCompare(b.name));
+const custom = new SortedQueue<{ name: string }>((a, b) =>
+  a.name.localeCompare(b.name)
+);
 custom.push({ name: "Mallory" });
 custom.push({ name: "Alice" });
 custom.push({ name: "Bob" });
-custom.pop().value;   // { name: "Alice" }
-custom.pop().value;   // { name: "Bob" }
-custom.pop().value;   // { name: "Mallory" }
+custom.pop().value; // { name: "Alice" }
+custom.pop().value; // { name: "Bob" }
+custom.pop().value; // { name: "Mallory" }
 ```
@@ -66,0 +71,0 @@

No alert changes

Improved metrics

Total package byte prevSize

34499

increased by36.05%

Number of package files

14

increased by27.27%

Lines of code

156

increased by6.12%

Number of lines in readme file

72

increased by7.46%

No dependency changes