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

pub struct TrieSet {
    // some fields omitted
}

A set implemented as a radix trie.

Example

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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>(&'a self) -> SetItems<'a>

Gets an iterator over the values in the set, in sorted order.

Example

extern crate collections; 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>(&'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

extern crate collections; 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>(&'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

extern crate collections; 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 len(&self) -> uint

Return the number of elements in the set

Example

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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);

impl TrieSet

fn new() -> TrieSet

Creates an empty TrieSet.

Example

extern crate collections; 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

extern crate collections; 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>(&'a self) -> SetItems<'a>

Gets an iterator over the values in the set, in sorted order.

Example

extern crate collections; 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>(&'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

extern crate collections; 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>(&'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

extern crate collections; 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 len(&self) -> uint

Return the number of elements in the set

Example

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

extern crate collections; 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

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 Show for TrieSet

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

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)

Derived Implementations

impl Ord for TrieSet

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

impl PartialOrd 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

impl Eq for TrieSet

impl PartialEq for TrieSet

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

fn ne(&self, __arg_0: &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, source: &Self)

impl Ord for TrieSet

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

impl PartialOrd 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

impl Eq for TrieSet

impl PartialEq for TrieSet

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

fn ne(&self, __arg_0: &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, source: &Self)