sorted-btree - npm Package Compare versions

Comparing version 1.4.0 to 1.5.0

b+tree.d.ts

@@ -8,8 +8,37 @@ import { ISortedMap, ISortedMapF } from './interfaces';
 };
-/** Compares two numbers, strings, arrays of numbers/strings, Dates,
- *  or objects that have a valueOf() method returning a number or string.
- *  Optimized for numbers. Returns 1 if a>b, -1 if a<b, and 0 if a===b.
+/**
+ * Types that BTree supports by default
  */
-export declare function defaultComparator(a: any, b: any): number;
+export declare type DefaultComparable = number | string | Date | boolean | null | undefined | (number | string)[] | {
+    valueOf: () => number | string | Date | boolean | null | undefined | (number | string)[];
+};
 /**
+ * Compares DefaultComparables to form a strict partial ordering.
+ *
+ * Handles +/-0 and NaN like Map: NaN is equal to NaN, and -0 is equal to +0.
+ *
+ * Arrays are compared using '<' and '>', which may cause unexpected equality:
+ * for example [1] will be considered equal to ['1'].
+ *
+ * Two objects with equal valueOf compare the same, but compare unequal to
+ * primitives that have the same value.
+ */
+export declare function defaultComparator(a: DefaultComparable, b: DefaultComparable): number;
+/**
+ * Compares items using the < and > operators. This function is probably slightly
+ * faster than the defaultComparator for Dates and strings, but has not been benchmarked.
+ * Unlike defaultComparator, this comparator doesn't support mixed types correctly,
+ * i.e. use it with `BTree<string>` or `BTree<number>` but not `BTree<string|number>`.
+ *
+ * NaN is not supported.
+ *
+ * Note: null is treated like 0 when compared with numbers or Date, but in general
+ *   null is not ordered with respect to strings (neither greater nor less), and
+ *   undefined is not ordered with other types.
+ */
+export declare function simpleComparator(a: string, b: string): number;
+export declare function simpleComparator(a: number | null, b: number | null): number;
+export declare function simpleComparator(a: Date | null, b: Date | null): number;
+export declare function simpleComparator(a: (number | string)[], b: (number | string)[]): number;
+/**
  * A reasonably fast collection of key-value pairs with a powerful API.
@@ -82,2 +111,6 @@ * Largely compatible with the standard Map. BTree is a B+ tree data structure,
     _maxNodeSize: number;
+    /**
+     * provides a total order over keys (and a strict partial order over the type K)
+     * @returns a negative value if a < b, 0 if a === b and a positive value if a > b
+     */
     _compare: (a: K, b: K) => number;
@@ -87,3 +120,3 @@ /**
      * @param compare Custom function to compare pairs of elements in the tree.
-     *   This is not required for numbers, strings and arrays of numbers/strings.
+     *   If not specified, defaultComparator will be used which is valid as long as K extends DefaultComparable.
      * @param entries A set of key-value pairs to initialize the tree
@@ -227,2 +260,38 @@ * @param maxNodeSize Branching factor (maximum items or children per node)
     private findPath;
+    /**
+     * Computes the differences between `this` and `other`.
+     * For efficiency, the diff is returned via invocations of supplied handlers.
+     * The computation is optimized for the case in which the two trees have large amounts
+     * of shared data (obtained by calling the `clone` or `with` APIs) and will avoid
+     * any iteration of shared state.
+     * The handlers can cause computation to early exit by returning {break: R}.
+     * Neither of the collections should be changed during the comparison process (in your callbacks), as this method assumes they will not be mutated.
+     * @param other The tree to compute a diff against.
+     * @param onlyThis Callback invoked for all keys only present in `this`.
+     * @param onlyOther Callback invoked for all keys only present in `other`.
+     * @param different Callback invoked for all keys with differing values.
+     */
+    diffAgainst<R>(other: BTree<K, V>, onlyThis?: (k: K, v: V) => {
+        break?: R;
+    } | void, onlyOther?: (k: K, v: V) => {
+        break?: R;
+    } | void, different?: (k: K, vThis: V, vOther: V) => {
+        break?: R;
+    } | void): R | undefined;
+    private static finishCursorWalk;
+    private static stepToEnd;
+    private static makeDiffCursor;
+    /**
+     * Advances the cursor to the next step in the walk of its tree.
+     * Cursors are walked backwards in sort order, as this allows them to leverage maxKey() in order to be compared in O(1).
+     * @param cursor The cursor to step
+     * @param stepToNode If true, the cursor will be advanced to the next node (skipping values)
+     * @returns true if the step was completed and false if the step would have caused the cursor to move beyond the end of the tree.
+     */
+    private static step;
+    /**
+     * Compares the two cursors. Returns a value indicating which cursor is ahead in a walk.
+     * Note that cursors are advanced in reverse sorting order.
+     */
+    private static compare;
     /** Returns a new iterator for iterating the keys of each pair in ascending order.
@@ -229,0 +298,0 @@ *  @param firstKey: Minimum key to include in the output. */

b+tree.min.js

@@ -1,1 +0,1 @@
-"use strict";var __extends=this&&this.__extends||function(){var i=function(e,t){return(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])})(e,t)};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 defaultComparator(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(exports,"__esModule",{value:!0}),exports.EmptyBTree=exports.defaultComparator=void 0,exports.defaultComparator=defaultComparator;var BTree=function(){function r(e,t,r){this._root=EmptyLeaf,this._size=0,this._maxNodeSize=4<=r?Math.min(r,256):32,this._compare=t||defaultComparator,e&&this.setPairs(e)}return Object.defineProperty(r.prototype,"size",{get:function(){return this._size},enumerable:!1,configurable:!0}),Object.defineProperty(r.prototype,"length",{get:function(){return this._size},enumerable:!1,configurable:!0}),Object.defineProperty(r.prototype,"isEmpty",{get:function(){return 0===this._size},enumerable:!1,configurable:!0}),r.prototype.clear=function(){this._root=EmptyLeaf,this._size=0},r.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)})},r.prototype.forEachPair=function(e,t){var r=this.minKey(),i=this.maxKey();return this.forRange(r,i,!0,e,t)},r.prototype.get=function(e,t){return this._root.get(e,t,this)},r.prototype.set=function(e,t,r){this._root.isShared&&(this._root=this._root.clone());r=this._root.set(e,t,r,this);return!0===r||!1===r?r:(this._root=new BNodeInternal([this._root,r]),!0)},r.prototype.has=function(e){return 0!==this.forRange(e,e,!0,void 0)},r.prototype.delete=function(e){return 0!==this.editRange(e,e,!0,DeleteRange)},r.prototype.with=function(e,t,r){var i=this.clone();return i.set(e,t,r)||r?i:this},r.prototype.withPairs=function(e,t){var r=this.clone();return 0!==r.setPairs(e,t)||t?r:this},r.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},r.prototype.without=function(e,t){return this.withoutRange(e,e,!0,t)},r.prototype.withoutKeys=function(e,t){var r=this.clone();return r.deleteKeys(e)||!t?r:this},r.prototype.withoutRange=function(e,t,r,i){var n=this.clone();return 0===n.deleteRange(e,t,r)&&i?this:n},r.prototype.filter=function(i,e){var n,t=this.greedyClone();return t.editAll(function(e,t,r){if(!i(e,t,r))return n=Delete}),!n&&e?this:t},r.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},r.prototype.reduce=function(e,t){for(var r,i=0,n=t,o=this.entries(this.minKey(),ReusedArray);!(r=o.next()).done;)n=e(n,r.value,i++,this);return n},r.prototype.entries=function(e,t){var r=this.findPath(e);if(void 0===r)return iterator();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 iterator(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}}})},r.prototype.entriesReversed=function(e,t,r){if(void 0===e&&(r=void 0)===(e=this.maxKey()))return iterator();var i=this.findPath(e)||this.findPath(this.maxKey()),n=i.nodequeue,o=i.nodeindex,s=i.leaf;check(!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 iterator(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}}})},r.prototype.findPath=function(e){var t,r,i=this._root;if(i.isLeaf)r=t=EmptyArray;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}},r.prototype.keys=function(e){var t=this.entries(e,ReusedArray);return iterator(function(){var e=t.next();return e.value&&(e.value=e.value[0]),e})},r.prototype.values=function(e){var t=this.entries(e,ReusedArray);return iterator(function(){var e=t.next();return e.value&&(e.value=e.value[1]),e})},Object.defineProperty(r.prototype,"maxNodeSize",{get:function(){return this._maxNodeSize},enumerable:!1,configurable:!0}),r.prototype.minKey=function(){return this._root.minKey()},r.prototype.maxKey=function(){return this._root.maxKey()},r.prototype.clone=function(){this._root.isShared=!0;var e=new r(void 0,this._compare,this._maxNodeSize);return e._root=this._root,e._size=this._size,e},r.prototype.greedyClone=function(e){var t=new r(void 0,this._compare,this._maxNodeSize);return t._root=this._root.greedyClone(e),t._size=this._size,t},r.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):[]},r.prototype.keysArray=function(){var r=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(e,t){r.push(e)}),r},r.prototype.valuesArray=function(){var r=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(e,t){r.push(t)}),r},r.prototype.toString=function(){return this.toArray().toString()},r.prototype.setIfNotPresent=function(e,t){return this.set(e,t,!1)},r.prototype.nextHigherPair=function(e){var t=this.entries(e,ReusedArray),r=t.next();return!r.done&&void 0!==e&&this._compare(r.value[0],e)<=0&&(r=t.next()),r.value},r.prototype.nextHigherKey=function(e){e=this.nextHigherPair(e);return e&&e[0]},r.prototype.nextLowerPair=function(e){return this.entriesReversed(e,ReusedArray,!0).next().value},r.prototype.nextLowerKey=function(e){e=this.nextLowerPair(e);return e&&e[0]},r.prototype.changeIfPresent=function(e,r){return 0!==this.editRange(e,e,!0,function(e,t){return{value:r}})},r.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?Break:void 0}),n},r.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},r.prototype.forRange=function(e,t,r,i,n){i=this._root.forRange(e,t,r,!1,this,n||0,i);return"number"==typeof i?i:i.break},r.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?EmptyLeaf:o.children[0]}},r.prototype.editAll=function(e,t){return this.editRange(this.minKey(),this.maxKey(),!0,e,t)},r.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,DeleteRange)},r.prototype.deleteKeys=function(e){for(var t=0,r=0;t<e.length;t++)this.delete(e[t])&&r++;return r},Object.defineProperty(r.prototype,"height",{get:function(){for(var e=this._root,t=-1;null!=e;t++)e=e.children;return t},enumerable:!1,configurable:!0}),r.prototype.freeze=function(){this.clear=this.set=this.editRange=function(){throw new Error("Attempted to modify a frozen BTree")}},r.prototype.unfreeze=function(){delete this.clear,delete this.set,delete this.editRange},Object.defineProperty(r.prototype,"isFrozen",{get:function(){return this.hasOwnProperty("editRange")},enumerable:!1,configurable:!0}),r.prototype.checkValid=function(){var e=this._root.checkValid(0,this,0);check(e===this.size,"size mismatch: counted ",e,"but stored",this.size)},r}();function iterator(e){void 0===e&&(e=function(){return{done:!0,value:void 0}});e={next:e};return Symbol&&Symbol.iterator&&(e[Symbol.iterator]=function(){return this}),e}exports.default=BTree,Symbol&&Symbol.iterator&&(BTree.prototype[Symbol.iterator]=BTree.prototype.entries),BTree.prototype.where=BTree.prototype.filter,BTree.prototype.setRange=BTree.prototype.setPairs,BTree.prototype.add=BTree.prototype.set;var BNode=function(){function t(e,t){void 0===e&&(e=[]),this.keys=e,this.values=t||undefVals,this.isShared=void 0}return Object.defineProperty(t.prototype,"isLeaf",{get:function(){return void 0===this.children},enumerable:!1,configurable:!0}),t.prototype.maxKey=function(){return this.keys[this.keys.length-1]},t.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},t.prototype.minKey=function(){return this.keys[0]},t.prototype.clone=function(){var e=this.values;return new t(this.keys.slice(0),e===undefVals?e:e.slice(0))},t.prototype.greedyClone=function(e){return this.isShared&&!e?this:this.clone()},t.prototype.get=function(e,t,r){r=this.indexOf(e,-1,r._compare);return r<0?t:this.values[r]},t.prototype.checkValid=function(e,t,r){var i=this.keys.length,n=this.values.length;return check(this.values===undefVals?i<=n:i===n,"keys/values length mismatch: depth",e,"with lengths",i,n,"and baseIndex",r),check(0==e||0<i,"empty leaf at depth",e,"and baseIndex",r),i},t.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},t.prototype.reifyValues=function(){return this.values===undefVals?this.values=this.values.slice(0,this.keys.length):this.values},t.prototype.insertInLeaf=function(e,t,r,i){if(this.keys.splice(e,0,t),this.values===undefVals){for(;undefVals.length<i._maxNodeSize;)undefVals.push(void 0);if(void 0===r)return!0;this.values=undefVals.slice(0,this.keys.length-1)}return this.values.splice(e,0,r),!0},t.prototype.takeFromRight=function(e){var t=this.values;e.values===undefVals?t!==undefVals&&t.push(void 0):(t=this.reifyValues()).push(e.values.shift()),this.keys.push(e.keys.shift())},t.prototype.takeFromLeft=function(e){var t=this.values;e.values===undefVals?t!==undefVals&&t.unshift(void 0):(t=this.reifyValues()).unshift(e.values.pop()),this.keys.unshift(e.keys.pop())},t.prototype.splitOffRightSide=function(){var e=this.keys.length>>1;return new t(this.keys.splice(e),this.values===undefVals?undefVals:this.values.splice(e))},t.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!==undefVals&&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},t.prototype.mergeSibling=function(e,t){if(this.keys.push.apply(this.keys,e.keys),this.values===undefVals){if(e.values===undefVals)return;this.values=this.values.slice(0,this.keys.length)}this.values.push.apply(this.values,e.reifyValues())},t}(),BNodeInternal=function(n){function i(e,t){var r=this;if(!t){t=[];for(var i=0;i<e.length;i++)t[i]=e[i].maxKey()}return(r=n.call(this,t)||this).children=e,r}return __extends(i,n),i.prototype.clone=function(){for(var e=this.children.slice(0),t=0;t<e.length;t++)e[t].isShared=!0;return new i(e,this.keys.slice(0))},i.prototype.greedyClone=function(e){if(this.isShared&&!e)return this;for(var t=new i(this.children.slice(0),this.keys.slice(0)),r=0;r<t.children.length;r++)t.children[r]=t.children[r].greedyClone();return t},i.prototype.minKey=function(){return this.children[0].minKey()},i.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},i.prototype.checkValid=function(e,t,r){var i=this.keys.length,n=this.children.length;check(i===n,"keys/children length mismatch: depth",e,"lengths",i,n,"baseIndex",r),check(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),check((a+=s[u].keys.length)<=o,"wtf",r),check(0===u||s[u-1].constructor===s[u].constructor,"type mismatch, baseIndex:",r),s[u].maxKey()!=h[u]&&check(!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||check(!1,"sort violation at depth",e,"index",u,"keys",h[u-1],h[u]);i=0===a;return(i||a>t.maxNodeSize*n)&&check(!1,i?"too few":"too many","children (",a,o,") at depth",e,"maxNodeSize:",t.maxNodeSize,"children.length:",n,"baseIndex:",r),o},i.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()));i=u.set(e,t,r,i);if(!1===i)return!1;if(this.keys[a]=u.maxKey(),!0===i)return!0;if(this.keys.length<s)return this.insert(a+1,i),!0;u=this.splitOffRightSide(),s=this;return 0<h(i.maxKey(),this.maxKey())&&(s=u,a-=this.keys.length),s.insert(a+1,i),u},i.prototype.insert=function(e,t){this.children.splice(e,0,t),this.keys.splice(e,0,t.maxKey())},i.prototype.splitOffRightSide=function(){var e=this.children.length>>1;return new i(this.children.splice(e),this.keys.splice(e))},i.prototype.takeFromRight=function(e){this.keys.push(e.keys.shift()),this.children.push(e.children.shift())},i.prototype.takeFromLeft=function(e){this.keys.unshift(e.keys.pop()),this.children.unshift(e.children.pop())},i.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&&check(!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},i.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)},i.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)},i}(BNode),undefVals=[],Delete={delete:!0},DeleteRange=function(){return Delete},Break={break:!0},EmptyLeaf=function(){var e=new BNode;return e.isShared=!0,e}(),EmptyArray=[],ReusedArray=[];function check(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(" "))}exports.EmptyBTree=function(){var e=new BTree;return e.freeze(),e}();
+"use strict";var __extends=this&&this.__extends||function(){var i=function(e,t){return(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])})(e,t)};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 defaultComparator(e,t){if(Number.isFinite(e)&&Number.isFinite(t))return e-t;var r=typeof e,i=typeof t;if(r!==i)return r<i?-1:1;if("object"===r){if(null===e)return null===t?0:-1;if(null===t)return 1;if((r=typeof(e=e.valueOf()))!==(i=typeof(t=t.valueOf())))return r<i?-1:1}return e<t?-1:t<e?1:e===t?0:Number.isNaN(e)?Number.isNaN(t)?0:-1:Number.isNaN(t)?1:Array.isArray(e)?0:Number.NaN}function simpleComparator(e,t){return t<e?1:e<t?-1:0}Object.defineProperty(exports,"__esModule",{value:!0}),exports.EmptyBTree=exports.simpleComparator=exports.defaultComparator=void 0,exports.defaultComparator=defaultComparator,exports.simpleComparator=simpleComparator;var BTree=function(){function x(e,t,r){this._root=EmptyLeaf,this._size=0,this._maxNodeSize=4<=r?Math.min(r,256):32,this._compare=t||defaultComparator,e&&this.setPairs(e)}return Object.defineProperty(x.prototype,"size",{get:function(){return this._size},enumerable:!1,configurable:!0}),Object.defineProperty(x.prototype,"length",{get:function(){return this._size},enumerable:!1,configurable:!0}),Object.defineProperty(x.prototype,"isEmpty",{get:function(){return 0===this._size},enumerable:!1,configurable:!0}),x.prototype.clear=function(){this._root=EmptyLeaf,this._size=0},x.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)})},x.prototype.forEachPair=function(e,t){var r=this.minKey(),i=this.maxKey();return this.forRange(r,i,!0,e,t)},x.prototype.get=function(e,t){return this._root.get(e,t,this)},x.prototype.set=function(e,t,r){this._root.isShared&&(this._root=this._root.clone());r=this._root.set(e,t,r,this);return!0===r||!1===r?r:(this._root=new BNodeInternal([this._root,r]),!0)},x.prototype.has=function(e){return 0!==this.forRange(e,e,!0,void 0)},x.prototype.delete=function(e){return 0!==this.editRange(e,e,!0,DeleteRange)},x.prototype.with=function(e,t,r){var i=this.clone();return i.set(e,t,r)||r?i:this},x.prototype.withPairs=function(e,t){var r=this.clone();return 0!==r.setPairs(e,t)||t?r:this},x.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},x.prototype.without=function(e,t){return this.withoutRange(e,e,!0,t)},x.prototype.withoutKeys=function(e,t){var r=this.clone();return r.deleteKeys(e)||!t?r:this},x.prototype.withoutRange=function(e,t,r,i){var n=this.clone();return 0===n.deleteRange(e,t,r)&&i?this:n},x.prototype.filter=function(i,e){var n,t=this.greedyClone();return t.editAll(function(e,t,r){if(!i(e,t,r))return n=Delete}),!n&&e?this:t},x.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},x.prototype.reduce=function(e,t){for(var r,i=0,n=t,o=this.entries(this.minKey(),ReusedArray);!(r=o.next()).done;)n=e(n,r.value,i++,this);return n},x.prototype.entries=function(e,t){var r=this.findPath(e);if(void 0===r)return iterator();var i=r.nodequeue,n=r.nodeindex,o=r.leaf,s=void 0!==t?1:0,a=void 0===e?-1:o.indexOf(e,0,this._compare)-1;return iterator(function(){e:for(;;)switch(s){case 0:if(++a<o.keys.length)return{done:!1,value:[o.keys[a],o.values[a]]};s=2;continue;case 1:if(++a<o.keys.length)return t[0]=o.keys[a],t[1]=o.values[a],{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]],a=-1,s=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},x.prototype.entriesReversed=function(e,t,r){if(void 0===e&&(r=void 0)===(e=this.maxKey()))return iterator();var i=this.findPath(e)||this.findPath(this.maxKey()),n=i.nodequeue,o=i.nodeindex,s=i.leaf;check(!n[0]||s===n[0][o[0]],"wat!");var a=s.indexOf(e,0,this._compare);r||0<this._compare(s.keys[a],e)||a++;var h=void 0!==t?1:0;return iterator(function(){e:for(;;)switch(h){case 0:if(0<=--a)return{done:!1,value:[s.keys[a],s.values[a]]};h=2;continue;case 1:if(0<=--a)return t[0]=s.keys[a],t[1]=s.values[a],{done:!1,value:t};h=2;case 2:for(var e=-1;;){if(++e>=n.length){h=3;continue e}if(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]],a=s.keys.length,h=void 0!==t?1:0;continue;case 3:return{done:!0,value:void 0}}})},x.prototype.findPath=function(e){var t,r,i=this._root;if(i.isLeaf)r=t=EmptyArray;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}},x.prototype.diffAgainst=function(e,t,r,i){if(e._compare!==this._compare)throw new Error("Tree comparators are not the same.");if(this.isEmpty||e.isEmpty)return this.isEmpty&&e.isEmpty?void 0:this.isEmpty?void 0===r?void 0:x.stepToEnd(x.makeDiffCursor(e),r):void 0===t?void 0:x.stepToEnd(x.makeDiffCursor(this),t);for(var n=this._compare,o=x.makeDiffCursor(this),s=x.makeDiffCursor(e),a=!0,h=!0,u=x.compare(o,s,n);a&&h;){var l=x.compare(o,s,n),f=o.leaf,p=o.internalSpine,c=o.levelIndices,y=s.leaf,d=s.internalSpine,v=s.levelIndices;if(f||y){if(0!==u)if(0===l){if(f&&y&&i){var g=f.values[c[c.length-1]],m=y.values[v[v.length-1]];if(!Object.is(g,m))if((k=i(o.currentKey,g,m))&&null!=k&&k.break)return k.break}}else if(0<l){if(y&&r){m=y.values[v[v.length-1]];if((k=r(s.currentKey,m))&&k.break)return k.break}}else if(t&&f&&0!==u){var k,g=f.values[c[c.length-1]];if((k=t(o.currentKey,g))&&k.break)return k.break}}else if(!f&&!y&&0===l){f=p.length-1,y=d.length-1,f=p[f][c[f]];if(d[y][v[y]]===f){a=x.step(o,!(u=0)),h=x.step(s,!0);continue}}(u=l)<0?a=x.step(o):h=x.step(s)}return a&&t?x.finishCursorWalk(o,s,n,t):h&&r?x.finishCursorWalk(s,o,n,r):void 0},x.finishCursorWalk=function(e,t,r,i){r=x.compare(e,t,r);if(0===r){if(!x.step(e))return}else r<0&&check(!1,"cursor walk terminated early");return x.stepToEnd(e,i)},x.stepToEnd=function(e,t){for(var r=!0;r;){var i=e.leaf,n=e.levelIndices,o=e.currentKey;if(i){n=t(o,i.values[n[n.length-1]]);if(n&&n.break)return n.break}r=x.step(e)}},x.makeDiffCursor=function(e){var t=e._root;return{height:e.height,internalSpine:[[t]],levelIndices:[0],leaf:void 0,currentKey:t.maxKey()}},x.step=function(e,t){void 0===t&&(t=!1);var r=e.internalSpine,i=e.levelIndices,n=e.leaf;if(t||n){var o=i.length;if(t||0===i[o-1]){var s=r.length;if(0===s)return!1;for(var a=s-1,h=a;0<=h;){if(0<(f=i[h])){h<o-1&&(e.leaf=void 0,i.splice(h+1,o-h)),h<a&&r.splice(h+1,s-h);var u=--i[h];return e.currentKey=r[h][u].maxKey(),!0}h--}return!1}var l=--i[o-1];return e.currentKey=n.keys[l],!0}var f,t=r.length,n=t-1,n=r[n][i[n]];return n.isLeaf?(e.leaf=n,l=i[t]=n.values.length-1,e.currentKey=n.keys[l]):(n=n.children,f=(r[t]=n).length-1,i[t]=f,e.currentKey=n[f].maxKey()),!0},x.compare=function(e,t,r){var i=e.height,n=e.currentKey,o=e.levelIndices,s=t.height,e=t.currentKey,t=t.levelIndices,n=r(e,n);if(0!==n)return n;n=i<s?i:s;return o.length-(i-n)-(t.length-(s-n))},x.prototype.keys=function(e){var t=this.entries(e,ReusedArray);return iterator(function(){var e=t.next();return e.value&&(e.value=e.value[0]),e})},x.prototype.values=function(e){var t=this.entries(e,ReusedArray);return iterator(function(){var e=t.next();return e.value&&(e.value=e.value[1]),e})},Object.defineProperty(x.prototype,"maxNodeSize",{get:function(){return this._maxNodeSize},enumerable:!1,configurable:!0}),x.prototype.minKey=function(){return this._root.minKey()},x.prototype.maxKey=function(){return this._root.maxKey()},x.prototype.clone=function(){this._root.isShared=!0;var e=new x(void 0,this._compare,this._maxNodeSize);return e._root=this._root,e._size=this._size,e},x.prototype.greedyClone=function(e){var t=new x(void 0,this._compare,this._maxNodeSize);return t._root=this._root.greedyClone(e),t._size=this._size,t},x.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):[]},x.prototype.keysArray=function(){var r=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(e,t){r.push(e)}),r},x.prototype.valuesArray=function(){var r=[];return this._root.forRange(this.minKey(),this.maxKey(),!0,!1,this,0,function(e,t){r.push(t)}),r},x.prototype.toString=function(){return this.toArray().toString()},x.prototype.setIfNotPresent=function(e,t){return this.set(e,t,!1)},x.prototype.nextHigherPair=function(e){var t=this.entries(e,ReusedArray),r=t.next();return!r.done&&void 0!==e&&this._compare(r.value[0],e)<=0&&(r=t.next()),r.value},x.prototype.nextHigherKey=function(e){e=this.nextHigherPair(e);return e&&e[0]},x.prototype.nextLowerPair=function(e){return this.entriesReversed(e,ReusedArray,!0).next().value},x.prototype.nextLowerKey=function(e){e=this.nextLowerPair(e);return e&&e[0]},x.prototype.changeIfPresent=function(e,r){return 0!==this.editRange(e,e,!0,function(e,t){return{value:r}})},x.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?Break:void 0}),n},x.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},x.prototype.forRange=function(e,t,r,i,n){i=this._root.forRange(e,t,r,!1,this,n||0,i);return"number"==typeof i?i:i.break},x.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?EmptyLeaf:o.children[0]}},x.prototype.editAll=function(e,t){return this.editRange(this.minKey(),this.maxKey(),!0,e,t)},x.prototype.deleteRange=function(e,t,r){return this.editRange(e,t,r,DeleteRange)},x.prototype.deleteKeys=function(e){for(var t=0,r=0;t<e.length;t++)this.delete(e[t])&&r++;return r},Object.defineProperty(x.prototype,"height",{get:function(){for(var e=this._root,t=-1;e;)t++,e=e.isLeaf?void 0:e.children[0];return t},enumerable:!1,configurable:!0}),x.prototype.freeze=function(){this.clear=this.set=this.editRange=function(){throw new Error("Attempted to modify a frozen BTree")}},x.prototype.unfreeze=function(){delete this.clear,delete this.set,delete this.editRange},Object.defineProperty(x.prototype,"isFrozen",{get:function(){return this.hasOwnProperty("editRange")},enumerable:!1,configurable:!0}),x.prototype.checkValid=function(){var e=this._root.checkValid(0,this,0);check(e===this.size,"size mismatch: counted ",e,"but stored",this.size)},x}();function iterator(e){void 0===e&&(e=function(){return{done:!0,value:void 0}});e={next:e};return Symbol&&Symbol.iterator&&(e[Symbol.iterator]=function(){return this}),e}exports.default=BTree,Symbol&&Symbol.iterator&&(BTree.prototype[Symbol.iterator]=BTree.prototype.entries),BTree.prototype.where=BTree.prototype.filter,BTree.prototype.setRange=BTree.prototype.setPairs,BTree.prototype.add=BTree.prototype.set;var BNode=function(){function t(e,t){void 0===e&&(e=[]),this.keys=e,this.values=t||undefVals,this.isShared=void 0}return Object.defineProperty(t.prototype,"isLeaf",{get:function(){return void 0===this.children},enumerable:!1,configurable:!0}),t.prototype.maxKey=function(){return this.keys[this.keys.length-1]},t.prototype.indexOf=function(e,t,r){for(var i=this.keys,n=0,o=i.length,s=o>>1;n<o;){var a=r(i[s],e);if(a<0)n=s+1;else{if(!(0<a)){if(0===a)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},t.prototype.minKey=function(){return this.keys[0]},t.prototype.clone=function(){var e=this.values;return new t(this.keys.slice(0),e===undefVals?e:e.slice(0))},t.prototype.greedyClone=function(e){return this.isShared&&!e?this:this.clone()},t.prototype.get=function(e,t,r){r=this.indexOf(e,-1,r._compare);return r<0?t:this.values[r]},t.prototype.checkValid=function(e,t,r){var i=this.keys.length,n=this.values.length;return check(this.values===undefVals?i<=n:i===n,"keys/values length mismatch: depth",e,"with lengths",i,n,"and baseIndex",r),check(0==e||0<i,"empty leaf at depth",e,"and baseIndex",r),i},t.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},t.prototype.reifyValues=function(){return this.values===undefVals?this.values=this.values.slice(0,this.keys.length):this.values},t.prototype.insertInLeaf=function(e,t,r,i){if(this.keys.splice(e,0,t),this.values===undefVals){for(;undefVals.length<i._maxNodeSize;)undefVals.push(void 0);if(void 0===r)return!0;this.values=undefVals.slice(0,this.keys.length-1)}return this.values.splice(e,0,r),!0},t.prototype.takeFromRight=function(e){var t=this.values;e.values===undefVals?t!==undefVals&&t.push(void 0):(t=this.reifyValues()).push(e.values.shift()),this.keys.push(e.keys.shift())},t.prototype.takeFromLeft=function(e){var t=this.values;e.values===undefVals?t!==undefVals&&t.unshift(void 0):(t=this.reifyValues()).unshift(e.values.pop()),this.keys.unshift(e.keys.pop())},t.prototype.splitOffRightSide=function(){var e=this.keys.length>>1;return new t(this.keys.splice(e),this.values===undefVals?undefVals:this.values.splice(e))},t.prototype.forRange=function(e,t,r,i,n,o,s){var a,h,u=n._compare;if(t===e){if(!r)return o;if(h=(a=this.indexOf(e,-1,u))+1,a<0)return o}else a=this.indexOf(e,0,u),(h=this.indexOf(t,-1,u))<0?h=~h:!0===r&&h++;var l=this.keys,f=this.values;if(void 0!==s)for(var p=a;p<h;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!==undefVals&&this.values.splice(p,1),n._size--,p--,h--):y.hasOwnProperty("value")&&(f[p]=y.value)}if(void 0!==y.break)return y}}else o+=h-a;return o},t.prototype.mergeSibling=function(e,t){if(this.keys.push.apply(this.keys,e.keys),this.values===undefVals){if(e.values===undefVals)return;this.values=this.values.slice(0,this.keys.length)}this.values.push.apply(this.values,e.reifyValues())},t}(),BNodeInternal=function(n){function i(e,t){var r=this;if(!t){t=[];for(var i=0;i<e.length;i++)t[i]=e[i].maxKey()}return(r=n.call(this,t)||this).children=e,r}return __extends(i,n),i.prototype.clone=function(){for(var e=this.children.slice(0),t=0;t<e.length;t++)e[t].isShared=!0;return new i(e,this.keys.slice(0))},i.prototype.greedyClone=function(e){if(this.isShared&&!e)return this;for(var t=new i(this.children.slice(0),this.keys.slice(0)),r=0;r<t.children.length;r++)t.children[r]=t.children[r].greedyClone();return t},i.prototype.minKey=function(){return this.children[0].minKey()},i.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},i.prototype.checkValid=function(e,t,r){var i=this.keys.length,n=this.children.length;check(i===n,"keys/children length mismatch: depth",e,"lengths",i,n,"baseIndex",r),check(1<i||0<e,"internal node has length",i,"at depth",e,"baseIndex",r);for(var o=0,s=this.children,a=this.keys,h=0,u=0;u<n;u++)o+=s[u].checkValid(e+1,t,r+o),check((h+=s[u].keys.length)<=o,"wtf",r),check(0===u||s[u-1].constructor===s[u].constructor,"type mismatch, baseIndex:",r),s[u].maxKey()!=a[u]&&check(!1,"keys[",u,"] =",a[u],"is wrong, should be ",s[u].maxKey(),"at depth",e,"baseIndex",r),0===u||t._compare(a[u-1],a[u])<0||check(!1,"sort violation at depth",e,"index",u,"keys",a[u-1],a[u]);i=0===h;return(i||h>t.maxNodeSize*n)&&check(!1,i?"too few":"too many","children (",h,o,") at depth",e,"maxNodeSize:",t.maxNodeSize,"children.length:",n,"baseIndex:",r),o},i.prototype.set=function(e,t,r,i){var n,o=this.children,s=i._maxNodeSize,a=i._compare,h=Math.min(this.indexOf(e,0,a),o.length-1),u=o[h];u.isShared&&(o[h]=u=u.clone()),u.keys.length>=s&&(0<h&&(n=o[h-1]).keys.length<s&&a(u.keys[0],e)<0?(n.isShared&&(o[h-1]=n=n.clone()),n.takeFromRight(u),this.keys[h-1]=n.maxKey()):void 0!==(n=o[h+1])&&n.keys.length<s&&a(u.maxKey(),e)<0&&(n.isShared&&(o[h+1]=n=n.clone()),n.takeFromLeft(u),this.keys[h]=o[h].maxKey()));i=u.set(e,t,r,i);if(!1===i)return!1;if(this.keys[h]=u.maxKey(),!0===i)return!0;if(this.keys.length<s)return this.insert(h+1,i),!0;u=this.splitOffRightSide(),s=this;return 0<a(i.maxKey(),this.maxKey())&&(s=u,h-=this.keys.length),s.insert(h+1,i),u},i.prototype.insert=function(e,t){this.children.splice(e,0,t),this.keys.splice(e,0,t.maxKey())},i.prototype.splitOffRightSide=function(){var e=this.children.length>>1;return new i(this.children.splice(e),this.keys.splice(e))},i.prototype.takeFromRight=function(e){this.keys.push(e.keys.shift()),this.children.push(e.children.shift())},i.prototype.takeFromLeft=function(e){this.keys.unshift(e.keys.pop()),this.children.unshift(e.children.pop())},i.prototype.forRange=function(e,t,r,i,n,o,s){var a=n._compare,h=this.keys,u=this.children,l=this.indexOf(e,0,a),f=l,p=Math.min(t===e?l:this.indexOf(t,0,a),h.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(h[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):(h.splice(f,1),u.splice(f,1)));0!==u.length&&0===u[0].keys.length&&check(!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},i.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)},i.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)},i}(BNode),undefVals=[],Delete={delete:!0},DeleteRange=function(){return Delete},Break={break:!0},EmptyLeaf=function(){var e=new BNode;return e.isShared=!0,e}(),EmptyArray=[],ReusedArray=[];function check(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(" "))}exports.EmptyBTree=function(){var e=new BTree;return e.freeze(),e}();

package.json

 {
   "name": "sorted-btree",
-  "version": "1.4.0",
+  "version": "1.5.0",
   "description": "A sorted list of key-value pairs in a fast, typed in-memory B+ tree with a powerful API.",
@@ -12,3 +12,4 @@ "main": "b+tree.js",
     "prepare": "npm run build",
-    "safePublish": "npm run build && testpack && npm publish"
+    "safePublish": "npm run build && testpack && npm publish",
+    "benchmark": "npm run build && node benchmarks.js"
   },
@@ -15,0 +16,0 @@ "files": [

readme.md

@@ -27,5 +27,5 @@ B+ tree
   with copy-on-edit behavior; both copies of the tree remain mutable.
-  I call this category of data structure "semi-persistent" because AFAIK no
-  one else has given it a name; it walks the line between mutating and 
-  [persistent](https://en.wikipedia.org/wiki/Persistent_data_structure).
+  I call this category of data structure "dynamically persistent" because 
+  AFAIK no one else has given it a name; it walks the line between mutating 
+  and [persistent](https://en.wikipedia.org/wiki/Persistent_data_structure).
 - Includes persistent methods such as `with` and `without`, which return a
@@ -40,4 +40,6 @@ modified tree without changing the original (in O(log(size)) time).
 - Throws an exception if you try to use `NaN` as a key, but infinity is allowed.
-- No dependencies. 16K minified.
+- No dependencies. 18K minified.
 - Includes a lattice of interfaces for TypeScript users (see below)
+- Supports diffing computation between two trees that is highly optimized for the case
+  in which a majority of nodes are shared (such as when persistent methods are used).
 
@@ -61,2 +63,3 @@ ### Additional operations supported on this B+ tree ###
 - Fast clone: `t.clone()`
+- Compute a diff between two trees (quickly skipping shared subtrees): `t.diffAgainst(otherTree, ...)`
 - For more information, **see [full documentation](https://github.com/qwertie/btree-typescript/blob/master/b%2Btree.ts) in the source code.**
@@ -378,2 +381,8 @@
 
+### v1.5.0 ###
+
+- Added `BTree.diffAgainst` method (PR #16)
+- Added `simpleComparator` function (PR #15)
+- Improved `defaultComparator` (PR #15) to support edge cases better. Most notably, heterogenous key types will no longer cause trouble such as failure to find keys that are, in fact, present in the tree. `BTree` is slightly slower using the new default comparator, but the benchmarks above have not been refreshed. For maximum performance, use `simpleComparator` or a custom comparator as the second constructor parameter. The simplest possible comparator is `(a, b) => a - b`, which works for finite numbers only.
+
 ### v1.4.0 ###
@@ -423,5 +432,4 @@
 
-Are you a C# developer? You might like the similar data structures I made for C#: 
-BDictionary, BList, etc. See http://core.loyc.net/collections/
+Are you a C# developer? You might like the similar data structures I made for C# ([BDictionary, BList, etc.](core.loyc.net/collections/alists-part2)), and other [dynamically persistent collection types](http://core.loyc.net/collections/).
 
 You might think that the package name "sorted btree" is overly redundant, but I _did_ make a data structure similar to B+ Tree that is _not_ sorted. I called it the [A-List](http://core.loyc.net/collections/alists-part1) (C#). But yeah, the names `btree` and `bplustree` were already taken, so what was I supposed to do, right?

No alert changes

Improved metrics

Total package byte prevSize

172540

increased by15.37%

Lines of code

2360

increased by17.59%

Number of lines in readme file

431

increased by1.89%

No dependency changes