bplustree - npm Package Compare versions

Comparing version 1.0.1 to 1.1.0

dist/bplustree.js

@@ -90,15 +90,35 @@ 'use strict';
       options || (options = {});
+      var hi = upperBound;
+      var lo = lowerBound;
 
       var result = [];
 
-      var leaf = this.fetch(lowerBound, { getLeaf: true });
+      var leaf = this.fetch(lo, { getLeaf: true });
       if (!leaf) {
-        // should we look for a new lowerBound?
-        return [];
+        // look for a new lower bound, which is quite slow
+        // check if lo is bigger than highest key in tree
+        leaf = this.tree;
+        while (leaf.t === 'branch') {
+          leaf = leaf.v[leaf.v.length - 1];
+        }
+        if (this.cmpFn(lo, leaf.k[leaf.k.length - 1]) === 1) {
+          // use cmpFn here
+          return [];
+        }
+        // ok, now this is REALLY suboptimal (and ugly)
+        var keys = this.repr({ getKeys: true });
+        for (var i = 0; i < this.numKeys; i++) {
+          if (this.cmpFn(keys[i], lo) === 1) {
+            lo = keys[i];
+            leaf = this.fetch(lo, { getLeaf: true });
+            break;
+          }
+        }
       }
 
-      var index = leaf.k.indexOf(lowerBound);
+      var index = leaf.k.indexOf(lo);
 
-      while (leaf.k[index] <= upperBound) {
-        if (this.cmpFn(leaf.k[index], upperBound) === 0) {
+      while (leaf.k[index] <= hi) {
+        if (this.cmpFn(leaf.k[index], hi) === 0) {
+          // if key at current index is upper bound, concat all vals and stop
           result = result.concat(leaf.v[index]).reduce(function (a, b) {
@@ -109,17 +129,26 @@ return a.concat(b);
         }
-        if (this.cmpFn(leaf.k[leaf.k.length - 1], upperBound) === 0) {
-          result = result.concat(leaf.v).reduce(function (a, b) {
+        if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === 0) {
+          // if last key is upper bound, concat all vals and stop
+          result = result.concat(leaf.v.slice(index)).reduce(function (a, b) {
             return a.concat(b);
           }, []);
           break;
-        } else if (this.cmpFn(leaf.k[leaf.k.length - 1], upperBound) === -1) {
+        } else if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === -1) {
+          // if last key is smaller than upper bound, fetch next leaf and iterate
           result = result.concat(leaf.v.slice(index)).reduce(function (a, b) {
             return a.concat(b);
           }, []);
-          leaf = this.fetch(leaf.n, { getLeaf: true });
-          index = 0;
+          if (leaf.n !== null) {
+            leaf = this.fetch(leaf.n, { getLeaf: true });
+            index = 0;
+          } else {
+            break;
+          }
         } else {
+          // if last key is bigger than upper bound, concat until upper bound
           var i = index;
-          for (; i < leaf.k.length && leaf.k[i] <= upperBound; i++) {}
-          result = result.concat(leaf.k.slice(0, i));
+          for (; leaf.k[i] <= hi; i++) {}
+          result = result.concat(leaf.v.slice(0, i)).reduce(function (a, b) {
+            return a.concat(b);
+          }, []);
           break;
@@ -126,0 +155,0 @@ }

lib/bplustree.js

@@ -74,29 +74,54 @@ /** Class representing a B+ Tree. */
     options || (options = {});
+    const hi = upperBound;
+    let lo = lowerBound;
 
     let result = [];
 
-    let leaf = this.fetch(lowerBound, { getLeaf: true });
-    if (!leaf) {
-      // should we look for a new lowerBound?
-      return [];
+    let leaf = this.fetch(lo, { getLeaf: true });
+    if (!leaf) { // look for a new lower bound, which is quite slow
+      // check if lo is bigger than highest key in tree
+      leaf = this.tree;
+      while (leaf.t === 'branch') {
+        leaf = leaf.v[leaf.v.length - 1];
+      }
+      if (this.cmpFn(lo, leaf.k[leaf.k.length - 1]) === 1) { // use cmpFn here
+        return [];
+      }
+      // ok, now this is REALLY suboptimal (and ugly)
+      const keys = this.repr({ getKeys: true });
+      for (let i = 0; i < this.numKeys; i++) {
+        if (this.cmpFn(keys[i], lo) === 1) {
+          lo = keys[i];
+          leaf = this.fetch(lo, { getLeaf: true });
+          break;
+        }
+      }
     }
 
-    let index = leaf.k.indexOf(lowerBound);
+    let index = leaf.k.indexOf(lo);
 
-    while (leaf.k[index] <= upperBound) {
-      if (this.cmpFn(leaf.k[index], upperBound) === 0) {
+    while (leaf.k[index] <= hi) {
+      if (this.cmpFn(leaf.k[index], hi) === 0) {
+        // if key at current index is upper bound, concat all vals and stop
         result = result.concat(leaf.v[index]).reduce((a, b) => a.concat(b), []);
         break;
       }
-      if (this.cmpFn(leaf.k[leaf.k.length - 1], upperBound) === 0) {
-        result = result.concat(leaf.v).reduce((a, b) => a.concat(b), []);
+      if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === 0) {
+        // if last key is upper bound, concat all vals and stop
+        result = result.concat(leaf.v.slice(index)).reduce((a, b) => a.concat(b), []);
         break;
-      } else if (this.cmpFn(leaf.k[leaf.k.length - 1], upperBound) === -1) {
+      } else if (this.cmpFn(leaf.k[leaf.k.length - 1], hi) === -1) {
+        // if last key is smaller than upper bound, fetch next leaf and iterate
         result = result.concat(leaf.v.slice(index)).reduce((a, b) => a.concat(b), []);
-        leaf = this.fetch(leaf.n, { getLeaf: true });
-        index = 0;
+        if (leaf.n !== null) {
+          leaf = this.fetch(leaf.n, { getLeaf: true });
+          index = 0;
+        } else {
+          break;
+        }
       } else {
+        // if last key is bigger than upper bound, concat until upper bound
         let i = index;
-        for (; i < leaf.k.length && leaf.k[i] <= upperBound; i++);
-        result = result.concat(leaf.k.slice(0, i));
+        for (; leaf.k[i] <= hi; i++);
+        result = result.concat(leaf.v.slice(0, i)).reduce((a, b) => a.concat(b), []);
         break;
@@ -103,0 +128,0 @@ }

package.json

 {
   "name": "bplustree",
-  "version": "1.0.1",
+  "version": "1.1.0",
   "scripts": {
@@ -5,0 +5,0 @@ "test": "mocha --compilers js:babel-core/register --check-leaks test/bplustree.js && npm run build",

test/bplustree.js

 /* eslint-env node, mocha */
 const BPlusTree = require('../lib/bplustree');
 const assert = require('assert');
-import {log} from '../utils/log';
 
@@ -73,3 +72,2 @@ const setup = (n) => {
     tree.store(4, 'b');
-    // assert.deepEqual(tree.fetchRange(1, 5), ['a']);
     assert.deepEqual(tree.fetchRange(4, 4), ['a', 'a', 'b']);
@@ -91,2 +89,20 @@
     assert.deepEqual(tree.fetchRange(1, 4, { descending: true }), ['z', 'b', 'c', 'c2', 'd'].reverse());
+
+    tree = new BPlusTree({ order: 50, debug: true });
+    tree.store(1, 1);
+    tree.store(1, 2);
+    tree.store(5, 2);
+    tree.store(10, 3);
+    assert.deepEqual(tree.fetchRange(1, 1), [1, 2]);
+    assert.deepEqual(tree.fetchRange(5, 5), [2]);
+    assert.deepEqual(tree.fetchRange(10, 10), [3]);
+    assert.deepEqual(tree.fetchRange(1, 5), [1, 2, 2]);
+    assert.deepEqual(tree.fetchRange(1, 10), [1, 2, 2, 3]);
+    assert.deepEqual(tree.fetchRange(1, 11), [1, 2, 2, 3]);
+    assert.deepEqual(tree.fetchRange(-1, 11), [1, 2, 2, 3]);
+    assert.deepEqual(tree.fetchRange(5, 10), [2, 3]);
+    assert.deepEqual(tree.fetchRange(1, 2), [1, 2]);
+    assert.deepEqual(tree.fetchRange(1, 20), [1, 2, 2, 3]);
+    assert.deepEqual(tree.fetchRange(-20, 20), [1, 2, 2, 3]);
+    assert.deepEqual(tree.fetchRange(4, 20), [2, 3]);
   });
@@ -93,0 +109,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

1120258

increased by0.3%

Lines of code

2080

increased by2.77%

Worsened metrics

Number of package files

39

decreased by-2.5%

No dependency changes