Module BitMaskSet.Make
Functor building an implementation of a BitMaskSet for a given BitMask
. Normally, the result of this functor will be constrained to S
as:
module BMSet =
struct
type elt = B0 | B1 | ...
include BitMaskSet.Make(struct ... end)
end
and the signature may be given as:
module BMSet :
sig
type elt = B0 | B1 | ...
include BitMaskSet.S with type elt := elt
with type storage = ...
with type t = private ...
end
Note that S
does not include create
, allowing internal code to create the bitmasks directly but forcing external code to use add
, singleton
or of_list
. This pattern allows you to guarantee that bitmasks will never include invalid bits.
Parameters
Signature
type storage
= Mask.storage
The underlying storage type.
type t
= Mask.storage
The type of bitmasks. This is separate from
storage
as it will typically be exposed as aprivate
type.
val create : storage -> t
Creates a bitmask from the storage type (this operation is simply the identity function).
val invalid : Mask.storage -> Mask.storage
invalid mask
returns a mask where only the bits which are invalid remain set. The handling of invalid bits in the subsequent functions is a compromise between performance and type safety. In general, invalid bits are only ignored if they must ignored to maintain type safety: for use cases where the invalid bits should be ignored, use this function to remove them from the bit mask (e.g.diff (create x) (invalid x)
).
val empty : Mask.storage
The empty bitmask.
val is_empty : Mask.storage -> bool
Tests whether a bitmask is empty or not (includes invalid bits).
val mem : Mask.t -> Mask.storage -> bool
mem x s
tests whetherx
is set ins
.
val add : Mask.t -> Mask.storage -> Mask.storage
add x s
returns a bitmask containing all the elements ofs
withx
set. Ifx
was already set ins
,s
is returned unchanged.
val singleton : Mask.t -> Mask.storage
singleton x
returns the bitmask with onlyx
set.
val remove : Mask.t -> Mask.storage -> Mask.storage
remove x s
returns a bitmask containing all the elements ofs
withx
not set. Ifx
was not set ins
,s
is returned unchanged.
val union : Mask.storage -> Mask.storage -> Mask.storage
Bitmask union (invalid bits are included).
val inter : Mask.storage -> Mask.storage -> Mask.storage
Bitmask intersection (invalid bits are included).
val disjoint : Mask.storage -> Mask.storage -> bool
disjoint a b
is true ifa
andb
have no elements in common. The presence of invalid bits may make two otherwise disjoint sets intersecting.- since
- 1.2.0
val diff : Mask.storage -> Mask.storage -> Mask.storage
Bitmask difference (invalid bits are included).
val compare : Mask.storage -> Mask.storage -> int
Total ordering between bitmasks. The presence of differing invalid bits may make two otherwise identical bitmasks differ.
val equal : Mask.storage -> Mask.storage -> bool
equal s1 s2
tests whether the bitmaskss1
ands2
are equal, that is, contain the same set elements. The presence of differing invalid bits may make two otherwise identical bitmasks differ.
val subset : Mask.storage -> Mask.storage -> bool
subset s1 s2
tests whether the bitmasks1
is a subset of the bitmasks2
(invalid bits are included).
val iter : (Mask.t -> unit) -> Mask.storage -> unit
iter f s
appliesf
in turn to all elements ofs
. The elements ofs
are presented tof
in increasing order with respect to the bit number (i.e. the constructor position within typeMask.t
).
val map : (Mask.t -> Mask.t) -> Mask.storage -> Mask.storage
map f s
is the bitmask whose elements aref a0
,f a1
...f aN
, wherea0
,a1
...aN
are the elements ofs
. The elements are passed tof
in increasing order with respect to the bit number (i.e. the constructor position within typeMask.t
).If no element of
s
is changed byf
,s
is returned unchanged.- since
- 1.1.0
val filter_map : (Mask.t -> Mask.t option) -> Mask.storage -> Mask.storage
filter_map f s
is the bitmask of allv
such thatf x = Some v
for some bitx
ofs
.If no element of
s
is changed byf
,s
is returned unchanged.- since
- 1.3.0
val fold : (Mask.t -> 'a -> 'a) -> Mask.storage -> 'a -> 'a
fold f s a
computes(f xN ... (f x2 (f x1 a))...)
, wherex1 ... xN
are the elements ofs
, in increasing order with respect to the bit number (i.e. the constructor position within typeMask.t
).
val for_all : (Mask.t -> bool) -> Mask.storage -> bool
for_all p s
checks if all elements of the bitmask satisfy the predicatep
.
val exists : (Mask.t -> bool) -> Mask.storage -> bool
exists p s
checks if at least one element of the bitmask satisfies the predicatep
.
val filter : (Mask.t -> bool) -> Mask.storage -> Mask.storage
filter p s
returns the bitmask of all elements ins
that satisfy the predicatep
.
val partition : (Mask.t -> bool) -> Mask.storage -> Mask.storage * Mask.storage
partition p s
returns a pair of bitmasks(s1, s2)
, wheres1
is the bitmask of all elements ofs
that satisfy the predicatep
, ands2
is the bitmask of all the elements ofs
that do not satisfyp
.s2
will not contain any invalid bits present ins
.
val cardinal : Mask.storage -> int
Return the number of bits which are set in the
bitmask
(does not include invalid bits).
val elements : Mask.storage -> Mask.t list
Return the list of all elements of the given bitmask. The returned list is sorted in increasing order with respect to the bit number (i.e. the constructor position within type
Mask.t
).
val min_elt : Mask.storage -> Mask.t
Return the smallest element of the given bitmask (with respect to the bit number, i.e. the constructor position within type
Mask.t
) or raiseNot_found
if the bitmask is empty.
val min_elt_opt : Mask.storage -> Mask.t option
Return the smallest element of the given bitmask (with respect to the bit number, i.e. the constructor position within type
Mask.t
) orNone
if the bitmask is empty.- since
- 1.1.0
val max_elt : Mask.storage -> Mask.t
Same as
min_elt
, but returns the largest element of the given bitmask.
val max_elt_opt : Mask.storage -> Mask.t option
Same as
min_elt_opt
, but returns the largest element of the given bitmask.- since
- 1.1.0
val choose : Mask.storage -> Mask.t
Return one element of the given bitmask, or raise
Not_found
if the bitmask is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal bitmasks (differing invalid bits do not affect this function).
val choose_opt : Mask.storage -> Mask.t option
Return one element of the given bitmask, or
None
if the bitmask is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal bitmasks (differing invalid bits do not affect this function).- since
- 1.1.0
val split : Mask.t -> Mask.storage -> Mask.storage * bool * Mask.storage
split x s
returns a triple(l, present, r)
, wherel
is the bitmask of elements ofs
that are strictly less thanx
;r
is the bitmask of elements ofs
that are strictly greater thanx
andpresent
istrue
ifx
is set ins
.l
andr
will not contain invalid bits.
val find : Mask.t -> Mask.storage -> Mask.t
find x s
returnsx
ifx
is set ins
or raisesNot_found
if it is not.
val find_opt : Mask.t -> Mask.storage -> Mask.t option
find_opt x s
returnsSome x
ifx
is set ins
orNone
if it is not.- since
- 1.1.0
val find_first : (Mask.t -> bool) -> Mask.storage -> Mask.t
find_first f s
, wheref
is a monotonically increasing function, returns the smallest elemente
ofs
(with respect to the bit number, i.e. the constructor position within typeMask.t
) such thatf e
or raisesNot_found
if no such element exists.- since
- 1.1.0
val find_first_opt : (Mask.t -> bool) -> Mask.storage -> Mask.t option
find_first_opt f s
, wheref
is a monotonically increasing function, returns an option containing the smallest elemente
ofs
(with respect to the bit number, i.e. the constructor position within typeMask.t
) such thatf e
orNone
if no such element exists.- since
- 1.1.0
val find_last : (Mask.t -> bool) -> Mask.storage -> Mask.t
find_last f s
, wheref
is a monotonically increasing function, returns the largest elemente
ofs
(with respect to the bit number, i.e. the constructor position within typeMask.t
) such thatf e
or raisesNot_found
if no such element exists.- since
- 1.1.0
val find_last_opt : (Mask.t -> bool) -> Mask.storage -> Mask.t option
find_last_opt f s
, wheref
is a monotonically increasing function, returns an option containing the largest elemente
ofs
(with respect to the bit number, i.e. the constructor position within typeMask.t
) such thatf e
orNone
if no such element exists.- since
- 1.1.0
val of_list : Mask.t list -> t
of_list l
creates a bitmask from a list of elements. For bitmasks, this is just a convenience vs foldingadd
over the list.
val to_seq_from : Mask.t -> t -> Mask.t Stdlib.Seq.t
to_seq_from x s
returns the sequence of elements ofs
which are greater than or equal tox
.- since
- 1.2.0
val to_seq : t -> Mask.t Stdlib.Seq.t
to_seq s
returns the sequence of all elements of the given bitmask in increasing order with respect to the bit number (i.e. the constructor position within typeMask.t
).- since
- 1.2.0
val to_rev_seq : t -> Mask.t Stdlib.Seq.t
to_rev_seq s
returns the sequence of all elements of the given bitmask in decreasing order with respect to the bit number (i.e. the constructor within typeMask.t
).