An ordered map and set implemented as self-balancing binary search trees. The only requirement for the types is that the key implements TotalOrd
.
TreeMap
TreeMapIterator
- Lazy forward iterator over a mapTreeSet
- A implementation of the Set
trait on top of the TreeMap
containerTreeSetIterator
- Lazy forward iterator over a setof Eq for TreeMap<K, V> where <K: Eq + TotalOrd, V: Eq>
of Ord for TreeMap<K, V> where <K: Ord + TotalOrd, V>
of Container for TreeMap<K, V> where <K: TotalOrd, V>
of Mutable for TreeMap<K, V> where <K: TotalOrd, V>
of Map<K, V> for TreeMap<K, V> where <K: TotalOrd, V>
for TreeMap<K, V> where <K: TotalOrd, V>
of Iterator<(&'self K, &'self V)> for TreeMapIterator<'self, K, V> where <'self, K, V>
of Iterator<&'self T> for TreeSetIterator<'self, T> where <'self, T>
of Eq for TreeSet<T> where <T: Eq + TotalOrd>
of Ord for TreeSet<T> where <T: Ord + TotalOrd>
of Container for TreeSet<T> where <T: TotalOrd>
of Mutable for TreeSet<T> where <T: TotalOrd>
of Set<T> for TreeSet<T> where <T: TotalOrd>
for TreeSet<T> where <T: TotalOrd>
for TreeNode<K, V> where <K: TotalOrd, V>
TreeMap
pub struct TreeMap<K, V> {
priv root: Option<~TreeNode<K, V>>,
priv length: uint,
}
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
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.
TreeSetIterator
pub struct TreeSetIterator<'self, T> {
priv iter: TreeMapIterator<'self, T, ()>,
}
Lazy forward iterator over a set
Eq
for TreeMap<K, V>
where <K: Eq + TotalOrd, V: Eq>
eq
fn eq(&self, other: &TreeMap<K, V>) -> bool
ne
fn ne(&self, other: &TreeMap<K, V>) -> bool
Ord
for TreeMap<K, V>
where <K: Ord + TotalOrd, V>
lt
fn lt(&self, other: &TreeMap<K, V>) -> bool
le
fn le(&self, other: &TreeMap<K, V>) -> bool
ge
fn ge(&self, other: &TreeMap<K, V>) -> bool
gt
fn gt(&self, other: &TreeMap<K, V>) -> bool
Container
for TreeMap<K, V>
where <K: TotalOrd, V>
len
fn len(&self) -> uint
Return the number of elements in the map
is_empty
fn is_empty(&self) -> bool
Return true if the map contains no elements
Mutable
for TreeMap<K, V>
where <K: TotalOrd, V>
clear
fn clear(&mut self)
Clear the map, removing all key-value pairs.
Map<K, V>
for TreeMap<K, V>
where <K: TotalOrd, V>
contains_key
fn contains_key(&self, key: &K) -> bool
Return true if the map contains a value for the specified key
find
fn find<'a>(&'a self, key: &K) -> Option<&'a V>
Return a reference to the value corresponding to the key
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
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.
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.
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.
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.
TreeMap<K, V>
where <K: TotalOrd, V>
new
fn new() -> TreeMap<K, V>
Create an empty TreeMap
each_key
fn each_key(&self, f: &fn(&K) -> bool) -> bool
Visit all keys in order
each_value
fn each_value<'a>(&'a self, f: &fn(&'a V) -> bool) -> bool
Visit all values in order
mutate_values
fn mutate_values(&mut self, f: &fn(&K, &mut V) -> bool) -> bool
Iterate over the map and mutate the contained values
each_reverse
fn each_reverse<'a>(&'a self, f: &fn(&'a K, &'a V) -> bool) -> bool
Visit all key-value pairs in reverse order
each_key_reverse
fn each_key_reverse(&self, f: &fn(&K) -> bool) -> bool
Visit all keys in reverse order
each_value_reverse
fn each_value_reverse(&self, f: &fn(&V) -> bool) -> bool
Visit all values in reverse order
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).
Iterator<(&'self K, &'self V)>
for TreeMapIterator<'self, K, V>
where <'self, K, V>
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
.
Iterator<&'self T>
for TreeSetIterator<'self, T>
where <'self, T>
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
.
Eq
for TreeSet<T>
where <T: Eq + TotalOrd>
eq
fn eq(&self, other: &TreeSet<T>) -> bool
ne
fn ne(&self, other: &TreeSet<T>) -> bool
Ord
for TreeSet<T>
where <T: Ord + TotalOrd>
lt
fn lt(&self, other: &TreeSet<T>) -> bool
le
fn le(&self, other: &TreeSet<T>) -> bool
ge
fn ge(&self, other: &TreeSet<T>) -> bool
gt
fn gt(&self, other: &TreeSet<T>) -> bool
Container
for TreeSet<T>
where <T: TotalOrd>
len
fn len(&self) -> uint
Return the number of elements in the set
is_empty
fn is_empty(&self) -> bool
Return true if the set contains no elements
Mutable
for TreeSet<T>
where <T: TotalOrd>
clear
fn clear(&mut self)
Clear the set, removing all values.
Set<T>
for TreeSet<T>
where <T: TotalOrd>
contains
fn contains(&self, value: &T) -> bool
Return true if the set contains a value
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.
remove
fn remove(&mut self, value: &T) -> bool
Remove a value from the set. Return true if the value was present in the set.
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.
is_subset
fn is_subset(&self, other: &TreeSet<T>) -> bool
Return true if the set is a subset of another
is_superset
fn is_superset(&self, other: &TreeSet<T>) -> bool
Return true if the set is a superset of another
difference
fn difference(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool
Visit the values (in-order) representing the difference
symmetric_difference
fn symmetric_difference(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool
Visit the values (in-order) representing the symmetric difference
intersection
fn intersection(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool
Visit the values (in-order) representing the intersection
union
fn union(&self, other: &TreeSet<T>, f: &fn(&T) -> bool) -> bool
Visit the values (in-order) representing the union
TreeSet<T>
where <T: TotalOrd>
new
fn new() -> TreeSet<T>
Create an empty TreeSet
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).
each_reverse
fn each_reverse(&self, f: &fn(&T) -> bool) -> bool
Visit all values in reverse order
TreeNode<K, V>
where <K: TotalOrd, V>
new
fn new(key: K, value: V) -> TreeNode<K, V>
Creates a new tree node.