BitVec.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/BitSpan.h>
 
#include <algorithm>
#include <array>
#include <bitset>
#include <charconv>
#include <cmath>
#include <concepts>
#include <cctype>
#include <cstdint>
#include <format>
#include <optional>
#include <ranges>
#include <string>
#include <string_view>
#include <vector>
 
namespace gf2 {

template<unsigned_word Word = usize>
class BitVec : public BitStore<BitVec<Word>> {
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_data;
 
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_data.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_data[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_data[i] = word;
        if (i == words() - 1) clean();
    }

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

    constexpr Word* data() { return m_data.data(); }

    constexpr u8 offset() const { return 0; }


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

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


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

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

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

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

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

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

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

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

    static constexpr BitVec from(usize len, std::invocable<usize> auto f) {
        BitVec result{len};
        result.fill(f);
        return result;
    }


    static BitVec random(usize len, double p = 0.5, u64 seed = 0) {
        BitVec result{len};
        result.random_fill(p, seed);
        return result;
    }

    static BitVec seeded_random(usize len, u64 seed) { return random(len, 0.5, seed); }

    static BitVec biased_random(usize len, double p) { return random(len, p, 0); }


    static std::optional<BitVec> from_string(std::string_view sv) {
        // Edge case ...
        if (sv.empty()) return BitVec<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 BitVec::from_binary_string(s, no_punctuation);
        }
 
        // Last gasp -- try hex ...
        return BitVec::from_hex_string(s, no_punctuation);
    }

    static std::optional<BitVec> from_binary_string(std::string_view sv, bool no_punctuation = false) {
        // Edge case ...
        if (sv.empty()) return BitVec<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 = BitVec::zeros(s.size());
        for (auto i = 0uz; i < s.size(); ++i)
            if (s[i] == '1') result.set(i);
        return result;
    }

    static std::optional<BitVec> from_hex_string(std::string_view sv, bool no_punctuation = false) {
        // Edge case ...
        if (sv.empty()) return BitVec<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 = BitVec::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_data.capacity(); }

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

    constexpr BitVec& clear() {
        m_data.clear();
        m_size = 0;
        return *this;
    }

    constexpr BitVec& resize(usize n) {
        if (n != size()) {
            m_data.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_data[words() - 1] &= Word(~(MAX<Word> << shift));
    }


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

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

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

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

    constexpr BitVec& 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 BitVec& 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 std::optional<bool> pop() {
        if (m_size == 0) return std::nullopt;
        auto b = this->get(m_size - 1);
        resize(m_size - 1);
        return b;
    }

    constexpr void split_off(usize at, BitVec<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);
    }

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

    template<unsigned_word Dst = Word>
    constexpr std::optional<Dst> split_off_unsigned() {
        // Edge case ...
        if (this->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 = this->words();
            auto shift = this->size() % bits_per_word;
            if (n_words == 1 || shift == 0) {
                auto result = static_cast<Dst>(m_data[n_words - 1]);
                resize(this->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_data[n_words - 2] >> shift;
            auto hi = m_data[n_words - 1] << (bits_per_word - shift);
            auto result = static_cast<Dst>(lo | hi);
            resize(this->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;
        }
    }

};
 
} // namespace gf2
 
// --------------------------------------------------------------------------------------------------------------------
// Specialises `std::formatter` for `BitVec` -- defers to the version for `BitStore` ...
// -------------------------------------------------------------------------------------------------------------------
template<gf2::unsigned_word Word>
struct std::formatter<gf2::BitVec<Word>> : std::formatter<gf2::BitStore<gf2::BitVec<Word>>> {
    // Inherits all functionality from `BitStore` formatter
};