path: root/packages/idb-bridge/src/tree/interfaces.ts

/*
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>;
}