bplustree - npm Package Compare versions

Comparing version 1.1.8 to 1.2.0

dist/bplustree.js

 'use strict';
 
-var _createClass = (function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; })();
+var _typeof = typeof Symbol === "function" && typeof Symbol.iterator === "symbol" ? function (obj) { return typeof obj; } : function (obj) { return obj && typeof Symbol === "function" && obj.constructor === Symbol && obj !== Symbol.prototype ? "symbol" : typeof obj; };
 
+var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }();
+
+require('regenerator-runtime/runtime');
+
 function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
 
 /** Class representing a B+ Tree. */
-
-var BPlusTree = (function () {
+var BPlusTree = function () {
   /**
@@ -16,12 +19,10 @@ * @param {Object} options
    */
-
   function BPlusTree() {
-    var _ref = arguments.length <= 0 || arguments[0] === undefined ? {} : arguments[0];
-
-    var _ref$order = _ref.order;
-    var order = _ref$order === undefined ? 6 : _ref$order;
-    var _ref$debug = _ref.debug;
-    var debug = _ref$debug === undefined ? false : _ref$debug;
-    var _ref$cmpFn = _ref.cmpFn;
-    var cmpFn = _ref$cmpFn === undefined ? function (a, b) {
+    var _ref = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
+        _ref$order = _ref.order,
+        order = _ref$order === undefined ? 6 : _ref$order,
+        _ref$debug = _ref.debug,
+        debug = _ref$debug === undefined ? false : _ref$debug,
+        _ref$cmpFn = _ref.cmpFn,
+        cmpFn = _ref$cmpFn === undefined ? function (a, b) {
       return a < b ? -1 : a > b ? 1 : 0;
@@ -58,16 +59,16 @@ } : _ref$cmpFn;
 
+
   _createClass(BPlusTree, [{
     key: 'repr',
     value: function repr() {
-      var _ref2 = arguments.length <= 0 || arguments[0] === undefined ? {} : arguments[0];
+      var _ref2 = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
+          _ref2$root = _ref2.root,
+          root = _ref2$root === undefined ? this.tree : _ref2$root,
+          _ref2$getKeys = _ref2.getKeys,
+          getKeys = _ref2$getKeys === undefined ? false : _ref2$getKeys,
+          _ref2$getValues = _ref2.getValues,
+          getValues = _ref2$getValues === undefined ? false : _ref2$getValues,
+          _ref2$descending = _ref2.descending,
+          descending = _ref2$descending === undefined ? false : _ref2$descending;
 
-      var _ref2$root = _ref2.root;
-      var root = _ref2$root === undefined ? this.tree : _ref2$root;
-      var _ref2$getKeys = _ref2.getKeys;
-      var getKeys = _ref2$getKeys === undefined ? false : _ref2$getKeys;
-      var _ref2$getValues = _ref2.getValues;
-      var getValues = _ref2$getValues === undefined ? false : _ref2$getValues;
-      var _ref2$descending = _ref2.descending;
-      var descending = _ref2$descending === undefined ? false : _ref2$descending;
-
       var tree = root;
@@ -82,9 +83,9 @@ var result = getKeys || getValues ? [] : {};
         } else if (node.t === 'leaf') {
-          for (var i = 0, nkl = node.k.length; i < nkl; i++) {
+          for (var _i = 0, nkl = node.k.length; _i < nkl; _i++) {
             if (getKeys) {
-              result.push(node.k[i]);
+              result.push(node.k[_i]);
             } else if (getValues) {
-              result.push(node.v[i]);
+              result.push(node.v[_i]);
             } else {
-              result[node.k[i]] = node.v[i];
+              result[node.k[_i]] = node.v[_i];
             }
@@ -115,7 +116,6 @@ }
     value: function fetchRange(lowerBound, upperBound) {
-      var _ref3 = arguments.length <= 2 || arguments[2] === undefined ? {} : arguments[2];
+      var _ref3 = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : {},
+          _ref3$descending = _ref3.descending,
+          descending = _ref3$descending === undefined ? false : _ref3$descending;
 
-      var _ref3$descending = _ref3.descending;
-      var descending = _ref3$descending === undefined ? false : _ref3$descending;
-
       var hi = upperBound;
@@ -171,5 +171,5 @@ var lo = lowerBound;
           // if last key is bigger than upper bound, concat until upper bound
-          var i = index;
-          for (; leaf.k[i] <= hi; i++) {}
-          result.push(leaf.v.slice(0, i));
+          var _i2 = index;
+          for (; leaf.k[_i2] <= hi; _i2++) {}
+          result.push(leaf.v.slice(0, _i2));
           break;
@@ -193,2 +193,137 @@ }
     /**
+     * Tree values generator. It will start generating values from a certain key
+     * until the end of the tree OR until `target` is found OR until `limit`
+     * is reached OR until there are no elements anymore.
+     *
+     * In other words:
+     * - if `target` is found before `limit`, it'll stop
+     * - if `limit` is reached before `target` was found, it'll stop
+     * - `target` and `limit` are both optional: use none of them, one of them, or both
+     * - `keyNotFound` is optional, it lets you decide which key to prefer when the key is not found
+     * @param {Object} options
+     * @param {Key} [options.key] - Key at which to start generating.
+     * @param {boolean} [options.target] - Stop generating when this value is found.
+     * @param {number} [options.limit] - Generate at max this number of values.
+     * @param {string} [options.keyNotFound] - See `notFound` of `BPlusTree.fetch`
+     * @return {Generator}
+     */
+
+  }, {
+    key: 'values',
+    value: regeneratorRuntime.mark(function values() {
+      var _ref4 = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
+          key = _ref4.key,
+          target = _ref4.target,
+          _ref4$limit = _ref4.limit,
+          limit = _ref4$limit === undefined ? Infinity : _ref4$limit,
+          keyNotFound = _ref4.keyNotFound;
+
+      var returned, leaf, i, length, remainder;
+      return regeneratorRuntime.wrap(function values$(_context) {
+        while (1) {
+          switch (_context.prev = _context.next) {
+            case 0:
+              returned = 0;
+              leaf = void 0;
+
+              if ((typeof key === 'undefined' ? 'undefined' : _typeof(key)) === undefined) {
+                key = -Infinity;
+                keyNotFound = 'right';
+              }
+              leaf = this.fetch(key, { getLeaf: true, notFound: keyNotFound });
+
+              if (leaf) {
+                _context.next = 6;
+                break;
+              }
+
+              return _context.abrupt('return', false);
+
+            case 6:
+              if (!true) {
+                _context.next = 33;
+                break;
+              }
+
+              i = 0;
+
+            case 8:
+              if (!(i < leaf.v.length)) {
+                _context.next = 26;
+                break;
+              }
+
+              length = leaf.v[i].length;
+
+              returned += length;
+
+              if (!(returned >= limit)) {
+                _context.next = 17;
+                break;
+              }
+
+              remainder = length - (returned - limit);
+
+              if (!(remainder >= 0)) {
+                _context.next = 15;
+                break;
+              }
+
+              return _context.abrupt('return', leaf.v[i].slice(0, remainder));
+
+            case 15:
+              _context.next = 17;
+              return leaf.v[i];
+
+            case 17:
+              if (!(target && leaf.v[i].indexOf(target) !== -1)) {
+                _context.next = 19;
+                break;
+              }
+
+              return _context.abrupt('return', leaf.v[i]);
+
+            case 19:
+              if (!(leaf.n === null && i + 1 === leaf.v.length)) {
+                _context.next = 21;
+                break;
+              }
+
+              return _context.abrupt('return', leaf.v[i]);
+
+            case 21:
+              _context.next = 23;
+              return leaf.v[i];
+
+            case 23:
+              i++;
+              _context.next = 8;
+              break;
+
+            case 26:
+              if (!(leaf.n !== null)) {
+                _context.next = 30;
+                break;
+              }
+
+              leaf = this.fetch(leaf.n, { getLeaf: true, notFound: keyNotFound });
+              _context.next = 31;
+              break;
+
+            case 30:
+              return _context.abrupt('break', 33);
+
+            case 31:
+              _context.next = 6;
+              break;
+
+            case 33:
+            case 'end':
+              return _context.stop();
+          }
+        }
+      }, values, this);
+    })
+
+    /**
      * Get tree depth (or height)
@@ -203,7 +338,6 @@ * @param {Object} options
     value: function depth() {
-      var _ref4 = arguments.length <= 0 || arguments[0] === undefined ? {} : arguments[0];
+      var _ref5 = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
+          _ref5$root = _ref5.root,
+          root = _ref5$root === undefined ? this.tree : _ref5$root;
 
-      var _ref4$root = _ref4.root;
-      var root = _ref4$root === undefined ? this.tree : _ref4$root;
-
       var tree = root;
@@ -228,7 +362,6 @@ var d = 0;
     value: function check() {
-      var _ref5 = arguments.length <= 0 || arguments[0] === undefined ? {} : arguments[0];
+      var _ref6 = arguments.length > 0 && arguments[0] !== undefined ? arguments[0] : {},
+          _ref6$root = _ref6.root,
+          root = _ref6$root === undefined ? this.tree : _ref6$root;
 
-      var _ref5$root = _ref5.root;
-      var root = _ref5$root === undefined ? this.tree : _ref5$root;
-
       var depth = this.depth({ root: root });
@@ -267,6 +400,6 @@
 
-          for (var i = 0; i < kidsLength; i++) {
-            var newLo = i === 0 ? lo : [node.k[i - 1]];
-            var newHi = i === keysLength ? hi : [node.k[i]];
-            checking(self, kids[i], currentDepth + 1, newLo, newHi);
+          for (var _i3 = 0; _i3 < kidsLength; _i3++) {
+            var newLo = _i3 === 0 ? lo : [node.k[_i3 - 1]];
+            var newHi = _i3 === keysLength ? hi : [node.k[_i3]];
+            checking(self, kids[_i3], currentDepth + 1, newLo, newHi);
           }
@@ -290,3 +423,6 @@ } else if (node.t === 'leaf') {
     /**
-     * Fetch the value(s) stored at `key`
+     * Fetch the value(s) stored at `key`.
+     * - `getLeaf` returns the whole leaf
+     * - `getPath` returns the path from the root to this leaf
+     * - when defined, `notFound` can be either 'left' or 'right', it controls which key to return when it wasn't found
      * @param {Key} key
@@ -297,3 +433,4 @@ * @param {Object} options
      * @param {boolean} [options.getPath=false] - Return {val: value(s), leaf: leaf, path: pathFromRootToLeaf}
-     * @return {Value|Value[]|Leaf|Object}
+     * @param {string} [options.notFound=left|right] - Return what was found left or right from key which doesn't exist
+     * @return {Value|Value[]|Leaf|Object|Boolean}
      */
@@ -304,14 +441,14 @@
     value: function fetch(key) {
-      var _ref6 = arguments.length <= 1 || arguments[1] === undefined ? {} : arguments[1];
+      var _ref7 = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : {},
+          _ref7$root = _ref7.root,
+          root = _ref7$root === undefined ? this.tree : _ref7$root,
+          _ref7$getLeaf = _ref7.getLeaf,
+          getLeaf = _ref7$getLeaf === undefined ? false : _ref7$getLeaf,
+          _ref7$getPath = _ref7.getPath,
+          getPath = _ref7$getPath === undefined ? false : _ref7$getPath,
+          notFound = _ref7.notFound;
 
-      var _ref6$root = _ref6.root;
-      var root = _ref6$root === undefined ? this.tree : _ref6$root;
-      var _ref6$getLeaf = _ref6.getLeaf;
-      var getLeaf = _ref6$getLeaf === undefined ? false : _ref6$getLeaf;
-      var _ref6$getPath = _ref6.getPath;
-      var getPath = _ref6$getPath === undefined ? false : _ref6$getPath;
-
       var node = root;
 
-      var index = undefined;
+      var index = void 0;
       var path = [];
@@ -334,4 +471,5 @@ while (node.t === 'branch') {
 
-      for (var j = 0, kl = node.k.length; j < kl; j++) {
-        if (this.cmpFn(key, node.k[j]) === 0) {
+      for (var j = 0, _kl = node.k.length; j < _kl; j++) {
+        var cmp = this.cmpFn(key, node.k[j]);
+        if (cmp === 0) {
           var val = node.v[j];
@@ -345,2 +483,22 @@ if (getPath) {
           return val;
+        } else if (notFound) {
+          if (notFound === 'right' && !(cmp < 0)) {
+            return this.fetch(node.n, { root: root, getLeaf: getLeaf, getPath: getPath });
+          }
+          node = this._get(path);
+          var _val = void 0;
+          if (notFound === 'left' && !(cmp < 0)) {
+            _val = node.v[node.v.length - 1];
+          } else if (notFound === 'right') {
+            _val = node.v[0];
+          }
+          if (_val) {
+            if (getPath) {
+              return { val: _val, leaf: node, path: path };
+            }
+            if (getLeaf) {
+              return node;
+            }
+            return _val;
+          }
         } else if (this.cmpFn(node.k[j], key) === 1) {
@@ -360,6 +518,6 @@ break; // just to finish quicker; not needed for correctness
       while (node.t === 'branch') {
-        var _i = 0;
+        var _i4 = 0;
         var _found = false;
-        for (var _nkl = node.k.length; _i < _nkl; _i++) {
-          if (this.cmpFn(key, node.k[_i]) === -1) {
+        for (var _nkl = node.k.length; _i4 < _nkl; _i4++) {
+          if (this.cmpFn(key, node.k[_i4]) === -1) {
             _found = true;
@@ -370,6 +528,6 @@ break;
         if (!_found) {
-          _i = node.k.length;
+          _i4 = node.k.length;
         }
-        path.push({ t: node.t, k: node.k, v: node.v, i: _i });
-        node = node.v[_i];
+        path.push({ t: node.t, k: node.k, v: node.v, i: _i4 });
+        node = node.v[_i4];
       }
@@ -447,4 +605,6 @@
     key: '_get',
-    value: function _get(path, node) {
-      var object = node || this.tree;
+    value: function _get(path) {
+      var node = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : this.tree;
+
+      var object = node;
       var index = 0;
@@ -565,3 +725,3 @@ var length = path.length;
       var valCount = fetched.leaf.v[keyIndex].length;
-      var removed = undefined;
+      var removed = void 0;
 
@@ -639,6 +799,6 @@ // we only have one val, remove it together with its key
           canBorrowLeft = true;
-          var keyToBorrow = leftSibling.k.pop();
-          var valBorrowed = leftSibling.v.pop();
-          leaf.k.unshift(keyToBorrow);
-          leaf.v.unshift(valBorrowed);
+          var _keyToBorrow = leftSibling.k.pop();
+          var _valBorrowed = leftSibling.v.pop();
+          leaf.k.unshift(_keyToBorrow);
+          leaf.v.unshift(_valBorrowed);
           parent.k = parent.v.slice(1).map(function (o) {
@@ -654,3 +814,3 @@ return o.k[0];
         var again = true;
-        var lastIndex = undefined;
+        var lastIndex = void 0;
         while (again) {
@@ -690,10 +850,10 @@ parent = this._get(path);
             } else if (rightExists) {
-                if (!roomOnRight) {
-                  splitIndex = lastIndex;
-                }
-                // merging with right, deleting sibling
-                // node becomes (node merged with sibling)
-                parent.v[lastIndex] = this._mergeRight(parent.v[lastIndex + 1], parent.v[lastIndex]);
-                parent.v.splice(lastIndex + 1, 1); // delete now merged sibling
+              if (!roomOnRight) {
+                splitIndex = lastIndex;
               }
+              // merging with right, deleting sibling
+              // node becomes (node merged with sibling)
+              parent.v[lastIndex] = this._mergeRight(parent.v[lastIndex + 1], parent.v[lastIndex]);
+              parent.v.splice(lastIndex + 1, 1); // delete now merged sibling
+            }
             if (splitIndex !== false) {
@@ -720,11 +880,11 @@ var branchToSplit = parent.v[splitIndex];
             // need to split
-            var mid = this.minKeys;
-            var leftContent = this.tree.v[index].v.slice(0, mid);
-            var rightContent = this.tree.v[index].v.slice(mid);
-            var left = { t: 'branch', k: [leftContent[leftContent.length - 1].k[0]], v: leftContent };
-            var right = { t: 'branch', k: [rightContent[rightContent.length - 1].k[0]], v: rightContent };
+            var _mid = this.minKeys;
+            var _leftContent = this.tree.v[index].v.slice(0, _mid);
+            var _rightContent = this.tree.v[index].v.slice(_mid);
+            var _left = { t: 'branch', k: [_leftContent[_leftContent.length - 1].k[0]], v: _leftContent };
+            var _right = { t: 'branch', k: [_rightContent[_rightContent.length - 1].k[0]], v: _rightContent };
             this.tree.t = 'branch';
             this.tree.n = null;
-            this.tree.k = [right.v[0].k[0]];
-            this.tree.v = [left, right];
+            this.tree.k = [_right.v[0].k[0]];
+            this.tree.v = [_left, _right];
           } else {
@@ -785,4 +945,4 @@ // need to hoist
   return BPlusTree;
-})();
+}();
 
 module.exports = BPlusTree;

lib/bplustree.js

@@ -0,1 +1,3 @@
+import 'regenerator-runtime/runtime';
+
 /** Class representing a B+ Tree. */
@@ -144,2 +146,58 @@ class BPlusTree {
   /**
+   * Tree values generator. It will start generating values from a certain key
+   * until the end of the tree OR until `target` is found OR until `limit`
+   * is reached OR until there are no elements anymore.
+   *
+   * In other words:
+   * - if `target` is found before `limit`, it'll stop
+   * - if `limit` is reached before `target` was found, it'll stop
+   * - `target` and `limit` are both optional: use none of them, one of them, or both
+   * - `keyNotFound` is optional, it lets you decide which key to prefer when the key is not found
+   * @param {Object} options
+   * @param {Key} [options.key] - Key at which to start generating.
+   * @param {boolean} [options.target] - Stop generating when this value is found.
+   * @param {number} [options.limit] - Generate at max this number of values.
+   * @param {string} [options.keyNotFound] - See `notFound` of `BPlusTree.fetch`
+   * @return {Generator}
+   */
+  * values({ key, target, limit = Infinity, keyNotFound } = {}) {
+    let returned = 0;
+    let leaf;
+    if (typeof key === undefined) {
+      key = -Infinity;
+      keyNotFound = 'right';
+    }
+    leaf = this.fetch(key, { getLeaf: true, notFound: keyNotFound });
+    if (!leaf) {
+      return false;
+    }
+
+    while (true) {
+      for (let i = 0; i < leaf.v.length; i++) {
+        const length = leaf.v[i].length;
+        returned += length;
+        if (returned >= limit) {
+          const remainder = length - (returned - limit);
+          if (remainder >= 0) {
+            return leaf.v[i].slice(0, remainder);
+          }
+          yield leaf.v[i];
+        }
+        if (target && leaf.v[i].indexOf(target) !== -1) {
+          return leaf.v[i];
+        }
+        if (leaf.n === null && i + 1 === leaf.v.length) {
+          return leaf.v[i];
+        }
+        yield leaf.v[i];
+      }
+      if (leaf.n !== null) {
+        leaf = this.fetch(leaf.n, { getLeaf: true, notFound: keyNotFound });
+      } else {
+        break;
+      }
+    }
+  }
+
+  /**
    * Get tree depth (or height)
@@ -222,3 +280,6 @@ * @param {Object} options
   /**
-   * Fetch the value(s) stored at `key`
+   * Fetch the value(s) stored at `key`.
+   * - `getLeaf` returns the whole leaf
+   * - `getPath` returns the path from the root to this leaf
+   * - when defined, `notFound` can be either 'left' or 'right', it controls which key to return when it wasn't found
    * @param {Key} key
@@ -229,5 +290,6 @@ * @param {Object} options
    * @param {boolean} [options.getPath=false] - Return {val: value(s), leaf: leaf, path: pathFromRootToLeaf}
-   * @return {Value|Value[]|Leaf|Object}
+   * @param {string} [options.notFound=left|right] - Return what was found left or right from key which doesn't exist
+   * @return {Value|Value[]|Leaf|Object|Boolean}
    */
-  fetch(key, { root = this.tree, getLeaf = false, getPath = false } = {}) {
+  fetch(key, { root = this.tree, getLeaf = false, getPath = false, notFound } = {}) {
     let node = root;
@@ -254,3 +316,4 @@
     for (let j = 0, kl = node.k.length; j < kl; j++) {
-      if (this.cmpFn(key, node.k[j]) === 0) {
+      const cmp = this.cmpFn(key, node.k[j]);
+      if (cmp === 0) {
         const val = node.v[j];
@@ -264,2 +327,22 @@ if (getPath) {
         return val;
+      } else if (notFound) {
+        if (notFound === 'right' && !(cmp < 0)) {
+          return this.fetch(node.n, { root, getLeaf, getPath });
+        }
+        node = this._get(path);
+        let val;
+        if (notFound === 'left' && !(cmp < 0)) {
+          val = node.v[node.v.length - 1];
+        } else if (notFound === 'right') {
+          val = node.v[0];
+        }
+        if (val) {
+          if (getPath) {
+            return { val, leaf: node, path };
+          }
+          if (getLeaf) {
+            return node;
+          }
+          return val;
+        }
       } else if (this.cmpFn(node.k[j], key) === 1) {
@@ -359,4 +442,4 @@ break; // just to finish quicker; not needed for correctness
 
-  _get(path, node) {
-    let object = node || this.tree;
+  _get(path, node = this.tree) {
+    let object = node;
     let index = 0;
@@ -363,0 +446,0 @@ const length = path.length;

package.json

 {
   "name": "bplustree",
-  "version": "1.1.8",
+  "version": "1.2.0",
   "scripts": {
@@ -9,4 +9,4 @@ "test": "mocha --compilers js:babel-core/register --check-leaks test/bplustree.js && npm run build",
     "coverage": "babel-node node_modules/isparta/bin/isparta cover ./node_modules/mocha/bin/_mocha -- test/bplustree.js",
-    "coverage-full": "babel-node node_modules/isparta/bin/isparta cover ./node_modules/mocha/bin/_mocha -- test/bplustree.js test/full.js",
-    "coveralls": "npm run coverage-full && cat ./coverage/lcov.info | coveralls",
+    "coverage-full": "./node_modules/.bin/babel-node ./node_modules/.bin/babel-istanbul cover ./node_modules/.bin/_mocha -- test/bplustree.js test/full.js",
+    "coveralls": "npm run coverage-full && cat /home/travis/build/vhf/bplustree/coverage/lcov.info | coveralls",
     "doc": "jsdoc lib -d docs",
@@ -18,10 +18,12 @@ "build": "babel lib -d dist"
     "babel-core": "^6.3.15",
-    "babel-eslint": "^4.1.6",
-    "babel-preset-es2015": "^6.3.13",
+    "babel-eslint": "^7.1.0",
+    "babel-istanbul": "^0.11.0",
+    "babel-plugin-transform-regenerator": "^6.16.1",
+    "babel-preset-latest": "^6.16.0",
     "coveralls": "^2.11.6",
-    "eslint": "^1.10.3",
-    "eslint-config-airbnb": "^2.0.0",
-    "eslint-plugin-react": "^3.11.3",
-    "isparta": "^4.0.0",
-    "mocha": "^2.3.4",
+    "eslint": "^3.9.1",
+    "eslint-config-airbnb-base": "^10.0.1",
+    "eslint-plugin-import": "^2.1.0",
+    "istanbul": "^0.4.5",
+    "mocha": "^3.1.2",
     "mocha-lcov-reporter": "^1.0.0"
@@ -31,3 +33,6 @@ },
   "main": "dist/bplustree.js",
-  "dependencies": {},
+  "dependencies": {
+    "babel-polyfill": "^6.16.0",
+    "regenerator-runtime": "^0.9.6"
+  },
   "repository": {
@@ -34,0 +39,0 @@ "type": "git",

README.md

@@ -6,2 +6,11 @@ # bplustree
 
+# Features
+
+* Insert
+* Delete
+* Fetch
+* Fetch ranges
+* Fetch as generator
+* Check tree invariants
+
 # Installation
@@ -11,6 +20,8 @@
 
-# Usage
+# Very Basic Usage (useless)
 
-`var BPlusTree = require('bplustree');`
+`const BPlusTree = require('bplustree');`
 
+# Much Better Documentation (useful)
+
 [API / Documentation](https://rawgit.com/vhf/bplustree/master/docs/BPlusTree.html)
@@ -27,6 +38,2 @@
 
-# Dependencies
-
-None
-
 # License
@@ -33,0 +40,0 @@

test/bplustree.js

@@ -7,3 +7,3 @@ /* eslint-env node, mocha */
   const tree = new BPlusTree({ order: 4, debug: true });
-  const data = [[1, 'z'], [2, 'b'], [3, 'c'], [3, 'c2'], [4, 'd'], [5, 'e'], [6, 'f'], [7, 'g'], [8, 'h'], [10, 'm'], [11, 'n'], [12, 'p']];
+  const data = [[1, 'z'], [2, 'b'], [3, 'c'], [3, 'c2'], [4, 'd'], [5, 'e'], [6, 'f'], [6, 'g'], [8, 'h'], [10, 'm'], [11, 'n'], [12, 'p']];
   for (let i = 0; i < ((n || n > data.length ? data.length : n) || data.length); i++) {
@@ -67,5 +67,4 @@ tree.store(data[i][0], data[i][1]);
     assert.deepEqual(tree.fetch(5), ['e']);
-    assert.deepEqual(tree.fetch(6), ['f']);
-    assert.deepEqual(tree.fetch(7), ['g']);
-    assert.equal(tree.fetch(300), false);
+    assert.deepEqual(tree.fetch(6), ['f', 'g']);
+    assert.deepEqual(tree.fetch(7), false);
     assert.deepEqual(tree.fetch(8), ['h']);
@@ -75,6 +74,22 @@ assert.deepEqual(tree.fetch(10), ['m']);
     assert.deepEqual(tree.fetch(12), ['p']);
-    assert.deepEqual(tree.fetch(12, { getLeaf: true }), { t: 'leaf', k: [10, 11, 12], v: [['m'], ['n'], ['p']], n: null });
-    assert.deepEqual(tree.fetch(12, { getLeaf: true, root: tree.fetch(11, { getLeaf: true }) }), { t: 'leaf', k: [10, 11, 12], v: [['m'], ['n'], ['p']], n: null });
   });
 
+  it('should fetch leaf', () => {
+    const tree = setup();
+    assert.deepEqual(tree.fetch(12, { getLeaf: true }), { t: 'leaf', k: [11, 12], v: [['n'], ['p']], n: null });
+    assert.deepEqual(tree.fetch(12, { getLeaf: true, root: tree.fetch(11, { getLeaf: true }) }), { t: 'leaf', k: [11, 12], v: [['n'], ['p']], n: null });
+  });
+
+  it('should fetch left or right', () => {
+    const tree = setup();
+    assert.deepEqual(tree.fetch(7, { notFound: 'right' }), ['h']);
+    assert.deepEqual(tree.fetch(7, { notFound: 'left' }), ['f', 'g']);
+    assert.deepEqual(tree.fetch(0, { notFound: 'left' }), false);
+    assert.deepEqual(tree.fetch(0, { notFound: 'right' }), ['z']);
+    assert.deepEqual(tree.fetch(-Infinity, { notFound: 'right' }), ['z']);
+    assert.deepEqual(tree.fetch(Infinity, { notFound: 'left' }), ['p']);
+    assert.deepEqual(tree.fetch(13, { notFound: 'left' }), ['p']);
+    assert.deepEqual(tree.fetch(13, { notFound: 'right' }), false);
+  });
+
   it('should range', () => {
@@ -121,2 +136,145 @@ let tree = new BPlusTree({ order: 4, debug: true });
 
+  it('should generate', () => {
+    const tree = setup();
+    let generator;
+    // limit is respected
+    generator = tree.values({ key: 2, targetValue: 'n', limit: 4 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: true });
+
+    // limit is respected
+    generator = tree.values({ key: 1, limit: 1 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: true });
+
+    // limit is respected
+    generator = tree.values({ key: 1, limit: 2 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: true });
+
+    // limit is respected
+    generator = tree.values({ key: 1, limit: 3 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c'], done: true });
+
+    // limit is respected although targetValue isn't found
+    generator = tree.values({ key: 2, targetValue: 'n', limit: 4 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: true });
+
+    // targetValue is respected before limit is reached
+    generator = tree.values({ key: 2, targetValue: 'n', limit: 10 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: false });
+    assert.deepEqual(generator.next(), { value: ['d'], done: false });
+    assert.deepEqual(generator.next(), { value: ['e'], done: false });
+    assert.deepEqual(generator.next(), { value: ['f', 'g'], done: false });
+    assert.deepEqual(generator.next(), { value: ['h'], done: false });
+    assert.deepEqual(generator.next(), { value: ['m'], done: true });
+
+    // key doesn't exist: not there
+    // user might want to use `keyNotFound`
+    generator = tree.values({ key: 7, targetValue: 'n', limit: 10 });
+    assert.deepEqual(generator.next(), { value: false, done: true });
+
+    // limit is bigger than the number of remaining values
+    generator = tree.values({ key: 2, targetValue: 'n', limit: 250 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: false });
+    assert.deepEqual(generator.next(), { value: ['d'], done: false });
+    assert.deepEqual(generator.next(), { value: ['e'], done: false });
+    assert.deepEqual(generator.next(), { value: ['f', 'g'], done: false });
+    assert.deepEqual(generator.next(), { value: ['h'], done: false });
+    assert.deepEqual(generator.next(), { value: ['m'], done: false });
+    assert.deepEqual(generator.next(), { value: ['n'], done: false });
+    assert.deepEqual(generator.next(), { value: ['p'], done: true });
+
+    // targetValue not found, generate until the end
+    generator = tree.values({ key: 2, targetValue: 'z' });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: false });
+    assert.deepEqual(generator.next(), { value: ['d'], done: false });
+    assert.deepEqual(generator.next(), { value: ['e'], done: false });
+    assert.deepEqual(generator.next(), { value: ['f', 'g'], done: false });
+    assert.deepEqual(generator.next(), { value: ['h'], done: false });
+    assert.deepEqual(generator.next(), { value: ['m'], done: false });
+    assert.deepEqual(generator.next(), { value: ['n'], done: false });
+    assert.deepEqual(generator.next(), { value: ['p'], done: true });
+
+    // targetValue not found, generate until the end
+    generator = tree.values({ key: 8, targetValue: 'z' });
+    assert.deepEqual(generator.next(), { value: ['h'], done: false });
+    assert.deepEqual(generator.next(), { value: ['m'], done: false });
+    assert.deepEqual(generator.next(), { value: ['n'], done: false });
+    assert.deepEqual(generator.next(), { value: ['p'], done: true });
+
+    // targetValue not found, generate until limit
+    generator = tree.values({ key: 2, targetValue: 'z', limit: 10 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: false });
+    assert.deepEqual(generator.next(), { value: ['d'], done: false });
+    assert.deepEqual(generator.next(), { value: ['e'], done: false });
+    assert.deepEqual(generator.next(), { value: ['f', 'g'], done: false });
+    assert.deepEqual(generator.next(), { value: ['h'], done: false });
+    assert.deepEqual(generator.next(), { value: ['m'], done: true });
+
+    // no targetValue
+    generator = tree.values({ key: 1, limit: 10 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: false });
+    assert.deepEqual(generator.next(), { value: ['d'], done: false });
+    assert.deepEqual(generator.next(), { value: ['e'], done: false });
+    assert.deepEqual(generator.next(), { value: ['f', 'g'], done: false });
+    assert.deepEqual(generator.next(), { value: ['h'], done: false });
+    assert.deepEqual(generator.next(), { value: ['m'], done: true });
+
+    // no limit
+    generator = tree.values({ key: 2, targetValue: 'n' });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: false });
+    assert.deepEqual(generator.next(), { value: ['d'], done: false });
+    assert.deepEqual(generator.next(), { value: ['e'], done: false });
+    assert.deepEqual(generator.next(), { value: ['f', 'g'], done: false });
+    assert.deepEqual(generator.next(), { value: ['h'], done: false });
+    assert.deepEqual(generator.next(), { value: ['m'], done: false });
+    assert.deepEqual(generator.next(), { value: ['n'], done: false });
+    assert.deepEqual(generator.next(), { value: ['p'], done: true });
+
+    // no limit
+    generator = tree.values({ key: 2 });
+    assert.deepEqual(generator.next(), { value: ['z'], done: false });
+    assert.deepEqual(generator.next(), { value: ['b'], done: false });
+    assert.deepEqual(generator.next(), { value: ['c', 'c2'], done: false });
+    assert.deepEqual(generator.next(), { value: ['d'], done: false });
+    assert.deepEqual(generator.next(), { value: ['e'], done: false });
+    assert.deepEqual(generator.next(), { value: ['f', 'g'], done: false });
+    assert.deepEqual(generator.next(), { value: ['h'], done: false });
+    assert.deepEqual(generator.next(), { value: ['m'], done: false });
+    assert.deepEqual(generator.next(), { value: ['n'], done: false });
+    assert.deepEqual(generator.next(), { value: ['p'], done: true });
+
+    // no key, assume first key, limit respected
+    generator = tree.values({ targetValue: 'n', limit: 5 });
+    assert.deepEqual(generator.next(), { value: ['n'], done: false });
+    assert.deepEqual(generator.next(), { value: ['p'], done: true });
+
+    // no key, assume first key, targetValue
+    generator = tree.values({ targetValue: 'd', limit: 10 });
+    assert.deepEqual(generator.next(), { value: ['n'], done: false });
+    assert.deepEqual(generator.next(), { value: ['p'], done: true });
+
+    // nothing, generate everything
+    generator = tree.values();
+    assert.deepEqual(generator.next(), { value: ['n'], done: false });
+    assert.deepEqual(generator.next(), { value: ['p'], done: true });
+  });
+
   it('should check', () => {
@@ -135,4 +293,4 @@ const tree = setup();
     const tree = setup();
-    assert.deepEqual(tree.repr(), { '1': ['z'], '2': ['b'], '3': ['c', 'c2'], '4': ['d'], '5': ['e'], '6': ['f'], '7': ['g'], '8': ['h'], '10': ['m'], '11': ['n'], '12': ['p'] });
-    assert.deepEqual(tree.repr({ getKeys: true }), ['1', '2', '3', '4', '5', '6', '7', '8', '10', '11', '12']);
+    assert.deepEqual(tree.repr(), { '1': ['z'], '2': ['b'], '3': ['c', 'c2'], '4': ['d'], '5': ['e'], '6': ['f', 'g'], '8': ['h'], '10': ['m'], '11': ['n'], '12': ['p'] });
+    assert.deepEqual(tree.repr({ getKeys: true }), ['1', '2', '3', '4', '5', '6', '8', '10', '11', '12']);
     assert.deepEqual(tree.repr({ getValues: true }), ['z', 'b', 'c', 'c2', 'd', 'e', 'f', 'g', 'h', 'm', 'n', 'p']);
@@ -164,3 +322,3 @@ assert.deepEqual(tree.repr({ getValues: true, descending: true }), ['z', 'b', 'c', 'c2', 'd', 'e', 'f', 'g', 'h', 'm', 'n', 'p'].reverse());
     tree.remove(3, 'c');
-    assert.deepEqual(tree.tree, { t: 'leaf', k: [], v: [], n: null });
+    assert.deepEqual(tree.tree, { t: 'leaf', k: [6], v: [['f', 'g']], n: null });
 
@@ -167,0 +325,0 @@ tree = new BPlusTree({ order: 4, debug: true });

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

1247629

increased by10.48%

Number of package files

41

increased by2.5%

Lines of code

2459

increased by16.98%

Number of lines in readme file

45

increased by18.42%

Worsened metrics

Dependency count

2

increased byInfinity%

Dev dependency count

13

increased by18.18%

Dependency changes

• + Addedbabel-polyfill@^6.16.0

• + Addedregenerator-runtime@^0.9.6

• + Addedbabel-polyfill@6.26.0(transitive)

• + Addedbabel-runtime@6.26.0(transitive)

• + Addedcore-js@2.6.12(transitive)

• + Addedregenerator-runtime@0.10.50.11.10.9.6(transitive)