dynamic_bitset.h

#ifndef __VECS_STORAGE_DYNAMIC_BITSET_H__
#define __VECS_STORAGE_DYNAMIC_BITSET_H__
 
#include <algorithm>
#include <cstdint>
#include <limits>
#include <string>
#include <vector>
 
#if defined(_MSC_VER)
    #include <intrin.h>
    #pragma intrinsic(_BitScanReverse64)
#endif
 
namespace vecs::storage {

class dynamic_bitset {
  public:
    using size_type = std::uint64_t;
    using block_type = std::uint64_t;
    static constexpr size_type bits_per_block =
        std::numeric_limits<block_type>::digits;
 
    dynamic_bitset() = default;
 
    // explicit dynamic_bitset(size_type num_bits) : m_num_bits(num_bits) {
    //     m_blocks.resize((num_bits + bits_per_block - 1) / bits_per_block);
    // }
 
    explicit dynamic_bitset(size_type value) {
        if (value == 0) {
            m_num_bits = 1;
            m_blocks.resize(1, 0);
        } else {
            // Calculate number of bits needed
            m_num_bits = std::numeric_limits<size_type>::digits - clzll(value);
            m_blocks.resize((m_num_bits + bits_per_block - 1) / bits_per_block);
            m_blocks[0] = value;
            zero_unused_bits();
        }
    }
 
    size_type size() const {
        return m_num_bits;
    }
 
    void clear() {
        std::fill(m_blocks.begin(), m_blocks.end(), 0);
    }
 
    void resize(size_type nbits) {
        m_num_bits = nbits;
        m_blocks.resize((nbits + bits_per_block - 1) / bits_per_block);
        zero_unused_bits();
    }
 
    dynamic_bitset& masked_and_not(dynamic_bitset& exclude_mask) {
        if (exclude_mask.size() > size()) {
            resize(exclude_mask.size());
        } else if (size() > exclude_mask.size()) {
            exclude_mask.resize(size());
        }
 
        for (size_type i = 0; i < m_blocks.size(); ++i) {
            m_blocks[i] &= ~exclude_mask.m_blocks[i];
        }
        zero_unused_bits();
        return *this;
    }
 
    // Bitwise AND assignment
    dynamic_bitset& operator&=(const dynamic_bitset& rhs) {
        // weirdness on MSVC maybe because min/max macros? ugh
        // size_type min_blocks = std::min(m_blocks.size(), rhs.m_blocks.size());
 
        size_type min_blocks = (m_blocks.size() < rhs.m_blocks.size())
            ? m_blocks.size()
            : rhs.m_blocks.size();
 
        for (size_type i = 0; i < min_blocks; ++i) {
            m_blocks[i] &= rhs.m_blocks[i];
        }
        // Zero the remaining blocks if lhs is longer than rhs
        if (m_blocks.size() > rhs.m_blocks.size()) {
            std::fill(m_blocks.begin() + min_blocks, m_blocks.end(), 0);
        }
        zero_unused_bits();
        return *this;
    }
 
    // Bitwise OR assignment
    dynamic_bitset& operator|=(const dynamic_bitset& rhs) {
        if (rhs.m_num_bits > m_num_bits) {
            resize(rhs.m_num_bits);
        }
        for (size_type i = 0; i < rhs.m_blocks.size(); ++i) {
            m_blocks[i] |= rhs.m_blocks[i];
        }
        zero_unused_bits();
        return *this;
    }
 
    // Bitwise XOR assignment
    dynamic_bitset& operator^=(const dynamic_bitset& rhs) {
        if (rhs.m_num_bits > m_num_bits) {
            resize(rhs.m_num_bits);
        }
        for (size_type i = 0; i < rhs.m_blocks.size(); ++i) {
            m_blocks[i] ^= rhs.m_blocks[i];
        }
        zero_unused_bits();
        return *this;
    }
 
    // Bitwise NOT
    dynamic_bitset operator~() const {
        dynamic_bitset result(*this);
        for (auto& block : result.m_blocks) {
            block = ~block;
        }
        result.zero_unused_bits();
        return result;
    }
 
    // Left shift assignment
    dynamic_bitset& operator<<=(size_type shift) {
        if (shift >= m_num_bits) {
            // All bits are shifted out
            std::fill(m_blocks.begin(), m_blocks.end(), 0);
            return *this;
        }
 
        size_type block_shift = shift / bits_per_block;
        size_type bit_shift = shift % bits_per_block;
        size_type inv_bit_shift = bits_per_block - bit_shift;
 
        if (block_shift != 0) {
            for (size_type i = m_blocks.size(); i-- > block_shift;) {
                m_blocks[i] = m_blocks[i - block_shift];
            }
            std::fill(m_blocks.begin(), m_blocks.begin() + block_shift, 0);
        }
 
        if (bit_shift != 0) {
            block_type carry = 0;
            for (size_type i = block_shift; i < m_blocks.size(); ++i) {
                block_type temp = m_blocks[i];
                m_blocks[i] = (temp << bit_shift) | carry;
                carry = temp >> inv_bit_shift;
            }
        }
        zero_unused_bits();
        return *this;
    }
 
    // Right shift assignment
    dynamic_bitset& operator>>=(size_type shift) {
        if (shift >= m_num_bits) {
            // All bits are shifted out
            std::fill(m_blocks.begin(), m_blocks.end(), 0);
            return *this;
        }
 
        size_type block_shift = shift / bits_per_block;
        size_type bit_shift = shift % bits_per_block;
        size_type inv_bit_shift = bits_per_block - bit_shift;
 
        if (block_shift != 0) {
            for (size_type i = 0; i < m_blocks.size() - block_shift; ++i) {
                m_blocks[i] = m_blocks[i + block_shift];
            }
            std::fill(m_blocks.end() - block_shift, m_blocks.end(), 0);
        }
 
        if (bit_shift != 0) {
            block_type carry = 0;
            for (size_type i = m_blocks.size(); i-- > 0;) {
                block_type temp = m_blocks[i];
                m_blocks[i] = (temp >> bit_shift) | carry;
                carry = temp << inv_bit_shift;
            }
        }
        zero_unused_bits();
        return *this;
    }
 
    // Bitwise operators
    friend dynamic_bitset
    operator&(dynamic_bitset lhs, const dynamic_bitset& rhs) {
        lhs &= rhs;
        return lhs;
    }
 
    friend dynamic_bitset
    operator|(dynamic_bitset lhs, const dynamic_bitset& rhs) {
        lhs |= rhs;
        return lhs;
    }
 
    friend dynamic_bitset
    operator^(dynamic_bitset lhs, const dynamic_bitset& rhs) {
        lhs ^= rhs;
        return lhs;
    }
 
    friend dynamic_bitset operator<<(dynamic_bitset lhs, size_type shift) {
        lhs <<= shift;
        return lhs;
    }
 
    friend dynamic_bitset operator>>(dynamic_bitset lhs, size_type shift) {
        lhs >>= shift;
        return lhs;
    }
 
    // Access operators
    bool operator[](size_type pos) const {
        if (pos >= m_num_bits) {
            return false;
        }
        size_type block_index = pos / bits_per_block;
        size_type bit_index = pos % bits_per_block;
        return (m_blocks[block_index] & (block_type(1) << bit_index)) != 0;
    }
 
    // Set bit at position
    void set(size_type pos, bool value = true) {
        if (pos >= m_num_bits) {
            resize(pos + 1);
        }
        size_type block_index = pos / bits_per_block;
        size_type bit_index = pos % bits_per_block;
        if (value) {
            m_blocks[block_index] |= (block_type(1) << bit_index);
        } else {
            m_blocks[block_index] &= ~(block_type(1) << bit_index);
        }
    }
 
    // Reset bit at position
    void reset(size_type pos) {
        set(pos, false);
    }
 
    // Flip bit at position
    void flip(size_type pos) {
        if (pos >= m_num_bits) {
            resize(pos + 1);
        }
        size_type block_index = pos / bits_per_block;
        size_type bit_index = pos % bits_per_block;
        m_blocks[block_index] ^= (block_type(1) << bit_index);
    }
 
    // Comparison operators
    bool operator==(const dynamic_bitset& rhs) const {
        if (m_num_bits != rhs.m_num_bits) {
            return false;
        }
        return m_blocks == rhs.m_blocks;
    }
 
    bool operator!=(const dynamic_bitset& rhs) const {
        return !(*this == rhs);
    }
 
    // Count number of set bits
    size_type count() const {
        size_type cnt = 0;
        for (const auto& block : m_blocks) {
            cnt += popcount(block);
        }
        return cnt;
    }
 
    // Check if any bits are set
    bool any() const {
        for (const auto& m_block : m_blocks) {
            if (m_block != 0) {
                return true;
            }
        }
        return false;
    }
 
    // Check if no bits are set
    bool none() const {
        return !any();
    }
 
    bool contains(const dynamic_bitset& other) const {
        // Compare up to the size of the `other` mask
        for (size_t i = 0; i < other.size(); ++i) {
            if (other.test(i) && !this->test(i)) {
                return false;
            }
        }
        return true;
    }
 
    // Test bit at position
    bool test(size_type pos) const {
        return operator[](pos);
    }
 
    std::string to_string() const {
        std::string result(m_num_bits, '0');  // Preallocate with '0's
 
        for (size_type i = 0; i < m_num_bits; ++i) {
            if (test(i)) {
                result[m_num_bits - 1 - i] = '1';  // Set bit to '1' directly
            }
        }
        return result;
    }
 
  private:
    std::vector<block_type> m_blocks;
    size_t m_num_bits {0};
 
    void zero_unused_bits() {
        if (m_num_bits == 0)
            return;
        size_type unused_bits = bits_per_block - (m_num_bits % bits_per_block);
        if (unused_bits != bits_per_block) {
            m_blocks.back() &= (block_type(~0) >> unused_bits);
        }
    }
 
#if defined(_MSC_VER)
    inline static int clzll(unsigned long long value) {
        unsigned long index;
        return _BitScanReverse64(&index, value) ? (63 - index) : 64;
    }
#else
    inline static int clzll(unsigned long long value) {
        return value == 0 ? 64 : __builtin_clzll(value);
    }
#endif
 
    static size_type popcount(block_type x) {
#if defined(__GNUC__) || defined(__clang__)
        if constexpr (sizeof(block_type) <= sizeof(unsigned int))
            return __builtin_popcount(x);
        else if constexpr (sizeof(block_type) <= sizeof(unsigned long))
            return __builtin_popcountl(x);
        else if constexpr (sizeof(block_type) <= sizeof(unsigned long long))
            return __builtin_popcountll(x);
        else {
            // Fallback for larger types
            size_type count = 0;
            while (x) {
                x &= x - 1;
                ++count;
            }
            return count;
        }
#elif defined(_MSC_VER)
        if constexpr (sizeof(block_type) == sizeof(unsigned int))
            return __popcnt(static_cast<unsigned int>(x));
        else if constexpr (sizeof(block_type) == sizeof(unsigned long long))
            return __popcnt64(static_cast<unsigned long long>(x));
        else {
            // Fallback for larger types
            size_type count = 0;
            while (x) {
                x &= x - 1;
                ++count;
            }
            return count;
        }
#else
        // Portable fallback
        size_type count = 0;
        while (x) {
            x &= x - 1;
            ++count;
        }
        return count;
#endif
    }
    friend struct std::hash<dynamic_bitset>;
};
 
}  // namespace vecs::storage
 
namespace std {
 
template<>
struct hash<vecs::storage::dynamic_bitset> {
    std::size_t operator()(const vecs::storage::dynamic_bitset& bitset) const {
        using size_type = typename vecs::storage::dynamic_bitset::size_type;
        using block_type = typename vecs::storage::dynamic_bitset::block_type;
 
        std::size_t hash_value = (sizeof(std::size_t) == 4)
            ? 0x811c9dc5  // 32-bit FNV-1a hash seed
            : 0xcbf29ce484222325;  // 64-bit FNV-1a hash seed
 
        for (const block_type& block : bitset.m_blocks) {
            hash_value ^= std::hash<block_type> {}(block) + 0x9e3779b9
                + (hash_value << 6) + (hash_value >> 2);
        }
 
        return hash_value;
    }
};
 
}  // namespace std
 
#endif