binary-search-tree - npm Package Compare versions

Comparing version 0.2.2 to 0.2.3

lib/avltree.js

@@ -447,3 +447,3 @@ /**
  */
-['getNumberOfKeys', 'search', 'prettyPrint', 'executeOnEveryNode'].forEach(function (fn) {
+['getNumberOfKeys', 'search', 'betweenBounds', 'prettyPrint', 'executeOnEveryNode'].forEach(function (fn) {
   AVLTree.prototype[fn] = function () {
@@ -450,0 +450,0 @@ return this.tree[fn].apply(this.tree, arguments);

lib/bst.js

@@ -246,3 +246,3 @@ /**
 /**
- * Search for a key
+ * Search for all data corresponding to a key
  */
@@ -269,6 +269,98 @@ BinarySearchTree.prototype.search = function (key) {
 
-var ooo = { a: 2, b : 4};
 
+/**
+ * Return a function that tells whether a given key matches a lower bound
+ */
+BinarySearchTree.prototype.getLowerBoundMatcher = function (query) {
+  var self = this;
 
+  // No lower bound
+  if (!query.hasOwnProperty('$gt') && !query.hasOwnProperty('$gte')) {
+    return function () { return true; };
+  }
+
+  if (query.hasOwnProperty('$gt') && query.hasOwnProperty('$gte')) {
+    if (self.compareKeys(query.$gte, query.$gt) === 0) {
+      return function (key) { return self.compareKeys(key, query.$gt) > 0; };
+    }
+
+    if (self.compareKeys(query.$gte, query.$gt) > 0) {
+      return function (key) { return self.compareKeys(key, query.$gte) >= 0; };
+    } else {
+      return function (key) { return self.compareKeys(key, query.$gt) > 0; };
+    }
+  }
+
+  if (query.hasOwnProperty('$gt')) {
+    return function (key) { return self.compareKeys(key, query.$gt) > 0; };
+  } else {
+    return function (key) { return self.compareKeys(key, query.$gte) >= 0; };
+  }
+};
+
+
 /**
+ * Return a function that tells whether a given key matches an upper bound
+ */
+BinarySearchTree.prototype.getUpperBoundMatcher = function (query) {
+  var self = this;
+
+  // No lower bound
+  if (!query.hasOwnProperty('$lt') && !query.hasOwnProperty('$lte')) {
+    return function () { return true; };
+  }
+
+  if (query.hasOwnProperty('$lt') && query.hasOwnProperty('$lte')) {
+    if (self.compareKeys(query.$lte, query.$lt) === 0) {
+      return function (key) { return self.compareKeys(key, query.$lt) < 0; };
+    }
+
+    if (self.compareKeys(query.$lte, query.$lt) < 0) {
+      return function (key) { return self.compareKeys(key, query.$lte) <= 0; };
+    } else {
+      return function (key) { return self.compareKeys(key, query.$lt) < 0; };
+    }
+  }
+
+  if (query.hasOwnProperty('$lt')) {
+    return function (key) { return self.compareKeys(key, query.$lt) < 0; };
+  } else {
+    return function (key) { return self.compareKeys(key, query.$lte) <= 0; };
+  }
+};
+
+
+// Append all elements in toAppend to array
+function append (array, toAppend) {
+  var i;
+
+  for (i = 0; i < toAppend.length; i += 1) {
+    array.push(toAppend[i]);
+  }
+}
+
+
+/**
+ * Get all data for a key between bounds
+ * Return it in key order
+ * @param {Object} query Mongo-style query where keys are $lt, $lte, $gt or $gte (other keys are not considered)
+ * @param {Functions} lbm/ubm matching functions calculated at the first recursive step
+ */
+BinarySearchTree.prototype.betweenBounds = function (query, lbm, ubm) {
+  var res = [];
+
+  if (!this.hasOwnProperty('key')) { return []; }   // Empty tree
+
+  lbm = lbm || this.getLowerBoundMatcher(query);
+  ubm = ubm || this.getUpperBoundMatcher(query);
+
+  if (lbm(this.key) && this.left) { append(res, this.left.betweenBounds(query, lbm, ubm)); }
+  if (lbm(this.key) && ubm(this.key)) { append(res, this.data); }
+  if (ubm(this.key) && this.right) { append(res, this.right.betweenBounds(query, lbm, ubm)); }
+
+  return res;
+};
+
+
+/**
  * Delete the current node if it is a leaf
@@ -275,0 +367,0 @@ * Return true if it was deleted

package.json

 {
   "name": "binary-search-tree",
-  "version": "0.2.2",
+  "version": "0.2.3",
   "author": {
@@ -5,0 +5,0 @@ "name": "Louis Chatriot",

README.md

@@ -39,2 +39,7 @@ # Binary search trees for Node.js
 
+// Search between bounds with a MongoDB-like query
+// Data is returned in key order
+// Note the difference between $lt (less than) and $gte (less than OR EQUAL)
+bst.betweenBounds({ $lt: 18, $gte: 12});   // Equal to ['something else', 'some data for key 15']
+
 // Deleting all the data relating to a key
@@ -41,0 +46,0 @@ bst.delete(15);   // bst.search(15) will now give []

test/avltree.test.js

@@ -387,2 +387,40 @@ var should = require('chai').should()
 
+    it('Can search for data between two bounds', function () {
+      var avlt = new AVLTree();
+
+      [10, 5, 15, 3, 8, 13, 18].forEach(function (k) {
+        avlt.insert(k, 'data ' + k);
+      });
+
+      assert.deepEqual(avlt.betweenBounds({ $gte: 8, $lte: 15 }), ['data 8', 'data 10', 'data 13', 'data 15']);
+      assert.deepEqual(avlt.betweenBounds({ $gt: 8, $lt: 15 }), ['data 10', 'data 13']);
+    });
+
+    it('Bounded search can handle cases where query contains both $lt and $lte, or both $gt and $gte', function () {
+      var avlt = new AVLTree();
+
+      [10, 5, 15, 3, 8, 13, 18].forEach(function (k) {
+        avlt.insert(k, 'data ' + k);
+      });
+
+      assert.deepEqual(avlt.betweenBounds({ $gt:8, $gte: 8, $lte: 15 }), ['data 10', 'data 13', 'data 15']);
+      assert.deepEqual(avlt.betweenBounds({ $gt:5, $gte: 8, $lte: 15 }), ['data 8', 'data 10', 'data 13', 'data 15']);
+      assert.deepEqual(avlt.betweenBounds({ $gt:8, $gte: 5, $lte: 15 }), ['data 10', 'data 13', 'data 15']);
+
+      assert.deepEqual(avlt.betweenBounds({ $gte: 8, $lte: 15, $lt: 15 }), ['data 8', 'data 10', 'data 13']);
+      assert.deepEqual(avlt.betweenBounds({ $gte: 8, $lte: 18, $lt: 15 }), ['data 8', 'data 10', 'data 13']);
+      assert.deepEqual(avlt.betweenBounds({ $gte: 8, $lte: 15, $lt: 18 }), ['data 8', 'data 10', 'data 13', 'data 15']);
+    });
+
+    it('Bounded search can work when one or both boundaries are missing', function () {
+      var avlt = new AVLTree();
+
+      [10, 5, 15, 3, 8, 13, 18].forEach(function (k) {
+        avlt.insert(k, 'data ' + k);
+      });
+
+      assert.deepEqual(avlt.betweenBounds({ $gte: 11 }), ['data 13', 'data 15', 'data 18']);
+      assert.deepEqual(avlt.betweenBounds({ $lte: 9 }), ['data 3', 'data 5', 'data 8']);
+    });
+
   });   /// ==== End of 'Search' ==== //
@@ -389,0 +427,0 @@

test/bst.test.js

@@ -415,2 +415,40 @@ var should = require('chai').should()
 
+    it('Can search for data between two bounds', function () {
+      var bst = new BinarySearchTree();
+
+      [10, 5, 15, 3, 8, 13, 18].forEach(function (k) {
+        bst.insert(k, 'data ' + k);
+      });
+
+      assert.deepEqual(bst.betweenBounds({ $gte: 8, $lte: 15 }), ['data 8', 'data 10', 'data 13', 'data 15']);
+      assert.deepEqual(bst.betweenBounds({ $gt: 8, $lt: 15 }), ['data 10', 'data 13']);
+    });
+
+    it('Bounded search can handle cases where query contains both $lt and $lte, or both $gt and $gte', function () {
+      var bst = new BinarySearchTree();
+
+      [10, 5, 15, 3, 8, 13, 18].forEach(function (k) {
+        bst.insert(k, 'data ' + k);
+      });
+
+      assert.deepEqual(bst.betweenBounds({ $gt:8, $gte: 8, $lte: 15 }), ['data 10', 'data 13', 'data 15']);
+      assert.deepEqual(bst.betweenBounds({ $gt:5, $gte: 8, $lte: 15 }), ['data 8', 'data 10', 'data 13', 'data 15']);
+      assert.deepEqual(bst.betweenBounds({ $gt:8, $gte: 5, $lte: 15 }), ['data 10', 'data 13', 'data 15']);
+
+      assert.deepEqual(bst.betweenBounds({ $gte: 8, $lte: 15, $lt: 15 }), ['data 8', 'data 10', 'data 13']);
+      assert.deepEqual(bst.betweenBounds({ $gte: 8, $lte: 18, $lt: 15 }), ['data 8', 'data 10', 'data 13']);
+      assert.deepEqual(bst.betweenBounds({ $gte: 8, $lte: 15, $lt: 18 }), ['data 8', 'data 10', 'data 13', 'data 15']);
+    });
+
+    it('Bounded search can work when one or both boundaries are missing', function () {
+      var bst = new BinarySearchTree();
+
+      [10, 5, 15, 3, 8, 13, 18].forEach(function (k) {
+        bst.insert(k, 'data ' + k);
+      });
+
+      assert.deepEqual(bst.betweenBounds({ $gte: 11 }), ['data 13', 'data 15', 'data 18']);
+      assert.deepEqual(bst.betweenBounds({ $lte: 9 }), ['data 3', 'data 5', 'data 8']);
+    });
+
   });   /// ==== End of 'Search' ==== //
@@ -417,0 +455,0 @@

No alert changes

Improved metrics

Total package byte prevSize

100662

increased by7.16%

Lines of code

2537

increased by5.31%

Number of lines in readme file

124

increased by4.2%

No dependency changes