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

template<usize N, Unsigned Word = usize>
class BitSet {
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 BitSet() {
        for (usize i = 0; i < words(); ++i) m_store[i] = 0;
    }

    explicit constexpr BitSet(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 BitSet zeros() { return BitSet{}; }

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

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

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

    static constexpr BitSet alternating() { return BitSet{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));
    }

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

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


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

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

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


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

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

};
 
} // namespace gf2