Socket
Socket
Sign inDemoInstall

sorted-btree

Package Overview
Dependencies
Maintainers
1
Versions
24
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

sorted-btree - npm Package Compare versions

Comparing version 1.2.1 to 1.2.2

2

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)}}();!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=p,this._size=0,this._maxNodeSize=i>=4?Math.min(i,256):32,this._compare=t||r,e&&this.setPairs(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}),Object.defineProperty(e.prototype,"isEmpty",{get:function(){return 0===this._size},enumerable:!0,configurable:!0}),e.prototype.clear=function(){this._root=p,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.with=function(e,t,r){var i=this.clone();return i.set(e,t,r)||r?i:this},e.prototype.withPairs=function(e,t){var r=this.clone();return 0!==r.setPairs(e,t)||t?r:this},e.prototype.withKeys=function(e,t){for(var r=this.clone(),i=!1,n=0;n<e.length;n++)i=r.set(e[n],void 0,!1)||i;return t&&!i?this:r},e.prototype.without=function(e,t){return this.withoutRange(e,e,!0,t)},e.prototype.withoutKeys=function(e,t){var r=this.clone();return r.deleteKeys(e)||!t?r:this},e.prototype.withoutRange=function(e,t,r,i){var n=this.clone();return 0===n.deleteRange(e,t,r)&&i?this:n},e.prototype.filter=function(e,t){var r,i=this.greedyClone();return i.editAll(function(t,i,n){if(!e(t,i,n))return r=u}),!r&&t?this:i},e.prototype.mapValues=function(e){var t={},r=this.greedyClone();return r.editAll(function(r,i,n){return t.value=e(i,r,n),t}),r},e.prototype.reduce=function(e,t){for(var r,i=0,n=t,o=this.entries(this.minKey(),y);!(r=o.next()).done;)n=e(n,r.value,i++,this);return n},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=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,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.greedyClone=function(t){var r=new e(void 0,this._compare,this._maxNodeSize);return r._root=this._root.greedyClone(t),r._size=this._size,r},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.nextHigherPair=function(e){var t=this.entries(e,y),r=t.next();return!r.done&&this._compare(r.value[0],e)<=0&&(r=t.next()),r.value},e.prototype.nextHigherKey=function(e){var t=this.nextHigherPair(e);return t?t[0]:t},e.prototype.nextLowerPair=function(e){return this.entriesReversed(e,y,!0).next().value},e.prototype.nextLowerKey=function(e){var t=this.nextLowerPair(e);return t?t[0]:t},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.setPairs=function(e,t){for(var r=0,i=0;i<e.length;i++)this.set(e[i][0],e[i][1],t)&&r++;return r},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?p:o.children[0]}},e.prototype.editAll=function(e,t){return this.editRange(this.minKey(),this.maxKey(),!0,e,t)},e.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,f)},e.prototype.deleteKeys=function(e){for(var t=0,r=0;t<e.length;t++)this.delete(e[t])&&r++;return r},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},Object.defineProperty(e.prototype,"isFrozen",{get:function(){return this.hasOwnProperty("editRange")},enumerable:!0,configurable:!0}),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),o.prototype.where=o.prototype.filter,o.prototype.setRange=o.prototype.setPairs,o.prototype.add=o.prototype.set;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.greedyClone=function(e){return this.isShared&&!e?this:this.clone()},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,p=this.values;if(void 0!==s)for(var c=h;c<u;c++){var y=l[c],d=s(y,p[c],o++);if(void 0!==d){if(!0===i){if(y!==l[c]||!0===this.isShared)throw new Error("BTree illegally changed or cloned in editRange");d.delete?(this.keys.splice(c,1),this.values!==a&&this.values.splice(c,1),n._size--,c--,u--):d.hasOwnProperty("value")&&(p[c]=d.value)}if(void 0!==d.break)return d}}else o+=u-h;return o},e.prototype.mergeSibling=function(e,t){if(this.keys.push.apply(this.keys,e.keys),this.values===a){if(e.values===a)return;this.values=this.values.slice(0,this.keys.length)}this.values.push.apply(this.values,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.greedyClone=function(e){if(this.isShared&&!e)return this;for(var r=new t(this.children.slice(0),this.keys.slice(0)),i=0;i<r.children.length;i++)r.children[i]=r.children[i].greedyClone();return r},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(),p=this;return s(f.maxKey(),this.maxKey())>0&&(p=l,h-=this.keys.length),p.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),p=this.keys,c=this.children;if(i){if(f<=l)try{for(;f<=l;f++){c[f].isShared&&(c[f]=c[f].clone());var y=c[f].forRange(e,t,r,i,o,s,h);if(p[f]=c[f].maxKey(),"number"!=typeof y)return y;s=y}}finally{var d=o._maxNodeSize>>1;for(u>0&&u--,f=l;f>=u;f--)c[f].keys.length<=d&&this.tryMerge(f,o._maxNodeSize);0===c[0].keys.length&&(n(1===c.length&&1===p.length,"emptiness bug"),c.shift(),p.shift())}}else for(;f<=l;f++){var y=c[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=this.keys.length;this.keys.push.apply(this.keys,e.keys),this.children.push.apply(this.children,e.children),this.tryMerge(r-1,t)},t}(s),a=[],u={delete:!0},f=function(){return u},l={break:!0},p=function(){var e=new s;return e.isShared=!0,e}(),c=[],y=[];t.EmptyBTree=function(){var e=new o;return e.freeze(),e}()});
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)}}();!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=p,this._size=0,this._maxNodeSize=i>=4?Math.min(i,256):32,this._compare=t||r,e&&this.setPairs(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}),Object.defineProperty(e.prototype,"isEmpty",{get:function(){return 0===this._size},enumerable:!0,configurable:!0}),e.prototype.clear=function(){this._root=p,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.with=function(e,t,r){var i=this.clone();return i.set(e,t,r)||r?i:this},e.prototype.withPairs=function(e,t){var r=this.clone();return 0!==r.setPairs(e,t)||t?r:this},e.prototype.withKeys=function(e,t){for(var r=this.clone(),i=!1,n=0;n<e.length;n++)i=r.set(e[n],void 0,!1)||i;return t&&!i?this:r},e.prototype.without=function(e,t){return this.withoutRange(e,e,!0,t)},e.prototype.withoutKeys=function(e,t){var r=this.clone();return r.deleteKeys(e)||!t?r:this},e.prototype.withoutRange=function(e,t,r,i){var n=this.clone();return 0===n.deleteRange(e,t,r)&&i?this:n},e.prototype.filter=function(e,t){var r,i=this.greedyClone();return i.editAll(function(t,i,n){if(!e(t,i,n))return r=u}),!r&&t?this:i},e.prototype.mapValues=function(e){var t={},r=this.greedyClone();return r.editAll(function(r,i,n){return t.value=e(i,r,n),t}),r},e.prototype.reduce=function(e,t){for(var r,i=0,n=t,o=this.entries(this.minKey(),y);!(r=o.next()).done;)n=e(n,r.value,i++,this);return n},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=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,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.greedyClone=function(t){var r=new e(void 0,this._compare,this._maxNodeSize);return r._root=this._root.greedyClone(t),r._size=this._size,r},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.nextHigherPair=function(e){var t=this.entries(e,y),r=t.next();return!r.done&&this._compare(r.value[0],e)<=0&&(r=t.next()),r.value},e.prototype.nextHigherKey=function(e){var t=this.nextHigherPair(e);return t?t[0]:t},e.prototype.nextLowerPair=function(e){return this.entriesReversed(e,y,!0).next().value},e.prototype.nextLowerKey=function(e){var t=this.nextLowerPair(e);return t?t[0]:t},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.setPairs=function(e,t){for(var r=0,i=0;i<e.length;i++)this.set(e[i][0],e[i][1],t)&&r++;return r},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?p:o.children[0]}},e.prototype.editAll=function(e,t){return this.editRange(this.minKey(),this.maxKey(),!0,e,t)},e.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,f)},e.prototype.deleteKeys=function(e){for(var t=0,r=0;t<e.length;t++)this.delete(e[t])&&r++;return r},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},Object.defineProperty(e.prototype,"isFrozen",{get:function(){return this.hasOwnProperty("editRange")},enumerable:!0,configurable:!0}),e.prototype.checkValid=function(){var e=this._root.checkValid(0,this,0);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),o.prototype.where=o.prototype.filter,o.prototype.setRange=o.prototype.setPairs,o.prototype.add=o.prototype.set;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.greedyClone=function(e){return this.isShared&&!e?this:this.clone()},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,r){var i=this.keys.length,o=this.values.length;return n(this.values===a?i<=o:i===o,"keys/values length mismatch: depth",e,"with lengths",i,o,"and baseIndex",r),n(0==e||i>0,"empty leaf at depth",e,"and baseIndex",r),i},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,p=this.values;if(void 0!==s)for(var c=h;c<u;c++){var y=l[c],d=s(y,p[c],o++);if(void 0!==d){if(!0===i){if(y!==l[c]||!0===this.isShared)throw new Error("BTree illegally changed or cloned in editRange");d.delete?(this.keys.splice(c,1),this.values!==a&&this.values.splice(c,1),n._size--,c--,u--):d.hasOwnProperty("value")&&(p[c]=d.value)}if(void 0!==d.break)return d}}else o+=u-h;return o},e.prototype.mergeSibling=function(e,t){if(this.keys.push.apply(this.keys,e.keys),this.values===a){if(e.values===a)return;this.values=this.values.slice(0,this.keys.length)}this.values.push.apply(this.values,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.greedyClone=function(e){if(this.isShared&&!e)return this;for(var r=new t(this.children.slice(0),this.keys.slice(0)),i=0;i<r.children.length;i++)r.children[i]=r.children[i].greedyClone();return r},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,r){var i=this.keys.length,o=this.children.length;n(i===o,"keys/children length mismatch: depth",e,"lengths",i,o,"baseIndex",r),n(i>1||e>0,"internal node has length",i,"at depth",e,"baseIndex",r);for(var s=0,h=this.children,a=this.keys,u=0,f=0;f<o;f++)s+=h[f].checkValid(e+1,t,r+s),u+=h[f].keys.length,n(s>=u,"wtf",r),n(0===f||h[f-1].constructor===h[f].constructor,"type mismatch, baseIndex:",r),h[f].maxKey()!=a[f]&&n(!1,"keys[",f,"] =",a[f],"is wrong, should be ",h[f].maxKey(),"at depth",e,"baseIndex",r),0===f||t._compare(a[f-1],a[f])<0||n(!1,"sort violation at depth",e,"index",f,"keys",a[f-1],a[f]);var l=0===u;return(l||u>t.maxNodeSize*o)&&n(!1,l?"too few":"too many","children (",u,s,") at depth",e,"maxNodeSize:",t.maxNodeSize,"children.length:",o,"baseIndex:",r),s},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(),p=this;return s(f.maxKey(),this.maxKey())>0&&(p=l,h-=this.keys.length),p.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.keys,f=this.children,l=this.indexOf(e,0,a),p=l,c=Math.min(t===e?l:this.indexOf(t,0,a),u.length-1);if(i){if(p<=c)try{for(;p<=c;p++){f[p].isShared&&(f[p]=f[p].clone());var y=f[p].forRange(e,t,r,i,o,s,h);if(u[p]=f[p].maxKey(),"number"!=typeof y)return y;s=y}}finally{var d=o._maxNodeSize>>1;for(l>0&&l--,p=c;p>=l;p--)f[p].keys.length<=d&&(0!==f[p].keys.length?this.tryMerge(p,o._maxNodeSize):(u.splice(p,1),f.splice(p,1)));0!==f.length&&0===f[0].keys.length&&n(!1,"emptiness bug")}}else for(;p<=c;p++){var y=f[p].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=this.keys.length;this.keys.push.apply(this.keys,e.keys),this.children.push.apply(this.children,e.children),this.tryMerge(r-1,t)},t}(s),a=[],u={delete:!0},f=function(){return u},l={break:!0},p=function(){var e=new s;return e.isShared=!0,e}(),c=[],y=[];t.EmptyBTree=function(){var e=new o;return e.freeze(),e}()});
{
"name": "sorted-btree",
"version": "1.2.1",
"version": "1.2.2",
"description": "A sorted list of key-value pairs in a fast, typed in-memory B+ tree with a powerful API.",

@@ -100,3 +100,3 @@ "main": "b+tree.js",

"replace-import": [
"|./b\\+tree|$P/b+tree.min|",
"|./b\\+tree|$P/b+tree|",
"|..?|$P|",

@@ -103,0 +103,0 @@ "|..?([/\\\\].*)|$P$1|"

@@ -10,2 +10,4 @@ B+ tree

Use `npm install sorted-btree` in a terminal to install it in your npm-based project.
Features

@@ -60,3 +62,3 @@ --------

**Note:** Confusingly, the ES6 `Map.forEach(c)` method calls `c(value,key)` instead of `c(key,value)`, in contrast to other methods such as `set()` and `entries()` which put the key first. I can only assume that they reversed the order on the theory that users would usually want to examine values and ignore keys. BTree's `forEach()` therefore works the same way, but a second method `.forEachPair((key,value)=>{...})` is provided which sends you the key first and the value second; this method is slightly faster because it is the "native" for-each method for this class.
**Note:** Confusingly, the ES6 `Map.forEach(c)` method calls `c(value,key)` instead of `c(key,value)`, in contrast to other methods such as `set()` and `entries()` which put the key first. I can only assume that they reversed the order on the hypothesis that users would usually want to examine values and ignore keys. BTree's `forEach()` therefore works the same way, but there is a second method `.forEachPair((key,value)=>{...})` which sends you the key first and the value second; this method is slightly faster because it is the "native" for-each method for this class.

@@ -63,0 +65,0 @@ **Note:** Duplicate keys are not allowed (supporting duplicates properly is complex).

Sorry, the diff of this file is too big to display

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc