`CCBV`

Imperative Bitvectors.

A bitvector is stored in some form of internal array (on the heap). Is it a bit similar to a more storage-efficient version of ```
bool
CCVector.vector
```

, with additional operations.

**BREAKING CHANGES** since 1.2: size is now stored along with the bitvector. Some functions have a new signature.

The size of the bitvector used to be rounded up to the multiple of 30 or 62. In other words some functions such as `iter`

would iterate on more bits than what was originally asked for. This is not the case anymore.

`val empty : unit -> t`

Empty bitvector. Length is 0.

`val create : size:int -> bool -> t`

Create a bitvector of given size, with given default value. Length of result is `size`

.

`val init : int -> (int -> bool) -> t`

`init len f`

initializes a bitvector of length `len`

, where bit `i`

is true iff `f i`

is.

`val cardinal : t -> int`

Number of bits set to one, seen as a set of bits.

`val length : t -> int`

Size of underlying bitvector. This is not related to the underlying implementation. Changed at 1.2

`val capacity : t -> int`

The number of bits this bitvector can store without resizing.

`val resize : t -> int -> unit`

Resize the BV so that it has the specified length. This can grow the underlying array, but it will not shrink it, to minimize memory traffic.

`val resize_minimize_memory : t -> int -> unit`

Same as `resize`

, but this can also shrink the underlying array if this reduces the size.

`val is_empty : t -> bool`

Are there any true bits?

`val set : t -> int -> unit`

Set i-th bit, extending the bitvector if needed.

`val get : t -> int -> bool`

Is the i-th bit true? Return false if the index is too high.

`val reset : t -> int -> unit`

Set i-th bit to 0, extending the bitvector if needed.

`val set_bool : t -> int -> bool -> unit`

Set or reset `i`

-th bit.

`val flip : t -> int -> unit`

Flip i-th bit, extending the bitvector if needed.

`val clear : t -> unit`

Set every bit to 0. Does not change the length.

`val clear_and_shrink : t -> unit`

Set every bit to 0, and set length to 0.

`val iter : t -> (int -> bool -> unit) -> unit`

Iterate on all bits.

`val iter_true : t -> (int -> unit) -> unit`

Iterate on bits set to 1.

`val to_list : t -> int list`

List of indexes that are true.

`val to_sorted_list : t -> int list`

Same as `to_list`

, but also guarantees the list is sorted in increasing order.

`val of_list : int list -> t`

From a list of true bits.

The bits are interpreted as indices into the returned bitvector, so the final bitvector `bv`

will have `length bv`

equal to 1 more than max of list indices.

`val first : t -> int option`

First set bit, or return `None`

. Changed type at 1.2

`val first_exn : t -> int`

First set bit, or

`val filter : t -> (int -> bool) -> unit`

`filter bv p`

only keeps the true bits of `bv`

whose `index`

satisfies `p index`

. Length is unchanged.

`val negate_self : t -> unit`

`negate_self t`

flips all of the bits in `t`

. Length is unchanged.

`union_into ~into bv`

sets `into`

to the union of itself and `bv`

. Also updates the length of `into`

to be at least `length bv`

.

`inter_into ~into bv`

sets `into`

to the intersection of itself and `bv`

. Also updates the length of `into`

to be at most `length bv`

.

After executing:

`length ~into' = min (length into) (length bv)`

.`for all i: get into' ==> get into i /\ get bv i`

`union bv1 bv2`

returns the union of the two sets. The length of the result is the max of the inputs' lengths.

`inter bv1 bv2`

returns the intersection of the two sets. The length of the result is the min of the inputs' lengths.

`diff_into ~into t`

modifies `into`

with only the bits set but not in `t`

.

`val select : t -> 'a array -> 'a list`

`select arr bv`

selects the elements of `arr`

whose index corresponds to a true bit in `bv`

. If `bv`

is too short, elements of `arr`

with too high an index cannot be selected and are therefore not selected.

`val selecti : t -> 'a array -> ('a * int) list`

Same as `select`

, but selected elements are paired with their indexes.

Bitwise comparison, including the size (`equal a b`

implies `length a=length b`

).

`val pp : Stdlib.Format.formatter -> t -> unit`

Print the bitvector as a string of bits.