Struct std::collections::trie_set::TrieSetExperimental [-]  [+] [src]

pub struct TrieSet {
    // some fields omitted
}

A set implemented as a radix trie.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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

Examples

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

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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.

Examples

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

fn fmt(&self, f: &mut Formatter) -> Result<(), Error>

impl Default for TrieSet

fn default() -> TrieSet

impl FromIterator<uint> for TrieSet

fn from_iter<Iter: Iterator<uint>>(iter: Iter) -> TrieSet

impl Extend<uint> for TrieSet

fn extend<Iter: Iterator<uint>>(&mut self, iter: Iter)

impl BitOr<TrieSet, TrieSet> for TrieSet

fn bitor(&self, rhs: &TrieSet) -> TrieSet

Returns the union of self and rhs as a new TrieSet.

Examples

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.

Examples

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.

Examples

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.

Examples

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]);

Derived Implementations

impl Ord<TrieSet> for TrieSet

fn cmp(&self, __arg_0: &TrieSet) -> Ordering

impl PartialOrd<TrieSet> for TrieSet

fn partial_cmp(&self, __arg_0: &TrieSet) -> Option<Ordering>

fn lt(&self, __arg_0: &TrieSet) -> bool

fn le(&self, __arg_0: &TrieSet) -> bool

fn gt(&self, __arg_0: &TrieSet) -> bool

fn ge(&self, __arg_0: &TrieSet) -> bool

fn lt(&self, &TrieSet) -> bool

fn le(&self, &TrieSet) -> bool

fn gt(&self, &TrieSet) -> bool

fn ge(&self, &TrieSet) -> bool

impl Eq<TrieSet> for TrieSet

fn assert_receiver_is_total_eq(&self)

impl PartialEq<TrieSet> for TrieSet

fn eq(&self, __arg_0: &TrieSet) -> bool

fn ne(&self, __arg_0: &TrieSet) -> bool

fn ne(&self, &TrieSet) -> bool

impl<__S: Writer> Hash<__S> for TrieSet

fn hash(&self, __arg_0: &mut __S)

impl Clone for TrieSet

fn clone(&self) -> TrieSet

fn clone_from(&mut self, &TrieSet)