package colibri2
Functor building an implementation of the set structure given a totally ordered type.
Parameters
module M : Map_intf.MapUnit
Signature
The module of association tables over elt
.
type elt = M.key
The type of set elements.
type t = unit M.t
The type of sets of type elt
.
val hash_fold_t : t Base.Hash.folder
val empty : t
The empty set.
val is_empty : t -> bool
Test whether a set is empty or not.
merge f s1 s2
computes a set whose elts is a subset of elts of s1
and of s2
. The presence of each such element is determined with the function f
.
iter f s
applies f
to all elements of s
. The elements are passed to f
in increasing order with respect to the ordering over the type of the elts.
fold f s a
computes (f eN ... (f e1 a)...)
, where e1 ... eN
are the element of s
in increasing order.
for_all p s
checks if all the elements of s
satisfy the predicate p
.
exists p s
checks if at least one element of s
satisfies the predicate p
.
filter p s
returns the set with all the elements of s
that satisfy predicate p
.
partition p s
returns a pair of sets (s1, s2)
, where s1
contains all the elements of s
that satisfy the predicate p
, and s2
is the map with all the elements of s
that do not satisfy p
.
val cardinal : t -> int
Return the number of elements in a set.
Return the list of all elements of the given set. The returned list is sorted in increasing order.
Return the smallest element of the given set or raise Not_found
if the set is empty.
Return the largest element of the given set or raise Not_found
if the set is empty.
Return one element of the given set, or raise Not_found
if the set is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal sets.
split x s
returns a triple (l, mem, r)
, where l
is the set with all the elements of s
that are strictly less than x
; r
is the set with all the elements of s
that are strictly greater than x
; mem
is true
if x
belongs to s
and false
otherwise.
change f x s
returns a set containing the same elements as s
, except x
which is added to s
if f (mem x s)
returns true
and removed otherwise.
fold2_inter f s1 s2 a
computes (f eN ... (f e1 a) ...)
, where e1 ... eN
are the elements of inter s1 s2
in increasing order.
fold2_union f s1 s2 a
computes (f eN ... (f e1 a) ...)
, where e1 ... eN
are the elements of union s1 s2
in increasing order.
translate f s
translates the elements in the set s
by the function f
. f
must be strictly monotone on the elements of s
. Otherwise it raises invalid_arg
add_new e x s
adds x
to s
if s
does not contain x
, and raises e
otherwise.
val is_num_elt : int -> t -> bool
check if the map has the given number of elements