module 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 Map
. See the
documentation in core_map.mli for a description of the approach.
type ('elt, 'cmp)
t
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
val is_empty : ('a, 'b) t -> bool
val mem : ('a, 'b) t -> 'a -> bool
val add : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
val remove : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
val union : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
val union_list : comparator:('a, 'cmp) Comparator.t ->
('a, 'cmp) t list -> ('a, 'cmp) t
val inter : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
val diff : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
val compare_direct : ('a, 'cmp) t -> ('a, 'cmp) t -> int
val equal : ('a, 'cmp) t -> ('a, 'cmp) t -> bool
val exists : ('a, 'b) t -> f:('a -> bool) -> bool
val for_all : ('a, 'b) t -> f:('a -> bool) -> bool
val count : ('a, 'b) t -> f:('a -> bool) -> int
val find : ('a, 'b) t -> f:('a -> bool) -> 'a option
val find_map : ('a, 'c) t -> f:('a -> 'b option) -> 'b option
val find_exn : ('a, 'b) t -> f:('a -> bool) -> 'a
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
.val remove_index : ('a, 'cmp) t -> int -> ('a, 'cmp) 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
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
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
val fold : ('a, 'b) t -> init:'accum -> f:('accum -> 'a -> 'accum) -> 'accum
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
val iter : ('a, 'b) t -> f:('a -> unit) -> unit
val iter2 : ('a, 'cmp) t ->
('a, 'cmp) t ->
f:([ `Both of 'a * 'a | `Left of 'a | `Right of 'a ] -> unit) -> unit
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
Set.to_list
.val min_elt : ('a, 'b) t -> 'a option
val min_elt_exn : ('a, 'b) t -> 'a
val max_elt : ('a, 'b) t -> 'a option
val max_elt_exn : ('a, 'b) t -> 'a
val choose : ('a, 'b) t -> 'a option
None
if the set is empty.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 Poly:sig
..end
with type ('a, 'b) set := ('a, 'b) t
module type Elt = Core_set_intf.Elt
module type Elt_binable = Core_set_intf.Elt_binable
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
module Make:
module Make_using_comparator:
module Make_binable:
module Make_binable_using_comparator:functor (
Elt
:
Comparator.S_binable
) ->
S_binable
with type Elt.t = Elt.t
with type Elt.comparator = Elt.comparator
val compare : ('elt -> 'elt -> int) ->
('cmp -> 'cmp -> int) ->
('elt, 'cmp) t -> ('elt, 'cmp) t -> int
find_index t i
returns the i
th smallest element of t
in O(log n) time. The
smallest element has i = 0
.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.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
.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
.Set.to_list
.None
if the set is empty.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.