A multimap that preserves the insertion order of its keys and values

order-preserving-multimap.ts

class Multimap<K, V> {
  #buckets = new Map<K, Map<V, readonly [K, V]>>();
  #order = new Set<readonly [K, V]>();
  constructor(from?: Iterable<readonly [K, V]> | null) {
    if(from != null) for(const { 0: key, 1: value } of from) {
      this.add(key, value);
    }
  }

  static fromHeaders<K, V>(headers: Iterable<{name: K, value: V}>) {
    const m = new this<K, V>();
    for(const { name, value } of headers) {
      m.add(name.toLowerCase(), value);
    }
    return m;
  }

  intoHeaders() {
    const headers: { name: K, value: V }[] = [];
    for(const { 0: key, 1: value } of this.#order) {
      headers.push({ name: key, value });
    }
    return headers;
  }

  get(key: K) {
    const bucket = this.#buckets.get(key);
    return bucket != null && [...bucket.keys()];
  }

  getFirst(key: K) {
    const bucket = this.#buckets.get(key);
    return bucket != null && bucket.keys().next().value;
  }

  add(key: K, value: V) {
    const bucket = this.#buckets.get(key);

    if(!bucket) {
      const tuple = [key, value] as const;
      this.#buckets.set(key, new Map([[value, tuple]]));
      this.#order.add(tuple);
    }
    else if(!bucket.has(value)) {
      const tuple = [key, value] as const;
      bucket.set(value, tuple);
      this.#order.add(tuple);
    }
  }

  set(key: K, values: Iterable<V>) {
		const bucket = this.#buckets.get(key);
		if (bucket) {
			const index = new Set(values);
			for(const v of bucket.keys()) {
				if(index.has(v)) continue;
				this.delete(key, v);
			}
			for(const v of index) {
				if(bucket.has(v)) continue;
				const tuple = [key, v] as const;
				bucket.set(v, tuple);
				this.#order.add(tuple);
			}
		}
		else {
			const bucket = new Map();
			this.#buckets.set(key, bucket);
			for(const v of values) {
				if(bucket.has(v)) continue;
				const tuple = [key, v] as const;
				bucket.set(v, tuple);
				this.#order.add(tuple);
			}
		}
	}

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

  delete(key: K, value: V) {
    const bucket = this.#buckets.get(key);
    if(!bucket) return false;

    const tuple = bucket.get(value);
    if(!tuple) return false;

    bucket.delete(value);
    if(bucket.size === 0) this.#buckets.delete(key);
    this.#order.delete(tuple);
    return true;
  }

  deleteKey(key: K) {
    const bucket = this.#buckets.get(key);
    if(!bucket) return false;

    // bucket is guaranteed to be non-empty
    for(const tuple of bucket.values()) {
      this.#order.delete(tuple);
    }

    this.#buckets.delete(key);
    return true;
  }

  has(key: K, value: V) {
    return this.#buckets.get(key)?.has(value);
  }

  hasKey(key: K) {
    return this.#buckets.has(key);
  }

  clear() {
    this.#order.clear();
    this.#buckets.clear();
  }

  get size() {
    return this.#order.size;
  }

  keys() {
    return this.#buckets.keys();
  }

  *values() {
    for (const { 1: value } of this.#order) {
      yield value;
    }
  }

  *entries() {
    for (const { 0: key, 1: value } of this.#order) {
      yield [key, value];
    }
  }

  [Symbol.iterator]() {
    return this.entries();
  }
}