module Core_set:sig
..end
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.
type ('elt, 'cmp)
t
Core_set.union
), require
that they be passed sets with the same element type and the same comparator type.module Tree:sig
..end
val invariants : ('a, 'b) t -> bool
val comparator : ('a, 'cmp) t -> ('a, 'cmp) Comparator.t
val empty : comparator:('a, 'cmp) Comparator.t -> ('a, 'cmp) t
val singleton : comparator:('a, 'cmp) Comparator.t -> 'a -> ('a, 'cmp) t
val length : ('a, 'b) t -> int
O(1)
.val is_empty : ('a, 'b) t -> bool
is_empty t
is true
iff t
is empty. O(1)
.val mem : ('a, 'b) t -> 'a -> bool
mem t a
returns true
iff a
is in t
. O(log n)
.val add : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
add t a
returns a new set with a
added to t
, or returns t
if mem t a
.
O(log n)
.val remove : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
remove t a
returns a new set with a
removed from t
if mem t a
, or returns t
otherwise. O(log n)
.val union : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
union t1 t2
returns the union of the two sets. O(length t1 + length t2)
.val union_list : comparator:('a, 'cmp) Comparator.t ->
('a, 'cmp) t list -> ('a, 'cmp) t
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.val inter : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
inter t1 t2
computes the intersection of sets t1
and t2
. O(log(length t1) +
log(length t2))
.val diff : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
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))
.val compare_direct : ('a, 'cmp) t -> ('a, 'cmp) t -> int
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)
.val equal : ('a, 'cmp) t -> ('a, 'cmp) t -> bool
equal t1 t2
returns true
iff the two sets have the same elements. O(length t1 +
length t2)
val exists : ('a, 'b) t -> f:('a -> bool) -> bool
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
.val for_all : ('a, 'b) t -> f:('a -> bool) -> bool
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)
.val count : ('a, 'b) t -> f:('a -> bool) -> int
count t
returns the number of elements of t
for which f
returns true
.
O(n)
.val find : ('a, 'b) t -> f:('a -> bool) -> 'a option
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.val find_map : ('a, 'c) t -> f:('a -> 'b option) -> 'b option
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.val find_exn : ('a, 'b) t -> f:('a -> bool) -> 'a
find
, but throws an exception on failure.val find_index : ('a, 'b) t -> int -> 'a option
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
.val remove_index : ('a, 'cmp) t -> int -> ('a, 'cmp) t
remove_index t i
returns a version of t
with the i
th smallest element removed,
in O(log n)
time. The smallest element has i = 0
. Returns t
if i < 0
or
i >= length t
.val subset : ('a, 'cmp) t -> ('a, 'cmp) t -> bool
subset t1 t2
returns true iff t1
is a subset of t2
.val of_list : comparator:('a, 'cmp) Comparator.t -> 'a list -> ('a, 'cmp) t
of_list
and of_array
need not be sorted.val of_array : comparator:('a, 'cmp) Comparator.t -> 'a array -> ('a, 'cmp) t
val to_list : ('a, 'b) t -> 'a list
to_list
and to_array
produce sequences sorted in ascending order according to the
comparator.val to_array : ('a, 'b) t -> 'a array
val to_tree : ('a, 'cmp) t -> ('a, 'cmp) Tree.t
val of_tree : comparator:('a, 'cmp) Comparator.t ->
('a, 'cmp) Tree.t -> ('a, 'cmp) t
val of_sorted_array : comparator:('a, 'cmp) Comparator.t ->
'a array -> ('a, 'cmp) t Or_error.t
O(n)
.val of_sorted_array_unchecked : comparator:('a, 'cmp) Comparator.t -> 'a array -> ('a, 'cmp) t
of_sorted_array
, but without checking the input array.val stable_dedup_list : comparator:('a, 'b) Comparator.t -> 'a list -> 'a list
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
.val map : comparator:('b, 'cmp) Comparator.t ->
('a, 'c) t -> f:('a -> 'b) -> ('b, 'cmp) t
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)
.val filter_map : comparator:('b, 'cmp) Comparator.t ->
('a, 'c) t -> f:('a -> 'b option) -> ('b, 'cmp) t
val filter : ('a, 'cmp) t -> f:('a -> bool) -> ('a, 'cmp) t
filter t ~f
returns the subset of t
for which f
evaluates to true. O(n log
n)
.val fold : ('a, 'b) t -> init:'accum -> f:('accum -> 'a -> 'accum) -> 'accum
fold t ~init ~f
folds over the elements of the set from smallest to largest.val fold_until : ('a, 'b) t ->
init:'accum ->
f:('accum -> 'a -> [ `Continue of 'accum | `Stop of 'accum ]) -> 'accum
val fold_right : ('a, 'b) t -> init:'accum -> f:('a -> 'accum -> 'accum) -> 'accum
Core_set.fold
, except that it goes from the largest to the smallest element.val iter : ('a, 'b) t -> f:('a -> unit) -> unit
iter t ~f
calls f
on every element of t
, going in order from the smallest to
largest.val iter2 : ('a, 'cmp) t ->
('a, 'cmp) t ->
f:([ `Both of 'a * 'a | `Left of 'a | `Right of 'a ] -> unit) -> unit
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
.val partition_tf : ('a, 'cmp) t ->
f:('a -> bool) -> ('a, 'cmp) t * ('a, 'cmp) t
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
.val elements : ('a, 'b) t -> 'a list
Core_set.to_list
.val min_elt : ('a, 'b) t -> 'a option
O(log n)
.
Like Core_set.min_elt
, but throws an exception when given an empty set.
val min_elt_exn : ('a, 'b) t -> 'a
val max_elt : ('a, 'b) t -> 'a option
O(log n)
.
Like Core_set.max_elt
, but throws an exception when given an empty set.
val max_elt_exn : ('a, 'b) t -> 'a
val choose : ('a, 'b) t -> 'a option
None
if the set is empty.
Like Core_set.choose
, but throws an exception on an empty set.
val choose_exn : ('a, 'b) t -> 'a
val split : ('a, 'cmp) t ->
'a -> ('a, 'cmp) t * bool * ('a, 'cmp) t
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
.val group_by : ('a, 'cmp) t ->
equiv:('a -> 'a -> bool) -> ('a, 'cmp) t list
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.
Module Core_set.Poly
deals with sets that use OCaml's polymorphic comparison to compare
elements.
module Poly:sig
..end
with type ('a, 'b) set := ('a, 'b) t
Set
modulesmodule type Elt = Core_set_intf.Elt
module type Elt_binable = Core_set_intf.Elt_binable
bin_io
.
module type S =S0
with type ('a, 'b) set := ('a, 'b) t
with type ('a, 'b) tree := ('a, 'b) Tree.t
module type S_binable =S0_binable
with type ('a, 'b) set := ('a, 'b) t
with type ('a, 'b) tree := ('a, 'b) Tree.t
bin_io
.
module Make:
Make
builds a set from an element type that has a compare
function but doesn't
have a comparator.
module Make_binable:
module Make_using_comparator:functor (
Elt
:
sig
end
) ->
S
with type Elt.t = Elt.t
with type Elt.comparator_witness = Elt.comparator_witness
Make_using_comparator
builds a set from an element type that has a comparator.
module Make_binable_using_comparator:functor (
Elt
:
sig
type
t
include Comparator.S
val t_of_sexp :Sexplib.Sexp.t -> t
val sexp_of_t :t -> Sexplib.Sexp.t
val bin_t :t Bin_prot.Type_class.t
val bin_read_t :t Bin_prot.Read.reader
val __bin_read_t__ :(int -> t) Bin_prot.Read.reader
val bin_reader_t :t Bin_prot.Type_class.reader
val bin_size_t :t Bin_prot.Size.sizer
val bin_write_t :t Bin_prot.Write.writer
val bin_writer_t :t Bin_prot.Type_class.writer
end
) ->
S_binable
with type Elt.t = Elt.t
with type Elt.comparator_witness = Elt.comparator_witness
val compare : ('elt -> 'elt -> int) ->
('cmp -> 'cmp -> int) ->
('elt, 'cmp) t -> ('elt, 'cmp) t -> int
Tree.t
contains just the tree data structure that a set is based on, without
including the comparator. Accordingly, any operation on a Tree.t
must also take
as an argument the corresponding comparator.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)
.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.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
.remove_index t i
returns a version of t
with the i
th 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
.of_list
and of_array
need not be sorted.to_list
and to_array
produce sequences sorted in ascending order according to the
comparator.O(n)
.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)
.Core_set.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.Core_set.fold
, except that it will terminate early, if f
returns `Stop
.Core_set.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.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
.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
.Core_set.to_list
.O(log n)
.Core_set.min_elt
, but throws an exception when given an empty set.O(log n)
.Core_set.max_elt
, but throws an exception when given an empty set.None
if the set is empty.Core_set.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
.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.
Module Core_set.Poly
deals with sets that use OCaml's polymorphic comparison to compare
elements.
Set
modulesbin_io
.bin_io
.Make
builds a set from an element type that has a compare
function but doesn't
have a comparator. This generates a new comparator.
Make_binable
is similar, except the element and set types support bin_io
.
Make_using_comparator
builds a set from an element type that has a comparator.
Make_binable_using_comparator
is similar, except the element and set types support
bin_io
.