Struct immutable_map::map::TreeMap

pub struct TreeMap<K, V> { /* fields omitted */ }

An immutable key-value map based on weight-balanced binary tree. See https://yoichihirai.com/bst.pdf for the balancing algorithm.

Examples

use immutable_map::TreeMap;

let map_0 = TreeMap::new();

// `insert` returns new copies with the given key and value inserted, and does not change
// the original map
let map_1 = map_0.insert(3, "Three");
let map_2 = map_1.insert(4, "Four");

assert_eq!(false, map_1.contains_key(&4));
assert_eq!(true, map_2.contains_key(&4));

assert_eq!("Four", map_2[&4]);

Methods

impl<K, V> TreeMap<K, V>

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

Makes a new empty TreeMap

Examples

use immutable_map::TreeMap;

let map = TreeMap::new();
let new_map = map.insert("One", 1);

fn len(&self) -> usize

Returns the number of elements in the map.

Examples

use immutable_map::TreeMap;

let map = TreeMap::new().insert(1, "One").insert(2, "Two");
assert_eq!(2, map.len());

fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Examples

use immutable_map::TreeMap;

let empty_map = TreeMap::new();
let new_map = empty_map.insert(1, "One");

assert_eq!(true, empty_map.is_empty());
assert_eq!(false, new_map.is_empty());

fn iter<'r>(&'r self) -> TreeMapIter<'r, K, V>

Gets an iterator over the entries of the map, sorted by key.

Examples

use immutable_map::TreeMap;

let map = TreeMap::new().insert(2, "Two").insert(3, "Three").insert(1, "One");

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

let (first_key, first_value) = map.iter().next().unwrap();
assert_eq!((1, "One"), (*first_key, *first_value));

fn rev_iter<'r>(&'r self) -> TreeMapRevIter<'r, K, V>

Gets an iterator over the entries of the map, sorted by key in decreasing order.

Examples

use immutable_map::TreeMap;

let map = TreeMap::new().insert(2, "Two").insert(3, "Three").insert(1, "One");

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

let (first_key, first_value) = map.rev_iter().next().unwrap();
assert_eq!((3, "Three"), (*first_key, *first_value));

fn keys<'r>(&'r self) -> TreeMapKeys<'r, K, V>

Gets an iterator over the keys of the map, in increasing order.

Examples

use immutable_map::TreeMap;

let map = TreeMap::new().insert(2, "Two").insert(3, "Three").insert(1, "One");

for key in map.keys() {
    println!("{}", key);
}

let first_key = map.keys().next().unwrap();
assert_eq!(1, *first_key);

fn values<'r>(&'r self) -> TreeMapValues<'r, K, V>

Gets an iterator over the values of the map, ordered by key.

Examples

use immutable_map::TreeMap;

let map = TreeMap::new().insert(2, "Two").insert(3, "Three").insert(1, "One");

for value in map.values() {
    println!("{}", value);
}

let first_value = map.values().next().unwrap();
assert_eq!("One", *first_value);

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

fn get<Q: ?Sized + Ord>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>

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 immutable_map::TreeMap;

let map = TreeMap::new().insert(1, "One");

assert_eq!(map.get(&1), Some(&"One"));
assert_eq!(map.get(&2), None);

fn contains_key<Q: ?Sized + Ord>(&self, key: &Q) -> bool where K: Borrow<Q>

Returns true if the map contains given 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 immutable_map::TreeMap;

let map = TreeMap::new().insert(1, "One");

assert_eq!(true, map.contains_key(&1));
assert_eq!(false, map.contains_key(&2));

fn range<'r, Q: Ord>(&'r self,
                     min: Bound<&Q>,
                     max: Bound<&Q>)
                     -> TreeMapRange<'r, K, V> where K: Borrow<Q>

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

use immutable_map::TreeMap;
use immutable_map::Bound::*;

let map = TreeMap::new().insert(8, "Eight").insert(3, "Three").insert(5, "Five");

for (key, value) in map.range(Included(&4), Included(&8)) {
    println!("{}: {}", key, value);
}

let pairs: Vec<_> = map.range(Included(&4), Included(&8)).map(|(k, v)| (*k, *v)).collect();

assert_eq!(pairs, [(5, "Five"), (8, "Eight")]);

impl<K, V> TreeMap<K, V> where K: Clone + Ord, V: Clone

fn insert(&self, key: K, value: V) -> TreeMap<K, V>

Return a new copy of TreeMap with the key-value pair inserted

If the map already has the key, the key-value pair is replaced in the new map

Examples

use immutable_map::TreeMap;

let map = TreeMap::new();

assert_eq!(false, map.contains_key(&1));
assert_eq!(None, map.get(&1));

let new_map = map.insert(1, "One");

assert_eq!(true, new_map.contains_key(&1));
assert_eq!(Some(&"One"), new_map.get(&1));

fn insert_if_absent(&self, key: K, value: V) -> Option<TreeMap<K, V>>

Return a new copy of TreeMap with the key-value pair inserted.

Returns None if the map already has the key

Examples

use immutable_map::TreeMap;

let map = TreeMap::new().insert(2, "Two").insert(3, "Three");

assert_eq!(None, map.insert_if_absent(2, "Zwei"));

let new_map = map.insert_if_absent(1, "One").unwrap();

assert_eq!(Some(&"One"), new_map.get(&1));

fn update<Q: ?Sized + Ord, F>(&self, key: &Q, f: F) -> Option<TreeMap<K, V>> where K: Borrow<Q>, F: FnMut(&V) -> V

Find the map with given key, and if the key is found, udpate the value with the provided function f, and return the new map. Returns None if the map already has the key.

When the key is found in the map, function f is called, and the value is updated with the return value of f.

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 immutable_map::TreeMap;

let map = TreeMap::new().insert("Two".to_string(), 2).insert("Three".to_string(), 3);

// returns `None` because the key "One" is not in the map
assert_eq!(None, map.update("One", |v| v+1));

let map_1 = map.update("Two", |v| v+10).unwrap();
// the value is updated
assert_eq!(Some(&12), map_1.get("Two"));

fn insert_or_update<F>(&self, key: K, value: V, f: F) -> TreeMap<K, V> where F: FnMut(&V) -> V

Find the map with given key, and if the key is found, udpate the value with the provided function f, and return the new map. If the key is not found, insert the key-value pair to the map and return it.

Examples

use immutable_map::TreeMap;

let map = TreeMap::new().insert("One", 1).insert("Three", 3);

// The new pair ("Two", 2) is inserted
let map_1 = map.insert_or_update("Two", 2, |v| v + 10);
assert_eq!(Some(&2), map_1.get("Two"));

// The ("Two", 2) pair is updated to ("Two", 2 + 10)
let map_2 = map_1.insert_or_update("Two", 2, |v| v + 10);
assert_eq!(Some(&12), map_2.get("Two"));

fn delete_min(&self) -> Option<(TreeMap<K, V>, (&K, &V))>

Remove the smallest key-value pair from the map, and returns the modified copy.

Returns None if the original map was empty.

Examples

use immutable_map::TreeMap;

let empty_map = TreeMap::new();
assert_eq!(None, empty_map.delete_min());

let map = empty_map.insert(2, "Two").insert(3, "Three").insert(1, "One");

let (new_map, pair) = map.delete_min().unwrap();

assert_eq!(None, new_map.get(&1));
assert_eq!((&1, &"One"), pair);

fn delete_max(&self) -> Option<(TreeMap<K, V>, (&K, &V))>

Remove the largest key-value pair from the map, and returns the modified copy.

Returns None if the original map was empty.

Examples

use immutable_map::TreeMap;

let empty_map = TreeMap::new();
assert_eq!(None, empty_map.delete_max());

let map = empty_map.insert(2, "Two").insert(3, "Three").insert(1, "One");

let (new_map, pair) = map.delete_max().unwrap();

assert_eq!(None, new_map.get(&3));
assert_eq!((&3, &"Three"), pair);

fn remove<Q: ?Sized + Ord>(&self, key: &Q) -> Option<(TreeMap<K, V>, &V)> where K: Borrow<Q>

Remove the key from the map

Returns None if the original map did not contain 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 immutable_map::TreeMap;

let empty_map = TreeMap::new();
assert_eq!(None, empty_map.remove(&2));

let map = empty_map.insert(2, "Two").insert(3, "Three").insert(1, "One");

let (new_map, pair) = map.remove(&2).unwrap();

assert_eq!(None, new_map.get(&2));
assert_eq!(&"Two", pair);

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Returns the "default value" for a type.

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

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

Formats the value using the given formatter.

impl<'r, K: Ord, V> IntoIterator for &'r TreeMap<K, V>

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

The type of the elements being iterated over.

type IntoIter = TreeMapIter<'r, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> TreeMapIter<'r, K, V>

Creates an iterator from a value.

impl<K: PartialEq, 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, V: Eq> Eq for TreeMap<K, V>

impl<K: PartialOrd, 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<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for TreeMap<K, V> where K: Borrow<Q>,
        Q: Ord

type Output = V

The returned type after indexing

fn index(&self, key: &Q) -> &V

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

impl<K: Ord + Clone, V: Clone> FromIterator<(K, V)> for TreeMap<K, V>

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

Creates a value from an iterator.