bitSet.h

Go to the documentation of this file.

#ifndef BITSET_H
#define BITSET_H
 
#include "array.h"
#include "couple.h"
#include "iterationStream.h"
 
 
namespace original {

    template<typename ALLOC = allocator<bool>>
    class bitSet final : public baseArray<bool, ALLOC>, public iterationStream<bool, bitSet<ALLOC>>{
            using underlying_type = u_integer;

            using rebind_alloc_underlying = typename ALLOC::template rebind_alloc<underlying_type>;
 
            static constexpr integer BLOCK_MAX_SIZE = sizeof(underlying_type) * 8; 

            array<underlying_type, rebind_alloc_underlying> map;
 
            u_integer size_; 
 

            void bitsetInit(u_integer size);

            [[nodiscard]] static bool getBitFromBlock(underlying_type block_value, integer bit);

            [[nodiscard]] static underlying_type setBitFromBlock(underlying_type block_value, integer bit);

            [[nodiscard]] static underlying_type clearBitFromBlock(underlying_type block_value, integer bit);

            [[nodiscard]] static underlying_type clearHigherBitsFromBlock(underlying_type block_value, integer bit);

            void clearRedundantBits();

            [[nodiscard]] bool getBit(integer bit, integer block) const;

            void setBit(integer bit, integer block);

            void clearBit(integer bit, integer block);

            void writeBit(integer bit, integer block, bool value);

            static couple<u_integer, integer> toInnerIdx(integer index);

            static integer toOuterIdx(u_integer cur_block, integer cur_bit);
 
        public:

        class Iterator final : public baseIterator<bool> {
                mutable integer cur_bit; 
                mutable integer cur_block; 
                mutable underlying_type* block_; 
                const bitSet* container_; 

                explicit Iterator(integer bit, integer block, underlying_type* block_p, const bitSet* container);

                bool equalPtr(const iterator *other) const override;
 
            public:
                friend class bitSet;

                Iterator* clone() const override;

                [[nodiscard]] bool hasNext() const override;

                [[nodiscard]] bool hasPrev() const override;

                bool atPrev(const iterator *other) const override;

                bool atNext(const iterator *other) const override;

                void next() const override;

                void prev() const override;

                Iterator* getPrev() const override;

                Iterator* getNext() const override;

                void operator+=(integer steps) const override;

                void operator-=(integer steps) const override;

                integer operator-(const iterator& other) const override;

                bool& get() override;

                [[nodiscard]] std::string className() const override;

                [[nodiscard]] bool get() const override;

                void set(const bool &data) override;

                [[nodiscard]] bool isValid() const override;
        };

            explicit bitSet(u_integer size, ALLOC allocator = ALLOC{});

            bitSet(const std::initializer_list<bool>& lst);

            bitSet(const bitSet& other);

            bitSet& operator=(const bitSet& other);

            bitSet(bitSet&& other) noexcept;

            bitSet& operator=(bitSet&& other) noexcept;

            [[nodiscard]] u_integer count() const;

            [[nodiscard]] bitSet resize(u_integer new_size) const;

            [[nodiscard]] u_integer size() const override;

            [[nodiscard]] Iterator* begins() const override;

            [[nodiscard]] Iterator* ends() const override;

            [[nodiscard]] bool get(integer index) const override;

            bool& operator[](integer index) override;

            void set(integer index, const bool &e) override;

            [[nodiscard]] u_integer indexOf(const bool &e) const override;
 
            ~bitSet() override = default;

            bitSet& operator&=(const bitSet& other);

            bitSet& operator|=(const bitSet& other);

            bitSet& operator^=(const bitSet& other);

            [[nodiscard]] std::string className() const override;
 
 
            template<typename Callback = transform<bool>>
            void forEach(Callback operation = Callback{}) = delete;

            template<typename ALLOC_>
            friend bitSet<ALLOC_> operator&(const bitSet<ALLOC_>& lbs, const bitSet<ALLOC_>& rbs);

            template<typename ALLOC_>
            friend bitSet<ALLOC_> operator|(const bitSet<ALLOC_>& lbs, const bitSet<ALLOC_>& rbs);

            template<typename ALLOC_>
            friend bitSet<ALLOC_> operator^(const bitSet<ALLOC_>& lbs, const bitSet<ALLOC_>& rbs);

            template<typename ALLOC_>
            friend bitSet<ALLOC_> operator~(const bitSet<ALLOC_>& bs);
    };
 
    template<typename ALLOC_>
    bitSet<ALLOC_> operator&(const bitSet<ALLOC_>& lbs, const bitSet<ALLOC_>& rbs);
 
    template<typename ALLOC_>
    bitSet<ALLOC_> operator|(const bitSet<ALLOC_>& lbs, const bitSet<ALLOC_>& rbs);
 
    template<typename ALLOC_>
    bitSet<ALLOC_> operator^(const bitSet<ALLOC_>& lbs, const bitSet<ALLOC_>& rbs);
 
    template<typename ALLOC_>
    bitSet<ALLOC_> operator~(const bitSet<ALLOC_>& bs);
}
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::bitsetInit(const u_integer size) -> void
    {
        this->map = array<underlying_type, rebind_alloc_underlying>((size + BLOCK_MAX_SIZE - 1) / BLOCK_MAX_SIZE, rebind_alloc_underlying{});
        this->size_ = size;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::getBitFromBlock(const underlying_type block_value, const integer bit) -> bool {
        return block_value & static_cast<underlying_type>(1) << bit;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::setBitFromBlock(const underlying_type block_value, const integer bit) -> underlying_type {
        return block_value | static_cast<underlying_type>(1) << bit;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::clearBitFromBlock(const underlying_type block_value, const integer bit) -> underlying_type {
        return block_value & ~(static_cast<underlying_type>(1) << bit);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::clearHigherBitsFromBlock(const underlying_type block_value, const integer bit) -> underlying_type
    {
        return block_value & (static_cast<underlying_type>(1) << (bit + 1)) - static_cast<underlying_type>(1);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::clearRedundantBits() -> void
    {
        this->map.set(-1, clearHigherBitsFromBlock(this->map.get(-1), toInnerIdx(this->size() - 1).second()));
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::getBit(const integer bit, const integer block) const -> bool {
        return getBitFromBlock(this->map.get(block), bit);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::setBit(const integer bit, const integer block) -> void {
        this->map.set(block, setBitFromBlock(this->map.get(block), bit));
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::clearBit(const integer bit, const integer block) -> void {
        this->map.set(block, clearBitFromBlock(this->map.get(block), bit));
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::writeBit(const integer bit, const integer block, const bool value) -> void {
        value ? this->setBit(bit, block) : this->clearBit(bit, block);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::toInnerIdx(const integer index) -> couple<u_integer, integer> {
        return {static_cast<u_integer>(index / BLOCK_MAX_SIZE), index % BLOCK_MAX_SIZE};
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::toOuterIdx(const u_integer cur_block, const integer cur_bit) -> integer
    {
        return cur_block *  BLOCK_MAX_SIZE + cur_bit;
    }
 
    template<typename ALLOC>
    original::bitSet<ALLOC>::Iterator::Iterator(const integer bit, const integer block, underlying_type* block_p, const bitSet* container)
        : cur_bit(bit), cur_block(block), block_(block_p), container_(container) {}
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::equalPtr(const iterator *other) const -> bool {
        auto* other_it = dynamic_cast<const Iterator*>(other);
        return other_it != nullptr
            && this->cur_bit == other_it->cur_bit
            && this->cur_block == other_it->cur_block;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::clone() const -> Iterator* {
        return new Iterator(*this);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::hasNext() const -> bool {
        return toOuterIdx(this->cur_block, this->cur_bit) < this->container_->size() - 1;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::hasPrev() const -> bool {
        return toOuterIdx(this->cur_block, this->cur_bit) > 0;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::atPrev(const iterator *other) const -> bool {
        auto* other_it = dynamic_cast<const Iterator*>(other);
        if (other_it == nullptr)
            return false;
        return this->operator-(*other_it) == -1;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::atNext(const iterator *other) const -> bool {
        auto* other_it = dynamic_cast<const Iterator*>(other);
        if (other_it == nullptr)
            return false;
        return this->operator-(*other_it) == 1;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::next() const -> void {
        this->operator+=(1);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::prev() const -> void {
        this->operator-=(1);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::getPrev() const -> Iterator* {
        if (!this->isValid()) throw outOfBoundError();
        auto* it = this->clone();
        it->prev();
        return it;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::getNext() const -> Iterator* {
        if (!this->isValid()) throw outOfBoundError();
        auto* it = this->clone();
        it->next();
        return it;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::operator+=(const integer steps) const -> void
    {
        auto new_idx = toInnerIdx(toOuterIdx(this->cur_block, this->cur_bit) + steps);
        this->cur_block = new_idx.first();
        this->cur_bit = new_idx.second();
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::operator-=(const integer steps) const -> void
    {
        auto new_idx = toInnerIdx(toOuterIdx(this->cur_block, this->cur_bit) - steps);
        this->cur_block = new_idx.first();
        this->cur_bit = new_idx.second();
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::operator-(const iterator &other) const -> integer {
        auto* other_it = dynamic_cast<const Iterator*>(&other);
        if (other_it == nullptr)
            return this > &other ?
                std::numeric_limits<integer>::max() :
                std::numeric_limits<integer>::min();
        if (this->container_ != other_it->container_)
            return this->container_ > other_it->container_ ?
                std::numeric_limits<integer>::max() :
                std::numeric_limits<integer>::min();
 
        return toOuterIdx(this->cur_block, this->cur_bit) - toOuterIdx(other_it->cur_block, other_it->cur_bit);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::get() -> bool & {
        throw unSupportedMethodError();
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::className() const -> std::string {
        return "bitSet::Iterator";
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::get() const -> bool
    {
        if (!this->isValid()) throw outOfBoundError();
        return getBitFromBlock(*this->block_, this->cur_bit);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::set(const bool &data) -> void {
        if (!this->isValid()) throw outOfBoundError();
        *this->block_ = data ?
         setBitFromBlock(*this->block_, this->cur_bit) : clearBitFromBlock(*this->block_, this->cur_bit);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::Iterator::isValid() const -> bool {
        const auto outer = toOuterIdx(this->cur_block, this->cur_bit);
        return outer >= 0 && outer < this->container_->size();
    }
 
    template<typename ALLOC>
    original::bitSet<ALLOC>::bitSet(const u_integer size, ALLOC allocator)
        : baseArray<bool, ALLOC>(std::move(allocator)), size_() {
            this->bitsetInit(size);
    }
 
    template<typename ALLOC>
    original::bitSet<ALLOC>::bitSet(const std::initializer_list<bool>& lst) : bitSet(lst.size()) {
        u_integer i = 0;
        for (const auto& e : lst) {
            auto idx = toInnerIdx(i);
            this->writeBit(idx.second(), idx.first(), e);
            i += 1;
        }
    }
 
    template<typename ALLOC>
    original::bitSet<ALLOC>::bitSet(const bitSet &other) : bitSet(other.size()) {
        this->operator=(other);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::operator=(const bitSet &other) -> bitSet& {
        if (this == &other) return *this;
        this->map = other.map;
        this->size_ = other.size_;
        if constexpr (ALLOC::propagate_on_container_copy_assignment::value){
            this->allocator = other.allocator;
        }
        return *this;
    }
 
    template<typename ALLOC>
    original::bitSet<ALLOC>::bitSet(bitSet&& other)  noexcept : bitSet(0)
    {
        this->operator=(std::move(other));
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::operator=(bitSet&& other)  noexcept -> bitSet&
    {
        if (this == &other)
            return *this;
 
        this->map = std::move(other.map);
        this->size_ = other.size_;
        if constexpr (ALLOC::propagate_on_container_move_assignment::value){
            this->allocator = other.allocator;
        }
        other.bitsetInit(0);
        return *this;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::count() const -> u_integer {
        u_integer count = 0;
        for (const auto& e : this->map) {
            auto n = e;
            while (n) {
                n &= n - 1;
                count += 1;
            }
        }
        return count;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::resize(const u_integer new_size) const -> bitSet {
        if (this->size() == new_size) {
            return *this;
        }
 
        auto nb = bitSet(new_size);
        const u_integer blocks_min = min(nb.map.size(),
                                        this->map.size());
        for (u_integer i = 0; i < blocks_min; i++) {
            nb.map.set(i, this->map.get(i));
        }
        nb.clearRedundantBits();
        return nb;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::size() const -> u_integer
    {
        return this->size_;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::begins() const -> Iterator* {
        return new Iterator(0, 0, &this->map.data(), this);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::ends() const -> Iterator* {
        return new Iterator(toInnerIdx(this->size() - 1).second(), this->map.size() - 1,
                    &this->map.data() + this->map.size() - 1, this);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::get(integer index) const -> bool {
        if (this->indexOutOfBound(index)) throw outOfBoundError();
        index = this->parseNegIndex(index);
        auto idx = toInnerIdx(index);
        return this->getBit(idx.second(), idx.first());
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::operator[](integer) -> bool& {
        throw unSupportedMethodError();
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::set(integer index, const bool &e) -> void {
        if (this->indexOutOfBound(index)) throw outOfBoundError();
        index = this->parseNegIndex(index);
        auto idx = toInnerIdx(index);
        this->writeBit(idx.second(), idx.first(), e);
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::indexOf(const bool &e) const -> u_integer {
        for (u_integer i = 0; i < this->size(); i++) {
            if (auto idx = toInnerIdx(i);
                e == this->getBit(idx.second(), idx.first())) {
                return i;
            }
        }
        return this->size();
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::operator&=(const bitSet &other) -> bitSet& {
        if (this->size() != other.size()) {
            const auto resized = other.resize(this->size());
            for (u_integer i = 0; i < this->map.size(); i++) {
                this->map.set(i, this->map.get(i) & resized.map.get(i));
            }
        }else {
            for (u_integer i = 0; i < this->map.size(); i++) {
                this->map.set(i, this->map.get(i) & other.map.get(i));
            }
        }
        return *this;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::operator|=(const bitSet &other) -> bitSet& {
        if (this->size() != other.size()) {
            const auto resized = other.resize(this->size());
            for (u_integer i = 0; i < this->map.size(); i++) {
                this->map.set(i, this->map.get(i) | resized.map.get(i));
            }
        }else {
            for (u_integer i = 0; i < this->map.size(); i++) {
                this->map.set(i, this->map.get(i) | other.map.get(i));
            }
        }
        return *this;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::operator^=(const bitSet &other) -> bitSet& {
        if (this->size() != other.size()) {
            const auto resized = other.resize(this->size());
            for (u_integer i = 0; i < this->map.size(); i++) {
                this->map.set(i, this->map.get(i) ^ resized.map.get(i));
            }
        }else {
            for (u_integer i = 0; i < this->map.size(); i++) {
                this->map.set(i, this->map.get(i) ^ other.map.get(i));
            }
        }
        return *this;
    }
 
    template<typename ALLOC>
    auto original::bitSet<ALLOC>::className() const -> std::string {
        return "bitSet";
    }
 
    template<typename ALLOC_>
    auto original::operator&(const bitSet<ALLOC_> &lbs, const bitSet<ALLOC_> &rbs) -> bitSet<ALLOC_> {
        bitSet bs(lbs);
        return bs &= rbs;
    }
 
    template<typename ALLOC_>
    auto original::operator|(const bitSet<ALLOC_> &lbs, const bitSet<ALLOC_> &rbs) -> bitSet<ALLOC_> {
        bitSet bs(lbs);
        return bs |= rbs;
    }
 
    template<typename ALLOC_>
    auto original::operator^(const bitSet<ALLOC_> &lbs, const bitSet<ALLOC_> &rbs) -> bitSet<ALLOC_> {
        bitSet bs(lbs);
        return bs ^= rbs;
    }
 
    template<typename ALLOC_>
    auto original::operator~(const bitSet<ALLOC_> &bs) -> bitSet<ALLOC_> {
        bitSet nbs(bs);
        for (u_integer i = 0; i < nbs.map.size(); i++) {
            nbs.map.set(i, ~nbs.map.get(i));
        }
        nbs.clearRedundantBits();
        return nbs;
    }
 
#endif //BITSET_H