Struct Set

pub struct Set { /* private fields */ }

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

Implementations

impl Set

pub fn new() -> Set

Creates an empty set.

Examples

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

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

pub 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);
}

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

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

pub 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());

pub 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());

pub 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());

pub 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());

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

pub 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());

pub 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());

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

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

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

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

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

pub 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<'a, 'b> BitAnd<&'b Set> for &'a Set

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

type Output = Set

The resulting type after applying the & operator.

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

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

type Output = Set

The resulting type after applying the | operator.

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

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

type Output = Set

The resulting type after applying the ^ operator.

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 Debug for Set

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

Formats the value using the given formatter.

impl Default for Set

fn default() -> Set

Returns the “default value” for a type.

impl Extend<usize> for Set

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl FromIterator<usize> for Set

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

Creates a value from an iterator.

impl Hash for Set

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

Feeds this value into the given Hasher.

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

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

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.

impl Ord for Set

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

This method returns an Ordering between self and other.

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

where Self: Sized,

Compares and returns the maximum of two values.

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

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for Set

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

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for Set

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

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

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

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

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

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

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

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

type Output = Set

The resulting type after applying the - operator.

impl Eq for Set

impl StructuralPartialEq for Set