[−][src]Struct trie::map::Map
A map implemented as a radix trie.
Keys are split into sequences of 4 bits, which are used to place elements in
16-entry arrays which are nested to form a tree structure. Inserted elements are placed
as close to the top of the tree as possible. The most significant bits of the key are used to
assign the key to a node/bucket in the first layer. If there are no other elements keyed by
the same 4 bits in the first layer, a leaf node will be created in the first layer.
When keys coincide, the next 4 bits are used to assign the node to a bucket in the next layer,
with this process continuing until an empty spot is found or there are no more bits left in the
key. As a result, the maximum depth using 32-bit usize
keys is 8. The worst collisions occur
for very small numbers. For example, 1 and 2 are identical in all but their least significant
4 bits. If both numbers are used as keys, a chain of maximum length will be created to
differentiate them.
Examples
let mut map = trie::Map::new(); map.insert(27, "Olaf"); map.insert(1, "Edgar"); map.insert(13, "Ruth"); map.insert(1, "Martin"); assert_eq!(map.len(), 3); assert_eq!(map.get(&1), Some(&"Martin")); if !map.contains_key(&90) { println!("Nobody is keyed 90"); } // Update a key match map.get_mut(&1) { Some(value) => *value = "Olga", None => (), } map.remove(&13); assert_eq!(map.len(), 2); // Print the key value pairs, ordered by key. for (key, value) in map.iter() { // Prints `1: Olga` then `27: Olaf` println!("{}: {}", key, value); } map.clear(); assert!(map.is_empty());
Implementations
impl<T> Map<T>
[src]
pub fn new() -> Map<T>
[src]
pub fn each_reverse<'a, F>(&'a self, f: F) -> bool where
F: FnMut(&usize, &'a T) -> bool,
[src]
F: FnMut(&usize, &'a T) -> bool,
Visits all key-value pairs in reverse order. Aborts traversal when f
returns false
.
Returns true
if f
returns true
for all elements.
Examples
let map: trie::Map<&str> = [(1, "a"), (2, "b"), (3, "c")].iter().cloned().collect(); let mut vec = vec![]; assert_eq!(true, map.each_reverse(|&key, &value| { vec.push((key, value)); true })); assert_eq!(vec, [(3, "c"), (2, "b"), (1, "a")]); // Stop when we reach 2 let mut vec = vec![]; assert_eq!(false, map.each_reverse(|&key, &value| { vec.push(value); key != 2 })); assert_eq!(vec, ["c", "b"]);
pub fn keys(&self) -> Keys<T>
[src]
Gets an iterator visiting all keys in ascending order by the keys.
The iterator's element type is usize
.
pub fn values(&self) -> Values<T>
[src]
Gets an iterator visiting all values in ascending order by the keys.
The iterator's element type is &'r T
.
pub fn iter(&self) -> Iter<T>
[src]
Gets an iterator over the key-value pairs in the map, ordered by keys.
Examples
let map: trie::Map<&str> = [(3, "c"), (1, "a"), (2, "b")].iter().cloned().collect(); for (key, value) in map.iter() { println!("{}: {}", key, value); }
pub fn iter_mut(&mut self) -> IterMut<T>
[src]
Gets an iterator over the key-value pairs in the map, with the ability to mutate the values.
Examples
let mut map: trie::Map<i32> = [(1, 2), (2, 4), (3, 6)].iter().cloned().collect(); for (key, value) in map.iter_mut() { *value = -(key as i32); } assert_eq!(map.get(&1), Some(&-1)); assert_eq!(map.get(&2), Some(&-2)); assert_eq!(map.get(&3), Some(&-3));
pub fn len(&self) -> usize
[src]
Return the number of elements in the map.
Examples
let mut a = trie::Map::new(); assert_eq!(a.len(), 0); a.insert(1, "a"); assert_eq!(a.len(), 1);
pub fn is_empty(&self) -> bool
[src]
Return true if the map contains no elements.
Examples
let mut a = trie::Map::new(); assert!(a.is_empty()); a.insert(1, "a"); assert!(!a.is_empty());
pub fn clear(&mut self)
[src]
Clears the map, removing all values.
Examples
let mut a = trie::Map::new(); a.insert(1, "a"); a.clear(); assert!(a.is_empty());
pub fn get(&self, key: &usize) -> Option<&T>
[src]
Returns a reference to the value corresponding to the key.
Examples
let mut map = trie::Map::new(); map.insert(1, "a"); assert_eq!(map.get(&1), Some(&"a")); assert_eq!(map.get(&2), None);
pub fn contains_key(&self, key: &usize) -> bool
[src]
Returns true if the map contains a value for the specified key.
Examples
let mut map = trie::Map::new(); map.insert(1, "a"); assert_eq!(map.contains_key(&1), true); assert_eq!(map.contains_key(&2), false);
pub fn get_mut(&mut self, key: &usize) -> Option<&mut T>
[src]
Returns a mutable reference to the value corresponding to the key.
Examples
let mut map = trie::Map::new(); map.insert(1, "a"); match map.get_mut(&1) { Some(x) => *x = "b", None => (), } assert_eq!(map[&1], "b");
pub fn insert(&mut self, key: usize, value: T) -> Option<T>
[src]
Inserts a key-value pair from the map. If the key already had a value
present in the map, that value is returned. Otherwise, None
is returned.
Examples
let mut map = trie::Map::new(); assert_eq!(map.insert(37, "a"), None); assert_eq!(map.is_empty(), false); map.insert(37, "b"); assert_eq!(map.insert(37, "c"), Some("b")); assert_eq!(map[&37], "c");
pub fn remove(&mut self, key: &usize) -> Option<T>
[src]
Removes a key from the map, returning the value at the key if the key was previously in the map.
Examples
let mut map = trie::Map::new(); map.insert(1, "a"); assert_eq!(map.remove(&1), Some("a")); assert_eq!(map.remove(&1), None);
impl<T> Map<T>
[src]
pub fn lower_bound(&self, key: usize) -> Range<T>
[src]
Gets an iterator pointing to the first key-value pair whose key is not less than key
.
If all keys in the map are less than key
an empty iterator is returned.
Examples
let map: trie::Map<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().cloned().collect(); assert_eq!(map.lower_bound(4).next(), Some((4, &"b"))); assert_eq!(map.lower_bound(5).next(), Some((6, &"c"))); assert_eq!(map.lower_bound(10).next(), None);
pub fn upper_bound(&self, key: usize) -> Range<T>
[src]
Gets an iterator pointing to the first key-value pair whose key is greater than key
.
If all keys in the map are not greater than key
an empty iterator is returned.
Examples
let map: trie::Map<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().cloned().collect(); assert_eq!(map.upper_bound(4).next(), Some((6, &"c"))); assert_eq!(map.upper_bound(5).next(), Some((6, &"c"))); assert_eq!(map.upper_bound(10).next(), None);
pub fn lower_bound_mut(&mut self, key: usize) -> RangeMut<T>
[src]
Gets an iterator pointing to the first key-value pair whose key is not less than key
.
If all keys in the map are less than key
an empty iterator is returned.
Examples
let mut map: trie::Map<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().cloned().collect(); assert_eq!(map.lower_bound_mut(4).next(), Some((4, &mut "b"))); assert_eq!(map.lower_bound_mut(5).next(), Some((6, &mut "c"))); assert_eq!(map.lower_bound_mut(10).next(), None); for (key, value) in map.lower_bound_mut(4) { *value = "changed"; } assert_eq!(map.get(&2), Some(&"a")); assert_eq!(map.get(&4), Some(&"changed")); assert_eq!(map.get(&6), Some(&"changed"));
pub fn upper_bound_mut(&mut self, key: usize) -> RangeMut<T>
[src]
Gets an iterator pointing to the first key-value pair whose key is greater than key
.
If all keys in the map are not greater than key
an empty iterator is returned.
Examples
let mut map: trie::Map<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().cloned().collect(); assert_eq!(map.upper_bound_mut(4).next(), Some((6, &mut "c"))); assert_eq!(map.upper_bound_mut(5).next(), Some((6, &mut "c"))); assert_eq!(map.upper_bound_mut(10).next(), None); for (key, value) in map.upper_bound_mut(4) { *value = "changed"; } assert_eq!(map.get(&2), Some(&"a")); assert_eq!(map.get(&4), Some(&"b")); assert_eq!(map.get(&6), Some(&"changed"));
impl<T> Map<T>
[src]
pub fn entry(&mut self, key: usize) -> Entry<T>
[src]
Gets the given key's corresponding entry in the map for in-place manipulation.
Trait Implementations
impl<T: Clone> Clone for Map<T>
[src]
impl<T: Debug> Debug for Map<T>
[src]
impl<T> Default for Map<T>
[src]
impl<T: Eq> Eq for Map<T>
[src]
impl<T> Extend<(usize, T)> for Map<T>
[src]
impl<T> FromIterator<(usize, T)> for Map<T>
[src]
impl<T: Hash> Hash for Map<T>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<'a, T> Index<&'a usize> for Map<T>
[src]
impl<'a, T> IndexMut<&'a usize> for Map<T>
[src]
impl<'a, T> IntoIterator for &'a Map<T>
[src]
type Item = (usize, &'a T)
The type of the elements being iterated over.
type IntoIter = Iter<'a, T>
Which kind of iterator are we turning this into?
fn into_iter(self) -> Iter<'a, T>
[src]
impl<'a, T> IntoIterator for &'a mut Map<T>
[src]
type Item = (usize, &'a mut T)
The type of the elements being iterated over.
type IntoIter = IterMut<'a, T>
Which kind of iterator are we turning this into?
fn into_iter(self) -> IterMut<'a, T>
[src]
impl<T: Ord> Ord for Map<T>
[src]
fn cmp(&self, other: &Map<T>) -> Ordering
[src]
#[must_use]fn max(self, other: Self) -> Self
1.21.0[src]
#[must_use]fn min(self, other: Self) -> Self
1.21.0[src]
#[must_use]fn clamp(self, min: Self, max: Self) -> Self
[src]
impl<T: PartialEq> PartialEq<Map<T>> for Map<T>
[src]
impl<T: PartialOrd> PartialOrd<Map<T>> for Map<T>
[src]
Auto Trait Implementations
impl<T> RefUnwindSafe for Map<T> where
T: RefUnwindSafe,
T: RefUnwindSafe,
impl<T> Send for Map<T> where
T: Send,
T: Send,
impl<T> Sync for Map<T> where
T: Sync,
T: Sync,
impl<T> Unpin for Map<T> where
T: Unpin,
T: Unpin,
impl<T> UnwindSafe for Map<T> where
T: UnwindSafe,
T: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,