BitSpan.h

Go to the documentation of this file.

#pragma once
// SPDX-FileCopyrightText: 2025 Nessan Fitzmaurice <nzznfitz+gh@icloud.com>
// SPDX-License-Identifier: MIT

 
#include <gf2/BitStore.h>
#include <gf2/Iterators.h>
#include <gf2/BitRef.h>
#include <gf2/BitVec.h>
 
namespace gf2 {

template<Unsigned Word = usize>
class BitSpan {
private:
    // A pointer to the first word containing bits in the span (it may be partially occupied).
    Word* m_store = nullptr;
 
    // The bit-span begins at this bit-offset inside `m_store[0]`.
    u8 m_offset = 0;
 
    // The number of bits in the span.
    usize m_size = 0;
 
    // The number of words (synthesised) needed to hold the bits in the span (cached for efficiency).
    usize m_words = 0;
 
public:
    // The underlying span uses words of this type (where we remove any `const` qualifier).
    using word_type = std::remove_const_t<Word>;

    static constexpr u8 bits_per_word = BITS<Word>;


    BitSpan(Word* data, u8 offset, usize size) {
 
        // Check that offset is valid.
        gf2_debug_assert(offset < bits_per_word, "Span begins at bit-offset {} > bits in a word ({})!", offset,
                         bits_per_word);
 
        // Set the member variables.
        m_store = data;
        m_offset = offset;
        m_size = size;
        m_words = gf2::words_needed<Word>(m_size);
    }


    constexpr usize size() const { return m_size; }

    constexpr usize words() const { return m_words; }

    constexpr word_type word(usize i) const {
        // Get the recipe for the "word" at index `i` (we may need two real words to synthesise it).
        auto [w0_bits, w1_bits] = recipe_for_word(i);
 
        // Our return value starts with all unset bits.
        word_type result = 0;
 
        // Replace `w0_bits` low-order bits in `result` with the same number of high-order bits from `w0`
        Word w0 = m_store[i];
        gf2::replace_bits(result, 0, w0_bits, w0 >> m_offset);
 
        // Perhaps our result spans two words.
        if (w1_bits > 0) {
            // Replace `w1_bits` high-order bits in result with the same number of low-order bits from `w1`
            Word w1 = m_store[i + 1];
            gf2::replace_bits(result, w0_bits, w0_bits + w1_bits, w1 << w0_bits);
        }
        return result;
    }

    constexpr void set_word(usize i, word_type value) {
        if constexpr (std::is_const_v<Word>) {
            // This should never get called for const bit-spans.
            throw std::logic_error("Cannot set a word in a const bit-span.");
        } else {
            // Get the recipe for the "word" at index `i` (it may be a synthesis of two real words).
            auto [w0_bits, w1_bits] = recipe_for_word(i);
 
            // Replace `w0_bits` low-order bits in `w0` with the same number of high-order bits from `value`
            // Shift `value` to the left to align its bits with the start of `w0`.
            gf2::replace_bits(m_store[i], m_offset, m_offset + w0_bits, value << m_offset);
 
            // Perhaps we also need to overwrite some bits in the second word.
            if (w1_bits > 0) {
                // Replace `w1_bits` low-order bits in `w1` with the same number of high-order bits from `value`
                gf2::replace_bits(m_store[i + 1], 0, w1_bits, value >> w0_bits);
            }
        }
    }

    constexpr const Word* store() const { return m_store; }

    constexpr Word* store() { return m_store; }

    constexpr u8 offset() const { return m_offset; }


    constexpr bool get(usize i) const { return gf2::get(*this, i); }

    constexpr bool operator[](usize i) const { return gf2::get(*this, i); }

    constexpr bool front() const { return gf2::front(*this); }

    constexpr bool back() const { return gf2::back(*this); }


    auto set(usize i, bool value = true) { return gf2::set(*this, i, value); }

    constexpr auto operator[](usize i) { return gf2::ref(*this, i); }

    auto flip(usize i) { return gf2::flip(*this, i); }

    constexpr auto swap(usize i0, usize i1) { return gf2::swap(*this, i0, i1); }


    constexpr bool is_empty() const { return gf2::is_empty(*this); }

    constexpr bool any() const { return gf2::any(*this); }

    constexpr bool all() const { return gf2::all(*this); }

    constexpr bool none() const { return gf2::none(*this); }


    auto set_all(bool value = true) { return gf2::set_all(*this, value); }

    auto flip_all() { return gf2::flip_all(*this); }


    template<Unsigned Src>
    auto copy(Src src) {
        return gf2::copy(src, *this);
    }

    template<BitStore Src>
    auto copy(Src const& src) {
        return gf2::copy(src, *this);
    }

    template<usize N>
    auto copy(std::bitset<N> const& src) {
        return gf2::copy(src, *this);
    }


    auto copy(std::invocable<usize> auto f) { return gf2::copy(*this, f); }

    auto random_fill(double p = 0.5, u64 seed = 0) { return gf2::random_fill(*this, p, seed); }


    constexpr usize count_ones() const { return gf2::count_ones(*this); }

    constexpr usize count_zeros() const { return gf2::count_zeros(*this); }

    constexpr usize leading_zeros() const { return gf2::leading_zeros(*this); }

    constexpr usize trailing_zeros() const { return gf2::trailing_zeros(*this); }


    constexpr std::optional<usize> first_set() const { return gf2::first_set(*this); }

    constexpr std::optional<usize> last_set() const { return gf2::last_set(*this); }

    constexpr std::optional<usize> next_set(usize index) const { return gf2::next_set(*this, index); }

    constexpr std::optional<usize> previous_set(usize index) const { return gf2::previous_set(*this, index); }


    constexpr std::optional<usize> first_unset() const { return gf2::first_unset(*this); }

    constexpr std::optional<usize> last_unset() const { return gf2::last_unset(*this); }

    constexpr std::optional<usize> next_unset(usize index) const { return gf2::next_unset(*this, index); }

    constexpr std::optional<usize> previous_unset(usize index) const { return gf2::previous_unset(*this, index); }


    constexpr auto bits() const { return gf2::bits(*this); }

    constexpr auto bits() { return gf2::bits(*this); }

    constexpr auto set_bits() const { return gf2::set_bits(*this); }

    constexpr auto unset_bits() const { return gf2::unset_bits(*this); }

    constexpr auto store_words() const { return gf2::store_words(*this); }

    constexpr auto to_words() const { return gf2::to_words(*this); }


    constexpr auto span(usize begin, usize end) const { return gf2::span(*this, begin, end); }

    constexpr auto span(usize begin, usize end) { return gf2::span(*this, begin, end); }


    constexpr auto sub(usize begin, usize end) const { return gf2::sub(*this, begin, end); }


    constexpr void split_at(usize at, BitVec<word_type>& left, BitVec<word_type>& right) const {
        return gf2::split(*this, at, left, right);
    }

    constexpr auto split_at(usize at) const { return gf2::split(*this, at); }


    constexpr void riffled(BitVec<word_type>& dst) const { return gf2::riffle(*this, dst); }

    constexpr auto riffled() const { return gf2::riffle(*this); }


    std::string to_binary_string(std::string_view sep = "", std::string_view pre = "",
                                 std::string_view post = "") const {
        return gf2::to_binary_string(*this, sep, pre, post);
    }

    std::string to_string(std::string_view sep = "", std::string_view pre = "", std::string_view post = "") const {
        return gf2::to_string(*this, sep, pre, post);
    }

    std::string to_pretty_string() const { return gf2::to_pretty_string(*this); }

    std::string to_hex_string() const { return gf2::to_hex_string(*this); }

    std::string describe() const { return gf2::describe(*this); }

 
private:
    // A helper method to get the recipe used to "bake" the (generally synthetic) `word(i)`.
    //
    // Spans may not be aligned with the underlying unsigneds so we need to synthesise "words" as needed.
    // To synthesise word `i`, we use two contiguous words from the underlying vector of words, `w0`, and `w1`,
    // where `w0` is always m_words[i] and `w1` is always m_words[i + 1].
    //
    // We copy `w0_bits` high-order bits from `w0` and they become the low-order bits in the span "word": `word(i)`.
    // We copy `w1_bits` low-order bits from `w1` and they become the high-order bits in the span "word": `word(i)`.
    //
    // This "recipe" method returns the pair: `(w0_bits, w1_bits)` which tells you the numbers of needed bits.
    //
    // The only tricky part is that the last span word may not be fully occupied so we need to handle it differently
    // from the others.
    //
    // In debug mode we also check that the index `i` is valid.
    constexpr auto recipe_for_word(usize i) const {
        gf2_debug_assert(i < m_words, "Index {} should be less than {}", i, m_words);
 
        // The default recipe (these sum to a whole word of bits).
        u8 w0_bits = bits_per_word - m_offset;
        u8 w1_bits = m_offset;
 
        // The last word in the span may not be fully occupied so we need to adjust the bits accordingly.
        if (i == m_words - 1) {
            auto last_offset = static_cast<u8>((m_offset + m_size - 1) % bits_per_word);
            if (last_offset < m_offset) {
                // Still need to use two words but `w1-bits` may shrink.
                w1_bits = static_cast<u8>(last_offset + 1);
            } else {
                // Only need to use one word so no need for `w1_bits`.
                w0_bits = static_cast<u8>(last_offset - m_offset + 1);
                w1_bits = 0;
            }
        }
        return std::pair{w0_bits, w1_bits};
    }
};
 
} // namespace gf2