BitVector.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/BitSpan.h>
 
#include <charconv>
 
namespace gf2 {

template<Unsigned Word = usize>
class BitVector {
private:
    // The number of bit elements in the bit-vector.
    usize m_size;
 
    // The bit elements are packed compactly into this standard vector of unsigned words
    std::vector<Word> m_store;
 
public:
    using word_type = Word;

    static constexpr u8 bits_per_word = BITS<Word>;


    constexpr usize size() const { return m_size; }

    constexpr usize words() const { return m_store.size(); }

    constexpr Word word(usize i) const {
        gf2_debug_assert(i < words(), "Index {} is too large for a bit-vector with {} words.", i, words());
        return m_store[i];
    }

    constexpr void set_word(usize i, Word word) {
        gf2_debug_assert(i < words(), "Index {} is too large for a bit-vector with {} words.", i, words());
 
        // Set the value and if it's the last word, make sure it is kept clean
        m_store[i] = word;
        if (i == words() - 1) clean();
    }

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

    constexpr Word* store() { return m_store.data(); }

    constexpr u8 offset() const { return 0; }


    explicit constexpr BitVector(usize size = 0) : m_size(size), m_store(gf2::words_needed<Word>(size)) {
        // Empty body -- we now have an underlying vector of words all initialized to 0.
        // Note: We avoided using uniform initialization on the `std::vector` data member.
    }

    explicit constexpr BitVector(usize size, Word word) : m_size(size), m_store(gf2::words_needed<Word>(size), word) {
        // Make sure any excess bits are set to 0.
        clean();
    }


    static constexpr BitVector with_capacity(usize capacity) {
        auto result = BitVector<Word>{};
        result.m_store.reserve(gf2::words_needed<Word>(capacity));
        return result;
    }

    static constexpr BitVector zeros(usize n) { return BitVector{n}; }

    static constexpr BitVector ones(usize n) { return BitVector{n, MAX<Word>}; }

    static constexpr BitVector constant(usize n, bool value) { return BitVector{n, value ? MAX<Word> : Word{0}}; }

    static constexpr BitVector unit(usize n, usize i) {
        gf2_assert(i < n, "Unit axis i = {} should be less than the bit-vector size n = {}", i, n);
        BitVector result{n};
        result.set(i);
        return result;
    }

    static constexpr BitVector alternating(usize n) { return BitVector{n, gf2::ALTERNATING<Word>}; }

    template<Unsigned Src>
    static constexpr BitVector from(Src src) {
        BitVector result{gf2::BITS<Src>};
        result.copy(src);
        return result;
    }

    template<typename Iter>
        requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>
    static constexpr BitVector from(Iter src_begin, Iter src_end) {
        // How many bits are we copying?
        using src_type = typename std::iterator_traits<Iter>::value_type;
        auto src_words = static_cast<std::size_t>(std::distance(src_begin, src_end));
        auto src_bits = src_words * BITS<src_type>;
        BitVector result{src_bits};
        result.copy(src_begin, src_end);
        return result;
    }

    template<BitStore Src>
    static constexpr BitVector from(Src const& src) {
        BitVector result{src.size()};
        result.copy(src);
        return result;
    }

    template<usize N>
    static constexpr BitVector from(std::bitset<N> const& src) {
        BitVector result{N};
        result.copy(src);
        return result;
    }

    static constexpr BitVector from(usize size, std::invocable<usize> auto f) {
        BitVector result{size};
        result.copy(f);
        return result;
    }


    static BitVector random(usize size, double p = 0.5, u64 seed = 0) {
        BitVector result{size};
        result.fill_random(p, seed);
        return result;
    }

    static BitVector seeded_random(usize size, u64 seed) { return random(size, 0.5, seed); }

    static BitVector biased_random(usize size, double p) { return random(size, p, 0); }


    static std::optional<BitVector> from_string(std::string_view sv) {
        // Edge case ...
        if (sv.empty()) return BitVector<Word>{};
 
        // Remove any whitespace, commas, single quotes, or underscores characters.
        std::string s{sv};
        std::erase_if(s, [](char c) { return c == ' ' || c == ',' || c == '\'' || c == '_'; });
        bool no_punctuation = true;
 
        // Check for a binary prefix.
        if (s.starts_with("0b")) return from_binary_string(s, no_punctuation);
 
        // Check for a hex prefix.
        if (s.starts_with("0x") || s.starts_with("0X")) return from_hex_string(s, no_punctuation);
 
        // No prefix, but perhaps the string only contains '0' and '1' characters.
        if (std::ranges::all_of(s, [](char c) { return c == '0' || c == '1'; })) {
            return BitVector::from_binary_string(s, no_punctuation);
        }
 
        // Last gasp -- try hex ...
        return BitVector::from_hex_string(s, no_punctuation);
    }

    static std::optional<BitVector> from_binary_string(std::string_view sv, bool no_punctuation = false) {
        // Edge case ...
        if (sv.empty()) return BitVector<Word>{};
 
        // Convert to a string & remove the "0b" prefix if it exists.
        std::string s{sv};
        if (s.starts_with("0b")) s = s.substr(2);
 
        // If necessary, also remove any whitespace, commas, single quotes, or underscores.
        if (!no_punctuation) std::erase_if(s, [](char c) { return c == ' ' || c == ',' || c == '\'' || c == '_'; });
 
        // The string should now be a sequence of 0's and 1's.
        if (std::ranges::any_of(s, [](char c) { return c != '0' && c != '1'; })) return std::nullopt;
 
        // Construct the bit-vector.
        auto result = BitVector::zeros(s.size());
        for (auto i = 0uz; i < s.size(); ++i)
            if (s[i] == '1') result.set(i);
        return result;
    }

    static std::optional<BitVector> from_hex_string(std::string_view sv, bool no_punctuation = false) {
        // Edge case ...
        if (sv.empty()) return BitVector<Word>{};
 
        // Convert to a string and remove the optional "0x" prefix if it exists.
        std::string s{sv};
        if (s.starts_with("0x") || s.starts_with("0X")) s = s.substr(2);
 
        // By default, the base of the last digit is 16 just like all the others.
        // However, there may be a suffix of the form ".base" where `base` is one of 2, 4 or 8.
        int last_digit_base = 16;
        if (s.ends_with(".2"))
            last_digit_base = 2;
        else if (s.ends_with(".4"))
            last_digit_base = 4;
        else if (s.ends_with(".8"))
            last_digit_base = 8;
 
        // Remove the suffix if it exists.
        if (last_digit_base != 16) s = s.substr(0, s.size() - 2);
 
        // If necessary, also remove any whitespace, commas, single quotes, or underscores.
        if (!no_punctuation) std::erase_if(s, [](char c) { return c == ' ' || c == ',' || c == '_'; });
 
        // The string should now be a sequence of 0-9, A-F, a-f.
        if (std::ranges::any_of(s, [](char c) { return !std::isxdigit(c); })) return std::nullopt;
 
        // Construct the bit-vector where we allow all the characters to be hex digits.
        auto result = BitVector::with_capacity(s.size() * 4);
 
        // Push all but the last character -- those are hex digits for sure.
        for (auto i = 0uz; i < s.size() - 1; ++i) result.append_hex_digit(s[i]);
 
        // Push the last character -- it may be a hex digit or a base indicator.
        result.append_digit(s[s.size() - 1], last_digit_base);
 
        return result;
    }


    constexpr usize capacity() const { return bits_per_word * m_store.capacity(); }

    constexpr usize remaining_capacity() const { return capacity() - size(); }

    constexpr BitVector& shrink_to_fit() {
        m_store.resize(gf2::words_needed<Word>(size()));
        m_store.shrink_to_fit();
        return *this;
    }

    constexpr BitVector& clear() {
        m_store.clear();
        m_size = 0;
        return *this;
    }

    constexpr BitVector& resize(usize n) {
        if (n != size()) {
            m_store.resize(gf2::words_needed<Word>(n), 0);
            auto old_size = size();
            m_size = n;
 
            // If we truncated, we need to clean up the last occupied word if necessary.
            if (n < old_size) clean();
        }
        return *this;
    }

    constexpr void clean() {
        // NOTE: This works fine even if `size() == 0`.
        auto shift = m_size % bits_per_word;
        if (shift != 0) m_store[words() - 1] &= Word(~(MAX<Word> << shift));
    }


    constexpr BitVector& push(bool b) {
        resize(size() + 1);
        if (b) this->set(size() - 1, true);
        return *this;
    }

    constexpr std::optional<bool> pop() {
        if (m_size == 0) return std::nullopt;
        bool b = this->back();
        resize(m_size - 1);
        return b;
    }


    template<Unsigned Src>
    constexpr auto append(Src src) {
        auto old_size = size();
        resize(old_size + BITS<Src>);
        this->span(old_size, size()).copy(src);
        return *this;
    }

    template<typename Iter>
        requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>
    constexpr auto append(Iter src_begin, Iter src_end) {
        // How many bits are we appending?
        using src_type = typename std::iterator_traits<Iter>::value_type;
        auto src_words = static_cast<std::size_t>(std::distance(src_begin, src_end));
        auto src_bits = src_words * BITS<src_type>;
 
        // Resize & copy.
        auto old_size = size();
        resize(old_size + src_bits);
        this->span(old_size, size()).copy(src_begin, src_end);
        return *this;
    }
 

    template<BitStore Src>
    constexpr BitVector& append(Src const& src) {
        auto old_size = size();
        resize(old_size + src.size());
        this->span(old_size, size()).copy(src);
        return *this;
    }

    template<usize N>
    auto append(std::bitset<N> const& src) {
        auto old_size = size();
        resize(old_size + src.size());
        this->span(old_size, size()).copy(src);
        return *this;
    }

    constexpr BitVector& append_digit(char c, int base) {
        // The known bases are 2, 4, 8, and 16.
        static constexpr std::array<int, 4> known_bases = {2, 4, 8, 16};
        if (std::ranges::contains(known_bases, base)) {
            // Try to convert the character to an integer.
            usize x;
            if (std::from_chars(&c, &c + 1, x, base).ec == std::errc{}) {
                // Success! Push the digits onto the bit-vector.
                auto digits = static_cast<usize>(std::log2(base));
                auto old_len = size();
                resize(old_len + digits);
                for (auto i = 0uz; i < digits; ++i) this->set(old_len + i, (x >> (digits - i - 1)) & 1);
            }
        }
        return *this;
    }

    constexpr BitVector& append_hex_digit(char c) {
        // Try to convert the hex digit to an integer.
        int x;
        if (std::from_chars(&c, &c + 1, x, 16).ec == std::errc{}) {
            // Success! Push the digits onto the bit-vector.
            auto old_len = size();
            resize(old_len + 4);
            for (auto i = 0uz; i < 4; ++i) this->set(old_len + i, (x >> (3 - i)) & 1);
        }
        return *this;
    }


    constexpr BitVector<Word> split_off(usize at) {
        BitVector result;
        split_off(at, result);
        return result;
    }

    constexpr void split_off(usize at, BitVector<Word>& dst) {
        gf2_assert(at <= m_size, "split point {} is beyond the end of the bit-vector", at);
        dst.clear();
        dst.append(this->span(at, m_size));
        resize(at);
    }

    template<Unsigned Dst = Word>
    constexpr std::optional<Dst> split_off_unsigned() {
        // Edge case ...
        if (size() == 0) return std::nullopt;
 
        // Perhaps we can safely cast an `Word` into a `Dst` without any loss of information.
        constexpr usize bits_per_dst = BITS<Dst>;
        if constexpr (bits_per_dst <= bits_per_word) {
            // Easy cases when we can safely cast an `Word` into a `Dst` without any loss of information.
            // 1. Just one word in the store & we know that all unused bits in that word are zeros.
            // 2. More than one word in the store but the last word is fully occupied.
            auto n_words = words();
            auto shift = size() % bits_per_word;
            if (n_words == 1 || shift == 0) {
                auto result = static_cast<Dst>(m_store[n_words - 1]);
                resize(size() - bits_per_dst);
                return result;
            }
 
            // The last word is not fully occupied so we need to combine it with the next to last word to form a
            // value that can be cast to a `Dst`.
            auto lo = m_store[n_words - 2] >> shift;
            auto hi = m_store[n_words - 1] << (bits_per_word - shift);
            auto result = static_cast<Dst>(lo | hi);
            resize(size() - bits_per_dst);
            return result;
        } else {
            // `Dst` is larger than `Word` -- it should be an integer multiple of `bits_per_word` is size.
            static_assert(bits_per_dst % bits_per_word == 0, "sizeof(Dst) % sizeof(Word) != 0");
 
            // Pop an appropriate number of `Word` sized chunks off the end of the bit-vector.
            auto              words_per_dst = bits_per_dst / bits_per_word;
            std::vector<Word> chunks(words_per_dst);
            for (auto i = 0uz; i < words_per_dst; ++i) chunks[i] = *split_off_unsigned<Word>();
 
            // Combine the chunks into a `Dst` value.
            Dst result = 0;
            for (auto i = words_per_dst; i-- > 0;) result |= static_cast<Dst>(chunks[i] << (i * bits_per_word));
 
            return result;
        }
    }


    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); }


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

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

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

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


    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); }


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

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


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

    template<typename Iter>
        requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>
    constexpr void copy(Iter src_begin, Iter src_end) {
        gf2::copy(src_begin, src_end, *this);
    }

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

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


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

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


    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 void to_words(std::output_iterator<word_type> auto out) { gf2::to_words(*this, out); }

    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, BitVector<word_type>& left, BitVector<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(BitVector<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); }

};
 
} // namespace gf2