ibtree - npm Package Compare versions

Comparing version 0.2.0 to 0.3.0

dist/ibtree.js

@@ -1,1 +0,1 @@
-var ibtree=function(t){function e(i){if(r[i])return r[i].exports;var n=r[i]={exports:{},id:i,loaded:!1};return t[i].call(n.exports,n,n.exports,e),n.loaded=!0,n.exports}var r={};return e.m=t,e.c=r,e.p="",e(0)}([function(t,e,r){"use strict";function i(t){return t&&t.__esModule?t:{"default":t}}function n(t){if(Array.isArray(t)){for(var e=0,r=Array(t.length);e<t.length;e++)r[e]=t[e];return r}return Array.from(t)}function h(t){var e=t||{};this.order=p.ORDER,this.isSet=void 0===e.isSet?!1:e.isSet,this.extractor=e.extractor,this.comparator=e.comparator||_,this.root=e.root||new d.Leaf({order:this.order}),this.size=e.size||0,this.height=e.height||0,this.ownerID=e.ownerID}function s(t,e,r){var i=e||{},n=p.ORDER,h=1,s=p.LEAF_MIN_CHILDREN+h,o=p.LEAF_MAX_CHILDREN,a=p.INTERNAL_MIN_CHILDREN,u=p.INTERNAL_MAX_CHILDREN,l=(0,y.boundedChunk)(s,o,t),c=(0,y.fastMap)(function(t){var e=void 0;e=r?(0,y.fastMap)(function(t){return i.extractor?i.extractor(t[0]):t[0]},t):i.extractor?(0,y.fastMap)(i.extractor,t):t;var h=r?(0,y.fastMap)(function(t){return t[1]},t):t;return new d.Leaf({order:n,keys:e,children:h})},l),f=0,v=null,g=!1;if(1===c.length)v=c[0];else{for(var I=c,_=function(){var t=(0,y.boundedChunk)(a+h,u,I),e=!0,r=(0,y.fastMap)(function(t){var r=g?function(t){var e=t.keys[0];return t.keys=(0,y.tail)(null,t.keys),e}:function(t){return t.keys[0]},i=e?(0,y.tail)(null,t):t,h=(0,y.fastMap)(r,i);return e=!1,new d.InternalNode({order:n,keys:h,children:t})},t);return 0===r.length?"break":(I=r,g=!0,void f++)};I.length>1;){var k=_();if("break"===k)break}v=I[0]}var w=this;return new w((0,y.extend)({},i,{root:v,size:t.length,height:f}))}function o(t,e){return s.call(this,t,e,!0)}function a(t,e){return s.call(this,t,e,!1)}function u(t){var e=t||{};e.isSet=!0,h.call(this,e)}Object.defineProperty(e,"__esModule",{value:!0}),e.BTMap=e.defaultComparator=void 0,e.BPlusTree=h,e.BTSet=u;var l=r(1),c=i(l),d=r(2),f=r(5),v=i(f),y=r(4),p=r(3),g=c["default"].eq,I={},_=e.defaultComparator=function(t,e){return t===e?0:e>t?-1:1},k=function(t,e){return t.children[e]},w=function(t,e){return t.keys[e]},E=function(t,e){return[w(t,e),k(t,e)]};(0,y.extend)(h.prototype,{has:function(t){return this.search(this.comparator,t)!==I},add:function(t){return this.set(t,t)},get:function(t){var e=this.search(this.comparator,t);return e===I?void 0:e},clear:function(){return new this.constructor({comparator:this.comparator,extractor:this.extractor})},set:function(t,e){var r=this.comparator,i=this.extractor?this.extractor(t):t,n=(0,y.makeRef)(!1),h=this.root.insert(r,this.ownerID,n,i,e);if(!(0,y.isSet)(n))return this;var s=void 0,o=!1,a=!!this.ownerID;if(3===h.length){o=!0;var u=h,l=u[0],c=u[1],f=u[2],v=(0,y.tagOwnerID)([l],this.ownerID),p=(0,y.tagOwnerID)([c,f],this.ownerID);s=new d.InternalNode({order:this.order,keys:v,children:p})}else s=h;var g=o?this.height+1:this.height,I=this.size+1;return a?(this.height=g,this.size=I,this.root=s,this._didAlter=!0,this):new this.constructor({extractor:this.extractor,comparator:this.comparator,root:s,height:g,size:I,ownerID:this.ownerID})},"delete":function(t){var e=(0,y.makeRef)(!1),r=this.root["delete"](this.comparator,this.ownerID,e,t);if(!(0,y.isSet)(e))return this;var i=!1;if(r.size<p.MIN_ROOT_CHILDREN){var n=r.constructor===d.Leaf;n||(r=r.children[0],i=!0)}var h=!!this.ownerID,s=void 0,o=i?this.height-1:this.height,a=this.size-1;return h?(s=this,this.root=r,this.height=o,this.size=a,this._didAlter=!0):s=new this.constructor({comparator:this.comparator,extractor:this.extractor,root:r,height:o,size:a,ownerID:this.ownerID}),s},asMutable:function(){return this.ownerID?this:new this.constructor({comparator:this.comparator,extractor:this.extractor,root:this.root,height:this.height,size:this.size,ownerID:(0,y.makeOwnerID)()})},asImmutable:function(){return this.ownerID?new this.constructor({comparator:this.comparator,extractor:this.extractor,root:this.root,height:this.height,size:this.size}):this},withMutations:function(t){var e=this.asMutable();return t(e),e._didAlter?e.asImmutable():this},_baseBetween:function(t,e,r){if(0===this.size)return(0,y.getEmptyIterator)();var i=this.extractor?this.extractor(e):e,n=this.extractor?this.extractor(r):r,h=this.comparator(i,n)>0,s=h,o=!s,a=this.findPath(i,s),u=this.findPath(n,o);return null===a||null===u?(0,y.getEmptyIterator)():this._iteratorFromTo(t,a,u,h)},between:function(t,e){return this._baseBetween(E,t,e)},_pathNodes:function(t){for(var e=new Array(t.length),r=this.root,i=0;i<t.length;i++)e[i]=r,r=r.children[t.get(i)];return e},_nextPath:function(t){var e=this._pathNodes(t),r=e.length-1;if(t.get(r)<e[r].children.length-1)return t.increment(r);for(r--;r>=0&&t.get(r)===e[r].children.length-1;)r--;return 0>r?null:t.increment(r)},_prevPath:function(t){if(t.equals(v["default"].EMPTY_PATH))return null;for(var e=this._pathNodes(t),r=t.length-1;0===t.get(r);)r--;var i=t.set(r,t.get(r)-1),n=e[r].children[i.get(r)];for(r++;r<t.length;r++){var h=n.children.length;i=i.set(r,h-1),n=n.children[h-1]}return i},_iterateAllWithExtractFn:function(t){return 0===this.size?(0,y.getEmptyIterator)():this._iteratorFromTo(t,this._getLeftmostPath(),this._getRightmostPath())},_getLeafFromPath:function(t){for(var e=this.height,r=0,i=this.root;r!==e;)i=i.children[t.get(r++)];return i},_getRightmostPath:function(){if(0===this.size)return null;for(var t=[],e=this.root,r=0,i=this.height;r!==i+1;){var n=e.children.length-1;t.push(n),e=e.children[n],r++}return v["default"].from(t)},_getLeftmostPath:function(){return 0===this.size?null:new v["default"](p.SHIFT_LEN,this.height+1)},_iteratorFromTo:function(t,e,r,i){var n=this,h=i?this._prevPath.bind(this):this._nextPath.bind(this),s=this.height,o=e,a=void 0,u=!1,l={next:function(){var e=null!==o&&o.equals(r);if(!(null===o||e&&u)){var l=o.get(s),c=a||n._getLeafFromPath(o);e?u=!0:i&&l>0?o=o.decrement(s):!i&&l<c.children.length-1?o=o.increment(s):(o=h(o),a=void 0);var d=t(c,l);return{value:d}}return{done:!0}}};return l[p.ITERATOR_PROPNAME]=function(){return l},l},findPath:function(t,e){if(0===this.size)return null;for(var r=this.comparator,i=this.root,n=this.height,h=new Array(n+1),s=0,o=i;n>s;s++){var a=i.childIdxForKey(r,t);h[s]=a,o=i,i=i.children[a]}var u=o,l=e?c["default"].lte(i.keys,t,r):c["default"].gte(i.keys,t,r);if(l===i.keys.length)if(e)h[s]=l-1;else{h[s-1]++;var d=h[s-1]<u.children.length;if(!d)return null;if(i=u.children[h[s-1]],!(i.keys[0]>=t))return null;h[s]=0}else if(-1===l)if(e){h[s-1]--;var f=h[s-1]>=0;if(!f)return null;if(i=u.children[h[s-1]],!(i.keys[i.keys.length-1]<=t))return null;h[s]=i.keys.length-1}else h[s]=0;else h[s]=l;return v["default"].from(h)},findLeaf:function(t,e){for(var r=this.root,i=this.height,n=0;i>n;n++){var h=r.childIdxForKey(t,e);r=r.children[h]}return r},search:function(t,e){var r=this.extractor?this.extractor(e):e,i=this.findLeaf(t,r),n=g(i.keys,r,t);return-1===n?I:i.children[n]},visit:function(t){for(var e=[this.root];e.length;){var r=e.shift();t(r),r.constructor!==d.Leaf&&r.children&&e.push.apply(e,n(r.children))}}});var m=function(t){return function(){if(0===arguments.length)return this._iterateAllWithExtractFn(t);var e=arguments[0],r=arguments[1];return this._baseBetween(t,e,r)}};h.prototype.values=m(k),h.prototype.valueRange=h.prototype.values,h.prototype.entries=m(E),h.prototype.entryRange=h.prototype.entries,h.prototype.keys=m(w),h.prototype.keyRange=h.prototype.keys,h.from=o,h.prototype[p.ITERATOR_PROPNAME]=function(){return this.isSet?this.values():this.entries()};var R=e.BTMap=h;u.from=a,u.prototype=h.prototype,e["default"]=R},function(t,e){"use strict";function r(t,e,r){var i=t.length;if(0===i||!(r(t[0],e)<=0))return-1;for(var n=0,h=i;h-n>1;){var s=h+n>>>1;r(t[s],e)<=0?n=s:h=s}return n}function i(t,e,r){var i=t.length;if(0===i||!(r(t[i-1],e)>=0))return i;for(var n=-1,h=i-1;h-n>1;){var s=h+n>>>1;r(t[s],e)>=0?h=s:n=s}return h}function n(t,e,i){var n=r(t,e,i);return-1!==n&&0===i(t[n],e)?n:-1}Object.defineProperty(e,"__esModule",{value:!0}),e.lte=r,e.gte=i,e.eq=n,e["default"]={lte:r,gte:i,eq:n}},function(t,e,r){"use strict";function i(t){return t&&t.__esModule?t:{"default":t}}function n(t){var e=t||{};this.keys=e.keys||[],this.children=e.children||[],this.order=u.ORDER,this.ownerID=e.ownerID}function h(t){n.call(this,t)}function s(t){n.call(this,t)}Object.defineProperty(e,"__esModule",{value:!0}),e.InternalNode=e.Leaf=e.Node=e.DELETION_STRATEGIES=void 0;var o=r(1),a=i(o),u=r(3),l=r(4),c=a["default"].eq,d=function(t,e,r){return a["default"].gte(r,e,t)};Object.defineProperty(n.prototype,"size",{enumerable:!0,get:function(){return this.children.length}}),(0,l.extend)(n.prototype,{satisfiesMinChildren:function(){return this.children.length>=this.minChildren},satisfiesMaxChildren:function(){return this.children.length<=this.maxChildren},tail:function(t){return new this.constructor({order:this.order,keys:(0,l.tail)(t,this.keys),children:(0,l.tail)(t,this.children),ownerID:t})},init:function(t){return new this.constructor({order:this.order,keys:(0,l.init)(t,this.keys),children:(0,l.init)(t,this.children),ownerID:t})},shouldSplit:function(){return!this.satisfiesMaxChildren()}}),h.prototype=Object.create(n.prototype),h.prototype.constructor=h,(0,l.extend)(h.prototype,{maxChildren:u.LEAF_MAX_CHILDREN,minChildren:u.LEAF_MIN_CHILDREN,"delete":function(t,e,r,i){var n=c(this.keys,i,t);if(-1===n)return this;(0,l.setRef)(r);var s=void 0,o=(0,l.withoutIdx)(e,n,this.keys),a=(0,l.withoutIdx)(e,n,this.children);return(0,l.canMutate)(this,e)?(s=this,s.keys=o,s.children=a):s=new h({order:this.order,keys:(0,l.withoutIdx)(e,n,this.keys),children:(0,l.withoutIdx)(e,n,this.children),ownerID:e}),s},merge:function(t){return new h({order:this.order,keys:this.keys.concat(t.keys),children:this.children.concat(t.children)})},idxForKey:function(t,e){return a["default"].gte(this.keys,e,t)},insert:function(t,e,r,i,n){var s=this.idxForKey(t,i),o=this.keys[s]===i,a=void 0,u=void 0;if(o){var c=this.children[s];if(c===n)return this;a=(0,l.set)(e,s,i,this.keys),u=(0,l.set)(e,s,n,this.children)}else a=(0,l.insert)(e,s,i,this.keys),u=(0,l.insert)(e,s,n,this.children);(0,l.setRef)(r);var d=void 0;return(0,l.canMutate)(this,e)?(d=this,this.keys=a,this.children=u):d=new h({order:this.order,keys:a,children:u,ownerID:e}),d.shouldSplit()?d.split(e):d},split:function(t){var e=(0,l.median)(this.keys.length),r=this.keys[e],i=(0,l.splitAt)(t,e,this.keys),n=i[0],s=i[1],o=(0,l.splitAt)(t,e,this.children),a=o[0],u=o[1],c=new h({order:this.order,keys:s,children:u,ownerID:t}),d=void 0;return(0,l.canMutate)(this,t)?(d=this,d.keys=n,d.children=a):d=new h({order:this.order,keys:n,children:a,ownerID:t}),[r,d,c]},smallestKey:function(){return this.keys[0]},stealFirstKeyFrom:function(t,e){var r=e.keys[0],i=e.children[0];this.keys=this.keys.concat(r),this.children=this.children.concat(i);var n=e.tail(t);return[this,n]},giveLastKeyTo:function(t,e){var r=this.keys[this.keys.length-1],i=this.children[this.children.length-1];e.keys=(0,l.unshift)(t,r,e.keys),e.children=(0,l.unshift)(t,i,e.children);var n=this.init(t);return[n,e]}});var f="REPLACE",v="STEAL_KEY_FROM_LEFT",y="STEAL_KEY_FROM_RIGHT",p="MERGE";e.DELETION_STRATEGIES={STEAL_KEY_FROM_LEFT:v,STEAL_KEY_FROM_RIGHT:y,MERGE:p};s.prototype=Object.create(n.prototype),s.prototype.constructor=s,(0,l.extend)(s.prototype,{maxChildren:u.INTERNAL_MAX_CHILDREN,minChildren:u.INTERNAL_MIN_CHILDREN,merge:function(t){var e=(0,l.unshift)(null,t.smallestKey(),t.keys),r=new s({order:this.order,keys:this.keys.concat(e),children:this.children.concat(t.children)});return r},chooseComplexDeletionStrategy:function(t,e){if(e.satisfiesMinChildren())return{strategy:f};var r=t+1<this.children.length,i=t-1>=0,n=e.constructor===h,s={size:0},o=r?this.children[t+1]:s,a=i?this.children[t-1]:s,l=n?u.LEAF_MIN_CHILDREN:u.INTERNAL_MIN_CHILDREN,c=void 0;return o.size>=a.size?(c=o.size<=l?p:y,{leftNode:e,rightNode:o,leftNodeIdx:t,strategy:c}):(c=a.size<=l?p:v,{leftNode:a,rightNode:e,leftNodeIdx:t-1,strategy:c})},"delete":function(t,e,r,i){var n=this.childIdxForKey(t,i),h=this.children[n],s=h["delete"](t,e,r,i);if(!(0,l.isSet)(r))return this;var o=this.chooseComplexDeletionStrategy(n,s),a=o.strategy;if(a===f)return this.withReplacedChildren(e,n,[s]);var u=o.leftNode,c=o.rightNode,d=o.leftNodeIdx;if(a===p)return this.withMergedChildren(e,d,u,c);var g=void 0,I=void 0;if(a===y){var _=u.stealFirstKeyFrom(e,c);g=_[0],I=_[1]}else if(a===v){var k=u.giveLastKeyTo(e,c);g=k[0],I=k[1]}var w=this.withReplacedChildren(e,d,[g,I]),E=d,m=I.smallestKey();return w.keys=(0,l.set)(e,E,m,w.keys),w},withMergedChildren:function(t,e,r,i){var n=r.merge(i),h=e,o=(0,l.withoutIdx)(t,h,this.keys),a=0===e;a||(o[e-1]=n.smallestKey());var u=(0,l.arrayClone)(this.children);u.splice(e,1),u[e]=n;var c=new s({order:this.order,keys:o,children:u,ownerID:t});return c},childIdxForKey:function(t,e){return a["default"].lte(this.keys,e,t)+1},stealFirstKeyFrom:function(t,e){var r=e.children[0];return this.keys=this.keys.concat(e.smallestKey()),this.children=this.children.concat(r),[this,e.tail(t)]},giveLastKeyTo:function(t,e){var r=(0,l.last)(this.children);return e.keys=(0,l.unshift)(t,e.smallestKey(),e.keys),e.children=(0,l.unshift)(t,r,e.children),[this.init(t),e]},withReplacedChildren:function(t,e,r){for(var i=(0,l.canMutate)(this.children,t)?this.children:(0,l.arrayClone)(this.children),n=0;n<r.length;n++)i[e+n]=r[n];return(0,l.canMutate)(this,t)?(this.children=i,this):new s({order:this.order,keys:this.keys,children:i,ownerID:t})},smallestKey:function(){for(var t=this;t.constructor!==h;)t=t.children[0];return t.keys[0]},split:function(t){var e=(0,l.median)(this.keys.length)-1,r=(0,l.takeIdxAndSplit)(t,e,this.keys),i=r[0],n=r[1],h=r[2],o=(0,l.splitAt)(t,e+1,this.children),a=o[0],u=o[1],c=void 0;(0,l.canMutate)(this,t)?(c=this,c.keys=i,c.children=a):c=new s({order:this.order,keys:i,children:a,ownerID:t});var d=new s({order:this.order,keys:h,children:u,ownerID:t});return[n,c,d]},withSplitChild:function(t,e,r,i,n){var h=d(t,r,this.keys),o=(0,l.insert)(e,h,r,this.keys),a=(0,l.insert)(e,h+1,n,this.children);return a[h]=i,(0,l.canMutate)(this,e)?(this.keys=o,this.children=a,this):new s({order:this.order,keys:o,children:a,ownerID:e})},insert:function(t,e,r,i,n){var h=this.childIdxForKey(t,i),s=this.children[h],o=s.insert(t,e,r,i,n);if(!(0,l.isSet)(r))return this;if(3===o.length){var a=o,u=a[0],c=a[1],d=a[2],f=this.withSplitChild(t,e,u,c,d);return f.shouldSplit()?f.split(e):f}return this.withReplacedChildren(e,h,[o])}}),e.Node=n,e.Leaf=h,e.InternalNode=s},function(t,e){"use strict";Object.defineProperty(e,"__esModule",{value:!0});var r=(e.MIN_ROOT_CHILDREN=2,e.ORDER=64);e.SHIFT_LEN=6,e.LEAF_MIN_CHILDREN=Math.ceil(r/2)-1,e.LEAF_MAX_CHILDREN=r-1,e.INTERNAL_MIN_CHILDREN=Math.ceil(r/2),e.INTERNAL_MAX_CHILDREN=r,e.ITERATOR_PROPNAME="function"==typeof Symbol?Symbol.iterator:"@@iterator"},function(t,e,r){"use strict";function i(){return{}}function n(t,e){return t.ownerID=e,t}function h(t,e){return e&&e===t.ownerID}function s(t,e){return n(e?new Array(e):[],t)}function o(t,e,r,i){var n=r-e;if(h(i,t)){for(var o=e,a=i.length-r;o--;)i.shift();for(;a--;)i.pop();return i}for(var u=s(t,n),l=e;r>l;l++)u[l-e]=i[l];return u}function a(t){for(var e=t.length,r=new Array(e),i=0;e>i;i++)r[i]=t[i];return r}function u(t,e,r){var i=h(r,t)?r:n(a(r),t);return i.splice(e,1),i}function l(t,e,r,i){if(h(i,t))return i.splice(e,0,r),i;for(var n=i.length+1,s=new Array(n),o=0;e>o;o++)s[o]=i[o];for(s[o++]=r;n>o;o++)s[o]=i[o-1];return s}function c(t,e,r,i){var s=h(i,t)?i:n(a(i),t);return s[e]=r,s}function d(t,e){for(var r=a(e),i=e.length,n=0;i>n;n++)r[n]=t(e[n],n);return r}function f(t,e,r){for(var i=r.length,n=e,h=i-e,o=s(t,h),a=s(t,n),u=0;e>u;u++)a[u]=r[u];for(var l=e;i>l;l++)o[l-e]=r[l];return[a,o]}function v(t,e,r){return l(t,0,e,r)}function y(t){return t[t.length-1]}function p(t,e){return h(e,t)?0===e.length?e:(e.pop(),e):e.length<=1?s(t):o(t,0,e.length-1,e)}function g(t,e){return h(e,t)?(e.shift(),e):e.length<=1?n([],t):o(t,1,e.length,e)}function I(){var t={next:function(){return{done:!0}}};return t[m.ITERATOR_PROPNAME]=function(){return t},t}function _(t){var e=arguments.length,r=void 0,i=void 0,n=void 0,h=void 0,s=void 0;for(s=1;e>s;s++)for(r=arguments[s],i=Object.keys(r),h=0;h<i.length;h++)n=i[h],t[n]=r[n];return t}function k(t){return{value:t}}function w(t){t.value=!0}function E(t){return!!t.value}Object.defineProperty(e,"__esModule",{value:!0}),e.boundedChunk=e.takeIdxAndSplit=e.median=void 0,e.makeOwnerID=i,e.tagOwnerID=n,e.canMutate=h,e.slice=o,e.arrayClone=a,e.withoutIdx=u,e.insert=l,e.set=c,e.fastMap=d,e.splitAt=f,e.unshift=v,e.last=y,e.init=p,e.tail=g,e.getEmptyIterator=I,e.extend=_,e.makeRef=k,e.setRef=w,e.isSet=E;var m=r(3);e.median=function(t){return Math.ceil(t/2)},e.takeIdxAndSplit=function(t,e,r){var i=e,n=i,h=o(t,0,n,r),s=o(t,i+1,r.length,r);return[h,r[i],s]},e.boundedChunk=function(t,e,r){var i=r.length;if(!r.length)return[];if(r.length<=e)return[r];for(var n=Math.ceil((t+e)/2),h=i/n,s=Math.ceil(h),o=1/s*i,a=new Array(s),u=0;s>u;u++)a[u]=r.slice(Math.ceil(u*o),Math.ceil((u+1)*o));return a}},function(t,e,r){"use strict";function i(t,e,r){this.shiftLen=t||n.SHIFT_LEN,this.length=e||a,this._path=r||0}Object.defineProperty(e,"__esModule",{value:!0}),e.Path=e.safePathSet=e.clearBitRange=e.pathSet=e.pathGet=e.bitSlice=e.LEVELS=void 0;var n=r(3),h=r(4),s=0,o=31,a=e.LEVELS=Math.floor(o/n.SHIFT_LEN),u=e.bitSlice=function(t,e,r){var i=Math.pow(2,e)-1;return(r&i)>>>t},l=e.pathGet=function(t,e,r){return u(t*e,t*(e+1),r)},c=e.pathSet=function(t,e,r,i){return r|i<<t*e},d=e.clearBitRange=function(t,e,r){var i=e-t,n=Math.pow(2,i)-1;return r&~(n<<t)},f=e.safePathSet=function(t,e,r,i){var n=d(t*e,t*(e+1),r);return c(t,e,n,i)};i.EMPTY_PATH=new i(n.SHIFT_LEN,a,s),i.from=function(t){for(var e=t.length,r=0,h=0;e>h;h++)r=c(n.SHIFT_LEN,h,r,t[h]);return new i(n.SHIFT_LEN,e,r)},(0,h.extend)(i.prototype,{get:function(t){return l(this.shiftLen,t,this._path)},equals:function(t){return this._path===t._path},clearAfter:function(t){for(var e=t+1,r=this;e<this.length;)r=r.set(e,0),e++;return r},toArray:function(){for(var t=new Array(this.length),e=0;e<this.length;e++)t[e]=this.get(e);return t},compareTo:function(t){var e=this._path,r=t._path;return e===r?0:r>e?-1:1},increment:function(t){var e=this.set(t,this.get(t)+1);return e.clearAfter(t)},decrement:function(t){return this.set(t,this.get(t)-1)},set:function(t,e){var r=f(this.shiftLen,t,this._path,e);return new i(this.shiftLen,this.length,r)}}),e.Path=i,e["default"]=i}]);
+var ibtree=function(t){function e(n){if(r[n])return r[n].exports;var i=r[n]={exports:{},id:n,loaded:!1};return t[n].call(i.exports,i,i.exports,e),i.loaded=!0,i.exports}var r={};return e.m=t,e.c=r,e.p="",e(0)}([function(t,e,r){"use strict";function n(t){return t&&t.__esModule?t:{"default":t}}function i(t){if(Array.isArray(t)){for(var e=0,r=Array(t.length);e<t.length;e++)r[e]=t[e];return r}return Array.from(t)}function o(t){var e=t||{};this.order=p.ORDER,this.isSet=void 0===e.isSet?!1:e.isSet,this.extractor=e.extractor,this.comparator=e.comparator||_,this.root=e.root||new f.Leaf({order:this.order}),this.size=e.size||0,this.height=e.height||0,this.ownerID=e.ownerID}function s(t,e,r){var n=e||{},i=p.ORDER,o=1,s=p.LEAF_MIN_CHILDREN+o,h=p.LEAF_MAX_CHILDREN,a=p.INTERNAL_MIN_CHILDREN,u=p.INTERNAL_MAX_CHILDREN,l=(0,y.boundedChunk)(s,h,t),c=(0,y.fastMap)(function(t){var e=void 0;e=r?(0,y.fastMap)(function(t){return n.extractor?n.extractor(t[0]):t[0]},t):n.extractor?(0,y.fastMap)(n.extractor,t):t;var o=r?(0,y.fastMap)(function(t){return t[1]},t):t;return new f.Leaf({order:i,keys:e,children:o})},l),d=0,v=null,g=!1;if(1===c.length)v=c[0];else{for(var I=c,_=function(){var t=(0,y.boundedChunk)(a+o,u,I),e=!0,r=(0,y.fastMap)(function(t){var r=g?function(t){var e=t.keys[0];return t.keys=(0,y.tail)(null,t.keys),e}:function(t){return t.keys[0]},n=e?(0,y.tail)(null,t):t,o=(0,y.fastMap)(r,n);return e=!1,new f.InternalNode({order:i,keys:o,children:t})},t);return 0===r.length?"break":(I=r,g=!0,void d++)};I.length>1;){var m=_();if("break"===m)break}v=I[0]}var w=this;return new w((0,y.extend)({},n,{root:v,size:t.length,height:d}))}function h(t,e){return s.call(this,t,e,!0)}function a(t,e){return s.call(this,t,e,!1)}function u(t){var e=t||{};e.isSet=!0,o.call(this,e)}Object.defineProperty(e,"__esModule",{value:!0}),e.BTMap=e.defaultComparator=void 0,e.BPlusTree=o,e.BTSet=u;var l=r(1),c=n(l),f=r(2),d=r(5),v=n(d),y=r(4),p=r(3),g=c["default"].eq,I={},_=e.defaultComparator=function(t,e){return t===e?0:e>t?-1:1},m=function(t,e){return t.children[e]},w=function(t,e){return t.keys[e]},k=function(t,e){return[w(t,e),m(t,e)]};(0,y.extend)(o.prototype,{has:function(t){return this.search(this.comparator,t)!==I},add:function(t){return this.set(t,t)},get:function(t){var e=this.search(this.comparator,t);return e===I?void 0:e},clear:function(){return new this.constructor({comparator:this.comparator,extractor:this.extractor})},set:function(t,e){var r=this.comparator,n=this.extractor?this.extractor(t):t,i=(0,y.makeRef)(!1),o=this.root.insert(r,this.ownerID,i,n,e);if(!(0,y.isSet)(i))return this;var s=void 0,h=!1,a=!!this.ownerID;if(3===o.length){h=!0;var u=o,l=u[0],c=u[1],d=u[2],v=(0,y.tagOwnerID)([l],this.ownerID),p=(0,y.tagOwnerID)([c,d],this.ownerID);s=new f.InternalNode({order:this.order,keys:v,children:p})}else s=o;var g=h?this.height+1:this.height,I=this.size+1;return a?(this.height=g,this.size=I,this.root=s,this._didAlter=!0,this):new this.constructor({extractor:this.extractor,comparator:this.comparator,root:s,height:g,size:I,ownerID:this.ownerID})},"delete":function(t){var e=(0,y.makeRef)(!1),r=this.root["delete"](this.comparator,this.ownerID,e,t);if(!(0,y.isSet)(e))return this;var n=!1;if(r.size<p.MIN_ROOT_CHILDREN){var i=r.constructor===f.Leaf;i||(r=r.children[0],n=!0)}var o=!!this.ownerID,s=void 0,h=n?this.height-1:this.height,a=this.size-1;return o?(s=this,this.root=r,this.height=h,this.size=a,this._didAlter=!0):s=new this.constructor({comparator:this.comparator,extractor:this.extractor,root:r,height:h,size:a,ownerID:this.ownerID}),s},asMutable:function(){return this.ownerID?this:new this.constructor({comparator:this.comparator,extractor:this.extractor,root:this.root,height:this.height,size:this.size,ownerID:(0,y.makeOwnerID)()})},asImmutable:function(){return this.ownerID?new this.constructor({comparator:this.comparator,extractor:this.extractor,root:this.root,height:this.height,size:this.size}):this},withMutations:function(t){var e=this.asMutable();return t(e),e._didAlter?e.asImmutable():this},_baseBetween:function(t,e){if(0===this.size)return(0,y.getEmptyIterator)();var r=(0,y.normalizeRangeSpec)(e),n=this.extractor?this.extractor(r.from):r.from,i=this.extractor?this.extractor(r.to):r.to,o=this.comparator(n,i)>0,s=o,h=!s,a=this.findPath(n,s,r.fromInclusive),u=this.findPath(i,h,r.toInclusive);return null===a||null===u?(0,y.getEmptyIterator)():this._iteratorFromTo(t,a,u,o)},between:function(t,e){if(1===arguments.length){var r=arguments[0];return this._baseBetween(k,r)}var n={from:t,to:e};return this._baseBetween(k,n)},_pathNodes:function(t){for(var e=new Array(t.length),r=this.root,n=0;n<t.length;n++)e[n]=r,r=r.children[t.get(n)];return e},_nextPath:function(t){var e=this._pathNodes(t),r=e.length-1;if(t.get(r)<e[r].children.length-1)return t.increment(r);for(r--;r>=0&&t.get(r)===e[r].children.length-1;)r--;return 0>r?null:t.increment(r)},_prevPath:function(t){if(t.equals(v["default"].EMPTY_PATH))return null;for(var e=this._pathNodes(t),r=t.length-1;0===t.get(r);)r--;var n=t.set(r,t.get(r)-1),i=e[r].children[n.get(r)];for(r++;r<t.length;r++){var o=i.children.length;n=n.set(r,o-1),i=i.children[o-1]}return n},_iterateAllWithExtractFn:function(t){return 0===this.size?(0,y.getEmptyIterator)():this._iteratorFromTo(t,this._getLeftmostPath(),this._getRightmostPath())},_getLeafFromPath:function(t){for(var e=this.height,r=0,n=this.root;r!==e;)n=n.children[t.get(r++)];return n},_getRightmostPath:function(){if(0===this.size)return null;for(var t=[],e=this.root,r=0,n=this.height;r!==n+1;){var i=e.children.length-1;t.push(i),e=e.children[i],r++}return v["default"].from(t)},_getLeftmostPath:function(){return 0===this.size?null:new v["default"](p.SHIFT_LEN,this.height+1)},_iteratorFromTo:function(t,e,r,n){var i=this,o=n?this._prevPath.bind(this):this._nextPath.bind(this),s=this.height,h=e,a=void 0,u=!1,l={next:function(){var e=null!==h&&h.equals(r);if(!(null===h||e&&u)){var l=h.get(s),c=a||i._getLeafFromPath(h);e?u=!0:n&&l>0?h=h.decrement(s):!n&&l<c.children.length-1?h=h.increment(s):(h=o(h),a=void 0);var f=t(c,l);return{value:f}}return{done:!0}}};return l[p.ITERATOR_PROPNAME]=function(){return l},l},findPath:function(t,e,r){if(0===this.size)return null;for(var n=this.comparator,i=this.root,o=this.height,s=new Array(o+1),h=0,a=i;o>h;h++){var u=i.childIdxForKey(n,t);s[h]=u,a=i,i=i.children[u]}var l=a,f=(e?"lt":"gt")+(r?"e":""),d=c["default"][f],y=d(i.keys,t,n);if(y===i.keys.length)if(e)s[h]=y-1;else{s[h-1]++;var p=s[h-1]<l.children.length;if(!p)return null;if(i=l.children[s[h-1]],!(i.keys[0]>=t))return null;s[h]=0}else if(-1===y)if(e){s[h-1]--;var g=s[h-1]>=0;if(!g)return null;if(i=l.children[s[h-1]],!(i.keys[i.keys.length-1]<=t))return null;s[h]=i.keys.length-1}else s[h]=0;else s[h]=y;return v["default"].from(s)},findLeaf:function(t,e){for(var r=this.root,n=this.height,i=0;n>i;i++){var o=r.childIdxForKey(t,e);r=r.children[o]}return r},search:function(t,e){var r=this.extractor?this.extractor(e):e,n=this.findLeaf(t,r),i=g(n.keys,r,t);return-1===i?I:n.children[i]},visit:function(t){for(var e=[this.root];e.length;){var r=e.shift();t(r),r.constructor!==f.Leaf&&r.children&&e.push.apply(e,i(r.children))}}});var E=function(t){return function(){if(0===arguments.length)return this._iterateAllWithExtractFn(t);if(1===arguments.length){var e=arguments[0];this._baseBetween(t,e)}var r={from:arguments[0],to:arguments[1]};return this._baseBetween(t,r)}};o.prototype.values=E(m),o.prototype.valueRange=o.prototype.values,o.prototype.entries=E(k),o.prototype.entryRange=o.prototype.entries,o.prototype.keys=E(w),o.prototype.keyRange=o.prototype.keys,o.from=h,o.prototype[p.ITERATOR_PROPNAME]=function(){return this.isSet?this.values():this.entries()};var R=e.BTMap=o;u.from=a,u.prototype=o.prototype,e["default"]=R},function(t,e){"use strict";function r(t,e,r,n){var i=e.length;if(0===i||!(t?n(e[0],r)<=0:n(e[0],r)<0))return-1;for(var o=0,s=i;s-o>1;){var h=s+o>>>1,a=e[h];(t?n(a,r)<=0:n(a,r)<0)?o=h:s=h}return o}function n(t,e,r,n){var i=e.length;if(0===i||!(t?n(e[i-1],r)>=0:n(e[i-1],r)>0))return i;for(var o=-1,s=i-1;s-o>1;){var h=s+o>>>1,a=e[h];(t?n(a,r)>=0:n(a,r)>0)?s=h:o=h}return s}function i(t,e,r){var n=o(t,e,r);return-1!==n&&0===r(t[n],e)?n:-1}Object.defineProperty(e,"__esModule",{value:!0}),e.baseGte=n,e.eq=i;var o=e.lte=r.bind(null,!0),s=e.lt=r.bind(null,!1),h=e.gte=n.bind(null,!0),a=e.gt=n.bind(null,!1);e["default"]={lt:s,gt:a,lte:o,gte:h,eq:i}},function(t,e,r){"use strict";function n(t){return t&&t.__esModule?t:{"default":t}}function i(t){var e=t||{};this.keys=e.keys||[],this.children=e.children||[],this.order=u.ORDER,this.ownerID=e.ownerID}function o(t){i.call(this,t)}function s(t){i.call(this,t)}Object.defineProperty(e,"__esModule",{value:!0}),e.InternalNode=e.Leaf=e.Node=e.DELETION_STRATEGIES=void 0;var h=r(1),a=n(h),u=r(3),l=r(4),c=a["default"].eq,f=function(t,e,r){return a["default"].gte(r,e,t)};Object.defineProperty(i.prototype,"size",{enumerable:!0,get:function(){return this.children.length}}),(0,l.extend)(i.prototype,{satisfiesMinChildren:function(){return this.children.length>=this.minChildren},satisfiesMaxChildren:function(){return this.children.length<=this.maxChildren},tail:function(t){return new this.constructor({order:this.order,keys:(0,l.tail)(t,this.keys),children:(0,l.tail)(t,this.children),ownerID:t})},init:function(t){return new this.constructor({order:this.order,keys:(0,l.init)(t,this.keys),children:(0,l.init)(t,this.children),ownerID:t})},shouldSplit:function(){return!this.satisfiesMaxChildren()}}),o.prototype=Object.create(i.prototype),o.prototype.constructor=o,(0,l.extend)(o.prototype,{maxChildren:u.LEAF_MAX_CHILDREN,minChildren:u.LEAF_MIN_CHILDREN,"delete":function(t,e,r,n){var i=c(this.keys,n,t);if(-1===i)return this;(0,l.setRef)(r);var s=void 0,h=(0,l.withoutIdx)(e,i,this.keys),a=(0,l.withoutIdx)(e,i,this.children);return(0,l.canMutate)(this,e)?(s=this,s.keys=h,s.children=a):s=new o({order:this.order,keys:(0,l.withoutIdx)(e,i,this.keys),children:(0,l.withoutIdx)(e,i,this.children),ownerID:e}),s},merge:function(t){return new o({order:this.order,keys:this.keys.concat(t.keys),children:this.children.concat(t.children)})},idxForKey:function(t,e){return a["default"].gte(this.keys,e,t)},insert:function(t,e,r,n,i){var s=this.idxForKey(t,n),h=this.keys[s]===n,a=void 0,u=void 0;if(h){var c=this.children[s];if(c===i)return this;a=(0,l.set)(e,s,n,this.keys),u=(0,l.set)(e,s,i,this.children)}else a=(0,l.insert)(e,s,n,this.keys),u=(0,l.insert)(e,s,i,this.children);(0,l.setRef)(r);var f=void 0;return(0,l.canMutate)(this,e)?(f=this,this.keys=a,this.children=u):f=new o({order:this.order,keys:a,children:u,ownerID:e}),f.shouldSplit()?f.split(e):f},split:function(t){var e=(0,l.median)(this.keys.length),r=this.keys[e],n=(0,l.splitAt)(t,e,this.keys),i=n[0],s=n[1],h=(0,l.splitAt)(t,e,this.children),a=h[0],u=h[1],c=new o({order:this.order,keys:s,children:u,ownerID:t}),f=void 0;return(0,l.canMutate)(this,t)?(f=this,f.keys=i,f.children=a):f=new o({order:this.order,keys:i,children:a,ownerID:t}),[r,f,c]},smallestKey:function(){return this.keys[0]},stealFirstKeyFrom:function(t,e){var r=e.keys[0],n=e.children[0];this.keys=this.keys.concat(r),this.children=this.children.concat(n);var i=e.tail(t);return[this,i]},giveLastKeyTo:function(t,e){var r=this.keys[this.keys.length-1],n=this.children[this.children.length-1];e.keys=(0,l.unshift)(t,r,e.keys),e.children=(0,l.unshift)(t,n,e.children);var i=this.init(t);return[i,e]}});var d="REPLACE",v="STEAL_KEY_FROM_LEFT",y="STEAL_KEY_FROM_RIGHT",p="MERGE";e.DELETION_STRATEGIES={STEAL_KEY_FROM_LEFT:v,STEAL_KEY_FROM_RIGHT:y,MERGE:p};s.prototype=Object.create(i.prototype),s.prototype.constructor=s,(0,l.extend)(s.prototype,{maxChildren:u.INTERNAL_MAX_CHILDREN,minChildren:u.INTERNAL_MIN_CHILDREN,merge:function(t){var e=(0,l.unshift)(null,t.smallestKey(),t.keys),r=new s({order:this.order,keys:this.keys.concat(e),children:this.children.concat(t.children)});return r},chooseComplexDeletionStrategy:function(t,e){if(e.satisfiesMinChildren())return{strategy:d};var r=t+1<this.children.length,n=t-1>=0,i=e.constructor===o,s={size:0},h=r?this.children[t+1]:s,a=n?this.children[t-1]:s,l=i?u.LEAF_MIN_CHILDREN:u.INTERNAL_MIN_CHILDREN,c=void 0;return h.size>=a.size?(c=h.size<=l?p:y,{leftNode:e,rightNode:h,leftNodeIdx:t,strategy:c}):(c=a.size<=l?p:v,{leftNode:a,rightNode:e,leftNodeIdx:t-1,strategy:c})},"delete":function(t,e,r,n){var i=this.childIdxForKey(t,n),o=this.children[i],s=o["delete"](t,e,r,n);if(!(0,l.isSet)(r))return this;var h=this.chooseComplexDeletionStrategy(i,s),a=h.strategy;if(a===d)return this.withReplacedChildren(e,i,[s]);var u=h.leftNode,c=h.rightNode,f=h.leftNodeIdx;if(a===p)return this.withMergedChildren(e,f,u,c);var g=void 0,I=void 0;if(a===y){var _=u.stealFirstKeyFrom(e,c);g=_[0],I=_[1]}else if(a===v){var m=u.giveLastKeyTo(e,c);g=m[0],I=m[1]}var w=this.withReplacedChildren(e,f,[g,I]),k=f,E=I.smallestKey();return w.keys=(0,l.set)(e,k,E,w.keys),w},withMergedChildren:function(t,e,r,n){var i=r.merge(n),o=e,h=(0,l.withoutIdx)(t,o,this.keys),a=0===e;a||(h[e-1]=i.smallestKey());var u=(0,l.arrayClone)(this.children);u.splice(e,1),u[e]=i;var c=new s({order:this.order,keys:h,children:u,ownerID:t});return c},childIdxForKey:function(t,e){return a["default"].lte(this.keys,e,t)+1},stealFirstKeyFrom:function(t,e){var r=e.children[0];return this.keys=this.keys.concat(e.smallestKey()),this.children=this.children.concat(r),[this,e.tail(t)]},giveLastKeyTo:function(t,e){var r=(0,l.last)(this.children);return e.keys=(0,l.unshift)(t,e.smallestKey(),e.keys),e.children=(0,l.unshift)(t,r,e.children),[this.init(t),e]},withReplacedChildren:function(t,e,r){for(var n=(0,l.canMutate)(this.children,t)?this.children:(0,l.arrayClone)(this.children),i=0;i<r.length;i++)n[e+i]=r[i];return(0,l.canMutate)(this,t)?(this.children=n,this):new s({order:this.order,keys:this.keys,children:n,ownerID:t})},smallestKey:function(){for(var t=this;t.constructor!==o;)t=t.children[0];return t.keys[0]},split:function(t){var e=(0,l.median)(this.keys.length)-1,r=(0,l.takeIdxAndSplit)(t,e,this.keys),n=r[0],i=r[1],o=r[2],h=(0,l.splitAt)(t,e+1,this.children),a=h[0],u=h[1],c=void 0;(0,l.canMutate)(this,t)?(c=this,c.keys=n,c.children=a):c=new s({order:this.order,keys:n,children:a,ownerID:t});var f=new s({order:this.order,keys:o,children:u,ownerID:t});return[i,c,f]},withSplitChild:function(t,e,r,n,i){var o=f(t,r,this.keys),h=(0,l.insert)(e,o,r,this.keys),a=(0,l.insert)(e,o+1,i,this.children);return a[o]=n,(0,l.canMutate)(this,e)?(this.keys=h,this.children=a,this):new s({order:this.order,keys:h,children:a,ownerID:e})},insert:function(t,e,r,n,i){var o=this.childIdxForKey(t,n),s=this.children[o],h=s.insert(t,e,r,n,i);if(!(0,l.isSet)(r))return this;if(3===h.length){var a=h,u=a[0],c=a[1],f=a[2],d=this.withSplitChild(t,e,u,c,f);return d.shouldSplit()?d.split(e):d}return this.withReplacedChildren(e,o,[h])}}),e.Node=i,e.Leaf=o,e.InternalNode=s},function(t,e){"use strict";Object.defineProperty(e,"__esModule",{value:!0});var r=(e.MIN_ROOT_CHILDREN=2,e.ORDER=64);e.SHIFT_LEN=6,e.LEAF_MIN_CHILDREN=Math.ceil(r/2)-1,e.LEAF_MAX_CHILDREN=r-1,e.INTERNAL_MIN_CHILDREN=Math.ceil(r/2),e.INTERNAL_MAX_CHILDREN=r,e.ITERATOR_PROPNAME="function"==typeof Symbol?Symbol.iterator:"@@iterator"},function(t,e,r){"use strict";function n(){return{}}function i(t,e){return t.ownerID=e,t}function o(t,e){return e&&e===t.ownerID}function s(t,e){return i(e?new Array(e):[],t)}function h(t,e,r,n){var i=r-e;if(o(n,t)){for(var h=e,a=n.length-r;h--;)n.shift();for(;a--;)n.pop();return n}for(var u=s(t,i),l=e;r>l;l++)u[l-e]=n[l];return u}function a(t){for(var e=t.length,r=new Array(e),n=0;e>n;n++)r[n]=t[n];return r}function u(t,e,r){var n=o(r,t)?r:i(a(r),t);return n.splice(e,1),n}function l(t,e,r,n){if(o(n,t))return n.splice(e,0,r),n;for(var i=n.length+1,s=new Array(i),h=0;e>h;h++)s[h]=n[h];for(s[h++]=r;i>h;h++)s[h]=n[h-1];return s}function c(t,e,r,n){var s=o(n,t)?n:i(a(n),t);return s[e]=r,s}function f(t,e){for(var r=a(e),n=e.length,i=0;n>i;i++)r[i]=t(e[i],i);return r}function d(t,e,r){for(var n=r.length,i=e,o=n-e,h=s(t,o),a=s(t,i),u=0;e>u;u++)a[u]=r[u];for(var l=e;n>l;l++)h[l-e]=r[l];return[a,h]}function v(t,e,r){return l(t,0,e,r)}function y(t){return t[t.length-1]}function p(t,e){return o(e,t)?0===e.length?e:(e.pop(),e):e.length<=1?s(t):h(t,0,e.length-1,e)}function g(t,e){return o(e,t)?(e.shift(),e):e.length<=1?i([],t):h(t,1,e.length,e)}function I(){var t={next:function(){return{done:!0}}};return t[R.ITERATOR_PROPNAME]=function(){return t},t}function _(t){var e=arguments.length,r=void 0,n=void 0,i=void 0,o=void 0,s=void 0;for(s=1;e>s;s++)for(r=arguments[s],n=Object.keys(r),o=0;o<n.length;o++)i=n[o],t[i]=r[i];return t}function m(t){return{value:t}}function w(t){t.value=!0}function k(t){return!!t.value}function E(t){return{from:t.from,to:t.to,fromInclusive:t.hasOwnProperty("fromInclusive")?t.fromInclusive:!0,toInclusive:t.hasOwnProperty("toInclusive")?t.toInclusive:!0}}Object.defineProperty(e,"__esModule",{value:!0}),e.boundedChunk=e.takeIdxAndSplit=e.median=void 0,e.makeOwnerID=n,e.tagOwnerID=i,e.canMutate=o,e.slice=h,e.arrayClone=a,e.withoutIdx=u,e.insert=l,e.set=c,e.fastMap=f,e.splitAt=d,e.unshift=v,e.last=y,e.init=p,e.tail=g,e.getEmptyIterator=I,e.extend=_,e.makeRef=m,e.setRef=w,e.isSet=k,e.normalizeRangeSpec=E;var R=r(3);e.median=function(t){return Math.ceil(t/2)},e.takeIdxAndSplit=function(t,e,r){var n=e,i=n,o=h(t,0,i,r),s=h(t,n+1,r.length,r);return[o,r[n],s]},e.boundedChunk=function(t,e,r){var n=r.length;if(!r.length)return[];if(r.length<=e)return[r];for(var i=Math.ceil((t+e)/2),o=n/i,s=Math.ceil(o),h=1/s*n,a=new Array(s),u=0;s>u;u++)a[u]=r.slice(Math.ceil(u*h),Math.ceil((u+1)*h));return a}},function(t,e,r){"use strict";function n(t,e,r){this.shiftLen=t||i.SHIFT_LEN,this.length=e||a,this._path=r||0}Object.defineProperty(e,"__esModule",{value:!0}),e.Path=e.safePathSet=e.clearBitRange=e.pathSet=e.pathGet=e.bitSlice=e.LEVELS=void 0;var i=r(3),o=r(4),s=0,h=31,a=e.LEVELS=Math.floor(h/i.SHIFT_LEN),u=e.bitSlice=function(t,e,r){var n=Math.pow(2,e)-1;return(r&n)>>>t},l=e.pathGet=function(t,e,r){return u(t*e,t*(e+1),r)},c=e.pathSet=function(t,e,r,n){return r|n<<t*e},f=e.clearBitRange=function(t,e,r){var n=e-t,i=Math.pow(2,n)-1;return r&~(i<<t)},d=e.safePathSet=function(t,e,r,n){var i=f(t*e,t*(e+1),r);return c(t,e,i,n)};n.EMPTY_PATH=new n(i.SHIFT_LEN,a,s),n.from=function(t){for(var e=t.length,r=0,o=0;e>o;o++)r=c(i.SHIFT_LEN,o,r,t[o]);return new n(i.SHIFT_LEN,e,r)},(0,o.extend)(n.prototype,{get:function(t){return l(this.shiftLen,t,this._path)},equals:function(t){return this._path===t._path},clearAfter:function(t){for(var e=t+1,r=this;e<this.length;)r=r.set(e,0),e++;return r},toArray:function(){for(var t=new Array(this.length),e=0;e<this.length;e++)t[e]=this.get(e);return t},compareTo:function(t){var e=this._path,r=t._path;return e===r?0:r>e?-1:1},increment:function(t){var e=this.set(t,this.get(t)+1);return e.clearAfter(t)},decrement:function(t){return this.set(t,this.get(t)-1)},set:function(t,e){var r=d(this.shiftLen,t,this._path,e);return new n(this.shiftLen,this.length,r)}}),e.Path=n,e["default"]=n}]);

lib/binarysearch.js

@@ -6,9 +6,8 @@ "use strict";
 });
-exports.lte = lte;
-exports.gte = gte;
+exports.baseGte = baseGte;
 exports.eq = eq;
 // predicate should return true if we should go right.
-function lte(array, value, cmp) {
+function baseLte(inclusive, array, value, cmp) {
     var len = array.length;
-    if (len === 0 || !(cmp(array[0], value) <= 0)) {
+    if (len === 0 || !(inclusive ? cmp(array[0], value) <= 0 : cmp(array[0], value) < 0)) {
         return -1;
@@ -23,3 +22,4 @@ }
         var mid = r + l >>> 1;
-        if (cmp(array[mid], value) <= 0) {
+        var item = array[mid];
+        if (inclusive ? cmp(item, value) <= 0 : cmp(item, value) < 0) {
             // value at `mid` is less than or equal to `value`, go right.
@@ -36,6 +36,9 @@ l = mid;
 
+var lte = exports.lte = baseLte.bind(null, true);
+var lt = exports.lt = baseLte.bind(null, false);
+
 // predicate should return true if we should go left
-function gte(array, value, cmp) {
+function baseGte(inclusive, array, value, cmp) {
     var len = array.length;
-    if (len === 0 || !(cmp(array[len - 1], value) >= 0)) return len;
+    if (len === 0 || !(inclusive ? cmp(array[len - 1], value) >= 0 : cmp(array[len - 1], value) > 0)) return len;
     var l = -1;
@@ -45,3 +48,4 @@ var r = len - 1;
         var mid = r + l >>> 1;
-        if (cmp(array[mid], value) >= 0) {
+        var item = array[mid];
+        if (inclusive ? cmp(item, value) >= 0 : cmp(item, value) > 0) {
             // value at `mid` is less than or equal to `value`, go right.
@@ -58,2 +62,5 @@ r = mid;
 
+var gte = exports.gte = baseGte.bind(null, true);
+var gt = exports.gt = baseGte.bind(null, false);
+
 function eq(array, value, cmp) {
@@ -68,2 +75,4 @@ var idx = lte(array, value, cmp);
 exports.default = {
+    lt: lt,
+    gt: gt,
     lte: lte,
@@ -70,0 +79,0 @@ gte: gte,

lib/index.js

@@ -204,8 +204,11 @@ 'use strict';
     },
-    _baseBetween: function _baseBetween(extractor, _fromKey, _toKey) {
+    _baseBetween: function _baseBetween(extractor, _rangeSpec) {
         if (this.size === 0) return (0, _utils.getEmptyIterator)();
-        var fromKey = this.extractor ? this.extractor(_fromKey) : _fromKey;
 
-        var toKey = this.extractor ? this.extractor(_toKey) : _toKey;
+        var rangeSpec = (0, _utils.normalizeRangeSpec)(_rangeSpec);
 
+        var fromKey = this.extractor ? this.extractor(rangeSpec.from) : rangeSpec.from;
+
+        var toKey = this.extractor ? this.extractor(rangeSpec.to) : rangeSpec.to;
+
         var isReverse = this.comparator(fromKey, toKey) > 0;
@@ -216,4 +219,4 @@
 
-        var fromPath = this.findPath(fromKey, fromIsRight);
-        var toPath = this.findPath(toKey, toIsRight);
+        var fromPath = this.findPath(fromKey, fromIsRight, rangeSpec.fromInclusive);
+        var toPath = this.findPath(toKey, toIsRight, rangeSpec.toInclusive);
 
@@ -227,3 +230,13 @@ if (fromPath === null || toPath === null) {
     between: function between(fromKey, toKey) {
-        return this._baseBetween(extractEntry, fromKey, toKey);
+        if (arguments.length === 1) {
+            var rangeSpec = arguments[0];
+            return this._baseBetween(extractEntry, rangeSpec);
+        }
+
+        var spec = {
+            from: fromKey,
+            to: toKey
+        };
+
+        return this._baseBetween(extractEntry, spec);
     },
@@ -384,3 +397,3 @@
     },
-    findPath: function findPath(key, fromRight) {
+    findPath: function findPath(key, fromRight, isInclusive) {
         if (this.size === 0) return null;
@@ -407,4 +420,7 @@
 
+        var searchFuncName = (fromRight ? 'lt' : 'gt') + (isInclusive ? 'e' : '');
+        var searchFunc = _binarysearch2.default[searchFuncName];
+
         // curr should be a leaf now.
-        var idx = fromRight ? _binarysearch2.default.lte(curr.keys, key, cmp) : _binarysearch2.default.gte(curr.keys, key, cmp);
+        var idx = searchFunc(curr.keys, key, cmp);
 
@@ -489,8 +505,13 @@ if (idx === curr.keys.length) {
             return this._iterateAllWithExtractFn(extractor);
+        } else if (arguments.length === 1) {
+            var _spec = arguments[0];
+            this._baseBetween(extractor, _spec);
         }
 
-        var fromKey = arguments[0];
-        var toKey = arguments[1];
+        var spec = {
+            from: arguments[0],
+            to: arguments[1]
+        };
 
-        return this._baseBetween(extractor, fromKey, toKey);
+        return this._baseBetween(extractor, spec);
     };
@@ -497,0 +518,0 @@ };

lib/test/testBinarySearch.js

@@ -52,2 +52,18 @@ 'use strict';
 
+    it('lt', function () {
+        var idx = _binarysearch2.default.lt(arr, 13, _index.defaultComparator);
+        expect(idx).to.equal(0);
+
+        var idxtwo = _binarysearch2.default.lt(arr, 12, _index.defaultComparator);
+        expect(idxtwo).to.equal(0);
+
+        expect(_binarysearch2.default.lt(arr, 10, _index.defaultComparator)).to.equal(-1);
+
+        var idxthree = _binarysearch2.default.lt(arr, 9, _index.defaultComparator);
+        expect(idxthree).to.equal(-1);
+
+        var idxfour = _binarysearch2.default.lt(arr, 18, _index.defaultComparator);
+        expect(idxfour).to.equal(3);
+    });
+
     it('gte', function () {
@@ -65,2 +81,15 @@ var idx = _binarysearch2.default.gte(arr, 13, _index.defaultComparator);
     });
+
+    it('gt', function () {
+        var idx = _binarysearch2.default.gt(arr, 13, _index.defaultComparator);
+        expect(idx).to.equal(2);
+        var idxtwo = _binarysearch2.default.gt(arr, 12, _index.defaultComparator);
+        expect(idxtwo).to.equal(1);
+
+        var idxthree = _binarysearch2.default.gt(arr, 9, _index.defaultComparator);
+        expect(idxthree).to.equal(0);
+
+        var idxfour = _binarysearch2.default.gt(arr, 18, _index.defaultComparator);
+        expect(idxfour).to.equal(4); // Note: this returns array length.
+    });
 });

lib/test/testBTree.js

@@ -21,3 +21,3 @@ 'use strict';
 
-var _path = require('../path');
+var _path2 = require('../path');
 
@@ -292,3 +292,3 @@ var _constants = require('../constants');
             it('_pathNodes', function () {
-                var nodes = tree._pathNodes(_path.Path.from([0, 0]));
+                var nodes = tree._pathNodes(_path2.Path.from([0, 0]));
                 expect(nodes).to.have.lengthOf(2);
@@ -298,3 +298,3 @@ expect(nodes[0]).to.equal(tree.root);
 
-                var nodes2 = tree._pathNodes(_path.Path.from([0, 1]));
+                var nodes2 = tree._pathNodes(_path2.Path.from([0, 1]));
                 expect(nodes2).to.have.lengthOf(2);
@@ -304,3 +304,3 @@ expect(nodes2[0]).to.equal(tree.root);
 
-                var nodes3 = tree._pathNodes(_path.Path.from([1, 0]));
+                var nodes3 = tree._pathNodes(_path2.Path.from([1, 0]));
                 expect(nodes3).to.have.lengthOf(2);
@@ -332,7 +332,7 @@ expect(nodes3[0]).to.equal(tree.root);
             it('_getLeafFromPath', function () {
-                var path = _path.Path.from([0, 0]);
+                var path = _path2.Path.from([0, 0]);
                 var leaf = tree._getLeafFromPath(path);
                 expect(leaf).to.equal(tree.root.children[0]);
 
-                var path2 = _path.Path.from([1, 0]);
+                var path2 = _path2.Path.from([1, 0]);
                 var leaf2 = tree._getLeafFromPath(path2);
@@ -441,22 +441,44 @@ expect(leaf2).to.equal(tree.root.children[1]);
                 var isRight = true;
+                var isInclusive = true;
+                var isExclusive = false;
 
-                var path = tree.findPath(1, isLeft);
+                // Inclusive lookup from the left.
+                var path = tree.findPath(1, isLeft, isInclusive);
                 expect(path.toArray()).to.deep.equal([0, 0]);
 
-                var nonexistingPath = tree.findPath(0, isLeft);
+                // Exclusive lookup from the left.
+                var _path = tree.findPath(1, isLeft, isExclusive);
+                expect(_path.toArray()).to.deep.equal([1, 0]);
+
+                var nonexistingPath = tree.findPath(0, isLeft, isInclusive);
                 // Should return the leftmost path in this case.
                 expect(nonexistingPath.toArray()).to.deep.equal([0, 0]);
 
-                expect(tree.findPath(0, isRight)).to.be.null;
+                var _nonexistingPath = tree.findPath(0, isLeft, isExclusive);
+                // Should return the leftmost path when exclusive too.
+                expect(_nonexistingPath.toArray()).to.deep.equal([0, 0]);
 
-                var betweenKeys = tree.findPath(1.5, isLeft);
+                expect(tree.findPath(0, isRight, isInclusive)).to.be.null;
+                expect(tree.findPath(0, isRight, isExclusive)).to.be.null;
+
+                var betweenKeys = tree.findPath(1.5, isLeft, isInclusive);
                 expect(betweenKeys.toArray()).to.deep.equal([1, 0]);
 
-                var betweenKeys2 = tree.findPath(1.5, isRight);
+                var betweenKeysExclusive = tree.findPath(1.5, isLeft, isExclusive);
+                expect(betweenKeysExclusive.toArray()).to.deep.equal([1, 0]);
+
+                var betweenKeys2 = tree.findPath(1.5, isRight, isInclusive);
                 expect(betweenKeys2.toArray()).to.deep.equal([0, 0]);
 
-                var nonexistingPath2 = tree.findPath(4, isRight);
+                var betweenKeys2Exclusive = tree.findPath(1.5, isRight, isExclusive);
+                expect(betweenKeys2Exclusive.toArray()).to.deep.equal([0, 0]);
+
+                var nonexistingPath2 = tree.findPath(4, isRight, isInclusive);
                 expect(nonexistingPath2.toArray()).to.deep.equal([1, 1]);
 
-                expect(tree.findPath(4, isLeft)).to.be.null;
+                var nonexistingPath2Exclusive = tree.findPath(4, isRight, isExclusive);
+                expect(nonexistingPath2Exclusive.toArray()).to.deep.equal([1, 1]);
+
+                expect(tree.findPath(4, isLeft, isInclusive)).to.be.null;
+                expect(tree.findPath(4, isLeft, isExclusive)).to.be.null;
             });
@@ -463,0 +485,0 @@

lib/test/testIntegration.js

@@ -268,2 +268,36 @@ 'use strict';
 
+                it('works with exclusive specification', function () {
+                    var data = [];
+                    for (var i = 0; i < testSize; i++) {
+                        data.push([i, 'value' + i]);
+                    }
+
+                    var tree = _index.BTMap.from(data);
+
+                    assertTreeOrder(tree.order, tree);
+
+                    if (testSize === 0) {
+                        expect(Array.from(tree.between({
+                            from: 0,
+                            to: 10,
+                            fromInclusive: false,
+                            toInclusive: false
+                        })).length).to.equal(0);
+                    } else {
+                        var end = testSize - 2;
+                        var start = 0;
+                        if (end < start) {
+                            end = start;
+                        }
+                        var n = end - start + 1;
+                        var result = Array.from(tree.between({
+                            from: start,
+                            to: end,
+                            fromInclusive: false,
+                            toInclusive: false
+                        }));
+                        expect(result.length).to.equal(n - 2);
+                    }
+                });
+
                 it('works when boundaries are outside keys', function () {
@@ -270,0 +304,0 @@ var data = [];

lib/utils.js

@@ -26,2 +26,3 @@ 'use strict';
 exports.isSet = isSet;
+exports.normalizeRangeSpec = normalizeRangeSpec;
 
@@ -246,2 +247,11 @@ var _constants = require('./constants');
     return !!ref.value;
+}
+
+function normalizeRangeSpec(spec) {
+    return {
+        from: spec.from,
+        to: spec.to,
+        fromInclusive: spec.hasOwnProperty('fromInclusive') ? spec.fromInclusive : true,
+        toInclusive: spec.hasOwnProperty('toInclusive') ? spec.toInclusive : true
+    };
 }

package.json

 {
   "name": "ibtree",
-  "version": "0.2.0",
+  "version": "0.3.0",
   "description": "A performant, in-memory, immutable B+ tree data structure",
@@ -5,0 +5,0 @@ "main": "lib/index.js",

README.md

@@ -52,3 +52,3 @@ ibtree
 Array.from(map.values())
-// ['one', 'two', 'three', 'four', 'give', 'six', 'seven']
+// ['one', 'two', 'three', 'four', 'five', 'six', 'seven']
 ```
@@ -65,3 +65,3 @@
 // true
-set.has(4)
+set.has(0)
 // false
@@ -77,2 +77,4 @@ set = set.add(0);
 // [2, 3]
+ 
+// Reverse range search when first argument is larger than the second.
 Array.from(map.values(2, -10));
@@ -90,2 +92,11 @@ // [2, 1, 0]
 
+### Summary
+
+- On additions, `ibtree` fares better than `Immutable.Map` on small and large N (10 and 100000), `Immutable.Map` is faster on mid-size (1000).
+- On deletions, `ibtree` is ~50% slower than `Immutable.Map`.
+- On single key search, `ibtree` is slower on a mid-size N (1000) but faster on a larger N (100000) than `Immutable.Map`.
+- On range search, `ibtree` is considerably faster than `Immutable.Map`.
+
+### Detailed Results
+
 **These are relative, not absolute benchmarks. The benchmark implementation uses an adapter to interface with both Immutable and ibtree, which introduces a small overhead.**
@@ -320,8 +331,38 @@
 
-The key benefit of B+ trees is the fast range search. Range searches extend the `entries`, `values` and `keys` instance methods to accept two arguments that specify the range boundaries.
+The key benefit of B+ trees is the fast range search. Range searches extend the `entries`, `values` and `keys` instance methods to accept a specification for the range boundaries that specify the range boundaries.
 
-- `entries([any fromKey, any toKey])` (also alias `entryRange`)
-- `values([any fromKey, any toKey])` (also alias `valueRange`)
-- `keys([any fromKey, any toKey])` (also alias `keyRange`)
+There are two ways to specify the boundaries -- an object specification or `from` and `to` keys.
 
+The object specification looks like this:
+
+```javascript
+tree.entries({
+  from: 5, // required
+  to: 10, // required
+  fromInclusive: true, // optional, default: true
+  toInclusive: false, // optional, default: true
+});
+```
+
+The two-key specification looks like this:
+
+```javascript
+tree.entries(20, 50);
+```
+
+and is equivalent to
+
+```javascript
+tree.entries({
+  from: 20, // required
+  to: 50, // required
+  // fromInclusive defaults to true
+  // toInclusive defaults to true
+});
+```
+
+- `entries([any fromKeyOrRangeSpec[, any toKey]])` (also alias `entryRange`)
+- `values([any fromKeyOrRangeSpec[, any toKey]])` (also alias `valueRange`)
+- `keys([any fromKeyOrRangeSpec[, any toKey]])` (also alias `keyRange`)
+
 If these functions are called with zero arguments, they iterate through all the elements in order, just like the corresponding native Map and Set methods.
@@ -333,3 +374,3 @@
 
-All these methods return an iterator for elements whose keys satisfy `fromKey <= key <= toKey`. The order of iteration is decided by comparing `fromKey` and `toKey`. If `fromKey` > `toKey` according to the instance's comparator, the iteration will be performed in reverse.
+The order of iteration is decided by comparing `fromKey` and `toKey`. If `fromKey` > `toKey` according to the instance's comparator, the iteration will be performed in reverse.
 
@@ -336,0 +377,0 @@ ```javascript

src/binarysearch.js

 // predicate should return true if we should go right.
-export function lte(array, value, cmp) {
+function baseLte(inclusive, array, value, cmp) {
     const len = array.length;
-    if (len === 0 || !(cmp(array[0], value) <= 0)) {
+    if (len === 0 || !(inclusive ? cmp(array[0], value) <= 0 : cmp(array[0], value) < 0)) {
         return - 1;
@@ -14,3 +14,4 @@ }
         const mid = (r + l) >>> 1;
-        if (cmp(array[mid], value) <= 0) {
+        const item = array[mid];
+        if (inclusive ? cmp(item, value) <= 0 : cmp(item, value) < 0) {
             // value at `mid` is less than or equal to `value`, go right.
@@ -27,6 +28,9 @@ l = mid;
 
+export const lte = baseLte.bind(null, true);
+export const lt = baseLte.bind(null, false);
+
 // predicate should return true if we should go left
-export function gte(array, value, cmp) {
+export function baseGte(inclusive, array, value, cmp) {
     const len = array.length;
-    if (len === 0 || !(cmp(array[len - 1], value) >= 0)) return len;
+    if (len === 0 || !(inclusive ? cmp(array[len - 1], value) >= 0 : cmp(array[len - 1], value) > 0)) return len;
     let l = -1;
@@ -36,3 +40,4 @@ let r = len - 1;
         const mid = (r + l) >>> 1;
-        if (cmp(array[mid], value) >= 0) {
+        const item = array[mid];
+        if (inclusive ? cmp(item, value) >= 0 : cmp(item, value) > 0) {
             // value at `mid` is less than or equal to `value`, go right.
@@ -49,2 +54,5 @@ r = mid;
 
+export const gte = baseGte.bind(null, true);
+export const gt = baseGte.bind(null, false);
+
 export function eq(array, value, cmp) {
@@ -59,2 +67,4 @@ const idx = lte(array, value, cmp);
 export default {
+    lt,
+    gt,
     lte,
@@ -61,0 +71,0 @@ gte,

src/index.js

@@ -14,2 +14,3 @@ import binarySearch from './binarysearch';
     isSet,
+    normalizeRangeSpec,
 } from './utils';
@@ -222,11 +223,14 @@ import {
 
-    _baseBetween(extractor, _fromKey, _toKey) {
+    _baseBetween(extractor, _rangeSpec) {
         if (this.size === 0) return getEmptyIterator();
+
+        const rangeSpec = normalizeRangeSpec(_rangeSpec);
+
         const fromKey = this.extractor
-            ? this.extractor(_fromKey)
-            : _fromKey;
+            ? this.extractor(rangeSpec.from)
+            : rangeSpec.from;
 
         const toKey = this.extractor
-            ? this.extractor(_toKey)
-            : _toKey;
+            ? this.extractor(rangeSpec.to)
+            : rangeSpec.to;
 
@@ -238,4 +242,4 @@ const isReverse = this.comparator(fromKey, toKey) > 0;
 
-        const fromPath = this.findPath(fromKey, fromIsRight);
-        const toPath = this.findPath(toKey, toIsRight);
+        const fromPath = this.findPath(fromKey, fromIsRight, rangeSpec.fromInclusive);
+        const toPath = this.findPath(toKey, toIsRight, rangeSpec.toInclusive);
 
@@ -255,3 +259,13 @@ if (fromPath === null || toPath === null) {
     between(fromKey, toKey) {
-        return this._baseBetween(extractEntry, fromKey, toKey);
+        if (arguments.length === 1) {
+            const rangeSpec = arguments[0];
+            return this._baseBetween(extractEntry, rangeSpec);
+        }
+
+        const spec = {
+            from: fromKey,
+            to: toKey,
+        };
+
+        return this._baseBetween(extractEntry, spec);
     },
@@ -420,3 +434,3 @@
 
-    findPath(key, fromRight) {
+    findPath(key, fromRight, isInclusive) {
         if (this.size === 0) return null;
@@ -443,6 +457,7 @@
 
+        const searchFuncName = (fromRight ? 'lt' : 'gt') + (isInclusive ? 'e' : '');
+        const searchFunc = binarySearch[searchFuncName];
+
         // curr should be a leaf now.
-        const idx = fromRight
-            ? binarySearch.lte(curr.keys, key, cmp)
-            : binarySearch.gte(curr.keys, key, cmp);
+        const idx = searchFunc(curr.keys, key, cmp);
 
@@ -532,8 +547,16 @@ if (idx === curr.keys.length) {
             return this._iterateAllWithExtractFn(extractor);
+        } else if (arguments.length === 1) {
+            const spec = arguments[0];
+            this._baseBetween(
+                extractor,
+                spec
+            );
         }
 
-        const fromKey = arguments[0];
-        const toKey = arguments[1];
+        const spec = {
+            from: arguments[0],
+            to: arguments[1],
+        };
 
-        return this._baseBetween(extractor, fromKey, toKey);
+        return this._baseBetween(extractor, spec);
     };
@@ -540,0 +563,0 @@

src/test/testBinarySearch.js

@@ -40,2 +40,18 @@ import chai from 'chai';
 
+    it('lt', () => {
+        const idx = binarySearch.lt(arr, 13, defaultComparator);
+        expect(idx).to.equal(0);
+
+        const idxtwo = binarySearch.lt(arr, 12, defaultComparator);
+        expect(idxtwo).to.equal(0);
+
+        expect(binarySearch.lt(arr, 10, defaultComparator)).to.equal(-1);
+
+        const idxthree = binarySearch.lt(arr, 9, defaultComparator);
+        expect(idxthree).to.equal(-1);
+
+        const idxfour = binarySearch.lt(arr, 18, defaultComparator);
+        expect(idxfour).to.equal(3);
+    });
+
     it('gte', () => {
@@ -53,2 +69,15 @@ const idx = binarySearch.gte(arr, 13, defaultComparator);
     });
+
+    it('gt', () => {
+        const idx = binarySearch.gt(arr, 13, defaultComparator);
+        expect(idx).to.equal(2);
+        const idxtwo = binarySearch.gt(arr, 12, defaultComparator);
+        expect(idxtwo).to.equal(1);
+
+        const idxthree = binarySearch.gt(arr, 9, defaultComparator);
+        expect(idxthree).to.equal(0);
+
+        const idxfour = binarySearch.gt(arr, 18, defaultComparator);
+        expect(idxfour).to.equal(4); // Note: this returns array length.
+    });
 });

src/test/testBTree.js

@@ -405,22 +405,44 @@ import chai from 'chai';
                 const isRight = true;
+                const isInclusive = true;
+                const isExclusive = false;
 
-                const path = tree.findPath(1, isLeft);
+                // Inclusive lookup from the left.
+                const path = tree.findPath(1, isLeft, isInclusive);
                 expect(path.toArray()).to.deep.equal([0, 0]);
 
-                const nonexistingPath = tree.findPath(0, isLeft);
+                // Exclusive lookup from the left.
+                const _path = tree.findPath(1, isLeft, isExclusive);
+                expect(_path.toArray()).to.deep.equal([1, 0]);
+
+                const nonexistingPath = tree.findPath(0, isLeft, isInclusive);
                 // Should return the leftmost path in this case.
                 expect(nonexistingPath.toArray()).to.deep.equal([0, 0]);
 
-                expect(tree.findPath(0, isRight)).to.be.null;
+                const _nonexistingPath = tree.findPath(0, isLeft, isExclusive);
+                // Should return the leftmost path when exclusive too.
+                expect(_nonexistingPath.toArray()).to.deep.equal([0, 0]);
 
-                const betweenKeys = tree.findPath(1.5, isLeft);
+                expect(tree.findPath(0, isRight, isInclusive)).to.be.null;
+                expect(tree.findPath(0, isRight, isExclusive)).to.be.null;
+
+                const betweenKeys = tree.findPath(1.5, isLeft, isInclusive);
                 expect(betweenKeys.toArray()).to.deep.equal([1, 0]);
 
-                const betweenKeys2 = tree.findPath(1.5, isRight);
+                const betweenKeysExclusive = tree.findPath(1.5, isLeft, isExclusive);
+                expect(betweenKeysExclusive.toArray()).to.deep.equal([1, 0]);
+
+                const betweenKeys2 = tree.findPath(1.5, isRight, isInclusive);
                 expect(betweenKeys2.toArray()).to.deep.equal([0, 0]);
 
-                const nonexistingPath2 = tree.findPath(4, isRight);
+                const betweenKeys2Exclusive = tree.findPath(1.5, isRight, isExclusive);
+                expect(betweenKeys2Exclusive.toArray()).to.deep.equal([0, 0]);
+
+                const nonexistingPath2 = tree.findPath(4, isRight, isInclusive);
                 expect(nonexistingPath2.toArray()).to.deep.equal([1, 1]);
 
-                expect(tree.findPath(4, isLeft)).to.be.null;
+                const nonexistingPath2Exclusive = tree.findPath(4, isRight, isExclusive);
+                expect(nonexistingPath2Exclusive.toArray()).to.deep.equal([1, 1]);
+
+                expect(tree.findPath(4, isLeft, isInclusive)).to.be.null;
+                expect(tree.findPath(4, isLeft, isExclusive)).to.be.null;
             });
@@ -427,0 +449,0 @@

src/test/testIntegration.js

@@ -240,2 +240,36 @@ import head from 'ramda/src/head';
 
+                it('works with exclusive specification', () => {
+                    const data = [];
+                    for (let i = 0; i < testSize; i++) {
+                        data.push([i, `value${i}`]);
+                    }
+
+                    const tree = BTMap.from(data);
+
+                    assertTreeOrder(tree.order, tree);
+
+                    if (testSize === 0) {
+                        expect(Array.from(tree.between({
+                            from: 0,
+                            to: 10,
+                            fromInclusive: false,
+                            toInclusive: false,
+                        })).length).to.equal(0);
+                    } else {
+                        let end = testSize - 2;
+                        const start = 0;
+                        if (end < start) {
+                            end = start;
+                        }
+                        const n = end - start + 1;
+                        const result = Array.from(tree.between({
+                            from: start,
+                            to: end,
+                            fromInclusive: false,
+                            toInclusive: false,
+                        }));
+                        expect(result.length).to.equal(n - 2);
+                    }
+                });
+
                 it('works when boundaries are outside keys', () => {
@@ -242,0 +276,0 @@ const data = [];

src/utils.js

@@ -220,1 +220,14 @@ import {
 }
+
+export function normalizeRangeSpec(spec) {
+    return {
+        from: spec.from,
+        to: spec.to,
+        fromInclusive: spec.hasOwnProperty('fromInclusive')
+            ? spec.fromInclusive
+            : true,
+        toInclusive: spec.hasOwnProperty('toInclusive')
+            ? spec.toInclusive
+            : true,
+    };
+}

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

135309019

increased by20.26%

Lines of code

6596

increased by3.22%

Number of lines in readme file

395

increased by11.58%

No dependency changes