BitArray.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 <gf2/BitArray.h>
 
namespace gf2 {

template<usize N, Unsigned Word = usize>
class BitArray {
private:
    // The bit elements are packed compactly into this standard array of unsigned words
    std::array<Word, words_needed<Word>(N)> m_store{};
 
public:
    using word_type = Word;

    static constexpr u8 bits_per_word = BITS<Word>;


    constexpr usize size() const { return N; }

    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 bitset 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 bitset 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 BitArray() {
        m_store.fill(Word{0});
    }

    explicit constexpr BitArray(Word word) {
        // Fill the store with the given word & then clean up any excess bits
        for (usize i = 0; i < words(); ++i) m_store[i] = word;
        clean();
    }


    static constexpr BitArray zeros() { return BitArray{}; }

    static constexpr BitArray ones() { return BitArray{MAX<Word>}; }

    static constexpr BitArray constant(bool value) { return BitArray{value ? MAX<Word> : Word{0}}; }

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

    static constexpr BitArray alternating() { return BitArray{gf2::ALTERNATING<Word>}; }


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

    template<Unsigned Src>
        requires (BITS<Src> == N)
    static constexpr BitArray from(Src src) {
        BitArray result;
        result.copy(src);
        return result;
    }

    template<typename Iter>
        requires std::is_unsigned_v<typename std::iterator_traits<Iter>::value_type>
    static constexpr BitArray 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>;
        gf2_always_assert(src_bits == N, "Lengths do not match: {} != {}.", N, src_bits);
        BitArray result;
        result.copy(src_begin, src_end);
        return result;
    }

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

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


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

    static BitArray seeded_random(u64 seed) { return random(0.5, seed); }

    static BitArray biased_random(double p) { return random(p, 0); }


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

    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