1

Data Structures: Bidirectional Map

 2 years ago
source link: https://dev.to/pretaporter/data-structures-bidirectional-map-3f73
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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();
  }
}
Enter fullscreen modeExit fullscreen mode

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.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK