A resizable bitvector

Empty bitvector. Length is 0.

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

init len f initializes a bitvector of length len, where bit i is true iff f i is.

• since 3.9

Copy of bitvector.

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

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

The number of bits this bitvector can store without resizing.

• since 1.2

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.

• raises Invalid_argument

  on negative sizes.

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

• raises Invalid_argument

  on negative sizes.

• since 3.9

Are there any true bits?

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

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

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

Set or reset i-th bit.

• since 3.9

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

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

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

• since 3.9

Iterate on all bits.

Iterate on bits set to 1.

List of indexes that are true.

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

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.

First set bit, or return None. Changed type at 1.2

First set bit, or

• raises Not_found

  if all bits are 0.

• since 1.2

filter bv p only keeps the true bits of bv whose index satisfies p index. Length is unchanged.

negate_self t flips all of the bits in t. Length is unchanged.

• since 1.2

negate t returns a copy of t with all of the bits flipped. 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.

• since 1.2

diff t1 t2 returns those bits found in t1 but not in t2.

• since 1.2

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.

Same as select, but selected elements are paired with their indexes.

Bitwise comparison, including the size (equal a b implies length a=length b).

• since 3.5

Iterate over the true bits.

Build from true bits.

Print the bitvector as a string of bits.

• since 0.13