How I build My Own Data structure for Indexing : Bidirectional Map

Recently, in my organization, we came across a need to build an index of files we are using for our in-browser filesystem, where we have the id's of the file/folder which is how frontend understands and a path associated with it in the in-browser file system.

Brainstorming

After a couple of ideas, I thought of creating a map with all the ids mapped to their current path, which was a good idea. But after thinking it harder I found that the update path ( which is basically update Name) would be harder and can't be achieved easily by using one map only, as if we update a folder we need to update all the child component's path also. To do so I also needed a reference to all the paths and a way to easily access them.

Bidirectional Map

I thought of building a bidirectional Map where one map's key are id and the other map's key is the path. Well, this was a very good solution and optimal in my case. Below is a mental picture of it.

API for bidirectional Map

After building a basic mental idea about this, I needed to build APIs for this datastructure which can be used and can be easily extended. I was pretty sure we would need operations like add(), get() , update(), delete() . But apart from these, we can also have, getall() other operations depending upon the need.

below is the code of how the finished structure looks in Typescript.

/**
 * @template K - The type of keys.
 * @template V - The type of values.
 *
 * @class
 * @classdesc A simple bidirectional map for mapping between keys and values.
 *   Provides methods to add mappings and retrieve values by key or value.
 *
 * @example
 * // Example usage:
 * const bidirectionalMap = new BidirectionalMap<string, number>();
 * bidirectionalMap.addMapping('apple', 1);
 * bidirectionalMap.addMapping('orange', 2);
 *
 * // Using key to get value
 * console.log(bidirectionalMap.getValue('apple')); // Output: 1
 *
 * // Using value to get key
 * console.log(bidirectionalMap.getValue(2)); // Output: orange
 */
class BidirectionalMap<K, V> {
  /**
   * @private
   * @type {Map<K, V>} - The forward mapping from keys to values.
   */
  private forwardMap: Map<K, V>;

  /**
   * @private
   * @type {Map<V, K>} - The reverse mapping from values to keys.
   */
  private reverseMap: Map<V, K>;

  /**
   * Creates a new instance of BidirectionalMap.
   * @constructor
   */
  constructor() {
    this.forwardMap = new Map<K, V>(); // used to map key ===> path
    this.reverseMap = new Map<V, K>(); // used to map path ====> key
  }

  /**
   * Adds a bidirectional mapping between a key and a value.
   *
   * @param {K} key - The key to be mapped.
   * @param {V} value - The value to be mapped.
   * @returns {void}
   * @memberof BidirectionalMap
   */
  addMapping(key: K, value: V): void {
    this.forwardMap.set(key, value);
    this.reverseMap.set(value, key);
  }

  /**
   * Retrieves the value associated with the provided key or value.
   *
   * @param {K | V} keyOrValue - The key or value for which to retrieve the associated value or key.
   * @returns {V | K | undefined} The associated value or key, or undefined if not found.
   * @memberof BidirectionalMap
   */
  getValue(keyOrValue: K | V): V | K | undefined {
    if (this.forwardMap.has(keyOrValue as K)) {
      return this.forwardMap.get(keyOrValue as K);
    } else if (this.reverseMap.has(keyOrValue as V)) {
      return this.reverseMap.get(keyOrValue as V);
    } else {
      return undefined;
    }
  }

  getAllKeysFromForwardMap() {
    return this.forwardMap.keys();
  }

  getAllKeysFromReverseMap() {
    return this.reverseMap.keys();
  }

  getAllValuesFromForwardMap() {
    return this.forwardMap.values();
  }

  getAllValuesFromReverseMap() {
    return this.reverseMap.values();
  }

  getValueFromForwardMap(key: K) {
    return this.forwardMap.get(key);
  }

  getValueFromReverseMap(key: V) {
    return this.reverseMap.get(key);
  }

  // TODO: This should update the the values in the both things

  updateValue(key: K, value: V) {
    // Update the value of key in forward Map and backward Map
    this.addMapping(key, value);
  }

  getMapping() {
    return {
      forwardMap: this.forwardMap,
      backwardMap: this.reverseMap,
    };
  }
}

the only thing that is missing is the delete() method, which you guys can create on your own.

Once this is gone the usage of this looks something like below.

Example Usage:

 @example
 // Example usage:
  const bidirectionalMap = new BidirectionalMap<string, number>();
  bidirectionalMap.addMapping('apple', 1);
  bidirectionalMap.addMapping('orange', 2);

  // Using key to get value
 console.log(bidirectionalMap.getValue('apple')); // Output: 1

 // Using value to get key
 console.log(bidirectionalMap.getValue(2)); // Output: orange

Thank you for reading so far. If you learned something new and liked the article please follow me and subscribe to my email newsletter.

Did you find this article valuable?

Support Ashish maurya by becoming a sponsor. Any amount is appreciated!