Efficient bit sets.
A bitset is an array of boolean values that can be accessed with indexes like an array but provides a better memory usage (divided by Sys.word_size; either 32 or 64) for a very small speed trade-off. It can provide efficient storage of dense sets of nonnegative integers near zero. Sparse sets should use BatSet, sets with large ranges of contiguous ints should use BatISet.
val empty : unit -> tCreate an empty bitset of capacity 0, the bitset will automatically expand when needed.
Example: BitSet.empty ()
val create : int -> tCreate an empty bitset with at least an initial capacity (in number of bits).
Example: BitSet.create 0 = BitSet.empty ()
Invalid_argument on negative capacity
val create_full : int -> tCreate a full bitset with at least initial capacity (in number of bits). All the bit under the defined capacity will be set.
Example: BitSet.count (BitSet.create_full n) = n
Invalid_argument on negative capacity
Copy a bitset : further modifications of first one will not affect the copy.
Example:
let a = Bitset.create 8 in
let b = BitSet.copy a in
BitSet.set a 6;
BitSet.mem a 6 && not (BitSet.mem b 6)
val mem : t -> int -> boolmem s n returns true if nth-bit in the bitset s is set, or false otherwise.
Example: let a = BitSet.create_full 256 in not (BitSet.mem a 300)
Invalid_argument on negative index (n < 0)
val count : t -> intcount s returns the number of bits set in the bitset s. Also known as Population Count, or cardinal for sets.
Example: BitSet.count (BitSet.of_list [6;4;2;2;1]) = 4
val next_set_bit : t -> int -> int optionnext_set_bit s n returns Some m when m is the next set element with index greater than or equal n, or None if no such element exists (i.e. n is greater than the largest element)
More efficient than scanning with repeated BitSet.mem.
Invalid_argument on negative index (n < 0)
These functions modify an existing bitset.
val set : t -> int -> unitset s n sets the nth-bit in the bitset s to true.
Invalid_argument on negative index (n < 0)
val unset : t -> int -> unitunset s n sets the nth-bit in the bitset s to false.
Invalid_argument on negative index (n < 0)
val put : t -> bool -> int -> unitput s v n sets the nth-bit in the bitset s to v.
Invalid_argument on negative index (n < 0)
val toggle : t -> int -> unittoggle s n changes the nth-bit value in the bitset s.
Invalid_argument on negative index (n < 0)
differentiate_sym s t sets s to the symmetrical difference of the sets s and t.
These functions return a new bitset that shares nothing with the input bitset. This is not as efficient as the in-place update.
add n s returns a copy of s with bit n true.
Invalid_argument on negative index (n < 0)
remove n s returns a copy of s with bit n false.
Invalid_argument on negative index (n < 0)
val print : 'a BatInnerIO.output -> t -> unitof_enum ~cap e builds a bitset of capacity cap an enumeration of ints e.
Note: Performance of this function may be poor if enumeration is in increasing order and the max.
val of_list : ?cap:int -> int list -> tAs of_enum, but from a list
compare s1 s2 compares two bitsets using a lexicographic ordering. Highest bit indexes are compared first. The capacity of the bitsets is not important for this comparison, only the bits starting with the highest set bit and going down.
equal s1 s2 returns true if, and only if, all bits values in s1 are the same as in s2.
val ord : t -> t -> BatOrd.orderord s1 s2 returns BatOrd.Lt, BatOrd.Eq or BatOrd.Gt if compare s1 s2 is, respectively, < 0, 0 or > 0.
val capacity : t -> intInternals
capacity s returns the number of bits, both set and unset, stored in s. This is guaranteed to be larger than the largest element (set bit index) in s.