Struct bst::map::TreeMap

pub struct TreeMap<K, V, C: Compare<K> = Natural<K>> {
    // some fields omitted
}

This is implemented as an AA tree, which is a simplified variation of a red-black tree where red (horizontal) nodes can only be added as a right child. The time complexity is the same, and re-balancing operations are more frequent but also cheaper.

Examples

use bst::TreeMap;

let mut map = TreeMap::new();

map.insert(2, "bar");
map.insert(1, "foo");
map.insert(3, "quux");

// In ascending order by keys
for (key, value) in map.iter() {
    println!("{}: {}", key, value);
}

// Prints 1, 2, 3
for key in map.keys() {
    println!("{}", key);
}

// Prints `foo`, `bar`, `quux`
for value in map.values() {
    println!("{}", value);
}

map.remove(&1);
assert_eq!(map.len(), 2);

if !map.contains_key(&1) {
    println!("1 is no more");
}

for key in 0..4 {
    match map.get(&key) {
        Some(value) => println!("{} has a value: {}", key, value),
        None => println!("{} not in map", key),
    }
}

map.clear();
assert!(map.is_empty());

A TreeMap can also be used with a custom ordering:

use bst::TreeMap;

struct Troll<'a> {
    name: &'a str,
    level: u32,
}

// Use a map to store trolls, sorted by level, and track a list of
// heroes slain.
let mut trolls = TreeMap::with_comparator(|l: &Troll, r: &Troll| l.level.cmp(&r.level));

trolls.insert(Troll { name: "Orgarr", level: 2 },
              vec!["King Karl"]);
trolls.insert(Troll { name: "Blargarr", level: 3 },
              vec!["Odd"]);
trolls.insert(Troll { name: "Kron the Smelly One", level: 4 },
              vec!["Omar the Brave", "Peter: Slayer of Trolls"]);
trolls.insert(Troll { name: "Wartilda", level: 1 },
              vec![]);

println!("You are facing {} trolls!", trolls.len());

// Print the trolls, ordered by level with smallest level first
for (troll, heroes) in trolls.iter() {
    let what = if heroes.len() == 1 { "hero" }
               else { "heroes" };

    println!("level {}: '{}' has slain {} {}",
             troll.level, troll.name, heroes.len(), what);
}

// Kill all trolls
trolls.clear();
assert_eq!(trolls.len(), 0);

Methods

impl<K: Ord, V> TreeMap<K, V>

fn new() -> TreeMap<K, V>

Creates an empty TreeMap ordered according to the natural order of its keys.

Examples

use bst::TreeMap;
let mut map: TreeMap<&str, i32> = TreeMap::new();

impl<K, V, C> TreeMap<K, V, C> where C: Compare<K>

fn with_comparator(cmp: C) -> TreeMap<K, V, C>

Creates an empty TreeMap ordered according to the given comparator.

fn comparator(&self) -> &C

Returns the comparator according to which the TreeMap is ordered.

fn keys<'a>(&'a self) -> Keys<'a, K, V>

Gets a lazy iterator over the keys in the map, in ascending order.

Examples

use bst::TreeMap;
let mut map = TreeMap::new();
map.insert("a", 1);
map.insert("c", 3);
map.insert("b", 2);

// Print "a", "b", "c" in order.
for x in map.keys() {
    println!("{}", x);
}

fn values<'a>(&'a self) -> Values<'a, K, V>

Gets a lazy iterator over the values in the map, in ascending order with respect to the corresponding keys.

Examples

use bst::TreeMap;
let mut map = TreeMap::new();
map.insert("a", 1);
map.insert("c", 3);
map.insert("b", 2);

// Print 1, 2, 3 ordered by keys.
for x in map.values() {
    println!("{}", x);
}

fn iter(&self) -> Iter<K, V>

Gets a lazy iterator over the key-value pairs in the map, in ascending order.

Examples

use bst::TreeMap;
let mut map = TreeMap::new();
map.insert("a", 1);
map.insert("c", 3);
map.insert("b", 2);

// Print contents in ascending order
for (key, value) in map.iter() {
    println!("{}: {}", key, value);
}

fn rev_iter(&self) -> RevIter<K, V>

Gets a lazy reverse iterator over the key-value pairs in the map, in descending order.

Examples

use bst::TreeMap;
let mut map = TreeMap::new();
map.insert("a", 1);
map.insert("c", 3);
map.insert("b", 2);

// Print contents in descending order
for (key, value) in map.rev_iter() {
    println!("{}: {}", key, value);
}

fn iter_mut(&mut self) -> IterMut<K, V>

Gets a lazy forward iterator over the key-value pairs in the map, with the values being mutable.

Examples

use bst::TreeMap;
let mut map = TreeMap::new();
map.insert("a", 1);
map.insert("c", 3);
map.insert("b", 2);

// Add 10 until we find "b"
for (key, value) in map.iter_mut() {
    *value += 10;
    if key == &"b" { break }
}

assert_eq!(map.get(&"a"), Some(&11));
assert_eq!(map.get(&"b"), Some(&12));
assert_eq!(map.get(&"c"), Some(&3));

fn rev_iter_mut(&mut self) -> RevIterMut<K, V>

Gets a lazy reverse iterator over the key-value pairs in the map, with the values being mutable.

Examples

use bst::TreeMap;
let mut map = TreeMap::new();
map.insert("a", 1);
map.insert("c", 3);
map.insert("b", 2);

// Add 10 until we find "b"
for (key, value) in map.rev_iter_mut() {
    *value += 10;
    if key == &"b" { break }
}

assert_eq!(map.get(&"a"), Some(&1));
assert_eq!(map.get(&"b"), Some(&12));
assert_eq!(map.get(&"c"), Some(&13));

fn into_iter(self) -> IntoIter<K, V>

Gets a lazy iterator that consumes the treemap.

Examples

use bst::TreeMap;
let mut map = TreeMap::new();
map.insert("a", 1);
map.insert("c", 3);
map.insert("b", 2);

// Not possible with a regular `.iter()`
let vec: Vec<(&str, i32)> = map.into_iter().collect();
assert_eq!(vec, vec![("a", 1), ("b", 2), ("c", 3)]);

fn len(&self) -> usize

Return the number of elements in the map.

Examples

use bst::TreeMap;

let mut a = TreeMap::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.

Examples

use bst::TreeMap;

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

fn clear(&mut self)

Clears the map, removing all values.

Examples

use bst::TreeMap;

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

fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where C: Compare<Q, K>

Returns a reference to the value corresponding to the key.

The key may be any borrowed form of the map's key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

use bst::TreeMap;

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

fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where C: Compare<Q, K>

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

The key may be any borrowed form of the map's key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

use bst::TreeMap;

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

fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where C: Compare<Q, K>

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

The key may be any borrowed form of the map's key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

use bst::TreeMap;

let mut map = TreeMap::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: K, value: V) -> Option<V>

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

use bst::TreeMap;

let mut map = TreeMap::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<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where C: Compare<Q, K>

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

The key may be any borrowed form of the map's key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

use bst::TreeMap;

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

fn find_with<F>(&self, f: F) -> Option<&V> where F: FnMut(&K) -> Ordering

Returns the value for which f(key) returns Equal. f is invoked with current key and guides tree navigation. That means f should be aware of natural ordering of the tree.

Examples

use bst::TreeMap;

fn get_headers() -> TreeMap<&'static str, &'static str> {
    let mut result = TreeMap::new();
    result.insert("Content-Type", "application/xml");
    result.insert("User-Agent", "Curl-Rust/0.1");
    result
}

let headers = get_headers();
let ua_key = "User-Agent";
let ua = headers.find_with(|&k| {
   ua_key.cmp(k)
});

assert_eq!(*ua.unwrap(), "Curl-Rust/0.1");

fn find_with_mut<F>(&mut self, f: F) -> Option<&mut V> where F: FnMut(&K) -> Ordering

Returns the value for which f(key) returns Equal. f is invoked with current key and guides tree navigation. That means f should be aware of natural ordering of the tree.

Examples

let mut t = bst::TreeMap::new();
t.insert("Content-Type", "application/xml");
t.insert("User-Agent", "Curl-Rust/0.1");

let new_ua = "Safari/156.0";
match t.find_with_mut(|&k| "User-Agent".cmp(k)) {
   Some(x) => *x = new_ua,
   None => panic!(),
}

assert_eq!(t.get(&"User-Agent"), Some(&new_ua));

impl<K, V, C> TreeMap<K, V, C> where C: Compare<K>

fn lower_bound<Q: ?Sized>(&self, k: &Q) -> Iter<K, V> where C: Compare<Q, K>

Returns a lazy iterator to the first key-value pair whose key is not less than k If all keys in map are less than k an empty iterator is returned.

Examples

use bst::TreeMap;

let mut map = TreeMap::new();
map.insert(2, "a");
map.insert(4, "b");
map.insert(6, "c");
map.insert(8, "d");

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<Q: ?Sized>(&self, k: &Q) -> Iter<K, V> where C: Compare<Q, K>

Returns a lazy iterator to the first key-value pair whose key is greater than k If all keys in map are less than or equal to k an empty iterator is returned.

Examples

use bst::TreeMap;

let mut map = TreeMap::new();
map.insert(2, "a");
map.insert(4, "b");
map.insert(6, "c");
map.insert(8, "d");

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<Q: ?Sized>(&mut self, k: &Q) -> IterMut<K, V> where C: Compare<Q, K>

Returns a lazy value iterator to the first key-value pair (with the value being mutable) whose key is not less than k.

If all keys in map are less than k an empty iterator is returned.

Examples

use bst::TreeMap;

let mut map = TreeMap::new();
map.insert(2, "a");
map.insert(4, "b");
map.insert(6, "c");
map.insert(8, "d");

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"));
assert_eq!(map.get(&8), Some(&"changed"));

fn upper_bound_mut<Q: ?Sized>(&mut self, k: &Q) -> IterMut<K, V> where C: Compare<Q, K>

Returns a lazy iterator to the first key-value pair (with the value being mutable) whose key is greater than k.

If all keys in map are less than or equal to k an empty iterator is returned.

Examples

use bst::TreeMap;

let mut map = TreeMap::new();
map.insert(2, "a");
map.insert(4, "b");
map.insert(6, "c");
map.insert(8, "d");

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"));
assert_eq!(map.get(&8), Some(&"changed"));

Trait Implementations

impl<K: PartialEq + Ord, V: PartialEq> PartialEq for TreeMap<K, V>

fn eq(&self, other: &TreeMap<K, V>) -> bool

fn ne(&self, other: &Rhs) -> bool

impl<K: Eq + Ord, V: Eq> Eq for TreeMap<K, V>

fn assert_receiver_is_total_eq(&self)

impl<K: Ord, V: PartialOrd> PartialOrd for TreeMap<K, V>

fn partial_cmp(&self, other: &TreeMap<K, V>) -> Option<Ordering>

fn lt(&self, other: &Rhs) -> bool

fn le(&self, other: &Rhs) -> bool

fn gt(&self, other: &Rhs) -> bool

fn ge(&self, other: &Rhs) -> bool

impl<K: Ord, V: Ord> Ord for TreeMap<K, V>

fn cmp(&self, other: &TreeMap<K, V>) -> Ordering

impl<K: Debug, V: Debug, C> Debug for TreeMap<K, V, C> where C: Compare<K>

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

impl<K, V, C> Default for TreeMap<K, V, C> where C: Compare<K> + Default

fn default() -> TreeMap<K, V, C>

impl<'a, K, V, C, Q: ?Sized> Index<&'a Q> for TreeMap<K, V, C> where C: Compare<K> + Compare<Q, K>

type Output = V

fn index(&self, i: &'a Q) -> &V

impl<'a, K, V, C, Q: ?Sized> IndexMut<&'a Q> for TreeMap<K, V, C> where C: Compare<K> + Compare<Q, K>

fn index_mut(&mut self, i: &'a Q) -> &mut V

impl<K, V, C> FromIterator<(K, V)> for TreeMap<K, V, C> where C: Compare<K> + Default

fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> TreeMap<K, V, C>

impl<K, V, C> Extend<(K, V)> for TreeMap<K, V, C> where C: Compare<K>

fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T)

impl<K: Hash, V: Hash, C> Hash for TreeMap<K, V, C> where C: Compare<K>

fn hash<H: Hasher>(&self, state: &mut H)

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

impl<K, V, C> IntoIterator for TreeMap<K, V, C> where C: Compare<K>

type Item = (K, V)

type IntoIter = IntoIter<K, V>

fn into_iter(self) -> IntoIter<K, V>

Derived Implementations

impl<K: Clone, V: Clone, C: Clone + Compare<K>> Clone for TreeMap<K, V, C> where K: Clone, V: Clone, C: Clone

fn clone(&self) -> TreeMap<K, V, C>

fn clone_from(&mut self, source: &Self)