Module incremental_topo::bimap

A fast two-way bijective map.

Disclaimer

This API and documentation is taken directly from Billy Rieger's bimap-rs. Specific changes have been made to the implementation such that left and right values can be searched for using Borrowed versions of themselves.

Before the change the get_by_left function signature looked like this:

pub fn get_by_left(&self, left: &L) -> Option<&R>;

After the change the get_by_left function signature looks like this:

pub fn get_by_left<P>(&self, left: &P) -> Option<&R>
where
    L: Borrow<P>,
    P: Hash + Eq + ?Sized,

In order to accomodate this change, the internal representation of the bimap changed slightly. Previously bimap used an internal representation of two hashmaps that mapped Rc<L> -> Rc<R> and Rc<R> -> Rc<L>. The new version also has two hashmaps that map hash(L) -> R and hash(R) -> L.

Overall, this version accomplishes the bare minimum needed for a bimap, while bimap-rs offers more options.

Description

A BiMap<L, R> is a bijective map between values of type L, called left values, and values of type R, called right values. This means every left value is associated with exactly one right value and vice versa. Compare this to a HashMap, where every key is associated with exactly one value but a value can be associated with more than one key.

Internally, a BiMap is composed of two HashMaps, one for the left-to-right direction and one for right-to-left. As such, the big-O performance of the get, remove, insert, and contains methods are the same as those of a HashMap.

As with HashMap, it is considered a logic error to modify a value's hash while it is in the BiMap using a Cell, RefCell, etc. This is especially important because both the left and right values are hashed, and accessible via mutable getters.

Examples

use incremental_topo::bimap::BiMap;

let mut elements = BiMap::new();

// insert chemicals and their corresponding symbols
elements.insert("hydrogen", "H");
elements.insert("carbon", "C");
elements.insert("bromine", "Br");
elements.insert("neodymium", "Nd");

// retrieve chemical symbol by name (left to right)
assert_eq!(elements.get_by_left(&"bromine"), Some(&"Br"));
assert_eq!(elements.get_by_left(&"oxygen"), None);

// retrieve name by chemical symbol (right to left)
assert_eq!(elements.get_by_right(&"C"), Some(&"carbon"));
assert_eq!(elements.get_by_right(&"Al"), None);

// check membership
assert!(elements.contains_left(&"hydrogen"));
assert!(!elements.contains_right(&"He"));

// remove elements
assert_eq!(
    elements.remove_by_left(&"neodymium"),
    Some(("neodymium", "Nd"))
);
assert_eq!(elements.remove_by_right(&"Nd"), None);

// iterate over elements
for (left, right) in elements.iter() {
    println!("the chemical symbol for {} is {}", left, right);
}

Insertion and overwriting

Consider the following example:

use incremental_topo::bimap::BiMap;

let mut bimap = BiMap::new();
bimap.insert('a', 1);
bimap.insert('b', 1); // what to do here?

In order to maintain the bijection, the BiMap cannot have both ('a', 1) and ('b', 1) in the map. Otherwise, the right-value 1 would have two left values associated with it. Either we should allow the call to insert to go through and overwrite ('a', 1), or not let ('b', 1) be inserted at all. BiMap allows for both possibilities. To insert with overwriting, use insert, and to insert without overwriting, use insert_no_overwrite. The return type of insert is the enum Overwritten, which indicates what values, if any, were overwritten; the return type of insert_no_overwrite is a boolean indicating if the insertion was successful.

This is especially important when dealing with types that can be equal while having different data. Unlike a HashMap, which doesn't update an equal key upon insertion, a BiMap updates both the left values and the right values.

use incremental_topo::bimap::{BiMap, Overwritten};
use std::hash::{Hash, Hasher};

#[derive(Clone, Copy, Debug)]
struct Foo {
    important: char,
    unimportant: u32,
}

// equality only depends on the important data
impl PartialEq for Foo {
    fn eq(&self, other: &Foo) -> bool {
        self.important == other.important
    }
}

impl Eq for Foo {}

// hash only depends on the important data
impl Hash for Foo {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.important.hash(state);
    }
}

// create two Foos that are equal but have different data
let foo1 = Foo {
    important: 'a',
    unimportant: 1,
};
let foo2 = Foo {
    important: 'a',
    unimportant: 2,
};
assert_eq!(foo1, foo2);

let mut bimap = BiMap::new();
bimap.insert(foo1, 99);
let overwritten = bimap.insert(foo2, 100);
// foo1 is overwritten and returned; foo2 is in the bimap
assert_eq!(overwritten, Overwritten::Left(foo1, 99));
assert_eq!(bimap.get_by_right(&100), Some(&foo2));

Structs

BiMap

A two-way map between left values and right values.

Enums

Overwritten

The previous pairs, if any, that were overwritten by a call the insert method of BiMap.