Struct stable_bst::map::TreeMap

pub struct TreeMap<K, V, C: Compare<K> = Natural<K>> { /* 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 stable_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 stable_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 stable_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 stable_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 stable_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 values_mut<'a>(&'a mut self) -> ValuesMut<'a, K, V>

Gets a lazy iterator over the values in the map, in ascending order with respect to the corresponding keys, returning a mutable reference to each value.

Examples

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

for x in map.values_mut() {
    *x += 1;
}

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

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

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

Examples

use stable_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 iter_mut(&mut self) -> IterMut<K, V, Forward>

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

Examples

use stable_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 into_iter(self) -> IntoIter<K, V>

Gets a lazy iterator that consumes the treemap.

Examples

use stable_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 stable_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 stable_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 stable_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 stable_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 stable_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 stable_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 stable_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 stable_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 get_or_insert<F>(&mut self, key: K, default: F) -> &mut V where
    F: FnOnce() -> V, 

If a value for key does not exist, create one by callling default. Returns a mut reference to the new or existing value.

Examples

use stable_bst::TreeMap;

let mut count: TreeMap<&str, usize> = TreeMap::new();

// count the number of occurrences of letters in the vec
for x in vec!["a","b","a","c","a","b"] {
    *count.get_or_insert(x, || 0) += 1;
}
assert_eq!(count[&"a"], 3);

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 stable_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 = stable_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 range_mut<'a, Min: ?Sized, Max: ?Sized>(
    &'a mut self,
    min: Bound<&Min>,
    max: Bound<&Max>
) -> RangeMut<'a, K, V> where
    C: Compare<Min, K> + Compare<Max, K>, 

Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting at min, and ending at max. If min is Unbounded, then it will be treated as "negative infinity", and if max is Unbounded, then it will be treated as "positive infinity". Thus range(Unbounded, Unbounded) will yield the whole collection.

Examples

Basic usage:

use stable_bst::TreeMap;
use stable_bst::Bound::{Included, Excluded};

let mut map: TreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
                                                                     .map(|&s| (s, 0))
                                                                     .collect();
for (_, balance) in map.range_mut(Included(&"B"), Excluded(&"Cheryl")) {
    *balance += 100;
}
for (name, balance) in &map {
    println!("{} => {}", name, balance);
}

fn range<'a, Min: ?Sized, Max: ?Sized>(
    &'a self,
    min: Bound<&Min>,
    max: Bound<&Max>
) -> Range<'a, K, V> where
    C: Compare<Min, K> + Compare<Max, K>, 

Constructs a double-ended iterator over a sub-range of elements in the map, starting at min, and ending at max. If min is Unbounded, then it will be treated as "negative infinity", and if max is Unbounded, then it will be treated as "positive infinity". Thus range(Unbounded, Unbounded) will yield the whole collection.

Examples

Basic usage:

use stable_bst::TreeMap;
use stable_bst::Bound::{Included, Unbounded};

let mut map = TreeMap::new();
map.insert(3, "a");
map.insert(5, "b");
map.insert(8, "c");
for (&key, &value) in map.range(Included(&4), Included(&8)) {
    println!("{}: {}", key, value);
}
assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

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

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

This method tests for !=.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

This method returns an Ordering between self and other.

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

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

Formats the value using the given formatter.

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

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

Returns the "default value" for a type.

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

The returned type after indexing

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

The method for the indexing (container[index]) operation

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

The method for the mutable indexing (container[index]) operation

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>

Creates a value from an iterator.

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)

Extends a collection with the contents of an iterator.

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

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

Feeds this value into the given [Hasher].

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

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

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

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V, Forward>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, K, V, Forward>

Creates an iterator from a value.

impl<'a, K, V, C> IntoIterator for &'a mut TreeMap<K, V, C> where
    C: Compare<K>, 

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V, Forward>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IterMut<'a, K, V, Forward>

Creates an iterator from a value.

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

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.