bintrees - npm Package Compare versions

Comparing version 0.0.7 to 0.0.8

lib/bintree.js

@@ -1,15 +0,4 @@
-(function(){
 
-var TreeBase;
+var TreeBase = require('./treebase');
 
-if(typeof module !== 'undefined' && module.exports) {
-    // CommonJS
-    var assert = require('assert');
-    TreeBase = require('./treebase');
-}
-else {
-    // browser
-    TreeBase = bintrees.TreeBase;
-}
-
 function Node(data) {
@@ -42,6 +31,2 @@ this.data = data;
 
-BinTree.prototype.assert = function() {
-    return bt_assert(this._root, this._comparator) !== 0;
-};
-
 // returns true if inserted, false if duplicate
@@ -123,30 +108,3 @@ BinTree.prototype.insert = function(data) {
 
-function bt_assert(root, comparator) {
-    if(root === null) {
-        return true;
-    }
-    else {
-        var ln = root.left;
-        var rn = root.right;
+module.exports = BinTree;
 
-        // invalid binary search tree
-        assert.equal((ln !== null && comparator(ln.data, root.data) >= 0) ||
-                         (rn !== null && comparator(rn.data, root.data) <= 0),
-                     false,
-                     "binary tree violation");
-
-        return bt_assert(ln, comparator) && bt_assert(rn, comparator);
-    }
-}
-
-if(typeof module !== 'undefined' && module.exports) {
-    // CommonJS
-    module.exports = BinTree;
-}
-else {
-    // browser
-    window.bintrees = window.bintrees || {};
-    window.bintrees.BinTree = BinTree;
-}
-
-}());

lib/rbtree.js

@@ -1,13 +0,3 @@
-(function(){
 
-var TreeBase;
-if(typeof module !== 'undefined' && module.exports) {
-    // CommonJS
-    var assert = require('assert');
-    TreeBase = require('./treebase');
-}
-else {
-    // browser
-    TreeBase = bintrees.TreeBase;
-}
+var TreeBase = require('./treebase');
 
@@ -42,6 +32,2 @@ function Node(data) {
 
-RBTree.prototype.assert = function() {
-    return rb_assert(this._root, this._comparator) !== 0;
-};
-
 // returns true if inserted, false if duplicate
@@ -233,47 +219,2 @@ RBTree.prototype.insert = function(data) {
 
-function rb_assert(root, comparator) {
-    if(root === null) {
-        return 1;
-    }
-    else {
-        var ln = root.left;
-        var rn = root.right;
-
-        // red violation
-        if(is_red(root)) {
-            assert.equal(is_red(ln) || is_red(rn), false, "red violation");
-        }
-
-        var lh = rb_assert(ln, comparator);
-        var rh = rb_assert(rn, comparator);
-
-        // invalid binary search tree
-        assert.equal((ln !== null && comparator(ln.data, root.data) >= 0) ||
-                         (rn !== null && comparator(rn.data, root.data) <= 0),
-                     false,
-                     "binary tree violation");
-
-        // black height mismatch
-        assert.equal(lh !== 0 && rh !== 0 && lh !== rh, false, "black violation");
-
-        // count black links
-        if(lh !== 0 && rh !== 0) {
-            return is_red(root) ? lh : lh + 1;
-        }
-        else {
-            return 0;
-        }
-    }
-}
-
-if(typeof module !== 'undefined' && module.exports) {
-    // CommonJS
-    module.exports = RBTree;
-}
-else {
-    // browser
-    window.bintrees = window.bintrees || {};
-    window.bintrees.RBTree = RBTree;
-}
-
-}());
+module.exports = RBTree;

lib/treebase.js

@@ -1,2 +0,1 @@
-(function(){
 
@@ -169,12 +168,3 @@ function TreeBase() {}
 
-if(typeof module !== 'undefined' && module.exports) {
-    // CommonJS
-    module.exports = TreeBase;
-}
-else {
-    // browser
-    window.bintrees = window.bintrees || {};
-    window.bintrees.TreeBase = TreeBase;
-}
+module.exports = TreeBase;
 
-}());

package.json

@@ -5,5 +5,10 @@ {
   "description": "Binary Search Trees",
-  "version": "0.0.7",
+  "version": "0.0.8",
   "homepage": "bitfloor.com",
-  "keywords": ["binary tree", "red black tree", "red-black tree", "redblack tree"],
+  "keywords": [
+    "binary tree",
+    "red black tree",
+    "red-black tree",
+    "redblack tree"
+  ],
   "repository": {
@@ -14,14 +19,16 @@ "type": "git",
   "directories": {
-      "lib": "lib"
+    "lib": "lib"
   },
   "main": "./index.js",
   "scripts": {
-    "test": "./node_modules/.bin/expresso ./test/test_*.js; ./node_modules/.bin/jshint lib/*.js"
+    "test": "nodeunit ./test/test_*.js && jshint lib/*.js index.js"
   },
-  "dependencies": {},
+  "dependencies": {
+  },
   "devDependencies": {
-      "underscore": ">=1.1.7",
-      "expresso": ">=0.8.1",
-      "jshint": ">=0.5.2"
+    "nodeunit": "0.7.4",
+    "jshint": "0.5.9",
+    "underscore": "1.3.1",
+    "reunion": "0.0.0"
   }
 }

test/perf_test.js

@@ -48,3 +48,3 @@ var fs = require('fs');
     var removes = loader.get_removes(tests);
-    
+
     console.log('build/destroy tree...');
@@ -90,2 +90,3 @@ print_times(timeit(function() {
 
+var test_funcs = {};
 TREES.forEach(function(tree) {
@@ -95,13 +96,17 @@ var tree_class = require('../lib/' + tree);
        var test_path = BASE_DIR + "/" + test;
-       exports[tree + "_" + test + "_build"] = function() {
-          build(tree_class, test_path); 
+       test_funcs[tree + "_" + test + "_build"] = function(assert) {
+          build(tree_class, test_path);
+          assert.done();
        };
-       exports[tree + "_" + test + "_build_destroy"] = function() {
-          build_destroy(tree_class, test_path); 
+       test_funcs[tree + "_" + test + "_build_destroy"] = function(assert) {
+          build_destroy(tree_class, test_path);
+          assert.done();
        };
-       exports[tree + "_" + test + "_find"] = function() {
-          find(tree_class, test_path); 
+       test_funcs[tree + "_" + test + "_find"] = function(assert) {
+          find(tree_class, test_path);
+          assert.done();
        };
-       exports[tree + "_" + test + "_interleaved"] = function() {
-          interleaved(tree_class, test_path); 
+       test_funcs[tree + "_" + test + "_interleaved"] = function(assert) {
+          interleaved(tree_class, test_path);
+          assert.done();
        };
@@ -111,1 +116,2 @@ });
 
+exports.performance = test_funcs;

test/test_api.js

@@ -1,2 +0,1 @@
-var assert = require('assert');
 var _ = require('underscore');
@@ -9,3 +8,3 @@
 
-function clear(tree_class) {
+function clear(assert, tree_class) {
     var inserts = loader.get_inserts(loader.load(SAMPLE_FILE));
@@ -19,3 +18,3 @@ var tree = loader.build_tree(tree_class, inserts);
 
-function dup(tree_class) {
+function dup(assert, tree_class) {
     var tree = loader.new_tree(tree_class);
@@ -33,3 +32,3 @@
 
-function nonexist(tree_class) {
+function nonexist(assert, tree_class) {
     var tree = loader.new_tree(tree_class);
@@ -43,3 +42,3 @@
 
-function minmax(tree_class) {
+function minmax(assert, tree_class) {
     var tree = loader.new_tree(tree_class);
@@ -56,3 +55,3 @@ assert.equal(tree.min(), null);
 
-function forward_it(tree_class) {
+function forward_it(assert, tree_class) {
     var inserts = loader.get_inserts(loader.load(SAMPLE_FILE));
@@ -79,3 +78,3 @@ var tree = loader.build_tree(tree_class, inserts);
 
-function reverse_it(tree_class) {
+function reverse_it(assert, tree_class) {
     var inserts = loader.get_inserts(loader.load(SAMPLE_FILE));
@@ -85,3 +84,3 @@ var tree = loader.build_tree(tree_class, inserts);
     var items = [];
-    
+
     var it=tree.iterator(), data;
@@ -104,3 +103,3 @@ while((data = it.prev()) !== null) {
 
-function switch_it(tree_class) {
+function switch_it(assert, tree_class) {
     var inserts = loader.get_inserts(loader.load(SAMPLE_FILE));
@@ -135,3 +134,3 @@ var tree = loader.build_tree(tree_class, inserts);
 
-function empty_it(tree_class) {
+function empty_it(assert, tree_class) {
     var tree = loader.new_tree(tree_class);
@@ -157,10 +156,15 @@
 
+var test_funcs = {};
 TREES.forEach(function(tree) {
     var tree_class = require('../lib/' + tree);
     for(var test in TESTS) {
-        exports[tree + "_" + test] = function() {
-            TESTS[test](tree_class);
-        }
+        (function(test) {
+            test_funcs[tree + "_" + test] = function(assert) {
+                TESTS[test](assert, tree_class);
+                assert.done();
+            }
+        })(test);
     }
 });
 
+exports.api = test_funcs;

test/test_correctness.js

@@ -0,3 +1,3 @@
+var fs = require('fs');
 var assert = require('assert');
-var fs = require('fs');
 
@@ -9,3 +9,71 @@ var loader = require('./loader');
 
-function run_test(tree_class, test_path) {
+function bt_assert(root, comparator) {
+    if(root === null) {
+        return true;
+    }
+    else {
+        var ln = root.left;
+        var rn = root.right;
+
+        // invalid binary search tree
+        assert.equal((ln !== null && comparator(ln.data, root.data) >= 0) ||
+                         (rn !== null && comparator(rn.data, root.data) <= 0),
+                     false,
+                     "binary tree violation");
+
+        return bt_assert(ln, comparator) && bt_assert(rn, comparator);
+    }
+}
+
+function is_red(node) {
+    return node !== null && node.red;
+}
+
+function rb_assert(root, comparator) {
+    if(root === null) {
+        return 1;
+    }
+    else {
+        var ln = root.left;
+        var rn = root.right;
+
+        // red violation
+        if(is_red(root)) {
+            assert.equal(is_red(ln) || is_red(rn), false, "red violation");
+        }
+
+        var lh = rb_assert(ln, comparator);
+        var rh = rb_assert(rn, comparator);
+
+        // invalid binary search tree
+        assert.equal((ln !== null && comparator(ln.data, root.data) >= 0) ||
+                         (rn !== null && comparator(rn.data, root.data) <= 0),
+                     false,
+                     "binary tree violation");
+
+        // black height mismatch
+        assert.equal(lh !== 0 && rh !== 0 && lh !== rh, false, "black violation");
+
+        // count black links
+        if(lh !== 0 && rh !== 0) {
+            return is_red(root) ? lh : lh + 1;
+        }
+        else {
+            return 0;
+        }
+    }
+}
+
+var assert_func = {
+    rbtree: rb_assert,
+    bintree: bt_assert
+};
+
+function tree_assert(tree_name) {
+    return function(tree) {
+        return assert_func[tree_name](tree._root, tree._comparator) !== 0;
+    }
+}
+
+function run_test(assert, tree_assert, tree_class, test_path) {
     var tree = loader.new_tree(tree_class);
@@ -31,3 +99,3 @@
         assert.equal(tree.size, elems);
-        assert.ok(tree.assert());
+        assert.ok(tree_assert(tree));
     });
@@ -38,8 +106,11 @@ }
 
+var test_funcs = {};
 TREES.forEach(function(tree) {
     var tree_class = require('../lib/' + tree);
+
     tests.forEach(function(test) {
        var test_path = BASE_DIR + "/" + test;
-       exports[tree + "_" + test] = function() {
-          run_test(tree_class, test_path); 
+       test_funcs[tree + "_" + test] = function(assert) {
+          run_test(assert, tree_assert(tree), tree_class, test_path);
+          assert.done();
        };
@@ -49,1 +120,2 @@ });
 
+exports.correctness = test_funcs;

No alert changes

Improved metrics

Total package byte prevSize

2337972

increased by1.04%

Number of package files

23

increased by43.75%

Lines of code

1438

increased by71.19%

Number of lines in readme file

94

increased by25.33%

Worsened metrics

Dev dependency count

4

increased by33.33%

No dependency changes