Struct std::collections::TrieSetExperimental
[-]
[+]
[src]
pub struct TrieSet {
// some fields omitted
}A set implemented as a radix trie.
Example
fn main() { use std::collections::TrieSet; let mut set = TrieSet::new(); set.insert(6); set.insert(28); set.insert(6); assert_eq!(set.len(), 2); if !set.contains(&3) { println!("3 is not in the set"); } // Print contents in order for x in set.iter() { println!("{}", x); } set.remove(&6); assert_eq!(set.len(), 1); set.clear(); assert!(set.is_empty()); }use std::collections::TrieSet; let mut set = TrieSet::new(); set.insert(6); set.insert(28); set.insert(6); assert_eq!(set.len(), 2); if !set.contains(&3) { println!("3 is not in the set"); } // Print contents in order for x in set.iter() { println!("{}", x); } set.remove(&6); assert_eq!(set.len(), 1); set.clear(); assert!(set.is_empty());
Methods
impl TrieSet
fn new() -> TrieSet
Creates an empty TrieSet.
Example
fn main() { use std::collections::TrieSet; let mut set = TrieSet::new(); }use std::collections::TrieSet; let mut set = TrieSet::new();
fn each_reverse(&self, f: |&uint| -> bool) -> bool
Visits all values in reverse order. Aborts traversal when f returns false.
Returns true if f returns true for all elements.
Example
fn main() { use std::collections::TrieSet; let set: TrieSet = [1, 2, 3, 4, 5].iter().map(|&x| x).collect(); let mut vec = Vec::new(); assert_eq!(true, set.each_reverse(|&x| { vec.push(x); true })); assert_eq!(vec, vec![5, 4, 3, 2, 1]); // Stop when we reach 3 let mut vec = Vec::new(); assert_eq!(false, set.each_reverse(|&x| { vec.push(x); x != 3 })); assert_eq!(vec, vec![5, 4, 3]); }use std::collections::TrieSet; let set: TrieSet = [1, 2, 3, 4, 5].iter().map(|&x| x).collect(); let mut vec = Vec::new(); assert_eq!(true, set.each_reverse(|&x| { vec.push(x); true })); assert_eq!(vec, vec![5, 4, 3, 2, 1]); // Stop when we reach 3 let mut vec = Vec::new(); assert_eq!(false, set.each_reverse(|&x| { vec.push(x); x != 3 })); assert_eq!(vec, vec![5, 4, 3]);
fn iter(&'a self) -> SetItems<'a>
Gets an iterator over the values in the set, in sorted order.
Example
fn main() { use std::collections::TrieSet; let mut set = TrieSet::new(); set.insert(3); set.insert(2); set.insert(1); set.insert(2); // Print 1, 2, 3 for x in set.iter() { println!("{}", x); } }use std::collections::TrieSet; let mut set = TrieSet::new(); set.insert(3); set.insert(2); set.insert(1); set.insert(2); // Print 1, 2, 3 for x in set.iter() { println!("{}", x); }
fn lower_bound(&'a self, val: uint) -> SetItems<'a>
Gets an iterator pointing to the first value that is not less than val.
If all values in the set are less than val an empty iterator is returned.
Example
fn main() { use std::collections::TrieSet; let set: TrieSet = [2, 4, 6, 8].iter().map(|&x| x).collect(); assert_eq!(set.lower_bound(4).next(), Some(4)); assert_eq!(set.lower_bound(5).next(), Some(6)); assert_eq!(set.lower_bound(10).next(), None); }use std::collections::TrieSet; let set: TrieSet = [2, 4, 6, 8].iter().map(|&x| x).collect(); assert_eq!(set.lower_bound(4).next(), Some(4)); assert_eq!(set.lower_bound(5).next(), Some(6)); assert_eq!(set.lower_bound(10).next(), None);
fn upper_bound(&'a self, val: uint) -> SetItems<'a>
Gets an iterator pointing to the first value that key is greater than val.
If all values in the set are less than or equal to val an empty iterator is returned.
Example
fn main() { use std::collections::TrieSet; let set: TrieSet = [2, 4, 6, 8].iter().map(|&x| x).collect(); assert_eq!(set.upper_bound(4).next(), Some(6)); assert_eq!(set.upper_bound(5).next(), Some(6)); assert_eq!(set.upper_bound(10).next(), None); }use std::collections::TrieSet; let set: TrieSet = [2, 4, 6, 8].iter().map(|&x| x).collect(); assert_eq!(set.upper_bound(4).next(), Some(6)); assert_eq!(set.upper_bound(5).next(), Some(6)); assert_eq!(set.upper_bound(10).next(), None);
fn difference(&'a self, other: &'a TrieSet) -> DifferenceItems<'a>
Visits the values representing the difference, in ascending order.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect(); // Can be seen as `a - b`. for x in a.difference(&b) { println!("{}", x); // Print 1 then 2 } let diff1: TrieSet = a.difference(&b).collect(); assert_eq!(diff1, [1, 2].iter().map(|&x| x).collect()); // Note that difference is not symmetric, // and `b - a` means something else: let diff2: TrieSet = b.difference(&a).collect(); assert_eq!(diff2, [4, 5].iter().map(|&x| x).collect()); }use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect(); // Can be seen as `a - b`. for x in a.difference(&b) { println!("{}", x); // Print 1 then 2 } let diff1: TrieSet = a.difference(&b).collect(); assert_eq!(diff1, [1, 2].iter().map(|&x| x).collect()); // Note that difference is not symmetric, // and `b - a` means something else: let diff2: TrieSet = b.difference(&a).collect(); assert_eq!(diff2, [4, 5].iter().map(|&x| x).collect());
fn symmetric_difference(&'a self, other: &'a TrieSet) -> SymDifferenceItems<'a>
Visits the values representing the symmetric difference, in ascending order.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect(); // Print 1, 2, 4, 5 in ascending order. for x in a.symmetric_difference(&b) { println!("{}", x); } let diff1: TrieSet = a.symmetric_difference(&b).collect(); let diff2: TrieSet = b.symmetric_difference(&a).collect(); assert_eq!(diff1, diff2); assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect()); }use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect(); // Print 1, 2, 4, 5 in ascending order. for x in a.symmetric_difference(&b) { println!("{}", x); } let diff1: TrieSet = a.symmetric_difference(&b).collect(); let diff2: TrieSet = b.symmetric_difference(&a).collect(); assert_eq!(diff1, diff2); assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect());
fn intersection(&'a self, other: &'a TrieSet) -> IntersectionItems<'a>
Visits the values representing the intersection, in ascending order.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let b: TrieSet = [2, 3, 4].iter().map(|&x| x).collect(); // Print 2, 3 in ascending order. for x in a.intersection(&b) { println!("{}", x); } let diff: TrieSet = a.intersection(&b).collect(); assert_eq!(diff, [2, 3].iter().map(|&x| x).collect()); }use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let b: TrieSet = [2, 3, 4].iter().map(|&x| x).collect(); // Print 2, 3 in ascending order. for x in a.intersection(&b) { println!("{}", x); } let diff: TrieSet = a.intersection(&b).collect(); assert_eq!(diff, [2, 3].iter().map(|&x| x).collect());
fn union(&'a self, other: &'a TrieSet) -> UnionItems<'a>
Visits the values representing the union, in ascending order.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect(); // Print 1, 2, 3, 4, 5 in ascending order. for x in a.union(&b) { println!("{}", x); } let diff: TrieSet = a.union(&b).collect(); assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect()); }use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let b: TrieSet = [3, 4, 5].iter().map(|&x| x).collect(); // Print 1, 2, 3, 4, 5 in ascending order. for x in a.union(&b) { println!("{}", x); } let diff: TrieSet = a.union(&b).collect(); assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect());
fn len(&self) -> uint
Return the number of elements in the set
Example
fn main() { use std::collections::TrieSet; let mut v = TrieSet::new(); assert_eq!(v.len(), 0); v.insert(1); assert_eq!(v.len(), 1); }use std::collections::TrieSet; let mut v = TrieSet::new(); assert_eq!(v.len(), 0); v.insert(1); assert_eq!(v.len(), 1);
fn is_empty(&self) -> bool
Returns true if the set contains no elements
Example
fn main() { use std::collections::TrieSet; let mut v = TrieSet::new(); assert!(v.is_empty()); v.insert(1); assert!(!v.is_empty()); }use std::collections::TrieSet; let mut v = TrieSet::new(); assert!(v.is_empty()); v.insert(1); assert!(!v.is_empty());
fn clear(&mut self)
Clears the set, removing all values.
Example
fn main() { use std::collections::TrieSet; let mut v = TrieSet::new(); v.insert(1); v.clear(); assert!(v.is_empty()); }use std::collections::TrieSet; let mut v = TrieSet::new(); v.insert(1); v.clear(); assert!(v.is_empty());
fn contains(&self, value: &uint) -> bool
Returns true if the set contains a value.
Example
fn main() { use std::collections::TrieSet; let set: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); assert_eq!(set.contains(&1), true); assert_eq!(set.contains(&4), false); }use std::collections::TrieSet; let set: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); assert_eq!(set.contains(&1), true); assert_eq!(set.contains(&4), false);
fn is_disjoint(&self, other: &TrieSet) -> bool
Returns true if the set has no elements in common with other.
This is equivalent to checking for an empty intersection.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let mut b: TrieSet = TrieSet::new(); assert_eq!(a.is_disjoint(&b), true); b.insert(4); assert_eq!(a.is_disjoint(&b), true); b.insert(1); assert_eq!(a.is_disjoint(&b), false); }use std::collections::TrieSet; let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let mut b: TrieSet = TrieSet::new(); assert_eq!(a.is_disjoint(&b), true); b.insert(4); assert_eq!(a.is_disjoint(&b), true); b.insert(1); assert_eq!(a.is_disjoint(&b), false);
fn is_subset(&self, other: &TrieSet) -> bool
Returns true if the set is a subset of another.
Example
fn main() { use std::collections::TrieSet; let sup: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let mut set: TrieSet = TrieSet::new(); assert_eq!(set.is_subset(&sup), true); set.insert(2); assert_eq!(set.is_subset(&sup), true); set.insert(4); assert_eq!(set.is_subset(&sup), false); }use std::collections::TrieSet; let sup: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); let mut set: TrieSet = TrieSet::new(); assert_eq!(set.is_subset(&sup), true); set.insert(2); assert_eq!(set.is_subset(&sup), true); set.insert(4); assert_eq!(set.is_subset(&sup), false);
fn is_superset(&self, other: &TrieSet) -> bool
Returns true if the set is a superset of another.
Example
fn main() { use std::collections::TrieSet; let sub: TrieSet = [1, 2].iter().map(|&x| x).collect(); let mut set: TrieSet = TrieSet::new(); assert_eq!(set.is_superset(&sub), false); set.insert(0); set.insert(1); assert_eq!(set.is_superset(&sub), false); set.insert(2); assert_eq!(set.is_superset(&sub), true); }use std::collections::TrieSet; let sub: TrieSet = [1, 2].iter().map(|&x| x).collect(); let mut set: TrieSet = TrieSet::new(); assert_eq!(set.is_superset(&sub), false); set.insert(0); set.insert(1); assert_eq!(set.is_superset(&sub), false); set.insert(2); assert_eq!(set.is_superset(&sub), true);
fn insert(&mut self, value: uint) -> bool
Adds a value to the set. Returns true if the value was not already
present in the set.
Example
fn main() { use std::collections::TrieSet; let mut set = TrieSet::new(); assert_eq!(set.insert(2), true); assert_eq!(set.insert(2), false); assert_eq!(set.len(), 1); }use std::collections::TrieSet; let mut set = TrieSet::new(); assert_eq!(set.insert(2), true); assert_eq!(set.insert(2), false); assert_eq!(set.len(), 1);
fn remove(&mut self, value: &uint) -> bool
Removes a value from the set. Returns true if the value was
present in the set.
Example
fn main() { use std::collections::TrieSet; let mut set = TrieSet::new(); set.insert(2); assert_eq!(set.remove(&2), true); assert_eq!(set.remove(&2), false); }use std::collections::TrieSet; let mut set = TrieSet::new(); set.insert(2); assert_eq!(set.remove(&2), true); assert_eq!(set.remove(&2), false);
Trait Implementations
impl Show for TrieSet
impl Default for TrieSet
impl FromIterator<uint> for TrieSet
impl Extend<uint> for TrieSet
impl BitOr<TrieSet, TrieSet> for TrieSet
fn bitor(&self, rhs: &TrieSet) -> TrieSet
Returns the union of self and rhs as a new TrieSet.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = vec![1, 2, 3].into_iter().collect(); let b: TrieSet = vec![3, 4, 5].into_iter().collect(); let set: TrieSet = a | b; let v: Vec<uint> = set.iter().collect(); assert_eq!(v, vec![1u, 2, 3, 4, 5]); }use std::collections::TrieSet; let a: TrieSet = vec![1, 2, 3].into_iter().collect(); let b: TrieSet = vec![3, 4, 5].into_iter().collect(); let set: TrieSet = a | b; let v: Vec<uint> = set.iter().collect(); assert_eq!(v, vec![1u, 2, 3, 4, 5]);
impl BitAnd<TrieSet, TrieSet> for TrieSet
fn bitand(&self, rhs: &TrieSet) -> TrieSet
Returns the intersection of self and rhs as a new TrieSet.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = vec![1, 2, 3].into_iter().collect(); let b: TrieSet = vec![2, 3, 4].into_iter().collect(); let set: TrieSet = a & b; let v: Vec<uint> = set.iter().collect(); assert_eq!(v, vec![2u, 3]); }use std::collections::TrieSet; let a: TrieSet = vec![1, 2, 3].into_iter().collect(); let b: TrieSet = vec![2, 3, 4].into_iter().collect(); let set: TrieSet = a & b; let v: Vec<uint> = set.iter().collect(); assert_eq!(v, vec![2u, 3]);
impl BitXor<TrieSet, TrieSet> for TrieSet
fn bitxor(&self, rhs: &TrieSet) -> TrieSet
Returns the symmetric difference of self and rhs as a new TrieSet.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = vec![1, 2, 3].into_iter().collect(); let b: TrieSet = vec![3, 4, 5].into_iter().collect(); let set: TrieSet = a ^ b; let v: Vec<uint> = set.iter().collect(); assert_eq!(v, vec![1u, 2, 4, 5]); }use std::collections::TrieSet; let a: TrieSet = vec![1, 2, 3].into_iter().collect(); let b: TrieSet = vec![3, 4, 5].into_iter().collect(); let set: TrieSet = a ^ b; let v: Vec<uint> = set.iter().collect(); assert_eq!(v, vec![1u, 2, 4, 5]);
impl Sub<TrieSet, TrieSet> for TrieSet
fn sub(&self, rhs: &TrieSet) -> TrieSet
Returns the difference of self and rhs as a new TrieSet.
Example
fn main() { use std::collections::TrieSet; let a: TrieSet = vec![1, 2, 3].into_iter().collect(); let b: TrieSet = vec![3, 4, 5].into_iter().collect(); let set: TrieSet = a - b; let v: Vec<uint> = set.iter().collect(); assert_eq!(v, vec![1u, 2]); }use std::collections::TrieSet; let a: TrieSet = vec![1, 2, 3].into_iter().collect(); let b: TrieSet = vec![3, 4, 5].into_iter().collect(); let set: TrieSet = a - b; let v: Vec<uint> = set.iter().collect(); assert_eq!(v, vec![1u, 2]);