[−][src]Crate bimap
A fast two-way bijective map.
A bimap 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
or BTreeMap
, where every key is associated with exactly one
value but a value can be associated with more than one key.
This crate provides two kinds of bimap: a BiHashMap
and a
BiBTreeMap
. Internally, each one is composed of two maps, 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 the backing map.
For convenience, the type definition BiMap
corresponds to a BiHashMap
.
If you're using this crate without the standard library, it instead
corresponds to a BiBTreeMap
.
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 left-right
pairs ('a', 1)
and ('b', 1)
. 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. This crate 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 Result
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
or BTreeMap
, which doesn't
update an equal key upon insertion, a bimap updates both the left values
and the right values.
use bimap::{BiMap, Overwritten}; use std::cmp::Ordering; 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 {} impl PartialOrd for Foo { fn partial_cmp(&self, other: &Foo) -> Option<Ordering> { Some(self.cmp(other)) } } // ordering only depends on the important data impl Ord for Foo { fn cmp(&self, other: &Foo) -> Ordering { self.important.cmp(&other.important) } } // 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); // insert both Foos into a bimap let mut bimap = BiMap::new(); bimap.insert(foo1, 99); let overwritten = bimap.insert(foo2, 100); // foo1 is overwritten and returned match overwritten { Overwritten::Left(foo, 99) => assert_eq!(foo.unimportant, foo1.unimportant), _ => unreachable!(), }; // foo2 is in the bimap assert_eq!( bimap.get_by_right(&100).unwrap().unimportant, foo2.unimportant );
Note that the FromIterator
and Extend
implementations for both
BiHashMap
and BiBTreeMap
use the insert
method internally, meaning
that values from the original iterator/collection can be silently
overwritten.
use bimap::BiMap; use std::iter::FromIterator; // note that both 'b' and 'c' have the right-value 2 let mut bimap = BiMap::from_iter(vec![('a', 1), ('b', 2), ('c', 2)]); // ('b', 2) was overwritten by ('c', 2) assert_eq!(bimap.len(), 2); assert_eq!(bimap.get_by_left(&'b'), None); assert_eq!(bimap.get_by_left(&'c'), Some(&2));
no_std
compatibility
This crate can be used without the standard library when the std
feature
is disabled. If you choose to do this, only BiBTreeMap
is available, not
BiHashMap
.
serde compatibility
When the serde
feature is enabled, implementations of Serialize
and
Deserialize
are provided for BiHashMap
and BiBTreeMap
, allowing
them to be serialized or deserialized painlessly. See the serde
module
for examples and more information.
Re-exports
pub use btree::BiBTreeMap; |
pub use hash::BiHashMap; |
Modules
btree | A bimap backed by two |
hash | A bimap backed by two |
serde | Implementations of |
Enums
Overwritten | The previous left-right pairs, if any, that were overwritten by a call to
the |
Type Definitions
BiMap | Type definition for convenience and compatibility with older versions of this crate. |