sorted-queue - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

dist/index.d.ts

@@ -6,13 +6,13 @@ declare type Cmp<T> = (a: T, b: T) => number;
     constructor(cmp?: Cmp<T>);
-    push(value: T): void;
-    peek(): Item<T> | undefined;
-    pop(): Item<T> | undefined;
+    push(value: T): SortedQueueItem<T>;
+    peek(): SortedQueueItem<T> | undefined;
+    pop(): SortedQueueItem<T> | undefined;
 }
-declare class Item<T> {
+declare class _SortedQueueItem<T> {
+    private constructor();
     readonly value: T;
-    private _queue;
-    private _index;
-    constructor(value: T, queue: SortedQueue<T>, index: number);
     pop(): boolean;
 }
+export declare const SortedQueueItem: typeof _SortedQueueItem;
+export declare type SortedQueueItem<T> = _SortedQueueItem<T>;
 export {};

dist/index.js

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

dist/index.umd.js

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

index.ts

@@ -12,17 +12,18 @@ type Cmp<T> = (a: T, b: T) => number;
 
-  push(value: T): void {
-    const item = new Item(value, this, this._array.length);
+  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);
-    siftUp(
-      (this._array as unknown) as InternalItem<T>[],
-      (item as unknown) as InternalItem<T>,
-      this._cmp
-    );
+    siftUp(this._array, item, this._cmp);
+    return item;
   }
 
-  peek(): Item<T> | undefined {
+  peek(): SortedQueueItem<T> | undefined {
     return this._array.length > 0 ? this._array[0] : undefined;
   }
 
-  pop(): Item<T> | undefined {
+  pop(): SortedQueueItem<T> | undefined {
     const item = this.peek();
@@ -37,3 +38,3 @@ if (!item) {
 
-interface InternalSortedQueue<T> {
+interface InternalQueue<T> {
   _cmp: Cmp<T>;
@@ -45,8 +46,8 @@ _array: Array<Item<T>>;
   readonly value: T;
-  private _queue: InternalSortedQueue<T> | null;
-  private _index: number;
+  _queue: InternalQueue<T> | null;
+  _index: number;
 
-  constructor(value: T, queue: SortedQueue<T>, index: number) {
+  constructor(value: T, queue: InternalQueue<T>, index: number) {
     this.value = value;
-    this._queue = (queue as unknown) as InternalSortedQueue<T>;
+    this._queue = queue;
     this._index = index;
@@ -64,7 +65,3 @@ }
       queue._array[this._index] = last;
-      siftDown(
-        (queue._array as unknown) as InternalItem<T>[],
-        (last as unknown) as InternalItem<T>,
-        queue._cmp
-      );
+      siftDown(queue._array, last, queue._cmp);
     }
@@ -76,7 +73,9 @@ this._queue = null;
 
-interface InternalItem<T> {
+declare class _SortedQueueItem<T> {
+  private constructor();
   readonly value: T;
-  _queue: InternalSortedQueue<T> | null;
-  _index: number;
+  pop(): boolean;
 }
+export const SortedQueueItem = (Item as unknown) as typeof _SortedQueueItem;
+export type SortedQueueItem<T> = _SortedQueueItem<T>;
 
@@ -93,7 +92,3 @@ function defaultCmp(a: unknown, b: unknown): number {
 
-function swap<T>(
-  array: InternalItem<T>[],
-  left: InternalItem<T>,
-  right: InternalItem<T>
-): void {
+function swap<T>(array: Item<T>[], left: Item<T>, right: Item<T>): void {
   const li = left._index;
@@ -107,7 +102,3 @@ const ri = right._index;
 
-function siftUp<T>(
-  array: InternalItem<T>[],
-  item: InternalItem<T>,
-  cmp: Cmp<T>
-): void {
+function siftUp<T>(array: Item<T>[], item: Item<T>, cmp: Cmp<T>): void {
   while (item._index > 0) {
@@ -124,7 +115,3 @@ // ECMA-262, 7ᵗʰ Edition / June 2016:
 
-function siftDown<T>(
-  array: InternalItem<T>[],
-  item: InternalItem<T>,
-  cmp: Cmp<T>
-): void {
+function siftDown<T>(array: Item<T>[], item: Item<T>, cmp: Cmp<T>): void {
   for (;;) {
@@ -131,0 +118,0 @@ const left = item._index * 2 + 1;

package.json

 {
   "name": "sorted-queue",
-  "version": "0.1.0",
+  "version": "0.2.0",
   "description": "A sorted queue, based on an array-backed binary heap",
@@ -5,0 +5,0 @@ "main": "dist/index.js",

README.md

@@ -1,2 +0,66 @@
-# sorted-queue
-A sorted queue, based on an array-backed binary heap
+# sorted-queue [![npm](https://img.shields.io/npm/v/sorted-queue.svg)](https://www.npmjs.com/package/sorted-queue)
+
+A sorted queue, based on an array-backed binary heap.
+
+## Installation
+
+```sh
+$ npm install --save sorted-queue
+```
+
+## Usage
+
+```ts
+import SortedQueue from "../index";
+
+const queue = new SortedQueue();
+
+// `queue.push()` adds a value to the queue and returns an object
+// `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.peek()` returns the item with the smallest value.
+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
+
+// `pop()` and `peek()` return `undefined` when the queue is empty
+queue.pop();          // undefined
+queue.peek();         // undefined
+
+// Items returned by push() can also be removed using `item.pop()`.
+const first = queue.push(0);
+const middle = queue.push(1);
+const last = queue.push(2);
+
+// `item.pop()` returns `true` if the item existed in the queue, and
+// `false` if the item has already been removed previously.
+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
+
+// 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));
+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" }
+```
+
+## License
+
+This library is licensed under the MIT license. See [LICENSE](./LICENSE).

No alert changes

Improved metrics

Total package byte prevSize

24865

increased by8.36%

Number of lines in readme file

67

increased by2133.33%

Worsened metrics

Lines of code

141

decreased by-7.24%

No dependency changes