diff options
Diffstat (limited to 'packages/idb-bridge/src/tree')
-rw-r--r-- | packages/idb-bridge/src/tree/b+tree.ts | 1070 | ||||
-rw-r--r-- | packages/idb-bridge/src/tree/interfaces.ts | 287 |
2 files changed, 857 insertions, 500 deletions
diff --git a/packages/idb-bridge/src/tree/b+tree.ts b/packages/idb-bridge/src/tree/b+tree.ts index 783c6b049..59a49baa3 100644 --- a/packages/idb-bridge/src/tree/b+tree.ts +++ b/packages/idb-bridge/src/tree/b+tree.ts @@ -24,14 +24,29 @@ SPDX-License-Identifier: MIT // Original repository: https://github.com/qwertie/btree-typescript - -import { ISortedMap, ISortedMapF } from './interfaces'; +import { ISortedMap, ISortedMapF } from "./interfaces"; export { - ISetSource, ISetSink, ISet, ISetF, ISortedSetSource, ISortedSet, ISortedSetF, - IMapSource, IMapSink, IMap, IMapF, ISortedMapSource, ISortedMap, ISortedMapF -} from './interfaces'; - -export type EditRangeResult<V,R=number> = {value?:V, break?:R, delete?:boolean}; + ISetSource, + ISetSink, + ISet, + ISetF, + ISortedSetSource, + ISortedSet, + ISortedSetF, + IMapSource, + IMapSink, + IMap, + IMapF, + ISortedMapSource, + ISortedMap, + ISortedMapF, +} from "./interfaces"; + +export type EditRangeResult<V, R = number> = { + value?: V; + break?: R; + delete?: boolean; +}; type index = number; @@ -57,7 +72,7 @@ type index = number; // - V8 source (NewElementsCapacity in src/objects.h): arrays grow by 50% + 16 elements /** Compares two numbers, strings, arrays of numbers/strings, Dates, - * or objects that have a valueOf() method returning a number or string. + * 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. */ export function defaultComparator(a: any, b: any) { @@ -66,42 +81,42 @@ export function defaultComparator(a: any, b: any) { // General case (c is NaN): string / arrays / Date / incomparable things if (a) a = a.valueOf(); if (b) b = b.valueOf(); - return a < b ? -1 : a > b ? 1 : a == b ? 0 : c; -}; + return a < b ? -1 : a > b ? 1 : a == b ? 0 : c; +} /** - * A reasonably fast collection of key-value pairs with a powerful API. + * A reasonably fast collection of key-value pairs with a powerful API. * Largely compatible with the standard Map. BTree is a B+ tree data structure, * so the collection is sorted by key. - * + * * B+ trees tend to use memory more efficiently than hashtables such as the - * standard Map, especially when the collection contains a large number of - * items. However, maintaining the sort order makes them modestly slower: + * standard Map, especially when the collection contains a large number of + * items. However, maintaining the sort order makes them modestly slower: * O(log size) rather than O(1). This B+ tree implementation supports O(1) * fast cloning. It also supports freeze(), which can be used to ensure that * a BTree is not changed accidentally. - * + * * Confusingly, the ES6 Map.forEach(c) method calls c(value,key) instead of * c(key,value), in contrast to other methods such as set() and entries() - * which put the key first. I can only assume that the order was reversed on + * which put the key first. I can only assume that the order was reversed on * the theory that users would usually want to examine values and ignore keys. - * BTree's forEach() therefore works the same way, but a second method + * BTree's forEach() therefore works the same way, but a second method * `.forEachPair((key,value)=>{...})` is provided which sends you the key - * first and the value second; this method is slightly faster because it is + * first and the value second; this method is slightly faster because it is * the "native" for-each method for this class. - * - * Out of the box, BTree supports keys that are numbers, strings, arrays of - * numbers/strings, Date, and objects that have a valueOf() method returning a + * + * Out of the box, BTree supports keys that are numbers, strings, arrays of + * numbers/strings, Date, and objects that have a valueOf() method returning a * number or string. Other data types, such as arrays of Date or custom - * objects, require a custom comparator, which you must pass as the second - * argument to the constructor (the first argument is an optional list of + * objects, require a custom comparator, which you must pass as the second + * argument to the constructor (the first argument is an optional list of * initial items). Symbols cannot be used as keys because they are unordered * (one Symbol is never "greater" or "less" than another). - * + * * @example * Given a {name: string, age: number} object, you can create a tree sorted by * name and then by age like this: - * + * * var tree = new BTree(undefined, (a, b) => { * if (a.name > b.name) * return 1; // Return a number >0 when a > b @@ -110,36 +125,36 @@ export function defaultComparator(a: any, b: any) { * else // names are equal (or incomparable) * return a.age - b.age; // Return >0 when a.age > b.age * }); - * + * * tree.set({name:"Bill", age:17}, "happy"); * tree.set({name:"Fran", age:40}, "busy & stressed"); * tree.set({name:"Bill", age:55}, "recently laid off"); * tree.forEachPair((k, v) => { * console.log(`Name: ${k.name} Age: ${k.age} Status: ${v}`); * }); - * + * * @description * The "range" methods (`forEach, forRange, editRange`) will return the number * of elements that were scanned. In addition, the callback can return {break:R} * to stop early and return R from the outer function. - * + * * - TODO: Test performance of preallocating values array at max size * - TODO: Add fast initialization when a sorted array is provided to constructor - * + * * For more documentation see https://github.com/qwertie/btree-typescript * - * Are you a C# developer? You might like the similar data structures I made for C#: + * 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/ - * + * * @author David Piepgrass */ -export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap<K,V> -{ - private _root: BNode<K, V> = EmptyLeaf as BNode<K,V>; +export default class BTree<K = any, V = any> + implements ISortedMapF<K, V>, ISortedMap<K, V> { + private _root: BNode<K, V> = EmptyLeaf as BNode<K, V>; _size: number = 0; _maxNodeSize: number; - _compare: (a:K, b:K) => number; - + _compare: (a: K, b: K) => number; + /** * Initializes an empty B+ tree. * @param compare Custom function to compare pairs of elements in the tree. @@ -148,60 +163,78 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap * @param maxNodeSize Branching factor (maximum items or children per node) * Must be in range 4..256. If undefined or <4 then default is used; if >256 then 256. */ - public constructor(entries?: [K,V][], compare?: (a: K, b: K) => number, maxNodeSize?: number) { + public constructor( + entries?: [K, V][], + compare?: (a: K, b: K) => number, + maxNodeSize?: number, + ) { this._maxNodeSize = maxNodeSize! >= 4 ? Math.min(maxNodeSize!, 256) : 32; this._compare = compare || defaultComparator; - if (entries) - this.setPairs(entries); + if (entries) this.setPairs(entries); } - + // ES6 Map<K,V> methods /////////////////////////////////////////////////// /** Gets the number of key-value pairs in the tree. */ - get size() { return this._size; } + get size() { + return this._size; + } /** Gets the number of key-value pairs in the tree. */ - get length() { return this._size; } + get length() { + return this._size; + } /** Returns true iff the tree contains no key-value pairs. */ - get isEmpty() { return this._size === 0; } + get isEmpty() { + return this._size === 0; + } /** Releases the tree so that its size is 0. */ clear() { - this._root = EmptyLeaf as BNode<K,V>; + this._root = EmptyLeaf as BNode<K, V>; this._size = 0; } - forEach(callback: (v:V, k:K, tree:BTree<K,V>) => void, thisArg?: any): number; + forEach( + callback: (v: V, k: K, tree: BTree<K, V>) => void, + thisArg?: any, + ): number; - /** Runs a function for each key-value pair, in order from smallest to + /** Runs a function for each key-value pair, in order from smallest to * largest key. For compatibility with ES6 Map, the argument order to - * the callback is backwards: value first, then key. Call forEachPair + * the callback is backwards: value first, then key. Call forEachPair * instead to receive the key as the first argument. * @param thisArg If provided, this parameter is assigned as the `this` * value for each callback. * @returns the number of values that were sent to the callback, * or the R value if the callback returned {break:R}. */ - forEach<R=number>(callback: (v:V, k:K, tree:BTree<K,V>) => {break?:R}|void, thisArg?: any): R|number { - if (thisArg !== undefined) - callback = callback.bind(thisArg); + forEach<R = number>( + callback: (v: V, k: K, tree: BTree<K, V>) => { break?: R } | void, + thisArg?: any, + ): R | number { + if (thisArg !== undefined) callback = callback.bind(thisArg); return this.forEachPair((k, v) => callback(v, k, this)); } - /** Runs a function for each key-value pair, in order from smallest to + /** Runs a function for each key-value pair, in order from smallest to * largest key. The callback can return {break:R} (where R is any value * except undefined) to stop immediately and return R from forEachPair. - * @param onFound A function that is called for each key-value pair. This + * @param onFound A function that is called for each key-value pair. This * function can return {break:R} to stop early with result R. - * The reason that you must return {break:R} instead of simply R - * itself is for consistency with editRange(), which allows + * The reason that you must return {break:R} instead of simply R + * itself is for consistency with editRange(), which allows * multiple actions, not just breaking. - * @param initialCounter This is the value of the third argument of - * `onFound` the first time it is called. The counter increases + * @param initialCounter This is the value of the third argument of + * `onFound` the first time it is called. The counter increases * by one each time `onFound` is called. Default value: 0 * @returns the number of pairs sent to the callback (plus initialCounter, * if you provided one). If the callback returned {break:R} then * the R value is returned instead. */ - forEachPair<R=number>(callback: (k:K, v:V, counter:number) => {break?:R}|void, initialCounter?: number): R|number { - var low = this.minKey(), high = this.maxKey(); + forEachPair<R = number>( + callback: (k: K, v: V, counter: number) => { break?: R } | void, + initialCounter?: number, + ): R | number { + var low = this.minKey(), + high = this.maxKey(); return this.forRange(low!, high!, true, callback, initialCounter); } @@ -214,13 +247,13 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap get(key: K, defaultValue?: V): V | undefined { return this._root.get(key, defaultValue, this); } - + /** * Adds or overwrites a key-value pair in the B+ tree. * @param key the key is used to determine the sort order of * data in the tree. * @param value data to associate with the key (optional) - * @param overwrite Whether to overwrite an existing key-value pair + * @param overwrite Whether to overwrite an existing key-value pair * (default: true). If this is false and there is an existing * key-value pair then this method has no effect. * @returns true if a new key-value pair was added. @@ -229,14 +262,12 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap * as well as the value. This has no effect unless the new key * has data that does not affect its sort order. */ - set(key: K, value: V, overwrite?: boolean): boolean { - if (this._root.isShared) - this._root = this._root.clone(); + set(key: K, value: V, overwrite?: boolean): boolean { + if (this._root.isShared) this._root = this._root.clone(); var result = this._root.set(key, value, overwrite, this); - if (result === true || result === false) - return result; + if (result === true || result === false) return result; // Root node has split, so create a new root node. - this._root = new BNodeInternal<K,V>([this._root, result]); + this._root = new BNodeInternal<K, V>([this._root, result]); return true; } @@ -247,7 +278,7 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap * @param key Key to detect * @description Computational complexity: O(log size) */ - has(key: K): boolean { + has(key: K): boolean { return this.forRange(key, key, true, undefined) !== 0; } @@ -264,42 +295,50 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap // Clone-mutators ///////////////////////////////////////////////////////// /** Returns a copy of the tree with the specified key set (the value is undefined). */ - with(key: K): BTree<K,V|undefined>; + with(key: K): BTree<K, V | undefined>; /** Returns a copy of the tree with the specified key-value pair set. */ - with<V2>(key: K, value: V2, overwrite?: boolean): BTree<K,V|V2>; - with<V2>(key: K, value?: V2, overwrite?: boolean): BTree<K,V|V2|undefined> { - let nu = this.clone() as BTree<K,V|V2|undefined>; + with<V2>(key: K, value: V2, overwrite?: boolean): BTree<K, V | V2>; + with<V2>( + key: K, + value?: V2, + overwrite?: boolean, + ): BTree<K, V | V2 | undefined> { + let nu = this.clone() as BTree<K, V | V2 | undefined>; return nu.set(key, value, overwrite) || overwrite ? nu : this; } /** Returns a copy of the tree with the specified key-value pairs set. */ - withPairs<V2>(pairs: [K,V|V2][], overwrite: boolean): BTree<K,V|V2> { - let nu = this.clone() as BTree<K,V|V2>; + withPairs<V2>(pairs: [K, V | V2][], overwrite: boolean): BTree<K, V | V2> { + let nu = this.clone() as BTree<K, V | V2>; return nu.setPairs(pairs, overwrite) !== 0 || overwrite ? nu : this; } - /** Returns a copy of the tree with the specified keys present. + /** 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 + * @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> { - let nu = this.clone() as BTree<K,V|undefined>, changed = false; + */ + withKeys( + keys: K[], + returnThisIfUnchanged?: boolean, + ): BTree<K, V | undefined> { + let nu = this.clone() as BTree<K, V | undefined>, + changed = false; for (var i = 0; i < keys.length; i++) changed = nu.set(keys[i], undefined, false) || changed; return returnThisIfUnchanged && !changed ? this : nu; } - /** Returns a copy of the tree with the specified key removed. + /** 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> { + without(key: K, returnThisIfUnchanged?: boolean): BTree<K, V> { return this.withoutRange(key, key, true, returnThisIfUnchanged); } @@ -309,61 +348,92 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap * 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> { + withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K, V> { let nu = this.clone(); return nu.deleteKeys(keys) || !returnThisIfUnchanged ? nu : this; } /** 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> { + withoutRange( + low: K, + high: K, + includeHigh: boolean, + returnThisIfUnchanged?: boolean, + ): BTree<K, V> { let nu = this.clone(); if (nu.deleteRange(low, high, includeHigh) === 0 && returnThisIfUnchanged) return this; return nu; } - /** Returns a copy of the tree with pairs removed whenever the callback + /** 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> { + filter( + callback: (k: K, v: V, counter: number) => boolean, + returnThisIfUnchanged?: boolean, + ): BTree<K, V> { var nu = this.greedyClone(); var del: any; - nu.editAll((k,v,i) => { - if (!callback(k, v, i)) return del = Delete; + nu.editAll((k, v, i) => { + if (!callback(k, v, i)) return (del = Delete); }); - if (!del && returnThisIfUnchanged) - return this; + if (!del && returnThisIfUnchanged) return this; return nu; } /** 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> { - var tmp = {} as {value:R}; + mapValues<R>(callback: (v: V, k: K, counter: number) => R): BTree<K, R> { + var tmp = {} as { value: R }; var nu = this.greedyClone(); - nu.editAll((k,v,i) => { - return tmp.value = callback(v, k, i), tmp as any; + nu.editAll((k, v, i) => { + return (tmp.value = callback(v, k, i)), tmp as any; }); - return nu as any as BTree<K,R>; + return (nu as any) as 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 + /** 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 + * `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,tree:BTree<K,V>) => R, initialValue: R): R; - reduce<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:BTree<K,V>) => R): R|undefined; - reduce<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:BTree<K,V>) => R, initialValue?: R): R|undefined { - let i = 0, p = initialValue; - var it = this.entries(this.minKey(), ReusedArray), next; - while (!(next = it.next()).done) - p = callback(p, next.value, i++, this); + reduce<R>( + callback: ( + previous: R, + currentPair: [K, V], + counter: number, + tree: BTree<K, V>, + ) => R, + initialValue: R, + ): R; + reduce<R>( + callback: ( + previous: R | undefined, + currentPair: [K, V], + counter: number, + tree: BTree<K, V>, + ) => R, + ): R | undefined; + reduce<R>( + callback: ( + previous: R | undefined, + currentPair: [K, V], + counter: number, + tree: BTree<K, V>, + ) => R, + initialValue?: R, + ): R | undefined { + let i = 0, + p = initialValue; + var it = this.entries(this.minKey(), ReusedArray), + next; + while (!(next = it.next()).done) p = callback(p, next.value, i++, this); return p; } @@ -377,53 +447,59 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap * @param reusedArray Optional array used repeatedly to store key-value * pairs, to avoid creating a new array on every iteration. */ - entries(lowestKey?: K, reusedArray?: (K|V)[]): IterableIterator<[K,V]> { + entries(lowestKey?: K, reusedArray?: (K | V)[]): IterableIterator<[K, V]> { var info = this.findPath(lowestKey); - if (info === undefined) return iterator<[K,V]>(); - var {nodequeue, nodeindex, leaf} = info; + if (info === undefined) return iterator<[K, V]>(); + var { nodequeue, nodeindex, leaf } = info; var state = reusedArray !== undefined ? 1 : 0; - var i = (lowestKey === undefined ? -1 : leaf.indexOf(lowestKey, 0, this._compare) - 1); + var i = + lowestKey === undefined + ? -1 + : leaf.indexOf(lowestKey, 0, this._compare) - 1; - return iterator<[K,V]>(() => { + return iterator<[K, V]>(() => { jump: for (;;) { - switch(state) { + switch (state) { case 0: if (++i < leaf.keys.length) - return {done: false, value: [leaf.keys[i], leaf.values[i]]}; + return { done: false, value: [leaf.keys[i], leaf.values[i]] }; state = 2; continue; case 1: if (++i < leaf.keys.length) { - reusedArray![0] = leaf.keys[i], reusedArray![1] = leaf.values[i]; - return {done: false, value: reusedArray as [K,V]}; + (reusedArray![0] = leaf.keys[i]), + (reusedArray![1] = leaf.values[i]); + return { done: false, value: reusedArray as [K, V] }; } state = 2; case 2: // Advance to the next leaf node - for (var level = -1;;) { + for (var level = -1; ; ) { if (++level >= nodequeue.length) { - state = 3; continue jump; + state = 3; + continue jump; } - if (++nodeindex[level] < nodequeue[level].length) - break; + if (++nodeindex[level] < nodequeue[level].length) break; } for (; level > 0; level--) { - nodequeue[level-1] = (nodequeue[level][nodeindex[level]] as BNodeInternal<K,V>).children; - nodeindex[level-1] = 0; + nodequeue[level - 1] = (nodequeue[level][ + nodeindex[level] + ] as BNodeInternal<K, V>).children; + nodeindex[level - 1] = 0; } leaf = nodequeue[0][nodeindex[0]]; i = -1; state = reusedArray !== undefined ? 1 : 0; continue; case 3: - return {done: true, value: undefined}; + return { done: true, value: undefined }; } } }); } /** Returns an iterator that provides items in reversed order. - * @param highestKey Key at which to start iterating, or undefined to + * @param highestKey Key at which to start iterating, or undefined to * start at minKey(). If the specified key doesn't exist then iteration * starts at the next lower key (according to the comparator). * @param reusedArray Optional array used repeatedly to store key-value @@ -431,49 +507,56 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap * @param skipHighest Iff this flag is true and the highestKey exists in the * collection, the pair matching highestKey is skipped, not iterated. */ - entriesReversed(highestKey?: K, reusedArray?: (K|V)[], skipHighest?: boolean): IterableIterator<[K,V]> { + entriesReversed( + highestKey?: K, + reusedArray?: (K | V)[], + skipHighest?: boolean, + ): IterableIterator<[K, V]> { if ((highestKey = highestKey || this.maxKey()) === undefined) - return iterator<[K,V]>(); // collection is empty - var {nodequeue,nodeindex,leaf} = this.findPath(highestKey) || this.findPath(this.maxKey())!; + return iterator<[K, V]>(); // collection is empty + var { nodequeue, nodeindex, leaf } = + this.findPath(highestKey) || this.findPath(this.maxKey())!; check(!nodequeue[0] || leaf === nodequeue[0][nodeindex[0]], "wat!"); var i = leaf.indexOf(highestKey, 0, this._compare); - if (!(skipHighest || this._compare(leaf.keys[i], highestKey) > 0)) - i++; + if (!(skipHighest || this._compare(leaf.keys[i], highestKey) > 0)) i++; var state = reusedArray !== undefined ? 1 : 0; - return iterator<[K,V]>(() => { + return iterator<[K, V]>(() => { jump: for (;;) { - switch(state) { + switch (state) { case 0: if (--i >= 0) - return {done: false, value: [leaf.keys[i], leaf.values[i]]}; + return { done: false, value: [leaf.keys[i], leaf.values[i]] }; state = 2; continue; case 1: if (--i >= 0) { - reusedArray![0] = leaf.keys[i], reusedArray![1] = leaf.values[i]; - return {done: false, value: reusedArray as [K,V]}; + (reusedArray![0] = leaf.keys[i]), + (reusedArray![1] = leaf.values[i]); + return { done: false, value: reusedArray as [K, V] }; } state = 2; case 2: // Advance to the next leaf node - for (var level = -1;;) { + for (var level = -1; ; ) { if (++level >= nodequeue.length) { - state = 3; continue jump; + state = 3; + continue jump; } - if (--nodeindex[level] >= 0) - break; + if (--nodeindex[level] >= 0) break; } for (; level > 0; level--) { - nodequeue[level-1] = (nodequeue[level][nodeindex[level]] as BNodeInternal<K,V>).children; - nodeindex[level-1] = nodequeue[level-1].length-1; + nodequeue[level - 1] = (nodequeue[level][ + nodeindex[level] + ] as BNodeInternal<K, V>).children; + nodeindex[level - 1] = nodequeue[level - 1].length - 1; } leaf = nodequeue[0][nodeindex[0]]; i = leaf.keys.length; state = reusedArray !== undefined ? 1 : 0; continue; case 3: - return {done: true, value: undefined}; + return { done: true, value: undefined }; } } }); @@ -481,36 +564,39 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap /* Used by entries() and entriesReversed() to prepare to start iterating. * It develops a "node queue" for each non-leaf level of the tree. - * Levels are numbered "bottom-up" so that level 0 is a list of leaf + * Levels are numbered "bottom-up" so that level 0 is a list of leaf * nodes from a low-level non-leaf node. The queue at a given level L - * consists of nodequeue[L] which is the children of a BNodeInternal, + * consists of nodequeue[L] which is the children of a BNodeInternal, * and nodeindex[L], the current index within that child list, such * such that nodequeue[L-1] === nodequeue[L][nodeindex[L]].children. * (However inside this function the order is reversed.) */ - private findPath(key?: K): { nodequeue: BNode<K,V>[][], nodeindex: number[], leaf: BNode<K,V> } | undefined - { + private findPath( + key?: K, + ): + | { nodequeue: BNode<K, V>[][]; nodeindex: number[]; leaf: BNode<K, V> } + | undefined { var nextnode = this._root; - var nodequeue: BNode<K,V>[][], nodeindex: number[]; + var nodequeue: BNode<K, V>[][], nodeindex: number[]; if (nextnode.isLeaf) { - nodequeue = EmptyArray, nodeindex = EmptyArray; // avoid allocations + (nodequeue = EmptyArray), (nodeindex = EmptyArray); // avoid allocations } else { - nodequeue = [], nodeindex = []; + (nodequeue = []), (nodeindex = []); for (var d = 0; !nextnode.isLeaf; d++) { - nodequeue[d] = (nextnode as BNodeInternal<K,V>).children; - nodeindex[d] = key === undefined ? 0 : nextnode.indexOf(key, 0, this._compare); - if (nodeindex[d] >= nodequeue[d].length) - return; // first key > maxKey() + nodequeue[d] = (nextnode as BNodeInternal<K, V>).children; + nodeindex[d] = + key === undefined ? 0 : nextnode.indexOf(key, 0, this._compare); + if (nodeindex[d] >= nodequeue[d].length) return; // first key > maxKey() nextnode = nodequeue[d][nodeindex[d]]; } nodequeue.reverse(); nodeindex.reverse(); } - return {nodequeue, nodeindex, leaf:nextnode}; + return { nodequeue, nodeindex, leaf: nextnode }; } - /** Returns a new iterator for iterating the keys of each pair in ascending order. + /** Returns a new iterator for iterating the keys of each pair in ascending order. * @param firstKey: Minimum key to include in the output. */ keys(firstKey?: K): IterableIterator<K> { var it = this.entries(firstKey, ReusedArray); @@ -520,8 +606,8 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap return n; }); } - - /** Returns a new iterator for iterating the values of each pair in order by key. + + /** Returns a new iterator for iterating the values of each pair in order by key. * @param firstKey: Minimum key whose associated value is included in the output. */ values(firstKey?: K): IterableIterator<V> { var it = this.entries(firstKey, ReusedArray); @@ -540,57 +626,79 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap } /** Gets the lowest key in the tree. Complexity: O(log size) */ - minKey(): K | undefined { return this._root.minKey(); } - + minKey(): K | undefined { + return this._root.minKey(); + } + /** Gets the highest key in the tree. Complexity: O(1) */ - maxKey(): K | undefined { return this._root.maxKey(); } + maxKey(): K | undefined { + return this._root.maxKey(); + } - /** Quickly clones the tree by marking the root node as shared. + /** Quickly clones the tree by marking the root node as shared. * Both copies remain editable. When you modify either copy, any * nodes that are shared (or potentially shared) between the two * copies are cloned so that the changes do not affect other copies. * This is known as copy-on-write behavior, or "lazy copying". */ - clone(): BTree<K,V> { + clone(): BTree<K, V> { this._root.isShared = true; - var result = new BTree<K,V>(undefined, this._compare, this._maxNodeSize); + var result = new BTree<K, V>(undefined, this._compare, this._maxNodeSize); result._root = this._root; result._size = this._size; return result; } - /** Performs a greedy clone, immediately duplicating any nodes that are + /** 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> { - var result = new BTree<K,V>(undefined, this._compare, this._maxNodeSize); + greedyClone(force?: boolean): BTree<K, V> { + var result = new BTree<K, V>(undefined, this._compare, this._maxNodeSize); result._root = this._root.greedyClone(force); result._size = this._size; return result; } /** Gets an array filled with the contents of the tree, sorted by key */ - toArray(maxLength: number = 0x7FFFFFFF): [K,V][] { - let min = this.minKey(), max = this.maxKey(); - if (min !== undefined) - return this.getRange(min, max!, true, maxLength) + toArray(maxLength: number = 0x7fffffff): [K, V][] { + let min = this.minKey(), + max = this.maxKey(); + if (min !== undefined) return this.getRange(min, max!, true, maxLength); return []; } /** Gets an array of all keys, sorted */ keysArray() { var results: K[] = []; - this._root.forRange(this.minKey()!, this.maxKey()!, true, false, this, 0, - (k,v) => { results.push(k); }); + this._root.forRange( + this.minKey()!, + this.maxKey()!, + true, + false, + this, + 0, + (k, v) => { + results.push(k); + }, + ); return results; } - + /** Gets an array of all values, sorted by key */ valuesArray() { var results: V[] = []; - this._root.forRange(this.minKey()!, this.maxKey()!, true, false, this, 0, - (k,v) => { results.push(v); }); + this._root.forRange( + this.minKey()!, + this.maxKey()!, + true, + false, + this, + 0, + (k, v) => { + results.push(v); + }, + ); return results; } @@ -599,45 +707,44 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap return this.toArray().toString(); } - /** Stores a key-value pair only if the key doesn't already exist in the tree. + /** Stores a key-value pair only if the key doesn't already exist in the tree. * @returns true if a new key was added - */ + */ setIfNotPresent(key: K, value: V): boolean { return this.set(key, value, false); } /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */ - nextHigherPair(key: K): [K,V]|undefined { + nextHigherPair(key: K): [K, V] | undefined { var it = this.entries(key, ReusedArray); var r = it.next(); - if (!r.done && this._compare(r.value[0], key) <= 0) - r = it.next(); + if (!r.done && this._compare(r.value[0], key) <= 0) r = it.next(); return r.value; } - + /** Returns the next key larger than the specified key (or undefined if there is none) */ - nextHigherKey(key: K): K|undefined { + nextHigherKey(key: K): K | undefined { var p = this.nextHigherPair(key); return p ? p[0] : p; } /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */ - nextLowerPair(key: K): [K,V]|undefined { + nextLowerPair(key: K): [K, V] | undefined { var it = this.entriesReversed(key, ReusedArray, true); return it.next().value; } - + /** Returns the next key smaller than the specified key (or undefined if there is none) */ - nextLowerKey(key: K): K|undefined { + nextLowerKey(key: K): K | undefined { var p = this.nextLowerPair(key); return p ? p[0] : p; } - /** Edits the value associated with a key in the tree, if it already exists. + /** Edits the value associated with a key in the tree, if it already exists. * @returns true if the key existed, false if not. - */ - changeIfPresent(key: K, value: V): boolean { - return this.editRange(key, key, true, (k,v) => ({value})) !== 0; + */ + changeIfPresent(key: K, value: V): boolean { + return this.editRange(key, key, true, (k, v) => ({ value })) !== 0; } /** @@ -648,106 +755,154 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap * @param includeHigh If the `high` key is present, its pair will be included * in the output if and only if this parameter is true. Note: if the * `low` key is present, it is always included in the output. - * @param maxLength Length limit. getRange will stop scanning the tree when + * @param maxLength Length limit. getRange will stop scanning the tree when * the array reaches this size. * @description Computational complexity: O(result.length + log size) */ - getRange(low: K, high: K, includeHigh?: boolean, maxLength: number = 0x3FFFFFF): [K,V][] { - var results: [K,V][] = []; - this._root.forRange(low, high, includeHigh, false, this, 0, (k,v) => { - results.push([k,v]) + getRange( + low: K, + high: K, + includeHigh?: boolean, + maxLength: number = 0x3ffffff, + ): [K, V][] { + var results: [K, V][] = []; + this._root.forRange(low, high, includeHigh, false, this, 0, (k, v) => { + results.push([k, v]); return results.length > maxLength ? Break : undefined; }); return results; } /** Adds all pairs from a list of key-value pairs. - * @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]] + * @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.) * @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)) */ - setPairs(pairs: [K,V][], overwrite?: boolean): number { + setPairs(pairs: [K, V][], overwrite?: boolean): number { var added = 0; for (var i = 0; i < pairs.length; i++) - if (this.set(pairs[i][0], pairs[i][1], overwrite)) - added++; + if (this.set(pairs[i][0], pairs[i][1], overwrite)) added++; return added; } - forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number; + forRange( + low: K, + high: K, + includeHigh: boolean, + onFound?: (k: K, v: V, counter: number) => void, + initialCounter?: number, + ): number; /** * Scans the specified range of keys, in ascending order by key. * Note: the callback `onFound` must not insert or remove items in the - * collection. Doing so may cause incorrect data to be sent to the + * collection. Doing so may cause incorrect data to be sent to the * callback afterward. * @param low The first key scanned will be greater than or equal to `low`. * @param high Scanning stops when a key larger than this is reached. * @param includeHigh If the `high` key is present, `onFound` is called for * that final pair if and only if this parameter is true. - * @param onFound A function that is called for each key-value pair. This + * @param onFound A function that is called for each key-value pair. This * function can return {break:R} to stop early with result R. - * @param initialCounter Initial third argument of onFound. This value + * @param initialCounter Initial third argument of onFound. This value * increases by one each time `onFound` is called. Default: 0 - * @returns The number of values found, or R if the callback returned + * @returns The number of values found, or R if the callback returned * `{break:R}` to stop early. * @description Computational complexity: O(number of items scanned + log size) */ - forRange<R=number>(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => {break?:R}|void, initialCounter?: number): R|number { - var r = this._root.forRange(low, high, includeHigh, false, this, initialCounter || 0, onFound); + forRange<R = number>( + low: K, + high: K, + includeHigh: boolean, + onFound?: (k: K, v: V, counter: number) => { break?: R } | void, + initialCounter?: number, + ): R | number { + var r = this._root.forRange( + low, + high, + includeHigh, + false, + this, + initialCounter || 0, + onFound, + ); return typeof r === "number" ? r : r.break!; } /** * Scans and potentially modifies values for a subsequence of keys. - * Note: the callback `onFound` should ideally be a pure function. - * Specfically, it must not insert items, call clone(), or change + * Note: the callback `onFound` should ideally be a pure function. + * Specfically, it must not insert items, call clone(), or change * the collection except via return value; out-of-band editing may * cause an exception or may cause incorrect data to be sent to - * the callback (duplicate or missed items). It must not cause a + * the callback (duplicate or missed items). It must not cause a * clone() of the collection, otherwise the clone could be modified * by changes requested by the callback. * @param low The first key scanned will be greater than or equal to `low`. * @param high Scanning stops when a key larger than this is reached. * @param includeHigh If the `high` key is present, `onFound` is called for * that final pair if and only if this parameter is true. - * @param onFound A function that is called for each key-value pair. This - * function can return `{value:v}` to change the value associated + * @param onFound A function that is called for each key-value pair. This + * function can return `{value:v}` to change the value associated * with the current key, `{delete:true}` to delete the current pair, * `{break:R}` to stop early with result R, or it can return nothing * (undefined or {}) to cause no effect and continue iterating. * `{break:R}` can be combined with one of the other two commands. - * The third argument `counter` is the number of items iterated + * The third argument `counter` is the number of items iterated * previously; it equals 0 when `onFound` is called the first time. - * @returns The number of values scanned, or R if the callback returned + * @returns The number of values scanned, or R if the callback returned * `{break:R}` to stop early. - * @description + * @description * Computational complexity: O(number of items scanned + log size) * Note: if the tree has been cloned with clone(), any shared - * nodes are copied before `onFound` is called. This takes O(n) time + * nodes are copied before `onFound` is called. This takes O(n) time * where n is proportional to the amount of shared data scanned. */ - editRange<R=V>(low: K, high: K, includeHigh: boolean, onFound: (k:K,v:V,counter:number) => EditRangeResult<V,R>|void, initialCounter?: number): R|number { + editRange<R = V>( + low: K, + high: K, + includeHigh: boolean, + onFound: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void, + initialCounter?: number, + ): R | number { var root = this._root; - if (root.isShared) - this._root = root = root.clone(); + if (root.isShared) this._root = root = root.clone(); try { - var r = root.forRange(low, high, includeHigh, true, this, initialCounter || 0, onFound); + var r = root.forRange( + low, + high, + includeHigh, + true, + this, + initialCounter || 0, + onFound, + ); return typeof r === "number" ? r : r.break!; } finally { while (root.keys.length <= 1 && !root.isLeaf) - this._root = root = root.keys.length === 0 ? EmptyLeaf : - (root as any as BNodeInternal<K,V>).children[0]; + this._root = root = + root.keys.length === 0 + ? EmptyLeaf + : ((root as any) as BNodeInternal<K, V>).children[0]; } } /** 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 { - return this.editRange(this.minKey()!, this.maxKey()!, true, onFound, initialCounter); + editAll<R = V>( + onFound: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void, + initialCounter?: number, + ): R | number { + return this.editRange( + this.minKey()!, + this.maxKey()!, + true, + onFound, + initialCounter, + ); } /** @@ -764,13 +919,11 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap /** Deletes a series of keys from the collection. */ deleteKeys(keys: K[]): number { - for (var i = 0, r = 0; i < keys.length; i++) - if (this.delete(keys[i])) - r++; + for (var i = 0, r = 0; i < keys.length; i++) if (this.delete(keys[i])) r++; return r; } - /** Gets the height of the tree: the number of internal nodes between the + /** Gets the height of the tree: the number of internal nodes between the * BTree object and its leaf nodes (zero if there are no internal nodes). */ get height(): number { for (var node = this._root, h = -1; node != null; h++) @@ -780,15 +933,15 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap /** Makes the object read-only to ensure it is not accidentally modified. * Freezing does not have to be permanent; unfreeze() reverses the effect. - * This is accomplished by replacing mutator functions with a function - * that throws an Error. Compared to using a property (e.g. this.isFrozen) + * This is accomplished by replacing mutator functions with a function + * that throws an Error. Compared to using a property (e.g. this.isFrozen) * this implementation gives better performance in non-frozen BTrees. */ freeze() { var t = this as any; - // Note: all other mutators ultimately call set() or editRange() + // Note: all other mutators ultimately call set() or editRange() // so we don't need to override those others. - t.clear = t.set = t.editRange = function() { + t.clear = t.set = t.editRange = function () { throw new Error("Attempted to modify a frozen BTree"); }; } @@ -802,7 +955,7 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap /** Returns true if the tree appears to be frozen. */ get isFrozen() { - return this.hasOwnProperty('editRange'); + return this.hasOwnProperty("editRange"); } /** Scans the tree for signs of serious bugs (e.g. this.size doesn't match @@ -812,65 +965,81 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap * does check that maxKey() of the children of internal nodes are sorted. */ checkValid() { var size = this._root.checkValid(0, this); - check(size === this.size, "size mismatch: counted ", size, "but stored", this.size); + check( + size === this.size, + "size mismatch: counted ", + size, + "but stored", + this.size, + ); } } declare const Symbol: any; -if (Symbol && Symbol.iterator) // iterator is equivalent to entries() +if (Symbol && Symbol.iterator) + // iterator is equivalent to entries() (BTree as any).prototype[Symbol.iterator] = BTree.prototype.entries; (BTree as any).prototype.where = BTree.prototype.filter; (BTree as any).prototype.setRange = BTree.prototype.setPairs; (BTree as any).prototype.add = BTree.prototype.set; -function iterator<T>(next: () => {done?:boolean,value?:T} = (() => ({ done:true, value:undefined }))): IterableIterator<T> { +function iterator<T>( + next: () => { done?: boolean; value?: T } = () => ({ + done: true, + value: undefined, + }), +): IterableIterator<T> { var result: any = { next }; if (Symbol && Symbol.iterator) - result[Symbol.iterator] = function() { return this; }; + result[Symbol.iterator] = function () { + return this; + }; return result; } - /** Leaf node / base class. **************************************************/ -class BNode<K,V> { +class BNode<K, V> { // If this is an internal node, _keys[i] is the highest key in children[i]. keys: K[]; values: V[]; isShared: true | undefined; - get isLeaf() { return (this as any).children === undefined; } - + get isLeaf() { + return (this as any).children === undefined; + } + constructor(keys: K[] = [], values?: V[]) { this.keys = keys; - this.values = values || undefVals as any[]; + this.values = values || (undefVals as any[]); this.isShared = undefined; } // Shared methods ///////////////////////////////////////////////////////// maxKey() { - return this.keys[this.keys.length-1]; + return this.keys[this.keys.length - 1]; } // If key not found, returns i^failXor where i is the insertion index. // Callers that don't care whether there was a match will set failXor=0. - indexOf(key: K, failXor: number, cmp: (a:K, b:K) => number): index { + indexOf(key: K, failXor: number, cmp: (a: K, b: K) => number): index { // TODO: benchmark multiple search strategies const keys = this.keys; - var lo = 0, hi = keys.length, mid = hi >> 1; - while(lo < hi) { + var lo = 0, + hi = keys.length, + mid = hi >> 1; + while (lo < hi) { var c = cmp(keys[mid], key); - if (c < 0) - lo = mid + 1; - else if (c > 0) // key < keys[mid] + if (c < 0) lo = mid + 1; + else if (c > 0) + // key < keys[mid] hi = mid; - else if (c === 0) - return mid; + else if (c === 0) return mid; else { // c is NaN or otherwise invalid - if (key === key) // at least the search key is not NaN + if (key === key) + // at least the search key is not NaN return keys.length; - else - throw new Error("BTree: NaN was used as a key"); + else throw new Error("BTree: NaN was used as a key"); } mid = (lo + hi) >> 1; } @@ -928,26 +1097,36 @@ class BNode<K,V> { return this.keys[0]; } - clone(): BNode<K,V> { + clone(): BNode<K, V> { var v = this.values; - return new BNode<K,V>(this.keys.slice(0), v === undefVals ? v : v.slice(0)); + return new BNode<K, V>( + this.keys.slice(0), + v === undefVals ? v : v.slice(0), + ); } - greedyClone(force?: boolean): BNode<K,V> { + greedyClone(force?: boolean): BNode<K, V> { return this.isShared && !force ? this : this.clone(); } - get(key: K, defaultValue: V|undefined, tree: BTree<K,V>): V|undefined { + get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined { var i = this.indexOf(key, -1, tree._compare); return i < 0 ? defaultValue : this.values[i]; } - checkValid(depth: number, tree: BTree<K,V>): number { - var kL = this.keys.length, vL = this.values.length; - check(this.values === undefVals ? kL <= vL : kL === vL, - "keys/values length mismatch: depth", depth, "with lengths", kL, vL); + checkValid(depth: number, tree: BTree<K, V>): number { + var kL = this.keys.length, + vL = this.values.length; + check( + this.values === undefVals ? kL <= vL : kL === vL, + "keys/values length mismatch: depth", + depth, + "with lengths", + kL, + vL, + ); // Note: we don't check for "node too small" because sometimes a node - // can legitimately have size 1. This occurs if there is a batch + // can legitimately have size 1. This occurs if there is a batch // deletion, leaving a node of size 1, and the siblings are full so // it can't be merged with adjacent nodes. However, the parent will // verify that the average node size is at least half of the maximum. @@ -957,18 +1136,24 @@ class BNode<K,V> { // Leaf Node: set & node splitting ////////////////////////////////////////// - set(key: K, value: V, overwrite: boolean|undefined, tree: BTree<K,V>): boolean|BNode<K,V> { + set( + key: K, + value: V, + overwrite: boolean | undefined, + tree: BTree<K, V>, + ): boolean | BNode<K, V> { var i = this.indexOf(key, -1, tree._compare); if (i < 0) { // key does not exist yet i = ~i; tree._size++; - + if (this.keys.length < tree._maxNodeSize) { return this.insertInLeaf(i, key, value, tree); } else { // This leaf node is full and must split - var newRightSibling = this.splitOffRightSide(), target: BNode<K,V> = this; + var newRightSibling = this.splitOffRightSide(), + target: BNode<K, V> = this; if (i > this.keys.length) { i -= this.keys.length; target = newRightSibling; @@ -979,8 +1164,7 @@ class BNode<K,V> { } else { // Key already exists if (overwrite !== false) { - if (value !== undefined) - this.reifyValues(); + if (value !== undefined) this.reifyValues(); // usually this is a no-op, but some users may wish to edit the key this.keys[i] = key; this.values[i] = value; @@ -991,15 +1175,14 @@ class BNode<K,V> { reifyValues() { if (this.values === undefVals) - return this.values = this.values.slice(0, this.keys.length); + return (this.values = this.values.slice(0, this.keys.length)); return this.values; } - insertInLeaf(i: index, key: K, value: V, tree: BTree<K,V>) { + insertInLeaf(i: index, key: K, value: V, tree: BTree<K, V>) { this.keys.splice(i, 0, key); if (this.values === undefVals) { - while (undefVals.length < tree._maxNodeSize) - undefVals.push(undefined); + while (undefVals.length < tree._maxNodeSize) undefVals.push(undefined); if (value === undefined) { return true; } else { @@ -1009,15 +1192,14 @@ class BNode<K,V> { this.values.splice(i, 0, value); return true; } - - takeFromRight(rhs: BNode<K,V>) { + + takeFromRight(rhs: BNode<K, V>) { // Reminder: parent node must update its copy of key for this node // assert: neither node is shared // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize) var v = this.values; if (rhs.values === undefVals) { - if (v !== undefVals) - v.push(undefined as any); + if (v !== undefVals) v.push(undefined as any); } else { v = this.reifyValues(); v.push(rhs.values.shift()!); @@ -1025,14 +1207,13 @@ class BNode<K,V> { this.keys.push(rhs.keys.shift()!); } - takeFromLeft(lhs: BNode<K,V>) { + takeFromLeft(lhs: BNode<K, V>) { // Reminder: parent node must update its copy of key for this node // assert: neither node is shared // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize) var v = this.values; if (lhs.values === undefVals) { - if (v !== undefVals) - v.unshift(undefined as any); + if (v !== undefVals) v.unshift(undefined as any); } else { v = this.reifyValues(); v.unshift(lhs.values.pop()!); @@ -1040,36 +1221,42 @@ class BNode<K,V> { this.keys.unshift(lhs.keys.pop()!); } - splitOffRightSide(): BNode<K,V> { + splitOffRightSide(): BNode<K, V> { // Reminder: parent node must update its copy of key for this node - var half = this.keys.length >> 1, keys = this.keys.splice(half); - var values = this.values === undefVals ? undefVals : this.values.splice(half); - return new BNode<K,V>(keys, values); + var half = this.keys.length >> 1, + keys = this.keys.splice(half); + var values = + this.values === undefVals ? undefVals : this.values.splice(half); + return new BNode<K, V>(keys, values); } // Leaf Node: scanning & deletions ////////////////////////////////////////// - forRange<R>(low: K, high: K, includeHigh: boolean|undefined, editMode: boolean, tree: BTree<K,V>, count: number, - onFound?: (k:K, v:V, counter:number) => EditRangeResult<V,R>|void): EditRangeResult<V,R>|number { + forRange<R>( + low: K, + high: K, + includeHigh: boolean | undefined, + editMode: boolean, + tree: BTree<K, V>, + count: number, + onFound?: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void, + ): EditRangeResult<V, R> | number { var cmp = tree._compare; var iLow, iHigh; if (high === low) { - if (!includeHigh) - return count; + if (!includeHigh) return count; iHigh = (iLow = this.indexOf(low, -1, cmp)) + 1; - if (iLow < 0) - return count; + if (iLow < 0) return count; } else { iLow = this.indexOf(low, 0, cmp); iHigh = this.indexOf(high, -1, cmp); - if (iHigh < 0) - iHigh = ~iHigh; - else if (includeHigh === true) - iHigh++; + if (iHigh < 0) iHigh = ~iHigh; + else if (includeHigh === true) iHigh++; } - var keys = this.keys, values = this.values; + var keys = this.keys, + values = this.values; if (onFound !== undefined) { - for(var i = iLow; i < iHigh; i++) { + for (var i = iLow; i < iHigh; i++) { var key = keys[i]; var result = onFound(key, values[i], count++); if (result !== undefined) { @@ -1078,30 +1265,26 @@ class BNode<K,V> { throw new Error("BTree illegally changed or cloned in editRange"); if (result.delete) { this.keys.splice(i, 1); - if (this.values !== undefVals) - this.values.splice(i, 1); + if (this.values !== undefVals) this.values.splice(i, 1); tree._size--; i--; iHigh--; - } else if (result.hasOwnProperty('value')) { + } else if (result.hasOwnProperty("value")) { values![i] = result.value!; } } - if (result.break !== undefined) - return result; + if (result.break !== undefined) return result; } } - } else - count += iHigh - iLow; + } else count += iHigh - iLow; return count; } /** Adds entire contents of right-hand sibling (rhs is left unchanged) */ - mergeSibling(rhs: BNode<K,V>, _: number) { + mergeSibling(rhs: BNode<K, V>, _: number) { this.keys.push.apply(this.keys, rhs.keys); if (this.values === undefVals) { - if (rhs.values === undefVals) - return; + if (rhs.values === undefVals) return; this.values = this.values.slice(0, this.keys.length); } this.values.push.apply(this.values, rhs.reifyValues()); @@ -1109,33 +1292,33 @@ class BNode<K,V> { } /** Internal node (non-leaf node) ********************************************/ -class BNodeInternal<K,V> extends BNode<K,V> { - // Note: conventionally B+ trees have one fewer key than the number of +class BNodeInternal<K, V> extends BNode<K, V> { + // Note: conventionally B+ trees have one fewer key than the number of // children, but I find it easier to keep the array lengths equal: each // keys[i] caches the value of children[i].maxKey(). - children: BNode<K,V>[]; + children: BNode<K, V>[]; - constructor(children: BNode<K,V>[], keys?: K[]) { + constructor(children: BNode<K, V>[], keys?: K[]) { if (!keys) { keys = []; - for (var i = 0; i < children.length; i++) - keys[i] = children[i].maxKey(); + for (var i = 0; i < children.length; i++) keys[i] = children[i].maxKey(); } super(keys); this.children = children; } - clone(): BNode<K,V> { + clone(): BNode<K, V> { var children = this.children.slice(0); - for (var i = 0; i < children.length; i++) - children[i].isShared = true; - return new BNodeInternal<K,V>(children, this.keys.slice(0)); + for (var i = 0; i < children.length; i++) children[i].isShared = true; + return new BNodeInternal<K, V>(children, this.keys.slice(0)); } - greedyClone(force?: boolean): BNode<K,V> { - if (this.isShared && !force) - return this; - var nu = new BNodeInternal<K,V>(this.children.slice(0), this.keys.slice(0)); + greedyClone(force?: boolean): BNode<K, V> { + if (this.isShared && !force) return this; + var nu = new BNodeInternal<K, V>( + this.children.slice(0), + this.keys.slice(0), + ); for (var i = 0; i < nu.children.length; i++) nu.children[i] = nu.children[i].greedyClone(); return nu; @@ -1145,141 +1328,229 @@ class BNodeInternal<K,V> extends BNode<K,V> { return this.children[0].minKey(); } - get(key: K, defaultValue: V|undefined, tree: BTree<K,V>): V|undefined { - var i = this.indexOf(key, 0, tree._compare), children = this.children; - return i < children.length ? children[i].get(key, defaultValue, tree) : undefined; - } - - checkValid(depth: number, tree: BTree<K,V>) : number { - var kL = this.keys.length, cL = this.children.length; - check(kL === cL, "keys/children length mismatch: depth", depth, "lengths", kL, cL); + get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined { + var i = this.indexOf(key, 0, tree._compare), + children = this.children; + return i < children.length + ? children[i].get(key, defaultValue, tree) + : undefined; + } + + checkValid(depth: number, tree: BTree<K, V>): number { + var kL = this.keys.length, + cL = this.children.length; + check( + kL === cL, + "keys/children length mismatch: depth", + depth, + "lengths", + kL, + cL, + ); check(kL > 1, "internal node has length", kL, "at depth", depth); - var size = 0, c = this.children, k = this.keys, childSize = 0; + var size = 0, + c = this.children, + k = this.keys, + childSize = 0; for (var i = 0; i < cL; i++) { size += c[i].checkValid(depth + 1, tree); childSize += c[i].keys.length; check(size >= childSize, "wtf"); // no way this will ever fail - check(i === 0 || c[i-1].constructor === c[i].constructor, "type mismatch"); + check( + i === 0 || c[i - 1].constructor === c[i].constructor, + "type mismatch", + ); if (c[i].maxKey() != k[i]) - check(false, "keys[", i, "] =", k[i], "is wrong, should be ", c[i].maxKey(), "at depth", depth); - if (!(i === 0 || tree._compare(k[i-1], k[i]) < 0)) - check(false, "sort violation at depth", depth, "index", i, "keys", k[i-1], k[i]); + check( + false, + "keys[", + i, + "] =", + k[i], + "is wrong, should be ", + c[i].maxKey(), + "at depth", + depth, + ); + if (!(i === 0 || tree._compare(k[i - 1], k[i]) < 0)) + check( + false, + "sort violation at depth", + depth, + "index", + i, + "keys", + k[i - 1], + k[i], + ); } - var toofew = childSize < (tree.maxNodeSize >> 1)*cL; - if (toofew || childSize > tree.maxNodeSize*cL) - check(false, toofew ? "too few" : "too many", "children (", childSize, size, ") at depth", depth, ", maxNodeSize:", tree.maxNodeSize, "children.length:", cL); + var toofew = childSize < (tree.maxNodeSize >> 1) * cL; + if (toofew || childSize > tree.maxNodeSize * cL) + check( + false, + toofew ? "too few" : "too many", + "children (", + childSize, + size, + ") at depth", + depth, + ", maxNodeSize:", + tree.maxNodeSize, + "children.length:", + cL, + ); return size; } // Internal Node: set & node splitting ////////////////////////////////////// - set(key: K, value: V, overwrite: boolean|undefined, tree: BTree<K,V>): boolean|BNodeInternal<K,V> { - var c = this.children, max = tree._maxNodeSize, cmp = tree._compare; - var i = Math.min(this.indexOf(key, 0, cmp), c.length - 1), child = c[i]; - - if (child.isShared) - c[i] = child = child.clone(); + set( + key: K, + value: V, + overwrite: boolean | undefined, + tree: BTree<K, V>, + ): boolean | BNodeInternal<K, V> { + var c = this.children, + max = tree._maxNodeSize, + cmp = tree._compare; + var i = Math.min(this.indexOf(key, 0, cmp), c.length - 1), + child = c[i]; + + if (child.isShared) c[i] = child = child.clone(); if (child.keys.length >= max) { // child is full; inserting anything else will cause a split. // Shifting an item to the left or right sibling may avoid a split. // We can do a shift if the adjacent node is not full and if the // current key can still be placed in the same node after the shift. - var other: BNode<K,V>; - if (i > 0 && (other = c[i-1]).keys.length < max && cmp(child.keys[0], key) < 0) { - if (other.isShared) - c[i-1] = other = other.clone(); + var other: BNode<K, V>; + if ( + i > 0 && + (other = c[i - 1]).keys.length < max && + cmp(child.keys[0], key) < 0 + ) { + if (other.isShared) c[i - 1] = other = other.clone(); other.takeFromRight(child); - this.keys[i-1] = other.maxKey(); - } else if ((other = c[i+1]) !== undefined && other.keys.length < max && cmp(child.maxKey(), key) < 0) { - if (other.isShared) - c[i+1] = other = other.clone(); + this.keys[i - 1] = other.maxKey(); + } else if ( + (other = c[i + 1]) !== undefined && + other.keys.length < max && + cmp(child.maxKey(), key) < 0 + ) { + if (other.isShared) c[i + 1] = other = other.clone(); other.takeFromLeft(child); this.keys[i] = c[i].maxKey(); } } var result = child.set(key, value, overwrite, tree); - if (result === false) - return false; + if (result === false) return false; this.keys[i] = child.maxKey(); - if (result === true) - return true; + if (result === true) return true; // The child has split and `result` is a new right child... does it fit? - if (this.keys.length < max) { // yes - this.insert(i+1, result); + if (this.keys.length < max) { + // yes + this.insert(i + 1, result); return true; - } else { // no, we must split also - var newRightSibling = this.splitOffRightSide(), target: BNodeInternal<K,V> = this; + } else { + // no, we must split also + var newRightSibling = this.splitOffRightSide(), + target: BNodeInternal<K, V> = this; if (cmp(result.maxKey(), this.maxKey()) > 0) { target = newRightSibling; i -= this.keys.length; } - target.insert(i+1, result); + target.insert(i + 1, result); return newRightSibling; } } - insert(i: index, child: BNode<K,V>) { + insert(i: index, child: BNode<K, V>) { this.children.splice(i, 0, child); this.keys.splice(i, 0, child.maxKey()); } splitOffRightSide() { var half = this.children.length >> 1; - return new BNodeInternal<K,V>(this.children.splice(half), this.keys.splice(half)); + return new BNodeInternal<K, V>( + this.children.splice(half), + this.keys.splice(half), + ); } - takeFromRight(rhs: BNode<K,V>) { + takeFromRight(rhs: BNode<K, V>) { // Reminder: parent node must update its copy of key for this node // assert: neither node is shared // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize) this.keys.push(rhs.keys.shift()!); - this.children.push((rhs as BNodeInternal<K,V>).children.shift()!); + this.children.push((rhs as BNodeInternal<K, V>).children.shift()!); } - takeFromLeft(lhs: BNode<K,V>) { + takeFromLeft(lhs: BNode<K, V>) { // Reminder: parent node must update its copy of key for this node // assert: neither node is shared // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize) this.keys.unshift(lhs.keys.pop()!); - this.children.unshift((lhs as BNodeInternal<K,V>).children.pop()!); + this.children.unshift((lhs as BNodeInternal<K, V>).children.pop()!); } // Internal Node: scanning & deletions ////////////////////////////////////// - forRange<R>(low: K, high: K, includeHigh: boolean|undefined, editMode: boolean, tree: BTree<K,V>, count: number, - onFound?: (k:K, v:V, counter:number) => EditRangeResult<V,R>|void): EditRangeResult<V,R>|number - { + forRange<R>( + low: K, + high: K, + includeHigh: boolean | undefined, + editMode: boolean, + tree: BTree<K, V>, + count: number, + onFound?: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void, + ): EditRangeResult<V, R> | number { var cmp = tree._compare; - var iLow = this.indexOf(low, 0, cmp), i = iLow; - var iHigh = Math.min(high === low ? iLow : this.indexOf(high, 0, cmp), this.keys.length-1); - var keys = this.keys, children = this.children; + var iLow = this.indexOf(low, 0, cmp), + i = iLow; + var iHigh = Math.min( + high === low ? iLow : this.indexOf(high, 0, cmp), + this.keys.length - 1, + ); + var keys = this.keys, + children = this.children; if (!editMode) { // Simple case - for(; i <= iHigh; i++) { - var result = children[i].forRange(low, high, includeHigh, editMode, tree, count, onFound); - if (typeof result !== 'number') - return result; + for (; i <= iHigh; i++) { + var result = children[i].forRange( + low, + high, + includeHigh, + editMode, + tree, + count, + onFound, + ); + if (typeof result !== "number") return result; count = result; } } else if (i <= iHigh) { try { - for(; i <= iHigh; i++) { - if (children[i].isShared) - children[i] = children[i].clone(); - var result = children[i].forRange(low, high, includeHigh, editMode, tree, count, onFound); + for (; i <= iHigh; i++) { + if (children[i].isShared) children[i] = children[i].clone(); + var result = children[i].forRange( + low, + high, + includeHigh, + editMode, + tree, + count, + onFound, + ); keys[i] = children[i].maxKey(); - if (typeof result !== 'number') - return result; + if (typeof result !== "number") return result; count = result; } } finally { // Deletions may have occurred, so look for opportunities to merge nodes. var half = tree._maxNodeSize >> 1; - if (iLow > 0) - iLow--; - for(i = iHigh; i >= iLow; i--) { + if (iLow > 0) iLow--; + for (i = iHigh; i >= iLow; i--) { if (children[i].keys.length <= half) this.tryMerge(i, tree._maxNodeSize); } @@ -1298,10 +1569,11 @@ class BNodeInternal<K,V> extends BNode<K,V> { tryMerge(i: index, maxSize: number): boolean { var children = this.children; if (i >= 0 && i + 1 < children.length) { - if (children[i].keys.length + children[i+1].keys.length <= maxSize) { - if (children[i].isShared) // cloned already UNLESS i is outside scan range + if (children[i].keys.length + children[i + 1].keys.length <= maxSize) { + if (children[i].isShared) + // cloned already UNLESS i is outside scan range children[i] = children[i].clone(); - children[i].mergeSibling(children[i+1], maxSize); + children[i].mergeSibling(children[i + 1], maxSize); children.splice(i + 1, 1); this.keys.splice(i + 1, 1); this.keys[i] = children[i].maxKey(); @@ -1311,15 +1583,18 @@ class BNodeInternal<K,V> extends BNode<K,V> { return false; } - mergeSibling(rhs: BNode<K,V>, maxNodeSize: number) { + mergeSibling(rhs: BNode<K, V>, maxNodeSize: number) { // assert !this.isShared; var oldLength = this.keys.length; this.keys.push.apply(this.keys, rhs.keys); - this.children.push.apply(this.children, (rhs as any as BNodeInternal<K,V>).children); + this.children.push.apply( + this.children, + ((rhs as any) as BNodeInternal<K, V>).children, + ); // If our children are themselves almost empty due to a mass-delete, // they may need to be merged too (but only the oldLength-1 and its // right sibling should need this). - this.tryMerge(oldLength-1, maxNodeSize); + this.tryMerge(oldLength - 1, maxNodeSize); } } @@ -1332,20 +1607,27 @@ class BNodeInternal<K,V> extends BNode<K,V> { // users from making this array too large, BTree has a maximum node size. var undefVals: any[] = []; -const Delete = {delete: true}, DeleteRange = () => Delete; -const Break = {break: true}; -const EmptyLeaf = (function() { - var n = new BNode<any,any>(); n.isShared = true; return n; +const Delete = { delete: true }, + DeleteRange = () => Delete; +const Break = { break: true }; +const EmptyLeaf = (function () { + var n = new BNode<any, any>(); + n.isShared = true; + return n; })(); const EmptyArray: any[] = []; const ReusedArray: any[] = []; // assumed thread-local function check(fact: boolean, ...args: any[]) { if (!fact) { - args.unshift('B+ tree '); // at beginning of message - throw new Error(args.join(' ')); + args.unshift("B+ tree "); // at beginning of message + throw new Error(args.join(" ")); } } /** A BTree frozen in the empty state. */ -export const EmptyBTree = (() => { let t = new BTree(); t.freeze(); return t; })(); +export const EmptyBTree = (() => { + let t = new BTree(); + t.freeze(); + return t; +})(); diff --git a/packages/idb-bridge/src/tree/interfaces.ts b/packages/idb-bridge/src/tree/interfaces.ts index 6bd0cdf58..ce8808d09 100644 --- a/packages/idb-bridge/src/tree/interfaces.ts +++ b/packages/idb-bridge/src/tree/interfaces.ts @@ -24,15 +24,13 @@ SPDX-License-Identifier: MIT // Original repository: https://github.com/qwertie/btree-typescript - /** Read-only set interface (subinterface of IMapSource<K,any>). * The word "set" usually means that each item in the collection is unique - * (appears only once, based on a definition of equality used by the - * collection.) Objects conforming to this interface aren't guaranteed not - * to contain duplicates, but as an example, BTree<K,V> implements this + * (appears only once, based on a definition of equality used by the + * collection.) Objects conforming to this interface aren't guaranteed not + * to contain duplicates, but as an example, BTree<K,V> implements this * interface and does not allow duplicates. */ -export interface ISetSource<K=any> -{ +export interface ISetSource<K = any> { /** Returns the number of key/value pairs in the map object. */ size: number; /** Returns a boolean asserting whether the key exists in the map object or not. */ @@ -42,21 +40,23 @@ export interface ISetSource<K=any> } /** Read-only map interface (i.e. a source of key-value pairs). */ -export interface IMapSource<K=any, V=any> extends ISetSource<K> -{ +export interface IMapSource<K = any, V = any> extends ISetSource<K> { /** Returns the number of key/value pairs in the map object. */ size: number; /** Returns the value associated to the key, or undefined if there is none. */ - get(key: K): V|undefined; + get(key: K): V | undefined; /** Returns a boolean asserting whether the key exists in the map object or not. */ has(key: K): boolean; /** Calls callbackFn once for each key-value pair present in the map object. * The ES6 Map class sends the value to the callback before the key, so * this interface must do likewise. */ - forEach(callbackFn: (v:V, k:K, map:IMapSource<K,V>) => void, thisArg?: any): void; - + forEach( + callbackFn: (v: V, k: K, map: IMapSource<K, V>) => void, + thisArg?: any, + ): void; + /** Returns an iterator that provides all key-value pairs from the collection (as arrays of length 2). */ - entries(): IterableIterator<[K,V]>; + entries(): IterableIterator<[K, V]>; /** Returns a new iterator for iterating the keys of each pair. */ keys(): IterableIterator<K>; /** Returns a new iterator for iterating the values of each pair. */ @@ -65,14 +65,13 @@ export interface IMapSource<K=any, V=any> extends ISetSource<K> //[Symbol.iterator](): IterableIterator<[K,V]>; } -/** Write-only set interface (the set cannot be queried, but items can be added to it.) +/** Write-only set interface (the set cannot be queried, but items can be added to it.) * @description Note: BTree<K,V> does not officially implement this interface, * but BTree<K> can be used as an instance of ISetSink<K>. */ -export interface ISetSink<K=any> -{ +export interface ISetSink<K = any> { /** Adds the specified item to the set, if it was not in the set already. */ add(key: K): any; - /** Returns true if an element in the map object existed and has been + /** Returns true if an element in the map object existed and has been * removed, or false if the element did not exist. */ delete(key: K): boolean; /** Removes everything so that the set is empty. */ @@ -80,12 +79,11 @@ export interface ISetSink<K=any> } /** Write-only map interface (i.e. a drain into which key-value pairs can be "sunk") */ -export interface IMapSink<K=any, V=any> -{ - /** Returns true if an element in the map object existed and has been +export interface IMapSink<K = any, V = any> { + /** Returns true if an element in the map object existed and has been * removed, or false if the element did not exist. */ delete(key: K): boolean; - /** Sets the value for the key in the map object (the return value is + /** Sets the value for the key in the map object (the return value is * boolean in BTree but Map returns the Map itself.) */ set(key: K, value: V): any; /** Removes all key/value pairs from the IMap object. */ @@ -95,119 +93,154 @@ export interface IMapSink<K=any, V=any> /** Set interface. * @description Note: BTree<K,V> does not officially implement this interface, * but BTree<K> can be used as an instance of ISet<K>. */ -export interface ISet<K=any> extends ISetSource<K>, ISetSink<K> { } +export interface ISet<K = any> extends ISetSource<K>, ISetSink<K> {} /** An interface compatible with ES6 Map and BTree. This interface does not - * describe the complete interface of either class, but merely the common + * describe the complete interface of either class, but merely the common * interface shared by both. */ -export interface IMap<K=any, V=any> extends IMapSource<K, V>, IMapSink<K, V> { } +export interface IMap<K = any, V = any> + extends IMapSource<K, V>, + IMapSink<K, V> {} /** An data source that provides read-only access to a set of items called * "keys" in sorted order. This is a subinterface of ISortedMapSource. */ -export interface ISortedSetSource<K=any> extends ISetSource<K> -{ +export interface ISortedSetSource<K = any> extends ISetSource<K> { /** Gets the lowest key in the collection. */ minKey(): K | undefined; /** Gets the highest key in the collection. */ maxKey(): K | undefined; /** Returns the next key larger than the specified key (or undefined if there is none) */ - nextHigherKey(key: K): K|undefined; + nextHigherKey(key: K): K | undefined; /** Returns the next key smaller than the specified key (or undefined if there is none) */ - nextLowerKey(key: K): K|undefined; + nextLowerKey(key: K): K | undefined; /** Calls `callback` on the specified range of keys, in ascending order by key. * @param low The first key scanned will be greater than or equal to `low`. * @param high Scanning stops when a key larger than this is reached. - * @param includeHigh If the `high` key is present in the map, `onFound` is called + * @param includeHigh If the `high` key is present in the map, `onFound` is called * for that final pair if and only if this parameter is true. * @param onFound A function that is called for each key pair. Because this - * is a subinterface of ISortedMapSource, if there is a value + * is a subinterface of ISortedMapSource, if there is a value * associated with the key, it is passed as the second parameter. - * @param initialCounter Initial third argument of `onFound`. This value + * @param initialCounter Initial third argument of `onFound`. This value * increases by one each time `onFound` is called. Default: 0 * @returns Number of pairs found and the number of times `onFound` was called. */ - forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:any,counter:number) => void, initialCounter?: number): number; - /** Returns a new iterator for iterating the keys of each pair in ascending order. + forRange( + low: K, + high: K, + includeHigh: boolean, + onFound?: (k: K, v: any, counter: number) => void, + initialCounter?: number, + ): number; + /** Returns a new iterator for iterating the keys of each pair in ascending order. * @param firstKey: Minimum key to include in the output. */ keys(firstKey?: K): IterableIterator<K>; } /** An data source that provides read-only access to items in sorted order. */ -export interface ISortedMapSource<K=any, V=any> extends IMapSource<K, V>, ISortedSetSource<K> -{ +export interface ISortedMapSource<K = any, V = any> + extends IMapSource<K, V>, + ISortedSetSource<K> { /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */ - nextHigherPair(key: K): [K,V]|undefined; + nextHigherPair(key: K): [K, V] | undefined; /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */ - nextLowerPair(key: K): [K,V]|undefined; + nextLowerPair(key: K): [K, V] | undefined; /** Builds an array of pairs from the specified range of keys, sorted by key. * Each returned pair is also an array: pair[0] is the key, pair[1] is the value. * @param low The first key in the array will be greater than or equal to `low`. * @param high This method returns when a key larger than this is reached. * @param includeHigh If the `high` key is present in the map, its pair will be - * included in the output if and only if this parameter is true. Note: + * included in the output if and only if this parameter is true. Note: * if the `low` key is present, it is always included in the output. * @param maxLength Maximum length of the returned array (default: unlimited) * @description Computational complexity: O(result.length + log size) */ - getRange(low: K, high: K, includeHigh?: boolean, maxLength?: number): [K,V][]; + getRange( + low: K, + high: K, + includeHigh?: boolean, + maxLength?: number, + ): [K, V][]; /** Calls `callback` on the specified range of keys, in ascending order by key. * @param low The first key scanned will be greater than or equal to `low`. * @param high Scanning stops when a key larger than this is reached. - * @param includeHigh If the `high` key is present in the map, `onFound` is called + * @param includeHigh If the `high` key is present in the map, `onFound` is called * for that final pair if and only if this parameter is true. * @param onFound A function that is called for each key-value pair. - * @param initialCounter Initial third argument of onFound. This value + * @param initialCounter Initial third argument of onFound. This value * increases by one each time `onFound` is called. Default: 0 * @returns Number of pairs found and the number of times `callback` was called. */ - forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number; + forRange( + low: K, + high: K, + includeHigh: boolean, + onFound?: (k: K, v: V, counter: number) => void, + initialCounter?: number, + ): number; /** Returns an iterator that provides items in order by key. * @param firstKey: Minimum key to include in the output. */ - entries(firstKey?: K): IterableIterator<[K,V]>; - /** Returns a new iterator for iterating the keys of each pair in ascending order. + entries(firstKey?: K): IterableIterator<[K, V]>; + /** Returns a new iterator for iterating the keys of each pair in ascending order. * @param firstKey: Minimum key to include in the output. */ keys(firstKey?: K): IterableIterator<K>; - /** Returns a new iterator for iterating the values of each pair in order by key. + /** Returns a new iterator for iterating the values of each pair in order by key. * @param firstKey: Minimum key whose associated value is included in the output. */ values(firstKey?: K): IterableIterator<V>; - + // This method should logically be in IMapSource but is not supported by ES6 Map - /** Performs a reduce operation like the `reduce` method of `Array`. + /** 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<R>(callback: (previous:R,currentPair:[K,V],counter:number,tree:IMapF<K,V>) => R, initialValue: R): R; - /** Performs a reduce operation like the `reduce` method of `Array`. + reduce<R>( + callback: ( + previous: R, + currentPair: [K, V], + counter: number, + tree: IMapF<K, V>, + ) => R, + initialValue: R, + ): 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<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:IMapF<K,V>) => R): R|undefined; + reduce<R>( + callback: ( + previous: R | undefined, + currentPair: [K, V], + counter: number, + tree: IMapF<K, V>, + ) => R, + ): R | undefined; } /** An interface for a set of keys (the combination of ISortedSetSource<K> and ISetSink<K>) */ -export interface ISortedSet<K=any> extends ISortedSetSource<K>, ISetSink<K> { } +export interface ISortedSet<K = any> extends ISortedSetSource<K>, ISetSink<K> {} -/** An interface for a sorted map (dictionary), +/** An interface for a sorted map (dictionary), * not including functional/persistent methods. */ -export interface ISortedMap<K=any, V=any> extends IMap<K,V>, ISortedMapSource<K, V> -{ +export interface ISortedMap<K = any, V = any> + extends IMap<K, V>, + ISortedMapSource<K, V> { // All of the following methods should be in IMap but are left out of IMap // so that IMap is compatible with ES6 Map. /** Adds or overwrites a key-value pair in the sorted map. * @param key the key is used to determine the sort order of data in the tree. * @param value data to associate with the key - * @param overwrite Whether to overwrite an existing key-value pair + * @param overwrite Whether to overwrite an existing key-value pair * (default: true). If this is false and there is an existing * key-value pair then the call to this method has no effect. - * @returns true if a new key-value pair was added, false if the key + * @returns true if a new key-value pair was added, false if the key * already existed. */ set(key: K, value: V, overwrite?: boolean): boolean; /** Adds all pairs from a list of key-value pairs. - * @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]] + * @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.) * @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. */ - setPairs(pairs: [K,V][], overwrite?: boolean): number; + setPairs(pairs: [K, V][], overwrite?: boolean): number; /** Deletes a series of keys from the collection. */ deleteKeys(keys: K[]): number; /** Removes a range of key-value pairs from the B+ tree. @@ -218,18 +251,18 @@ export interface ISortedMap<K=any, V=any> extends IMap<K,V>, ISortedMapSource<K, deleteRange(low: K, high: K, includeHigh: boolean): number; // TypeScript requires these methods of ISortedMapSource to be repeated - entries(firstKey?: K): IterableIterator<[K,V]>; + entries(firstKey?: K): IterableIterator<[K, V]>; keys(firstKey?: K): IterableIterator<K>; values(firstKey?: K): IterableIterator<V>; } -/** An interface for a functional set, in which the set object could be read-only - * but new versions of the set can be created by calling "with" or "without" +/** An interface for a functional set, in which the set object could be read-only + * but new versions of the set can be created by calling "with" or "without" * methods to add or remove keys. This is a subinterface of IMapF<K,V>, * so the items in the set may be referred to as "keys". */ -export interface ISetF<K=any> extends ISetSource<K> { - /** Returns a copy of the set with the specified key included. - * @description You might wonder why this method accepts only one key +export interface ISetF<K = any> extends ISetSource<K> { + /** Returns a copy of the set with the specified key included. + * @description You might wonder why this method accepts only one key * instead of `...keys: K[]`. The reason is that the derived interface * IMapF expects the second parameter to be a value. Therefore * withKeys() is provided to set multiple keys at once. */ @@ -239,91 +272,133 @@ export interface ISetF<K=any> extends ISetSource<K> { /** Returns a copy of the tree with all the keys in the specified array present. * @param keys The keys to add. * @param returnThisIfUnchanged If true, the method returns `this` when - * all of the keys are already present in the collection. The + * all of the keys are already present in the collection. The * default value may be true or false depending on the concrete * implementation of the interface (in BTree, the default is false.) */ withKeys(keys: K[], returnThisIfUnchanged?: boolean): ISetF<K>; /** Returns a copy of the tree with all the keys in the specified array removed. */ withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISetF<K>; - /** Returns a copy of the tree with items removed whenever the callback + /** Returns a copy of the tree with items removed whenever the callback * function returns false. * @param callback A function to call for each item in the set. * The second parameter to `callback` exists because ISetF * is a subinterface of IMapF. If the object is a map, v * is the value associated with the key, otherwise v could be * undefined or another copy of the third parameter (counter). */ - filter(callback: (k:K,v:any,counter:number) => boolean, returnThisIfUnchanged?: boolean): ISetF<K>; + filter( + callback: (k: K, v: any, counter: number) => boolean, + returnThisIfUnchanged?: boolean, + ): ISetF<K>; } /** An interface for a functional map, in which the map object could be read-only - * but new versions of the map can be created by calling "with" or "without" - * methods to add or remove keys or key-value pairs. + * but new versions of the map can be created by calling "with" or "without" + * methods to add or remove keys or key-value pairs. */ -export interface IMapF<K=any, V=any> extends IMapSource<K, V>, ISetF<K> { +export interface IMapF<K = any, V = any> extends IMapSource<K, V>, ISetF<K> { /** Returns a copy of the tree with the specified key set (the value is undefined). */ - with(key: K): IMapF<K,V|undefined>; + with(key: K): IMapF<K, V | undefined>; /** Returns a copy of the tree with the specified key-value pair set. */ - with<V2>(key: K, value: V2, overwrite?: boolean): IMapF<K,V|V2>; + with<V2>(key: K, value: V2, overwrite?: boolean): IMapF<K, V | V2>; /** Returns a copy of the tree with the specified key-value pairs set. */ - withPairs<V2>(pairs: [K,V|V2][], overwrite: boolean): IMapF<K,V|V2>; + withPairs<V2>(pairs: [K, V | V2][], overwrite: boolean): IMapF<K, V | V2>; /** Returns a copy of the tree with all the keys in the specified array 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. + * neither the existing key nor the existing value is modified. * @param returnThisIfUnchanged If true, the method returns `this` when - * all of the keys are already present in the collection. The + * all of the keys are already present in the collection. The * default value may be true or false depending on the concrete * implementation of the interface (in BTree, the default is false.) */ - withKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF<K,V|undefined>; + withKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF<K, V | undefined>; /** Returns a copy of the tree with all values altered by a callback function. */ - mapValues<R>(callback: (v:V,k:K,counter:number) => R): IMapF<K,R>; - /** Performs a reduce operation like the `reduce` method of `Array`. + mapValues<R>(callback: (v: V, k: K, counter: number) => R): IMapF<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<R>(callback: (previous:R,currentPair:[K,V],counter:number,tree:IMapF<K,V>) => R, initialValue: R): R; - /** Performs a reduce operation like the `reduce` method of `Array`. + reduce<R>( + callback: ( + previous: R, + currentPair: [K, V], + counter: number, + tree: IMapF<K, V>, + ) => R, + initialValue: R, + ): 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<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:IMapF<K,V>) => R): R|undefined; + reduce<R>( + callback: ( + previous: R | undefined, + currentPair: [K, V], + counter: number, + tree: IMapF<K, V>, + ) => R, + ): R | undefined; // Update return types in ISetF - without(key: K): IMapF<K,V>; - withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF<K,V>; - /** Returns a copy of the tree with pairs removed whenever the callback + without(key: K): IMapF<K, V>; + withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF<K, V>; + /** Returns a copy of the tree with pairs removed whenever the callback * function returns false. */ - filter(callback: (k:K,v:V,counter:number) => boolean, returnThisIfUnchanged?: boolean): IMapF<K,V>; + filter( + callback: (k: K, v: V, counter: number) => boolean, + returnThisIfUnchanged?: boolean, + ): IMapF<K, V>; } -/** An interface for a functional sorted set: a functional set in which the +/** An interface for a functional sorted set: a functional set in which the * keys (items) are sorted. This is a subinterface of ISortedMapF. */ -export interface ISortedSetF<K=any> extends ISetF<K>, ISortedSetSource<K> -{ +export interface ISortedSetF<K = any> extends ISetF<K>, ISortedSetSource<K> { // TypeScript requires this method of ISortedSetSource to be repeated keys(firstKey?: K): IterableIterator<K>; } -export interface ISortedMapF<K=any,V=any> extends ISortedSetF<K>, IMapF<K,V>, ISortedMapSource<K,V> -{ +export interface ISortedMapF<K = any, V = any> + extends ISortedSetF<K>, + IMapF<K, V>, + ISortedMapSource<K, V> { /** Returns a copy of the tree with the specified range of keys removed. */ - withoutRange(low: K, high: K, includeHigh: boolean, returnThisIfUnchanged?: boolean): ISortedMapF<K,V>; + withoutRange( + low: K, + high: K, + includeHigh: boolean, + returnThisIfUnchanged?: boolean, + ): ISortedMapF<K, V>; // TypeScript requires these methods of ISortedSetF and ISortedMapSource to be repeated - entries(firstKey?: K): IterableIterator<[K,V]>; + entries(firstKey?: K): IterableIterator<[K, V]>; keys(firstKey?: K): IterableIterator<K>; values(firstKey?: K): IterableIterator<V>; - forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number; + forRange( + low: K, + high: K, + includeHigh: boolean, + onFound?: (k: K, v: V, counter: number) => void, + initialCounter?: number, + ): number; // Update the return value of methods from base interfaces - with(key: K): ISortedMapF<K,V|undefined>; - with<V2>(key: K, value: V2, overwrite?: boolean): ISortedMapF<K,V|V2>; - withKeys(keys: K[], returnThisIfUnchanged?: boolean): ISortedMapF<K,V|undefined>; - withPairs<V2>(pairs: [K,V|V2][], overwrite: boolean): ISortedMapF<K,V|V2>; - mapValues<R>(callback: (v:V,k:K,counter:number) => R): ISortedMapF<K,R>; - without(key: K): ISortedMapF<K,V>; - withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISortedMapF<K,V>; - filter(callback: (k:K,v:any,counter:number) => boolean, returnThisIfUnchanged?: boolean): ISortedMapF<K,V>; + with(key: K): ISortedMapF<K, V | undefined>; + with<V2>(key: K, value: V2, overwrite?: boolean): ISortedMapF<K, V | V2>; + withKeys( + keys: K[], + returnThisIfUnchanged?: boolean, + ): ISortedMapF<K, V | undefined>; + withPairs<V2>( + pairs: [K, V | V2][], + overwrite: boolean, + ): ISortedMapF<K, V | V2>; + mapValues<R>(callback: (v: V, k: K, counter: number) => R): ISortedMapF<K, R>; + without(key: K): ISortedMapF<K, V>; + withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISortedMapF<K, V>; + filter( + callback: (k: K, v: any, counter: number) => boolean, + returnThisIfUnchanged?: boolean, + ): ISortedMapF<K, V>; } -export interface ISortedMapConstructor<K,V> { - new (entries?: [K,V][], compare?: (a: K, b: K) => number): ISortedMap<K,V>; +export interface ISortedMapConstructor<K, V> { + new (entries?: [K, V][], compare?: (a: K, b: K) => number): ISortedMap<K, V>; +} +export interface ISortedMapFConstructor<K, V> { + new (entries?: [K, V][], compare?: (a: K, b: K) => number): ISortedMapF<K, V>; } -export interface ISortedMapFConstructor<K,V> { - new (entries?: [K,V][], compare?: (a: K, b: K) => number): ISortedMapF<K,V>; -}
\ No newline at end of file |