Struct std::collections::trie_map::TrieMapExperimental [-]  [+] [src]

pub struct TrieMap<T> {
    // some 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 uint 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.

Example

fn main() { use std::collections::TrieMap; let mut map = TrieMap::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()); }
use std::collections::TrieMap;

let mut map = TrieMap::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> TrieMap<T>

fn new() -> TrieMap<T>

Creates an empty TrieMap.

Example

fn main() { use std::collections::TrieMap; let mut map: TrieMap<&str> = TrieMap::new(); }
use std::collections::TrieMap;
let mut map: TrieMap<&str> = TrieMap::new();

fn each_reverse(&'a self, f: |&uint, &'a T| -> bool) -> bool

Visits all key-value pairs in reverse order. Aborts traversal when f returns false. Returns true if f returns true for all elements.

Example

fn main() { use std::collections::TrieMap; let map: TrieMap<&str> = [(1, "a"), (2, "b"), (3, "c")].iter().map(|&x| x).collect(); let mut vec = Vec::new(); assert_eq!(true, map.each_reverse(|&key, &value| { vec.push((key, value)); true })); assert_eq!(vec, vec![(3, "c"), (2, "b"), (1, "a")]); // Stop when we reach 2 let mut vec = Vec::new(); assert_eq!(false, map.each_reverse(|&key, &value| { vec.push(value); key != 2 })); assert_eq!(vec, vec!["c", "b"]); }
use std::collections::TrieMap;
let map: TrieMap<&str> = [(1, "a"), (2, "b"), (3, "c")].iter().map(|&x| x).collect();

let mut vec = Vec::new();
assert_eq!(true, map.each_reverse(|&key, &value| { vec.push((key, value)); true }));
assert_eq!(vec, vec![(3, "c"), (2, "b"), (1, "a")]);

// Stop when we reach 2
let mut vec = Vec::new();
assert_eq!(false, map.each_reverse(|&key, &value| { vec.push(value); key != 2 }));
assert_eq!(vec, vec!["c", "b"]);

fn keys(&'r self) -> Map<'static, (uint, &'r T), uint, Entries<'r, T>>

Gets an iterator visiting all keys in ascending order by the keys. The iterator's element type is uint.

fn values(&'r self) -> Map<'static, (uint, &'r T), &'r T, Entries<'r, T>>

Gets an iterator visiting all values in ascending order by the keys. The iterator's element type is &'r T.

fn iter(&'a self) -> Entries<'a, T>

Gets an iterator over the key-value pairs in the map, ordered by keys.

Example

fn main() { use std::collections::TrieMap; let map: TrieMap<&str> = [(3, "c"), (1, "a"), (2, "b")].iter().map(|&x| x).collect(); for (key, value) in map.iter() { println!("{}: {}", key, value); } }
use std::collections::TrieMap;
let map: TrieMap<&str> = [(3, "c"), (1, "a"), (2, "b")].iter().map(|&x| x).collect();

for (key, value) in map.iter() {
    println!("{}: {}", key, value);
}

fn iter_mut(&'a mut self) -> MutEntries<'a, T>

Gets an iterator over the key-value pairs in the map, with the ability to mutate the values.

Example

fn main() { use std::collections::TrieMap; let mut map: TrieMap<int> = [(1, 2), (2, 4), (3, 6)].iter().map(|&x| x).collect(); for (key, value) in map.iter_mut() { *value = -(key as int); } assert_eq!(map.get(&1), Some(&-1)); assert_eq!(map.get(&2), Some(&-2)); assert_eq!(map.get(&3), Some(&-3)); }
use std::collections::TrieMap;
let mut map: TrieMap<int> = [(1, 2), (2, 4), (3, 6)].iter().map(|&x| x).collect();

for (key, value) in map.iter_mut() {
    *value = -(key as int);
}

assert_eq!(map.get(&1), Some(&-1));
assert_eq!(map.get(&2), Some(&-2));
assert_eq!(map.get(&3), Some(&-3));

fn len(&self) -> uint

Return the number of elements in the map.

Example

fn main() { use std::collections::TrieMap; let mut a = TrieMap::new(); assert_eq!(a.len(), 0); a.insert(1, "a"); assert_eq!(a.len(), 1); }
use std::collections::TrieMap;

let mut a = TrieMap::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);

fn is_empty(&self) -> bool

Return true if the map contains no elements.

Example

fn main() { use std::collections::TrieMap; let mut a = TrieMap::new(); assert!(a.is_empty()); a.insert(1, "a"); assert!(!a.is_empty()); }
use std::collections::TrieMap;

let mut a = TrieMap::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());

fn clear(&mut self)

Clears the map, removing all values.

Example

fn main() { use std::collections::TrieMap; let mut a = TrieMap::new(); a.insert(1, "a"); a.clear(); assert!(a.is_empty()); }
use std::collections::TrieMap;

let mut a = TrieMap::new();
a.insert(1, "a");
a.clear();
assert!(a.is_empty());

fn find(&self, key: &uint) -> Option<&T>

Deprecated: renamed to get.

fn get(&self, key: &uint) -> Option<&T>

Returns a reference to the value corresponding to the key.

Example

fn main() { use std::collections::TrieMap; let mut map = TrieMap::new(); map.insert(1, "a"); assert_eq!(map.get(&1), Some(&"a")); assert_eq!(map.get(&2), None); }
use std::collections::TrieMap;

let mut map = TrieMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);

fn contains_key(&self, key: &uint) -> bool

Returns true if the map contains a value for the specified key.

Example

fn main() { use std::collections::TrieMap; let mut map = TrieMap::new(); map.insert(1, "a"); assert_eq!(map.contains_key(&1), true); assert_eq!(map.contains_key(&2), false); }
use std::collections::TrieMap;

let mut map = TrieMap::new();
map.insert(1, "a");
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

fn find_mut(&mut self, key: &uint) -> Option<&mut T>

Deprecated: renamed to get_mut.

fn get_mut(&'a mut self, key: &uint) -> Option<&'a mut T>

Returns a mutable reference to the value corresponding to the key.

Example

fn main() { use std::collections::TrieMap; let mut map = TrieMap::new(); map.insert(1, "a"); match map.get_mut(&1) { Some(x) => *x = "b", None => (), } assert_eq!(map[1], "b"); }
use std::collections::TrieMap;

let mut map = TrieMap::new();
map.insert(1, "a");
match map.get_mut(&1) {
    Some(x) => *x = "b",
    None => (),
}
assert_eq!(map[1], "b");

fn swap(&mut self, key: uint, value: T) -> Option<T>

Deprecated: Renamed to insert.

fn insert(&mut self, key: uint, value: T) -> Option<T>

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.

Example

fn main() { use std::collections::TrieMap; let mut map = TrieMap::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"); }
use std::collections::TrieMap;

let mut map = TrieMap::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 pop(&mut self, key: &uint) -> Option<T>

Deprecated: Renamed to remove.

fn remove(&mut self, key: &uint) -> Option<T>

Removes a key from the map, returning the value at the key if the key was previously in the map.

Example

fn main() { use std::collections::TrieMap; let mut map = TrieMap::new(); map.insert(1, "a"); assert_eq!(map.remove(&1), Some("a")); assert_eq!(map.remove(&1), None); }
use std::collections::TrieMap;

let mut map = TrieMap::new();
map.insert(1, "a");
assert_eq!(map.remove(&1), Some("a"));
assert_eq!(map.remove(&1), None);

impl<T> TrieMap<T>

fn lower_bound(&'a self, key: uint) -> Entries<'a, T>

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.

Example

fn main() { use std::collections::TrieMap; let map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).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); }
use std::collections::TrieMap;
let map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).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(&'a self, key: uint) -> Entries<'a, T>

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.

Example

fn main() { use std::collections::TrieMap; let map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).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); }
use std::collections::TrieMap;
let map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).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(&'a mut self, key: uint) -> MutEntries<'a, T>

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.

Example

fn main() { use std::collections::TrieMap; let mut map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).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")); }
use std::collections::TrieMap;
let mut map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).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(&'a mut self, key: uint) -> MutEntries<'a, T>

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.

Example

fn main() { use std::collections::TrieMap; let mut map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).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")); }
use std::collections::TrieMap;
let mut map: TrieMap<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().map(|&x| x).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> TrieMap<T>

fn entry(&'a mut self, key: uint) -> Entry<'a, T>

Gets the given key's corresponding entry in the map for in-place manipulation.

Trait Implementations

impl<T: PartialEq> PartialEq for TrieMap<T>

fn eq(&self, other: &TrieMap<T>) -> bool

fn ne(&self, &TrieMap<T>) -> bool

impl<T: Eq> Eq for TrieMap<T>

fn assert_receiver_is_total_eq(&self)

impl<T: PartialOrd> PartialOrd for TrieMap<T>

fn partial_cmp(&self, other: &TrieMap<T>) -> Option<Ordering>

fn lt(&self, &TrieMap<T>) -> bool

fn le(&self, &TrieMap<T>) -> bool

fn gt(&self, &TrieMap<T>) -> bool

fn ge(&self, &TrieMap<T>) -> bool

impl<T: Ord> Ord for TrieMap<T>

fn cmp(&self, other: &TrieMap<T>) -> Ordering

impl<T: Show> Show for TrieMap<T>

fn fmt(&self, f: &mut Formatter) -> Result<(), Error>

impl<T> Default for TrieMap<T>

fn default() -> TrieMap<T>

impl<T> FromIterator<(uint, T)> for TrieMap<T>

fn from_iter<Iter: Iterator<(uint, T)>>(iter: Iter) -> TrieMap<T>

impl<T> Extend<(uint, T)> for TrieMap<T>

fn extend<Iter: Iterator<(uint, T)>>(&mut self, iter: Iter)

impl<S: Writer, T: Hash<S>> Hash<S> for TrieMap<T>

fn hash(&self, state: &mut S)

impl<T> Index<uint, T> for TrieMap<T>

fn index(&'a self, i: &uint) -> &'a T

impl<T> IndexMut<uint, T> for TrieMap<T>

fn index_mut(&'a mut self, i: &uint) -> &'a mut T

Derived Implementations

impl<T: Clone> Clone for TrieMap<T>

fn clone(&self) -> TrieMap<T>

fn clone_from(&mut self, &TrieMap<T>)