Hashmap.ts

export interface HashImpl<T> {
  hash?(value: T): unknown;
  equals(a: T, b: T): boolean;
}

export class AssociationList<K, V> implements Map<K, V> {
  private inner: {readonly key: K; value: V}[] = [];

  constructor(
    private readonly impl: HashImpl<K>,
    entries: Iterable<[K, V]> = [],
  ) {
    for (const [k, v] of entries) {
      this.set(k, v);
    }
  }

  get [Symbol.toStringTag]() {
    return "AssociationList";
  }

  get size(): number {
    return this.inner.length;
  }

  [Symbol.iterator](): IterableIterator<[K, V]> {
    return this.entries();
  }

  clear(): void {
    this.inner = [];
  }

  delete(key: K): boolean {
    for (let i = 0; i < this.inner.length; i++) {
      const obj = this.inner[i];
      if (this.impl.equals(obj.key, key)) {
        this.inner.splice(i, 1);
        return true;
      }
    }
    return false;
  }

  *entries(): IterableIterator<[K, V]> {
    for (const obj of this.inner) {
      yield [obj.key, obj.value];
    }
  }

  forEach(
    callbackfn: (value: V, key: K, map: Map<K, V>) => void,
    thisArg?: any,
  ): void {
    for (const obj of this.inner) {
      callbackfn.call(thisArg, obj.value, obj.key, this);
    }
  }

  get(key: K): V | undefined {
    for (const obj of this.inner) {
      if (this.impl.equals(obj.key, key)) {
        return obj.value;
      }
    }
    return undefined;
  }

  has(key: K): boolean {
    for (const obj of this.inner) {
      if (this.impl.equals(obj.key, key)) {
        return true;
      }
    }
    return false;
  }

  *keys(): IterableIterator<K> {
    for (const obj of this.inner) {
      yield obj.key;
    }
  }

  set(key: K, value: V): this {
    for (const obj of this.inner) {
      if (this.impl.equals(obj.key, key)) {
        obj.value = value;
        return this;
      }
    }
    this.inner.push({key, value});
    return this;
  }

  *values(): IterableIterator<V> {
    for (const obj of this.inner) {
      yield obj.value;
    }
  }
}

export class HashMap<K, V> implements Map<K, V> {
  private readonly lists = new Map<unknown, AssociationList<K, V>>();

  constructor(
    private readonly impl: HashImpl<K>,
    entries: Iterable<[K, V]> = [],
  ) {
    for (const [k, v] of entries) {
      this.set(k, v);
    }
  }

  get [Symbol.toStringTag]() {
    return "HashMap";
  }

  get size() {
    let ret = 0;
    for (const lists of this.lists.values()) {
      ret += lists.size;
    }
    return ret;
  }

  *[Symbol.iterator](): IterableIterator<[K, V]> {
    for (const list of this.lists.values()) {
      yield* list;
    }
  }

  clear(): void {
    this.lists.clear();
  }

  delete(key: K): boolean {
    const list = this.lists.get(this.impl.hash?.(key));
    return list ? list.delete(key) : false;
  }

  entries(): IterableIterator<[K, V]> {
    return this[Symbol.iterator]();
  }

  forEach(
    callbackfn: (value: V, key: K, map: Map<K, V>) => void,
    thisArg?: any,
  ): void {
    for (const list of this.lists.values()) {
      for (const [key, value] of list) {
        callbackfn.call(thisArg, value, key, this);
      }
    }
  }

  get(key: K): V | undefined {
    const list = this.lists.get(this.impl.hash?.(key));
    return list ? list.get(key) : undefined;
  }

  has(key: K): boolean {
    const list = this.lists.get(this.impl.hash?.(key));
    return list ? list.has(key) : false;
  }

  *keys(): IterableIterator<K> {
    for (const list of this.lists.values()) {
      yield* list.keys();
    }
  }

  set(key: K, value: V): this {
    const hash = this.impl.hash?.(key);
    let list = this.lists.get(hash);
    if (!list) {
      list = new AssociationList(this.impl);
      this.lists.set(hash, list);
    }
    list.set(key, value);
    return this;
  }

  *values(): IterableIterator<V> {
    for (const list of this.lists.values()) {
      yield* list.values();
    }
  }
}

export class MultiMap<K, V> implements Map<K, V> {
  private readonly map: Map<K, V[]>;

  constructor(
    makeMap: <T>() => Map<K, T> = <T>() => new Map(),
    entries: Iterable<[K, V]> = [],
  ) {
    this.map = makeMap();
    for (const [k, v] of entries) {
      this.set(k, v);
    }
  }

  set(key: K, value: V): this {
    this.map.set(key, [value]);
    return this;
  }

  add(key: K, value: V): this {
    let list = this.map.get(key);
    if (!list) {
      list = [];
      this.map.set(key, list);
    }
    list.push(value);
    return this;
  }

  get size() {
    let ret = 0;
    for (const v of this.map.values()) {
      ret += v.length;
    }
    return ret;
  }

  readonly [Symbol.toStringTag]: string;

  [Symbol.iterator](): IterableIterator<[K, V]> {
    return this.entries();
  }

  clear(): void {
    this.map.clear();
  }

  delete(key: K): boolean {
    const list = this.map.get(key);
    if (list) {
      this.map.delete(key);
      if (list.length > 0) {
        return true;
      }
    }
    return false;
  }

  *entries(): IterableIterator<[K, V]> {
    for (const [k, list] of this.map) {
      for (const value of list) {
        yield [k, value];
      }
    }
  }

  forEach(
    callbackfn: (value: V, key: K, map: Map<K, V>) => void,
    thisArg?: any,
  ): void {
    for (const [key, list] of this.map) {
      for (const value of list) {
        callbackfn.call(thisArg, value, key, this);
      }
    }
  }

  get(key: K): V | undefined {
    const list = this.map.get(key);
    return list && list.length > 0 ? list[0] : undefined;
  }

  getAll(key: K): V[] {
    return this.map.get(key) || [];
  }

  has(key: K): boolean {
    const list = this.map.get(key);
    return list ? list.length > 0 : false;
  }

  *keys(): IterableIterator<K> {
    for (const [key, list] of this.map) {
      if (list.length > 0) {
        yield key;
      }
    }
  }

  *values(): IterableIterator<V> {
    for (const list of this.map.values()) {
      yield* list;
    }
  }
}