bplustree - npm Package Compare versions

Comparing version 2.0.0 to 2.0.1

__tests__/bplustree.test.js

@@ -486,1 +486,40 @@ /* eslint-disable flowtype/require-return-type */
 });
+
+let tree;
+describe('regression tests', () => {
+  describe('works over ranges with a new leaf and a removed element in the first leaf', () => {
+    beforeEach(() => {
+      tree = new BPlusTree({ order: 4, debug: true });
+      tree.store(1, 'one');
+      tree.store(2, 'two');
+      tree.store(3, 'three');
+      tree.store(4, 'four');
+      tree.store(5, 'five');
+    });
+    it('#1a', () => {
+      // https://github.com/vhf/bplustree/issues/5#issuecomment-440056079
+      tree.remove(3, 'three');
+      expect(tree.fetchRange(1, 4)).toEqual(['one', 'two', 'four']);
+      expect(tree.fetchRange(1, 2)).toEqual(['one', 'two']);
+      expect(tree.fetchRange(1, 3)).toEqual(['one', 'two']);
+      expect(tree.fetchRange(1, 5)).toEqual(['one', 'two', 'four', 'five']);
+    });
+    it('#1b', () => {
+      tree.remove(2, 'two');
+      expect(tree.fetchRange(1, 5)).toEqual(['one', 'three', 'four', 'five']);
+      expect(tree.fetchRange(2, 5)).toEqual(['three', 'four', 'five']);
+      expect(tree.fetchRange(3, 5)).toEqual(['three', 'four', 'five']);
+      expect(tree.fetchRange(4, 5)).toEqual(['four', 'five']);
+    });
+    it('#2', () => {
+      // Removing from the new leaf, instead of the old one
+      tree.remove(5, 'five');
+      expect(tree.fetchRange(1, 7)).toEqual(['one', 'two', 'three', 'four']);
+    });
+    it('#3', () => {
+      tree.remove(3, 'three');
+      // Fetching a range that does not include the removed element
+      expect(tree.fetchRange(1, 2)).toEqual(['one', 'two']);
+    });
+  });
+});

dist/bplustree.js

@@ -57,6 +57,6 @@ /** Class representing a B+ Tree. */
       if (node.t === 'branch') {
-        const kids = node.v;
+        const children = node.v;
 
-        for (let i = 0, kl = kids.length; i < kl; i++) {
-          walk(kids[i]);
+        for (let i = 0, kl = children.length; i < kl; i++) {
+          walk(children[i]);
         }
@@ -160,3 +160,4 @@ } else if (node.t === 'leaf') {
           leaf = this.fetch(leaf.n, {
-            getLeaf: true
+            getLeaf: true,
+            notFound: 'right'
           });
@@ -346,17 +347,17 @@ index = 0;
       if (node.t === 'branch') {
-        const kids = node.v;
-        const kidsLength = kids.length;
+        const children = node.v;
+        const childrenLength = children.length;
 
         if (currentDepth === 0) {
-          assert(kidsLength >= 2, 'Underpopulated root');
+          assert(childrenLength >= 2, 'Underpopulated root');
         } else {
-          assert(kidsLength >= self.minKeys, 'Underpopulated branch');
+          assert(childrenLength >= self.minKeys, 'Underpopulated branch');
         }
 
-        assert(keysLength === kidsLength - 1, 'keys and kids don\'t correspond');
+        assert(keysLength === childrenLength - 1, 'keys and children don\'t correspond');
 
-        for (let i = 0; i < kidsLength; i++) {
+        for (let i = 0; i < childrenLength; i++) {
           const newLo = i === 0 ? lo : [node.k[i - 1]];
           const newHi = i === keysLength ? hi : [node.k[i]];
-          checking(self, kids[i], currentDepth + 1, newLo, newHi);
+          checking(self, children[i], currentDepth + 1, newLo, newHi);
         }
@@ -392,3 +393,3 @@ } else if (node.t === 'leaf') {
    * @param {boolean} [options.getPath=false] - Return {val: value(s), leaf: leaf, path: pathFromRootToLeaf}
-   * @param {string} [options.notFound] - either 'left' or 'right' - Return what was found left or right from key which doesn't exist
+   * @param {string} [options.notFound] - either 'left' or 'right' - Return what was found left or right from key that doesn't exist
    * @return {Value|Value[]|Leaf|Object|Boolean}
@@ -482,3 +483,3 @@ */
       } else if (this.cmpFn(node.k[j], key) === 1) {
-        break; // just to finish quicker; not needed for correctness
+        break; // just to return early; not needed for correctness
       }
@@ -648,9 +649,9 @@ }
       if (node.t === 'branch') {
-        const kids = node.v;
+        const children = node.v;
 
-        for (let i = 0, kl = kids.length; i < kl; i++) {
-          if (kids[i].t === 'branch') {
+        for (let i = 0, kl = children.length; i < kl; i++) {
+          if (children[i].t === 'branch') {
             const newPath = path.slice(0, depth).concat([i]);
             result.push(newPath);
-            walk(kids[i], depth + 1, newPath);
+            walk(children[i], depth + 1, newPath);
           }
@@ -657,0 +658,0 @@ }

lib/bplustree.js

@@ -70,5 +70,5 @@ // @flow
       if (node.t === 'branch') {
-        const kids = node.v;
-        for (let i = 0, kl = kids.length; i < kl; i++) {
-          walk(kids[i]);
+        const children = node.v;
+        for (let i = 0, kl = children.length; i < kl; i++) {
+          walk(children[i]);
         }
@@ -153,3 +153,3 @@ } else if (node.t === 'leaf') {
         if (leaf.n !== null) {
-          leaf = this.fetch(leaf.n, { getLeaf: true });
+          leaf = this.fetch(leaf.n, { getLeaf: true, notFound: 'right' });
           index = 0;
@@ -293,17 +293,17 @@ } else {
       if (node.t === 'branch') {
-        const kids = node.v;
-        const kidsLength = kids.length;
+        const children = node.v;
+        const childrenLength = children.length;
 
         if (currentDepth === 0) {
-          assert(kidsLength >= 2, 'Underpopulated root');
+          assert(childrenLength >= 2, 'Underpopulated root');
         } else {
-          assert(kidsLength >= self.minKeys, 'Underpopulated branch');
+          assert(childrenLength >= self.minKeys, 'Underpopulated branch');
         }
 
-        assert(keysLength === kidsLength - 1, 'keys and kids don\'t correspond');
+        assert(keysLength === childrenLength - 1, 'keys and children don\'t correspond');
 
-        for (let i = 0; i < kidsLength; i++) {
+        for (let i = 0; i < childrenLength; i++) {
           const newLo = (i === 0 ? lo : [node.k[i - 1]]);
           const newHi = (i === keysLength ? hi : [node.k[i]]);
-          checking(self, kids[i], currentDepth + 1, newLo, newHi);
+          checking(self, children[i], currentDepth + 1, newLo, newHi);
         }
@@ -338,3 +338,3 @@ } else if (node.t === 'leaf') {
    * @param {boolean} [options.getPath=false] - Return {val: value(s), leaf: leaf, path: pathFromRootToLeaf}
-   * @param {string} [options.notFound] - either 'left' or 'right' - Return what was found left or right from key which doesn't exist
+   * @param {string} [options.notFound] - either 'left' or 'right' - Return what was found left or right from key that doesn't exist
    * @return {Value|Value[]|Leaf|Object|Boolean}
@@ -398,3 +398,3 @@ */
       } else if (this.cmpFn(node.k[j], key) === 1) {
-        break; // just to finish quicker; not needed for correctness
+        break; // just to return early; not needed for correctness
       }
@@ -566,8 +566,8 @@ }
       if (node.t === 'branch') {
-        const kids = node.v;
-        for (let i = 0, kl = kids.length; i < kl; i++) {
-          if (kids[i].t === 'branch') {
+        const children = node.v;
+        for (let i = 0, kl = children.length; i < kl; i++) {
+          if (children[i].t === 'branch') {
             const newPath = path.slice(0, depth).concat([i]);
             result.push(newPath);
-            walk(kids[i], depth + 1, newPath);
+            walk(children[i], depth + 1, newPath);
           }
@@ -574,0 +574,0 @@ }

package.json

 {
   "name": "bplustree",
-  "version": "2.0.0",
+  "version": "2.0.1",
   "engines": {
@@ -5,0 +5,0 @@ "node": ">=8.0.0"

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

1158302

increased by0.15%

Lines of code

2574

increased by1.54%

No dependency changes