qheap - npm Package Compare versions

Comparing version 1.0.8 to 1.1.0

lib/qheap.js

@@ -22,13 +22,15 @@ /**
     this._compar = opts.compar || defaultCompar;
+    this.length = 0;
+    this._freeSpace = opts.freeSpace ? this._trimArraySize : false;
     this._list = new Array(100);
-    this._freeSpace = opts.freeSpace ? this._trimArraySize : false;
-    this.length = 0;
 }
 
+Heap.prototype._list = null;
 Heap.prototype._compar = null;
-Heap.prototype._list = null;
 Heap.prototype._freeSpace = null;
 Heap.prototype.length = 0;
 
-// insert new item at end, and bubble up
+/*
+ * insert new item at end, and bubble up
+ */
 Heap.prototype.insert = function Heap_insert( item ) {
@@ -57,28 +59,31 @@ var idx = ++this.length;
 
-// TODO: the .length property hides the method
-Heap.prototype.length = function Heap_length( ) {
+Heap.prototype.size = function Heap_size( ) {
     return this.length;
 };
 
-// return the root, and bubble down last item
+/*
+ * return the root, and bubble down last item from top root position
+ * when bubbling down, r: root idx, c: child sub-tree root idx, cv: child root value
+ * Note that the child at (c == this.length) does not have to be tested in the loop,
+ * since its value is the one being bubbled down.
+ * Also, node-v0.10 needs the redundant (c < len) test in the loop, else runs 3x slower.
+ */
 Heap.prototype.remove = function Heap_remove( ) {
     if (this.length < 1) return undefined;
     var ret = this._list[1];
-    var itm = this._list[this.length--];
+    var itm = this._list[this.length];
+    this._list[this.length] = 0;
+    var len = --this.length;
 
-    if (this.length > 0) {
-        var r = 1, c = 2, cv;
-        while (c <= this.length) {
-            cv = this._list[c];
-            if (c < this.length && this._compar(this._list[c+1], cv) < 0) { cv = this._list[c+1] ; c = c+1 }
-            if (this._compar(cv, itm) < 0) {
-                this._list[r] = cv;
-                r = c;
-                c = c << 1;
-            }
-            else break;
-        }
-        this._list[r] = itm;
-        if (this._freeSpace) this._freeSpace(this._list, this.length);
+    var r = 1, c = 2, cv;
+    while (c < len) {
+        cv = this._list[c];
+        if (c < len && this._compar(this._list[c+1], cv) < 0) { cv = this._list[c+1] ; c = c+1 }
+        if (!(this._compar(cv, itm) < 0)) break;
+        this._list[r] = cv;
+        r = c;
+        c = c << 1;
     }
+    if (len) this._list[r] = itm;
+    if (this._freeSpace) this._freeSpace(this._list, len);
 
@@ -101,11 +106,13 @@ return ret;
     var compar = function(a,b) { return comparfn(a, b); }
-    var i, fail = 0;
+    var i, p, fail = 0;
     for (i=this.length; i>1; i--) {
         // error if parent should go after child, but not if don`t care
-        if (compar((i/2|0), i) > 0 && this._compar(i, (i/2|0)) < 0) fail = i;
+        p = i >>> 1;
+        if (compar(p, i) > 0 && this._compar(i, p) < 0) fail = i;
     }
-    if (fail) console.log("failed at", (fail/2|0), fail);
+    if (fail) console.log("failed at", (fail >>> 1), fail);
     return !fail;
 }
 
+// optimize access
 Heap.prototype = Heap.prototype;

package.json

 {
   "name": "qheap",
-  "version": "1.0.8",
+  "version": "1.1.0",
   "description": "binary heap priority queue",
@@ -19,4 +19,7 @@ "license": "Apache-2.0",
   "scripts": {
-    "test": "nodeunit"
+    "test": "qnit test/test-*"
   },
+  "devDependencies": {
+    "qnit": "0.11.0"
+  },
   "keywords": [
@@ -23,0 +26,0 @@ "Andras",

test/benchmark.js

@@ -1,2 +0,2 @@
-if (process.argv[1] && process.argv[1].indexOf('nodeunit') > 0) return;
+if (process.argv[1] && process.argv[1].indexOf('qnit') > 0) return;
 
@@ -13,3 +13,3 @@ Heap = require('../index');
 
-if (1) {
+if (0) {
     // for (i=0; i<nloops; i++) q = new Heap();    // churn?
@@ -16,0 +16,0 @@

test/quicktest.js

@@ -1,2 +0,2 @@
-if (process.argv[1] && process.argv[1].indexOf('nodeunit') > 0) return;
+if (process.argv[1] && process.argv[1].indexOf('qnit') > 0) return;
 
@@ -3,0 +3,0 @@ var Heap = require('../index');

test/test-qheap.js

@@ -110,2 +110,22 @@ /**
     },
+
+    'fuzz test': function(t) {
+        for (var nitems=2; nitems<8; nitems++) {
+            for (var loop=0; loop<20000; loop++) {
+                var cut = new Heap();
+                for (var i=0; i<nitems; i++) {
+                    // bubbles up new value into correct position after insert
+                    cut.insert((Math.random() * 1000 + 1) >> 0);
+                    t.ok(cut._check());
+                    t.ok(cut.length, i+1);
+                }
+                for (var i=0; i<nitems; i++) {
+                    // bubbles down last element into correct position after remove
+                    cut.remove();
+                    t.ok(cut._check());
+                }
+            }
+        }
+        t.done();
+    },
 };

No alert changes

Improved metrics

Total package byte prevSize

16101

increased by6.88%

Lines of code

332

increased by8.5%

Worsened metrics

Dev dependency count

1

increased byInfinity%

No dependency changes