Module Make.Bitset

A bitset is a compact structure to store a set of integers.

type Error_monad.error +=
  1. | Bitset_invalid_position of int
  2. | Bitset_invalid_input of string
val encoding : t Data_encoding.t
val empty : t

A bitset encoding the empty set.

val is_empty : t -> bool

is_empty i is true if i is empty.

val equal : t -> t -> bool

equal i j is true if i and j are identical.

val mem : t -> int -> bool Error_monad.tzresult

mem bitset i returns true iff i has been added in bitset.

This functions returns Invalid_position i if i is negative.

val add : t -> int -> t Error_monad.tzresult

add bitset i returns a new bitset which contains i in addition to the previous integers of bitset.

This functions returns Invalid_position i if i is negative.

val remove : t -> int -> t Error_monad.tzresult

remove bitset i returns a new bitset in which i is removed from bitset.

This functions returns Invalid_position i if i is negative.

val from_list : int list -> t Error_monad.tzresult

from_list positions folds add over the positions starting from empty. This function returns Invalid_position i if i is negative and appears in positions.

val to_list : t -> int list

to_list t returns the list of integers in the bitset.

val fill : length:int -> t Error_monad.tzresult

fill ~length is equivalent to setting all bits for positions in 0, length - 1 to one, or to from_list (0 -- size-1), or to from_z ((2 ^ length) - 1). But it's more efficient than folding on individual positions to set them.

The function returns Invalid_input "fill" if length is negative.

val inter : t -> t -> t

inter set_l set_r returns set which is result of the intersection of set_l and set_r.

val diff : t -> t -> t

diff set_l set_r returns a bitset containing integers in set_l that are not in set_r.

val occupied_size_in_bits : t -> int

occupied_size_in_bits bitset returns the current number of bits occupied by the bitset.

val cardinal : t -> int

cardinat bitset returns the number of elements in the bitsest.

val to_z : t -> Z.t

to_z t returns the sum of powers of two of the integers in the given bitset.

val from_z : Z.t -> t Error_monad.tzresult

from_z builds a bitset from its integer representation. Returns Invalid_input "from_z" if the given argument is negative.