// B+ tree by David Piepgrass. License: MIT

/** 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>;
  without(key: K): ISortedSetF<K>;
  with(key: K): ISortedSetF<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>;
}