1042 Advanced

1042-bimap — Bidirectional Map

Functional Programming

Tutorial

The Problem

A bidirectional map (bimap) maintains a one-to-one correspondence between keys and values, enabling O(1) lookup in both directions: given a key, find the value; given a value, find the key. Use cases: ID to name lookups where you need reverse resolution, encoding/decoding tables, symbol tables in compilers.

The classic implementation uses two hash maps — one forward, one backward — and keeps them synchronized on insert and removal. Inserting a key that already exists must clean up both the old key-to-value and value-to-key entries.

🎯 Learning Outcomes

• Implement a bidirectional map with two synchronized HashMaps

• Handle the invariant that both key and value must be unique

• Provide O(1) forward and reverse lookup

• Ensure consistency on insert: remove stale entries in both directions

• Understand when bimap crate provides additional guarantees

Code Example

#![allow(clippy::all)]
// 1042: Bidirectional Map — Two HashMaps for Key↔Value
// Both key and value must be unique — inserting overwrites both directions

use std::collections::HashMap;
use std::hash::Hash;

/// Bidirectional map: key ↔ value, both unique
struct BiMap<K, V> {
    forward: HashMap<K, V>,
    backward: HashMap<V, K>,
}

impl<K, V> BiMap<K, V>
where
    K: Hash + Eq + Clone,
    V: Hash + Eq + Clone,
{
    fn new() -> Self {
        BiMap {
            forward: HashMap::new(),
            backward: HashMap::new(),
        }
    }

    fn insert(&mut self, key: K, value: V) {
        // Remove old mappings if key or value already exists
        if let Some(old_value) = self.forward.remove(&key) {
            self.backward.remove(&old_value);
        }
        if let Some(old_key) = self.backward.remove(&value) {
            self.forward.remove(&old_key);
        }

        self.backward.insert(value.clone(), key.clone());
        self.forward.insert(key, value);
    }

    fn get_by_key(&self, key: &K) -> Option<&V> {
        self.forward.get(key)
    }

    fn get_by_value(&self, value: &V) -> Option<&K> {
        self.backward.get(value)
    }

    fn remove_by_key(&mut self, key: &K) -> Option<V> {
        if let Some(value) = self.forward.remove(key) {
            self.backward.remove(&value);
            Some(value)
        } else {
            None
        }
    }

    fn remove_by_value(&mut self, value: &V) -> Option<K> {
        if let Some(key) = self.backward.remove(value) {
            self.forward.remove(&key);
            Some(key)
        } else {
            None
        }
    }

    fn len(&self) -> usize {
        self.forward.len()
    }

    fn contains_key(&self, key: &K) -> bool {
        self.forward.contains_key(key)
    }

    fn contains_value(&self, value: &V) -> bool {
        self.backward.contains_key(value)
    }
}

fn basic_ops() {
    let mut bm = BiMap::new();
    bm.insert("one", 1);
    bm.insert("two", 2);
    bm.insert("three", 3);

    assert_eq!(bm.get_by_key(&"two"), Some(&2));
    assert_eq!(bm.get_by_value(&2), Some(&"two"));
    assert_eq!(bm.get_by_key(&"four"), None);
    assert_eq!(bm.len(), 3);
}

fn overwrite_test() {
    let mut bm = BiMap::new();
    bm.insert("a", 1);
    bm.insert("b", 2);
    bm.insert("a", 3); // overwrites "a"->1, removes 1->"a"

    assert_eq!(bm.get_by_key(&"a"), Some(&3));
    assert_eq!(bm.get_by_value(&1), None); // old mapping gone
    assert_eq!(bm.get_by_value(&3), Some(&"a"));
}

fn codec_test() {
    let mut bm = BiMap::new();
    bm.insert("red", 0xFF0000u32);
    bm.insert("green", 0x00FF00);
    bm.insert("blue", 0x0000FF);

    assert_eq!(bm.get_by_key(&"red"), Some(&0xFF0000));
    assert_eq!(bm.get_by_value(&0x00FF00), Some(&"green"));

    bm.remove_by_key(&"red");
    assert_eq!(bm.get_by_key(&"red"), None);
    assert_eq!(bm.get_by_value(&0xFF0000u32), None);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_ops();
    }

    #[test]
    fn test_overwrite() {
        overwrite_test();
    }

    #[test]
    fn test_codec() {
        codec_test();
    }

    #[test]
    fn test_remove_by_value() {
        let mut bm = BiMap::new();
        bm.insert("x", 10);
        bm.insert("y", 20);
        assert_eq!(bm.remove_by_value(&10), Some("x"));
        assert!(!bm.contains_key(&"x"));
        assert!(!bm.contains_value(&10));
    }
}

(* 1042: Bidirectional Map — Two Maps for Key↔Value *)
(* Both directions must be unique for bimap to work *)

module StringMap = Map.Make(String)
module IntMap = Map.Make(Int)

type bimap = {
  forward: int StringMap.t;     (* string -> int *)
  backward: string IntMap.t;    (* int -> string *)
}

let empty = { forward = StringMap.empty; backward = IntMap.empty }

let insert key value bm =
  (* Remove old mappings if either key or value already exists *)
  let bm = match StringMap.find_opt key bm.forward with
    | Some old_val -> { bm with backward = IntMap.remove old_val bm.backward }
    | None -> bm
  in
  let bm = match IntMap.find_opt value bm.backward with
    | Some old_key -> { bm with forward = StringMap.remove old_key bm.forward }
    | None -> bm
  in
  { forward = StringMap.add key value bm.forward;
    backward = IntMap.add value key bm.backward }

let get_by_key key bm = StringMap.find_opt key bm.forward
let get_by_value value bm = IntMap.find_opt value bm.backward

let remove_by_key key bm =
  match StringMap.find_opt key bm.forward with
  | None -> bm
  | Some value ->
    { forward = StringMap.remove key bm.forward;
      backward = IntMap.remove value bm.backward }

let size bm = StringMap.cardinal bm.forward

(* Approach 1: Basic bidirectional lookup *)
let basic_ops () =
  let bm = empty
    |> insert "one" 1
    |> insert "two" 2
    |> insert "three" 3
  in
  assert (get_by_key "two" bm = Some 2);
  assert (get_by_value 2 bm = Some "two");
  assert (get_by_key "four" bm = None);
  assert (size bm = 3)

(* Approach 2: Overwrite handling *)
let overwrite_test () =
  let bm = empty
    |> insert "a" 1
    |> insert "b" 2
    |> insert "a" 3  (* overwrites "a"->1, removes 1->"a" *)
  in
  assert (get_by_key "a" bm = Some 3);
  assert (get_by_value 1 bm = None);  (* old mapping gone *)
  assert (get_by_value 3 bm = Some "a")

(* Approach 3: Encoding/decoding table *)
let codec_test () =
  let bm = empty
    |> insert "red" 0xFF0000
    |> insert "green" 0x00FF00
    |> insert "blue" 0x0000FF
  in
  assert (get_by_key "red" bm = Some 0xFF0000);
  assert (get_by_value 0x00FF00 bm = Some "green");
  let bm = remove_by_key "red" bm in
  assert (get_by_key "red" bm = None);
  assert (get_by_value 0xFF0000 bm = None)

let () =
  basic_ops ();
  overwrite_test ();
  codec_test ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Invariant maintenance: Rust's insert must manually clean up stale entries in both directions; OCaml's persistent approach naturally handles this by rebuilding both maps.

Uniqueness enforcement: Both implementations silently overwrite conflicting entries; a strict variant would return Err on conflicts.

Library support: The bimap crate provides a production-ready Rust implementation; OCaml's Base.Bimap is the equivalent.

Clone bounds: Rust's BiMap requires K: Clone + Hash + Eq and V: Clone + Hash + Eq because both maps need copies of keys and values; OCaml's GC makes sharing free.

OCaml Approach

OCaml's persistent map requires coordination between two maps:

module StringMap = Map.Make(String)
module IntMap = Map.Make(Int)

type ('k, 'v) bimap = {
  forward: 'v StringMap.t;
  backward: 'k IntMap.t;
}

Persistent maps make the two-map approach natural — both maps are updated together when building a new bimap version. OCaml's Base.Bimap module provides this in the standard Base library.

Full Source

#![allow(clippy::all)]
// 1042: Bidirectional Map — Two HashMaps for Key↔Value
// Both key and value must be unique — inserting overwrites both directions

use std::collections::HashMap;
use std::hash::Hash;

/// Bidirectional map: key ↔ value, both unique
struct BiMap<K, V> {
    forward: HashMap<K, V>,
    backward: HashMap<V, K>,
}

impl<K, V> BiMap<K, V>
where
    K: Hash + Eq + Clone,
    V: Hash + Eq + Clone,
{
    fn new() -> Self {
        BiMap {
            forward: HashMap::new(),
            backward: HashMap::new(),
        }
    }

    fn insert(&mut self, key: K, value: V) {
        // Remove old mappings if key or value already exists
        if let Some(old_value) = self.forward.remove(&key) {
            self.backward.remove(&old_value);
        }
        if let Some(old_key) = self.backward.remove(&value) {
            self.forward.remove(&old_key);
        }

        self.backward.insert(value.clone(), key.clone());
        self.forward.insert(key, value);
    }

    fn get_by_key(&self, key: &K) -> Option<&V> {
        self.forward.get(key)
    }

    fn get_by_value(&self, value: &V) -> Option<&K> {
        self.backward.get(value)
    }

    fn remove_by_key(&mut self, key: &K) -> Option<V> {
        if let Some(value) = self.forward.remove(key) {
            self.backward.remove(&value);
            Some(value)
        } else {
            None
        }
    }

    fn remove_by_value(&mut self, value: &V) -> Option<K> {
        if let Some(key) = self.backward.remove(value) {
            self.forward.remove(&key);
            Some(key)
        } else {
            None
        }
    }

    fn len(&self) -> usize {
        self.forward.len()
    }

    fn contains_key(&self, key: &K) -> bool {
        self.forward.contains_key(key)
    }

    fn contains_value(&self, value: &V) -> bool {
        self.backward.contains_key(value)
    }
}

fn basic_ops() {
    let mut bm = BiMap::new();
    bm.insert("one", 1);
    bm.insert("two", 2);
    bm.insert("three", 3);

    assert_eq!(bm.get_by_key(&"two"), Some(&2));
    assert_eq!(bm.get_by_value(&2), Some(&"two"));
    assert_eq!(bm.get_by_key(&"four"), None);
    assert_eq!(bm.len(), 3);
}

fn overwrite_test() {
    let mut bm = BiMap::new();
    bm.insert("a", 1);
    bm.insert("b", 2);
    bm.insert("a", 3); // overwrites "a"->1, removes 1->"a"

    assert_eq!(bm.get_by_key(&"a"), Some(&3));
    assert_eq!(bm.get_by_value(&1), None); // old mapping gone
    assert_eq!(bm.get_by_value(&3), Some(&"a"));
}

fn codec_test() {
    let mut bm = BiMap::new();
    bm.insert("red", 0xFF0000u32);
    bm.insert("green", 0x00FF00);
    bm.insert("blue", 0x0000FF);

    assert_eq!(bm.get_by_key(&"red"), Some(&0xFF0000));
    assert_eq!(bm.get_by_value(&0x00FF00), Some(&"green"));

    bm.remove_by_key(&"red");
    assert_eq!(bm.get_by_key(&"red"), None);
    assert_eq!(bm.get_by_value(&0xFF0000u32), None);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_ops();
    }

    #[test]
    fn test_overwrite() {
        overwrite_test();
    }

    #[test]
    fn test_codec() {
        codec_test();
    }

    #[test]
    fn test_remove_by_value() {
        let mut bm = BiMap::new();
        bm.insert("x", 10);
        bm.insert("y", 20);
        assert_eq!(bm.remove_by_value(&10), Some("x"));
        assert!(!bm.contains_key(&"x"));
        assert!(!bm.contains_value(&10));
    }
}

(* 1042: Bidirectional Map — Two Maps for Key↔Value *)
(* Both directions must be unique for bimap to work *)

module StringMap = Map.Make(String)
module IntMap = Map.Make(Int)

type bimap = {
  forward: int StringMap.t;     (* string -> int *)
  backward: string IntMap.t;    (* int -> string *)
}

let empty = { forward = StringMap.empty; backward = IntMap.empty }

let insert key value bm =
  (* Remove old mappings if either key or value already exists *)
  let bm = match StringMap.find_opt key bm.forward with
    | Some old_val -> { bm with backward = IntMap.remove old_val bm.backward }
    | None -> bm
  in
  let bm = match IntMap.find_opt value bm.backward with
    | Some old_key -> { bm with forward = StringMap.remove old_key bm.forward }
    | None -> bm
  in
  { forward = StringMap.add key value bm.forward;
    backward = IntMap.add value key bm.backward }

let get_by_key key bm = StringMap.find_opt key bm.forward
let get_by_value value bm = IntMap.find_opt value bm.backward

let remove_by_key key bm =
  match StringMap.find_opt key bm.forward with
  | None -> bm
  | Some value ->
    { forward = StringMap.remove key bm.forward;
      backward = IntMap.remove value bm.backward }

let size bm = StringMap.cardinal bm.forward

(* Approach 1: Basic bidirectional lookup *)
let basic_ops () =
  let bm = empty
    |> insert "one" 1
    |> insert "two" 2
    |> insert "three" 3
  in
  assert (get_by_key "two" bm = Some 2);
  assert (get_by_value 2 bm = Some "two");
  assert (get_by_key "four" bm = None);
  assert (size bm = 3)

(* Approach 2: Overwrite handling *)
let overwrite_test () =
  let bm = empty
    |> insert "a" 1
    |> insert "b" 2
    |> insert "a" 3  (* overwrites "a"->1, removes 1->"a" *)
  in
  assert (get_by_key "a" bm = Some 3);
  assert (get_by_value 1 bm = None);  (* old mapping gone *)
  assert (get_by_value 3 bm = Some "a")

(* Approach 3: Encoding/decoding table *)
let codec_test () =
  let bm = empty
    |> insert "red" 0xFF0000
    |> insert "green" 0x00FF00
    |> insert "blue" 0x0000FF
  in
  assert (get_by_key "red" bm = Some 0xFF0000);
  assert (get_by_value 0x00FF00 bm = Some "green");
  let bm = remove_by_key "red" bm in
  assert (get_by_key "red" bm = None);
  assert (get_by_value 0xFF0000 bm = None)

let () =
  basic_ops ();
  overwrite_test ();
  codec_test ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_ops();
    }

    #[test]
    fn test_overwrite() {
        overwrite_test();
    }

    #[test]
    fn test_codec() {
        codec_test();
    }

    #[test]
    fn test_remove_by_value() {
        let mut bm = BiMap::new();
        bm.insert("x", 10);
        bm.insert("y", 20);
        assert_eq!(bm.remove_by_value(&10), Some("x"));
        assert!(!bm.contains_key(&"x"));
        assert!(!bm.contains_value(&10));
    }
}

Deep Comparison

Bidirectional Map — Comparison

Core Insight

A bimap enforces a one-to-one relationship between keys and values. It's built from two maps synchronized on insert/remove. The tricky part is handling overwrites — if you insert a key that already exists, you must clean up the old value's backward entry, and vice versa.

OCaml Approach

• Two functor-instantiated maps: StringMap.t and IntMap.t

• Record type { forward; backward } holds both

• Insert checks both directions for existing mappings

• Immutable — returns new bimap on each operation

• Different map modules needed for different types

Rust Approach

• HashMap<K, V> + HashMap<V, K> in a struct

• Generic over K: Hash + Eq + Clone, V: Hash + Eq + Clone

• Clone needed because values stored in both maps

• remove + insert for overwrite handling

• Single impl block covers all type combinations

Comparison Table

Feature	OCaml	Rust
Forward map	`StringMap.t` (functor)	`HashMap<K, V>`
Backward map	`IntMap.t` (functor)	`HashMap<V, K>`
Generics	Need different functors per type	Single generic struct
Clone	N/A (immutable sharing)	Required for both K and V
Insert complexity	Two map rebuilds	Two hash inserts + cleanup
Mutability	Immutable	Mutable

Exercises

Add a remove_by_key(&mut self, key: &K) -> Option<V> method that removes an entry and keeps both maps consistent.

Implement BiMap::from_iter(pairs: impl IntoIterator<Item=(K,V)>) -> Result<BiMap<K,V>, String> that returns an error if any key or value appears twice.

Write a symbol table for a simple language using BiMap<String, u32> where the u32 is a numeric ID.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust