bitset.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_BITSET_HPP__
#define NEFORCE_CORE_CONTAINER_BITSET_HPP__

 
#include "NeForce/core/container/array.hpp"
#include "NeForce/core/interface/inumeric.hpp"
#include "NeForce/core/interface/istringify.hpp"
#include "NeForce/core/memory/bit.hpp"
NEFORCE_BEGIN_NAMESPACE__


template <size_t N>
class bitset : public icomparable<bitset<N>>, public ibinary<bitset<N>>, public istringify<bitset<N>> {
public:
    class reference {
    private:
        bitset& set_;     
        size_t position_; 
 
    public:
        constexpr reference(bitset& set, const size_t position) noexcept :
        set_(set),
        position_(position) {}

        constexpr reference& operator=(const bool value) noexcept {
            set_.set(position_, value);
            return *this;
        }

        constexpr reference& operator=(const reference& value) noexcept { return *this = static_cast<bool>(value); }

        explicit constexpr operator bool() const noexcept { return set_.test(position_); }

        constexpr reference& flip() noexcept {
            set_.flip(position_);
            return *this;
        }
    };
 
private:
    using block_type = size_t;                                                       
    static constexpr size_t bits_per_block = sizeof(block_type) * 8;                 
    static constexpr size_t block_count = (N + bits_per_block - 1) / bits_per_block; 
 
    array<block_type, block_count> blocks{}; 
 
private:
    static constexpr block_type last_block_mask() noexcept {
        if constexpr (block_count == 0) {
            return 0;
        }
        const size_t excess = block_count * bits_per_block - N;
        if (excess == 0) {
            return static_cast<block_type>(~0ULL);
        }
        return static_cast<block_type>(~0ULL) >> excess;
    }
 
    NEFORCE_ALWAYS_INLINE constexpr void check_range(const size_t pos) const noexcept {
        NEFORCE_DEBUG_VERIFY(pos < N, "bitset position out of range");
    }
 
    NEFORCE_NODISCARD NEFORCE_ALWAYS_INLINE constexpr size_t block_index(const size_t pos) const noexcept {
        return pos / bits_per_block;
    }
 
    NEFORCE_NODISCARD NEFORCE_ALWAYS_INLINE constexpr size_t bit_index(const size_t pos) const noexcept {
        return pos % bits_per_block;
    }
 
public:
    constexpr bitset() noexcept { blocks.fill(0); }

    constexpr explicit bitset(unsigned long long value) noexcept {
        blocks.fill(0);
        static_assert(sizeof(unsigned long long) >= sizeof(block_type),
                      "unsigned long long should be at least as large as block_type");
        size_t i = 0;
        while (value != 0 && i < block_count) {
            blocks[i] = static_cast<block_type>(value);
            NEFORCE_IF_CONSTEXPR(bits_per_block < sizeof(unsigned long long) * 8) {
                value >>= static_cast<uint32_t>(bits_per_block);
            }
            else {
                value = 0;
            }
            ++i;
        }
        NEFORCE_IF_CONSTEXPR(block_count > 0) { blocks[block_count - 1] &= last_block_mask(); }
    }

    constexpr explicit bitset(const string_view str, const char zero = '0', const char one = '1') {
        blocks.fill(0);
        const size_t str_len = str.length();
        const size_t M = (str_len < N) ? str_len : N;
 
        for (size_t i = 0; i < M; ++i) {
            const char c = str[i];
            size_t pos = M - 1 - i;
            if (c == one) {
                set(pos);
            } else if (c == zero) {
                reset(pos);
            } else {
                NEFORCE_THROW_EXCEPTION(value_exception("bitset string ctor: invalid character"));
            }
        }
    }

    constexpr explicit bitset(const string& str, const char zero = '0', const char one = '1') :
    bitset(str.view(), zero, one) {}

    constexpr explicit bitset(const char* str, const char zero = '0', const char one = '1') :
    bitset(string_view{str}, zero, one) {}

    constexpr bitset& set() noexcept {
        for (auto& b: blocks) {
            b = ~static_cast<block_type>(0ULL);
        }
        NEFORCE_IF_CONSTEXPR(N > 0) { blocks[block_count - 1] &= last_block_mask(); }
        return *this;
    }

    constexpr bitset& set(const size_t pos, const bool value = true) noexcept {
        check_range(pos);
        const size_t idx = block_index(pos);
        const size_t bit = bit_index(pos);
        if (value) {
            blocks[idx] |= (static_cast<block_type>(1) << bit);
        } else {
            blocks[idx] &= ~(static_cast<block_type>(1) << bit);
        }
        return *this;
    }

    constexpr bitset& reset() noexcept {
        blocks.fill(0);
        return *this;
    }

    constexpr bitset& reset(const size_t pos) noexcept {
        check_range(pos);
        const size_t idx = block_index(pos);
        const size_t bit = bit_index(pos);
        blocks[idx] &= ~(static_cast<block_type>(1) << bit);
        return *this;
    }

    constexpr bitset& flip() noexcept {
        for (auto& b: blocks) {
            b = ~b;
        }
        blocks[block_count - 1] &= last_block_mask();
        return *this;
    }

    constexpr bitset& flip(const size_t pos) noexcept {
        check_range(pos);
        const size_t idx = block_index(pos);
        const size_t bit = bit_index(pos);
        blocks[idx] ^= (static_cast<block_type>(1) << bit);
        return *this;
    }

    NEFORCE_NODISCARD constexpr bool operator[](const size_t pos) const noexcept { return test(pos); }

    NEFORCE_NODISCARD constexpr reference operator[](size_t pos) noexcept {
        check_range(pos);
        return reference(*this, pos);
    }

    NEFORCE_NODISCARD NEFORCE_ALWAYS_INLINE constexpr size_t size() const noexcept { return N; }

    NEFORCE_NODISCARD NEFORCE_ALWAYS_INLINE constexpr bool empty() const noexcept { return N == 0; }

    NEFORCE_NODISCARD constexpr bool test(const size_t position) const noexcept {
        check_range(position);
        const size_t idx = block_index(position);
        const size_t bit = bit_index(position);
        return (blocks[idx] & (static_cast<block_type>(1) << bit)) != 0;
    }

    constexpr bitset& operator&=(const bitset& other) noexcept {
        for (size_t i = 0; i < block_count; ++i) {
            blocks[i] &= other.blocks[i];
        }
        return *this;
    }

    constexpr bitset& operator|=(const bitset& other) noexcept {
        for (size_t i = 0; i < block_count; ++i) {
            blocks[i] |= other.blocks[i];
        }
        return *this;
    }

    constexpr bitset& operator^=(const bitset& other) noexcept {
        for (size_t i = 0; i < block_count; ++i) {
            blocks[i] ^= other.blocks[i];
        }
        return *this;
    }

    NEFORCE_NODISCARD constexpr bitset operator~() const noexcept {
        bitset res = *this;
        res.flip();
        return res;
    }

    constexpr bitset& operator<<=(const uint32_t pos) noexcept {
        if (pos >= N) {
            reset();
            return *this;
        }
        const size_t block_shift = pos / bits_per_block;
        const size_t bit_shift = pos % bits_per_block;
 
        if (block_shift > 0) {
            for (size_t i = block_count - 1; i >= block_shift; --i) {
                blocks[i] = blocks[i - block_shift];
            }
            for (size_t i = 0; i < block_shift; ++i) {
                blocks[i] = 0;
            }
        }
        if (bit_shift > 0) {
            for (size_t i = block_count - 1; i > 0; --i) {
                blocks[i] = (blocks[i] << bit_shift) | (blocks[i - 1] >> (bits_per_block - bit_shift));
            }
            blocks[0] <<= bit_shift;
        }
        blocks[block_count - 1] &= last_block_mask();
 
        return *this;
    }

    constexpr bitset& operator>>=(const uint32_t pos) noexcept {
        if (pos >= N) {
            reset();
            return *this;
        }
        const size_t block_shift = pos / bits_per_block;
        const size_t bit_shift = pos % bits_per_block;
 
        if (block_shift > 0) {
            for (size_t i = 0; i < block_count - block_shift; ++i) {
                blocks[i] = blocks[i + block_shift];
            }
            for (size_t i = block_count - block_shift; i < block_count; ++i) {
                blocks[i] = 0;
            }
        }
        if (bit_shift > 0) {
            for (size_t i = 0; i < block_count - 1; ++i) {
                blocks[i] = (blocks[i] >> bit_shift) | (blocks[i + 1] << (bits_per_block - bit_shift));
            }
            blocks[block_count - 1] >>= bit_shift;
            blocks[block_count - 1] &= last_block_mask();
        }
        return *this;
    }

    NEFORCE_NODISCARD constexpr size_t count() const noexcept {
        size_t cnt = 0;
        for (size_t i = 0; i < block_count; ++i) {
            cnt += _NEFORCE popcount(blocks[i]);
        }
        return cnt;
    }

    NEFORCE_NODISCARD constexpr bool all() const noexcept {
        NEFORCE_IF_CONSTEXPR(N == 0) { return true; }
        for (size_t i = 0; i < block_count - 1; ++i) {
            if (blocks[i] != ~static_cast<block_type>(0ULL)) {
                return false;
            }
        }
        return blocks[block_count - 1] == last_block_mask();
    }

    NEFORCE_NODISCARD constexpr bool any() const noexcept {
        for (auto b: blocks) {
            if (b != 0) {
                return true;
            }
        }
        return false;
    }

    NEFORCE_NODISCARD constexpr bool none() const noexcept { return !any(); }

    NEFORCE_NODISCARD constexpr unsigned long to_ulong() const {
        NEFORCE_IF_CONSTEXPR(N > sizeof(unsigned long) * 8) {
            constexpr size_t ulong_blocks = (sizeof(unsigned long) * 8 + bits_per_block - 1) / bits_per_block;
            for (size_t i = ulong_blocks; i < block_count; ++i) {
                if (blocks[i] != 0) {
                    NEFORCE_THROW_EXCEPTION(value_exception("bitset to_ulong overflow"));
                }
            }
 
            constexpr size_t ulong_bits = sizeof(unsigned long) * 8;
            constexpr size_t remainder_bits = ulong_bits % bits_per_block;
            NEFORCE_IF_CONSTEXPR(remainder_bits != 0) {
                constexpr size_t last_ulong_block = ulong_bits / bits_per_block;
                block_type mask = (~static_cast<block_type>(0ULL)) << remainder_bits;
                if ((blocks[last_ulong_block] & mask) != 0) {
                    NEFORCE_THROW_EXCEPTION(value_exception("bitset to_ulong overflow"));
                }
            }
        }
 
        NEFORCE_IF_CONSTEXPR(sizeof(unsigned long) >= sizeof(block_type)) {
            return static_cast<unsigned long>(blocks[0]);
        }
        else {
            unsigned long result = 0;
            constexpr size_t ulong_blocks = (sizeof(unsigned long) * 8 + bits_per_block - 1) / bits_per_block;
            constexpr size_t blocks_to_use = ulong_blocks < block_count ? ulong_blocks : block_count;
            for (size_t i = 0; i < blocks_to_use; ++i) {
                result |= static_cast<unsigned long>(blocks[i]) << (i * bits_per_block);
            }
            return result;
        }
    }

    NEFORCE_NODISCARD constexpr unsigned long long to_ullong() const {
        NEFORCE_IF_CONSTEXPR(N > sizeof(unsigned long long) * 8) {
            constexpr size_t ullong_blocks = (sizeof(unsigned long long) * 8 + bits_per_block - 1) / bits_per_block;
            for (size_t i = ullong_blocks; i < block_count; ++i) {
                if (blocks[i] != 0) {
                    NEFORCE_THROW_EXCEPTION(value_exception("bitset to_ullong overflow"));
                }
            }
 
            constexpr size_t ullong_bits = sizeof(unsigned long long) * 8;
            constexpr size_t remainder_bits = ullong_bits % bits_per_block;
            NEFORCE_IF_CONSTEXPR(remainder_bits != 0) {
                constexpr size_t last_ullong_block = ullong_bits / bits_per_block;
                block_type mask = (~static_cast<block_type>(0ULL)) << remainder_bits;
                if ((blocks[last_ullong_block] & mask) != 0) {
                    NEFORCE_THROW_EXCEPTION(value_exception("bitset to_ullong overflow"));
                }
            }
        }
 
        unsigned long long result = 0;
        constexpr size_t ullong_bits = sizeof(unsigned long long) * 8;
        constexpr size_t blocks_needed = (ullong_bits + bits_per_block - 1) / bits_per_block;
        constexpr size_t blocks_to_use = (block_count < blocks_needed) ? block_count : blocks_needed;
        for (size_t i = 0; i < blocks_to_use; ++i) {
            result |= static_cast<unsigned long long>(blocks[i]) << (i * bits_per_block);
        }
        return result;
    }

    NEFORCE_NODISCARD constexpr bool equal_to(const bitset& other) const noexcept { return blocks == other.blocks; }

    NEFORCE_NODISCARD constexpr bool less_than(const bitset& other) const noexcept { return blocks < other.blocks; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 string to_string(const char zero, const char one) const {
        string result;
        result.reserve(N);
        for (size_t i = N; i > 0; --i) {
            result.push_back(test(i - 1) ? one : zero);
        }
        return result;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 string to_string() const { return bitset::to_string('0', '1'); }

    constexpr void swap(bitset& other) noexcept { blocks.swap(other.blocks); }
};
 // BitManipulation
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_BITSET_HPP__