diff options
Diffstat (limited to 'packages/idb-bridge/src/tree/interfaces.ts')
-rw-r--r-- | packages/idb-bridge/src/tree/interfaces.ts | 329 |
1 files changed, 329 insertions, 0 deletions
diff --git a/packages/idb-bridge/src/tree/interfaces.ts b/packages/idb-bridge/src/tree/interfaces.ts new file mode 100644 index 000000000..c708c20b5 --- /dev/null +++ b/packages/idb-bridge/src/tree/interfaces.ts @@ -0,0 +1,329 @@ +/* +Copyright (c) 2018 David Piepgrass + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. + +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 + * interface and does not allow duplicates. */ +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. */ + has(key: K): boolean; + /** Returns a new iterator for iterating the items in the set (the order is implementation-dependent). */ + keys(): IterableIterator<K>; +} + +/** Read-only map interface (i.e. a source of key-value pairs). */ +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; + /** 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; + + /** Returns an iterator that provides all key-value pairs from the collection (as arrays of length 2). */ + 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. */ + values(): IterableIterator<V>; + // TypeScript compiler decided Symbol.iterator has type 'any' + //[Symbol.iterator](): IterableIterator<[K,V]>; +} + +/** 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> +{ + /** 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 + * removed, or false if the element did not exist. */ + delete(key: K): boolean; + /** Removes everything so that the set is empty. */ + clear(): void; +} + +/** 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 + * 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 + * boolean in BTree but Map returns the Map itself.) */ + set(key: K, value: V): any; + /** Removes all key/value pairs from the IMap object. */ + clear(): void; +} + +/** 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> { } + +/** An interface compatible with ES6 Map and BTree. This interface does not + * 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> { } + +/** 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> +{ + /** 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; + /** Returns the next key smaller than the specified key (or undefined if there is none) */ + 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 + * 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 + * associated with the key, it is passed as the second parameter. + * @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. + * @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> +{ + /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */ + nextHigherPair(key: K): [K,V]|undefined; + /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */ + 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: + * 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][]; + /** 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 + * 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 + * 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; + /** 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. + * @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. + * @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`. + * 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`. + * 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; +} + +/** 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> { } + +/** 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> +{ + // 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 + * (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 + * 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]] + * 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; + /** Deletes a series of keys from the collection. */ + deleteKeys(keys: K[]): number; + /** Removes a range of key-value pairs from the B+ tree. + * @param low The first key deleted will be greater than or equal to `low`. + * @param high Deleting stops when a key larger than this is reached. + * @param includeHigh Specifies whether the `high` key, if present, is deleted. + * @returns The number of key-value pairs that were deleted. */ + deleteRange(low: K, high: K, includeHigh: boolean): number; + + // TypeScript requires these methods of ISortedMapSource to be repeated + 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" + * 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 + * 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. */ + with(key: K): ISetF<K>; + /** Returns a copy of the set with the specified key removed. */ + without(key: K): ISetF<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 + * 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 + * 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>; +} + +/** 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. + */ +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>; + /** 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>; + /** 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>; + /** 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. + * @param returnThisIfUnchanged If true, the method returns `this` when + * 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>; + /** 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`. + * 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`. + * 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; + + // 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 + * function returns false. */ + 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 + * keys (items) are sorted. This is a subinterface of ISortedMapF. */ +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> +{ + /** 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>; + + // TypeScript requires these methods of ISortedSetF and ISortedMapSource to be repeated + 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; + + // 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>; +} + +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>; +}
\ No newline at end of file |