Construct an empty set.

Construct a set with a single value.

Examples

let set = OrdSet::unit(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());

Test whether two sets refer to the same content in memory.

This is true if the two sides are references to the same set, or if the two sets refer to the same root node.

This would return true if you’re comparing a set to itself, or if you’re comparing a set to a fresh clone of itself.

Time: O(1)

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

Get the smallest value in a set.

If the set is empty, returns None.

Time: O(log n)

Get the largest value in a set.

If the set is empty, returns None.

Time: O(log n)

Create an iterator over the contents of the set.

Create an iterator over a range inside the set.

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

Get the closest smaller value in a set to a given value.

If the set contains the given value, this is returned. Otherwise, the closest value in the set smaller than the given value is returned. If the smallest value in the set is larger than the given value, None is returned.

Examples

let set = ordset![1, 3, 5, 7, 9];
assert_eq!(Some(&5), set.get_prev(&6));

Get the closest larger value in a set to a given value.

If the set contains the given value, this is returned. Otherwise, the closest value in the set larger than the given value is returned. If the largest value in the set is smaller than the given value, None is returned.

Examples

let set = ordset![1, 3, 5, 7, 9];
assert_eq!(Some(&5), set.get_next(&4));

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 m) where m is the size of the other set

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 m) where m is the size of the other set

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)

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 symmetric difference between two sets.

This is an alias for the symmetric_difference method.

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 symmetric 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.symmetric_difference(set2));

Construct the relative complement between two sets, that is the set of values in self that do not occur in other.

Time: O(m log n) where m is the size of the other set

Examples

let set1 = ordset!{1, 2};
let set2 = ordset!{2, 3};
let expected = ordset!{1};
assert_eq!(expected, set1.relative_complement(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));

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)