Abstract
Bitset module
A bitset data structure is an array of bits where a bit can be set or not set. If the bit is set then it is a member of the set otherwise it is not. The indexes of these bits can then be related to the indexes of another array.
nbs is assumed to be constant in the time complexities.
Synopsis
module type bitset = {
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| module mk_bitset | : | (I: integral) -> bitset | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Description
- ↑module type bitset
- ↑module int: integral
The integral module used in the definition of the bitset.
- ↑type t
The integral type used to construct the bitset.
- ↑type bitset [n]
The bitset type.
- ↑val nbs: i64
The number of bits for the chosen integral type.
- ↑val empty: (n: i64) -> bitset [(n - 1) / nbs + 1]
Makes a empty bitset of a given capacity.
Work: O(n)
Span: O(1)
- ↑val singleton: (n: i64) -> i64 -> bitset [(n - 1) / nbs + 1]
Makes a singleton bitset with a given capacity.
Work: O(n)
Span: O(1)
- ↑val is_empty [n]: bitset [(n - 1) / nbs + 1] -> bool
Checks if a bitset is empty.
Work: O(n)
Span: O(log n)
- ↑val insert [n]: i64 -> bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1]
Inserts a single bit in a bitset.
Work: O(1)
Span: O(1)
- ↑val delete [n]: i64 -> bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1]
Deletes a single bit in a bitset.
Work: O(1)
Span: O(1)
- ↑val member [n]: i64 -> bitset [(n - 1) / nbs + 1] -> bool
Checks if a bit is a member of a bitset.
Work: O(1)
Span: O(1)
- ↑val union [n]: bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1]
Bitset union.
Work: O(n)
Span: O(1)
- ↑val intersection [n]: bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1]
Bitset intersection.
Work: O(n)
Span: O(1)
- ↑val difference [n]: bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1]
Bitset difference.
Work: O(n)
Span: O(1)
- ↑val is_subset [n]: bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1] -> bool
Checks if a bitset is a subset of another.
Work: O(n)
Span: O(1)
- ↑val complement [n]: bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1]
Finds the complement of a bitset.
Work: O(n)
Span: O(1)
- ↑val set_capacity [m]: (n: i64) -> bitset [(m - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1]
Sets the bitset capacity to a new value.
Work: O(n)
Span: O(1)
- ↑val size [n]: bitset [(n - 1) / nbs + 1] -> i64
Computes the size of the set i.e. the population count.
Work: O(n)
Span: O(log n)
- ↑val == [n]: bitset [(n - 1) / nbs + 1] -> bitset [(n - 1) / nbs + 1] -> bool
If a two bitsets contains the same bits then they are equal.
Work: O(n)
Span: O(log n)
- ↑val from_array [m]: (n: i64) -> [m]i64 -> bitset [(n - 1) / nbs + 1]
Convert an array of indices to a bitset.
Work: O(n × m)
Span: O(log m)
- ↑val from_bit_array [m]: (n: i64) -> (arr: [m]u64) -> bitset [(n - 1) / nbs + 1]
Converts an array of integral types to a bitset.
Work: O(1)
Span: O(1)
- ↑val to_array [n]: bitset [(n - 1) / nbs + 1] -> []i64
Convert a bitset to an array of indices to a bitset.
Work: O(n)
Span: O(log n)