js-redblacktree - npm Package Compare versions

Comparing version 1.0.6 to 1.0.7

package.json

 {
   "name": "js-redblacktree",
-  "version": "1.0.6",
+  "version": "1.0.7",
   "description": "Package implements left leaning red black balanced search tree for symbol table key-sorted map",
@@ -5,0 +5,0 @@ "author": "Caishun Chen",

README.md

@@ -8,3 +8,8 @@ # js-redblacktree
 
+# Features
 
+* Balanced Search Tree with Left Leaning Red Black Tree
+* Customizable comparer function for keys
+
+
 # Install
@@ -52,2 +57,17 @@
 
+console.log(bst.minKey()); 
+console.log(bst.maxKey());
+
+```
+
+If you are handling key which requires custom comparer, you can do so in the constructor:
+
+```javascript
+var jsrbtree = require("js-redblacktree");
+
+var compare = function(a1, a2){
+    return a1 - a2;
+};
+
+var bst = new jsrbtree.RedBlackTree(compare);
 ```

src/jsrbtree.js

@@ -6,6 +6,2 @@ var jsrbtree = jsrbtree || {};
 	
-    jss.less = function (a1, a2, compare) {
-        return compare(a1, a2) < 0; 
-    };
-    
     var Node = function (key, value) {
@@ -50,2 +46,7 @@ this.key = key;
         
+        if(this._isRed(x.right) && !this._isRed(x.left)) x = this._rotateLeft(x);
+        if(this._isRed(x.left) && this._isRed(x.left.left)) x = this._rotateRight(x);
+        if(this._isRed(x.left) && this._isRed(x.right)) this._flipColor(x);
+        
+        
         x.count = 1 + this._count(x.left) + this._count(x.right);
@@ -117,8 +118,6 @@
             else {
-                var m = this._min(x.right);
-
-                m.left = x.left;
-                m.right = this._delMin(x.right);
-
-                x = m;
+                var t = x;
+                x = this._min(t.right);
+                x.right = this._delMin(t.right);
+                x.left = t.left;
             }
@@ -133,3 +132,2 @@ }
             
-            
             x.count = 1 + this._count(x.left) + this._count(x.right);
@@ -187,2 +185,28 @@ }
     
+    RedBlackTree.prototype._max = function (x) {
+        if (x == null) {
+            return null;
+        }  
+        if (x.right == null) {
+            return x;
+        }
+        return this._max(x.right);
+    };
+    
+    RedBlackTree.prototype.minKey = function (x) {
+        var x = this._min(this.root);
+        if (x != null) {
+            return x.key;
+        }
+        return undefined;
+    };
+    
+    RedBlackTree.prototype.maxKey = function(x) {
+        var x = this._max(this.root);
+        if (x != null) {
+            return x.key;
+        }
+        return undefined;
+    };
+    
     RedBlackTree.prototype._delMin = function (x) {
@@ -193,3 +217,3 @@ if (x == null) {
         
-        if (x.left = null) {
+        if (x.left == null) {
             return x.right;
@@ -199,5 +223,3 @@ }
         x.left = this._delMin(x.left);
-        
         x.count = 1 + this._count(x.left) + this._count(x.right);
-        
         return x;
@@ -204,0 +226,0 @@ };

test/bst-spec.js

@@ -35,2 +35,4 @@ var expect    = require("chai").expect;
         bst.put(6, 5.4);
+        expect(bst.minKey()).to.equal(2);
+        expect(bst.maxKey()).to.equal(6);
         expect(bst.size()).to.equal(4);
@@ -67,3 +69,71 @@ expect(bst.containsKey(6));
   });
-         
+     
+  describe("with customized comparer", function() {
+    
+    it("should store two values at this point", function() {
+        var bst = new jsrbtree.RedBlackTree(function (a1, a2){
+            return a2 - a1; // sort descendingly instead of default ascendingly
+        });
+      
+        bst.put(2, 2.4);
+        bst.put(4, 3.2);
+        bst.put(5, 3.4);
+        bst.put(6, 3.4);
+        expect(bst.minKey()).to.equal(6);
+        expect(bst.maxKey()).to.equal(2);
+        expect(bst.size()).to.equal(4);
+        expect(bst.get(2)).to.equal(2.4);
+        expect(bst.get(4)).to.equal(3.2);
+        expect(bst.isEmpty()).to.equal(false);
+        expect(bst.containsKey(2)).to.equal(true);
+        expect(bst.containsKey(4)).to.equal(true);
+        expect(bst.get(3)).to.equal(undefined);
+        expect(bst.get(6)).to.equal(3.4);
+    });
+      
+    
+    it("should overwrite old value when put using same key", function(){
+        var bst = new jsrbtree.RedBlackTree(function (a1, a2){
+            return a2 - a1; // sort descendingly instead of default ascendingly
+        });
+      
+        bst.put(2, 2.4);
+        bst.put(4, 3.2);
+        bst.put(5, 3.4);
+        bst.put(6, 3.4);
+        bst.put(6, 5.4);
+        expect(bst.size()).to.equal(4);
+        expect(bst.containsKey(6));
+        expect(bst.get(6)).to.equal(5.4);
+        
+        var keys = bst.keySet();
+        for(var i = 1; i < keys.length; ++i) {
+            expect(keys[i-1]).to.above(keys[i]);
+        }
+    });
+      
+    it("should delete correctly", function () {
+        var bst = new jsrbtree.RedBlackTree(function (a1, a2){
+            return a2 - a1; // sort descendingly instead of default ascendingly
+        });
+        
+        for(var i = 0; i < 100; i+=2) {
+            bst.put(i, i);
+        }
+        for(var i = 1; i < 100; i+=2) {
+            bst.put(i, i);
+        }
+        
+        var count = 100;
+        expect(bst.size()).to.equal(count);
+        for(var i = 0; i < 100; i += 5) {
+            bst.delete(i);
+            count--;
+            expect(bst.size()).to.equal(count);
+        }
+    });
+    
+
+  });
+      
 });

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

15357

increased by27.83%

Lines of code

335

increased by31.89%

Number of lines in readme file

71

increased by39.22%

No dependency changes