Struct TreeMap

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

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]);

Implementations

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

pub 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);

pub 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());

pub 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());

pub 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));

pub 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));

pub 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);

pub 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,

pub 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);

pub 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));

pub 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,

pub 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));

pub 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));

pub 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"));

pub 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"));

pub 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);

pub 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);

pub 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: Debug + Ord, V: Debug> Debug for TreeMap<K, V>

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

Formats the value using the given formatter.

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

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

Returns the “default value” for a type.

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.

impl<'a, K, Q, V> Index<&'a Q> for TreeMap<K, V>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

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 = Iter<'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: 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.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

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

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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

Tests less than (for self and other) and is used by the < operator.

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

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

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

Tests greater than (for self and other) and is used by the > operator.

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

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

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