Module Tezos_base.Bitset

type t

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

type Tezos_error_monad.Error_monad.error +=
  1. | Invalid_position of int
  2. | Invalid_range of {
    1. pos : int;
    2. length : int;
    }
  3. | 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 Tezos_error_monad.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.

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 add_many : t -> int -> int -> t Tezos_error_monad.Error_monad.tzresult

add_many bitset i length returns a new bitset which contains i, i+1, ..., i+length-1 in addition to the previous integers of bitset.

This functions returns Invalid_range {pos = i; length} if i is negative or length is not positive.

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 remove_many : t -> int -> int -> t Tezos_error_monad.Error_monad.tzresult

remove_many bitset i length returns a new bitset in which i, i+1, ... i+length-1 are removed from bitset.

This functions returns Invalid_range {pos = i; length} if i is negative or length is not positive.

val shift_right : t -> offset:int -> t Tezos_error_monad.Error_monad.tzresult

shift_right bitset ~offset returns a new bitset bitset' such that for any i we have:

mem (i - offset) bitset' if and only if i >= offset and mem i bitset.

In other words, positions smaller than `offset` are removed and positions larger or equal than `offset` are decreased by `offset`.

This functions returns Invalid_input "shift_right" if offset is negative.

val from_list : int list -> t Tezos_error_monad.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 Tezos_error_monad.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.

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