sorted-btree - npm Package Compare versions

Comparing version 1.0.2 to 1.0.3

b+tree.d.ts

@@ -109,2 +109,3 @@ export declare type EditRangeResult<V, R = number> = {
     _compare: (a: K, b: K) => number;
+    static defaultComparator(a: any, b: any): number;
     /**
@@ -111,0 +112,0 @@ * Initializes an empty B+ tree.

b+tree.js

@@ -120,16 +120,18 @@ // B+ tree by David Piepgrass. License: MIT
             this._maxNodeSize = maxNodeSize >= 4 ? Math.min(maxNodeSize, 256) : 32;
-            this._compare = compare || function cmp(a, b) {
-                var c = a - b;
-                if (c === c)
-                    return c; // a & b are number
-                // General case (c is NaN): string / arrays / Date / incomparable things
-                if (a)
-                    a = a.valueOf();
-                if (b)
-                    b = b.valueOf();
-                return a < b ? -1 : a > b ? 1 : a == b ? 0 : c;
-            };
+            this._compare = compare || BTree.defaultComparator;
             if (entries)
                 this.setRange(entries);
         }
+        BTree.defaultComparator = function (a, b) {
+            var c = a - b;
+            if (c === c)
+                return c; // a & b are number
+            // General case (c is NaN): string / arrays / Date / incomparable things
+            if (a)
+                a = a.valueOf();
+            if (b)
+                b = b.valueOf();
+            return a < b ? -1 : a > b ? 1 : a == b ? 0 : c;
+        };
+        ;
         Object.defineProperty(BTree.prototype, "size", {
@@ -136,0 +138,0 @@ // ES6 Map<K,V> methods ///////////////////////////////////////////////////

b+tree.min.js

@@ -1,1 +0,1 @@
-var __extends=this&&this.__extends||function(){var e=Object.setPrototypeOf||{__proto__:[]}instanceof Array&&function(e,t){e.__proto__=t}||function(e,t){for(var r in t)t.hasOwnProperty(r)&&(e[r]=t[r])};return function(t,r){function i(){this.constructor=t}e(t,r),t.prototype=null===r?Object.create(r):(i.prototype=r.prototype,new i)}}(),__read=this&&this.__read||function(e,t){var r="function"==typeof Symbol&&e[Symbol.iterator];if(!r)return e;var i,n,o=r.call(e),s=[];try{for(;(void 0===t||t-- >0)&&!(i=o.next()).done;)s.push(i.value)}catch(e){n={error:e}}finally{try{i&&!i.done&&(r=o.return)&&r.call(o)}finally{if(n)throw n.error}}return s},__spread=this&&this.__spread||function(){for(var e=[],t=0;t<arguments.length;t++)e=e.concat(__read(arguments[t]));return e};!function(e){if("object"==typeof module&&"object"==typeof module.exports){var t=e(require,exports);void 0!==t&&(module.exports=t)}else"function"==typeof define&&define.amd&&define(["require","exports"],e)}(function(e,t){"use strict";function r(e){void 0===e&&(e=function(){return{done:!0,value:void 0}});var t={next:e};return Symbol&&Symbol.iterator&&(t[Symbol.iterator]=function(){return this}),t}function i(e){for(var t=[],r=1;r<arguments.length;r++)t[r-1]=arguments[r];if(!e)throw t.unshift("B+ tree "),new Error(t.join(" "))}Object.defineProperty(t,"__esModule",{value:!0});var n=function(){function e(e,t,r){this._root=l,this._size=0,this._maxNodeSize=r>=4?Math.min(r,256):32,this._compare=t||function(e,t){var r=e-t;return r===r?r:(e&&(e=e.valueOf()),t&&(t=t.valueOf()),e<t?-1:e>t?1:e==t?0:r)},e&&this.setRange(e)}return Object.defineProperty(e.prototype,"size",{get:function(){return this._size},enumerable:!0,configurable:!0}),Object.defineProperty(e.prototype,"length",{get:function(){return this._size},enumerable:!0,configurable:!0}),e.prototype.clear=function(){this._root=l,this._size=0},e.prototype.forEach=function(e,t){var r=this;return void 0!==t&&(e=e.bind(t)),this.forEachPair(function(t,i){return e(i,t,r)})},e.prototype.forEachPair=function(e,t){var r=this.minKey(),i=this.maxKey();return this.forRange(r,i,!0,e,t)},e.prototype.get=function(e,t){return this._root.get(e,t,this)},e.prototype.set=function(e,t,r){this._root.isShared&&(this._root=this._root.clone());var i=this._root.set(e,t,r,this);return!0===i||!1===i?i:(this._root=new s([this._root,i]),!0)},e.prototype.has=function(e){return 0!==this.forRange(e,e,!0,void 0)},e.prototype.delete=function(e){return 0!==this.editRange(e,e,!0,u)},e.prototype.entries=function(e,t){var i=this.findPath(e);if(void 0===i)return r();var n=i.nodequeue,o=i.nodeindex,s=i.leaf,h=void 0!==t?1:0,a=void 0===e?-1:s.indexOf(e,0,this._compare)-1;return r(function(){e:for(;;)switch(h){case 0:if(++a<s.keys.length)return{done:!1,value:[s.keys[a],s.values[a]]};h=2;continue;case 1:if(++a<s.keys.length)return t[0]=s.keys[a],t[1]=s.values[a],{done:!1,value:t};h=2;case 2:for(var e=-1;;){if(++e>=n.length){h=3;continue e}if(++o[e]<n[e].length)break}for(;e>0;e--)n[e-1]=n[e][o[e]].children,o[e-1]=0;s=n[0][o[0]],a=-1,h=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},e.prototype.entriesReversed=function(e,t,n){if(void 0===(e=e||this.maxKey()))return r();var o=this.findPath(e)||this.findPath(this.maxKey()),s=o.nodequeue,h=o.nodeindex,a=o.leaf;i(!s[0]||a===s[0][h[0]],"wat!");var u=a.indexOf(e,0,this._compare);n||this._compare(a.keys[u],e)>0||u++;var f=void 0!==t?1:0;return r(function(){e:for(;;)switch(f){case 0:if(--u>=0)return{done:!1,value:[a.keys[u],a.values[u]]};f=2;continue;case 1:if(--u>=0)return t[0]=a.keys[u],t[1]=a.values[u],{done:!1,value:t};f=2;case 2:for(var e=-1;;){if(++e>=s.length){f=3;continue e}if(--h[e]>=0)break}for(;e>0;e--)s[e-1]=s[e][h[e]].children,h[e-1]=s[e-1].length-1;a=s[0][h[0]],u=a.keys.length,f=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},e.prototype.findPath=function(e){var t,r,i=this._root;if(i.isLeaf)t=c,r=c;else{t=[],r=[];for(var n=0;!i.isLeaf;n++){if(t[n]=i.children,r[n]=void 0===e?0:i.indexOf(e,0,this._compare),r[n]>=t[n].length)return;i=t[n][r[n]]}t.reverse(),r.reverse()}return{nodequeue:t,nodeindex:r,leaf:i}},e.prototype.keys=function(e){var t=this.entries(e,p);return r(function(){var e=t.next();return e.value&&(e.value=e.value[0]),e})},e.prototype.values=function(e){var t=this.entries(e,p);return r(function(){var e=t.next();return e.value&&(e.value=e.value[1]),e})},Object.defineProperty(e.prototype,"maxNodeSize",{get:function(){return this._maxNodeSize},enumerable:!0,configurable:!0}),e.prototype.minKey=function(){return this._root.minKey()},e.prototype.maxKey=function(){return this._root.maxKey()},e.prototype.clone=function(){this._root.isShared=!0;var t=new e(void 0,this._compare,this._maxNodeSize);return t._root=this._root,t._size=this._size,t},e.prototype.toArray=function(e){void 0===e&&(e=2147483647);var t=this.minKey(),r=this.maxKey();return void 0!==t?this.getRange(t,r,!0,e):[]},e.prototype.keysArray=function(){var e=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(t,r){e.push(t)}),e},e.prototype.valuesArray=function(){var e=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(t,r){e.push(r)}),e},e.prototype.toString=function(){return this.toArray().toString()},e.prototype.setIfNotPresent=function(e,t){return this.set(e,t,!1)},e.prototype.changeIfPresent=function(e,t){return 0!==this.editRange(e,e,!0,function(e,r){return{value:t}})},e.prototype.getRange=function(e,t,r,i){void 0===i&&(i=67108863);var n=[];return this._root.forRange(e,t,r,!1,this,0,function(e,t){return n.push([e,t]),n.length>i?f:void 0}),n},e.prototype.setRange=function(e){for(var t=0;t<e.length;t++)this.set(e[t][0],e[t][1]);return this},e.prototype.forRange=function(e,t,r,i,n){var o=this._root.forRange(e,t,r,!1,this,n||0,i);return"number"==typeof o?o:o.break},e.prototype.editRange=function(e,t,r,i,n){var o=this._root;o.isShared&&(this._root=o=o.clone());try{var s=o.forRange(e,t,r,!0,this,n||0,i);return"number"==typeof s?s:s.break}finally{for(;o.keys.length<=1&&!o.isLeaf;)this._root=o=0===o.keys.length?l:o.children[0]}},e.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,u)},Object.defineProperty(e.prototype,"height",{get:function(){for(var e=this._root,t=-1;null!=e;t++)e=e.children;return t},enumerable:!0,configurable:!0}),e.prototype.freeze=function(){var e=this;e.clear=e.set=e.editRange=function(){throw new Error("Attempted to modify a frozen BTree")}},e.prototype.unfreeze=function(){delete this.clear,delete this.set,delete this.editRange},e.prototype.checkValid=function(){var e=this._root.checkValid(0,this);i(e===this.size,"size mismatch: counted ",e,"but stored",this.size)},e}();t.default=n,Symbol&&Symbol.iterator&&(n.prototype[Symbol.iterator]=n.prototype.entries);var o=function(){function e(e,t){void 0===e&&(e=[]),this.keys=e,this.values=t||h,this.isShared=void 0}return Object.defineProperty(e.prototype,"isLeaf",{get:function(){return void 0===this.children},enumerable:!0,configurable:!0}),e.prototype.maxKey=function(){return this.keys[this.keys.length-1]},e.prototype.indexOf=function(e,t,r){for(var i=this.keys,n=0,o=i.length,s=o>>1;n<o;){var h=r(i[s],e);if(h<0)n=s+1;else{if(!(h>0)){if(0===h)return s;if(e===e)return i.length;throw new Error("BTree: NaN was used as a key")}o=s}s=n+o>>1}return s^t},e.prototype.minKey=function(){return this.keys[0]},e.prototype.clone=function(){var t=this.values;return new e(this.keys.slice(0),t===h?t:t.slice(0))},e.prototype.get=function(e,t,r){var i=this.indexOf(e,-1,r._compare);return i<0?t:this.values[i]},e.prototype.checkValid=function(e,t){var r=this.keys.length,n=this.values.length;return i(this.values===h?r<=n:r===n,"keys/values length mismatch: depth",e,"with lengths",r,n),i(0==e||r>0,"empty leaf at depth",e),r},e.prototype.set=function(e,t,r,i){var n=this.indexOf(e,-1,i._compare);if(n<0){if(n=~n,i._size++,this.keys.length<i._maxNodeSize)return this.insertInLeaf(n,e,t,i);var o=this.splitOffRightSide(),s=this;return n>this.keys.length&&(n-=this.keys.length,s=o),s.insertInLeaf(n,e,t,i),o}return!1!==r&&(void 0!==t&&this.reifyValues(),this.keys[n]=e,this.values[n]=t),!1},e.prototype.reifyValues=function(){return this.values===h?this.values=this.values.slice(0,this.keys.length):this.values},e.prototype.insertInLeaf=function(e,t,r,i){if(this.keys.splice(e,0,t),this.values===h){for(;h.length<i._maxNodeSize;)h.push(void 0);if(void 0===r)return!0;this.values=h.slice(0,this.keys.length-1)}return this.values.splice(e,0,r),!0},e.prototype.takeFromRight=function(e){var t=this.values;e.values===h?t!==h&&t.push(void 0):(t=this.reifyValues(),t.push(e.values.shift())),this.keys.push(e.keys.shift())},e.prototype.takeFromLeft=function(e){var t=this.values;e.values===h?t!==h&&t.unshift(void 0):(t=this.reifyValues(),t.unshift(e.values.pop())),this.keys.unshift(e.keys.pop())},e.prototype.splitOffRightSide=function(){var t=this.keys.length>>1;return new e(this.keys.splice(t),this.values===h?h:this.values.splice(t))},e.prototype.forRange=function(e,t,r,i,n,o,s){var a,u,f=n._compare;if(t===e){if(!r)return o;if(u=(a=this.indexOf(e,-1,f))+1,a<0)return o}else a=this.indexOf(e,0,f),u=this.indexOf(t,-1,f),u<0?u=~u:!0===r&&u++;var l=this.keys,c=this.values;if(void 0!==s)for(var p=a;p<u;p++){var y=l[p],d=s(y,c[p],o++);if(void 0!==d){if(!0===i){if(y!==l[p]||!0===this.isShared)throw new Error("BTree illegally changed or cloned in editRange");d.delete?(this.keys.splice(p,1),this.values!==h&&this.values.splice(p,1),n._size--,p--,u--):d.hasOwnProperty("value")&&(c[p]=d.value)}if(void 0!==d.break)return d}}else o+=u-a;return o},e.prototype.mergeSibling=function(e,t){var r,i;if((r=this.keys).push.apply(r,__spread(e.keys)),this.values===h){if(e.values===h)return;this.values=this.values.slice(0,this.keys.length)}(i=this.values).push.apply(i,__spread(e.reifyValues()))},e}(),s=function(e){function t(t,r){var i=this;if(!r){r=[];for(var n=0;n<t.length;n++)r[n]=t[n].maxKey()}return i=e.call(this,r)||this,i.children=t,i}return __extends(t,e),t.prototype.clone=function(){for(var e=this.children.slice(0),r=0;r<e.length;r++)e[r].isShared=!0;return new t(e,this.keys.slice(0))},t.prototype.minKey=function(){return this.children[0].minKey()},t.prototype.get=function(e,t,r){var i=this.indexOf(e,0,r._compare),n=this.children;return i<n.length?n[i].get(e,t,r):void 0},t.prototype.checkValid=function(e,t){var r=this.keys.length,n=this.children.length;i(r===n,"keys/children length mismatch: depth",e,"lengths",r,n),i(r>1,"internal node has length",r,"at depth",e);for(var o=0,s=this.children,h=this.keys,a=0,u=0;u<n;u++)o+=s[u].checkValid(e+1,t),a+=s[u].keys.length,i(o>=a,"wtf"),i(0===u||s[u-1].constructor===s[u].constructor,"type mismatch"),s[u].maxKey()!=h[u]&&i(!1,"keys[",u,"] =",h[u],"is wrong, should be ",s[u].maxKey(),"at depth",e),0===u||t._compare(h[u-1],h[u])<0||i(!1,"sort violation at depth",e,"index",u,"keys",h[u-1],h[u]);var f=a<(t.maxNodeSize>>1)*n;return(f||a>t.maxNodeSize*n)&&i(!1,f?"too few":"too many","children (",a,o,") at depth",e,", maxNodeSize:",t.maxNodeSize,"children.length:",n),o},t.prototype.set=function(e,t,r,i){var n=this.children,o=i._maxNodeSize,s=i._compare,h=Math.min(this.indexOf(e,0,s),n.length-1),a=n[h];if(a.isShared&&(n[h]=a=a.clone()),a.keys.length>=o){var u;h>0&&(u=n[h-1]).keys.length<o&&s(a.keys[0],e)<0?(u.isShared&&(n[h-1]=u=u.clone()),u.takeFromRight(a),this.keys[h-1]=u.maxKey()):void 0!==(u=n[h+1])&&u.keys.length<o&&s(a.maxKey(),e)<0&&(u.isShared&&(n[h+1]=u=u.clone()),u.takeFromLeft(a),this.keys[h]=n[h].maxKey())}var f=a.set(e,t,r,i);if(!1===f)return!1;if(this.keys[h]=a.maxKey(),!0===f)return!0;if(this.keys.length<o)return this.insert(h+1,f),!0;var l=this.splitOffRightSide(),c=this;return s(f.maxKey(),this.maxKey())>0&&(c=l,h-=this.keys.length),c.insert(h+1,f),l},t.prototype.insert=function(e,t){this.children.splice(e,0,t),this.keys.splice(e,0,t.maxKey())},t.prototype.splitOffRightSide=function(){var e=this.children.length>>1;return new t(this.children.splice(e),this.keys.splice(e))},t.prototype.takeFromRight=function(e){this.keys.push(e.keys.shift()),this.children.push(e.children.shift())},t.prototype.takeFromLeft=function(e){this.keys.unshift(e.keys.pop()),this.children.unshift(e.children.pop())},t.prototype.forRange=function(e,t,r,n,o,s,h){var a=o._compare,u=this.indexOf(e,0,a),f=u,l=Math.min(t===e?u:this.indexOf(t,0,a),this.keys.length-1),c=this.keys,p=this.children;if(n){if(f<=l)try{for(;f<=l;f++){p[f].isShared&&(p[f]=p[f].clone());var y=p[f].forRange(e,t,r,n,o,s,h);if(c[f]=p[f].maxKey(),"number"!=typeof y)return y;s=y}}finally{var d=o._maxNodeSize>>1;for(u>0&&u--,f=l;f>=u;f--)p[f].keys.length<=d&&this.tryMerge(f,o._maxNodeSize);0===p[0].keys.length&&(i(1===p.length&&1===c.length,"emptiness bug"),p.shift(),c.shift())}}else for(;f<=l;f++){var y=p[f].forRange(e,t,r,n,o,s,h);if("number"!=typeof y)return y;s=y}return s},t.prototype.tryMerge=function(e,t){var r=this.children;return e>=0&&e+1<r.length&&r[e].keys.length+r[e+1].keys.length<=t&&(r[e].isShared&&(r[e]=r[e].clone()),r[e].mergeSibling(r[e+1],t),r.splice(e+1,1),this.keys.splice(e+1,1),this.keys[e]=r[e].maxKey(),!0)},t.prototype.mergeSibling=function(e,t){var r,i,n=this.keys.length;(r=this.keys).push.apply(r,__spread(e.keys)),(i=this.children).push.apply(i,__spread(e.children)),this.tryMerge(n-1,t)},t}(o),h=[],a={delete:!0},u=function(){return a},f={break:!0},l=function(){var e=new o;return e.isShared=!0,e}(),c=[],p=[]});
+var __extends=this&&this.__extends||function(){var e=Object.setPrototypeOf||{__proto__:[]}instanceof Array&&function(e,t){e.__proto__=t}||function(e,t){for(var r in t)t.hasOwnProperty(r)&&(e[r]=t[r])};return function(t,r){function i(){this.constructor=t}e(t,r),t.prototype=null===r?Object.create(r):(i.prototype=r.prototype,new i)}}(),__read=this&&this.__read||function(e,t){var r="function"==typeof Symbol&&e[Symbol.iterator];if(!r)return e;var i,n,o=r.call(e),s=[];try{for(;(void 0===t||t-- >0)&&!(i=o.next()).done;)s.push(i.value)}catch(e){n={error:e}}finally{try{i&&!i.done&&(r=o.return)&&r.call(o)}finally{if(n)throw n.error}}return s},__spread=this&&this.__spread||function(){for(var e=[],t=0;t<arguments.length;t++)e=e.concat(__read(arguments[t]));return e};!function(e){if("object"==typeof module&&"object"==typeof module.exports){var t=e(require,exports);void 0!==t&&(module.exports=t)}else"function"==typeof define&&define.amd&&define(["require","exports"],e)}(function(e,t){"use strict";function r(e){void 0===e&&(e=function(){return{done:!0,value:void 0}});var t={next:e};return Symbol&&Symbol.iterator&&(t[Symbol.iterator]=function(){return this}),t}function i(e){for(var t=[],r=1;r<arguments.length;r++)t[r-1]=arguments[r];if(!e)throw t.unshift("B+ tree "),new Error(t.join(" "))}Object.defineProperty(t,"__esModule",{value:!0});var n=function(){function e(t,r,i){this._root=l,this._size=0,this._maxNodeSize=i>=4?Math.min(i,256):32,this._compare=r||e.defaultComparator,t&&this.setRange(t)}return e.defaultComparator=function(e,t){var r=e-t;return r===r?r:(e&&(e=e.valueOf()),t&&(t=t.valueOf()),e<t?-1:e>t?1:e==t?0:r)},Object.defineProperty(e.prototype,"size",{get:function(){return this._size},enumerable:!0,configurable:!0}),Object.defineProperty(e.prototype,"length",{get:function(){return this._size},enumerable:!0,configurable:!0}),e.prototype.clear=function(){this._root=l,this._size=0},e.prototype.forEach=function(e,t){var r=this;return void 0!==t&&(e=e.bind(t)),this.forEachPair(function(t,i){return e(i,t,r)})},e.prototype.forEachPair=function(e,t){var r=this.minKey(),i=this.maxKey();return this.forRange(r,i,!0,e,t)},e.prototype.get=function(e,t){return this._root.get(e,t,this)},e.prototype.set=function(e,t,r){this._root.isShared&&(this._root=this._root.clone());var i=this._root.set(e,t,r,this);return!0===i||!1===i?i:(this._root=new s([this._root,i]),!0)},e.prototype.has=function(e){return 0!==this.forRange(e,e,!0,void 0)},e.prototype.delete=function(e){return 0!==this.editRange(e,e,!0,u)},e.prototype.entries=function(e,t){var i=this.findPath(e);if(void 0===i)return r();var n=i.nodequeue,o=i.nodeindex,s=i.leaf,h=void 0!==t?1:0,a=void 0===e?-1:s.indexOf(e,0,this._compare)-1;return r(function(){e:for(;;)switch(h){case 0:if(++a<s.keys.length)return{done:!1,value:[s.keys[a],s.values[a]]};h=2;continue;case 1:if(++a<s.keys.length)return t[0]=s.keys[a],t[1]=s.values[a],{done:!1,value:t};h=2;case 2:for(var e=-1;;){if(++e>=n.length){h=3;continue e}if(++o[e]<n[e].length)break}for(;e>0;e--)n[e-1]=n[e][o[e]].children,o[e-1]=0;s=n[0][o[0]],a=-1,h=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},e.prototype.entriesReversed=function(e,t,n){if(void 0===(e=e||this.maxKey()))return r();var o=this.findPath(e)||this.findPath(this.maxKey()),s=o.nodequeue,h=o.nodeindex,a=o.leaf;i(!s[0]||a===s[0][h[0]],"wat!");var u=a.indexOf(e,0,this._compare);n||this._compare(a.keys[u],e)>0||u++;var f=void 0!==t?1:0;return r(function(){e:for(;;)switch(f){case 0:if(--u>=0)return{done:!1,value:[a.keys[u],a.values[u]]};f=2;continue;case 1:if(--u>=0)return t[0]=a.keys[u],t[1]=a.values[u],{done:!1,value:t};f=2;case 2:for(var e=-1;;){if(++e>=s.length){f=3;continue e}if(--h[e]>=0)break}for(;e>0;e--)s[e-1]=s[e][h[e]].children,h[e-1]=s[e-1].length-1;a=s[0][h[0]],u=a.keys.length,f=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},e.prototype.findPath=function(e){var t,r,i=this._root;if(i.isLeaf)t=c,r=c;else{t=[],r=[];for(var n=0;!i.isLeaf;n++){if(t[n]=i.children,r[n]=void 0===e?0:i.indexOf(e,0,this._compare),r[n]>=t[n].length)return;i=t[n][r[n]]}t.reverse(),r.reverse()}return{nodequeue:t,nodeindex:r,leaf:i}},e.prototype.keys=function(e){var t=this.entries(e,p);return r(function(){var e=t.next();return e.value&&(e.value=e.value[0]),e})},e.prototype.values=function(e){var t=this.entries(e,p);return r(function(){var e=t.next();return e.value&&(e.value=e.value[1]),e})},Object.defineProperty(e.prototype,"maxNodeSize",{get:function(){return this._maxNodeSize},enumerable:!0,configurable:!0}),e.prototype.minKey=function(){return this._root.minKey()},e.prototype.maxKey=function(){return this._root.maxKey()},e.prototype.clone=function(){this._root.isShared=!0;var t=new e(void 0,this._compare,this._maxNodeSize);return t._root=this._root,t._size=this._size,t},e.prototype.toArray=function(e){void 0===e&&(e=2147483647);var t=this.minKey(),r=this.maxKey();return void 0!==t?this.getRange(t,r,!0,e):[]},e.prototype.keysArray=function(){var e=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(t,r){e.push(t)}),e},e.prototype.valuesArray=function(){var e=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(t,r){e.push(r)}),e},e.prototype.toString=function(){return this.toArray().toString()},e.prototype.setIfNotPresent=function(e,t){return this.set(e,t,!1)},e.prototype.changeIfPresent=function(e,t){return 0!==this.editRange(e,e,!0,function(e,r){return{value:t}})},e.prototype.getRange=function(e,t,r,i){void 0===i&&(i=67108863);var n=[];return this._root.forRange(e,t,r,!1,this,0,function(e,t){return n.push([e,t]),n.length>i?f:void 0}),n},e.prototype.setRange=function(e){for(var t=0;t<e.length;t++)this.set(e[t][0],e[t][1]);return this},e.prototype.forRange=function(e,t,r,i,n){var o=this._root.forRange(e,t,r,!1,this,n||0,i);return"number"==typeof o?o:o.break},e.prototype.editRange=function(e,t,r,i,n){var o=this._root;o.isShared&&(this._root=o=o.clone());try{var s=o.forRange(e,t,r,!0,this,n||0,i);return"number"==typeof s?s:s.break}finally{for(;o.keys.length<=1&&!o.isLeaf;)this._root=o=0===o.keys.length?l:o.children[0]}},e.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,u)},Object.defineProperty(e.prototype,"height",{get:function(){for(var e=this._root,t=-1;null!=e;t++)e=e.children;return t},enumerable:!0,configurable:!0}),e.prototype.freeze=function(){var e=this;e.clear=e.set=e.editRange=function(){throw new Error("Attempted to modify a frozen BTree")}},e.prototype.unfreeze=function(){delete this.clear,delete this.set,delete this.editRange},e.prototype.checkValid=function(){var e=this._root.checkValid(0,this);i(e===this.size,"size mismatch: counted ",e,"but stored",this.size)},e}();t.default=n,Symbol&&Symbol.iterator&&(n.prototype[Symbol.iterator]=n.prototype.entries);var o=function(){function e(e,t){void 0===e&&(e=[]),this.keys=e,this.values=t||h,this.isShared=void 0}return Object.defineProperty(e.prototype,"isLeaf",{get:function(){return void 0===this.children},enumerable:!0,configurable:!0}),e.prototype.maxKey=function(){return this.keys[this.keys.length-1]},e.prototype.indexOf=function(e,t,r){for(var i=this.keys,n=0,o=i.length,s=o>>1;n<o;){var h=r(i[s],e);if(h<0)n=s+1;else{if(!(h>0)){if(0===h)return s;if(e===e)return i.length;throw new Error("BTree: NaN was used as a key")}o=s}s=n+o>>1}return s^t},e.prototype.minKey=function(){return this.keys[0]},e.prototype.clone=function(){var t=this.values;return new e(this.keys.slice(0),t===h?t:t.slice(0))},e.prototype.get=function(e,t,r){var i=this.indexOf(e,-1,r._compare);return i<0?t:this.values[i]},e.prototype.checkValid=function(e,t){var r=this.keys.length,n=this.values.length;return i(this.values===h?r<=n:r===n,"keys/values length mismatch: depth",e,"with lengths",r,n),i(0==e||r>0,"empty leaf at depth",e),r},e.prototype.set=function(e,t,r,i){var n=this.indexOf(e,-1,i._compare);if(n<0){if(n=~n,i._size++,this.keys.length<i._maxNodeSize)return this.insertInLeaf(n,e,t,i);var o=this.splitOffRightSide(),s=this;return n>this.keys.length&&(n-=this.keys.length,s=o),s.insertInLeaf(n,e,t,i),o}return!1!==r&&(void 0!==t&&this.reifyValues(),this.keys[n]=e,this.values[n]=t),!1},e.prototype.reifyValues=function(){return this.values===h?this.values=this.values.slice(0,this.keys.length):this.values},e.prototype.insertInLeaf=function(e,t,r,i){if(this.keys.splice(e,0,t),this.values===h){for(;h.length<i._maxNodeSize;)h.push(void 0);if(void 0===r)return!0;this.values=h.slice(0,this.keys.length-1)}return this.values.splice(e,0,r),!0},e.prototype.takeFromRight=function(e){var t=this.values;e.values===h?t!==h&&t.push(void 0):(t=this.reifyValues(),t.push(e.values.shift())),this.keys.push(e.keys.shift())},e.prototype.takeFromLeft=function(e){var t=this.values;e.values===h?t!==h&&t.unshift(void 0):(t=this.reifyValues(),t.unshift(e.values.pop())),this.keys.unshift(e.keys.pop())},e.prototype.splitOffRightSide=function(){var t=this.keys.length>>1;return new e(this.keys.splice(t),this.values===h?h:this.values.splice(t))},e.prototype.forRange=function(e,t,r,i,n,o,s){var a,u,f=n._compare;if(t===e){if(!r)return o;if(u=(a=this.indexOf(e,-1,f))+1,a<0)return o}else a=this.indexOf(e,0,f),u=this.indexOf(t,-1,f),u<0?u=~u:!0===r&&u++;var l=this.keys,c=this.values;if(void 0!==s)for(var p=a;p<u;p++){var y=l[p],d=s(y,c[p],o++);if(void 0!==d){if(!0===i){if(y!==l[p]||!0===this.isShared)throw new Error("BTree illegally changed or cloned in editRange");d.delete?(this.keys.splice(p,1),this.values!==h&&this.values.splice(p,1),n._size--,p--,u--):d.hasOwnProperty("value")&&(c[p]=d.value)}if(void 0!==d.break)return d}}else o+=u-a;return o},e.prototype.mergeSibling=function(e,t){var r,i;if((r=this.keys).push.apply(r,__spread(e.keys)),this.values===h){if(e.values===h)return;this.values=this.values.slice(0,this.keys.length)}(i=this.values).push.apply(i,__spread(e.reifyValues()))},e}(),s=function(e){function t(t,r){var i=this;if(!r){r=[];for(var n=0;n<t.length;n++)r[n]=t[n].maxKey()}return i=e.call(this,r)||this,i.children=t,i}return __extends(t,e),t.prototype.clone=function(){for(var e=this.children.slice(0),r=0;r<e.length;r++)e[r].isShared=!0;return new t(e,this.keys.slice(0))},t.prototype.minKey=function(){return this.children[0].minKey()},t.prototype.get=function(e,t,r){var i=this.indexOf(e,0,r._compare),n=this.children;return i<n.length?n[i].get(e,t,r):void 0},t.prototype.checkValid=function(e,t){var r=this.keys.length,n=this.children.length;i(r===n,"keys/children length mismatch: depth",e,"lengths",r,n),i(r>1,"internal node has length",r,"at depth",e);for(var o=0,s=this.children,h=this.keys,a=0,u=0;u<n;u++)o+=s[u].checkValid(e+1,t),a+=s[u].keys.length,i(o>=a,"wtf"),i(0===u||s[u-1].constructor===s[u].constructor,"type mismatch"),s[u].maxKey()!=h[u]&&i(!1,"keys[",u,"] =",h[u],"is wrong, should be ",s[u].maxKey(),"at depth",e),0===u||t._compare(h[u-1],h[u])<0||i(!1,"sort violation at depth",e,"index",u,"keys",h[u-1],h[u]);var f=a<(t.maxNodeSize>>1)*n;return(f||a>t.maxNodeSize*n)&&i(!1,f?"too few":"too many","children (",a,o,") at depth",e,", maxNodeSize:",t.maxNodeSize,"children.length:",n),o},t.prototype.set=function(e,t,r,i){var n=this.children,o=i._maxNodeSize,s=i._compare,h=Math.min(this.indexOf(e,0,s),n.length-1),a=n[h];if(a.isShared&&(n[h]=a=a.clone()),a.keys.length>=o){var u;h>0&&(u=n[h-1]).keys.length<o&&s(a.keys[0],e)<0?(u.isShared&&(n[h-1]=u=u.clone()),u.takeFromRight(a),this.keys[h-1]=u.maxKey()):void 0!==(u=n[h+1])&&u.keys.length<o&&s(a.maxKey(),e)<0&&(u.isShared&&(n[h+1]=u=u.clone()),u.takeFromLeft(a),this.keys[h]=n[h].maxKey())}var f=a.set(e,t,r,i);if(!1===f)return!1;if(this.keys[h]=a.maxKey(),!0===f)return!0;if(this.keys.length<o)return this.insert(h+1,f),!0;var l=this.splitOffRightSide(),c=this;return s(f.maxKey(),this.maxKey())>0&&(c=l,h-=this.keys.length),c.insert(h+1,f),l},t.prototype.insert=function(e,t){this.children.splice(e,0,t),this.keys.splice(e,0,t.maxKey())},t.prototype.splitOffRightSide=function(){var e=this.children.length>>1;return new t(this.children.splice(e),this.keys.splice(e))},t.prototype.takeFromRight=function(e){this.keys.push(e.keys.shift()),this.children.push(e.children.shift())},t.prototype.takeFromLeft=function(e){this.keys.unshift(e.keys.pop()),this.children.unshift(e.children.pop())},t.prototype.forRange=function(e,t,r,n,o,s,h){var a=o._compare,u=this.indexOf(e,0,a),f=u,l=Math.min(t===e?u:this.indexOf(t,0,a),this.keys.length-1),c=this.keys,p=this.children;if(n){if(f<=l)try{for(;f<=l;f++){p[f].isShared&&(p[f]=p[f].clone());var y=p[f].forRange(e,t,r,n,o,s,h);if(c[f]=p[f].maxKey(),"number"!=typeof y)return y;s=y}}finally{var d=o._maxNodeSize>>1;for(u>0&&u--,f=l;f>=u;f--)p[f].keys.length<=d&&this.tryMerge(f,o._maxNodeSize);0===p[0].keys.length&&(i(1===p.length&&1===c.length,"emptiness bug"),p.shift(),c.shift())}}else for(;f<=l;f++){var y=p[f].forRange(e,t,r,n,o,s,h);if("number"!=typeof y)return y;s=y}return s},t.prototype.tryMerge=function(e,t){var r=this.children;return e>=0&&e+1<r.length&&r[e].keys.length+r[e+1].keys.length<=t&&(r[e].isShared&&(r[e]=r[e].clone()),r[e].mergeSibling(r[e+1],t),r.splice(e+1,1),this.keys.splice(e+1,1),this.keys[e]=r[e].maxKey(),!0)},t.prototype.mergeSibling=function(e,t){var r,i,n=this.keys.length;(r=this.keys).push.apply(r,__spread(e.keys)),(i=this.children).push.apply(i,__spread(e.children)),this.tryMerge(n-1,t)},t}(o),h=[],a={delete:!0},u=function(){return a},f={break:!0},l=function(){var e=new o;return e.isShared=!0,e}(),c=[],p=[]});

package.json

 {
   "name": "sorted-btree",
-  "version": "1.0.2",
-  "description": "A list of key-value pairs kept sorted in a fast in-memory B+ tree with a powerful API, similar to Map.",
+  "version": "1.0.3",
+  "description": "A sorted list of key-value pairs in a fast, typed in-memory B+ tree with a powerful API.",
   "main": "b+tree.js",
@@ -17,2 +17,4 @@ "scripts": {
     "b+tree.min.js",
+    "sorted-array.js",
+    "sorted-array.d.ts",
     "readme.md"
@@ -29,7 +31,8 @@ ],
     "sorted",
+    "set",
     "map",
+    "list",
     "collection",
     "fast-cloning",
     "copy-on-write",
-    "lazy-copying",
     "optimized"
@@ -44,5 +47,10 @@ ],
   "devDependencies": {
+    "@types/collections": "^5.0.0",
     "@types/jasmine": "^2.8.8",
     "@types/mersenne-twister": "^1.1.2",
+    "@types/node": "^10.5.3",
     "babel-core": "^6.26.3",
+    "bintrees": "^1.0.2",
+    "collections": "^5.1.5",
+    "functional-red-black-tree": "^1.0.1",
     "jest": "^23.4.1",
@@ -55,3 +63,2 @@ "mersenne-twister": "^1.1.0",
   },
-  "dependencies": {},
   "jest": {
@@ -95,3 +102,6 @@ "transform": {
     ]
+  },
+  "dependencies": {
+    "@types/bintrees": "^1.0.2"
   }
 }

readme.md

 B+ tree
--------
+=======
 
@@ -8,14 +8,21 @@ B+ trees are ordered collections of key-value pairs, sorted by key.
 
-### Features ###
+`BTree` is faster and/or more memory-efficient than other popular JavaScript sorted trees (see Benchmarks). However, data structures in JavaScript tend to be slower than the built-in `Array` and `Map` data structures in typical cases, because the built-in data structures are mostly implemented in a faster language such as C++. Even so, if you have a large amount of data that you want to keep sorted, the built-in data structures will not serve you well, and `BTree` offers features like fast cloning that the built-in types don't.
 
+Features
+--------
+
 - Requires ES5 only (`Symbol.iterator` is not required but is used if defined.)
-- Supports a custom comparator, which must be passed to the constructor.
+- Includes typings (`BTree` was written in TypeScript)
+- API similar to ES6 `Map` with methods such as `size(), clear()`, 
+  `forEach((v,k,tree)=>{}), get(K), set(K,V), has(K), delete(K)`,
+  plus iterator functions `keys()`, `values()` and `entries()`.
+- Supports keys that are numbers, strings, arrays of numbers/strings, `Date`,
+  and objects that have a `valueOf()` method that returns a number or string.
+- Other data types can also be supported with a custom comparator (second  
+  constructor argument).
 - Supports O(1) fast cloning with subtree sharing. This works by marking the
   root node as "shared between instances". This makes the tree read-only 
   with copy-on-edit behavior; both copies of the tree remain mutable.
-- API similar to `Map<K,V>` with methods such as `size(), clear()`, 
-  `forEach((v,k,tree)=>{}), get(K), set(K,V), has(K), delete(K)`,
-  plus iterator functions `keys()`, `values()` and `entries()`.
-- For efficiency, when a node fills up, items are shifted to siblings when
-  possible to encourage nodes to stay near their capacity.
+- When a node fills up, items are shifted to siblings when possible to 
+  keep nodes near their capacity, to improve memory utilization.
 - Efficiently supports sets (keys without values). The collection does
@@ -26,2 +33,3 @@ not allocate memory for values if the value `undefined` is associated
 - Throws an exception if you try to use `NaN` as a key, but infinity is allowed.
+- No dependencies. Under 14K minified.
 
@@ -53,4 +61,7 @@ Additional operations supported on this B+ tree:
 
-### Custom comparator example ###
+Examples
+--------
 
+### Custom comparator ###
+
 Given a set of `{name: string, age: number}` objects, you can create a tree sorted by name and then by age like this:
@@ -91,4 +102,162 @@
 
-### Endnote ###
+Benchmarks (in milliseconds for integer keys/values)
+----------------------------------------------------
 
+- These benchmark results were gathered on my PC in Node v10.4.1
+- `BTree` is 3 to 5 times faster than `SortedMap` and `SortedSet` in the `collections` package
+- `BTree` has similar speed to `RBTree` at smaller sizes, but is faster at very large sizes and uses less memory because it packs many keys into arrays instead of allocating an extra heap object for every key.
+- If you need a persistent tree, `functional-red-black-tree` is faster than I expected, but `BTree` should require less memory.
+- "Sorted array" refers to `SortedArray<K,V>`, a wrapper class for an array of `[K,V]` pairs. Benchmark results were not gathered for sorted arrays with one million elements (it takes too long)
+
+### Insertions at random locations: sorted-btree vs the competition ###
+
+    0.9     Insert 1000 pairs in sorted-btree's BTree
+    0.5     Insert 1000 pairs in sorted-btree's BTree set (no values)
+    2.6     Insert 1000 pairs in collections' SortedMap
+    1.7     Insert 1000 pairs in collections' SortedSet (no values)
+    0.7     Insert 1000 pairs in functional-red-black-tree
+    0.5     Insert 1000 pairs in bintrees' RBTree (no values)
+    
+    10.9    Insert 10000 pairs in sorted-btree's BTree
+    8.6     Insert 10000 pairs in sorted-btree's BTree set (no values)
+    47.7    Insert 10000 pairs in collections' SortedMap
+    27.8    Insert 10000 pairs in collections' SortedSet (no values)
+    9.4     Insert 10000 pairs in functional-red-black-tree
+    6.6     Insert 10000 pairs in bintrees' RBTree (no values)
+    
+    138.5   Insert 100000 pairs in sorted-btree's BTree
+    92.3    Insert 100000 pairs in sorted-btree's BTree set (no values)
+    601     Insert 100000 pairs in collections' SortedMap
+    450     Insert 100000 pairs in collections' SortedSet (no values)
+    179.3   Insert 100000 pairs in functional-red-black-tree
+    110     Insert 100000 pairs in bintrees' RBTree (no values)
+    
+    1834    Insert 1000000 pairs in sorted-btree's BTree
+    1262    Insert 1000000 pairs in sorted-btree's BTree set (no values)
+    9674    Insert 1000000 pairs in collections' SortedMap
+    6108    Insert 1000000 pairs in collections' SortedSet (no values)
+    3811    Insert 1000000 pairs in functional-red-black-tree
+    1883    Insert 1000000 pairs in bintrees' RBTree (no values)
+
+### Insertions at random locations: sorted-btree vs Array vs Map ###
+
+    0.5     Insert 1000 pairs in sorted array
+    0.8     Insert 1000 pairs in B+ tree
+    0.1     Insert 1000 pairs in ES6 Map (hashtable)
+    
+    16.6    Insert 10000 pairs in sorted array
+    9.9     Insert 10000 pairs in B+ tree
+    1.4     Insert 10000 pairs in ES6 Map (hashtable)
+    
+    56670   Insert 100000 pairs in sorted array
+    140.5   Insert 100000 pairs in B+ tree
+    21.8    Insert 100000 pairs in ES6 Map (hashtable)
+    
+    SLOW!   Insert 1000000 pairs in sorted array
+    1913    Insert 1000000 pairs in B+ tree
+    346.5   Insert 1000000 pairs in ES6 Map (hashtable)
+
+### Insert in order, delete: sorted-btree vs the competition ###
+
+    0.8     Insert 1000 sorted pairs in B+ tree
+    0.7     Insert 1000 sorted keys in B+ tree (no values)
+    0.6     Insert 1000 sorted pairs in collections' SortedMap
+    0.4     Insert 1000 sorted keys in collections' SortedSet (no values)
+    0.7     Insert 1000 sorted pairs in functional-red-black-tree
+    0.5     Insert 1000 sorted keys in bintrees' RBTree (no values)
+    0.1     Delete every second item in B+ tree
+    0.1     Delete every second item in B+ tree set
+    0.3     Delete every second item in collections' SortedMap
+    0.3     Delete every second item in collections' SortedSet
+    0.1     Delete every second item in functional-red-black-tree
+    0.2     Delete every second item in bintrees' RBTree
+    
+    8.9     Insert 10000 sorted pairs in B+ tree
+    8.4     Insert 10000 sorted keys in B+ tree (no values)
+    6.3     Insert 10000 sorted pairs in collections' SortedMap
+    3.9     Insert 10000 sorted keys in collections' SortedSet (no values)
+    11.4    Insert 10000 sorted pairs in functional-red-black-tree
+    6.8     Insert 10000 sorted keys in bintrees' RBTree (no values)
+    1.7     Delete every second item in B+ tree
+    1.6     Delete every second item in B+ tree set
+    3.2     Delete every second item in collections' SortedMap
+    3       Delete every second item in collections' SortedSet
+    1       Delete every second item in functional-red-black-tree
+    2.6     Delete every second item in bintrees' RBTree
+    
+    87.5    Insert 100000 sorted pairs in B+ tree
+    88.2    Insert 100000 sorted keys in B+ tree (no values)
+    102.2   Insert 100000 sorted pairs in collections' SortedMap
+    65      Insert 100000 sorted keys in collections' SortedSet (no values)
+    177.7   Insert 100000 sorted pairs in functional-red-black-tree
+    84.8    Insert 100000 sorted keys in bintrees' RBTree (no values)
+    25.4    Delete every second item in B+ tree
+    25.1    Delete every second item in B+ tree set
+    37.4    Delete every second item in collections' SortedMap
+    32.1    Delete every second item in collections' SortedSet
+    12.9    Delete every second item in functional-red-black-tree
+    37.3    Delete every second item in bintrees' RBTree
+    
+    965     Insert 1000000 sorted pairs in B+ tree
+    945     Insert 1000000 sorted keys in B+ tree (no values)
+    1162    Insert 1000000 sorted pairs in collections' SortedMap
+    689     Insert 1000000 sorted keys in collections' SortedSet (no values)
+    2177    Insert 1000000 sorted pairs in functional-red-black-tree
+    1033    Insert 1000000 sorted keys in bintrees' RBTree (no values)
+    589     Delete every second item in B+ tree
+    579     Delete every second item in B+ tree set
+    1578    Delete every second item in collections' SortedMap
+    734     Delete every second item in collections' SortedSet
+    898     Delete every second item in functional-red-black-tree
+    639     Delete every second item in bintrees' RBTree
+
+### Insert in order, scan, delete: sorted-btree vs the competition ###
+
+    0.3     Insert 1000 sorted pairs in array
+    0.7     Insert 1000 sorted pairs in B+ tree
+    0.1     Insert 1000 sorted pairs in Map hashtable
+    0       Sum of all values with forEach in sorted array: 26886700
+    0       Sum of all values with forEachPair in B+ tree: 26886700
+    0       Sum of all values with forEach in B+ tree: 26886700
+    0       Sum of all values with forEach in Map: 26886700
+    0.1     Delete every second item in sorted array
+    0.1     Delete every second item in B+ tree
+    0       Delete every second item in Map hashtable
+    
+    4.1     Insert 10000 sorted pairs in array
+    8.3     Insert 10000 sorted pairs in B+ tree
+    1.4     Insert 10000 sorted pairs in Map hashtable
+    0.2     Sum of all values with forEach in sorted array: 2744969490
+    0.3     Sum of all values with forEachPair in B+ tree: 2744969490
+    0.5     Sum of all values with forEach in B+ tree: 2744969490
+    0.2     Sum of all values with forEach in Map: 2744969490
+    1.4     Delete every second item in sorted array
+    1.8     Delete every second item in B+ tree
+    0.3     Delete every second item in Map hashtable
+    
+    74.6    Insert 100000 sorted pairs in array
+    101.6   Insert 100000 sorted pairs in B+ tree
+    20.3    Insert 100000 sorted pairs in Map hashtable
+    2.6     Sum of all values with forEach in sorted array: 275145933120
+    3.6     Sum of all values with forEachPair in B+ tree: 275145933120
+    5.2     Sum of all values with forEach in B+ tree: 275145933120
+    2.2     Sum of all values with forEach in Map: 275145933120
+    2369    Delete every second item in sorted array
+    28.4    Delete every second item in B+ tree
+    3.9     Delete every second item in Map hashtable
+    
+    1030    Insert 1000000 sorted pairs in array
+    983     Insert 1000000 sorted pairs in B+ tree
+    331     Insert 1000000 sorted pairs in Map hashtable
+    26.1    Sum of all values with forEach in sorted array: 27505579162970
+    38.3    Sum of all values with forEachPair in B+ tree: 27505579162970
+    52.9    Sum of all values with forEach in B+ tree: 27505579162970
+    23      Sum of all values with forEach in Map: 27505579162970
+    SLOW!   Delete every second item in sorted array
+    658     Delete every second item in B+ tree
+    98.3    Delete every second item in Map hashtable
+
+Endnote
+-------
+
 ♥ This package was made to help people [learn TypeScript & React](http://typescript-react-primer.loyc.net/).
@@ -95,0 +264,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

112581

increased by15.41%

Number of package files

8

increased by33.33%

Lines of code

1565

increased by8.68%

Number of lines in readme file

263

increased by179.79%

Worsened metrics

Dependency count

1

increased byInfinity%

Dev dependency count

14

increased by55.56%

Dependency changes

• + Added@types/bintrees@^1.0.2

• + Added@types/bintrees@1.0.6(transitive)