Struct trie::set::Set

pub struct Set { /* fields omitted */ }

A set implemented as a radix trie.

Examples

let mut set = trie::Set::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 Set

fn new() -> Set

Creates an empty set.

Examples

let mut set = trie::Set::new();

fn each_reverse<F>(&self, f: F) -> bool where
    F: FnMut(&usize) -> bool, 

Visits all values in reverse order. Aborts traversal when f returns false. Returns true if f returns true for all elements.

Examples

let set: trie::Set = [1, 2, 3, 4, 5].iter().cloned().collect();

let mut vec = vec![];
assert_eq!(true, set.each_reverse(|&x| { vec.push(x); true }));
assert_eq!(vec, [5, 4, 3, 2, 1]);

// Stop when we reach 3
let mut vec = vec![];
assert_eq!(false, set.each_reverse(|&x| { vec.push(x); x != 3 }));
assert_eq!(vec, [5, 4, 3]);

fn iter(&self) -> Iter

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

Examples

let mut set = trie::Set::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(&self, val: usize) -> Range

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

let set: trie::Set = [2, 4, 6, 8].iter().cloned().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(&self, val: usize) -> Range

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

let set: trie::Set = [2, 4, 6, 8].iter().cloned().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>(&'a self, other: &'a Set) -> Difference<'a>

Visits the values representing the difference, in ascending order.

Examples

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let b: trie::Set = [3, 4, 5].iter().cloned().collect();

// Can be seen as `a - b`.
for x in a.difference(&b) {
    println!("{}", x); // Print 1 then 2
}

let diff1: trie::Set = a.difference(&b).collect();
assert_eq!(diff1, [1, 2].iter().cloned().collect());

// Note that difference is not symmetric,
// and `b - a` means something else:
let diff2: trie::Set = b.difference(&a).collect();
assert_eq!(diff2, [4, 5].iter().cloned().collect());

fn symmetric_difference<'a>(&'a self, other: &'a Set) -> SymmetricDifference<'a>

Visits the values representing the symmetric difference, in ascending order.

Examples

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let b: trie::Set = [3, 4, 5].iter().cloned().collect();

// Print 1, 2, 4, 5 in ascending order.
for x in a.symmetric_difference(&b) {
    println!("{}", x);
}

let diff1: trie::Set = a.symmetric_difference(&b).collect();
let diff2: trie::Set = b.symmetric_difference(&a).collect();

assert_eq!(diff1, diff2);
assert_eq!(diff1, [1, 2, 4, 5].iter().cloned().collect());

fn intersection<'a>(&'a self, other: &'a Set) -> Intersection<'a>

Visits the values representing the intersection, in ascending order.

Examples

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let b: trie::Set = [2, 3, 4].iter().cloned().collect();

// Print 2, 3 in ascending order.
for x in a.intersection(&b) {
    println!("{}", x);
}

let diff: trie::Set = a.intersection(&b).collect();
assert_eq!(diff, [2, 3].iter().cloned().collect());

fn union<'a>(&'a self, other: &'a Set) -> Union<'a>

Visits the values representing the union, in ascending order.

Examples

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let b: trie::Set = [3, 4, 5].iter().cloned().collect();

// Print 1, 2, 3, 4, 5 in ascending order.
for x in a.union(&b) {
    println!("{}", x);
}

let diff: trie::Set = a.union(&b).collect();
assert_eq!(diff, [1, 2, 3, 4, 5].iter().cloned().collect());

fn len(&self) -> usize

Return the number of elements in the set

Examples

let mut v = trie::Set::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

let mut v = trie::Set::new();
assert!(v.is_empty());
v.insert(1);
assert!(!v.is_empty());

fn clear(&mut self)

Clears the set, removing all values.

Examples

let mut v = trie::Set::new();
v.insert(1);
v.clear();
assert!(v.is_empty());

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

Returns true if the set contains a value.

Examples

let set: trie::Set = [1, 2, 3].iter().cloned().collect();
assert_eq!(set.contains(&1), true);
assert_eq!(set.contains(&4), false);

fn is_disjoint(&self, other: &Set) -> bool

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

Examples

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let mut b = trie::Set::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: &Set) -> bool

Returns true if the set is a subset of another.

Examples

let sup: trie::Set = [1, 2, 3].iter().cloned().collect();
let mut set = trie::Set::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: &Set) -> bool

Returns true if the set is a superset of another.

Examples

let sub: trie::Set = [1, 2].iter().cloned().collect();
let mut set = trie::Set::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: usize) -> bool

Adds a value to the set. Returns true if the value was not already present in the set.

Examples

let mut set = trie::Set::new();

assert_eq!(set.insert(2), true);
assert_eq!(set.insert(2), false);
assert_eq!(set.len(), 1);

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

Removes a value from the set. Returns true if the value was present in the set.

Examples

let mut set = trie::Set::new();

set.insert(2);
assert_eq!(set.remove(&2), true);
assert_eq!(set.remove(&2), false);

Trait Implementations

impl Clone for Set

fn clone(&self) -> Set

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Default for Set

fn default() -> Set

Returns the "default value" for a type.

impl Hash for Set

fn hash<__H: Hasher>(&self, __arg_0: &mut __H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl PartialEq for Set

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

impl Eq for Set

impl PartialOrd for Set

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

This method returns an ordering between self and other values if one exists.

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

This method tests less than (for self and other) and is used by the < operator.

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

This method tests less than or equal to (for self and other) and is used by the <= operator.

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

This method tests greater than (for self and other) and is used by the > operator.

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

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl Ord for Set

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

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl Debug for Set

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

Formats the value using the given formatter.

impl FromIterator<usize> for Set

fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Set

Creates a value from an iterator.

impl Extend<usize> for Set

fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

impl<'a, 'b> BitOr<&'b Set> for &'a Set

type Output = Set

The resulting type after applying the | operator.

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

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

Example

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let b: trie::Set = [3, 4, 5].iter().cloned().collect();

let set: trie::Set = &a | &b;
let v: Vec<usize> = set.iter().collect();
assert_eq!(v, [1, 2, 3, 4, 5]);

impl<'a, 'b> BitAnd<&'b Set> for &'a Set

type Output = Set

The resulting type after applying the & operator.

fn bitand(self, rhs: &Set) -> Set

Returns the intersection of self and rhs as a new set.

Example

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let b: trie::Set = [2, 3, 4].iter().cloned().collect();

let set: trie::Set = &a & &b;
let v: Vec<usize> = set.iter().collect();
assert_eq!(v, [2, 3]);

impl<'a, 'b> BitXor<&'b Set> for &'a Set

type Output = Set

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: &Set) -> Set

Returns the symmetric difference of self and rhs as a new set.

Example

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let b: trie::Set = [3, 4, 5].iter().cloned().collect();

let set: trie::Set = &a ^ &b;
let v: Vec<usize> = set.iter().collect();
assert_eq!(v, [1, 2, 4, 5]);

impl<'a, 'b> Sub<&'b Set> for &'a Set

type Output = Set

The resulting type after applying the - operator.

fn sub(self, rhs: &Set) -> Set

Returns the difference of self and rhs as a new set.

Example

let a: trie::Set = [1, 2, 3].iter().cloned().collect();
let b: trie::Set = [3, 4, 5].iter().cloned().collect();

let set: trie::Set = &a - &b;
let v: Vec<usize> = set.iter().collect();
assert_eq!(v, [1, 2]);

impl<'a> IntoIterator for &'a Set

type Item = usize

The type of the elements being iterated over.

type IntoIter = Iter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a>

Creates an iterator from a value.