Data Structures: Bidirectional Map

In computer science, a bidirectional map is an associative data structure in which the (key,value) pairs form a one-to-one correspondence. Also known as bijective map. Article on Wikipedia.

It is not widely used data structure in web development, but in some cases really quite useful, for instance in encryption.

Let's describe our goal. Implement data structure, where following operations are performed in constant time:

Get value by key
Get key by value
Remove record by key
Remove record by value
Check for the existence of key
Check for the existence of value
Get the size of the map

Implementation below:

class BidirectionalMap<Key, Value> {
  private readonly map: Map<Key, Value>;
  private readonly inverseMap: Map<Value, Key>;

  constructor() {
    this.map = new Map();
    this.inverseMap = new Map();
  }

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

  deleteKey(key: Key): boolean {
    if (!this.hasKey(key)) {
      return false;
    }

    const value = this.getValue(key)!;
    this.inverseMap.delete(value);
    return this.map.delete(key);
  }

  deleteValue(value: Value): boolean {
    if (!this.hasValue(value)) {
      return false;
    }

    const key = this.getKey(value)!;
    this.map.delete(key); 
    return this.inverseMap.delete(value);
  }

  entries(): IterableIterator<[Key, Value]> {
    return this.map.entries();
  }

  getKey(value: Value): Key | undefined {
    return this.inverseMap.get(value);
  }

  getValue(key: Key): Value | undefined {
    return this.map.get(key);
  }

  hasKey(key: Key): boolean {
    return this.map.has(key);
  }

  hasValue(value: Value): boolean {
    return this.inverseMap.has(value);
  }

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

  keys(): IterableIterator<Key> {
    return this.map.keys();
  }

  set(key: Key, value: Value): void {
    if (this.hasKey(key) || this.hasValue(value)) {
      throw new Error('Key or Value already exists');
    }

    this.map.set(key, value);
    this.inverseMap.set(value, key);
  }

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

  values(): IterableIterator<Value> {
    return this.inverseMap.keys();
  }
}

Basically we can consider this data structure as extending of Map class. Current implementation could be improved by adding forEach method and iterable protocol, which will allow to define iteration behavior of Bidirectional Map. Let me know in comments if your interesting to know, how to do it exactly.

Blog

Data Structures: Bidirectional Map

Maksim

Join Our Newsletter. No Spam, Only the good stuff.

Related