An ordered map and set implemented as self-balancing binary search trees. The only requirement for the types is that the key implements TotalOrd.

Struct TreeMap

pub struct TreeMap<K, V> {
    priv root: Option<~TreeNode<K, V>>,
    priv length: uint,
}

Struct TreeMapIterator

pub struct TreeMapIterator<'self, K, V> {
    priv stack: ~[&'self ~TreeNode<K, V>],
    priv node: &'self Option<~TreeNode<K, V>>,
}

Lazy forward iterator over a map

Struct TreeSet

pub struct TreeSet<T> {
    priv map: TreeMap<T, ()>,
}

A implementation of the Set trait on top of the TreeMap container. The only requirement is that the type of the elements contained ascribes to the TotalOrd trait.

Struct TreeSetIterator

pub struct TreeSetIterator<'self, T> {
    priv iter: TreeMapIterator<'self, T, ()>,
}

Lazy forward iterator over a set

Implementation of Eq for TreeMap<K, V> where <K: Eq + TotalOrd, V: Eq>

Method eq

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

Method ne

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

Implementation of Ord for TreeMap<K, V> where <K: Ord + TotalOrd, V>

Method lt

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

Method le

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

Method ge

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

Method gt

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

Implementation of Container for TreeMap<K, V> where <K: TotalOrd, V>

Method len

fn len(&self) -> uint

Return the number of elements in the map

Method is_empty

fn is_empty(&self) -> bool

Return true if the map contains no elements

Implementation of Mutable for TreeMap<K, V> where <K: TotalOrd, V>

Method clear

fn clear(&mut self)

Clear the map, removing all key-value pairs.

Implementation of Map<K, V> for TreeMap<K, V> where <K: TotalOrd, V>

Method contains_key

fn contains_key(&self, key: &K) -> bool

Return true if the map contains a value for the specified key

Method find

fn find<'a>(&'a self, key: &K) -> Option<&'a V>

Return a reference to the value corresponding to the key

Method find_mut

fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>

Return a mutable reference to the value corresponding to the key

Method insert

fn insert(&mut self, key: K, value: V) -> bool

Insert a key-value pair into the map. An existing value for a key is replaced by the new value. Return true if the key did not already exist in the map.

Method remove

fn remove(&mut self, key: &K) -> bool

Remove a key-value pair from the map. Return true if the key was present in the map, otherwise false.

Method swap

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

Insert a key-value pair from the map. If the key already had a value present in the map, that value is returned. Otherwise None is returned.

Method pop

fn pop(&mut self, key: &K) -> Option<V>

Removes a key from the map, returning the value at the key if the key was previously in the map.

Implementation for TreeMap<K, V> where <K: TotalOrd, V>

Method new

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

Create an empty TreeMap

Method each_key

fn each_key(&self, f: &fn(&K) -> bool) -> bool

Visit all keys in order

Method each_value

fn each_value<'a>(&'a self, f: &fn(&'a V) -> bool) -> bool

Visit all values in order

Method mutate_values

fn mutate_values(&mut self, f: &fn(&K, &mut V) -> bool) -> bool

Iterate over the map and mutate the contained values

Method each_reverse

fn each_reverse<'a>(&'a self, f: &fn(&'a K, &'a V) -> bool) -> bool

Visit all key-value pairs in reverse order

Method each_key_reverse

fn each_key_reverse(&self, f: &fn(&K) -> bool) -> bool

Visit all keys in reverse order

Method each_value_reverse

fn each_value_reverse(&self, f: &fn(&V) -> bool) -> bool

Visit all values in reverse order

Method iter

fn iter<'a>(&'a self) -> TreeMapIterator<'a, K, V>

Get a lazy iterator over the key-value pairs in the map. Requires that it be frozen (immutable).

Implementation of Iterator<(&'self K, &'self V)> for TreeMapIterator<'self, K, V> where <'self, K, V>

Method next

fn next(&mut self) -> Option<(&'self K, &'self V)>

Advance the iterator to the next node (in order) and return a tuple with a reference to the key and value. If there are no more nodes, return None.

Implementation of Iterator<&'self T> for TreeSetIterator<'self, T> where <'self, T>

Method next

fn next(&mut self) -> Option<&'self T>

Advance the iterator to the next node (in order). If there are no more nodes, return None.

Implementation of Eq for TreeSet<T> where <T: Eq + TotalOrd>

Method eq

fn eq(&self, other: &TreeSet<T>) -> bool

Method ne

fn ne(&self, other: &TreeSet<T>) -> bool

Implementation of Ord for TreeSet<T> where <T: Ord + TotalOrd>

Method lt

fn lt(&self, other: &TreeSet<T>) -> bool

Method le

fn le(&self, other: &TreeSet<T>) -> bool

Method ge

fn ge(&self, other: &TreeSet<T>) -> bool

Method gt

fn gt(&self, other: &TreeSet<T>) -> bool

Implementation of Container for TreeSet<T> where <T: TotalOrd>

Method len

fn len(&self) -> uint

Return the number of elements in the set

Method is_empty

fn is_empty(&self) -> bool

Return true if the set contains no elements

Implementation of Mutable for TreeSet<T> where <T: TotalOrd>

Method clear

fn clear(&mut self)

Clear the set, removing all values.

Implementation of Set<T> for TreeSet<T> where <T: TotalOrd>

Method contains

fn contains(&self, value: &T) -> bool

Return true if the set contains a value

Method insert

fn insert(&mut self, value: T) -> bool

Add a value to the set. Return true if the value was not already present in the set.

Method remove

fn remove(&mut self, value: &T) -> bool

Remove a value from the set. Return true if the value was present in the set.

Method is_disjoint

fn is_disjoint(&self, other: &TreeSet<T>) -> bool

Return true if the set has no elements in common with other. This is equivalent to checking for an empty intersection.

Method is_subset

fn is_subset(&self, other: &TreeSet<T>) -> bool

Return true if the set is a subset of another

Method is_superset

fn is_superset(&self, other: &TreeSet<T>) -> bool

Return true if the set is a superset of another

Method difference

fn difference(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool

Visit the values (in-order) representing the difference

Method symmetric_difference

fn symmetric_difference(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool

Visit the values (in-order) representing the symmetric difference

Method intersection

fn intersection(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool

Visit the values (in-order) representing the intersection

Method union

fn union(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool

Visit the values (in-order) representing the union

Implementation for TreeSet<T> where <T: TotalOrd>

Method new

fn new() -> TreeSet<T>

Create an empty TreeSet

Method iter

fn iter<'a>(&'a self) -> TreeSetIterator<'a, T>

Get a lazy iterator over the values in the set. Requires that it be frozen (immutable).

Method each_reverse

fn each_reverse(&self, f: &fn(&T) -> bool) -> bool

Visit all values in reverse order

Implementation for TreeNode<K, V> where <K: TotalOrd, V>

Method new

fn new(key: K, value: V) -> TreeNode<K, V>

Creates a new tree node.