# Struct im::ordset::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]

#### `pub fn new() -> Self`[src]

Construct an empty set.

#### `pub fn singleton(a: A) -> Self`[src]

Construct a set with a single value.

# Examples

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

#### `pub fn is_empty(&self) -> bool`[src]

Test whether a set is empty.

Time: O(1)

# Examples

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

#### `pub fn len(&self) -> usize`[src]

Get the size of a set.

Time: O(1)

# Examples

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

#### `pub fn get_min(&self) -> Option<&A>`[src]

Get the smallest value in a set.

If the set is empty, returns `None`.

#### `pub fn get_max(&self) -> Option<&A>`[src]

Get the largest value in a set.

If the set is empty, returns `None`.

#### ⓘImportant traits for DiffIter<'a, A>### Important traits for DiffIter<'a, A> `impl<'a, A> Iterator for DiffIter<'a, A> where    A: 'a + Ord + Clone + PartialEq,  type Item = DiffItem<'a, A>;``pub fn diff<'a>(&'a self, other: &'a Self) -> DiffIter<A>`[src]

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)

#### `pub fn contains<BA: ?Sized>(&self, a: &BA) -> bool where    BA: Ord,    A: Borrow<BA>, `[src]

Test if a value is part of a set.

Time: O(log n)

#### `pub fn insert(&mut self, a: A) -> Option<A>`[src]

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

#### `pub fn remove<BA: ?Sized>(&mut self, a: &BA) -> Option<A> where    BA: Ord,    A: Borrow<BA>, `[src]

Remove a value from a set.

Time: O(log n)

#### `pub fn remove_min(&mut self) -> Option<A>`[src]

Remove the smallest value from a set.

Time: O(log n)

#### `pub fn remove_max(&mut self) -> Option<A>`[src]

Remove the largest value from a set.

Time: O(log n)

#### `pub fn update(&self, a: A) -> Self`[src]

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

Time: O(log n)

# Examples

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

#### `pub fn without<BA: ?Sized>(&self, a: &BA) -> Self where    BA: Ord,    A: Borrow<BA>, `[src]

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

Time: O(log n)

#### `pub fn without_min(&self) -> (Option<A>, Self)`[src]

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

Time: O(log n)

#### `pub fn without_max(&self) -> (Option<A>, Self)`[src]

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

Time: O(log n)

#### `pub fn union(self, other: Self) -> Self`[src]

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

#### `pub fn unions<I>(i: I) -> Self where    I: IntoIterator<Item = Self>, `[src]

Construct the union of multiple sets.

Time: O(n log n)

#### `pub fn difference(self, other: Self) -> Self`[src]

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

#### `pub fn intersection(self, other: Self) -> Self`[src]

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

#### `pub fn is_subset<RS>(&self, other: RS) -> bool where    RS: Borrow<Self>, `[src]

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)

#### `pub fn is_proper_subset<RS>(&self, other: RS) -> bool where    RS: Borrow<Self>, `[src]

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)

#### `pub fn split<BA: ?Sized>(self, split: &BA) -> (Self, Self) where    BA: Ord,    A: Borrow<BA>, `[src]

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)

#### `pub fn split_member<BA: ?Sized>(self, split: &BA) -> (Self, bool, Self) where    BA: Ord,    A: Borrow<BA>, `[src]

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)

#### `pub fn take(&self, n: usize) -> Self`[src]

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

Time: O(n)

#### `pub fn skip(&self, n: usize) -> Self`[src]

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]

#### `fn clone(&self) -> Self`[src]

Returns a copy of the value. Read more

#### `fn clone_from(&mut self, source: &Self)`1.0.0[src]

Performs copy-assignment from `source`. Read more

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

#### `fn eq(&self, other: &Self) -> bool`[src]

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

#### `fn ne(&self, other: &Rhs) -> bool`1.0.0[src]

This method tests for `!=`.

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

#### `fn partial_cmp(&self, other: &Self) -> Option<Ordering>`[src]

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

#### `fn lt(&self, other: &Rhs) -> bool`1.0.0[src]

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

#### `fn le(&self, other: &Rhs) -> bool`1.0.0[src]

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

#### `fn gt(&self, other: &Rhs) -> bool`1.0.0[src]

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

#### `fn ge(&self, other: &Rhs) -> bool`1.0.0[src]

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]

#### `fn cmp(&self, other: &Self) -> Ordering`[src]

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

#### `fn max(self, other: Self) -> Self`1.21.0[src]

Compares and returns the maximum of two values. Read more

#### `fn min(self, other: Self) -> Self`1.21.0[src]

Compares and returns the minimum of two values. Read more

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

#### `fn hash<H>(&self, state: &mut H) where    H: Hasher, `[src]

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

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

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

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

#### `fn default() -> Self`[src]

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

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

#### `type Output = OrdSet<A>`

The resulting type after applying the `+` operator.

#### `fn add(self, other: Self) -> Self::Output`[src]

Performs the `+` operation.

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

#### `type Output = OrdSet<A>`

The resulting type after applying the `+` operator.

#### `fn add(self, other: Self) -> Self::Output`[src]

Performs the `+` operation.

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

#### `type Output = OrdSet<A>`

The resulting type after applying the `*` operator.

#### `fn mul(self, other: Self) -> Self::Output`[src]

Performs the `*` operation.

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

#### `type Output = OrdSet<A>`

The resulting type after applying the `*` operator.

#### `fn mul(self, other: Self) -> Self::Output`[src]

Performs the `*` operation.

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

#### `fn sum<I>(it: I) -> Self where    I: Iterator<Item = Self>, `[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]

#### `fn extend<I>(&mut self, iter: I) where    I: IntoIterator<Item = R>, `[src]

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

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

#### `fn fmt(&self, f: &mut Formatter) -> Result<(), Error>`[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]

#### `fn from_iter<T>(i: T) -> Self where    T: IntoIterator<Item = R>, `[src]

Creates a value from an iterator. Read more

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

#### `type Item = &'a A`

The type of the elements being iterated over.

#### `type IntoIter = Iter<'a, A>`

Which kind of iterator are we turning this into?

#### `fn into_iter(self) -> Self::IntoIter`[src]

Creates an iterator from a value. Read more

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

#### `type Item = A`

The type of the elements being iterated over.

#### `type IntoIter = ConsumingIter<A>`

Which kind of iterator are we turning this into?

#### `fn into_iter(self) -> Self::IntoIter`[src]

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]

#### `fn from(set: &OrdSet<&A>) -> Self`[src]

Performs the conversion.

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

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

Performs the conversion.

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

#### `fn from(vec: Vec<A>) -> Self`[src]

Performs the conversion.

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

#### `fn from(vec: &Vec<A>) -> Self`[src]

Performs the conversion.

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

#### `fn from(hash_set: HashSet<A>) -> Self`[src]

Performs the conversion.

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

#### `fn from(hash_set: &HashSet<A>) -> Self`[src]

Performs the conversion.

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

#### `fn from(btree_set: BTreeSet<A>) -> Self`[src]

Performs the conversion.

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

#### `fn from(btree_set: &BTreeSet<A>) -> Self`[src]

Performs the conversion.

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

#### `fn from(hashset: HashSet<A, S>) -> Self`[src]

Performs the conversion.

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

#### `fn from(hashset: &HashSet<A, S>) -> Self`[src]

Performs the conversion.

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

#### `fn from(ordset: OrdSet<A>) -> Self`[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]

#### `fn from(ordset: &OrdSet<A>) -> Self`[src]

Performs the conversion.