BitSet.hpp

Go to the documentation of this file.

 
 
#ifndef UTIL_BITSET_HPP_
#define UTIL_BITSET_HPP_
 
#include <bit>
#include <cstddef>
#include <cstdint>
#include <ostream>
#include <vector>
#include <string_view>
 
// As of 2022, C++20 is still considered "experimental" by G++, `constexpr` for std::vector was only added in G++ 12.1.
// So we need to disable `constexpr` on most BitSet functions in G++ versions below 12.1.
//
// For G++ 12.1 and above, em++, and MSVC, constexpr support is enabled.
#if !defined(__clang__) && defined(__GNUG__) && (__GNUG__ < 12 || __GNUC_MINOR__ < 1)
    #define BIT_SET_CONSTEXPR inline
#else
    #define BIT_SET_CONSTEXPR constexpr
#endif // !defined(__clang__) && defined(__GNUG__) && (__GNUG__ < 12 || __GNUC_MINOR__ < 1)
 
namespace util
{
    class BitSet {
      public:
        class Reference {
          public:
            BIT_SET_CONSTEXPR Reference &operator=(bool value) noexcept
            {
                this->_set.set(this->_pos, value);
                return *this;
            }
 
            BIT_SET_CONSTEXPR operator bool() const noexcept
            {
                return const_cast<BitSet const &>(this->_set)[this->_pos];
            }
 
            BIT_SET_CONSTEXPR bool operator~() const noexcept
            {
                return !bool(*this);
            }
 
            BIT_SET_CONSTEXPR Reference &flip() noexcept
            {
                *this = ~(*this);
                return *this;
            }
 
          private:
            BitSet &_set;
            std::size_t _pos;
 
            constexpr Reference(BitSet &set, std::size_t pos) : _set(set), _pos(pos)
            {
            }
 
            friend BitSet;
        };
 
        BitSet(std::size_t initialSize = 0);
 
        BitSet(std::string_view bitString);
 
        [[nodiscard]] constexpr std::size_t size() const noexcept
        {
            return this->_size;
        }
 
        [[nodiscard]] BIT_SET_CONSTEXPR bool test(std::size_t pos) const noexcept
        {
            return (this->_store[pos >> 6] & mask(pos)) != 0;
        }
 
        [[nodiscard]] BIT_SET_CONSTEXPR bool operator[](std::size_t pos) const noexcept
        {
            return this->test(pos);
        }
 
        BIT_SET_CONSTEXPR BitSet &set(std::size_t pos, bool value = true) noexcept
        {
            if (value)
                this->_store[pos >> 6] |= mask(pos);
            else
                this->_store[pos >> 6] &= ~mask(pos);
            return *this;
        }
 
        BitSet &setAll(bool value = true) noexcept;
 
        constexpr Reference operator[](std::size_t pos) noexcept
        {
            return Reference(*this, pos);
        }
 
        [[nodiscard]] bool operator==(BitSet const &other) const noexcept;
 
        [[nodiscard]] bool operator!=(BitSet const &other) const noexcept;
 
        BitSet &flip() noexcept;
 
        BitSet operator~() const;
 
        BitSet operator&(BitSet const &other) const;
 
        BitSet operator|(BitSet const &other) const;
 
        BitSet operator^(BitSet const &other) const;
 
        BitSet &operator&=(BitSet const &other) noexcept;
 
        BitSet &operator|=(BitSet const &other) noexcept;
 
        BitSet &operator^=(BitSet const &other) noexcept;
 
        BitSet &inplaceAnd(BitSet const &other) noexcept;
 
        BitSet &inplaceOr(BitSet const &other) noexcept;
 
        BitSet &inplaceXor(BitSet const &other) noexcept;
 
        inline void resize(std::size_t size)
        {
            this->_resize(size);
            this->normalize();
        }
 
        void resizeSentinel(std::size_t size, bool sentinelValue);
 
        BitSet &push(bool value);
 
        bool pop();
 
        [[nodiscard]] BIT_SET_CONSTEXPR std::size_t firstSet(std::size_t start = 0) const
        {
            std::uint64_t mask = (~std::uint64_t(0)) << (start & 0b111111);
            std::size_t word_pos = start >> 6;
            std::uint64_t word = this->_store[word_pos] & mask;
 
            while (word == 0) {
                ++word_pos;
                word = this->_store[word_pos];
            }
            return (word_pos << 6) + static_cast<std::size_t>(std::countr_zero(word));
        }
 
        [[nodiscard]] BIT_SET_CONSTEXPR std::size_t lastSet() const
        {
            std::uint64_t mask = ~((~std::uint64_t(0)) << (_size & 0b111111));
            std::size_t word_pos = _size >> 6;
            std::uint64_t word = this->_store[word_pos] & mask;
 
            while (word == 0) {
                // Avoid underflow
                if (word_pos == 0)
                    break;
                --word_pos;
                word = this->_store[word_pos];
            }
            if (word == 0)
                return 0;
            return (word_pos << 6) + static_cast<std::size_t>(0b111111 - std::countl_zero(word));
        }
 
        [[nodiscard]] BIT_SET_CONSTEXPR std::size_t firstUnset(std::size_t start = 0) const
        {
            std::uint64_t mask = (~std::uint64_t(0)) << (start & 0b111111);
            std::size_t word_pos = start >> 6;
            std::uint64_t word = this->_store[word_pos] | (~mask);
 
            while (word == (~std::uint64_t(0))) {
                ++word_pos;
                word = this->_store[word_pos];
            }
            return (word_pos << 6) + static_cast<std::size_t>(std::countr_one(word));
        }
 
        [[nodiscard]] BIT_SET_CONSTEXPR std::size_t lastUnset() const
        {
            std::uint64_t mask = ~((~std::uint64_t(0)) << (_size & 0b111111));
            std::size_t word_pos = _size >> 6;
            std::uint64_t word = this->_store[word_pos] | (~mask);
 
            while (word == (~std::uint64_t(0))) {
                // Avoid underflow
                if (word_pos == 0)
                    break;
                --word_pos;
                word = this->_store[word_pos];
            }
            if (word == (~std::uint64_t(0)))
                return 0;
            return (word_pos << 6) + static_cast<std::size_t>(0b111111 - std::countl_one(word));
        }
 
      private:
        std::size_t _size;
        std::vector<std::uint64_t> _store;
 
        static constexpr std::uint64_t mask(std::size_t pos)
        {
            return std::uint64_t(1) << (pos & 0b111111);
        }
 
        static constexpr std::size_t getStoreWordCount(std::size_t bitCount)
        {
            if ((bitCount & (~static_cast<std::size_t>(0b111111))) == bitCount)
                return bitCount >> 6; // if bitCount is a multiple of 64, return bitCount / 64
            else
                return (bitCount >> 6) + 1; // or else, add one word to contain the extra bits
        }
 
        void normalize() noexcept;
 
        void _resize(std::size_t size);
 
        friend Reference;
        friend class BitSetTester;
    };
 
    std::ostream &operator<<(std::ostream &output, BitSet const &set);
} // namespace util
 
#endif // !defined(UTIL_BITSET_HPP_)