Struct extended_collections::red_black_tree::RedBlackMap

pub struct RedBlackMap<T, U> { /* fields omitted */ }

An ordered map implemented using an avl tree.

An avl tree is a self-balancing binary search tree that uses a color bit to ensure that the tree remains approximately balanced during insertions and deletions. heights of two child subtrees of any node differ by at most one.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(0, 1);
map.insert(3, 4);

assert_eq!(map[&0], 1);
assert_eq!(map.get(&1), None);
assert_eq!(map.len(), 2);

assert_eq!(map.min(), Some(&0));
assert_eq!(map.ceil(&2), Some(&3));

map[&0] = 2;
assert_eq!(map.remove(&0), Some((0, 2)));
assert_eq!(map.remove(&1), None);

Methods

impl<T, U> RedBlackMap<T, U>

pub fn new() -> Self

Constructs a new, empty RedBlackMap<T, U>.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let map: RedBlackMap<u32, u32> = RedBlackMap::new();

pub fn insert(&mut self, key: T, value: U) -> Option<(T, U)> where     T: Ord,

Inserts a key-value pair into the map. If the key already exists in the map, it will return and replace the old key-value pair.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
assert_eq!(map.insert(1, 1), None);
assert_eq!(map.get(&1), Some(&1));
assert_eq!(map.insert(1, 2), Some((1, 1)));
assert_eq!(map.get(&1), Some(&2));

pub fn remove<V: ?Sized>(&mut self, key: &V) -> Option<(T, U)> where     T: Borrow<V>,     V: Ord,

Removes a key-value pair from the map. If the key exists in the map, it will return the associated key-value pair. Otherwise it will return None.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
assert_eq!(map.remove(&1), Some((1, 1)));
assert_eq!(map.remove(&1), None);

pub fn contains_key<V: ?Sized>(&self, key: &V) -> bool where     T: Borrow<V>,     V: Ord,

Checks if a key exists in the map.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
assert!(!map.contains_key(&0));
assert!(map.contains_key(&1));

pub fn get<V: ?Sized>(&self, key: &V) -> Option<&U> where     T: Borrow<V>,     V: Ord,

Returns an immutable reference to the value associated with a particular key. It will return None if the key does not exist in the map.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
assert_eq!(map.get(&0), None);
assert_eq!(map.get(&1), Some(&1));

pub fn get_mut<V: ?Sized>(&mut self, key: &V) -> Option<&mut U> where     T: Borrow<V>,     V: Ord,

Returns a mutable reference to the value associated with a particular key. Returns None if such a key does not exist.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
*map.get_mut(&1).unwrap() = 2;
assert_eq!(map.get(&1), Some(&2));

pub fn len(&self) -> usize

Returns the number of elements in the map.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
assert_eq!(map.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the map is empty.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let map: RedBlackMap<u32, u32> = RedBlackMap::new();
assert!(map.is_empty());

pub fn clear(&mut self)

Clears the map, removing all values.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
map.insert(2, 2);
map.clear();
assert_eq!(map.is_empty(), true);

pub fn floor<V: ?Sized>(&self, key: &V) -> Option<&T> where     T: Borrow<V>,     V: Ord,

Returns a key in the map that is less than or equal to a particular key. Returns None if such a key does not exist.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
assert_eq!(map.floor(&0), None);
assert_eq!(map.floor(&2), Some(&1));

pub fn ceil<V: ?Sized>(&self, key: &V) -> Option<&T> where     T: Borrow<V>,     V: Ord,

Returns a key in the map that is greater than or equal to a particular key. Returns None if such a key does not exist.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
assert_eq!(map.ceil(&0), Some(&1));
assert_eq!(map.ceil(&2), None);

pub fn min(&self) -> Option<&T> where     T: Ord,

Returns the minimum key of the map. Returns None if the map is empty.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
map.insert(3, 3);
assert_eq!(map.min(), Some(&1));

pub fn max(&self) -> Option<&T> where     T: Ord,

Returns the maximum key of the map. Returns None if the map is empty.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
map.insert(3, 3);
assert_eq!(map.max(), Some(&3));

pub fn iter(&self) -> RedBlackMapIter<T, U>

Returns an iterator over the map. The iterator will yield key-value pairs using in-order traversal.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
map.insert(2, 2);

let mut iterator = map.iter();
assert_eq!(iterator.next(), Some((&1, &1)));
assert_eq!(iterator.next(), Some((&2, &2)));
assert_eq!(iterator.next(), None);

pub fn iter_mut(&mut self) -> RedBlackMapIterMut<T, U>

Returns a mutable iterator over the map. The iterator will yield key-value pairs using in-order traversal.

Examples

use extended_collections::red_black_tree::RedBlackMap;

let mut map = RedBlackMap::new();
map.insert(1, 1);
map.insert(2, 2);

for (key, value) in &mut map {
    *value += 1;
}

let mut iterator = map.iter_mut();
assert_eq!(iterator.next(), Some((&1, &mut 2)));
assert_eq!(iterator.next(), Some((&2, &mut 3)));
assert_eq!(iterator.next(), None);

Trait Implementations

impl<T, U> IntoIterator for RedBlackMap<T, U>

type Item = (T, U)

The type of the elements being iterated over.

type IntoIter = RedBlackMapIntoIter<T, U>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T, U> IntoIterator for &'a RedBlackMap<T, U> where     T: 'a,     U: 'a,

type Item = (&'a T, &'a U)

The type of the elements being iterated over.

type IntoIter = RedBlackMapIter<'a, T, U>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T, U> IntoIterator for &'a mut RedBlackMap<T, U> where     T: 'a,     U: 'a,

type Item = (&'a T, &'a mut U)

The type of the elements being iterated over.

type IntoIter = RedBlackMapIterMut<'a, T, U>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, U> Default for RedBlackMap<T, U>

fn default() -> Self

Returns the "default value" for a type.

impl<'a, T, U, V: ?Sized> Index<&'a V> for RedBlackMap<T, U> where     T: Borrow<V>,     V: Ord,

type Output = U

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<'a, T, U, V: ?Sized> IndexMut<&'a V> for RedBlackMap<T, U> where     T: Borrow<V>,     V: Ord,

fn index_mut(&mut self, key: &V) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.