sorted-btree - npm Package Compare versions

Comparing version 1.0.3 to 1.0.4

b+tree.d.ts

@@ -40,2 +40,7 @@ export declare type EditRangeResult<V, R = number> = {
 }
+/** Compares two numbers, strings, arrays of numbers/strings, Dates,
+ *  or objects that have a valueOf() method returning a number or string.
+ *  Optimized for numbers. Returns 1 if a>b, -1 if a<b, and 0 if a===b.
+ */
+export declare function defaultComparator(a: any, b: any): number;
 /**
@@ -110,3 +115,2 @@ * A reasonably fast collection of key-value pairs with a powerful API.
     _compare: (a: K, b: K) => number;
-    static defaultComparator(a: any, b: any): number;
     /**
@@ -113,0 +117,0 @@ * Initializes an empty B+ tree.

b+tree.js

@@ -43,2 +43,19 @@ // B+ tree by David Piepgrass. License: MIT
     Object.defineProperty(exports, "__esModule", { value: true });
+    /** Compares two numbers, strings, arrays of numbers/strings, Dates,
+     *  or objects that have a valueOf() method returning a number or string.
+     *  Optimized for numbers. Returns 1 if a>b, -1 if a<b, and 0 if a===b.
+     */
+    function defaultComparator(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;
+    }
+    exports.defaultComparator = defaultComparator;
+    ;
     /**
@@ -121,18 +138,6 @@ * A reasonably fast collection of key-value pairs with a powerful API.
             this._maxNodeSize = maxNodeSize >= 4 ? Math.min(maxNodeSize, 256) : 32;
-            this._compare = compare || BTree.defaultComparator;
+            this._compare = compare || 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", {
@@ -139,0 +144,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(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=[]});
+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,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)}function i(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 n(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}),t.defaultComparator=r;var o=function(){function e(e,t,i){this._root=c,this._size=0,this._maxNodeSize=i>=4?Math.min(i,256):32,this._compare=t||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=c,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 h([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,f)},e.prototype.entries=function(e,t){var r=this.findPath(e);if(void 0===r)return i();var n=r.nodequeue,o=r.nodeindex,s=r.leaf,h=void 0!==t?1:0,a=void 0===e?-1:s.indexOf(e,0,this._compare)-1;return i(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,r){if(void 0===(e=e||this.maxKey()))return i();var o=this.findPath(e)||this.findPath(this.maxKey()),s=o.nodequeue,h=o.nodeindex,a=o.leaf;n(!s[0]||a===s[0][h[0]],"wat!");var u=a.indexOf(e,0,this._compare);r||this._compare(a.keys[u],e)>0||u++;var f=void 0!==t?1:0;return i(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=p,r=p;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,y);return i(function(){var e=t.next();return e.value&&(e.value=e.value[0]),e})},e.prototype.values=function(e){var t=this.entries(e,y);return i(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?l: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?c:o.children[0]}},e.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,f)},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);n(e===this.size,"size mismatch: counted ",e,"but stored",this.size)},e}();t.default=o,Symbol&&Symbol.iterator&&(o.prototype[Symbol.iterator]=o.prototype.entries);var s=function(){function e(e,t){void 0===e&&(e=[]),this.keys=e,this.values=t||a,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===a?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,i=this.values.length;return n(this.values===a?r<=i:r===i,"keys/values length mismatch: depth",e,"with lengths",r,i),n(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===a?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===a){for(;a.length<i._maxNodeSize;)a.push(void 0);if(void 0===r)return!0;this.values=a.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===a?t!==a&&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===a?t!==a&&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===a?a:this.values.splice(t))},e.prototype.forRange=function(e,t,r,i,n,o,s){var h,u,f=n._compare;if(t===e){if(!r)return o;if(u=(h=this.indexOf(e,-1,f))+1,h<0)return o}else h=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=h;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!==a&&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-h;return o},e.prototype.mergeSibling=function(e,t){var r,i;if((r=this.keys).push.apply(r,__spread(e.keys)),this.values===a){if(e.values===a)return;this.values=this.values.slice(0,this.keys.length)}(i=this.values).push.apply(i,__spread(e.reifyValues()))},e}(),h=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,i=this.children.length;n(r===i,"keys/children length mismatch: depth",e,"lengths",r,i),n(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<i;u++)o+=s[u].checkValid(e+1,t),a+=s[u].keys.length,n(o>=a,"wtf"),n(0===u||s[u-1].constructor===s[u].constructor,"type mismatch"),s[u].maxKey()!=h[u]&&n(!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||n(!1,"sort violation at depth",e,"index",u,"keys",h[u-1],h[u]);var f=a<(t.maxNodeSize>>1)*i;return(f||a>t.maxNodeSize*i)&&n(!1,f?"too few":"too many","children (",a,o,") at depth",e,", maxNodeSize:",t.maxNodeSize,"children.length:",i),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,i,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(i){if(f<=l)try{for(;f<=l;f++){p[f].isShared&&(p[f]=p[f].clone());var y=p[f].forRange(e,t,r,i,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&&(n(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,i,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}(s),a=[],u={delete:!0},f=function(){return u},l={break:!0},c=function(){var e=new s;return e.isShared=!0,e}(),p=[],y=[]});

package.json

 {
   "name": "sorted-btree",
-  "version": "1.0.3",
+  "version": "1.0.4",
   "description": "A sorted list of key-value pairs in a fast, typed in-memory B+ tree with a powerful API.",
@@ -5,0 +5,0 @@ "main": "b+tree.js",

readme.md

@@ -8,3 +8,3 @@ B+ tree
 
-`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.
+`BTree` is faster and/or uses less memory 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.
 
@@ -58,4 +58,2 @@ Features
 
-B+ trees normally use memory more efficiently than hashtables (such as the standard `Map`), although in JavaScript this is not guaranteed because the B+ tree's memory efficiency depends on avoiding wasted space in the arrays for each node, and JavaScript provides no way to detect or control the capacity of an array's underlying memory area.
-
 Examples
@@ -106,4 +104,5 @@ --------
 - `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.
+- `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 one array 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.
+- B+ trees normally use less memory than hashtables (such as the standard `Map`), although in JavaScript this is not guaranteed because the B+ tree's memory efficiency depends on avoiding wasted space in the arrays for each node, and JavaScript provides no way to detect or control the capacity of an array's underlying memory area. Also, `Map` should be faster because it does not sort its keys.
 - "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)
@@ -110,0 +109,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

113080

increased by0.44%

Lines of code

1574

increased by0.58%

Worsened metrics

Number of lines in readme file

262

decreased by-0.38%

No dependency changes