flatten-interval-tree - npm Package Compare versions

Comparing version 0.1.2 to 0.1.3

classes/interval.js

@@ -11,2 +11,6 @@ /**
 
+    get max() {
+        return this.high;
+    }
+
     interval(low, high) {
@@ -13,0 +17,0 @@ return new Interval(low, high);

classes/node.js

@@ -28,3 +28,3 @@ /**
         }
-        this.max = this.item.key ? this.item.key.high : undefined;
+        this.max = this.item.key ? this.item.key.max : undefined;
     }
@@ -55,3 +55,4 @@
     update_max() {
-        this.max = this.item.key ? this.item.key.high : undefined;
+        // use key (Interval) max property instead of key.high
+        this.max = this.item.key ? this.item.key.max : undefined;
         if (this.right && this.right.max) {
@@ -68,13 +69,14 @@ let maximal_val = this.item.key.maximal_val;
     // Other_node does not intersect any node of left subtree, if this.left.max < other_node.item.key.low
-    not_intersect_left_subtree(other_node) {
+    not_intersect_left_subtree(search_node) {
         let val_less_than = this.item.key.val_less_than;
-        return val_less_than(this.left.max, other_node.item.key.low);
+        let high = this.left.max.high ? this.left.max.high : this.left.max;
+        return val_less_than(high, search_node.item.key.low);
     }
 
     // Other_node does not intersect right subtree if other_node.item.key.high < this.right.key.low
-    not_intersect_right_subtree(other_node) {
+    not_intersect_right_subtree(search_node) {
         let val_less_than = this.item.key.val_less_than;
-        return val_less_than(other_node.item.key.high, this.right.item.key.low);
-    };
-
+        let low = this.right.max.low ? this.right.max.low : this.right.item.key.low;
+        return val_less_than(search_node.item.key.high, low);
+    }
 };
@@ -81,0 +83,0 @@

index.js

@@ -503,4 +503,30 @@ /**
 
+    /* Throw error if not every path from root to bottom has same black height */
+    testBlackHeightProperty(node) {
+        let height = 0;
+        let heightLeft = 0;
+        let heightRight = 0;
+        if (node.color == RB_TREE_COLOR_BLACK) {
+            height++;
+        }
+        if (node.left != nil_node) {
+            heightLeft = this.testBlackHeightProperty(node.left);
+        }
+        else {
+            heightLeft = 1;
+        }
+        if (node.right != nil_node) {
+            heightRight = this.testBlackHeightProperty(node.right);
+        }
+        else {
+            heightRight = 1;
+        }
+        if (heightLeft != heightRight) {
+            throw new Error('Red-black height property violated');
+        }
+        height += heightLeft;
+        return height;
+    };
 };
 
 module.exports = IntervalTree;

package.json

 {
   "name": "flatten-interval-tree",
-  "version": "0.1.2",
+  "version": "0.1.3",
   "description": "Interval Tree implementation as augmented extention of binary red-black tree",
@@ -5,0 +5,0 @@ "main": "index.js",

test/test.js

@@ -72,2 +72,17 @@ /**
     });
+    it('Each red node has exactly two black child nodes', function () {
+        let tree = new IntervalTree();
+        let ints = [[6,8],[1,2],[7,12],[1,1],[5,7]];
+        for (let i=0; i < ints.length; i++) tree.insert(ints[i],"val"+i)
+        expect(tree.testRedBlackProperty()).to.equal(true);
+    });
+    it('Each path from root to nil node has same black height', function () {
+        let tree = new IntervalTree();
+        let ints = [[6,8],[1,2],[7,12],[1,1],[5,7]];
+        for (let i=0; i < ints.length; i++) tree.insert(ints[i],"val"+i)
+        let height = (tree) => {
+            return tree.testBlackHeightProperty(tree.root);
+        };
+        expect(height(tree)).to.equal(3);
+    });
 });

No alert changes

Improved metrics

Total package byte prevSize

1540168

increased by0.1%

Lines of code

1514

increased by3.2%

No dependency changes