sorted-btree - npm Package Compare versions

Comparing version 1.2.3 to 1.2.4

b+tree.d.ts

@@ -215,3 +215,3 @@ import { ISortedMap, ISortedMapF } from './interfaces';
      *  @param highestKey Key at which to start iterating, or undefined to
-     *         start at minKey(). If the specified key doesn't exist then iteration
+     *         start at maxKey(). If the specified key doesn't exist then iteration
      *         starts at the next lower key (according to the comparator).
@@ -261,10 +261,14 @@ *  @param reusedArray Optional array used repeatedly to store key-value
     setIfNotPresent(key: K, value: V): boolean;
-    /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */
-    nextHigherPair(key: K): [K, V] | undefined;
+    /** Returns the next pair whose key is larger than the specified key (or undefined if there is none).
+     *  If key === undefined, this function returns the lowest pair.
+     */
+    nextHigherPair(key: K | undefined): [K, V] | undefined;
     /** Returns the next key larger than the specified key (or undefined if there is none) */
-    nextHigherKey(key: K): K | undefined;
-    /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */
-    nextLowerPair(key: K): [K, V] | undefined;
+    nextHigherKey(key: K | undefined): K | undefined;
+    /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none).
+     *  If key === undefined, this function returns the highest pair.
+     */
+    nextLowerPair(key: K | undefined): [K, V] | undefined;
     /** Returns the next key smaller than the specified key (or undefined if there is none) */
-    nextLowerKey(key: K): K | undefined;
+    nextLowerKey(key: K | undefined): K | undefined;
     /** Edits the value associated with a key in the tree, if it already exists.
@@ -271,0 +275,0 @@ * @returns true if the key existed, false if not.

b+tree.min.js

@@ -1,1 +0,1 @@
-var __extends=this&&this.__extends||function(){var i=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(e,t){function r(){this.constructor=e}i(e,t),e.prototype=null===t?Object.create(t):(r.prototype=t.prototype,new r)}}();!function(e){"object"==typeof module&&"object"==typeof module.exports?e(require,exports):"function"==typeof define&&define.amd&&define(["require","exports"],e)}(function(e,t){"use strict";function i(e,t){var r=e-t;return r==r?r:(e=e&&e.valueOf())<(t=t&&t.valueOf())?-1:t<e?1:e==t?0:r}Object.defineProperty(t,"__esModule",{value:!0}),t.defaultComparator=i;var r=(Object.defineProperty(n.prototype,"size",{get:function(){return this._size},enumerable:!0,configurable:!0}),Object.defineProperty(n.prototype,"length",{get:function(){return this._size},enumerable:!0,configurable:!0}),Object.defineProperty(n.prototype,"isEmpty",{get:function(){return 0===this._size},enumerable:!0,configurable:!0}),n.prototype.clear=function(){this._root=g,this._size=0},n.prototype.forEach=function(r,e){var i=this;return void 0!==e&&(r=r.bind(e)),this.forEachPair(function(e,t){return r(t,e,i)})},n.prototype.forEachPair=function(e,t){var r=this.minKey(),i=this.maxKey();return this.forRange(r,i,!0,e,t)},n.prototype.get=function(e,t){return this._root.get(e,t,this)},n.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 a([this._root,i]),!0)},n.prototype.has=function(e){return 0!==this.forRange(e,e,!0,void 0)},n.prototype.delete=function(e){return 0!==this.editRange(e,e,!0,y)},n.prototype.with=function(e,t,r){var i=this.clone();return i.set(e,t,r)||r?i:this},n.prototype.withPairs=function(e,t){var r=this.clone();return 0!==r.setPairs(e,t)||t?r:this},n.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},n.prototype.without=function(e,t){return this.withoutRange(e,e,!0,t)},n.prototype.withoutKeys=function(e,t){var r=this.clone();return r.deleteKeys(e)||!t?r:this},n.prototype.withoutRange=function(e,t,r,i){var n=this.clone();return 0===n.deleteRange(e,t,r)&&i?this:n},n.prototype.filter=function(i,e){var n,t=this.greedyClone();return t.editAll(function(e,t,r){if(!i(e,t,r))return n=c}),!n&&e?this:t},n.prototype.mapValues=function(i){var n={},e=this.greedyClone();return e.editAll(function(e,t,r){return n.value=i(t,e,r),n}),e},n.prototype.reduce=function(e,t){for(var r,i=0,n=t,o=this.entries(this.minKey(),k);!(r=o.next()).done;)n=e(n,r.value,i++,this);return n},n.prototype.entries=function(e,t){var r=this.findPath(e);if(void 0===r)return u();var i=r.nodequeue,n=r.nodeindex,o=r.leaf,s=void 0!==t?1:0,h=void 0===e?-1:o.indexOf(e,0,this._compare)-1;return u(function(){e:for(;;)switch(s){case 0:if(++h<o.keys.length)return{done:!1,value:[o.keys[h],o.values[h]]};s=2;continue;case 1:if(++h<o.keys.length)return t[0]=o.keys[h],t[1]=o.values[h],{done:!1,value:t};s=2;case 2:for(var e=-1;;){if(++e>=i.length){s=3;continue e}if(++n[e]<i[e].length)break}for(;0<e;e--)i[e-1]=i[e][n[e]].children,n[e-1]=0;o=i[0][n[0]],h=-1,s=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},n.prototype.entriesReversed=function(e,t,r){if(void 0===(e=e||this.maxKey()))return u();var i=this.findPath(e)||this.findPath(this.maxKey()),n=i.nodequeue,o=i.nodeindex,s=i.leaf;x(!n[0]||s===n[0][o[0]],"wat!");var h=s.indexOf(e,0,this._compare);r||0<this._compare(s.keys[h],e)||h++;var a=void 0!==t?1:0;return u(function(){e:for(;;)switch(a){case 0:if(0<=--h)return{done:!1,value:[s.keys[h],s.values[h]]};a=2;continue;case 1:if(0<=--h)return t[0]=s.keys[h],t[1]=s.values[h],{done:!1,value:t};a=2;case 2:for(var e=-1;;){if(++e>=n.length){a=3;continue e}if(0<=--o[e])break}for(;0<e;e--)n[e-1]=n[e][o[e]].children,o[e-1]=n[e-1].length-1;s=n[0][o[0]],h=s.keys.length,a=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},n.prototype.findPath=function(e){var t,r,i=this._root;if(i.isLeaf)r=t=m;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}},n.prototype.keys=function(e){var t=this.entries(e,k);return u(function(){var e=t.next();return e.value&&(e.value=e.value[0]),e})},n.prototype.values=function(e){var t=this.entries(e,k);return u(function(){var e=t.next();return e.value&&(e.value=e.value[1]),e})},Object.defineProperty(n.prototype,"maxNodeSize",{get:function(){return this._maxNodeSize},enumerable:!0,configurable:!0}),n.prototype.minKey=function(){return this._root.minKey()},n.prototype.maxKey=function(){return this._root.maxKey()},n.prototype.clone=function(){this._root.isShared=!0;var e=new n(void 0,this._compare,this._maxNodeSize);return e._root=this._root,e._size=this._size,e},n.prototype.greedyClone=function(e){var t=new n(void 0,this._compare,this._maxNodeSize);return t._root=this._root.greedyClone(e),t._size=this._size,t},n.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):[]},n.prototype.keysArray=function(){var r=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(e,t){r.push(e)}),r},n.prototype.valuesArray=function(){var r=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(e,t){r.push(t)}),r},n.prototype.toString=function(){return this.toArray().toString()},n.prototype.setIfNotPresent=function(e,t){return this.set(e,t,!1)},n.prototype.nextHigherPair=function(e){var t=this.entries(e,k),r=t.next();return!r.done&&this._compare(r.value[0],e)<=0&&(r=t.next()),r.value},n.prototype.nextHigherKey=function(e){var t=this.nextHigherPair(e);return t?t[0]:t},n.prototype.nextLowerPair=function(e){return this.entriesReversed(e,k,!0).next().value},n.prototype.nextLowerKey=function(e){var t=this.nextLowerPair(e);return t?t[0]:t},n.prototype.changeIfPresent=function(e,r){return 0!==this.editRange(e,e,!0,function(e,t){return{value:r}})},n.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?v:void 0}),n},n.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},n.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},n.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?g:o.children[0]}},n.prototype.editAll=function(e,t){return this.editRange(this.minKey(),this.maxKey(),!0,e,t)},n.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,y)},n.prototype.deleteKeys=function(e){for(var t=0,r=0;t<e.length;t++)this.delete(e[t])&&r++;return r},Object.defineProperty(n.prototype,"height",{get:function(){for(var e=this._root,t=-1;null!=e;t++)e=e.children;return t},enumerable:!0,configurable:!0}),n.prototype.freeze=function(){this.clear=this.set=this.editRange=function(){throw new Error("Attempted to modify a frozen BTree")}},n.prototype.unfreeze=function(){delete this.clear,delete this.set,delete this.editRange},Object.defineProperty(n.prototype,"isFrozen",{get:function(){return this.hasOwnProperty("editRange")},enumerable:!0,configurable:!0}),n.prototype.checkValid=function(){var e=this._root.checkValid(0,this,0);x(e===this.size,"size mismatch: counted ",e,"but stored",this.size)},n);function n(e,t,r){this._root=g,this._size=0,this._maxNodeSize=4<=r?Math.min(r,256):32,this._compare=t||i,e&&this.setPairs(e)}function u(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}t.default=r,Symbol&&Symbol.iterator&&(r.prototype[Symbol.iterator]=r.prototype.entries),r.prototype.where=r.prototype.filter,r.prototype.setRange=r.prototype.setPairs,r.prototype.add=r.prototype.set;var o=(Object.defineProperty(s.prototype,"isLeaf",{get:function(){return void 0===this.children},enumerable:!0,configurable:!0}),s.prototype.maxKey=function(){return this.keys[this.keys.length-1]},s.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(!(0<h)){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},s.prototype.minKey=function(){return this.keys[0]},s.prototype.clone=function(){var e=this.values;return new s(this.keys.slice(0),e===d?e:e.slice(0))},s.prototype.greedyClone=function(e){return this.isShared&&!e?this:this.clone()},s.prototype.get=function(e,t,r){var i=this.indexOf(e,-1,r._compare);return i<0?t:this.values[i]},s.prototype.checkValid=function(e,t,r){var i=this.keys.length,n=this.values.length;return x(this.values===d?i<=n:i===n,"keys/values length mismatch: depth",e,"with lengths",i,n,"and baseIndex",r),x(0==e||0<i,"empty leaf at depth",e,"and baseIndex",r),i},s.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},s.prototype.reifyValues=function(){return this.values===d?this.values=this.values.slice(0,this.keys.length):this.values},s.prototype.insertInLeaf=function(e,t,r,i){if(this.keys.splice(e,0,t),this.values===d){for(;d.length<i._maxNodeSize;)d.push(void 0);if(void 0===r)return!0;this.values=d.slice(0,this.keys.length-1)}return this.values.splice(e,0,r),!0},s.prototype.takeFromRight=function(e){var t=this.values;e.values===d?t!==d&&t.push(void 0):(t=this.reifyValues()).push(e.values.shift()),this.keys.push(e.keys.shift())},s.prototype.takeFromLeft=function(e){var t=this.values;e.values===d?t!==d&&t.unshift(void 0):(t=this.reifyValues()).unshift(e.values.pop()),this.keys.unshift(e.keys.pop())},s.prototype.splitOffRightSide=function(){var e=this.keys.length>>1;return new s(this.keys.splice(e),this.values===d?d:this.values.splice(e))},s.prototype.forRange=function(e,t,r,i,n,o,s){var h,a,u=n._compare;if(t===e){if(!r)return o;if(a=(h=this.indexOf(e,-1,u))+1,h<0)return o}else h=this.indexOf(e,0,u),(a=this.indexOf(t,-1,u))<0?a=~a:!0===r&&a++;var l=this.keys,f=this.values;if(void 0!==s)for(var p=h;p<a;p++){var c=l[p],y=s(c,f[p],o++);if(void 0!==y){if(!0===i){if(c!==l[p]||!0===this.isShared)throw new Error("BTree illegally changed or cloned in editRange");y.delete?(this.keys.splice(p,1),this.values!==d&&this.values.splice(p,1),n._size--,p--,a--):y.hasOwnProperty("value")&&(f[p]=y.value)}if(void 0!==y.break)return y}}else o+=a-h;return o},s.prototype.mergeSibling=function(e,t){if(this.keys.push.apply(this.keys,e.keys),this.values===d){if(e.values===d)return;this.values=this.values.slice(0,this.keys.length)}this.values.push.apply(this.values,e.reifyValues())},s);function s(e,t){void 0===e&&(e=[]),this.keys=e,this.values=t||d,this.isShared=void 0}var h,a=(__extends(l,h=o),l.prototype.clone=function(){for(var e=this.children.slice(0),t=0;t<e.length;t++)e[t].isShared=!0;return new l(e,this.keys.slice(0))},l.prototype.greedyClone=function(e){if(this.isShared&&!e)return this;for(var t=new l(this.children.slice(0),this.keys.slice(0)),r=0;r<t.children.length;r++)t.children[r]=t.children[r].greedyClone();return t},l.prototype.minKey=function(){return this.children[0].minKey()},l.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},l.prototype.checkValid=function(e,t,r){var i=this.keys.length,n=this.children.length;x(i===n,"keys/children length mismatch: depth",e,"lengths",i,n,"baseIndex",r),x(1<i||0<e,"internal node has length",i,"at depth",e,"baseIndex",r);for(var o=0,s=this.children,h=this.keys,a=0,u=0;u<n;u++)o+=s[u].checkValid(e+1,t,r+o),x((a+=s[u].keys.length)<=o,"wtf",r),x(0===u||s[u-1].constructor===s[u].constructor,"type mismatch, baseIndex:",r),s[u].maxKey()!=h[u]&&x(!1,"keys[",u,"] =",h[u],"is wrong, should be ",s[u].maxKey(),"at depth",e,"baseIndex",r),0===u||t._compare(h[u-1],h[u])<0||x(!1,"sort violation at depth",e,"index",u,"keys",h[u-1],h[u]);var l=0===a;return(l||a>t.maxNodeSize*n)&&x(!1,l?"too few":"too many","children (",a,o,") at depth",e,"maxNodeSize:",t.maxNodeSize,"children.length:",n,"baseIndex:",r),o},l.prototype.set=function(e,t,r,i){var n,o=this.children,s=i._maxNodeSize,h=i._compare,a=Math.min(this.indexOf(e,0,h),o.length-1),u=o[a];u.isShared&&(o[a]=u=u.clone()),u.keys.length>=s&&(0<a&&(n=o[a-1]).keys.length<s&&h(u.keys[0],e)<0?(n.isShared&&(o[a-1]=n=n.clone()),n.takeFromRight(u),this.keys[a-1]=n.maxKey()):void 0!==(n=o[a+1])&&n.keys.length<s&&h(u.maxKey(),e)<0&&(n.isShared&&(o[a+1]=n=n.clone()),n.takeFromLeft(u),this.keys[a]=o[a].maxKey()));var l=u.set(e,t,r,i);if(!1===l)return!1;if(this.keys[a]=u.maxKey(),!0===l)return!0;if(this.keys.length<s)return this.insert(a+1,l),!0;var f=this.splitOffRightSide(),p=this;return 0<h(l.maxKey(),this.maxKey())&&(p=f,a-=this.keys.length),p.insert(a+1,l),f},l.prototype.insert=function(e,t){this.children.splice(e,0,t),this.keys.splice(e,0,t.maxKey())},l.prototype.splitOffRightSide=function(){var e=this.children.length>>1;return new l(this.children.splice(e),this.keys.splice(e))},l.prototype.takeFromRight=function(e){this.keys.push(e.keys.shift()),this.children.push(e.children.shift())},l.prototype.takeFromLeft=function(e){this.keys.unshift(e.keys.pop()),this.children.unshift(e.children.pop())},l.prototype.forRange=function(e,t,r,i,n,o,s){var h=n._compare,a=this.keys,u=this.children,l=this.indexOf(e,0,h),f=l,p=Math.min(t===e?l:this.indexOf(t,0,h),a.length-1);if(i){if(f<=p)try{for(;f<=p;f++){u[f].isShared&&(u[f]=u[f].clone());var c=u[f].forRange(e,t,r,i,n,o,s);if(a[f]=u[f].maxKey(),"number"!=typeof c)return c;o=c}}finally{var y=n._maxNodeSize>>1;for(0<l&&l--,f=p;l<=f;f--)u[f].keys.length<=y&&(0!==u[f].keys.length?this.tryMerge(f,n._maxNodeSize):(a.splice(f,1),u.splice(f,1)));0!==u.length&&0===u[0].keys.length&&x(!1,"emptiness bug")}}else for(;f<=p;f++){if("number"!=typeof(c=u[f].forRange(e,t,r,i,n,o,s)))return c;o=c}return o},l.prototype.tryMerge=function(e,t){var r=this.children;return 0<=e&&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)},l.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)},l);function l(e,t){var r=this;if(!t){t=[];for(var i=0;i<e.length;i++)t[i]=e[i].maxKey()}return(r=h.call(this,t)||this).children=e,r}var f,p,d=[],c={delete:!0},y=function(){return c},v={break:!0},g=((f=new o).isShared=!0,f),m=[],k=[];function x(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(" "))}t.EmptyBTree=((p=new r).freeze(),p)});
+var __extends=this&&this.__extends||function(){var i=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(e,t){function r(){this.constructor=e}i(e,t),e.prototype=null===t?Object.create(t):(r.prototype=t.prototype,new r)}}();!function(e){"object"==typeof module&&"object"==typeof module.exports?e(require,exports):"function"==typeof define&&define.amd&&define(["require","exports"],e)}(function(e,t){"use strict";function i(e,t){var r=e-t;return r==r?r:(e=e&&e.valueOf())<(t=t&&t.valueOf())?-1:t<e?1:e==t?0:r}Object.defineProperty(t,"__esModule",{value:!0}),t.defaultComparator=i;var r=(Object.defineProperty(n.prototype,"size",{get:function(){return this._size},enumerable:!0,configurable:!0}),Object.defineProperty(n.prototype,"length",{get:function(){return this._size},enumerable:!0,configurable:!0}),Object.defineProperty(n.prototype,"isEmpty",{get:function(){return 0===this._size},enumerable:!0,configurable:!0}),n.prototype.clear=function(){this._root=g,this._size=0},n.prototype.forEach=function(r,e){var i=this;return void 0!==e&&(r=r.bind(e)),this.forEachPair(function(e,t){return r(t,e,i)})},n.prototype.forEachPair=function(e,t){var r=this.minKey(),i=this.maxKey();return this.forRange(r,i,!0,e,t)},n.prototype.get=function(e,t){return this._root.get(e,t,this)},n.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 a([this._root,i]),!0)},n.prototype.has=function(e){return 0!==this.forRange(e,e,!0,void 0)},n.prototype.delete=function(e){return 0!==this.editRange(e,e,!0,y)},n.prototype.with=function(e,t,r){var i=this.clone();return i.set(e,t,r)||r?i:this},n.prototype.withPairs=function(e,t){var r=this.clone();return 0!==r.setPairs(e,t)||t?r:this},n.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},n.prototype.without=function(e,t){return this.withoutRange(e,e,!0,t)},n.prototype.withoutKeys=function(e,t){var r=this.clone();return r.deleteKeys(e)||!t?r:this},n.prototype.withoutRange=function(e,t,r,i){var n=this.clone();return 0===n.deleteRange(e,t,r)&&i?this:n},n.prototype.filter=function(i,e){var n,t=this.greedyClone();return t.editAll(function(e,t,r){if(!i(e,t,r))return n=c}),!n&&e?this:t},n.prototype.mapValues=function(i){var n={},e=this.greedyClone();return e.editAll(function(e,t,r){return n.value=i(t,e,r),n}),e},n.prototype.reduce=function(e,t){for(var r,i=0,n=t,o=this.entries(this.minKey(),k);!(r=o.next()).done;)n=e(n,r.value,i++,this);return n},n.prototype.entries=function(e,t){var r=this.findPath(e);if(void 0===r)return u();var i=r.nodequeue,n=r.nodeindex,o=r.leaf,s=void 0!==t?1:0,h=void 0===e?-1:o.indexOf(e,0,this._compare)-1;return u(function(){e:for(;;)switch(s){case 0:if(++h<o.keys.length)return{done:!1,value:[o.keys[h],o.values[h]]};s=2;continue;case 1:if(++h<o.keys.length)return t[0]=o.keys[h],t[1]=o.values[h],{done:!1,value:t};s=2;case 2:for(var e=-1;;){if(++e>=i.length){s=3;continue e}if(++n[e]<i[e].length)break}for(;0<e;e--)i[e-1]=i[e][n[e]].children,n[e-1]=0;o=i[0][n[0]],h=-1,s=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},n.prototype.entriesReversed=function(e,t,r){if(void 0===e&&(r=void 0)===(e=this.maxKey()))return u();var i=this.findPath(e)||this.findPath(this.maxKey()),n=i.nodequeue,o=i.nodeindex,s=i.leaf;x(!n[0]||s===n[0][o[0]],"wat!");var h=s.indexOf(e,0,this._compare);r||0<this._compare(s.keys[h],e)||h++;var a=void 0!==t?1:0;return u(function(){e:for(;;)switch(a){case 0:if(0<=--h)return{done:!1,value:[s.keys[h],s.values[h]]};a=2;continue;case 1:if(0<=--h)return t[0]=s.keys[h],t[1]=s.values[h],{done:!1,value:t};a=2;case 2:for(var e=-1;;){if(++e>=n.length){a=3;continue e}if(0<=--o[e])break}for(;0<e;e--)n[e-1]=n[e][o[e]].children,o[e-1]=n[e-1].length-1;s=n[0][o[0]],h=s.keys.length,a=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},n.prototype.findPath=function(e){var t,r,i=this._root;if(i.isLeaf)r=t=m;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}},n.prototype.keys=function(e){var t=this.entries(e,k);return u(function(){var e=t.next();return e.value&&(e.value=e.value[0]),e})},n.prototype.values=function(e){var t=this.entries(e,k);return u(function(){var e=t.next();return e.value&&(e.value=e.value[1]),e})},Object.defineProperty(n.prototype,"maxNodeSize",{get:function(){return this._maxNodeSize},enumerable:!0,configurable:!0}),n.prototype.minKey=function(){return this._root.minKey()},n.prototype.maxKey=function(){return this._root.maxKey()},n.prototype.clone=function(){this._root.isShared=!0;var e=new n(void 0,this._compare,this._maxNodeSize);return e._root=this._root,e._size=this._size,e},n.prototype.greedyClone=function(e){var t=new n(void 0,this._compare,this._maxNodeSize);return t._root=this._root.greedyClone(e),t._size=this._size,t},n.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):[]},n.prototype.keysArray=function(){var r=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(e,t){r.push(e)}),r},n.prototype.valuesArray=function(){var r=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(e,t){r.push(t)}),r},n.prototype.toString=function(){return this.toArray().toString()},n.prototype.setIfNotPresent=function(e,t){return this.set(e,t,!1)},n.prototype.nextHigherPair=function(e){var t=this.entries(e,k),r=t.next();return!r.done&&void 0!==e&&this._compare(r.value[0],e)<=0&&(r=t.next()),r.value},n.prototype.nextHigherKey=function(e){var t=this.nextHigherPair(e);return t?t[0]:t},n.prototype.nextLowerPair=function(e){return this.entriesReversed(e,k,!0).next().value},n.prototype.nextLowerKey=function(e){var t=this.nextLowerPair(e);return t?t[0]:t},n.prototype.changeIfPresent=function(e,r){return 0!==this.editRange(e,e,!0,function(e,t){return{value:r}})},n.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?v:void 0}),n},n.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},n.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},n.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?g:o.children[0]}},n.prototype.editAll=function(e,t){return this.editRange(this.minKey(),this.maxKey(),!0,e,t)},n.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,y)},n.prototype.deleteKeys=function(e){for(var t=0,r=0;t<e.length;t++)this.delete(e[t])&&r++;return r},Object.defineProperty(n.prototype,"height",{get:function(){for(var e=this._root,t=-1;null!=e;t++)e=e.children;return t},enumerable:!0,configurable:!0}),n.prototype.freeze=function(){this.clear=this.set=this.editRange=function(){throw new Error("Attempted to modify a frozen BTree")}},n.prototype.unfreeze=function(){delete this.clear,delete this.set,delete this.editRange},Object.defineProperty(n.prototype,"isFrozen",{get:function(){return this.hasOwnProperty("editRange")},enumerable:!0,configurable:!0}),n.prototype.checkValid=function(){var e=this._root.checkValid(0,this,0);x(e===this.size,"size mismatch: counted ",e,"but stored",this.size)},n);function n(e,t,r){this._root=g,this._size=0,this._maxNodeSize=4<=r?Math.min(r,256):32,this._compare=t||i,e&&this.setPairs(e)}function u(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}t.default=r,Symbol&&Symbol.iterator&&(r.prototype[Symbol.iterator]=r.prototype.entries),r.prototype.where=r.prototype.filter,r.prototype.setRange=r.prototype.setPairs,r.prototype.add=r.prototype.set;var o=(Object.defineProperty(s.prototype,"isLeaf",{get:function(){return void 0===this.children},enumerable:!0,configurable:!0}),s.prototype.maxKey=function(){return this.keys[this.keys.length-1]},s.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(!(0<h)){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},s.prototype.minKey=function(){return this.keys[0]},s.prototype.clone=function(){var e=this.values;return new s(this.keys.slice(0),e===d?e:e.slice(0))},s.prototype.greedyClone=function(e){return this.isShared&&!e?this:this.clone()},s.prototype.get=function(e,t,r){var i=this.indexOf(e,-1,r._compare);return i<0?t:this.values[i]},s.prototype.checkValid=function(e,t,r){var i=this.keys.length,n=this.values.length;return x(this.values===d?i<=n:i===n,"keys/values length mismatch: depth",e,"with lengths",i,n,"and baseIndex",r),x(0==e||0<i,"empty leaf at depth",e,"and baseIndex",r),i},s.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},s.prototype.reifyValues=function(){return this.values===d?this.values=this.values.slice(0,this.keys.length):this.values},s.prototype.insertInLeaf=function(e,t,r,i){if(this.keys.splice(e,0,t),this.values===d){for(;d.length<i._maxNodeSize;)d.push(void 0);if(void 0===r)return!0;this.values=d.slice(0,this.keys.length-1)}return this.values.splice(e,0,r),!0},s.prototype.takeFromRight=function(e){var t=this.values;e.values===d?t!==d&&t.push(void 0):(t=this.reifyValues()).push(e.values.shift()),this.keys.push(e.keys.shift())},s.prototype.takeFromLeft=function(e){var t=this.values;e.values===d?t!==d&&t.unshift(void 0):(t=this.reifyValues()).unshift(e.values.pop()),this.keys.unshift(e.keys.pop())},s.prototype.splitOffRightSide=function(){var e=this.keys.length>>1;return new s(this.keys.splice(e),this.values===d?d:this.values.splice(e))},s.prototype.forRange=function(e,t,r,i,n,o,s){var h,a,u=n._compare;if(t===e){if(!r)return o;if(a=(h=this.indexOf(e,-1,u))+1,h<0)return o}else h=this.indexOf(e,0,u),(a=this.indexOf(t,-1,u))<0?a=~a:!0===r&&a++;var l=this.keys,f=this.values;if(void 0!==s)for(var p=h;p<a;p++){var c=l[p],y=s(c,f[p],o++);if(void 0!==y){if(!0===i){if(c!==l[p]||!0===this.isShared)throw new Error("BTree illegally changed or cloned in editRange");y.delete?(this.keys.splice(p,1),this.values!==d&&this.values.splice(p,1),n._size--,p--,a--):y.hasOwnProperty("value")&&(f[p]=y.value)}if(void 0!==y.break)return y}}else o+=a-h;return o},s.prototype.mergeSibling=function(e,t){if(this.keys.push.apply(this.keys,e.keys),this.values===d){if(e.values===d)return;this.values=this.values.slice(0,this.keys.length)}this.values.push.apply(this.values,e.reifyValues())},s);function s(e,t){void 0===e&&(e=[]),this.keys=e,this.values=t||d,this.isShared=void 0}var h,a=(__extends(l,h=o),l.prototype.clone=function(){for(var e=this.children.slice(0),t=0;t<e.length;t++)e[t].isShared=!0;return new l(e,this.keys.slice(0))},l.prototype.greedyClone=function(e){if(this.isShared&&!e)return this;for(var t=new l(this.children.slice(0),this.keys.slice(0)),r=0;r<t.children.length;r++)t.children[r]=t.children[r].greedyClone();return t},l.prototype.minKey=function(){return this.children[0].minKey()},l.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},l.prototype.checkValid=function(e,t,r){var i=this.keys.length,n=this.children.length;x(i===n,"keys/children length mismatch: depth",e,"lengths",i,n,"baseIndex",r),x(1<i||0<e,"internal node has length",i,"at depth",e,"baseIndex",r);for(var o=0,s=this.children,h=this.keys,a=0,u=0;u<n;u++)o+=s[u].checkValid(e+1,t,r+o),x((a+=s[u].keys.length)<=o,"wtf",r),x(0===u||s[u-1].constructor===s[u].constructor,"type mismatch, baseIndex:",r),s[u].maxKey()!=h[u]&&x(!1,"keys[",u,"] =",h[u],"is wrong, should be ",s[u].maxKey(),"at depth",e,"baseIndex",r),0===u||t._compare(h[u-1],h[u])<0||x(!1,"sort violation at depth",e,"index",u,"keys",h[u-1],h[u]);var l=0===a;return(l||a>t.maxNodeSize*n)&&x(!1,l?"too few":"too many","children (",a,o,") at depth",e,"maxNodeSize:",t.maxNodeSize,"children.length:",n,"baseIndex:",r),o},l.prototype.set=function(e,t,r,i){var n,o=this.children,s=i._maxNodeSize,h=i._compare,a=Math.min(this.indexOf(e,0,h),o.length-1),u=o[a];u.isShared&&(o[a]=u=u.clone()),u.keys.length>=s&&(0<a&&(n=o[a-1]).keys.length<s&&h(u.keys[0],e)<0?(n.isShared&&(o[a-1]=n=n.clone()),n.takeFromRight(u),this.keys[a-1]=n.maxKey()):void 0!==(n=o[a+1])&&n.keys.length<s&&h(u.maxKey(),e)<0&&(n.isShared&&(o[a+1]=n=n.clone()),n.takeFromLeft(u),this.keys[a]=o[a].maxKey()));var l=u.set(e,t,r,i);if(!1===l)return!1;if(this.keys[a]=u.maxKey(),!0===l)return!0;if(this.keys.length<s)return this.insert(a+1,l),!0;var f=this.splitOffRightSide(),p=this;return 0<h(l.maxKey(),this.maxKey())&&(p=f,a-=this.keys.length),p.insert(a+1,l),f},l.prototype.insert=function(e,t){this.children.splice(e,0,t),this.keys.splice(e,0,t.maxKey())},l.prototype.splitOffRightSide=function(){var e=this.children.length>>1;return new l(this.children.splice(e),this.keys.splice(e))},l.prototype.takeFromRight=function(e){this.keys.push(e.keys.shift()),this.children.push(e.children.shift())},l.prototype.takeFromLeft=function(e){this.keys.unshift(e.keys.pop()),this.children.unshift(e.children.pop())},l.prototype.forRange=function(e,t,r,i,n,o,s){var h=n._compare,a=this.keys,u=this.children,l=this.indexOf(e,0,h),f=l,p=Math.min(t===e?l:this.indexOf(t,0,h),a.length-1);if(i){if(f<=p)try{for(;f<=p;f++){u[f].isShared&&(u[f]=u[f].clone());var c=u[f].forRange(e,t,r,i,n,o,s);if(a[f]=u[f].maxKey(),"number"!=typeof c)return c;o=c}}finally{var y=n._maxNodeSize>>1;for(0<l&&l--,f=p;l<=f;f--)u[f].keys.length<=y&&(0!==u[f].keys.length?this.tryMerge(f,n._maxNodeSize):(a.splice(f,1),u.splice(f,1)));0!==u.length&&0===u[0].keys.length&&x(!1,"emptiness bug")}}else for(;f<=p;f++){if("number"!=typeof(c=u[f].forRange(e,t,r,i,n,o,s)))return c;o=c}return o},l.prototype.tryMerge=function(e,t){var r=this.children;return 0<=e&&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)},l.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)},l);function l(e,t){var r=this;if(!t){t=[];for(var i=0;i<e.length;i++)t[i]=e[i].maxKey()}return(r=h.call(this,t)||this).children=e,r}var f,p,d=[],c={delete:!0},y=function(){return c},v={break:!0},g=((f=new o).isShared=!0,f),m=[],k=[];function x(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(" "))}t.EmptyBTree=((p=new r).freeze(),p)});

package.json

 {
   "name": "sorted-btree",
-  "version": "1.2.3",
+  "version": "1.2.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

@@ -375,2 +375,6 @@ B+ tree
 
+### v1.2.4 ###
+
+- Issue #9 fixed: `nextLowerPair(0)` was being treated like `nextLowerPair(undefined)`, and `nextLowerPair(undefined)` was returning the second-highest pair when it should have returned the highest pair.
+
 ### v1.2.3 ###
@@ -377,0 +381,0 @@

No alert changes

Improved metrics

Total package byte prevSize

154740

increased by0.5%

Lines of code

2023

increased by0.6%

Number of lines in readme file

415

increased by0.97%

No dependency changes