Module type Set_intf.Set
type ('elt, 'cmp) t
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.
val compare : ('elt -> 'elt -> int) -> ('cmp -> 'cmp -> int) -> ('elt, 'cmp) t -> ('elt, 'cmp) t -> int
type ('k, 'cmp) comparator
= (module Base.Comparator.S with type comparator_witness = 'cmp and type t = 'k)
val invariants : (_, _) t -> bool
Tests internal invariants of the set data structure. Returns true on success.
val comparator_s : ('a, 'cmp) t -> ('a, 'cmp) comparator
Returns a first-class module that can be used to build other map/set/etc with the same notion of comparison.
val comparator : ('a, 'cmp) t -> ('a, 'cmp) Base.Comparator.t
val empty : ('a, 'cmp) comparator -> ('a, 'cmp) t
Creates an empty set based on the provided comparator.
val singleton : ('a, 'cmp) comparator -> 'a -> ('a, 'cmp) t
Creates a set based on the provided comparator that contains only the provided element.
val length : (_, _) t -> int
Returns the cardinality of the set.
O(1)
.
val is_empty : (_, _) t -> bool
is_empty t
istrue
ifft
is empty.O(1)
.
val mem : ('a, _) t -> 'a -> bool
mem t a
returnstrue
iffa
is int
.O(log n)
.
val add : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
add t a
returns a new set witha
added tot
, or returnst
ifmem t a
.O(log n)
.
val remove : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t
remove t a
returns a new set witha
removed fromt
ifmem t a
, or returnst
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 : ('a, 'cmp) comparator -> ('a, 'cmp) t list -> ('a, 'cmp) t
union c list
returns the union of all the sets inlist
. Thecomparator
argument is required for the case wherelist
is empty.O(max(List.length list, n log n))
, wheren
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 setst1
andt2
.O(length t1 + length t2)
.
val diff : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'cmp) t
diff t1 t2
computes the set differencet1 - t2
, i.e., the set containing all elements int1
that are not int2
.O(length t1 + length t2)
.
val symmetric_diff : ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'a) Base.Either.t Base.Sequence.t
symmetric_diff t1 t2
returns a sequence of changes betweent1
andt2
. It is intended to be efficient in the case wheret1
andt2
share a large amount of structure.
val compare_direct : ('a, 'cmp) t -> ('a, 'cmp) t -> int
compare_direct t1 t2
compares the setst1
andt2
. It returns the same result ascompare
, but unlike compare, doesn't require arguments to be passed in for the type parameters of the set.O(length t1 + length t2)
.
val hash_fold_direct : 'a Base.Hash.folder -> ('a, 'cmp) t Base.Hash.folder
Hash function: a building block to use when hashing data structures containing sets in them.
hash_fold_direct hash_fold_key
is compatible withcompare_direct
iffhash_fold_key
is compatible with(comparator s).compare
of the sets
being hashed.
val equal : ('a, 'cmp) t -> ('a, 'cmp) t -> bool
equal t1 t2
returnstrue
iff the two sets have the same elements.O(length t1 + length t2)
val exists : ('a, _) t -> f:('a -> bool) -> bool
exists t ~f
returnstrue
iff there exists ana
int
for whichf a
.O(n)
, but returns as soon as it finds ana
for whichf a
.
val for_all : ('a, _) t -> f:('a -> bool) -> bool
for_all t ~f
returnstrue
iff for alla
int
,f a
.O(n)
, but returns as soon as it finds ana
for whichnot (f a)
.
val count : ('a, _) t -> f:('a -> bool) -> int
count t
returns the number of elements oft
for whichf
returnstrue
.O(n)
.
val sum : (module Base.Container.Summable with type t = 'sum) -> ('a, _) t -> f:('a -> 'sum) -> 'sum
sum t
returns the sum off t
for eacht
in the set.O(n)
.
val find : ('a, _) t -> f:('a -> bool) -> 'a option
find t f
returns an element oft
for whichf
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, _) t -> f:('a -> 'b option) -> 'b option
find_map t f
returnsb
for somea
int
for whichf a = Some b
. If no sucha
exists, thenfind
returnsNone
.O(n)
, but returns as soon as a suitable element is found.
val find_exn : ('a, _) t -> f:('a -> bool) -> 'a
Like
find
, but throws an exception on failure.
val nth : ('a, _) t -> int -> 'a option
nth t i
returns thei
th smallest element oft
, inO(log n)
time. The smallest element hasi = 0
. ReturnsNone
ifi < 0
ori >= length t
.
val remove_index : ('a, 'cmp) t -> int -> ('a, 'cmp) t
remove_index t i
returns a version oft
with thei
th smallest element removed, inO(log n)
time. The smallest element hasi = 0
. Returnst
ifi < 0
ori >= length t
.
val is_subset : ('a, 'cmp) t -> of_:('a, 'cmp) t -> bool
is_subset t1 ~of_:t2
returns true ifft1
is a subset oft2
.
val are_disjoint : ('a, 'cmp) t -> ('a, 'cmp) t -> bool
are_disjoint t1 t2
returnstrue
iffis_empty (inter t1 t2)
, but is more efficient.
module Named : sig ... end
Named
allows the validation of subset and equality relationships between sets. ANamed.t
is a record of a set and a name, where the name is used in error messages, andNamed.is_subset
andNamed.equal
validate subset and equality relationships respectively.
val of_list : ('a, 'cmp) comparator -> 'a list -> ('a, 'cmp) t
The list or array given to
of_list
andof_array
need not be sorted.
val of_array : ('a, 'cmp) comparator -> 'a array -> ('a, 'cmp) t
val to_list : ('a, _) t -> 'a list
to_list
andto_array
produce sequences sorted in ascending order according to the comparator.
val to_array : ('a, _) t -> 'a array
val of_sorted_array : ('a, 'cmp) comparator -> 'a array -> ('a, 'cmp) t Base.Or_error.t
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)
.
val of_sorted_array_unchecked : ('a, 'cmp) comparator -> 'a array -> ('a, 'cmp) t
Similar to
of_sorted_array
, but without checking the input array.
val of_increasing_iterator_unchecked : ('a, 'cmp) comparator -> len:int -> f:(int -> 'a) -> ('a, 'cmp) t
of_increasing_iterator_unchecked c ~len ~f
behaves likeof_sorted_array_unchecked c (Array.init len ~f)
, with the additional restriction that a decreasing order is not supported. The advantage is not requiring you to allocate an intermediate array.f
will be called with 0, 1, ...len - 1
, in order.
val stable_dedup_list : ('a, _) comparator -> 'a list -> 'a list
stable_dedup_list
is here rather than in theList
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 ofComparator
and using the resultingstable_dedup_list
.
val map : ('b, 'cmp) comparator -> ('a, _) t -> f:('a -> 'b) -> ('b, 'cmp) t
map c t ~f
returns a new set created by applyingf
to every element int
. The returned set is based on the providedcomparator
.O(n log n)
.
val filter_map : ('b, 'cmp) comparator -> ('a, _) t -> f:('a -> 'b option) -> ('b, 'cmp) t
Like
map
, except elements for whichf
returnsNone
will be dropped.
val filter : ('a, 'cmp) t -> f:('a -> bool) -> ('a, 'cmp) t
filter t ~f
returns the subset oft
for whichf
evaluates to true.O(n log n)
.
val fold : ('a, _) 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_result : ('a, _) t -> init:'accum -> f:('accum -> 'a -> ('accum, 'e) Base.Result.t) -> ('accum, 'e) Base.Result.t
fold_result ~init ~f
folds over the elements of the set from smallest to largest, short circuiting the fold iff accum x
is anError _
val fold_until : ('a, _) t -> init:'accum -> f:('accum -> 'a -> ('accum, 'final) Continue_or_stop.t) -> finish:('accum -> 'final) -> 'final
fold_until t ~init ~f
is a short-circuiting version offold
. Iff
returnsStop _
the computation ceases and results in that value. Iff
returnsContinue _
, the fold will proceed.
val fold_right : ('a, _) t -> init:'accum -> f:('a -> 'accum -> 'accum) -> 'accum
Like
fold
, except that it goes from the largest to the smallest element.
val iter : ('a, _) t -> f:('a -> unit) -> unit
iter t ~f
callsf
on every element oft
, going in order from the smallest to largest.
val iter2 : ('a, 'cmp) t -> ('a, 'cmp) t -> f:([ `Left of 'a | `Right of 'a | `Both of 'a * 'a ] -> unit) -> unit
Iterate two sets side by side. Complexity is
O(m+n)
wherem
andn
are the sizes of the two input sets. As an example, with the inputs0; 1
and1; 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
if
a, b = partition_tf set ~f
thena
is the elements on whichf
producedtrue
, andb
is the elements on whichf
producesfalse
.
val min_elt : ('a, _) t -> 'a option
Returns the smallest element of the set.
O(log n)
.
val max_elt : ('a, _) t -> 'a option
Returns the largest element of the set.
O(log n)
.
val choose : ('a, _) t -> 'a option
returns an arbitrary element, or
None
if the set is empty.
val split : ('a, 'cmp) t -> 'a -> ('a, 'cmp) t * 'a option * ('a, 'cmp) t
split t x
produces a triple(t1, maybe_x, t2)
wheret1
is the set of elements strictly less thanx
,maybe_x
is the member (if any) oft
which compares equal tox
, andt2
is the set of elements strictly larger thanx
.
val group_by : ('a, 'cmp) t -> equiv:('a -> 'a -> bool) -> ('a, 'cmp) t list
if
equiv
is an equivalence predicate, thengroup_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 useSet.of_list
.
val to_sequence : ?order:[ `Increasing | `Decreasing ] -> ?greater_or_equal_to:'a -> ?less_or_equal_to:'a -> ('a, 'cmp) t -> 'a Base.Sequence.t
to_sequence t
converts the sett
to a sequence of the elements betweengreater_or_equal_to
andless_or_equal_to
inclusive in the order indicated byorder
. Ifgreater_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.
val binary_search : ('a, 'cmp) t -> compare:('a -> 'key -> int) -> [ `Last_strictly_less_than | `Last_less_than_or_equal_to | `Last_equal_to | `First_equal_to | `First_greater_than_or_equal_to | `First_strictly_greater_than ] -> 'key -> 'a option
binary_search t ~compare which elt
returns the element int
specified bycompare
andwhich
, if one exists.t
must be sorted in increasing order according tocompare
, wherecompare
andelt
dividet
into three (possibly empty) segments:| < elt | = elt | > elt |
binary_search
returns an element on the boundary of segments as specified bywhich
. See the diagram below next to thewhich
variants.binary_search
does not check thatcompare
orderst
, and behavior is unspecified ifcompare
doesn't ordert
. Behavior is also unspecified ifcompare
mutatest
.
val binary_search_segmented : ('a, 'cmp) t -> segment_of:('a -> [ `Left | `Right ]) -> [ `Last_on_left | `First_on_right ] -> 'a option
binary_search_segmented t ~segment_of which
takes asegment_of
function that dividest
into two (possibly empty) segments:| segment_of elt = `Left | segment_of elt = `Right |
binary_search_segmented
returns the element on the boundary of the segments as specified bywhich
:`Last_on_left
yields the last element of the left segment, while`First_on_right
yields the first element of the right segment. It returnsNone
if the segment is empty.binary_search_segmented
does not check thatsegment_of
segmentst
as in the diagram, and behavior is unspecified ifsegment_of
doesn't segmentt
. Behavior is also unspecified ifsegment_of
mutatest
.
module Merge_to_sequence_element : sig ... end
Produces the elements of the two sets between
greater_or_equal_to
andless_or_equal_to
inorder
, noting whether each element appears in the left set, the right set, or both. In the both case, both elements are returned, in case the caller can distinguish between elements that are equal to the sets' comparator. Runs in O(length t + length t').
val merge_to_sequence : ?order:[ `Increasing | `Decreasing ] -> ?greater_or_equal_to:'a -> ?less_or_equal_to:'a -> ('a, 'cmp) t -> ('a, 'cmp) t -> ('a, 'a) Merge_to_sequence_element.t Base.Sequence.t
module M : functor (Elt : sig ... end) -> sig ... end
M
is meant to be used in combination with OCaml applicative functor types:
include For_deriving with type ('a, 'b) t := ('a, 'b) t
module type Sexp_of_m = sig ... end
module type M_of_sexp = sig ... end
module type Compare_m = sig ... end
module type Equal_m = sig ... end
module type Hash_fold_m = Base.Hasher.S
val sexp_of_m__t : (module Sexp_of_m with type t = 'elt) -> ('elt, 'cmp) t -> Base.Sexp.t
val m__t_of_sexp : (module M_of_sexp with type comparator_witness = 'cmp and type t = 'elt) -> Base.Sexp.t -> ('elt, 'cmp) t
val compare_m__t : (module Compare_m) -> ('elt, 'cmp) t -> ('elt, 'cmp) t -> int
val equal_m__t : (module Equal_m) -> ('elt, 'cmp) t -> ('elt, 'cmp) t -> bool
val hash_fold_m__t : (module Hash_fold_m with type t = 'elt) -> Base.Hash.state -> ('elt, _) t -> Base.Hash.state
val hash_m__t : (module Hash_fold_m with type t = 'elt) -> ('elt, _) t -> int
module Poly : S_poly with type 'elt t = ('elt, Base.Comparator.Poly.comparator_witness) t
A polymorphic Set.
module Using_comparator : sig ... end
Using comparator is a similar interface as the toplevel of
Set
, except the functions take a~comparator:('elt, 'cmp) Comparator.t
where the functions at the toplevel ofSet
takes a('elt, 'cmp) comparator
.
Modules and module types for extending Set
For use in extensions of Base, like Core_kernel
.
module With_comparator = With_comparator
module With_first_class_module = With_first_class_module
module Without_comparator = Without_comparator
module type For_deriving = For_deriving
module type Accessors0 = Accessors0
module type Accessors1 = Accessors1
module type Accessors2 = Accessors2
module type Accessors2_with_comparator = Accessors2_with_comparator
module type Accessors_generic = Accessors_generic
module type Creators2_with_comparator = Creators2_with_comparator
module type Creators_and_accessors0 = Creators_and_accessors0
module type Creators_and_accessors1 = Creators_and_accessors1
module type Creators_and_accessors2 = Creators_and_accessors2
module type Creators_generic = Creators_generic