Crate bimap [−] [src]
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 HashMap
s, 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 |
Iter |
An iterator over the left-right pairs in a |
LeftValues |
An iterator over the left values in a |
RightValues |
An iterator over the right values in a |
Enums
Overwritten |
The previous left-right pairs, if any, that were overwritten by a call to the |