Crate bimap

A fast two-way bijective map.

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.

Examples

use 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 {
    println!("the chemical symbol for {} is {}", left, right);
}

Insertion and overwriting

Consider the following example:

use 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 std::hash::{Hash, Hasher};
use bimap::{BiMap, Overwritten};

#[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.
IntoIter	An owning iterator over the left-right pairs in a BiMap.
Iter	An iterator over the left-right pairs in a BiMap.
LeftValues	An iterator over the left values in a BiMap.
RightValues	An iterator over the right values in a BiMap.

Enums

Overwritten

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