idb wip

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