This module defines the Set
module for Core.Std
. We use "core_set" as the file
name rather than "set" to avoid conflicts with OCaml's standard set module.
This module uses the same organizational approach as Core_map
. See the
documentation in core_map.mli for a description of the approach.
Functions that construct a set take as an argument the comparator for the element type.
The type of a set. The first type parameter identifies the type of the element, and the second identifies the comparator, which determines the comparison function that is used for ordering elements in this set. Many operations (e.g., union), require that they be passed sets with the same element type and the same comparator type.
Tests internal invariants of the set data structure. Returns true on success.
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)
.
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.
symmetric_diff t1 t2
returns a sequence of changes between t1
and t2
. It is
intended to be efficient in the case where t1
and t2
share a large amount of
structure.
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)
.
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 i
th smallest element of t
, in O(log n)
time. The
smallest element has i = 0
. Returns None
if i < 0
or i >= length t
.
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)
.
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.
fold t ~init ~f
folds over the elements of the set from smallest to largest.
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 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 t
converts the set t
to a sequence of the elements between
greater_or_equal_to
and less_or_equal_to
inclusive in the order indicated by
order
. If greater_or_equal_to > less_or_equal_to
the sequence is empty. Cost is
O(log n) up front and amortized O(1) for each element produced.
greater_or_equal_to
and
less_or_equal_to
in order
, noting whether each element appears in the left set,
the right set, or both.
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).
Module Poly deals with sets that use OCaml's polymorphic comparison to compare elements.
Set
modules
bin_io
.
Make_using_comparator
builds a set from an element type that has a comparator.