bintrees - npm Package Compare versions

Comparing version 0.0.9 to 0.0.10

dist/bintree.js

@@ -42,2 +42,38 @@ BinTree = (function(window) {
 
+// returns iterator to node if found, null otherwise
+TreeBase.prototype.findIter = function(data) {
+    var res = this._root;
+    var iter = this.iterator();
+
+    while(res !== null) {
+        var c = this._comparator(data, res.data);
+        if(c === 0) {
+            iter._cursor = res;
+            return iter;
+        }
+        else {
+            iter._ancestors.push(res);
+            res = res.get_child(c > 0);
+        }
+    }
+
+    return null;
+};
+
+// Returns an interator to the tree node immediately before (or at) the element
+TreeBase.prototype.lowerBound = function(data) {
+    return this._bound(data, this._comparator);
+};
+
+// Returns an interator to the tree node immediately after (or at) the element
+TreeBase.prototype.upperBound = function(data) {
+    var cmp = this._comparator;
+
+    function reverse_cmp(a, b) {
+        return cmp(b, a);
+    }
+
+    return this._bound(data, reverse_cmp);
+};
+
 // returns null if tree is empty
@@ -93,2 +129,31 @@ TreeBase.prototype.min = function() {
 
+// used for lowerBound and upperBound
+TreeBase.prototype._bound = function(data, cmp) {
+    var cur = this._root;
+    var iter = this.iterator();
+
+    while(cur !== null) {
+        var c = this._comparator(data, cur.data);
+        if(c === 0) {
+            iter._cursor = cur;
+            return iter;
+        }
+        iter._ancestors.push(cur);
+        cur = cur.get_child(c > 0);
+    }
+
+    for(var i=iter._ancestors.length - 1; i >= 0; --i) {
+        cur = iter._ancestors[i];
+        if(cmp(data, cur.data) > 0) {
+            iter._cursor = cur;
+            iter._ancestors.length = i;
+            return iter;
+        }
+    }
+
+    iter._ancestors.length = 0;
+    return iter;
+};
+
+
 function Iterator(tree) {
@@ -95,0 +160,0 @@ this._tree = tree;

dist/bintree.min.js

@@ -1,6 +0,8 @@
-BinTree=function(){var g=function(d){d=g.m[d];if(d.mod)return d.mod.exports;var b=d.mod={exports:{}};d(b,b.exports);return b.exports};g.m={};g.m["./treebase"]=function(d){function b(){}function c(a){this._tree=a;this._ancestors=[];this._cursor=null}b.prototype.clear=function(){this._root=null;this.size=0};b.prototype.find=function(a){for(var h=this._root;null!==h;){var b=this._comparator(a,h.data);if(0===b)return h.data;h=h.get_child(0<b)}return null};b.prototype.min=function(){var a=this._root;if(null===
-a)return null;for(;null!==a.left;)a=a.left;return a.data};b.prototype.max=function(){var a=this._root;if(null===a)return null;for(;null!==a.right;)a=a.right;return a.data};b.prototype.iterator=function(){return new c(this)};b.prototype.each=function(a){for(var h=this.iterator(),b;null!==(b=h.next());)a(b)};b.prototype.reach=function(a){for(var b=this.iterator(),j;null!==(j=b.prev());)a(j)};c.prototype.data=function(){return null!==this._cursor?this._cursor.data:null};c.prototype.next=function(){if(null===
-this._cursor){var a=this._tree._root;null!==a&&this._minNode(a)}else if(null===this._cursor.right){do if(a=this._cursor,this._ancestors.length)this._cursor=this._ancestors.pop();else{this._cursor=null;break}while(this._cursor.right===a)}else this._ancestors.push(this._cursor),this._minNode(this._cursor.right);return null!==this._cursor?this._cursor.data:null};c.prototype.prev=function(){if(null===this._cursor){var a=this._tree._root;null!==a&&this._maxNode(a)}else if(null===this._cursor.left){do if(a=
-this._cursor,this._ancestors.length)this._cursor=this._ancestors.pop();else{this._cursor=null;break}while(this._cursor.left===a)}else this._ancestors.push(this._cursor),this._maxNode(this._cursor.left);return null!==this._cursor?this._cursor.data:null};c.prototype._minNode=function(a){for(;null!==a.left;)this._ancestors.push(a),a=a.left;this._cursor=a};c.prototype._maxNode=function(a){for(;null!==a.right;)this._ancestors.push(a),a=a.right;this._cursor=a};d.exports=b};g.m.__main__=function(d){function b(a){this.data=
-a;this.right=this.left=null}function c(a){this._root=null;this._comparator=a;this.size=0}var a=g("./treebase");b.prototype.get_child=function(a){return a?this.right:this.left};b.prototype.set_child=function(a,b){a?this.right=b:this.left=b};c.prototype=new a;c.prototype.insert=function(a){if(null===this._root)return this._root=new b(a),this.size++,!0;for(var c=0,e=null,f=this._root;;){if(null===f)return f=new b(a),e.set_child(c,f),ret=!0,this.size++,!0;if(0===this._comparator(f.data,a))return!1;c=
-0>this._comparator(f.data,a);e=f;f=f.get_child(c)}};c.prototype.remove=function(a){if(null===this._root)return!1;var c=new b(void 0),e=c;e.right=this._root;for(var f=null,d=null,g=1;null!==e.get_child(g);){var f=e,e=e.get_child(g),k=this._comparator(a,e.data),g=0<k;0===k&&(d=e)}return null!==d?(d.data=e.data,f.set_child(f.right===e,e.get_child(null===e.left)),this._root=c.right,this.size--,!0):!1};d.exports=c};return g("__main__")}(window);
+BinTree=function(){var j=function(g){g=j.m[g];if(g.mod)return g.mod.exports;var c=g.mod={exports:{}};g(c,c.exports);return c.exports};j.m={};j.m["./treebase"]=function(g){function c(){}function f(a){this._tree=a;this._ancestors=[];this._cursor=null}c.prototype.clear=function(){this._root=null;this.size=0};c.prototype.find=function(a){for(var e=this._root;null!==e;){var b=this._comparator(a,e.data);if(0===b)return e.data;e=e.get_child(0<b)}return null};c.prototype.findIter=function(a){for(var e=this._root,
+b=this.iterator();null!==e;){var d=this._comparator(a,e.data);if(0===d)return b._cursor=e,b;b._ancestors.push(e);e=e.get_child(0<d)}return null};c.prototype.lowerBound=function(a){return this._bound(a,this._comparator)};c.prototype.upperBound=function(a){var e=this._comparator;return this._bound(a,function(a,d){return e(d,a)})};c.prototype.min=function(){var a=this._root;if(null===a)return null;for(;null!==a.left;)a=a.left;return a.data};c.prototype.max=function(){var a=this._root;if(null===a)return null;
+for(;null!==a.right;)a=a.right;return a.data};c.prototype.iterator=function(){return new f(this)};c.prototype.each=function(a){for(var e=this.iterator(),b;null!==(b=e.next());)a(b)};c.prototype.reach=function(a){for(var e=this.iterator(),b;null!==(b=e.prev());)a(b)};c.prototype._bound=function(a,e){for(var b=this._root,d=this.iterator();null!==b;){var c=this._comparator(a,b.data);if(0===c)return d._cursor=b,d;d._ancestors.push(b);b=b.get_child(0<c)}for(c=d._ancestors.length-1;0<=c;--c)if(b=d._ancestors[c],
+0<e(a,b.data))return d._cursor=b,d._ancestors.length=c,d;d._ancestors.length=0;return d};f.prototype.data=function(){return null!==this._cursor?this._cursor.data:null};f.prototype.next=function(){if(null===this._cursor){var a=this._tree._root;null!==a&&this._minNode(a)}else if(null===this._cursor.right){do if(a=this._cursor,this._ancestors.length)this._cursor=this._ancestors.pop();else{this._cursor=null;break}while(this._cursor.right===a)}else this._ancestors.push(this._cursor),this._minNode(this._cursor.right);
+return null!==this._cursor?this._cursor.data:null};f.prototype.prev=function(){if(null===this._cursor){var a=this._tree._root;null!==a&&this._maxNode(a)}else if(null===this._cursor.left){do if(a=this._cursor,this._ancestors.length)this._cursor=this._ancestors.pop();else{this._cursor=null;break}while(this._cursor.left===a)}else this._ancestors.push(this._cursor),this._maxNode(this._cursor.left);return null!==this._cursor?this._cursor.data:null};f.prototype._minNode=function(a){for(;null!==a.left;)this._ancestors.push(a),
+a=a.left;this._cursor=a};f.prototype._maxNode=function(a){for(;null!==a.right;)this._ancestors.push(a),a=a.right;this._cursor=a};g.exports=c};j.m.__main__=function(g){function c(a){this.data=a;this.right=this.left=null}function f(a){this._root=null;this._comparator=a;this.size=0}var a=j("./treebase");c.prototype.get_child=function(a){return a?this.right:this.left};c.prototype.set_child=function(a,b){a?this.right=b:this.left=b};f.prototype=new a;f.prototype.insert=function(a){if(null===this._root)return this._root=
+new c(a),this.size++,!0;for(var b=0,d=null,h=this._root;;){if(null===h)return h=new c(a),d.set_child(b,h),ret=!0,this.size++,!0;if(0===this._comparator(h.data,a))return!1;b=0>this._comparator(h.data,a);d=h;h=h.get_child(b)}};f.prototype.remove=function(a){if(null===this._root)return!1;var b=new c(void 0),d=b;d.right=this._root;for(var h=null,f=null,g=1;null!==d.get_child(g);){var h=d,d=d.get_child(g),j=this._comparator(a,d.data),g=0<j;0===j&&(f=d)}return null!==f?(f.data=d.data,h.set_child(h.right===
+d,d.get_child(null===d.left)),this._root=b.right,this.size--,!0):!1};g.exports=f};return j("__main__")}(window);

dist/rbtree.js

@@ -42,2 +42,38 @@ RBTree = (function(window) {
 
+// returns iterator to node if found, null otherwise
+TreeBase.prototype.findIter = function(data) {
+    var res = this._root;
+    var iter = this.iterator();
+
+    while(res !== null) {
+        var c = this._comparator(data, res.data);
+        if(c === 0) {
+            iter._cursor = res;
+            return iter;
+        }
+        else {
+            iter._ancestors.push(res);
+            res = res.get_child(c > 0);
+        }
+    }
+
+    return null;
+};
+
+// Returns an interator to the tree node immediately before (or at) the element
+TreeBase.prototype.lowerBound = function(data) {
+    return this._bound(data, this._comparator);
+};
+
+// Returns an interator to the tree node immediately after (or at) the element
+TreeBase.prototype.upperBound = function(data) {
+    var cmp = this._comparator;
+
+    function reverse_cmp(a, b) {
+        return cmp(b, a);
+    }
+
+    return this._bound(data, reverse_cmp);
+};
+
 // returns null if tree is empty
@@ -93,2 +129,31 @@ TreeBase.prototype.min = function() {
 
+// used for lowerBound and upperBound
+TreeBase.prototype._bound = function(data, cmp) {
+    var cur = this._root;
+    var iter = this.iterator();
+
+    while(cur !== null) {
+        var c = this._comparator(data, cur.data);
+        if(c === 0) {
+            iter._cursor = cur;
+            return iter;
+        }
+        iter._ancestors.push(cur);
+        cur = cur.get_child(c > 0);
+    }
+
+    for(var i=iter._ancestors.length - 1; i >= 0; --i) {
+        cur = iter._ancestors[i];
+        if(cmp(data, cur.data) > 0) {
+            iter._cursor = cur;
+            iter._ancestors.length = i;
+            return iter;
+        }
+    }
+
+    iter._ancestors.length = 0;
+    return iter;
+};
+
+
 function Iterator(tree) {
@@ -95,0 +160,0 @@ this._tree = tree;

dist/rbtree.min.js

@@ -1,8 +0,10 @@
-RBTree=function(){var n=function(g){g=n.m[g];if(g.mod)return g.mod.exports;var b=g.mod={exports:{}};g(b,b.exports);return b.exports};n.m={};n.m["./treebase"]=function(g){function b(){}function c(a){this._tree=a;this._ancestors=[];this._cursor=null}b.prototype.clear=function(){this._root=null;this.size=0};b.prototype.find=function(a){for(var b=this._root;null!==b;){var c=this._comparator(a,b.data);if(0===c)return b.data;b=b.get_child(0<c)}return null};b.prototype.min=function(){var a=this._root;if(null===
-a)return null;for(;null!==a.left;)a=a.left;return a.data};b.prototype.max=function(){var a=this._root;if(null===a)return null;for(;null!==a.right;)a=a.right;return a.data};b.prototype.iterator=function(){return new c(this)};b.prototype.each=function(a){for(var b=this.iterator(),c;null!==(c=b.next());)a(c)};b.prototype.reach=function(a){for(var b=this.iterator(),c;null!==(c=b.prev());)a(c)};c.prototype.data=function(){return null!==this._cursor?this._cursor.data:null};c.prototype.next=function(){if(null===
-this._cursor){var a=this._tree._root;null!==a&&this._minNode(a)}else if(null===this._cursor.right){do if(a=this._cursor,this._ancestors.length)this._cursor=this._ancestors.pop();else{this._cursor=null;break}while(this._cursor.right===a)}else this._ancestors.push(this._cursor),this._minNode(this._cursor.right);return null!==this._cursor?this._cursor.data:null};c.prototype.prev=function(){if(null===this._cursor){var a=this._tree._root;null!==a&&this._maxNode(a)}else if(null===this._cursor.left){do if(a=
-this._cursor,this._ancestors.length)this._cursor=this._ancestors.pop();else{this._cursor=null;break}while(this._cursor.left===a)}else this._ancestors.push(this._cursor),this._maxNode(this._cursor.left);return null!==this._cursor?this._cursor.data:null};c.prototype._minNode=function(a){for(;null!==a.left;)this._ancestors.push(a),a=a.left;this._cursor=a};c.prototype._maxNode=function(a){for(;null!==a.right;)this._ancestors.push(a),a=a.right;this._cursor=a};g.exports=b};n.m.__main__=function(g){function b(a){this.data=
-a;this.right=this.left=null;this.red=!0}function c(a){this._root=null;this._comparator=a;this.size=0}function a(a){return null!==a&&a.red}function p(a,b){var d=a.get_child(!b);a.set_child(!b,d.get_child(b));d.set_child(b,a);a.red=!0;d.red=!1;return d}function q(a,b){a.set_child(!b,p(a.get_child(!b),!b));return p(a,b)}var r=n("./treebase");b.prototype.get_child=function(a){return a?this.right:this.left};b.prototype.set_child=function(a,b){a?this.right=b:this.left=b};c.prototype=new r;c.prototype.insert=
-function(c){var g=!1;if(null===this._root)this._root=new b(c),g=!0,this.size++;else{var d=new b(void 0),h=0,k=0,l=null,j=d,f=null,e=this._root;for(j.right=this._root;;){null===e?(e=new b(c),f.set_child(h,e),g=!0,this.size++):a(e.left)&&a(e.right)&&(e.red=!0,e.left.red=!1,e.right.red=!1);if(a(e)&&a(f)){var m=j.right===l;e===f.get_child(k)?j.set_child(m,p(l,!k)):j.set_child(m,q(l,!k))}m=this._comparator(e.data,c);if(0===m)break;k=h;h=0>m;null!==l&&(j=l);l=f;f=e;e=e.get_child(h)}this._root=d.right}this._root.red=
-!1;return g};c.prototype.remove=function(c){if(null===this._root)return!1;var g=new b(void 0),d=g;d.right=this._root;for(var h=null,k=null,l=null,j=1;null!==d.get_child(j);){var f=j,k=h,h=d,d=d.get_child(j),e=this._comparator(c,d.data),j=0<e;0===e&&(l=d);if(!a(d)&&!a(d.get_child(j)))if(a(d.get_child(!j)))k=p(d,j),h.set_child(f,k),h=k;else if(!a(d.get_child(!j))&&(e=h.get_child(!f),null!==e))if(!a(e.get_child(!f))&&!a(e.get_child(f)))h.red=!1,e.red=!0,d.red=!0;else{var m=k.right===h;a(e.get_child(f))?
-k.set_child(m,q(h,f)):a(e.get_child(!f))&&k.set_child(m,p(h,f));f=k.get_child(m);f.red=!0;d.red=!0;f.left.red=!1;f.right.red=!1}}null!==l&&(l.data=d.data,h.set_child(h.right===d,d.get_child(null===d.left)),this.size--);this._root=g.right;null!==this._root&&(this._root.red=!1);return null!==l};g.exports=c};return n("__main__")}(window);
+RBTree=function(){var p=function(h){h=p.m[h];if(h.mod)return h.mod.exports;var b=h.mod={exports:{}};h(b,b.exports);return b.exports};p.m={};p.m["./treebase"]=function(h){function b(){}function e(a){this._tree=a;this._ancestors=[];this._cursor=null}b.prototype.clear=function(){this._root=null;this.size=0};b.prototype.find=function(a){for(var j=this._root;null!==j;){var d=this._comparator(a,j.data);if(0===d)return j.data;j=j.get_child(0<d)}return null};b.prototype.findIter=function(a){for(var j=this._root,
+d=this.iterator();null!==j;){var b=this._comparator(a,j.data);if(0===b)return d._cursor=j,d;d._ancestors.push(j);j=j.get_child(0<b)}return null};b.prototype.lowerBound=function(a){return this._bound(a,this._comparator)};b.prototype.upperBound=function(a){var b=this._comparator;return this._bound(a,function(a,g){return b(g,a)})};b.prototype.min=function(){var a=this._root;if(null===a)return null;for(;null!==a.left;)a=a.left;return a.data};b.prototype.max=function(){var a=this._root;if(null===a)return null;
+for(;null!==a.right;)a=a.right;return a.data};b.prototype.iterator=function(){return new e(this)};b.prototype.each=function(a){for(var b=this.iterator(),d;null!==(d=b.next());)a(d)};b.prototype.reach=function(a){for(var b=this.iterator(),d;null!==(d=b.prev());)a(d)};b.prototype._bound=function(a,b){for(var d=this._root,g=this.iterator();null!==d;){var q=this._comparator(a,d.data);if(0===q)return g._cursor=d,g;g._ancestors.push(d);d=d.get_child(0<q)}for(q=g._ancestors.length-1;0<=q;--q)if(d=g._ancestors[q],
+0<b(a,d.data))return g._cursor=d,g._ancestors.length=q,g;g._ancestors.length=0;return g};e.prototype.data=function(){return null!==this._cursor?this._cursor.data:null};e.prototype.next=function(){if(null===this._cursor){var a=this._tree._root;null!==a&&this._minNode(a)}else if(null===this._cursor.right){do if(a=this._cursor,this._ancestors.length)this._cursor=this._ancestors.pop();else{this._cursor=null;break}while(this._cursor.right===a)}else this._ancestors.push(this._cursor),this._minNode(this._cursor.right);
+return null!==this._cursor?this._cursor.data:null};e.prototype.prev=function(){if(null===this._cursor){var a=this._tree._root;null!==a&&this._maxNode(a)}else if(null===this._cursor.left){do if(a=this._cursor,this._ancestors.length)this._cursor=this._ancestors.pop();else{this._cursor=null;break}while(this._cursor.left===a)}else this._ancestors.push(this._cursor),this._maxNode(this._cursor.left);return null!==this._cursor?this._cursor.data:null};e.prototype._minNode=function(a){for(;null!==a.left;)this._ancestors.push(a),
+a=a.left;this._cursor=a};e.prototype._maxNode=function(a){for(;null!==a.right;)this._ancestors.push(a),a=a.right;this._cursor=a};h.exports=b};p.m.__main__=function(h){function b(a){this.data=a;this.right=this.left=null;this.red=!0}function e(a){this._root=null;this._comparator=a;this.size=0}function a(a){return null!==a&&a.red}function j(a,b){var c=a.get_child(!b);a.set_child(!b,c.get_child(b));c.set_child(b,a);a.red=!0;c.red=!1;return c}function d(a,b){a.set_child(!b,j(a.get_child(!b),!b));return j(a,
+b)}var g=p("./treebase");b.prototype.get_child=function(a){return a?this.right:this.left};b.prototype.set_child=function(a,b){a?this.right=b:this.left=b};e.prototype=new g;e.prototype.insert=function(g){var e=!1;if(null===this._root)this._root=new b(g),e=!0,this.size++;else{var c=new b(void 0),l=0,r=0,n=null,m=c,k=null,f=this._root;for(m.right=this._root;;){null===f?(f=new b(g),k.set_child(l,f),e=!0,this.size++):a(f.left)&&a(f.right)&&(f.red=!0,f.left.red=!1,f.right.red=!1);if(a(f)&&a(k)){var h=m.right===
+n;f===k.get_child(r)?m.set_child(h,j(n,!r)):m.set_child(h,d(n,!r))}h=this._comparator(f.data,g);if(0===h)break;r=l;l=0>h;null!==n&&(m=n);n=k;k=f;f=f.get_child(l)}this._root=c.right}this._root.red=!1;return e};e.prototype.remove=function(g){if(null===this._root)return!1;var h=new b(void 0),c=h;c.right=this._root;for(var l=null,e=null,n=null,m=1;null!==c.get_child(m);){var k=m,e=l,l=c,c=c.get_child(m),f=this._comparator(g,c.data),m=0<f;0===f&&(n=c);if(!a(c)&&!a(c.get_child(m)))if(a(c.get_child(!m)))e=
+j(c,m),l.set_child(k,e),l=e;else if(!a(c.get_child(!m))&&(f=l.get_child(!k),null!==f))if(!a(f.get_child(!k))&&!a(f.get_child(k)))l.red=!1,f.red=!0,c.red=!0;else{var p=e.right===l;a(f.get_child(k))?e.set_child(p,d(l,k)):a(f.get_child(!k))&&e.set_child(p,j(l,k));k=e.get_child(p);k.red=!0;c.red=!0;k.left.red=!1;k.right.red=!1}}null!==n&&(n.data=c.data,l.set_child(l.right===c,c.get_child(null===c.left)),this.size--);this._root=h.right;null!==this._root&&(this._root.red=!1);return null!==n};h.exports=
+e};return p("__main__")}(window);

lib/treebase.js

@@ -27,2 +27,38 @@
 
+// returns iterator to node if found, null otherwise
+TreeBase.prototype.findIter = function(data) {
+    var res = this._root;
+    var iter = this.iterator();
+
+    while(res !== null) {
+        var c = this._comparator(data, res.data);
+        if(c === 0) {
+            iter._cursor = res;
+            return iter;
+        }
+        else {
+            iter._ancestors.push(res);
+            res = res.get_child(c > 0);
+        }
+    }
+
+    return null;
+};
+
+// Returns an interator to the tree node immediately before (or at) the element
+TreeBase.prototype.lowerBound = function(data) {
+    return this._bound(data, this._comparator);
+};
+
+// Returns an interator to the tree node immediately after (or at) the element
+TreeBase.prototype.upperBound = function(data) {
+    var cmp = this._comparator;
+
+    function reverse_cmp(a, b) {
+        return cmp(b, a);
+    }
+
+    return this._bound(data, reverse_cmp);
+};
+
 // returns null if tree is empty
@@ -78,2 +114,31 @@ TreeBase.prototype.min = function() {
 
+// used for lowerBound and upperBound
+TreeBase.prototype._bound = function(data, cmp) {
+    var cur = this._root;
+    var iter = this.iterator();
+
+    while(cur !== null) {
+        var c = this._comparator(data, cur.data);
+        if(c === 0) {
+            iter._cursor = cur;
+            return iter;
+        }
+        iter._ancestors.push(cur);
+        cur = cur.get_child(c > 0);
+    }
+
+    for(var i=iter._ancestors.length - 1; i >= 0; --i) {
+        cur = iter._ancestors[i];
+        if(cmp(data, cur.data) > 0) {
+            iter._cursor = cur;
+            iter._ancestors.length = i;
+            return iter;
+        }
+    }
+
+    iter._ancestors.length = 0;
+    return iter;
+};
+
+
 function Iterator(tree) {
@@ -80,0 +145,0 @@ this._tree = tree;

package.json

@@ -5,3 +5,3 @@ {
   "description": "Binary Search Trees",
-  "version": "0.0.9",
+  "version": "0.0.10",
   "keywords": [
@@ -8,0 +8,0 @@ "binary tree",

README.md

@@ -59,14 +59,41 @@ Binary Trees [![Build Status](https://secure.travis-ci.org/vadimg/js_bintrees.png?branch=master)](http://travis-ci.org/vadimg/js_bintrees)
 
-* insert(item)
-* remove(item)
-* clear()
-* find(item)
-* min()
-* max()
-* each(f)
-* reach(f)
-* iterator()
+### insert(item)
+> Inserts the item into the tree. Returns true if inserted, false if duplicate.
 
-See the comments inside the lib directory for more info.
+### remove(item)
+> Removes the item from the tree. Returns true if removed, false if not found.
 
+### size
+> Number of nodes in the tree.
+
+### clear()
+> Removes all nodes from the tree.
+
+### find(item)
+> Returns node data if found, null otherwise.
+
+### findIter(item)
+> Returns an iterator to the node if found, null otherwise.
+
+### lowerBound(item)
+> Returns an interator to the tree node immediately before (or at) the element. Returns null-iterator if tree is empty.
+
+### upperBound(item)
+> Returns an interator to the tree node immediately after (or at) the element. Returns null-iterator if tree is empty.
+
+### min()
+> Returns the min node data in the tree, or null if the tree is empty.
+
+### max()
+> Returns the max node data in the tree, or null if the tree is empty.
+
+### each(f)
+> Calls f on each node's data, in order.
+
+### reach(f)
+> Calls f on each node's data, in reverse order.
+
+### iterator()
+> Returns a null-iterator. See __Iterators__ section below.
+
 Iterators
@@ -95,1 +122,3 @@ ------------
 If you are iterating forward through the tree, you can always call prev() to go back, and vice versa.
+
+__NOTE:__ iterators become invalid when you add or remove elements from the tree.

test/test_api.js

@@ -105,3 +105,3 @@ var _ = require('underscore');
         var it = tree.iterator();
-        for(var i =0; i < after; i++) {
+        for(var i = 0; i < after; i++) {
             items.push(it.next());
@@ -137,2 +137,80 @@ }
 
+function lower_bound(assert, tree_class) {
+    var inserts = loader.get_inserts(loader.load(SAMPLE_FILE));
+    var tree = loader.build_tree(tree_class, inserts);
+
+    inserts.sort(function(a,b) { return a - b; });
+
+    for(var i=1; i<inserts.length-1; ++i) {
+        var item = inserts[i];
+
+        var iter = tree.lowerBound(item);
+        assert.equal(iter.data(), item);
+        assert.equal(iter.prev(), inserts[i-1]);
+        iter.next();
+        assert.equal(iter.next(), inserts[i+1]);
+
+        var prev = tree.lowerBound(item - 0.1);
+        assert.equal(prev.data(), inserts[i-1]);
+
+        var next = tree.lowerBound(item + 0.1);
+        assert.equal(next.data(), inserts[i]);
+    }
+}
+
+function upper_bound(assert, tree_class) {
+    var inserts = loader.get_inserts(loader.load(SAMPLE_FILE));
+    var tree = loader.build_tree(tree_class, inserts);
+
+    inserts.sort(function(a,b) { return a - b; });
+
+    for(var i=1; i<inserts.length-1; ++i) {
+        var item = inserts[i];
+
+        var iter = tree.upperBound(item);
+        assert.equal(iter.data(), item);
+        assert.equal(iter.prev(), inserts[i-1]);
+        iter.next();
+        assert.equal(iter.next(), inserts[i+1]);
+
+        var prev = tree.upperBound(item - 0.1);
+        assert.equal(prev.data(), inserts[i]);
+
+        var next = tree.upperBound(item + 0.1);
+        assert.equal(next.data(), inserts[i+1]);
+    }
+}
+
+function find(assert, tree_class) {
+    var inserts = loader.get_inserts(loader.load(SAMPLE_FILE));
+    var tree = loader.build_tree(tree_class, inserts);
+
+    for(var i=1; i<inserts.length-1; ++i) {
+        var item = inserts[i];
+
+        assert.equal(tree.find(item), item);
+        assert.equal(tree.find(item + 0.1), null);
+    }
+}
+
+function find_iter(assert, tree_class) {
+    var inserts = loader.get_inserts(loader.load(SAMPLE_FILE));
+    var tree = loader.build_tree(tree_class, inserts);
+
+    inserts.sort(function(a,b) { return a - b; });
+
+    for(var i=1; i<inserts.length-1; ++i) {
+        var item = inserts[i];
+
+        var iter = tree.findIter(item);
+        assert.equal(iter.data(), item);
+        assert.equal(iter.prev(), inserts[i-1]);
+        iter.next();
+        assert.equal(iter.next(), inserts[i+1]);
+
+        assert.equal(tree.findIter(item + 0.1), null);
+    }
+}
+
+
 var TESTS = {
@@ -146,3 +224,7 @@ clear: clear,
     switch_it: switch_it,
-    empty_it: empty_it
+    empty_it: empty_it,
+    lower_bound: lower_bound,
+    upper_bound: upper_bound,
+    find: find,
+    find_iter: find_iter
 };
@@ -149,0 +231,0 @@

New alerts

Non-existent author

Supply chain risk

The package was published by an npm account that no longer exists.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

2347562

increased by0.41%

Lines of code

1665

increased by15.79%

Number of lines in readme file

123

increased by30.85%

Worsened metrics

Number of high supply chain risk alerts

1

increased byInfinity%

No dependency changes