Struct im::set::Set

pub struct Set<A>(_);

Ordered Set

An immutable ordered set implemented as a balanced 2-3 tree.

This is implemented as a Map with no values, so it shares the exact performance characteristics of Map.

Methods

impl<A> Set<A>

fn new() -> Self

Construct an empty set.

fn singleton<R>(a: R) -> Self where
    Arc<A>: From<R>, 

Construct a set with a single value.

Examples

let set = Set::singleton(123);
assert!(set.contains(&123));

fn iter(&self) -> Iter<A>

fn is_empty(&self) -> bool

Test whether a set is empty.

Time: O(1)

Examples

assert!(
  !set![1, 2, 3].is_empty()
);
assert!(
  Set::<i32>::new().is_empty()
);

fn len(&self) -> usize

Get the size of a set.

Time: O(1)

Examples

assert_eq!(3, set![1, 2, 3].len());

fn get_min(&self) -> Option<Arc<A>>

Get the smallest value in a set.

If the set is empty, returns None.

fn get_max(&self) -> Option<Arc<A>>

Get the largest value in a set.

If the set is empty, returns None.

impl<A: Ord> Set<A>

fn insert<R>(&self, a: R) -> Self where
    Arc<A>: From<R>, 

Insert a value into a set.

Time: O(log n)

Examples

let set = set![456];
assert_eq!(
  set.insert(123),
  set![123, 456]
);

fn contains(&self, a: &A) -> bool

Test if a value is part of a set.

Time: O(log n)

fn remove(&self, a: &A) -> Self

Remove a value from a set.

fn union(&self, other: &Self) -> Self

Construct the union of two sets.

fn unions<I>(i: I) -> Self where
    I: IntoIterator<Item = Self>, 

Construct the union of multiple sets.

fn difference<RS>(&self, other: RS) -> Self where
    RS: Borrow<Self>, 

Construct the difference between two sets.

fn intersection<RS>(&self, other: RS) -> Self where
    RS: Borrow<Self>, 

Construct the intersection of two sets.

fn split(&self, split: &A) -> (Self, Self)

Split a set into two, with the left hand set containing values which are smaller than split, and the right hand set containing values which are larger than split.

The split value itself is discarded.

fn split_member(&self, split: &A) -> (Self, bool, Self)

Split a set into two, with the left hand set containing values which are smaller than split, and the right hand set containing values which are larger than split.

Returns a tuple of the two maps and a boolean which is true if the split value existed in the original set, and false otherwise.

fn is_subset<RS>(&self, other: RS) -> bool where
    RS: Borrow<Self>, 

Test whether a set is a subset of another set, meaning that all values in our set must also be in the other set.

fn is_proper_subset<RS>(&self, other: RS) -> bool where
    RS: Borrow<Self>, 

Test whether a set is a proper subset of another set, meaning that all values in our set must also be in the other set. A proper subset must also be smaller than the other set.

fn take(&self, n: usize) -> Self

Construct a set with only the n smallest values from a given set.

fn drop(&self, n: usize) -> Self

Construct a set with the n smallest values removed from a given set.

fn pop_min(&self) -> (Option<Arc<A>>, Self)

Remove the smallest value from a set, and return that value as well as the updated set.

fn pop_max(&self) -> (Option<Arc<A>>, Self)

Remove the largest value from a set, and return that value as well as the updated set.

fn remove_min(&self) -> Self

Discard the smallest value from a set, returning the updated set.

fn remove_max(&self) -> Self

Discard the largest value from a set, returning the updated set.

Trait Implementations

impl<A> Clone for Set<A>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A: PartialEq> PartialEq for Set<A>

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

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

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

This method tests for !=.

impl<A: Eq> Eq for Set<A>

impl<A: PartialOrd> PartialOrd for Set<A>

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

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

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

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

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

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

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

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

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

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

impl<A: Ord> Ord for Set<A>

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

This method returns an Ordering between self and other.

impl<A: Hash> Hash for Set<A>

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

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<A> Default for Set<A>

fn default() -> Self

Returns the "default value" for a type.

impl<'a, A: Ord> Add for &'a Set<A>

type Output = Set<A>

The resulting type after applying the + operator

fn add(self, other: Self) -> Self::Output

The method for the + operator

impl<'a, A: Ord> Mul for &'a Set<A>

type Output = Set<A>

The resulting type after applying the * operator

fn mul(self, other: Self) -> Self::Output

The method for the * operator

impl<A: Debug> Debug for Set<A>

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

Formats the value using the given formatter.

impl<A: Ord, RA> FromIterator<RA> for Set<A> where
    Arc<A>: From<RA>, 

fn from_iter<T>(i: T) -> Self where
    T: IntoIterator<Item = RA>, 

Creates a value from an iterator.

impl<'a, A> IntoIterator for &'a Set<A>

type Item = Arc<A>

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) -> Self::IntoIter

Creates an iterator from a value.

impl<A> IntoIterator for Set<A>

type Item = Arc<A>

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) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, A: Ord + Clone> From<&'a [A]> for Set<A>

fn from(slice: &'a [A]) -> Self

Performs the conversion.

impl<'a, A: Ord> From<&'a [Arc<A>]> for Set<A>

fn from(slice: &'a [Arc<A>]) -> Self

Performs the conversion.

impl<A: Ord> From<Vec<A>> for Set<A>

fn from(vec: Vec<A>) -> Self

Performs the conversion.

impl<'a, A: Ord + Clone> From<&'a Vec<A>> for Set<A>

fn from(vec: &Vec<A>) -> Self

Performs the conversion.

impl<'a, A: Ord> From<&'a Vec<Arc<A>>> for Set<A>

fn from(vec: &Vec<Arc<A>>) -> Self

Performs the conversion.

impl<A: Eq + Hash + Ord> From<HashSet<A>> for Set<A>

fn from(hash_set: HashSet<A>) -> Self

Performs the conversion.

impl<'a, A: Eq + Hash + Ord + Clone> From<&'a HashSet<A>> for Set<A>

fn from(hash_set: &HashSet<A>) -> Self

Performs the conversion.

impl<'a, A: Eq + Hash + Ord> From<&'a HashSet<Arc<A>>> for Set<A>

fn from(hash_set: &HashSet<Arc<A>>) -> Self

Performs the conversion.

impl<A: Ord> From<BTreeSet<A>> for Set<A>

fn from(btree_set: BTreeSet<A>) -> Self

Performs the conversion.

impl<'a, A: Ord + Clone> From<&'a BTreeSet<A>> for Set<A>

fn from(btree_set: &BTreeSet<A>) -> Self

Performs the conversion.

impl<'a, A: Ord> From<&'a BTreeSet<Arc<A>>> for Set<A>

fn from(btree_set: &BTreeSet<Arc<A>>) -> Self

Performs the conversion.