Multimap

Multimap.spec.ts

import { SetMultimap } from "./Multimap"

describe(`SetMultimap`, () => {
  let multimap: SetMultimap<string, string>;

  beforeEach(() => {
    multimap = new SetMultimap<string, string>((a, b) => a === b);
  });

  describe(`put`, () => {
    test(`Adds value to the map`, async () => {
      multimap.put('key', 'value');

      expect(multimap.containsEntry('key', 'value')).toBe(true);
    });

    test(`A key can contain multiple values`, async () => {
      multimap.put('key', 'A');
      multimap.put('key', 'B');

      expect(multimap.containsEntry('key', 'A')).toBe(true);
      expect(multimap.containsEntry('key', 'B')).toBe(true);
    });

    test(`Value not in the map returns true`, async () => {
      const added = multimap.put('key', 'value');

      expect(added).toBe(true);
    });

    test(`Value already in the map returns false`, async () => {
      multimap.put('key', 'value');

      const added = multimap.put('key', 'value');

      expect(added).toBe(false);
    });
  });

  describe(`get`, () => {
    test(`Empty map returns empty array`, async () => {
      expect(multimap.get('key')).toStrictEqual([]);
    });

    test(`Returns every value added for that key`, async () => {
      multimap.put('key', 'A');
      multimap.put('key', 'B');

      expect(multimap.get('key')).toStrictEqual(['A', 'B']);
    });

    test(`No matching key in map returns empty array`, async () => {
      multimap.put('A', 'value');

      expect(multimap.get('B')).toStrictEqual([]);
    });
  });

  describe(`remove`, () => {
    test(`Removes value value the map`, async () => {
      multimap.put('key', 'value');

      multimap.remove('key', 'value');

      expect(multimap.containsEntry('key', 'value')).toBe(false);
    });

    test(`Value in the map returns true`, async () => {
      multimap.put('key', 'value');

      const removed = multimap.remove('key', 'value');

      expect(removed).toBe(true);
    });

    test(`Value not in the map returns false`, async () => {
      const removed = multimap.remove('key', 'value');

      expect(removed).toBe(false);
    });

    test(`Removing the only value for a key removes the key`, async () => {
      multimap.put('key', 'value');

      multimap.remove('key', 'value');

      expect(multimap.containsKey('key')).toBe(false);
    });
  });

  describe(`containsEntry`, () => {
    test(`Entry under given key returns true`, async () => {
      multimap.put('key', 'value');

      expect(multimap.containsEntry('key', 'value')).toBe(true);
    });

    test(`Entry under a different key returns false`, async () => {
      multimap.put('A', 'A');
      multimap.put('B', 'B');

      expect(multimap.containsEntry('A', 'B')).toBe(false);
    });

    test(`Uses given equality function to compare`, async () => {
      const objectMultimap = new SetMultimap<string, { id: string }>(
        (a, b) => a.id === b.id,
      );

      objectMultimap.put('key', { id: 'A' });

      expect(objectMultimap.containsEntry('key', { id: 'A' })).toBe(true);
    });
  });

  describe(`containsKey`, () => {
    test(`No key in map returns false`, async () => {
      expect(multimap.containsKey('key')).toBe(false);
    });

    test(`Key in map returns true`, async () => {
      multimap.put('key', 'value');

      expect(multimap.containsKey('key')).toBe(true);
    });

    test(`No matching key in map returns false`, async () => {
      multimap.put('A', 'value');

      expect(multimap.containsKey('B')).toBe(false);
    });
  });

  describe(`Contains value`, () => {
    test(`No value in map returns false`, async () => {
      expect(multimap.containsValue('value')).toBe(false);
    });

    test(`A matching value in map returns true`, async () => {
      multimap.put('key', 'value');

      expect(multimap.containsValue('value')).toBe(true);
    });

    test(`No matching value in map returns false`, async () => {
      multimap.put('key', 'A');

      expect(multimap.containsValue('B')).toBe(false);
    });

    test(`Uses given equality function for comparison`, async () => {
      const objectMultimap = new SetMultimap<string, { id: string }>(
        (a, b) => a.id === b.id,
      );

      objectMultimap.put('key', { id: 'A' });

      expect(objectMultimap.containsValue({ id: 'A' })).toBe(true);
    });
  });

  describe(`Clear`, () => {
    test(`No value in map does nothing`, async () => {
      multimap.clear();
    });

    test(`Removes every value in map`, async () => {
      multimap.put('A', 'A');
      multimap.put('B', 'B');

      multimap.clear();

      expect(multimap.isEmpty()).toBe(true);
    });
  });

  describe(`Size`, () => {
    test(`Empty map returns 0`, async () => {
      expect(multimap.size()).toBe(0);
    });

    test(`Count increases per key`, async () => {
      multimap.put('A', 'value');
      multimap.put('B', 'value');
      expect(multimap.size()).toBe(2);
    });

    test(`Returns the amount of keys (not values) in the map`, async () => {
      multimap.put('A', 'A');
      multimap.put('A', 'B');
      expect(multimap.size()).toBe(1);
    });
  });

  describe(`entriesSize`, () => {
    test(`Empty map returns 0`, async () => {
      expect(multimap.entriesSize()).toBe(0);
    });

    test(`Count increases per key`, async () => {
      multimap.put('A', 'A');
      multimap.put('A', 'B');
      expect(multimap.entriesSize()).toBe(2);
    });

    test(`Count increases per value`, async () => {
      multimap.put('A', 'value');
      multimap.put('B', 'value');
      expect(multimap.entriesSize()).toBe(2);
    });
  });

  describe(`isEmpty`, () => {
    test(`Empty map returns true`, async () => {
      expect(multimap.isEmpty()).toBe(true);
    });

    test(`A value in the map returns false`, async () => {
      multimap.put('key', 'value');

      expect(multimap.isEmpty()).toBe(false);
    });
  });
});

Multimap.ts

export interface Multimap<K, V> {
  /**
   * Returns a collection view of all values associated with a key.
   */
  get(key: K): V[];

  /**
   * Returns true if the multimap contains the specified key-value pair.
   */
  containsEntry(key: K, value: V): boolean;

  /**
   * Returns true if the multimap contains any values for the specified key.
   */
  containsKey(key: K): boolean;

  /**
   * Returns true if the multimap contains the specified value for any key.
   */
  containsValue(value: V): boolean;

  /**
   * Returns true if the multimap contains no key-value pairs.
   */
  isEmpty(): boolean;

  /**
   * Stores a key-value pair in the multimap.
   * Returns true if a new pair was added, false if the pair was already present.
   */
  put(key: K, value: V): boolean;

  /**
   * Removes a key-value pair from the multimap.
   * Returns true if the pair was removed, false if the pair did not exist.
   */
  remove(key: K, value: V): boolean;

  /**
   * Removes all key-value pairs from the multimap.
   */
  clear(): void;

  /**
   * Returns the number of key-value pairs in the multimap.
   */
  size(): number;

  /**
   * Returns the number of values in the multimap.
   */
  entriesSize(): number;
}

export class SetMultimap<K, V> implements Multimap<K, V> {
  private map: Map<K, Set<V>>;
  private readonly isEqual: (a: V, b: V) => boolean;

  constructor(isEqual: (a: V, b: V) => boolean) {
    this.isEqual = isEqual;
    this.map = new Map<K, Set<V>>();
  }

  get(key: K): V[] {
    const values = this.map.get(key);

    if (!values) return [];

    return Array.from(values);
  }

  put(key: K, value: V): boolean {
    if (!this.map.has(key)) {
      this.map.set(key, new Set<V>());
    }
    const values = this.map.get(key)!;
    if (values.has(value)) {
      return false; // Already present
    }
    values.add(value);
    return true; // New entry added
  }

  remove(key: K, value: V): boolean {
    const values = this.map.get(key);
    if (!values) {
      return false;
    }

    const removedSomething = values.delete(value);

    // Remove the set if there is no value left
    if (values.size === 0) this.map.delete(key);

    return removedSomething;
  }

  containsKey(key: K): boolean {
    return this.map.has(key);
  }

  containsEntry(key: K, value: V): boolean {
    const values = this.map.get(key);
    if (!values) return false;
    return Array.from(values).some((v) => this.isEqual(v, value));
  }

  containsValue(value: V): boolean {
    return Array.from(this.map.values()).some((set) =>
      Array.from(set).some((v) => this.isEqual(v, value)),
    );
  }

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

  size(): number {
    return this.map.size;
  }

  entriesSize(): number {
    return Array.from(this.map.values()).reduce(
      (count, set) => count + set.size,
      0,
    );
  }

  isEmpty(): boolean {
    return this.size() === 0;
  }
}