DynamicBitSet.hpp

Go to the documentation of this file.

//
//  CeresEngine - A game development framework
//
//  Created by Rogiel Sulzbach.
//  Copyright (c) 2018-2022 Rogiel Sulzbach. All rights reserved.
//
 
#pragma once
 
#include "CeresEngine/DataTypes.hpp"
 
#include "CeresEngine/Foundation/Container/SmallVector.hpp"
#include "CeresEngine/Foundation/Container/Vector.hpp"
 
#include <cassert>
#include <cstdint>
#include <vector>
 
namespace CeresEngine {
 
    struct DynamicBitSetIteratorBase {
        explicit DynamicBitSetIteratorBase(const size_t i) noexcept : index(i) {}
        void inc() { ++index; }
        void dec() { --index; }
        bool operator==(const DynamicBitSetIteratorBase& other) const { return index == other.index; }
        bool operator!=(const DynamicBitSetIteratorBase& other) const { return index != other.index; }
 
        friend ptrdiff_t operator-(const DynamicBitSetIteratorBase& a, const DynamicBitSetIteratorBase& b) { return ptrdiff_t(a.index) - ptrdiff_t(b.index); }
        size_t index;
    };
 
    template<typename Buffer = Vector<uint32_t>> class DynamicBitSet {
    public:
        using buffer_type = Buffer;
        using word_type = typename buffer_type::value_type;
        static_assert(std::is_unsigned<word_type>::value, "word_type must be unsigned");
        using allocator_type = typename buffer_type::allocator_type;
        using size_type = size_t;
        using buffer_size_type = typename buffer_type::size_type;
        static constexpr uint8_t bits_per_word = sizeof(word_type) * 8;
 
        explicit DynamicBitSet(const allocator_type& alloc = allocator_type()) noexcept : mBuffer(alloc), mSize(0) {}
        explicit DynamicBitSet(const size_type size, word_type value = 0, const allocator_type& alloc = allocator_type())
                : mBuffer(word_size(size), value, alloc), mSize(size) {}
 
        // copy and move
        DynamicBitSet(const DynamicBitSet& x) = default;
        DynamicBitSet& operator=(const DynamicBitSet& x) = default;
 
        DynamicBitSet(DynamicBitSet&& x) noexcept : mBuffer(std::move(x.mBuffer)), mSize(x.mSize) { x.mSize = 0; }
        DynamicBitSet& operator=(DynamicBitSet&& x) noexcept {
            mBuffer = std::move(x.mBuffer);
            mSize = x.mSize;
            x.mSize = 0;
            return *this;
        }
 
        // access
        [[nodiscard]] size_type size() const noexcept { return mSize; }
        [[nodiscard]] buffer_size_type word_size() const noexcept { return mBuffer.size(); }
        [[nodiscard]] word_type* data() noexcept { return mBuffer.data(); }
        [[nodiscard]] const word_type* data() const noexcept { return mBuffer.data(); }
        [[nodiscard]] bool empty() const noexcept { return mBuffer.empty(); }
        [[nodiscard]] size_t byte_size() const noexcept { return (mSize + 7) / 8; }
        [[nodiscard]] const buffer_type& buffer() const { return mBuffer; }
 
        [[nodiscard]] bool test(const size_type i) const noexcept { return mBuffer[word_index(i)] & word_mask(i); }
 
        [[nodiscard]] bool all() const noexcept {
            if(empty()) {
                return false;
            }
            auto it = mBuffer.begin();
            auto endit = it + mSize / bits_per_word;
            for(; it != endit; ++it) {
                if(*it != ~word_type(0)) {
                    return false;
                }
            }
            if(endit != mBuffer.end()) {
                word_type mask = word_mask(mSize % bits_per_word) - 1;
                if((mBuffer.back() & mask) != mask) {
                    return false;
                }
            }
            return true;
        }
 
        [[nodiscard]] bool any() const noexcept {
            if(empty()) {
                return false;
            }
            auto it = mBuffer.begin();
            auto endit = it + mSize / bits_per_word;
            for(; it != endit; ++it) {
                if(*it != 0) {
                    return true;
                }
            }
            if(endit != mBuffer.end()) {
                word_type mask = word_mask(mSize % bits_per_word) - 1;
                if(mBuffer.back() & mask) {
                    return true;
                }
            }
            return false;
        }
 
        [[nodiscard]] bool none() const noexcept { return !any(); }
 
        // modifiers
        // set bit to true
        void set(const size_type i) { mBuffer[word_index(i)] |= word_mask(i); }
        // set bit to false
        void reset(const size_type i) { mBuffer[word_index(i)] &= ~word_mask(i); }
        // set bit to value
        void set(const size_type i, const bool b) {
            if(b) {
                set(i);
            } else {
                reset(i);
            }
        }
        // flip bit
        void flip(const size_type i) { mBuffer[word_index(i)] ^= word_mask(i); }
 
        // size modifiers
        void reserve(const size_type size) { mBuffer.reserve(word_size(size)); }
        void resize(const size_type size) {
            const auto pad = mSize % bits_per_word;
            if(pad) {
                // clear the tail of the buf with zeroes in case they remain from previous ops
                mBuffer.back() &= word_mask(pad) - 1;
            }
            mSize = size;
            mBuffer.resize(word_size(size));
        }
        void push_back(const bool b) {
            resize(mSize + 1);
            set(mSize - 1, b);
        }
 
        void assign(const buffer_type& buf) {
            mBuffer = buf;
            mSize = mBuffer.size() * bits_per_word;
        }
 
        void append(const DynamicBitSet& other) {
            if(other.empty()) {
                return;
            }
 
            const auto pad = mSize % bits_per_word;
            if(pad == 0) {
                // lucky
                mBuffer.insert(mBuffer.end(), other.mBuffer.begin(), other.mBuffer.end());
                mSize += other.size();
                return;
            }
 
            auto back_buf_index = mBuffer.size() - 1;
            resize(mSize + other.mSize);
            auto myi = mBuffer.begin() + back_buf_index;
            for(size_t i = 0; i < other.mBuffer.size(); ++i) {
                auto cur = other.mBuffer[i];
                *myi |= cur << pad;
                ++myi;
                if(myi == mBuffer.end()) {
                    break;
                }
                *myi = cur >> (bits_per_word - pad);
            }
        }
 
        // vector-like
        struct bitref {
            bitref(word_type& w, word_type m) : word(w), mask(m) {}
            [[nodiscard]] bool test() const { return word & mask; }
            void set() { word |= mask; }
            void reset() { word &= ~mask; }
            void flip() { word ^= mask; }
            void set(const bool b) {
                if(b) {
                    set();
                } else {
                    reset();
                }
            }
            [[nodiscard]] operator bool() const { return test(); }
            bitref operator=(const bool b) {
                set(b);
                return *this;
            }
 
        private:
            word_type& word;
            const word_type mask;
        };
 
        [[nodiscard]] bool operator[](const size_type i) const { return test(i); }
        [[nodiscard]] bitref operator[](const size_type i) { return bitref(mBuffer[word_index(i)], word_mask(i)); }
 
        struct iterator : public DynamicBitSetIteratorBase {
            iterator(DynamicBitSet& b, const size_t i) : DynamicBitSetIteratorBase(i), bitset(b) {}
            iterator& operator++() {
                inc();
                return *this;
            }
            iterator operator++(int) {
                auto ret = *this;
                inc();
                return ret;
            }
            iterator& operator--() {
                dec();
                return *this;
            }
            iterator operator--(int) {
                auto ret = *this;
                dec();
                return ret;
            }
            friend iterator operator+(iterator a, ptrdiff_t b) { return iterator(a.bitset, a.index + b); }
            friend iterator operator-(iterator a, ptrdiff_t b) { return iterator(a.bitset, a.index - b); }
            bool operator*() const { return bitset.test(index); }
            bitref operator*() { return bitset[index]; }
 
            DynamicBitSet& bitset;
        };
 
        struct const_iterator : public DynamicBitSetIteratorBase {
            const_iterator(const DynamicBitSet& b, const size_t i) : DynamicBitSetIteratorBase(i), bitset(b) {}
            const_iterator(iterator i) : const_iterator(i.bitset, i.index) {}
            const_iterator& operator++() {
                inc();
                return *this;
            }
            const_iterator operator++(int) {
                auto ret = *this;
                inc();
                return ret;
            }
            const_iterator& operator--() {
                dec();
                return *this;
            }
            const_iterator operator--(int) {
                auto ret = *this;
                dec();
                return ret;
            }
            friend const_iterator operator+(const_iterator a, ptrdiff_t b) { return const_iterator(a.bitset, a.index + b); }
            friend const_iterator operator-(const_iterator a, ptrdiff_t b) { return const_iterator(a.bitset, a.index - b); }
            bool operator*() const { return bitset.test(index); }
 
            const DynamicBitSet& bitset;
        };
 
        [[nodiscard]] iterator begin() { return iterator(*this, 0); }
        [[nodiscard]] iterator end() { return iterator(*this, mSize); }
 
        [[nodiscard]] const_iterator begin() const { return const_iterator(*this, 0); }
        [[nodiscard]] const_iterator end() const { return const_iterator(*this, mSize); }
 
        void copy(iterator from, iterator to, const_iterator source) {
            while(from.index % bits_per_word) {
                // copy single bits until we reach a word boundary of our bitset
                if(from == to) {
                    return;
                }
                *from++ = *source++;
            }
 
            const auto pad = source.index % bits_per_word;
            auto own_windex = word_index(from.index);
            auto src_windex = word_index(source.index);
            auto& src = source.bitset.mBuffer;
            // for each whole word of our bitset
            while(to - from >= bits_per_word) {
                mBuffer[own_windex] = src[src_windex] >> pad;
                if(pad) {
                    // there is padding so there must be at least one more element in the source
                    mBuffer[own_windex] |= src[src_windex + 1] << (bits_per_word - pad);
                }
                ++own_windex;
                ++src_windex;
                from.index += bits_per_word;
            }
 
            if(from == to) {
                return; // we finished on a word boundary
            }
 
            // now what remains is some bits from source that need to be splicet onto our last element
            const auto rpad = to.index % bits_per_word;
            mBuffer[own_windex] = ((src[src_windex] >> pad) & (word_mask(rpad) - 1)) | (mBuffer[own_windex] & ~(word_mask(rpad) - 1));
        }
 
        // static ops
 
        static constexpr buffer_size_type word_size(const size_type size) noexcept { return (size + bits_per_word - 1) / bits_per_word; }
 
        static constexpr buffer_size_type word_index(const size_type i) noexcept { return i / bits_per_word; }
 
        static constexpr uint8_t bit_index(const size_type i) noexcept { return uint8_t(i % bits_per_word); }
 
        static constexpr word_type word_mask(const size_type index) noexcept { return word_type(1) << bit_index(index); }
 
    private:
        buffer_type mBuffer;
        size_type mSize; // doesn't need to be divisible by bits_per_word
    };
 
    template<size_t N, typename RawAllocator = DefaultAllocator> using SmallDynamicBitSet = DynamicBitSet<SmallVector<UInt32, N, RawAllocator>>;
 
} // namespace CeresEngine