Struct trie::map::Map [−] [src]

`pub struct Map<T> { /* fields omitted */ }`

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());```

Methods

`impl<T> Map<T>`[src]

`fn new() -> Map<T>`[src]

Creates an empty map.

Examples

`let mut map: trie::Map<&str> = trie::Map::new();`

`fn each_reverse<'a, F>(&'a self, f: F) -> bool where    F: FnMut(&usize, &'a T) -> bool, `[src]

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"]);```

`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`.

`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`.

`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);
}```

`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));```

`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);```

`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());```

`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());```

`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);```

`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);```

`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");```

`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");```

`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]

`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);```

`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);```

`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"));```

`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]

`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]

`fn clone(&self) -> Map<T>`[src]

Returns a copy of the value. Read more

`fn clone_from(&mut self, source: &Self)`1.0.0[src]

Performs copy-assignment from `source`. Read more

`impl<T: PartialEq> PartialEq for Map<T>`[src]

`fn eq(&self, other: &Map<T>) -> bool`[src]

This method tests for `self` and `other` values to be equal, and is used by `==`. Read more

`fn ne(&self, other: &Rhs) -> bool`1.0.0[src]

This method tests for `!=`.

`impl<T: PartialOrd> PartialOrd for Map<T>`[src]

`fn partial_cmp(&self, other: &Map<T>) -> Option<Ordering>`[src]

This method returns an ordering between `self` and `other` values if one exists. Read more

`fn lt(&self, other: &Rhs) -> bool`1.0.0[src]

This method tests less than (for `self` and `other`) and is used by the `<` operator. Read more

`fn le(&self, other: &Rhs) -> bool`1.0.0[src]

This method tests less than or equal to (for `self` and `other`) and is used by the `<=` operator. Read more

`fn gt(&self, other: &Rhs) -> bool`1.0.0[src]

This method tests greater than (for `self` and `other`) and is used by the `>` operator. Read more

`fn ge(&self, other: &Rhs) -> bool`1.0.0[src]

This method tests greater than or equal to (for `self` and `other`) and is used by the `>=` operator. Read more

`impl<T: Ord> Ord for Map<T>`[src]

`fn cmp(&self, other: &Map<T>) -> Ordering`[src]

This method returns an `Ordering` between `self` and `other`. Read more

`fn max(self, other: Self) -> Self`1.22.0[src]

Compares and returns the maximum of two values. Read more

`fn min(self, other: Self) -> Self`1.22.0[src]

Compares and returns the minimum of two values. Read more

`impl<T: Debug> Debug for Map<T>`[src]

`fn fmt(&self, f: &mut Formatter) -> Result`[src]

Formats the value using the given formatter.

`impl<T> Default for Map<T>`[src]

`fn default() -> Map<T>`[src]

Returns the "default value" for a type. Read more

`impl<T> FromIterator<(usize, T)> for Map<T>`[src]

`fn from_iter<I: IntoIterator<Item = (usize, T)>>(iter: I) -> Map<T>`[src]

Creates a value from an iterator. Read more

`impl<T> Extend<(usize, T)> for Map<T>`[src]

`fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I)`[src]

Extends a collection with the contents of an iterator. Read more

`impl<T: Hash> Hash for Map<T>`[src]

`fn hash<H: Hasher>(&self, state: &mut H)`[src]

Feeds this value into the given [`Hasher`]. Read more

`fn hash_slice<H>(data: &[Self], state: &mut H) where    H: Hasher, `1.3.0[src]

Feeds a slice of this type into the given [`Hasher`]. Read more

`impl<'a, T> Index<&'a usize> for Map<T>`[src]

`type Output = T`

The returned type after indexing.

`fn index(&self, i: &'a usize) -> &T`[src]

Performs the indexing (`container[index]`) operation.

`impl<'a, T> IndexMut<&'a usize> for Map<T>`[src]

`fn index_mut(&mut self, i: &'a usize) -> &mut T`[src]

Performs the mutable indexing (`container[index]`) operation.

`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]

Creates an iterator from a value. Read more

`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]

Creates an iterator from a value. Read more