Struct rb_tree::RBMap[][src]

pub struct RBMap<K: PartialOrd, V> { /* fields omitted */ }
Expand description

A map implemented using a red black tree to store key-value pairs.

Implementations

impl<K: PartialOrd, V> RBMap<K, V>[src]

pub fn new() -> RBMap<K, V>[src]

Creates and returns a new, empty RBMap

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert("Hello", "World");
assert_eq!(map.remove(&"Hello").unwrap(), "World");

pub fn keyset(&self) -> RBTree<&K>[src]

Creates an RBTree set of the keys contained in this map.

Example:

use rb_tree::{RBMap, RBTree};

let mut map = RBMap::new();
map.insert("Hello", "World");
map.insert("Foo", "Bar");
let kset = map.keyset();
assert!(kset.contains(&&"Hello"));
assert!(kset.contains(&&"Foo"));
assert!(!kset.contains(&&"Bar"));

pub fn into_keyset(self) -> RBTree<K>[src]

Creates a set from the keys in this map.

Example:

use rb_tree::{RBMap, RBTree};

let mut map = RBMap::new();
map.insert("Hello", "World");
map.insert("Foo", "Bar");
let kset = map.into_keyset();
assert!(kset.contains(&"Hello"));
assert!(kset.contains(&"Foo"));
assert!(!kset.contains(&"Bar"));

pub fn clear(&mut self)[src]

Clears all entries from the RBMap

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert("Hello", "world");
map.insert("Foo", "bar");
assert_eq!(map.len(), 2);
map.clear();
assert_eq!(map.len(), 0);
assert!(map.remove(&"Hello").is_none());

pub fn contains_key(&self, key: &K) -> bool[src]

Returns true if the map contains an entry for key, false otherwise.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert!(!map.contains_key(&"Hello"));
map.insert("Hello", "world");
assert!(map.contains_key(&"Hello"));

pub fn drain(&mut self) -> Drain<K, V>

Notable traits for Drain<K, V>

impl<K: PartialOrd, V> Iterator for Drain<K, V> type Item = (K, V);
[src]

Clears the map and returns an iterator over all key-value pairs that were contained in the order of their keys’ PartialOrd order.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert("Hello", "world");
map.insert("Foo", "bar");
let mut drain = map.drain();
assert_eq!(drain.next().unwrap(), ("Foo", "bar"));
assert_eq!(drain.next().unwrap(), ("Hello", "world"));
assert!(drain.next().is_none());

pub fn get(&self, key: &K) -> Option<&V>[src]

Returns an option containing a reference to the value associated with this key, or none if this key does not have an associated value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert!(map.get(&"Hello").is_none());
map.insert("Hello", "world");
assert_eq!(map.get(&"Hello").unwrap(), &"world");

pub fn get_pair(&self, key: &K) -> Option<(&K, &V)>[src]

Returns an option containing a reference to the key-value pair associated with this key, or none if this key does not have an associated value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert!(map.get(&"Hello").is_none());
map.insert("Hello", "world");
assert_eq!(map.get_pair(&"Hello").unwrap(), (&"Hello", &"world"));

pub fn get_pair_mut(&mut self, key: &K) -> Option<(&K, &mut V)>[src]

Returns an option containing a reference to the key-value pair associated with this key of which the value is mutable. Returns none if this key does not have an associated value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert!(map.get(&"Hello").is_none());
map.insert("Hello", "world");
assert_eq!(map.get_pair(&"Hello").unwrap(), (&"Hello", &"world"));

pub fn get_mut(&mut self, key: &K) -> Option<&mut V>[src]

Returns an option containing a mutable reference to the value associated with this key, or none if this key does not have an associated value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert!(map.get(&"Hello").is_none());
map.insert("Hello", "world");
*map.get_mut(&"Hello").unwrap() = "world!";
assert_eq!(map.get(&"Hello").unwrap(), &"world!");

pub fn peek(&self) -> Option<&V>[src]

Returns an option containing a reference to the value associated with the key that has the smallest PartialOrd value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.peek(), None);

map.insert(5, "Hello");
map.insert(2, "World");
map.insert(7, "Foo");
map.insert(6, "Bar");

assert_eq!(map.peek().unwrap(), &"World");

pub fn peek_back(&self) -> Option<&V>[src]

Returns an option containing a reference to the value associated with the key that has the largest PartialOrd value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.peek_back(), None);

map.insert(5, "Hello");
map.insert(2, "World");
map.insert(7, "Foo");
map.insert(6, "Bar");

assert_eq!(map.peek_back().unwrap(), &"Foo");

pub fn peek_pair(&self) -> Option<(&K, &V)>[src]

Returns an option containing a pair with a reference to the key with the smallest PartialOrd value and a reference to its associated value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.peek_pair(), None);

map.insert(5, "Hello");
map.insert(2, "World");
map.insert(7, "Foo");
map.insert(6, "Bar");

assert_eq!(map.peek_pair().unwrap(), (&2, &"World"));

pub fn peek_pair_back(&self) -> Option<(&K, &V)>[src]

Returns an option containing a pair with a reference to the key with the largest PartialOrd value and a reference to its associated value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.peek_pair_back(), None);

map.insert(5, "Hello");
map.insert(2, "World");
map.insert(7, "Foo");
map.insert(6, "Bar");

assert_eq!(map.peek_pair_back().unwrap(), (&7, &"Foo"));

pub fn insert(&mut self, key: K, val: V) -> Option<(K, V)>[src]

Inserts a value to associate with the given key into the map, returning the previously-stored key-value pair if one existed, None otherwise.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert("Hello", "world");
map.insert("Foo", "bar");
assert_eq!(map.len(), 2);

pub fn is_empty(&self) -> bool[src]

Returns true if there are no key-value pairs stored in this RBMap, false otherwise.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert!(map.is_empty());
map.insert(1, 2);
assert!(!map.is_empty());

pub fn len(&self) -> usize[src]

Returns the number of key-value pairs stored in this RBMap.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.len(), 0);
map.insert(1, 1);
assert_eq!(map.len(), 1);
map.insert(2, 4);
assert_eq!(map.len(), 2);
map.remove(&2);
assert_eq!(map.len(), 1);

pub fn remove(&mut self, key: &K) -> Option<V>[src]

Removes the key-value pair associated with key, if one exists, and returns the associated value, or None if the pair did not exist.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert!(map.remove(&2).is_none());
map.insert(2, 4);
assert_eq!(map.remove(&2).unwrap(), 4);

pub fn remove_entry(&mut self, key: &K) -> Option<(K, V)>[src]

Removes the key-value pair associated with key, if one exists, and returns it, or None if the pair did not exist.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert!(map.remove_entry(&2).is_none());
map.insert(2, 4);
assert_eq!(map.remove_entry(&2).unwrap(), (2, 4));

pub fn pop(&mut self) -> Option<V>[src]

Removes the pair associated with the key that has the smallest PartialOrd value and returns the associated value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.pop(), None);

map.insert(5, "Hello");
map.insert(2, "World");
map.insert(7, "Foo");
map.insert(6, "Bar");

assert_eq!(map.pop().unwrap(), "World");
assert_eq!(map.pop().unwrap(), "Hello");

pub fn pop_back(&mut self) -> Option<V>[src]

Removes the pair associated with the key that has the largest PartialOrd value and returns the associated value.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.pop(), None);

map.insert(5, "Hello");
map.insert(2, "World");
map.insert(7, "Foo");
map.insert(6, "Bar");

assert_eq!(map.pop_back().unwrap(), "Foo");
assert_eq!(map.pop_back().unwrap(), "Bar");

pub fn pop_pair(&mut self) -> Option<(K, V)>[src]

Removes the pair associated with the key that has the smallest PartialOrd value and returns it.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.pop_pair(), None);

map.insert(5, "Hello");
map.insert(2, "World");
map.insert(7, "Foo");
map.insert(6, "Bar");

assert_eq!(map.pop_pair().unwrap(), (2, "World"));
assert_eq!(map.pop_pair().unwrap(), (5, "Hello"));

pub fn pop_pair_back(&mut self) -> Option<(K, V)>[src]

Removes the pair associated with the key that has the smallest PartialOrd value and returns it.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
assert_eq!(map.pop_pair_back(), None);

map.insert(5, "Hello");
map.insert(2, "World");
map.insert(7, "Foo");
map.insert(6, "Bar");

assert_eq!(map.pop_pair_back().unwrap(), (7, "Foo"));
assert_eq!(map.pop_pair_back().unwrap(), (6, "Bar"));

pub fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, logic: F)[src]

Removes all key-value pairs that do not return true for the provided method.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert(1, 1);
map.insert(2, 4);
map.insert(3, 9);
map.retain(|_, v| *v % 2 == 0);

let mut pairs = map.drain();
assert_eq!(pairs.next().unwrap(), (2, 4));
assert_eq!(pairs.next(), None);

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

Notable traits for Iter<'a, K, V>

impl<'a, K: PartialOrd, V> Iterator for Iter<'a, K, V> type Item = (&'a K, &'a V);
[src]

An iterator that visits all key-value pairs in their key’s partialord order.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert(1, 1);
map.insert(2, 4);
map.insert(3, 9);

let mut pairs = map.iter();
assert_eq!(pairs.next().unwrap(), (&1, &1));
assert_eq!(pairs.next().unwrap(), (&2, &4));
assert_eq!(pairs.next().unwrap(), (&3, &9));
assert_eq!(pairs.next(), None);

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

Notable traits for IterMut<'a, K, V>

impl<'a, K: PartialOrd, V> Iterator for IterMut<'a, K, V> type Item = (&'a K, &'a mut V);
[src]

An iterator that visits all key-value pairs in their key’s partialord order and presents the value only as mutable.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert(1, 1);
map.insert(2, 4);
map.insert(3, 9);

map.iter_mut().for_each(|(_, v)| *v *= 2);

let mut pairs = map.iter();
assert_eq!(pairs.next().unwrap(), (&1, &2));
assert_eq!(pairs.next().unwrap(), (&2, &8));
assert_eq!(pairs.next().unwrap(), (&3, &18));
assert_eq!(pairs.next(), None);

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

Notable traits for Values<'a, K, V>

impl<'a, K: PartialOrd, V> Iterator for Values<'a, K, V> type Item = &'a V;
[src]

An iterator that visits all values in their key’s partialord order.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert(1, 1);
map.insert(2, 4);
map.insert(3, 9);

let mut vals = map.values();
assert_eq!(*vals.next().unwrap(), 1);
assert_eq!(*vals.next().unwrap(), 4);
assert_eq!(*vals.next().unwrap(), 9);
assert_eq!(vals.next(), None);

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

Notable traits for ValuesMut<'a, K, V>

impl<'a, K: PartialOrd, V> Iterator for ValuesMut<'a, K, V> type Item = &'a mut V;
[src]

An iterator that visits all values in their key’s partialord order and presents them as mutable.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert(1, 1);
map.insert(2, 4);
map.insert(3, 9);

map.values_mut().for_each(|v| *v *= 2);

let mut vals = map.values();
assert_eq!(*vals.next().unwrap(), 2);
assert_eq!(*vals.next().unwrap(), 8);
assert_eq!(*vals.next().unwrap(), 18);
assert_eq!(vals.next(), None);

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

Notable traits for Keys<'a, K, V>

impl<'a, K: PartialOrd, V> Iterator for Keys<'a, K, V> type Item = &'a K;
[src]

An iterator that visits all keys in their partialord order.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();
map.insert(1, 1);
map.insert(2, 4);
map.insert(3, 9);

let mut keys = map.keys();
assert_eq!(*keys.next().unwrap(), 1);
assert_eq!(*keys.next().unwrap(), 2);
assert_eq!(*keys.next().unwrap(), 3);
assert_eq!(keys.next(), None);

pub fn entry(&mut self, key: K) -> Entry<'_, K, V>[src]

Provides an interface for ensuring values are allocated to the given key.

Example:

use rb_tree::RBMap;

let mut map = RBMap::new();

let val = map.entry(1).or_insert(2);
*val = 3;
assert_eq!(*map.get(&1).unwrap(), 3);

impl<K: PartialOrd, V: PartialOrd> RBMap<K, V>[src]

pub fn valueset(&self) -> RBTree<&V>[src]

Creates an RBTree set of the values contained in this map.

Example:

use rb_tree::{RBMap, RBTree};

let mut map = RBMap::new();
map.insert("Hello", "World");
map.insert("Foo", "Bar");
let vset = map.valueset();
assert!(vset.contains(&&"World"));
assert!(vset.contains(&&"Bar"));
assert!(!vset.contains(&&"Foo"));

pub fn into_sets(self) -> (RBTree<K>, RBTree<V>)[src]

Creates a set of keys and a set of values from the given map.

Note: any mapping information is lost when this operation is performed.

Example:

use rb_tree::{RBMap, RBTree};

let mut map = RBMap::new();
map.insert("Hello", "World");
map.insert("Foo", "Bar");
let (kset, vset) = map.into_sets();
assert!(kset.contains(&"Hello"));
assert!(kset.contains(&"Foo"));
assert!(!kset.contains(&"Bar"));
assert!(vset.contains(&"World"));
assert!(vset.contains(&"Bar"));
assert!(!vset.contains(&"Foo"));

pub fn into_valueset(self) -> RBTree<V>[src]

Creates an RBTree set from the values contained in this map.

Example:

use rb_tree::{RBMap, RBTree};

let mut map = RBMap::new();
map.insert("Hello", "World");
map.insert("Foo", "Bar");
let vset = map.into_valueset();
assert!(vset.contains(&"World"));
assert!(vset.contains(&"Bar"));
assert!(!vset.contains(&"Foo"));

Trait Implementations

impl<K: Clone + PartialOrd, V: Clone> Clone for RBMap<K, V>[src]

fn clone(&self) -> RBMap<K, V>[src]

Returns a copy of the value. Read more

fn clone_from(&mut self, source: &Self)1.0.0[src]

Performs copy-assignment from source. Read more

impl<K: PartialOrd + Debug, V: Debug> Debug for RBMap<K, V>[src]

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

Formats the value using the given formatter. Read more

impl<K: PartialOrd, V> Default for RBMap<K, V>[src]

fn default() -> Self[src]

Returns the “default value” for a type. Read more

impl<K: PartialOrd + Debug, V: Debug> Display for RBMap<K, V>[src]

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

Formats the value using the given formatter. Read more

impl<'a, K: PartialOrd + Copy + 'a, V: Copy + 'a> Extend<(&'a K, &'a V)> for RBMap<K, V>[src]

fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I)[src]

Extends a collection with the contents of an iterator. Read more

fn extend_one(&mut self, item: A)[src]

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)[src]

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

impl<K: PartialOrd, V> Extend<(K, V)> for RBMap<K, V>[src]

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)[src]

Extends a collection with the contents of an iterator. Read more

fn extend_one(&mut self, item: A)[src]

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)[src]

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

impl<K: PartialOrd, V> FromIterator<(K, V)> for RBMap<K, V>[src]

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self[src]

Creates a value from an iterator. Read more

impl<K: PartialOrd, V> IntoIterator for RBMap<K, V>[src]

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>

Notable traits for IntoIter<K, V>

impl<K: PartialOrd, V> Iterator for IntoIter<K, V> type Item = (K, V);
[src]

Creates an iterator from a value. Read more

Auto Trait Implementations

impl<K, V> RefUnwindSafe for RBMap<K, V> where
    K: RefUnwindSafe,
    V: RefUnwindSafe

impl<K, V> Send for RBMap<K, V> where
    K: Send,
    V: Send

impl<K, V> Sync for RBMap<K, V> where
    K: Sync,
    V: Sync

impl<K, V> Unpin for RBMap<K, V> where
    K: Unpin,
    V: Unpin

impl<K, V> UnwindSafe for RBMap<K, V> where
    K: UnwindSafe,
    V: UnwindSafe

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

pub fn type_id(&self) -> TypeId[src]

Gets the TypeId of self. Read more

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

pub fn borrow(&self) -> &T[src]

Immutably borrows from an owned value. Read more

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

pub fn borrow_mut(&mut self) -> &mut T[src]

Mutably borrows from an owned value. Read more

impl<T> From<T> for T[src]

pub fn from(t: T) -> T[src]

Performs the conversion.

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

pub fn into(self) -> U[src]

Performs the conversion.

impl<T> ToOwned for T where
    T: Clone
[src]

type Owned = T

The resulting type after obtaining ownership.

pub fn to_owned(&self) -> T[src]

Creates owned data from borrowed data, usually by cloning. Read more

pub fn clone_into(&self, target: &mut T)[src]

🔬 This is a nightly-only experimental API. (toowned_clone_into)

recently added

Uses borrowed data to replace owned data, usually by cloning. Read more

impl<T> ToString for T where
    T: Display + ?Sized
[src]

pub default fn to_string(&self) -> String[src]

Converts the given value to a String. Read more

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>[src]

Performs the conversion.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.

pub fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>[src]

Performs the conversion.