ts-heap - npm Package Compare versions

Comparing version 1.1.0 to 1.1.1

bundles/bundle.amd.js

@@ -16,3 +16,3 @@ define("ts-heap", ["require", "exports"], function (require, exports) {
             this.itemToIndexMap = new Map();
-            this.compare = compareFunction;
+            this.innerCompare = compareFunction;
         }
@@ -31,3 +31,7 @@ peek() {
         pop() {
-            return this.popAt(0);
+            if (this.isEmpty)
+                return undefined;
+            let obj = this.items[0];
+            this.removeAt(0);
+            return obj;
         }
@@ -38,3 +42,3 @@ get size() {
         get isEmpty() {
-            return this.items.length <= 0;
+            return this.items.length === 0;
         }
@@ -45,3 +49,3 @@ remove(item) {
                 return false;
-            this.popAt(index);
+            this.removeAt(index);
             return true;
@@ -59,15 +63,26 @@ }
         }
-        popAt(index) {
-            if (this.items.length === 0)
-                return undefined;
+        compare(a, b) {
+            let result = this.innerCompare(a, b);
+            if (typeof result !== "number")
+                throw new Error(`The typeof compare result cannot be different from number: ${result}`);
+            if (isNaN(result))
+                throw new Error(`Compare result cannot be is NaN.`);
+            return result;
+        }
+        removeAt(index) {
             if (this.items.length === 1) {
                 let item = this.items[0];
                 this.clear();
-                return item;
+                return;
             }
+            if (index === this.items.length - 1) {
+                this.itemToIndexMap.delete(this.items[this.items.length - 1]);
+                this.items.splice(this.items.length - 1, 1);
+                return;
+            }
             let poppedItem = this.items[index];
             this.itemToIndexMap.delete(poppedItem);
             this.items[index] = this.items[this.items.length - 1];
+            this.items.splice(this.items.length - 1, 1);
             this.itemToIndexMap.set(this.items[index], index);
-            this.items.splice(this.items.length - 1, 1);
             let compare = this.compare(this.items[index], poppedItem);
@@ -80,3 +95,2 @@ if (compare < 0) {
             }
-            return poppedItem;
         }
@@ -83,0 +97,0 @@ getLeftChildIndex(nodeIndex) {

bundles/bundle.amd.min.js

@@ -1,1 +0,1 @@
-define("ts-heap",["require","exports"],function(t,i){"use strict";Object.defineProperty(i,"__esModule",{value:!0}),i.minNumberCompare=function(t,i){return t-i},i.MaxNumberComparer=function(t,i){return i-t};class e{constructor(t){this.a=[],this.b=new Map,this.c=t}peek(){return this.a[0]}add(t){if(this.b.has(t))throw new Error("Connot add an item that is already in the heap.");this.a.push(t),this.b.set(t,this.a.length-1),this.h(this.a.length-1)}pop(){return this.d(0)}get size(){return this.a.length}get isEmpty(){return this.a.length<=0}remove(t){let i=this.b.get(t);return void 0!==i&&(this.d(i),!0)}clear(){this.a.length=0,this.b.clear()}contains(t){return this.b.has(t)}[Symbol.iterator](){return this.a[Symbol.iterator]()}d(t){if(0===this.a.length)return;if(1===this.a.length){let t=this.a[0];return this.clear(),t}let i=this.a[t];this.b.delete(i),this.a[t]=this.a[this.a.length-1],this.b.set(this.a[t],t),this.a.splice(this.a.length-1,1);let e=this.c(this.a[t],i);return e<0?this.h(t):e>0&&this.i(t),i}e(t){return 2*t+1}f(t){return Math.floor((t-1)/2)}g(t,i){return i>=this.a.length?t>=this.a.length?void 0:t:t>=this.a.length?i:this.c(this.a[t],this.a[i])<=0?t:i}h(t){if(0===t)return;let i=this.a[t];for(;;){let e=this.f(t),h=this.a[e];if(this.c(h,i)<=0)break;if(this.j(t,e,i,h),0===e)break;t=e}}i(t){let i=this.e(t),e=this.g(i,i+1);for(;void 0!==e;){let h=this.a[t],s=this.a[e];if(this.c(h,s)<0)break;this.j(t,e,h,s),t=e,i=this.e(t),e=this.g(i,i+1)}}j(t,i,e,h){e=e||this.a[t],h=h||this.a[i];let s=e;this.a[t]=h,this.a[i]=s,this.b.set(e,i),this.b.set(h,t)}}i.Heap=e});
+define("ts-heap",["require","exports"],function(t,e){"use strict";Object.defineProperty(e,"__esModule",{value:!0}),e.minNumberCompare=function(t,e){return t-e},e.MaxNumberComparer=function(t,e){return e-t};class i{constructor(t){this.a=[],this.b=new Map,this.c=t}peek(){return this.a[0]}add(t){if(this.b.has(t))throw new Error("Connot add an item that is already in the heap.");this.a.push(t),this.b.set(t,this.a.length-1),this.i(this.a.length-1)}pop(){if(this.isEmpty)return;let t=this.a[0];return this.e(0),t}get size(){return this.a.length}get isEmpty(){return 0===this.a.length}remove(t){let e=this.b.get(t);return void 0!==e&&(this.e(e),!0)}clear(){this.a.length=0,this.b.clear()}contains(t){return this.b.has(t)}[Symbol.iterator](){return this.a[Symbol.iterator]()}d(t,e){let i=this.c(t,e);if("number"!=typeof i)throw new Error(`The typeof compare result cannot be different from number: ${i}`);if(isNaN(i))throw new Error(`Compare result cannot be is NaN.`);return i}e(t){if(1===this.a.length){this.a[0];return void this.clear()}if(t===this.a.length-1)return this.b.delete(this.a[this.a.length-1]),void this.a.splice(this.a.length-1,1);let e=this.a[t];this.b.delete(e),this.a[t]=this.a[this.a.length-1],this.a.splice(this.a.length-1,1),this.b.set(this.a[t],t);let i=this.d(this.a[t],e);i<0?this.i(t):i>0&&this.j(t)}f(t){return 2*t+1}g(t){return Math.floor((t-1)/2)}h(t,e){return e>=this.a.length?t>=this.a.length?void 0:t:t>=this.a.length?e:this.d(this.a[t],this.a[e])<=0?t:e}i(t){if(0===t)return;let e=this.a[t];for(;;){let i=this.g(t),h=this.a[i];if(this.d(h,e)<=0)break;if(this.k(t,i,e,h),0===i)break;t=i}}j(t){let e=this.f(t),i=this.h(e,e+1);for(;void 0!==i;){let h=this.a[t],s=this.a[i];if(this.d(h,s)<0)break;this.k(t,i,h,s),t=i,e=this.f(t),i=this.h(e,e+1)}}k(t,e,i,h){i=i||this.a[t],h=h||this.a[e];let s=i;this.a[t]=h,this.a[e]=s,this.b.set(i,e),this.b.set(h,t)}}e.Heap=i});

bundles/bundle.system.js

@@ -20,3 +20,3 @@ System.register("ts-heap", [], function (exports_1, context_1) {
                     this.itemToIndexMap = new Map();
-                    this.compare = compareFunction;
+                    this.innerCompare = compareFunction;
                 }
@@ -35,3 +35,7 @@ peek() {
                 pop() {
-                    return this.popAt(0);
+                    if (this.isEmpty)
+                        return undefined;
+                    let obj = this.items[0];
+                    this.removeAt(0);
+                    return obj;
                 }
@@ -42,3 +46,3 @@ get size() {
                 get isEmpty() {
-                    return this.items.length <= 0;
+                    return this.items.length === 0;
                 }
@@ -49,3 +53,3 @@ remove(item) {
                         return false;
-                    this.popAt(index);
+                    this.removeAt(index);
                     return true;
@@ -63,15 +67,26 @@ }
                 }
-                popAt(index) {
-                    if (this.items.length === 0)
-                        return undefined;
+                compare(a, b) {
+                    let result = this.innerCompare(a, b);
+                    if (typeof result !== "number")
+                        throw new Error(`The typeof compare result cannot be different from number: ${result}`);
+                    if (isNaN(result))
+                        throw new Error(`Compare result cannot be is NaN.`);
+                    return result;
+                }
+                removeAt(index) {
                     if (this.items.length === 1) {
                         let item = this.items[0];
                         this.clear();
-                        return item;
+                        return;
                     }
+                    if (index === this.items.length - 1) {
+                        this.itemToIndexMap.delete(this.items[this.items.length - 1]);
+                        this.items.splice(this.items.length - 1, 1);
+                        return;
+                    }
                     let poppedItem = this.items[index];
                     this.itemToIndexMap.delete(poppedItem);
                     this.items[index] = this.items[this.items.length - 1];
+                    this.items.splice(this.items.length - 1, 1);
                     this.itemToIndexMap.set(this.items[index], index);
-                    this.items.splice(this.items.length - 1, 1);
                     let compare = this.compare(this.items[index], poppedItem);
@@ -84,3 +99,2 @@ if (compare < 0) {
                     }
-                    return poppedItem;
                 }
@@ -87,0 +101,0 @@ getLeftChildIndex(nodeIndex) {

bundles/bundle.system.min.js

@@ -1,1 +0,1 @@
-System.register("ts-heap",[],function(t,i){"use strict";i&&i.id;t("minNumberCompare",function(t,i){return t-i}),t("MaxNumberComparer",function(t,i){return i-t});var e;return{setters:[],execute:function(){t("Heap",e=class{constructor(t){this.a=[],this.b=new Map,this.c=t}peek(){return this.a[0]}add(t){if(this.b.has(t))throw new Error("Connot add an item that is already in the heap.");this.a.push(t),this.b.set(t,this.a.length-1),this.h(this.a.length-1)}pop(){return this.d(0)}get size(){return this.a.length}get isEmpty(){return this.a.length<=0}remove(t){let i=this.b.get(t);return void 0!==i&&(this.d(i),!0)}clear(){this.a.length=0,this.b.clear()}contains(t){return this.b.has(t)}[Symbol.iterator](){return this.a[Symbol.iterator]()}d(t){if(0===this.a.length)return;if(1===this.a.length){let t=this.a[0];return this.clear(),t}let i=this.a[t];this.b.delete(i),this.a[t]=this.a[this.a.length-1],this.b.set(this.a[t],t),this.a.splice(this.a.length-1,1);let e=this.c(this.a[t],i);return e<0?this.h(t):e>0&&this.i(t),i}e(t){return 2*t+1}f(t){return Math.floor((t-1)/2)}g(t,i){return i>=this.a.length?t>=this.a.length?void 0:t:t>=this.a.length?i:this.c(this.a[t],this.a[i])<=0?t:i}h(t){if(0===t)return;let i=this.a[t];for(;;){let e=this.f(t),h=this.a[e];if(this.c(h,i)<=0)break;if(this.j(t,e,i,h),0===e)break;t=e}}i(t){let i=this.e(t),e=this.g(i,i+1);for(;void 0!==e;){let h=this.a[t],s=this.a[e];if(this.c(h,s)<0)break;this.j(t,e,h,s),t=e,i=this.e(t),e=this.g(i,i+1)}}j(t,i,e,h){e=e||this.a[t],h=h||this.a[i];let s=e;this.a[t]=h,this.a[i]=s,this.b.set(e,i),this.b.set(h,t)}})}}});
+System.register("ts-heap",[],function(t,e){"use strict";e&&e.id;t("minNumberCompare",function(t,e){return t-e}),t("MaxNumberComparer",function(t,e){return e-t});var i;return{setters:[],execute:function(){t("Heap",i=class{constructor(t){this.a=[],this.b=new Map,this.c=t}peek(){return this.a[0]}add(t){if(this.b.has(t))throw new Error("Connot add an item that is already in the heap.");this.a.push(t),this.b.set(t,this.a.length-1),this.i(this.a.length-1)}pop(){if(this.isEmpty)return;let t=this.a[0];return this.e(0),t}get size(){return this.a.length}get isEmpty(){return 0===this.a.length}remove(t){let e=this.b.get(t);return void 0!==e&&(this.e(e),!0)}clear(){this.a.length=0,this.b.clear()}contains(t){return this.b.has(t)}[Symbol.iterator](){return this.a[Symbol.iterator]()}d(t,e){let i=this.c(t,e);if("number"!=typeof i)throw new Error(`The typeof compare result cannot be different from number: ${i}`);if(isNaN(i))throw new Error(`Compare result cannot be is NaN.`);return i}e(t){if(1===this.a.length){this.a[0];return void this.clear()}if(t===this.a.length-1)return this.b.delete(this.a[this.a.length-1]),void this.a.splice(this.a.length-1,1);let e=this.a[t];this.b.delete(e),this.a[t]=this.a[this.a.length-1],this.a.splice(this.a.length-1,1),this.b.set(this.a[t],t);let i=this.d(this.a[t],e);i<0?this.i(t):i>0&&this.j(t)}f(t){return 2*t+1}g(t){return Math.floor((t-1)/2)}h(t,e){return e>=this.a.length?t>=this.a.length?void 0:t:t>=this.a.length?e:this.d(this.a[t],this.a[e])<=0?t:e}i(t){if(0===t)return;let e=this.a[t];for(;;){let i=this.g(t),h=this.a[i];if(this.d(h,e)<=0)break;if(this.k(t,i,e,h),0===i)break;t=i}}j(t){let e=this.f(t),i=this.h(e,e+1);for(;void 0!==i;){let h=this.a[t],s=this.a[i];if(this.d(h,s)<0)break;this.k(t,i,h,s),t=i,e=this.f(t),i=this.h(e,e+1)}}k(t,e,i,h){i=i||this.a[t],h=h||this.a[e];let s=i;this.a[t]=h,this.a[e]=s,this.b.set(i,e),this.b.set(h,t)}})}}});

lib/Heap.d.ts

@@ -7,3 +7,3 @@ export declare type ICompareFunction<T> = (obj1: T, obj2: T) => number;
     private itemToIndexMap;
-    private compare;
+    private innerCompare;
     constructor(compareFunction: ICompareFunction<T>);
@@ -19,3 +19,4 @@ peek(): T | undefined;
     [Symbol.iterator](): IterableIterator<T>;
-    private popAt(index);
+    private compare(a, b);
+    private removeAt(index);
     private getLeftChildIndex(nodeIndex);
@@ -22,0 +23,0 @@ private getParentIndex(nodeIndex);

lib/Heap.js

@@ -24,3 +24,3 @@ (function (factory) {
             this.itemToIndexMap = new Map();
-            this.compare = compareFunction;
+            this.innerCompare = compareFunction;
         }
@@ -39,3 +39,7 @@ peek() {
         pop() {
-            return this.popAt(0);
+            if (this.isEmpty)
+                return undefined;
+            let obj = this.items[0];
+            this.removeAt(0);
+            return obj;
         }
@@ -46,3 +50,3 @@ get size() {
         get isEmpty() {
-            return this.items.length <= 0;
+            return this.items.length === 0;
         }
@@ -53,3 +57,3 @@ remove(item) {
                 return false;
-            this.popAt(index);
+            this.removeAt(index);
             return true;
@@ -67,15 +71,26 @@ }
         }
-        popAt(index) {
-            if (this.items.length === 0)
-                return undefined;
+        compare(a, b) {
+            let result = this.innerCompare(a, b);
+            if (typeof result !== "number")
+                throw new Error(`The typeof compare result cannot be different from number: ${result}`);
+            if (isNaN(result))
+                throw new Error(`Compare result cannot be is NaN.`);
+            return result;
+        }
+        removeAt(index) {
             if (this.items.length === 1) {
                 let item = this.items[0];
                 this.clear();
-                return item;
+                return;
             }
+            if (index === this.items.length - 1) {
+                this.itemToIndexMap.delete(this.items[this.items.length - 1]);
+                this.items.splice(this.items.length - 1, 1);
+                return;
+            }
             let poppedItem = this.items[index];
             this.itemToIndexMap.delete(poppedItem);
             this.items[index] = this.items[this.items.length - 1];
+            this.items.splice(this.items.length - 1, 1);
             this.itemToIndexMap.set(this.items[index], index);
-            this.items.splice(this.items.length - 1, 1);
             let compare = this.compare(this.items[index], poppedItem);
@@ -88,3 +103,2 @@ if (compare < 0) {
             }
-            return poppedItem;
         }
@@ -91,0 +105,0 @@ getLeftChildIndex(nodeIndex) {

lib/Heap.test.js

@@ -27,5 +27,17 @@ (function (factory) {
                     heap.add(1);
-                    chai_1.assert.throws(() => { heap.add(1); });
+                    chai_1.assert.throws(() => heap.add(1));
                 });
             });
+            suite.describe("compare", suit => {
+                suite.test("When compare return typeof different then number, throws.", (t) => {
+                    let heap = new Heap_1.Heap(() => undefined);
+                    heap.add(1); // First item will not call compare.
+                    chai_1.assert.throws(() => heap.add(2));
+                });
+                suite.test("When compare return NaN, throws.", (t) => {
+                    let heap = new Heap_1.Heap(() => NaN);
+                    heap.add(1); // First item will not call compare.
+                    chai_1.assert.throws(() => heap.add(2));
+                });
+            });
             suite.describe("size", () => {
@@ -145,2 +157,12 @@ suite.test("When has element after removal.", (t) => {
                 });
+                suite.test("Removing last element in the array when length > 1.", test => {
+                    test.arrange();
+                    let heap = new Heap_1.Heap(Heap_1.minNumberCompare);
+                    heap.add(0);
+                    heap.add(1);
+                    heap.add(2);
+                    heap.add(3);
+                    test.act();
+                    heap.remove(3);
+                });
                 suite.test("Doesn't remove when not found.", (t) => {
@@ -147,0 +169,0 @@ let heap = new Heap_1.Heap(Heap_1.minNumberCompare);

package.json

 {
   "name": "ts-heap",
-  "version": "1.1.0",
+  "version": "1.1.1",
   "description": "Heap data-structure, written in typescript.",
@@ -5,0 +5,0 @@ "main": "./lib/Heap.js",

No alert changes

Improved metrics

Total package byte prevSize

34311

increased by12.01%

Lines of code

725

increased by9.85%

No dependency changes