gf2::BitSpan< Word >

A bit_span is a non-owning view of contiguous bits in a bit-store.
. More...

#include <BitSpan.h>

Public Member Functions
Constructors
	BitSpan (Word *data, u8 offset, usize size)
	Constructs a non-owning view over bits stored in contiguous words — a bit-span.
Required BitStore Concept Methods:
constexpr usize	size () const
	Returns the number of bits in the bit-span.
constexpr usize	words () const
	Returns the minimum number of words needed to hold the bits in the bit-span.
constexpr word_type	word (usize i) const
	Returns a "word"'s worth of bits from the bit-span.
constexpr void	set_word (usize i, word_type value)
	Sets a "word"'s worth of bits in the bit-span.
constexpr const Word *	store () const
	Returns a pointer to the first bit-span word in some underlying span of words (const version).
constexpr Word *	store ()
	Returns a pointer to the first bit-span word in some underlying span of words (non-const version).
constexpr u8	offset () const
	Returns the offset (in bits) of the first bit in the bit-span within the first bit-span word.
Bit Accessors:
constexpr bool	get (usize i) const
	Returns true if the bit at the given index i is set, false otherwise.
constexpr bool	operator[] (usize i) const
	Returns the boolean value of the bit element i.
constexpr bool	front () const
	Returns true if the first bit element is set, false otherwise.
constexpr bool	back () const
	Returns true if the last bit element is set, false otherwise.
Bit Mutators:
constexpr auto	set (usize i, bool value=true)
	Sets the bit-element i to the specified boolean value & returns this for chaining. The default value for value is true.
constexpr auto	operator[] (usize i)
	Returns a "reference" to the bit element i.
constexpr auto	flip (usize i)
	Flips the value of the bit-element i and returns this for chaining.
constexpr auto	swap (usize i0, usize i1)
	Swaps the bits in the bit-span at indices i0 and i1 and returns this for chaining.
Span Queries:
constexpr bool	is_empty () const
	Returns true if the bit-span is empty, false otherwise.
constexpr bool	any () const
	Returns true if at least one bit in the bit-span is set, false otherwise.
constexpr bool	all () const
	Returns true if all bits in the bit-span are set, false otherwise.
constexpr bool	none () const
	Returns true if no bits in the bit-span are set, false otherwise.
BitSpan Mutators:
auto	set_all (bool value=true)
	Sets the bits in the bit-span to the boolean value and returns a reference to this for chaining.
auto	flip_all ()
	Flips the value of the bits in the bit-span and returns a reference to this for chaining.
Copying into the BitSpan:
template<Unsigned Src>
constexpr auto	copy (Src src)
	Copies all the bits from any unsigned integral src value to this equal-sized bit-span and returns a reference to this for chaining.
template<typename Iter> requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>
constexpr void	copy (Iter src_begin, Iter src_end)
	Copies all the bits from an iteration of any unsigned integral src values to this equal-sized bit-span.
template<BitStore Src>
constexpr auto	copy (Src const &src)
	Copies all the bits from an equal-sized src bit-store and returns a reference to this for chaining.
template<usize N>
constexpr auto	copy (std::bitset< N > const &src)
	Copies all the bits from an equal-sized std::bitset and returns a reference to this for chaining.
Fills:
constexpr auto	copy (std::invocable< usize > auto f)
	Fill the bit-span by repeatedly calling f(i) and returns a reference to this for chaining.
constexpr auto	fill_random (double p=0.5, u64 seed=0)
	Fill the bit-span with random bits and returns a reference to this for chaining.
Bit Counts:
constexpr usize	count_ones () const
	Returns the number of set bits in the bit-span.
constexpr usize	count_zeros () const
	Returns the number of unset bits in the bit-span.
constexpr usize	leading_zeros () const
	Returns the number of leading zeros in the bit-span.
constexpr usize	trailing_zeros () const
	Returns the number of trailing zeros in the bit-span.
Set-bit Indices:
constexpr std::optional< usize >	first_set () const
	Returns the index of the first set bit in the bit-span or {} if no bits are set.
constexpr std::optional< usize >	last_set () const
	Returns the index of the last set bit in the bit-span or {} if no bits are set.
constexpr std::optional< usize >	next_set (usize index) const
	Returns the index of the next set bit after index in the bit-span or {} if no more set bits exist.
constexpr std::optional< usize >	previous_set (usize index) const
	Returns the index of the previous set bit before index in the bit-span or {} if there are none.
Unset-bit Indices:
constexpr std::optional< usize >	first_unset () const
	Returns the index of the first unset bit in the bit-span or {} if no bits are unset.
constexpr std::optional< usize >	last_unset () const
	Returns the index of the last unset bit in the bit-span or {} if no bits are unset.
constexpr std::optional< usize >	next_unset (usize index) const
	Returns the index of the next unset bit after index in the bit-span or {} if no more unset bits exist.
constexpr std::optional< usize >	previous_unset (usize index) const
	Returns the index of the previous unset bit before index in the bit-span or {} if no more unset bits exist.
Iterators:
constexpr auto	bits () const
	Returns a const iterator over the bool values of the bits in the const bit-span.
constexpr auto	bits ()
	Returns a non-const iterator over the values of the bits in the mutable bit-span.
constexpr auto	set_bits () const
	Returns an iterator over the indices of any set bits in the bit-span.
constexpr auto	unset_bits () const
	Returns an iterator over the indices of any unset bits in the bit-span.
constexpr auto	store_words () const
	Returns a const iterator over all the words underlying the bit-span.
Exports:
constexpr void	to_words (std::output_iterator< word_type > auto out)
	Returns a copy of the words underlying this bit-span and puts them into the passed output iterator.
constexpr auto	to_words () const
	Returns a copy of the words underlying this bit-span as a std::vector<word_type>.
Spans:
constexpr auto	span (usize begin, usize end) const
	Returns an immutable sub-span encompassing the bit-span's bits in the half-open range [begin, end).
constexpr auto	span (usize begin, usize end)
	Returns an mutable sub-span encompassing the bit-span's bits in the half-open range [begin, end).
Sub-vectors:
constexpr auto	sub (usize begin, usize end) const
	Returns a clone of the span elements in the half-open range [begin, end) as a new bit-vector.
Splits:
constexpr void	split_at (usize at, BitVector< word_type > &left, BitVector< word_type > &right) const
	Views a bit-span as two parts containing the elements [0, at) and [at, size()) respectively.
constexpr auto	split_at (usize at) const
	Views a bit-span as two parts containing the elements [0, at) and [at, size()) respectively.
Riffling:
constexpr void	riffled (BitVector< word_type > &dst) const
	Interleaves the bits of this bit-span with zeros storing the result into the bit-vector dst.
constexpr auto	riffled () const
	Returns a new bit-vector that is the result of riffling the bits in this bit-span with zeros.
String Representations:
std::string	to_binary_string (std::string_view sep="", std::string_view pre="", std::string_view post="") const
	Returns a binary string representation of the bit-span.
std::string	to_string (std::string_view sep="", std::string_view pre="", std::string_view post="") const
	Returns a binary string representation of the bit-span.
std::string	to_pretty_string () const
	Returns a "pretty" string representation of the bit-span.
std::string	to_hex_string () const
	Returns the "hex" string representation of the bits in the bit-span.
std::string	describe () const
	Returns a multi-line string describing the bit-span in some detail.

Static Public Attributes
static constexpr u8	bits_per_word = BITS<Word>
	A constant – the number of bits in a Word.

Detailed Description

template<Unsigned Word = usize>
class gf2::BitSpan< Word >

A bit_span is a non-owning view of contiguous bits in a bit-store.
.

Bit-spans created from const bit-stores will have a type like BitSpan<const u64>, while bit-spans from non-const bit-stores will have a type like BitSpan<u64>. The existence or absence of that const qualifier in the template paramater is important as it allows us to maintain const-correctness for the underlying container. The BitSpan<const u64> type is read-only, the BitSpan<u64> type is read-write.

What matters is the interior const-ness of the span. In fact, you can generally pass a bit-span by value and not worry about passing a reference/const reference – the type is small enough to pass on the stack. This is similar in spirit to the std::span<T> template class.

The BitSpan class satisfies the BitStore concept so is itself a bit-span. This means you can take spans of spans, pass them to methods that accept bit-stores, and so forth.

Constructor & Destructor Documentation

BitSpan()

template<Unsigned Word = usize>

gf2::BitSpan< Word >::BitSpan ( Word * data, u8 offset, usize size )

inline

Constructs a non-owning view over bits stored in contiguous words — a bit-span.

Parameters

data	A pointer to the first word that holds the span's bits.
offset	The bit-offset within data[0] where the span begins.
size	The number of bits in the span.

A BitSpan is non-owning view into a contiguous span of size bits which are assumed to be stored in contiguous words starting at the offset bit of the word data[0].

Generally bit-spans are constructed using the span method of any gf2::BitStore compatible object.

Note

It is the responsibility of the caller to ensure that the underlying store of unsigneds continues to exist for as long as the BitSpan is in use.

Example

std::vector<u8> words{0b1010'1010, 0b1100'1100};
BitSpan s{words.data(), 0, 16};
assert_eq(s.to_string(), "0101010100110011");

Member Function Documentation

all()

template<Unsigned Word = usize>

bool gf2::BitSpan< Word >::all ( ) const

inlineconstexpr

Returns true if all bits in the bit-span are set, false otherwise.

Note: Empty bit-spans have no set bits (logical connective for all is AND with identity true).

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(1,3);
assert_eq(v.all(), false);
v.set(0);
v.set(1);
assert_eq(v.all(), true);
assert_eq(u.all(), false);

any()

template<Unsigned Word = usize>

bool gf2::BitSpan< Word >::any ( ) const

inlineconstexpr

Returns true if at least one bit in the bit-span is set, false otherwise.

Note: Empty bit-spans have no set bits (logical connective for any is OR with identity false).

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(1,3);
assert_eq(v.any(), false);
v.set(0);
assert_eq(v.any(), true);

back()

template<Unsigned Word = usize>

bool gf2::BitSpan< Word >::back ( ) const

inlineconstexpr

Returns true if the last bit element is set, false otherwise.

Panics

In debug mode the method panics of the bit-span is empty.

Example

auto u = BitVector<>::ones(10);
auto v = u.span(0,3);
assert_eq(v.back(), true);

bits() [1/2]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::bits ( )

inlineconstexpr

Returns a non-const iterator over the values of the bits in the mutable bit-span.

You can use this iterator to iterate over the bits in the bit-span to get or set the value of each bit.

Note

For the most part, try to avoid iterating through individual bits. It is much more efficient to use methods that work on whole words of bits at a time.

Example

auto u = BitVector<u8>::ones(14);
auto s = u.span(4,12);
for (auto&& bit : s.bits()) bit = false;
assert_eq(s.to_string(), "00000000")
assert_eq(u.to_string(), "11110000000011");

bits() [2/2]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::bits ( ) const

inlineconstexpr

Returns a const iterator over the bool values of the bits in the const bit-span.

You can use this iterator to iterate over the bits in the bit-span and get the values of each bit as a bool.

Note

For the most part, try to avoid iterating through individual bits. It is much more efficient to use methods that work on whole words of bits at a time.

Example

auto u = BitVector<u8>::ones(14);
auto s = u.span(4,12);
for (auto&& bit : s.bits()) assert_eq(bit, true);

copy() [1/5]

template<Unsigned Word = usize>

template<typename Iter>
requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>

void gf2::BitSpan< Word >::copy ( Iter src_begin, Iter src_end )

inlineconstexpr

Copies all the bits from an iteration of any unsigned integral src values to this equal-sized bit-span.

Note

We allow any unsigned integral source, e.g. copying u64 words into a BitSpan<u8> of the correct size.

Panics

Panics if the size of this bit-span does not match the number of bits in the source iteration.

Example

BitArray<52, u8> v;
auto s = v.span(2,50);
std::vector<u16> src = { 0b1010101010101010, 0b1010101010101010, 0b1111111111111111 };
s.copy(src.begin(), src.end());
assert_eq(s.to_string(), "010101010101010101010101010101011111111111111111");
assert_eq(v.to_string(), "0001010101010101010101010101010101111111111111111100");

copy() [2/5]

template<Unsigned Word = usize>

template<BitStore Src>

auto gf2::BitSpan< Word >::copy ( Src const & src )

inlineconstexpr

Copies all the bits from an equal-sized src bit-store and returns a reference to this for chaining.

Note

This is one of the few methods in the library that doesn't require the two stores to have the same word_type. You can use it to convert between different word_type stores (e.g., from BitSpan<u32> to BitVector<u8>) as long as the sizes match.

Panics

Panics if the size of the bit-span does not match the number of bits in the source store.

Example

auto v = BitVector<u8>::ones(16);
assert_eq(v.to_string(), "1111111111111111");
auto s = v.span(0,10);
s.copy(BitVector<u8>::alternating(10));
assert_eq(v.to_string(), "1010101010111111");

copy() [3/5]

template<Unsigned Word = usize>

template<Unsigned Src>

auto gf2::BitSpan< Word >::copy ( Src src )

inlineconstexpr

Copies all the bits from any unsigned integral src value to this equal-sized bit-span and returns a reference to this for chaining.

Note

1. We allow any unsigned integral source, e.g. copying a single u64 into a BitSpan<u8> of size 64.
2. The least-significant bit of the source becomes the bit at index 0 in the bit-span.

Panics

Panics if the size of the bit-span does not match the number of bits in the source integer type.

Example

BitVector<u8> v{26};
auto s = v.span(3, 19);
u16 src = 0b1010101010101010;
s.copy(src);
assert_eq(s.to_string(), "0101010101010101");
assert_eq(v.to_string(), "00001010101010101010000000");
BitVector<u32> w{26};
auto t = w.span(3, 19);
t.copy(src);
assert_eq(t.to_string(), "0101010101010101");
assert_eq(w.to_string(), "00001010101010101010000000");

copy() [4/5]

template<Unsigned Word = usize>

template<usize N>

auto gf2::BitSpan< Word >::copy ( std::bitset< N > const & src )

inlineconstexpr

Copies all the bits from an equal-sized std::bitset and returns a reference to this for chaining.

Note

A std::bitset prints its bit elements in bit-order which is the reverse of our convention.

Panics

Panics if the size of the bit-span does not match the number of bits in the source bitset.

Example

std::bitset<10> src{0b1010101010};
auto v = BitVector<u8>::ones(16);
auto s = v.span(0,10);
s.copy(src);
assert_eq(s.to_string(), "0101010101");
assert_eq(v.to_string(), "0101010101111111");

copy() [5/5]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::copy ( std::invocable< usize > auto f )

inlineconstexpr

Fill the bit-span by repeatedly calling f(i) and returns a reference to this for chaining.

Example

auto v = BitVector<u8>::ones(16);
auto s = v.span(0,10);
s.copy([](usize i) { return i % 2 == 0; });
assert_eq(s.to_string(), "1010101010");
assert_eq(v.to_string(), "1010101010111111");

count_ones()

template<Unsigned Word = usize>

usize gf2::BitSpan< Word >::count_ones ( ) const

inlineconstexpr

Returns the number of set bits in the bit-span.

Example

BitVector v{10};
auto s = v.span(2,10);
assert_eq(s.count_ones(), 0);
v.set(2);
assert_eq(s.count_ones(), 1);

count_zeros()

template<Unsigned Word = usize>

usize gf2::BitSpan< Word >::count_zeros ( ) const

inlineconstexpr

Returns the number of unset bits in the bit-span.

Example

BitVector v{10};
auto s = v.span(2,10);
assert_eq(s.count_zeros(), 8);
v.set(2);
assert_eq(s.count_zeros(), 7);

describe()

template<Unsigned Word = usize>

std::string gf2::BitSpan< Word >::describe ( ) const

inline

Returns a multi-line string describing the bit-span in some detail.

This method is useful for debugging but you should not rely on the output format which may change.

fill_random()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::fill_random ( double p = 0.5, u64 seed = 0 )

inlineconstexpr

Fill the bit-span with random bits and returns a reference to this for chaining.

The default call fill_random() sets each bit to 1 with probability 0.5 (fair coin).

Parameters

p	The probability of the elements being 1 (defaults to a fair coin, i.e. 50-50).
seed	The seed to use for the random number generator (defaults to 0, which means use entropy).

If p < 0 then the fill is all zeros, if p > 1 then the fill is all ones.

Example

BitVector u{10}, v{10};
auto s = u.span(2,10);
auto t = v.span(2,10);
u64 seed = 1234567890;
s.fill_random(0.5, seed);
t.fill_random(0.5, seed);
assert(u == v);

first_set()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitSpan< Word >::first_set ( ) const

inlineconstexpr

Returns the index of the first set bit in the bit-span or {} if no bits are set.

Example

auto v = BitVector<u8>::zeros(37);
auto s = v.span(4,12);
assert(s.first_set() == std::optional<usize>{});
v.set(2);
assert(s.first_set() == std::optional<usize>{});
v.set(4);
assert(s.first_set() == std::optional<usize>{0});

first_unset()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitSpan< Word >::first_unset ( ) const

inlineconstexpr

Returns the index of the first unset bit in the bit-span or {} if no bits are unset.

Example

auto v = BitVector<u8>::ones(37);
auto s = v.span(4,12);
assert(s.first_unset() == std::optional<usize>{});
v.set(2, false);
assert(s.first_unset() == std::optional<usize>{});
v.set(4, false);
assert(s.first_unset() == std::optional<usize>{0});

flip()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::flip ( usize i )

inlineconstexpr

Flips the value of the bit-element i and returns this for chaining.

Panics

In debug mode the index is bounds-checked.

Example

auto u = BitVector<>::ones(10);
auto v = u.span(1,5);
assert_eq(v.to_string(), "1111");
v.flip(0);
assert_eq(v.to_string(), "0111");
assert_eq(u.to_string(), "1011111111");

flip_all()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::flip_all ( )

inline

Flips the value of the bits in the bit-span and returns a reference to this for chaining.

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(5,10);
v.flip_all();
assert_eq(v.to_string(), "11111");
assert_eq(u.to_string(), "0000011111");

front()

template<Unsigned Word = usize>

bool gf2::BitSpan< Word >::front ( ) const

inlineconstexpr

Returns true if the first bit element is set, false otherwise.

Panics

In debug mode the method panics of the bit-span is empty.

Example

auto u = BitVector<>::ones(10);
auto v = u.span(0,3);
assert_eq(v.front(), true);

get()

template<Unsigned Word = usize>

bool gf2::BitSpan< Word >::get ( usize i ) const

inlineconstexpr

Returns true if the bit at the given index i is set, false otherwise.

Panics

In debug mode the index is bounds-checked.

Example

BitVector u{10};
auto v = u.span(0,2);
assert_eq(v.get(0), false);
u.set(0);
assert_eq(v.get(0), true);

is_empty()

template<Unsigned Word = usize>

bool gf2::BitSpan< Word >::is_empty ( ) const

inlineconstexpr

Returns true if the bit-span is empty, false otherwise.

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(1,1);
assert_eq(v.is_empty(), true);
auto w = u.span(0,1);
assert_eq(w.is_empty(), false);

last_set()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitSpan< Word >::last_set ( ) const

inlineconstexpr

Returns the index of the last set bit in the bit-span or {} if no bits are set.

Example

auto v = BitVector<u8>::zeros(37);
auto s = v.span(4,12);
assert(s.last_set() == std::optional<usize>{});
v.set(27);
assert(s.last_set() == std::optional<usize>{});
v.set(11);
assert_eq(s.to_string(), "00000001");
assert(s.last_set() == std::optional<usize>{7});

last_unset()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitSpan< Word >::last_unset ( ) const

inlineconstexpr

Returns the index of the last unset bit in the bit-span or {} if no bits are unset.

Example

auto v = BitVector<u8>::ones(37);
auto s = v.span(4,12);
assert(s.last_unset() == std::optional<usize>{});
v.set(27);
assert(s.last_unset() == std::optional<usize>{});
v.set(4, false);
assert_eq(s.to_string(), "01111111");
assert(s.last_unset() == std::optional<usize>{0});

leading_zeros()

template<Unsigned Word = usize>

usize gf2::BitSpan< Word >::leading_zeros ( ) const

inlineconstexpr

Returns the number of leading zeros in the bit-span.

Example

BitVector v{37};
auto s = v.span(2,10);
assert_eq(s.leading_zeros(), 8);
v.set(11);
assert_eq(s.leading_zeros(), 8);
v.set(2);
assert_eq(s.leading_zeros(), 0);

next_set()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitSpan< Word >::next_set ( usize index ) const

inlineconstexpr

Returns the index of the next set bit after index in the bit-span or {} if no more set bits exist.

Example

auto v = BitVector<u8>::zeros(37);
auto s = v.span(4,12);
assert(s.next_set(0) == std::optional<usize>{});
v.set(5);
v.set(6);
assert(s.next_set(0) == std::optional<usize>{1});
assert(s.next_set(1) == std::optional<usize>{2});

next_unset()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitSpan< Word >::next_unset ( usize index ) const

inlineconstexpr

Returns the index of the next unset bit after index in the bit-span or {} if no more unset bits exist.

Example

auto v = BitVector<u8>::ones(37);
auto s = v.span(4,12);
assert(s.last_unset() == std::optional<usize>{});
v.set(27);
assert(s.last_unset() == std::optional<usize>{});
v.set(11, false);
assert_eq(s.to_string(), "11111110");
assert(s.last_unset() == std::optional<usize>{7});

none()

template<Unsigned Word = usize>

bool gf2::BitSpan< Word >::none ( ) const

inlineconstexpr

Returns true if no bits in the bit-span are set, false otherwise.

Note: Empty bit-spans have no set bits (logical connective for none is AND with identity true).

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(1,3);
assert_eq(v.none(), true);
v.set(0);
assert_eq(v.none(), false);

operator[]() [1/2]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::operator[] ( usize i )

inlineconstexpr

Returns a "reference" to the bit element i.

The returned object is a BitRef reference for the bit element at index rather than a true reference.

Note: The referenced bit-span must continue to exist while the BitRef is in use.

Panics

In debug mode the index is bounds-checked.

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(0,5);
v[2] = true;
assert_eq(v.to_string(), "00100");
assert_eq(u.to_string(), "0010000000");
auto w = BitVector<>::ones(10);
v[3] = w[3];
assert_eq(v.to_string(), "00110");
v[4] |= w[4];
assert_eq(v.to_string(), "00111");
assert_eq(u.to_string(), "0011100000")

operator[]() [2/2]

template<Unsigned Word = usize>

bool gf2::BitSpan< Word >::operator[] ( usize i ) const

inlineconstexpr

Returns the boolean value of the bit element i.

Panics

In debug mode the index is bounds-checked.

Example

BitVector u{10};
auto v = u.span(1, 4);
assert_eq(v[0], false);

previous_set()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitSpan< Word >::previous_set ( usize index ) const

inlineconstexpr

Returns the index of the previous set bit before index in the bit-span or {} if there are none.

Example

auto v = BitVector<u8>::zeros(37);
auto s = v.span(4,12);
assert(s.previous_set(s.size()) == std::optional<usize>{});
v.set(5);
v.set(6);
assert(s.previous_set(s.size()) == std::optional<usize>{2});
assert(s.previous_set(2) == std::optional<usize>{1});

previous_unset()

template<Unsigned Word = usize>

std::optional< usize > gf2::BitSpan< Word >::previous_unset ( usize index ) const

inlineconstexpr

Returns the index of the previous unset bit before index in the bit-span or {} if no more unset bits exist.

Example

auto v = BitVector<u8>::ones(37);
auto s = v.span(4,12);
assert(s.previous_unset(s.size()) == std::optional<usize>{});
v.set(5, false);
v.set(6, false);
assert(s.previous_unset(s.size()) == std::optional<usize>{2});
assert(s.previous_unset(2) == std::optional<usize>{1});

riffled() [1/2]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::riffled ( ) const

inlineconstexpr

Returns a new bit-vector that is the result of riffling the bits in this bit-span with zeros.

If bit-span has the bits abcde then the output bit-vector will have the bits a0b0c0d0e.

Note: There is no last zero bit in dst.

Example

auto v = BitVector<u8>::ones(20);
auto dst = v.span(4,14).riffled();
assert_eq(dst.to_string(), "1010101010101010101");

riffled() [2/2]

template<Unsigned Word = usize>

void gf2::BitSpan< Word >::riffled ( BitVector< word_type > & dst ) const

inlineconstexpr

Interleaves the bits of this bit-span with zeros storing the result into the bit-vector dst.

On return, dst will have the bits of this bit-span interleaved with zeros. For example, if this bit-span has the bits abcde then dst will have the bits a0b0c0d0e.

Note: There is no last zero bit in dst.

Example

auto v = BitVector<u8>::ones(20);
BitVector<u8> dst;
v.span(4,14).riffled(dst);
assert_eq(dst.to_string(), "1010101010101010101");

set()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::set ( usize i, bool value = true )

inlineconstexpr

Sets the bit-element i to the specified boolean value & returns this for chaining. The default value for value is true.

Panics

In debug mode the index is bounds-checked.

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(0,3);
assert_eq(v.get(0), false);
v.set(0);
assert_eq(v.get(0), true);
assert_eq(u.get(0), true);

set_all()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::set_all ( bool value = true )

inline

Sets the bits in the bit-span to the boolean value and returns a reference to this for chaining.

By default, all bits are set to true.

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(5,10);
v.set_all();
assert_eq(v.to_string(), "11111");
assert_eq(u.to_string(), "0000011111");

set_bits()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::set_bits ( ) const

inlineconstexpr

Returns an iterator over the indices of any set bits in the bit-span.

You can use this iterator to iterate over the set bits in the bit-span and get the index of each bit.

Example

auto v = BitVector<u8>::alternating(19);
auto s = v.span(4,12);
assert_eq(s.to_string(), "10101010");
auto indices = std::ranges::to<std::vector>(s.set_bits());
assert_eq(indices, (std::vector<usize>{0, 2, 4, 6}));

set_word()

template<Unsigned Word = usize>

void gf2::BitSpan< Word >::set_word ( usize i, word_type value )

inlineconstexpr

Sets a "word"'s worth of bits in the bit-span.

These spans are views into a contiguous range of bits from some underlying array of unsigned words. Generally a bit-span is not aligned with the word boundaries of that array. However, the bit-span can synthesise words as if it copied the bits and shifted them down so that element 0 is at bit-position zero in synthetic word number 0. This function sets those words by altering bits in pairs of adjacent words in the underlying array.

Example

auto v = BitVector<u8>::from_string("0000_0000_1111_1111").value();
auto s = v.span(4, 12);     // The span covers words 0 and 1 in the span underlying v.
assert_eq(s.words(), 1);    // However, it can be fitted into a single synthetic word!
assert_eq(s.word(0), 0b1111'0000);
s.set_word(0, 0b1111'1111);
assert_eq(v.to_string(), "0000111111111111");

size()

template<Unsigned Word = usize>

usize gf2::BitSpan< Word >::size ( ) const

inlineconstexpr

Returns the number of bits in the bit-span.

Example

std::vector<u8> words{0b1010'1010, 0b1100'1100};
BitSpan s{words.data(), 0, 16};
assert_eq(s.size(), 16);

span() [1/2]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::span ( usize begin, usize end )

inlineconstexpr

Returns an mutable sub-span encompassing the bit-span's bits in the half-open range [begin, end).

Mutability here is deep – the interior pointer in the returned sub-span is to non-const words.

Panics

This method panics if the sub-span range is not valid.

Example

auto v = BitVector<u8>::alternating(14);
auto s0 = v.span(4,12);
assert_eq(s0.to_string(), "10101010");
auto s1 = s0.span(4,8);
assert_eq(s1.to_string(), "1010")
s1.set_all();
assert_eq(s1.to_string(), "1111")
assert_eq(s0.to_string(), "10101111");
assert_eq(v.to_string(), "10101010111110");

span() [2/2]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::span ( usize begin, usize end ) const

inlineconstexpr

Returns an immutable sub-span encompassing the bit-span's bits in the half-open range [begin, end).

Span mutability is deep – the interior pointer in the returned sub-span is to const words.

Panics

This method panics if the sub-span range is not valid.

Example

const auto v = BitVector<u8>::alternating(14);
const auto s0 = v.span(4,12);
assert_eq(s0.to_string(), "10101010");
auto s1 = s0.span(4,8);
assert_eq(s1.to_string(), "1010")

split_at() [1/2]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::split_at ( usize at ) const

inlineconstexpr

Views a bit-span as two parts containing the elements [0, at) and [at, size()) respectively.

Clones of the parts are returned as a pair of bit-vectors [left, right].

On return, left is a clone of the bits from the start of the bit-span up to but not including at and right contains the bits from at to the end of the bit-span. This bit-span itself is not modified.

Panics

This method panics if the split point is beyond the end of the bit-span.

Example

auto u = BitVector<>::alternating(14);
auto s = u.span(4,12);
auto [left, right] = s.split_at(5);
assert_eq(left.to_string(), "10101");
assert_eq(right.to_string(), "010");
assert_eq(u.to_string(), "10101010101010");

split_at() [2/2]

template<Unsigned Word = usize>

void gf2::BitSpan< Word >::split_at ( usize at, BitVector< word_type > & left, BitVector< word_type > & right ) const

inlineconstexpr

Views a bit-span as two parts containing the elements [0, at) and [at, size()) respectively.

Clones of the parts are stored in the passed bit-vectors left and right.

On return, left contains the bits from the start of the bit-span up to but not including at and right contains the bits from at to the end of the bit-span. This bit-span itself is not modified.

This lets one reuse the left and right destinations without having to allocate new bit-vectors. This is useful when implementing iterative algorithms that need to split a bit-span into two parts repeatedly.

Panics

This method panics if the split point is beyond the end of the bit-span.

Example

auto u = BitVector<>::alternating(14);
auto s = u.span(4,12);
BitVector left, right;
s.split_at(5, left, right);
assert_eq(left.to_string(), "10101");
assert_eq(right.to_string(), "010");
assert_eq(u.to_string(), "10101010101010");

store_words()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::store_words ( ) const

inlineconstexpr

Returns a const iterator over all the words underlying the bit-span.

You can use this iterator to iterate over the words in the bit-span and read the Word value of each word. You cannot use this iterator to modify the words in the span.

Note

The words here are likely a synthetic construct. The expectation is that the bit 0 in the span is located at the bit-location 0 of word(0). That is always the case for bit-vectors but bit-slices typically synthesise "words" on the fly from adjacent pairs of bit-vector words. Nevertheless, almost all the methods in BitStore are implemented efficiently by operating on those words.

Example

auto v = BitVector<u8>::ones(100);
auto s = v.span(4,14);
assert_eq(s.to_string(), "1111111111");
auto words = std::ranges::to<std::vector>(s.store_words());
assert_eq(words, (std::vector<u8>{0b1111'1111, 0b0000'0011}));

sub()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::sub ( usize begin, usize end ) const

inlineconstexpr

Returns a clone of the span elements in the half-open range [begin, end) as a new bit-vector.

Panics

This method panics if the sub-span range is not valid.

Example

auto u = BitVector<>::alternating(14);
auto s = u.span(4,12);
auto v = s.sub(0,4);
assert_eq(v.to_string(), "1010");
s.set_all();
assert_eq(s.to_string(), "11111111");
assert_eq(u.to_string(), "10101111111110");
assert_eq(v.to_string(), "1010");

swap()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::swap ( usize i0, usize i1 )

inlineconstexpr

Swaps the bits in the bit-span at indices i0 and i1 and returns this for chaining.

Panics

In debug mode the indices are bounds-checked.

Example

auto u = BitVector<>::zeros(10);
auto v = u.span(1,5);
v.set(0);
assert_eq(v.to_string(), "1000");
assert_eq(u.to_string(), "0100000000");
v.swap(0, 1);
assert_eq(v.to_string(), "0100");
assert_eq(u.to_string(), "0010000000");

to_binary_string()

template<Unsigned Word = usize>

std::string gf2::BitSpan< Word >::to_binary_string ( std::string_view sep = "", std::string_view pre = "", std::string_view post = "" ) const

inline

Returns a binary string representation of the bit-span.

The string is formatted as a sequence of 0s and 1s with the least significant bit on the right.

Parameters

sep	The separator between bit elements which defaults to no separator.
pre	The prefix to add to the string which defaults to no prefix.
post	The postfix to add to the string which defaults to no postfix.

Example

BitVector v{14};
auto s = v.span(2,12);
assert_eq(s.to_binary_string(), "0000000000");
s.set(0);
assert_eq(s.to_binary_string(), "1000000000");
assert_eq(v.to_binary_string(",", "[", "]"), "[0,0,1,0,0,0,0,0,0,0,0,0,0,0]");

to_hex_string()

template<Unsigned Word = usize>

std::string gf2::BitSpan< Word >::to_hex_string ( ) const

inline

Returns the "hex" string representation of the bits in the bit-span.

The output is a string of hex characters without any spaces, commas, or other formatting.

The string may have a two character suffix of the form ".base" where base is one of 2, 4 or 8.
All hex characters encode 4 bits: "0X0" -> 0b0000, "0X1" -> 0b0001, ..., "0XF" -> 0b1111.
The three possible ".base" suffixes allow for bit-vectors whose length is not a multiple of 4.
Empty bit-vectors are represented as the empty string.

• 0X1 is the hex representation of the bit-vector 0001 => length 4.
• 0X1.8 is the hex representation of the bit-vector 001 => length 3.
• 0X1.4 is the hex representation of the bit-vector 01 => length 2.
• 0X1.2 is the hex representation of the bit-vector 1 => length 1.

The output is in vector-order. If "h0" is the first hex digit in the output string, you can print it as four binary digits v_0v_1v_2v_3. For example, if h0 = "A" which is 1010 in binary, then v = 1010.

Example

auto v = BitVector<u8>::ones(20);
assert_eq(v.span(4,4).to_hex_string(), "");
assert_eq(v.span(4,8).to_hex_string(), "F");
assert_eq(v.span(4,9).to_hex_string(), "F1.2");

to_pretty_string()

template<Unsigned Word = usize>

std::string gf2::BitSpan< Word >::to_pretty_string ( ) const

inline

Returns a "pretty" string representation of the bit-span.

The output is a string of 0's and 1's with spaces between each bit, and the whole thing enclosed in square brackets.

Example

auto v = BitVector<u8>::alternating(14);
auto s = v.span(2,12);
assert_eq(s.to_pretty_string(), "[1,0,1,0,1,0,1,0,1,0]");
auto empty = v.span(3,3);
assert_eq(empty.to_pretty_string(), "[]");

to_string()

template<Unsigned Word = usize>

std::string gf2::BitSpan< Word >::to_string ( std::string_view sep = "", std::string_view pre = "", std::string_view post = "" ) const

inline

Returns a binary string representation of the bit-span.

The string is formatted as a sequence of 0s and 1s with the least significant bit on the right.

Parameters

sep	The separator between bit elements which defaults to no separator.
pre	The prefix to add to the string which defaults to no prefix.
post	The postfix to add to the string which defaults to no postfix.

Example

BitVector v{14};
auto s = v.span(2,12);
assert_eq(s.to_binary_string(), "0000000000");
s.set(0);
assert_eq(s.to_binary_string(), "1000000000");
assert_eq(v.to_binary_string(",", "[", "]"), "[0,0,1,0,0,0,0,0,0,0,0,0,0,0]");

to_words() [1/2]

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::to_words ( ) const

inlineconstexpr

Returns a copy of the words underlying this bit-span as a std::vector<word_type>.

Note: The last word in the vector may not be fully occupied but unused slots will be all zeros.

Example

auto v = BitVector<u8>::ones(100);
auto s = v.span(4,14);
assert_eq(s.to_string(), "1111111111");
auto words = s.to_words();
assert_eq(words, (std::vector<u8>{0b1111'1111, 0b0000'0011}));

to_words() [2/2]

template<Unsigned Word = usize>

void gf2::BitSpan< Word >::to_words ( std::output_iterator< word_type > auto out )

inlineconstexpr

Returns a copy of the words underlying this bit-span and puts them into the passed output iterator.

Note

• The last word in the bit-span may not be fully occupied but unused slots will be all zeros.
• The output iterator must be able to accept values of the bit-span's word_type.
• The output iterator must have enough space to accept all the words in the bit-span.
• If there is extra space in the output iterator, those extra slots are left unchanged.

Example

auto v = BitVector<u8>::ones(100);
auto s = v.span(4,14);
std::vector<u8> out8(s.words());
s.to_words(out8.begin());
assert_eq(out8, (std::vector<u8>{0b1111'1111, 0b0000'0011}));
std::vector<u16> out16(s.words());
s.to_words(out16.begin());
assert_eq(out16, (std::vector<u16>{0b1111'1111, 0b0000'0011}));

trailing_zeros()

template<Unsigned Word = usize>

usize gf2::BitSpan< Word >::trailing_zeros ( ) const

inlineconstexpr

Returns the number of trailing zeros in the bit-span.

Example

auto v = BitVector<u8>::zeros(27);
auto s = v.span(2,10);
assert_eq(s.trailing_zeros(), 8);
v.set(11);
assert_eq(s.trailing_zeros(), 8);
v.set(2);
assert_eq(s.trailing_zeros(), 7);

unset_bits()

template<Unsigned Word = usize>

auto gf2::BitSpan< Word >::unset_bits ( ) const

inlineconstexpr

Returns an iterator over the indices of any unset bits in the bit-span.

You can use this iterator to iterate over the unset bits in the bit-span and get the index of each bit.

Example

auto v = BitVector<u8>::alternating(19);
auto s = v.span(4,12);
assert_eq(s.to_string(), "10101010");
auto indices = std::ranges::to<std::vector>(s.unset_bits());
assert_eq(indices, (std::vector<usize>{1, 3, 5, 7}));

word()

template<Unsigned Word = usize>

word_type gf2::BitSpan< Word >::word ( usize i ) const

inlineconstexpr

Returns a "word"'s worth of bits from the bit-span.

These spans are views into a contiguous range of bits from some underlying array of unsigned words. Generally a bit-span is not aligned with the word boundaries of that array. However, the bit-span can synthesise words as if it copied the bits and shifted them down so that element 0 is at bit-position zero in synthetic word number 0. This function returns those words by combining bits from pairs of adjacent words in the true underlying array.

Example

auto v = BitVector<u8>::from_string("0000'0000'1111'1111").value();
auto s = v.span(4, 12);     // The span covers words 0 and 1 in the span underlying v.
assert_eq(s.words(), 1);    // However, it can be fitted into a single synthetic word!
assert_eq(s.word(0), 0b1111'0000);

words()

template<Unsigned Word = usize>

usize gf2::BitSpan< Word >::words ( ) const

inlineconstexpr

Returns the minimum number of words needed to hold the bits in the bit-span.

These bit-spans are views into a contiguous range of bits from some underlying array of unsigned words. Generally a bit-span is not aligned with the word boundaries of that array. However, the bit-span can synthesise words as if it copied the bits and shifted them down so that element 0 is at bit-position zero in synthetic word number 0. This function returns the number of such words.

Example

auto v = BitVector<u8>::ones(18);
assert_eq(v.words(), 3);
auto s = v.span(4, 12);     // The span covers words 0 and 1 in the span underlying v.
assert_eq(s.words(), 1);    // However, it can be fitted into a single synthetic word!