Tests internal invariants of the set data structure. Returns true on success.

Creates an empty set based on the provided comparator.

Creates a set based on the provided comparator that contains only the provided element.

Returns the number of elements in the set. O(1).

is_empty t is true iff t is empty. O(1).

mem t a returns true iff a is in t. O(log n).

add t a returns a new set with a added to t, or returns t if mem t a. O(log n).

remove t a returns a new set with a removed from t if mem t a, or returns t otherwise. O(log n).

union t1 t2 returns the union of the two sets. O(length t1 + length t2).

union ~comparator list returns the union of all the sets in list. The comparator argument is required for the case where list is empty. O(max(List.length list, n log n)), where n is the sum of sizes of the input sets.

inter t1 t2 computes the intersection of sets t1 and t2. O(log(length t1) + log(length t2)).

diff t1 t2 computes the set difference t1 - t2, i.e., the set containing all elements in t1 that are not in t2. O(log(length t1) + log(length t2)).

compare_direct t1 t2 compares the sets t1 and t2. It returns the same result as compare, but unlike compare, doesn't require arguments to be passed in for the type parameters of the set. O(length t1 + length t2).

equal t1 t2 returns true iff the two sets have the same elements. O(length t1 + length t2)

exists t ~f returns true iff there exists an a in t for which f a. O(n), but returns as soon as it finds an a for which f a.

for_all t ~f returns true iff for all a in t, f a. O(n), but returns as soon as it finds an a for which not (f a).

count t returns the number of elements of t for which f returns true. O(n).

sum t returns the sum of f t for each t in the set. O(n).

find t f returns an element of t for which f returns true, with no guarantee as to which element is returned. O(n), but returns as soon as a suitable element is found.

find_map t f returns b for some a in t for which f a = Some b. If no such a exists, then find returns None. O(n), but returns as soon as a suitable element is found.

Like find, but throws an exception on failure.

find_index t i returns the ith smallest element of t, in O(log n) time. The smallest element has i = 0. Returns None if i < 0 or i >= length t.

remove_index t i returns a version of t with the ith smallest element removed, in O(log n) time. The smallest element has i = 0. Returns t if i < 0 or i >= length t.

subset t1 t2 returns true iff t1 is a subset of t2.

The list or array given to of_list and of_array need not be sorted.

to_list and to_array produce sequences sorted in ascending order according to the comparator.

Create set from sorted array. The input must be sorted (either in ascending or descending order as given by the comparator) and contain no duplicates, otherwise the result is an error. The complexity of this function is O(n).

Similar to of_sorted_array, but without checking the input array.

stable_dedup_list is here rather than in the List module because the implementation relies crucially on sets, and because doing so allows one to avoid uses of polymorphic comparison by instantiating the functor at a different implementation of Comparator and using the resulting stable_dedup_list.

map ~comparator t ~f returns a new set created by applying f to every element in t. The returned set is based on the provided comparator. O(n log n).

Like map, except elements for which f returns None will be dropped.

filter t ~f returns the subset of t for which f evaluates to true. O(n log n).

fold t ~init ~f folds over the elements of the set from smallest to largest.

Like fold, except that it will terminate early, if f returns `Stop.

Like fold, except that it goes from the largest to the smallest element.

iter t ~f calls f on every element of t, going in order from the smallest to largest.

Iterate two sets side by side. Complexity is O(m+n) where m and n are the sizes of the two input sets. As an example, with the inputs 0; 1 and 1; 2, f will be called with `Left 0; `Both (1, 1); and `Right 2.

if a, b = partition_tf set ~f then a is the elements on which f produced true, and b is the elements on which f produces false.

Same as to_list.

Returns the smallest element of the set. O(log n).

Like min_elt, but throws an exception when given an empty set.

Returns the largest element of the set. O(log n).

Like max_elt, but throws an exception when given an empty set.

returns an arbitrary element, or None if the set is empty.

Like choose, but throws an exception on an empty set.

split t x produces a triple (t1, b, t2) where t1 is the set of elements strictly less than x, b = mem set x, and t2 is the set of elements strictly larger than x.

if equiv is an equivalence predicate, then group_by set ~equiv produces a list of equivalence classes (i.e., a set-theoretic quotient). E.g.,

      let chars = Set.of_list ['A'; 'a'; 'b'; 'c'] in
      let equiv c c' = Char.equal (Char.uppercase c) (Char.uppercase c') in
      group_by chars ~equiv

produces:

      Set.of_list['A';'a']; Set.singleton 'b'; Set.singleton 'c']

group_by runs in O(n^2) time, so if you have a comparison function, it's usually much faster to use Set.of_list.

to_sequence ?in_ t converts the set t to a sequence of the elements in the order indicated by in_.

Convert a set to or from a map. to_map takes a function to produce data for each key. Both functions run in O(n) time (assuming the function passed to to_map runs in constant time).