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

pub struct Map<K, V, C = Natural<K>> where
    C: Compare<K>,  { /* fields omitted */ }

An ordered map based on a binary search tree.

The behavior of this map is undefined if a key's ordering relative to any other key changes while the key is in the map. This is normally only possible through Cell, RefCell, or unsafe code.

Methods

`impl<K, V> Map<K, V> where K: Ord,`
[src]

`fn new() -> Self`

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

Examples

let mut map = tree::Map::new();

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

let mut it = map.iter();
assert_eq!(it.next(), Some((&1, &"a")));
assert_eq!(it.next(), Some((&2, &"b")));
assert_eq!(it.next(), Some((&3, &"c")));
assert_eq!(it.next(), None);

`impl<K, V, C> Map<K, V, C> where C: Compare<K>,`
[src]

`fn with_cmp(cmp: C) -> Self`

Creates an empty map ordered according to the given comparator.

Examples

use compare::{Compare, natural};

let mut map = tree::Map::with_cmp(natural().rev());

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

let mut it = map.iter();
assert_eq!(it.next(), Some((&3, &"c")));
assert_eq!(it.next(), Some((&2, &"b")));
assert_eq!(it.next(), Some((&1, &"a")));
assert_eq!(it.next(), None);

`fn is_empty(&self) -> bool`

Checks if the map is empty.

Examples

let mut map = tree::Map::new();
assert!(map.is_empty());

map.insert(2, "b");
assert!(!map.is_empty());

`fn len(&self) -> usize`

Returns the number of entries in the map.

Examples

let mut map = tree::Map::new();
assert_eq!(map.len(), 0);

map.insert(2, "b");
assert_eq!(map.len(), 1);

`fn cmp(&self) -> &C`

Returns a reference to the map's comparator.

Examples

use compare::{Compare, natural};

let map: tree::Map<i32, &str> = tree::Map::new();
assert!(map.cmp().compares_lt(&1, &2));

let map: tree::Map<i32, &str, _> = tree::Map::with_cmp(natural().rev());
assert!(map.cmp().compares_gt(&1, &2));

`fn clear(&mut self)`

Removes all entries from the map.

Examples

let mut map = tree::Map::new();

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

assert_eq!(map.len(), 3);
assert_eq!(map.iter().next(), Some((&1, &"a")));

map.clear();

assert_eq!(map.len(), 0);
assert_eq!(map.iter().next(), None);

`fn insert(&mut self, key: K, value: V) -> Option<V>`

Inserts an entry into the map, returning the previous value, if any, associated with the key.

Examples

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

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

Removes and returns the entry whose key is equal to the given key, returning None if the map does not contain the key.

Examples

let mut map = tree::Map::new();

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

assert_eq!(map.len(), 3);
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.remove(&1), Some((1, "a")));

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

`fn entry(&mut self, key: K) -> Entry<K, V>`

Returns the map's entry corresponding to the given key.

Examples

let mut counts = tree::Map::new();

for s in vec!["a", "b", "a", "c", "a", "b"] {
    *counts.entry(s).or_insert(0) += 1;
}

assert_eq!(counts[&"a"], 3);
assert_eq!(counts[&"b"], 2);
assert_eq!(counts[&"c"], 1);

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

Checks if the map contains the given key.

Examples

let mut map = tree::Map::new();
assert!(!map.contains_key(&1));
map.insert(1, "a");
assert!(map.contains_key(&1));

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

Returns a reference to the value associated with the given key, or None if the map does not contain the key.

Examples

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

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

Returns a mutable reference to the value associated with the given key, or None if the map does not contain the key.

Examples

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

{
    let value = map.get_mut(&1).unwrap();
    assert_eq!(*value, "a");
    *value = "b";
}

assert_eq!(map.get(&1), Some(&"b"));

`fn max(&self) -> Option<(&K, &V)>`

Returns a reference to the map's maximum key and a reference to its associated value, or None if the map is empty.

Examples

let mut map = tree::Map::new();
assert_eq!(map.max(), None);

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

assert_eq!(map.max(), Some((&3, &"c")));

`fn max_mut(&mut self) -> Option<(&K, &mut V)>`

Returns a reference to the map's maximum key and a mutable reference to its associated value, or None if the map is empty.

Examples

let mut map = tree::Map::new();
assert_eq!(map.max(), None);

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

{
    let max = map.max_mut().unwrap();
    assert_eq!(max, (&3, &mut "c"));
    *max.1 = "cc";
}

assert_eq!(map.max(), Some((&3, &"cc")));

`fn remove_max(&mut self) -> Option<(K, V)>`

Removes the map's maximum key and returns it and its associated value, or None if the map is empty.

Examples

let mut map = tree::Map::new();
assert_eq!(map.remove_max(), None);

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

assert_eq!(map.remove_max(), Some((3, "c")));

`fn max_entry(&mut self) -> Option<OccupiedEntry<K, V>>`

Returns the map's entry corresponding to its maximum key.

Examples

let mut map = tree::Map::new();
assert!(map.max_entry().is_none());

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

{
    let mut e = map.max_entry().unwrap();
    assert_eq!(*e.key(), 3);
    assert_eq!(e.insert("cc"), "c");
}

assert_eq!(map[&3], "cc");

`fn min(&self) -> Option<(&K, &V)>`

Returns a reference to the map's minimum key and a reference to its associated value, or None if the map is empty.

Examples

let mut map = tree::Map::new();
assert_eq!(map.min(), None);

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

assert_eq!(map.min(), Some((&1, &"a")));

`fn min_mut(&mut self) -> Option<(&K, &mut V)>`

Returns a reference to the map's minimum key and a mutable reference to its associated value, or None if the map is empty.

Examples

let mut map = tree::Map::new();
assert_eq!(map.min(), None);

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

{
    let min = map.min_mut().unwrap();
    assert_eq!(min, (&1, &mut "a"));
    *min.1 = "aa";
}

assert_eq!(map.min(), Some((&1, &"aa")));

`fn remove_min(&mut self) -> Option<(K, V)>`

Removes the map's minimum key and returns it and its associated value, or None if the map is empty.

Examples

let mut map = tree::Map::new();
assert_eq!(map.remove_min(), None);

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

assert_eq!(map.remove_min(), Some((1, "a")));

`fn min_entry(&mut self) -> Option<OccupiedEntry<K, V>>`

Returns the map's entry corresponding to its minimum key.

Examples

let mut map = tree::Map::new();
assert!(map.min_entry().is_none());

map.insert(2, "b");
map.insert(1, "a");
map.insert(3, "c");

{
    let mut e = map.min_entry().unwrap();
    assert_eq!(*e.key(), 1);
    assert_eq!(e.insert("aa"), "a");
}

assert_eq!(map[&1], "aa");

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

Returns a reference to the predecessor of the given key and a reference to its associated value, or None if no such key is present in the map.

If inclusive is false, this method finds the greatest key that is strictly less than the given key. If inclusive is true, this method finds the greatest key that is less than or equal to the given key.