Module incremental_topo::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. 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 |