sorted-btree - npm Package Compare versions

Comparing version 1.0.6 to 1.1.0

b+tree.d.ts

@@ -125,3 +125,6 @@ export declare type EditRangeResult<V, R = number> = {
     readonly size: number;
+    /** Gets the number of key-value pairs in the tree. */
     readonly length: number;
+    /** Returns true iff the tree contains no key-value pairs. */
+    readonly isEmpty: boolean;
     /** Releases the tree so that its size is 0. */
@@ -194,2 +197,49 @@ clear(): void;
     delete(key: K): boolean;
+    /** Returns a copy of the tree with the specified key-value pair set. */
+    with<V2>(key: K, value: V2): BTree<K, V | V2>;
+    /** Returns a copy of the tree with the specified key-value pair set. */
+    withPairs<V2>(pairs: [K, V | V2][], overwrite: boolean): BTree<K, V | V2>;
+    /** Returns a copy of the tree with the specified keys present.
+     *  @param keys The keys to add. If a key is already present in the tree,
+     *         neither the existing key nor the existing value is modified.
+     *  @param returnThisIfUnchanged if true, returns this if all keys already
+     *  existed. Performance note: due to the architecture of this class, all
+     *  node(s) leading to existing keys are cloned even if the collection is
+     *  ultimately unchanged.
+    */
+    withKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K, V | undefined>;
+    /** Returns a copy of the tree with the specified key removed.
+     * @param returnThisIfUnchanged if true, returns this if the key didn't exist.
+     *  Performance note: due to the architecture of this class, node(s) leading
+     *  to where the key would have been stored are cloned even when the key
+     *  turns out not to exist and the collection is unchanged.
+     */
+    without(key: K, returnThisIfUnchanged?: boolean): BTree<K, V>;
+    /** Returns a copy of the tree with the specified keys removed.
+     * @param returnThisIfUnchanged if true, returns this if none of the keys
+     *  existed. Performance note: due to the architecture of this class,
+     *  node(s) leading to where the key would have been stored are cloned
+     *  even when the key turns out not to exist.
+     */
+    withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K, V>;
+    /** Returns a copy of the tree with the specified range of keys removed. */
+    withoutRange(low: K, high: K, includeHigh: boolean, returnThisIfUnchanged?: boolean): BTree<K, V>;
+    /** Returns a copy of the tree with pairs removed whenever the callback
+     *  function returns false. `where()` is a synonym for this method. */
+    filter(callback: (k: K, v: V, counter: number) => boolean, returnThisIfUnchanged?: boolean): BTree<K, V>;
+    /** Returns a copy of the tree with all values altered by a callback function. */
+    mapValues<R>(callback: (v: V, k: K, counter: number) => R): BTree<K, R>;
+    /** Performs a reduce operation like the `reduce` method of `Array`.
+     *  It is used to combine all pairs into a single value, or perform
+     *  conversions. `reduce` is best understood by example. For example,
+     *  `tree.reduce((P, pair) => P * pair[0], 1)` multiplies all keys
+     *  together. It means "start with P=1, and for each pair multiply
+     *  it by the key in pair[0]". Another example would be converting
+     *  the tree to a Map (in this example, note that M.set returns M):
+     *
+     *  var M = tree.reduce((M, pair) => M.set(pair[0],pair[1]), new Map())
+     *
+     *  **Note**: the same array is sent to the callback on every iteration.
+     */
+    reduce<R>(callback: (previous: R, currentPair: [K, V], counter: number) => R, initialValue: R): R;
     /** Returns an iterator that provides items in order (ascending order if
@@ -203,3 +253,3 @@ *  the collection's comparator uses ascending order, as is the default.)
      */
-    entries(lowestKey?: K, reusedArray?: [K, V]): IterableIterator<[K, V]>;
+    entries(lowestKey?: K, reusedArray?: (K | V)[]): IterableIterator<[K, V]>;
     /** Returns an iterator that provides items in reversed order.
@@ -214,3 +264,3 @@ *  @param highestKey Key at which to start iterating, or undefined to
      */
-    entriesReversed(highestKey?: K, reusedArray?: [K, V], skipHighest?: boolean): IterableIterator<[K, V]>;
+    entriesReversed(highestKey?: K, reusedArray?: (K | V)[], skipHighest?: boolean): IterableIterator<[K, V]>;
     protected findPath(key?: K): {
@@ -237,2 +287,8 @@ nodequeue: BNode<K, V>[][];
     clone(): BTree<K, V>;
+    /** Performs a greedy clone, immediately duplicating any nodes that are
+     *  not currently marked as shared, in order to avoid marking any nodes
+     *  as shared.
+     *  @param force Clone all nodes, even shared ones.
+     */
+    greedyClone(force?: boolean): BTree<K, V>;
     /** Gets an array filled with the contents of the tree, sorted by key */
@@ -250,3 +306,10 @@ toArray(maxLength?: number): [K, V][];
     setIfNotPresent(key: K, value: V): boolean;
-    /** Returns the next key larger than the specified key */
+    /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */
+    nextHigherPair(key: K): [K, V] | undefined;
+    /** Returns the next key larger than the specified key (or undefined if there is none) */
+    nextHigherKey(key: K): K | undefined;
+    /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */
+    nextLowerPair(key: K): [K, V] | undefined;
+    /** Returns the next key larger than the specified key (or undefined if there is none) */
+    nextLowerKey(key: K): K | undefined;
     /** Edits the value associated with a key in the tree, if it already exists.
@@ -271,7 +334,10 @@ * @returns true if the key existed, false if not.
      * @param pairs Pairs to add to this tree. If there are duplicate keys,
-     * later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]]
-     * associates 0 with 7.)
+     *        later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]]
+     *        associates 0 with 7.)
+     * @param overwrite Whether to overwrite pairs that already exist (if false,
+     *        pairs[i] is ignored when the key pairs[i][0] already exists.)
+     * @returns The number of pairs added to the collection.
      * @description Computational complexity: O(pairs.length * log(size + pairs.length))
      */
-    setRange(pairs: [K, V][]): this;
+    setPairs(pairs: [K, V][], overwrite?: boolean): number;
     /**
@@ -327,2 +393,4 @@ * Scans the specified range of keys, in ascending order by key.
     editRange<R = V>(low: K, high: K, includeHigh: boolean, onFound: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void, initialCounter?: number): R | number;
+    /** Same as `editRange` except that the callback is called for all pairs. */
+    editAll<R = V>(onFound: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void, initialCounter?: number): R | number;
     /**
@@ -337,2 +405,4 @@ * Removes a range of key-value pairs from the B+ tree.
     deleteRange(low: K, high: K, includeHigh: boolean): number;
+    /** Deletes a series of keys from the collection. */
+    deleteKeys(keys: K[]): number;
     /** Gets the height of the tree: the number of internal nodes between the
@@ -368,2 +438,3 @@ *  BTree object and its leaf nodes (zero if there are no internal nodes). */
     clone(): BNode<K, V>;
+    greedyClone(force?: boolean): BNode<K, V>;
     get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined;
@@ -381,2 +452,4 @@ checkValid(depth: number, tree: BTree<K, V>): number;
 }
+/** A BTree frozen in the empty state. */
+export declare const EmptyBTree: BTree<any, any>;
 export {};

b+tree.min.js

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

package.json

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

readme.md

@@ -25,2 +25,7 @@ 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).
+- Includes persistent methods such as `with` and `without`, which return a
+  modified tree without changing the original (in O(log(size)) time).
 - When a node fills up, items are shifted to siblings when possible to 
@@ -33,5 +38,5 @@ keep nodes near their capacity, to improve memory utilization.
 - Throws an exception if you try to use `NaN` as a key, but infinity is allowed.
-- No dependencies. Under 14K minified.
+- No dependencies. 15.3K minified.
 
-Additional operations supported on this B+ tree:
+### Additional operations supported on this B+ tree ###
 
@@ -46,5 +51,7 @@ - Set a value only if the key does not already exist: `t.setIfNotPresent(k,v)`
 - Scan all items: `t.forEachPair((key, value, index) => {...})`
-- Scan a range of items: `t.forRange(lowKey, highKey, includeHighFlag, (k,v) => {...})`
+- Scan a range of items: `t.forRange(lowKey, highKey, includeHiFlag, (k,v) => {...})`
 - Count the number of keys in a range: `c = t.forRange(loK, hiK, includeHi, undefined)`
 - Get smallest or largest key: `t.minKey()`, `t.maxKey()`
+- Get next larger key/pair than `k`: `t.nextHigherKey(k)`, `t.nextHigherPair(k)`
+- Get largest key/pair that is lower than `k`: `t.nextLowerKey(k)`, `t.nextLowerPair(k)`
 - Freeze to prevent modifications: `t.freeze()` (you can also `t.unfreeze()`)
@@ -60,2 +67,19 @@ - Fast clone: `t.clone()`
 
+#### Functional methods
+
+- Get a copy of the tree including only items fitting a criteria: `t.filter((k,v) => k.fitsCriteria())`
+- Get a copy of the tree with all values modified: `t.mapValues((v,k) => v.toString())`
+- Reduce a tree (see below): `t.reduce((acc, pair) => acc+pair[1], 0)`
+
+#### Persistent methods
+
+- Get a new tree with one pair changed: `t.with(key, value)`
+- Get a new tree with multiple pairs changed: `t.withPairs([[k1,v1], [k2,v2]])`
+- Ensure that specified keys exist in a new tree: `t.withKeys([k1,k2])`
+- Get a new tree with one pair removed: `t.without(key)`
+- Get a new tree with specific pairs removed: `t.withoutKeys(keys)`
+- Get a new tree with a range of keys removed: `t.withoutRange(low, high, includeHi)`
+
+**Things to keep in mind:** I ran a test which suggested `t.with` is three times slower than `t.set`. These methods do not return a frozen tree even if the original tree was frozen (for performance reasons, e.g. frozen trees use slightly more memory.)
+
 Examples
@@ -87,2 +111,20 @@ --------
 
+### reduce ###
+
+The `reduce` method performs a reduction operation, like the `reduce` method of `Array`. It is used to combine all keys, values or pairs into a single value, or to perform type conversions conversions. `reduce` is best understood by example. So here's how you can multiply all the keys in a tree together:
+
+    var product = tree.reduce((p, pair) => p * pair[0], 1)
+
+It means "start with `p=1`, and for each pair change `p` to `p * pair[0]`" (`pair[0]` is the key). You may be thinking "hey, wouldn't it make more sense if the `1` argument came _first_?" Yes it would, but in `Array` the parameter is second, so it must also be second in `BTree` for consistency.
+
+Here's a similar example that adds all values together:
+
+    var total = tree.reduce((sum, pair) => sum + pair[1], 0)
+
+This final example converts the tree to a Map:
+
+    var map = tree.reduce((m, pair) => m.set(pair[0], pair[1]), new Map())`
+
+Remember that `m.set` returns `m`, which is different from `BTree` where `tree.set` returns a boolean indicating whether a new key was added.
+
 ### editRange ###
@@ -105,6 +147,6 @@
 
-- These benchmark results were gathered on my PC in Node v10.4.1
+- These benchmark results were gathered on my PC in Node v10.4.1, July 2018
 - `BTree` is 3 to 5 times faster than `SortedMap` and `SortedSet` in the `collections` package
 - `BTree` has similar speed to `RBTree` at smaller sizes, but is faster at very large sizes and uses less memory because it packs many keys into one array instead of allocating an extra heap object for every key.
-- If you need a persistent tree, `functional-red-black-tree` is faster than I expected, but `BTree` should require less memory.
+- If you need [functional persistence](https://en.wikipedia.org/wiki/Persistent_data_structure), `functional-red-black-tree` is remarkably fast for a persistent tree, but `BTree` should require less memory _unless_ you frequently use `clone/with/without` and are saving snapshots of the old tree to prevent garbage collection.
 - B+ trees normally use less memory than hashtables (such as the standard `Map`), although in JavaScript this is not guaranteed because the B+ tree's memory efficiency depends on avoiding wasted space in the arrays for each node, and JavaScript provides no way to detect or control the capacity of an array's underlying memory area. Also, `Map` should be faster because it does not sort its keys.
@@ -265,5 +307,24 @@ - "Sorted array" refers to `SortedArray<K,V>`, a wrapper class for an array of `[K,V]` pairs. Benchmark results were not gathered for sorted arrays with one million elements (it takes too long)
 
-Endnote
--------
+Version history
+---------------
 
+### v1.1 ###
+
+- Added `isEmpty` property getter
+- Added `nextHigherPair`, `nextHigherKey`, `nextLowerPair`, `nextLowerKey` methods
+- Added `editAll`, which is like `editRange` but touches all keys
+- Added `deleteKeys` for deleting a sequence of keys (iterable)
+- Added persistent methods `with`, `withPairs`, `withKeys`, `without`, `withoutKeys`, `withoutRange`
+- Added functional methods `filter`, `reduce`, `mapValues`
+- Added `greedyClone` for cloning nodes immediately, to avoid marking the original tree as shared which slows it down.
+- Relaxed type constraint on second parameter of `entries`/`entriesReversed`
+- Renamed `setRange` to `setPairs` for logical consistency with `withoutPairs` and `withoutRange`. The old name is deprecated but added to the `prototype` as a synonym. `setPairs` returns the number of pairs added instead of `this`.
+- Added export `EmptyBTree`, a frozen empty tree
+
+### v1.0: Initial version ###
+
+- With fast cloning and all that good stuff
+
+### Endnote ###
+
 ♥ This package was made to help people [learn TypeScript & React](http://typescript-react-primer.loyc.net/).
@@ -273,1 +334,3 @@
 BDictionary, BList, etc. See 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?

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

133193

increased by17.58%

Lines of code

1816

increased by15.37%

Number of lines in readme file

329

increased by23.68%

No dependency changes