Struct im::OrdSet[][src]

pub struct OrdSet<A> { /* fields omitted */ }

An ordered set.

An immutable ordered set implemented as a B-tree.

Most operations on this type of set are O(log n). A HashSet is usually a better choice for performance, but the OrdSet has the advantage of only requiring an Ord constraint on its values, and of being ordered, so values always come out from lowest to highest, where a HashSet has no guaranteed ordering.

Methods

impl<A> OrdSet<A> where
    A: Ord + Clone
[src]

Construct an empty set.

Construct a set with a single value.

Examples

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

Test whether a set is empty.

Time: O(1)

Examples

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

Get the size of a set.

Time: O(1)

Examples

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

Get the smallest value in a set.

If the set is empty, returns None.

Get the largest value in a set.

If the set is empty, returns None.

Important traits for Iter<'a, A>

Important traits for RangedIter<'a, A>

Important traits for DiffIter<'a, A>

Get an iterator over the differences between this set and another, i.e. the set of entries to add or remove to this set in order to make it equal to the other set.

This function will avoid visiting nodes which are shared between the two sets, meaning that even very large sets can be compared quickly if most of their structure is shared.

Time: O(n) (where n is the number of unique elements across the two sets, minus the number of elements belonging to nodes shared between them)

Test if a value is part of a set.

Time: O(log n)

Examples

let mut set = ordset!{1, 2, 3};
assert!(set.contains(&1));
assert!(!set.contains(&4));

Insert a value into a set.

Time: O(log n)

Examples

let mut set = ordset!{};
set.insert(123);
set.insert(456);
assert_eq!(
  set,
  ordset![123, 456]
);

Remove a value from a set.

Time: O(log n)

Remove the smallest value from a set.

Time: O(log n)

Remove the largest value from a set.

Time: O(log n)

Discard all elements from the set.

This leaves you with an empty set, and all elements that were previously inside it are dropped.

Time: O(n)

Examples

let mut set = ordset![1, 2, 3];
set.clear();
assert!(set.is_empty());

Construct a new set from the current set with the given value added.

Time: O(log n)

Examples

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

Construct a new set with the given value removed if it's in the set.

Time: O(log n)

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

Time: O(log n)

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

Time: O(log n)

Construct the union of two sets.

Time: O(n log n)

Examples

let set1 = ordset!{1, 2};
let set2 = ordset!{2, 3};
let expected = ordset!{1, 2, 3};
assert_eq!(expected, set1.union(set2));

Construct the union of multiple sets.

Time: O(n log n)

Construct the difference between two sets.

Time: O(n log n)

Examples

let set1 = ordset!{1, 2};
let set2 = ordset!{2, 3};
let expected = ordset!{1, 3};
assert_eq!(expected, set1.difference(set2));

Construct the intersection of two sets.

Time: O(n log n)

Examples

let set1 = ordset!{1, 2};
let set2 = ordset!{2, 3};
let expected = ordset!{2};
assert_eq!(expected, set1.intersection(set2));

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

Time: O(n log n)

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.

Time: O(n log n)

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.

Time: O(n)

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 sets and a boolean which is true if the split value existed in the original set, and false otherwise.

Time: O(n)

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

Time: O(n)

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

Time: O(n)

Trait Implementations

impl<A> Clone for OrdSet<A>
[src]

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

impl<A: Ord + Clone> PartialEq for OrdSet<A>
[src]

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

This method tests for !=.

impl<A: Ord + Eq + Clone> Eq for OrdSet<A>
[src]

impl<A: Ord + Clone> PartialOrd for OrdSet<A>
[src]

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

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

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

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

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

impl<A: Ord + Clone> Ord for OrdSet<A>
[src]

This method returns an Ordering between self and other. Read more

Compares and returns the maximum of two values. Read more

Compares and returns the minimum of two values. Read more

impl<A: Ord + Clone + Hash> Hash for OrdSet<A>
[src]

Feeds this value into the given [Hasher]. Read more

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

impl<A> Default for OrdSet<A> where
    A: Ord + Clone
[src]

Returns the "default value" for a type. Read more

impl<A: Ord + Clone> Add for OrdSet<A>
[src]

The resulting type after applying the + operator.

Performs the + operation.

impl<'a, A: Ord + Clone> Add for &'a OrdSet<A>
[src]

The resulting type after applying the + operator.

Performs the + operation.

impl<A: Ord + Clone> Mul for OrdSet<A>
[src]

The resulting type after applying the * operator.

Performs the * operation.

impl<'a, A: Ord + Clone> Mul for &'a OrdSet<A>
[src]

The resulting type after applying the * operator.

Performs the * operation.

impl<A: Ord + Clone> Sum for OrdSet<A>
[src]

Method which takes an iterator and generates Self from the elements by "summing up" the items. Read more

impl<A, R> Extend<R> for OrdSet<A> where
    A: Ord + Clone + From<R>, 
[src]

Extends a collection with the contents of an iterator. Read more

impl<A: Ord + Clone + Debug> Debug for OrdSet<A>
[src]

Formats the value using the given formatter. Read more

impl<A, R> FromIterator<R> for OrdSet<A> where
    A: Ord + Clone + From<R>, 
[src]

Creates a value from an iterator. Read more

impl<'a, A> IntoIterator for &'a OrdSet<A> where
    A: 'a + Ord + Clone
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

impl<A> IntoIterator for OrdSet<A> where
    A: Ord + Clone
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

impl<'s, 'a, A: ?Sized, OA> From<&'s OrdSet<&'a A>> for OrdSet<OA> where
    A: ToOwned<Owned = OA> + Ord,
    OA: Borrow<A> + Ord + Clone
[src]

Performs the conversion.

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

Performs the conversion.

impl<A: Ord + Clone> From<Vec<A>> for OrdSet<A>
[src]

Performs the conversion.

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

Performs the conversion.

impl<A: Eq + Hash + Ord + Clone> From<HashSet<A>> for OrdSet<A>
[src]

Performs the conversion.

impl<'a, A: Eq + Hash + Ord + Clone> From<&'a HashSet<A>> for OrdSet<A>
[src]

Performs the conversion.

impl<A: Ord + Clone> From<BTreeSet<A>> for OrdSet<A>
[src]

Performs the conversion.

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

Performs the conversion.

impl<A: Hash + Eq + Ord + Clone, S: BuildHasher> From<HashSet<A, S>> for OrdSet<A>
[src]

Performs the conversion.

impl<'a, A: Hash + Eq + Ord + Clone, S: BuildHasher> From<&'a HashSet<A, S>> for OrdSet<A>
[src]

Performs the conversion.

impl<A, S> From<OrdSet<A>> for HashSet<A, S> where
    A: Ord + Hash + Eq + Clone,
    S: BuildHasher + Default
[src]

Performs the conversion.

impl<'a, A, S> From<&'a OrdSet<A>> for HashSet<A, S> where
    A: Ord + Hash + Eq + Clone,
    S: BuildHasher + Default
[src]

Performs the conversion.

Auto Trait Implementations

impl<A> Send for OrdSet<A> where
    A: Send + Sync

impl<A> Sync for OrdSet<A> where
    A: Send + Sync