bitmap.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_BITMAP_HPP__
#define NEFORCE_CORE_CONTAINER_BITMAP_HPP__

 
#include "NeForce/core/interface/iiterator.hpp"
#include "NeForce/core/interface/istringify.hpp"
NEFORCE_BEGIN_NAMESPACE__


NEFORCE_INLINE17 constexpr uint32_t BITMAP_WORD_SIZE = 8 * sizeof(uint32_t);

struct bit_reference : icommon<bit_reference>, istringify<bit_reference> {
private:
    uint32_t* ptr_ = nullptr; 
    uint32_t mask_ = 0;       
 
public:
    NEFORCE_CONSTEXPR20 bit_reference() = default;
    NEFORCE_CONSTEXPR20 ~bit_reference() = default;

    NEFORCE_CONSTEXPR20 bit_reference(uint32_t* ptr, const uint32_t mask) noexcept :
    ptr_(ptr),
    mask_(mask) {}

    NEFORCE_CONSTEXPR20 bit_reference(const bit_reference& other) noexcept :
    ptr_(other.ptr_),
    mask_(other.mask_) {}

    NEFORCE_CONSTEXPR20 bit_reference& operator=(const bit_reference& other) noexcept {
        if (addressof(other) == this) {
            return *this;
        }
        return *this = static_cast<bool>(other);
    }

    NEFORCE_CONSTEXPR20 bit_reference(bit_reference&& other) noexcept :
    ptr_(other.ptr_),
    mask_(other.mask_) {
        other.ptr_ = nullptr;
        other.mask_ = 0;
    }

    NEFORCE_CONSTEXPR20 bit_reference& operator=(bit_reference&& other) noexcept {
        if (addressof(other) == this) {
            return *this;
        }
        *this = static_cast<bool>(other);
        other.ptr_ = nullptr;
        other.mask_ = 0;
        return *this;
    }

    NEFORCE_CONSTEXPR20 bit_reference& operator=(const bool value) noexcept {
        if (ptr_ == nullptr) {
            return *this;
        }
        *ptr_ = (*ptr_ & ~mask_) | (value ? mask_ : 0);
        return *this;
    }

    NEFORCE_CONSTEXPR20 explicit operator bool() const noexcept {
        if (ptr_ == nullptr) {
            return false;
        }
        return (*ptr_ & mask_) != 0U;
    }

    NEFORCE_CONSTEXPR20 void flip() const noexcept {
        if (ptr_ == nullptr) {
            return;
        }
        *ptr_ ^= mask_;
    }

    NEFORCE_CONSTEXPR20 void swap(bit_reference& other) noexcept {
        if (_NEFORCE addressof(other) == this) {
            return;
        }
        const bool tmp = static_cast<bool>(other);
        other = *this;
        *this = tmp;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool equal_to(const bit_reference& rhs) const noexcept {
        return static_cast<bool>(*this) == static_cast<bool>(rhs);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool less_than(const bit_reference& rhs) const noexcept {
        return !static_cast<bool>(*this) && static_cast<bool>(rhs);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 size_t to_hash() const noexcept {
        return hash<bool>()(static_cast<bool>(*this));
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 string to_string() const { return static_cast<bool>(*this) ? "1"_s : "0"_s; }
};
 

template <bool IsConst, typename BitMap>
struct bitmap_iterator : iiterator<bitmap_iterator<IsConst, BitMap>> {
public:
    using container_type = BitMap;                                    
    using value_type = typename container_type::value_type;           
    using size_type = typename container_type::size_type;             
    using difference_type = typename container_type::difference_type; 
    using iterator_category = random_access_iterator_tag;             
    using reference = conditional_t<IsConst, typename container_type::const_reference,
                                    typename container_type::reference>; 
    using pointer = conditional_t<IsConst, typename container_type::const_pointer,
                                  typename container_type::pointer>; 
 
private:
    uint32_t* ptr_ = nullptr;                   
    uint32_t off_ = 0;                          
    const container_type* container_ = nullptr; 
 
    friend class bitmap;
    template <bool, typename>
    friend struct bitmap_iterator;
 
private:
    template <typename Ref>
    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 enable_if_t<is_boolean_v<Ref>, Ref> reference_dispatch() const noexcept {
        return (*ptr_ & (1ULL << off_)) != 0;
    }
 
    template <typename Ref>
    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 enable_if_t<!is_boolean_v<Ref>, Ref> reference_dispatch() const noexcept {
        return Ref(ptr_, 1ULL << off_);
    }
 
public:
    NEFORCE_CONSTEXPR20 bitmap_iterator() noexcept = default;
    NEFORCE_CONSTEXPR20 ~bitmap_iterator() = default;
 
    NEFORCE_CONSTEXPR20 bitmap_iterator(const bitmap_iterator&) noexcept = default;
    NEFORCE_CONSTEXPR20 bitmap_iterator& operator=(const bitmap_iterator&) noexcept = default;
    NEFORCE_CONSTEXPR20 bitmap_iterator(bitmap_iterator&&) noexcept = default;
    NEFORCE_CONSTEXPR20 bitmap_iterator& operator=(bitmap_iterator&&) noexcept = default;

    explicit NEFORCE_CONSTEXPR20 bitmap_iterator(const container_type* bm) noexcept :
    container_(bm) {}

    NEFORCE_CONSTEXPR20 bitmap_iterator(uint32_t* ptr, const uint32_t offset, const container_type* bm) noexcept :
    ptr_(ptr),
    off_(offset),
    container_(bm) {}

    template <bool IsConst2>
    NEFORCE_CONSTEXPR20 explicit bitmap_iterator(const bitmap_iterator<IsConst2, BitMap>& other) noexcept :
    ptr_(other.ptr_),
    off_(other.off_),
    container_(other.container_) {}

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference dereference() const noexcept {
        NEFORCE_DEBUG_VERIFY(ptr_ && container_, "Attempting to dereference on a null pointer");
        return reference_dispatch<reference>();
    }

    NEFORCE_CONSTEXPR20 void increment() noexcept {
        NEFORCE_DEBUG_VERIFY(ptr_ && container_, "Attempting to increment a null pointer");
        if (off_++ == BITMAP_WORD_SIZE - 1) {
            off_ = 0;
            ++ptr_;
        }
    }

    NEFORCE_CONSTEXPR20 void decrement() noexcept {
        NEFORCE_DEBUG_VERIFY(ptr_ && container_, "Attempting to increment a null pointer");
        if (off_-- == 0) {
            off_ = BITMAP_WORD_SIZE - 1;
            --ptr_;
        }
    }

    NEFORCE_CONSTEXPR20 void advance(difference_type off) noexcept {
        NEFORCE_DEBUG_VERIFY((off == 0 || (ptr_ != nullptr && container_ != nullptr)),
                             "Attempting to advance a null pointer");
        difference_type n = off + static_cast<difference_type>(off_);
        ptr_ += n / static_cast<difference_type>(BITMAP_WORD_SIZE);
        n = n % static_cast<difference_type>(BITMAP_WORD_SIZE);
        if (n < 0) {
            off_ = static_cast<uint32_t>(n + BITMAP_WORD_SIZE);
            --ptr_;
        } else {
            off_ = static_cast<uint32_t>(n);
        }
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 difference_type distance_to(const bitmap_iterator& other) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == other.container_, "Attempting to distance to a different container");
        return BITMAP_WORD_SIZE * (ptr_ - other.ptr_) + static_cast<difference_type>(off_) -
               static_cast<difference_type>(other.off_);
    }

    NEFORCE_CONSTEXPR20 reference operator[](const difference_type n) const noexcept { return *(*this + n); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool equal_to(const bitmap_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "Attempting to equal to a different container");
        return ptr_ == rhs.ptr_ && off_ == rhs.off_;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool less_than(const bitmap_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "Attempting to equal to a different container");
        return ptr_ < rhs.ptr_ || (ptr_ == rhs.ptr_ && off_ < rhs.off_);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 decltype(auto) base() const noexcept { return ptr_; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const container_type* container() const noexcept { return container_; }
};
 

class bitmap : public icomparable<bitmap> {
public:
    using value_type = bool;                                                  
    using pointer = bit_reference*;                                           
    using reference = bit_reference;                                          
    using const_pointer = const bool*;                                        
    using const_reference = const bool;                                       
    using size_type = size_t;                                                 
    using difference_type = ptrdiff_t;                                        
    using iterator = bitmap_iterator<false, bitmap>;                          
    using const_iterator = bitmap_iterator<true, bitmap>;                     
    using reverse_iterator = _NEFORCE reverse_iterator<iterator>;             
    using const_reverse_iterator = _NEFORCE reverse_iterator<const_iterator>; 
    using allocator_type = allocator<uint32_t>;                               
 
private:
    struct bit_storage {
        uint32_t* ptr = nullptr;                                                   
        compressed_pair<allocator_type, size_t> cpair{default_construct_tag{}, 0}; 

        NEFORCE_CONSTEXPR20 bit_storage() noexcept = default;

        explicit NEFORCE_CONSTEXPR20 bit_storage(const size_t word) {
            if (word == 0) {
                return;
            }
            ptr = cpair.get_base().allocate(word);
            cpair.value = word;
            memory_zero(ptr, word * sizeof(uint32_t));
        }

        NEFORCE_CONSTEXPR20 ~bit_storage() {
            if (ptr != nullptr) {
                cpair.get_base().deallocate(ptr, cpair.value);
            }
        }
 
        bit_storage(const bit_storage&) = delete;
        bit_storage& operator=(const bit_storage&) = delete;

        NEFORCE_CONSTEXPR20 bit_storage(bit_storage&& other) noexcept :
        ptr(other.ptr),
        cpair(_NEFORCE move(other.cpair)) {
            other.ptr = nullptr;
            other.cpair.value = 0;
        }

        NEFORCE_CONSTEXPR20 bit_storage& operator=(bit_storage&& other) noexcept {
            if (addressof(other) == this) {
                return *this;
            }
 
            reset();
            ptr = other.ptr;
            cpair = _NEFORCE move(other.cpair);
            other.ptr = nullptr;
            other.cpair.value = 0;
 
            return *this;
        }

        NEFORCE_CONSTEXPR20 void reset(uint32_t* new_ptr = nullptr, const size_t cap = 0) {
            if (ptr != nullptr) {
                cpair.get_base().deallocate(ptr, cpair.value);
            }
            ptr = new_ptr;
            cpair.value = cap;
        }

        NEFORCE_CONSTEXPR20 void allocate(const size_t word) { reset(cpair.get_base().allocate(word), word); }

        NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 uint32_t* get() const noexcept { return ptr; }

        NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 size_t capacity() const noexcept { return cpair.value; }
    };
 
    iterator start_{this};  
    iterator finish_{this}; 
    bit_storage storage_;   
 
private:
    static constexpr size_t word_count(const size_type word) noexcept {
        return (word + BITMAP_WORD_SIZE - 1) / BITMAP_WORD_SIZE;
    }

    NEFORCE_CONSTEXPR20 void allocate_storage(const size_type word) {
        if (word == 0) {
            return;
        }
        storage_.allocate(word_count(word));
    }

    NEFORCE_CONSTEXPR20 void set_iterators(const size_type word) noexcept {
        start_ = iterator(storage_.get(), 0, this);
        finish_ = start_ + static_cast<difference_type>(word);
    }

    template <typename Iterator1, typename Iterator2>
    NEFORCE_CONSTEXPR20 Iterator2 bit_copy(Iterator1 first, Iterator1 last, Iterator2 result) {
        iter_difference_t<Iterator1> n = _NEFORCE distance(first, last);
        for (; n > 0; --n, ++first, ++result) {
            *result = *first;
        }
        return result;
    }

    template <typename Iterator1, typename Iterator2>
    NEFORCE_CONSTEXPR20 Iterator2 bit_copy_backward(Iterator1 first, Iterator1 last, Iterator2 result) {
        iter_difference_t<Iterator1> n = _NEFORCE distance(first, last);
        for (; n > 0; --n) {
            *--result = *--last;
        }
        return result;
    }

    void reallocate_insert(const iterator& position, const size_type extra_len, const bool value) {
        const size_type old_size = size();
        const size_type new_size = old_size + extra_len;
        const size_type new_words = word_count(new_size);
        bit_storage new_storage(new_words);
 
        const iterator new_start(new_storage.get(), 0, this);
        auto new_finish = bitmap::bit_copy(begin(), position, new_start);
        _NEFORCE fill_n(new_finish, static_cast<difference_type>(extra_len), value);
        new_finish += static_cast<difference_type>(extra_len);
        new_finish = bitmap::bit_copy(position, end(), new_finish);
 
        storage_ = _NEFORCE move(new_storage);
        start_ = new_start;
        finish_ = new_finish;
    }

    template <typename Iterator>
    void reallocate_insert_range(const iterator position, Iterator first, Iterator last, const size_type extra_len) {
        const size_type old_size = size();
        const size_type new_size = old_size + extra_len;
        const size_type new_words = word_count(new_size);
        bit_storage new_storage(new_words);
 
        const iterator new_start(new_storage.get(), 0, this);
        auto new_finish = bitmap::bit_copy(begin(), position, new_start);
        new_finish = bitmap::bit_copy(first, last, new_finish);
        new_finish = bitmap::bit_copy(position, end(), new_finish);
 
        storage_ = _NEFORCE move(new_storage);
        start_ = new_start;
        finish_ = new_finish;
    }

    void insert_aux(const iterator& position, const bool value) {
        if (finish_.ptr_ != storage_.get() + storage_.capacity()) {
            bit_copy_backward(position, finish_, finish_ + 1);
            *position = value;
            ++finish_;
        } else {
            reallocate_insert(position, 1, value);
        }
    }

    template <typename Iterator>
    enable_if_t<!is_ranges_fwd_iter_v<Iterator>> range_init(Iterator first, Iterator last) {
        if (first == last) {
            return;
        }
 
        bitmap tmp{};
        while (first != last) {
            tmp.push_back(*first);
            ++first;
        }
 
        bitmap::swap(tmp);
        return;
    }

    template <typename Iterator>
    enable_if_t<is_ranges_fwd_iter_v<Iterator>> range_init(Iterator first, Iterator last) {
        if (first == last) {
            return;
        }
 
        const size_type n = _NEFORCE distance(first, last);
        bit_storage tmp_storage(word_count(n));
        iterator tmp_start(tmp_storage.get(), 0, this);
        const iterator tmp_finish = bitmap::bit_copy(first, last, tmp_start);
 
        storage_ = _NEFORCE move(tmp_storage);
        start_ = tmp_start;
        finish_ = tmp_finish;
        return;
    }

    template <typename Iterator>
    enable_if_t<!is_ranges_fwd_iter_v<Iterator>> insert_range(iterator position, Iterator first, Iterator last) {
        if (first == last) {
            return;
        }
        bitmap tmp(first, last);
        insert_range(position, tmp.begin(), tmp.end());
        return;
    }

    template <typename Iterator>
    enable_if_t<is_ranges_fwd_iter_v<Iterator>> insert_range(iterator position, Iterator first, Iterator last) {
        if (first == last) {
            return;
        }
        const size_type n = _NEFORCE distance(first, last);
        if (capacity() - size() >= n) {
            bitmap::bit_copy_backward(position, end(), finish_ + static_cast<difference_type>(n));
            bitmap::bit_copy(first, last, position);
            finish_ += static_cast<difference_type>(n);
        } else {
            bitmap::reallocate_insert_range(position, first, last, n);
        }
        return;
    }
 
public:
    NEFORCE_CONSTEXPR20 bitmap() noexcept = default;

    NEFORCE_CONSTEXPR20 explicit bitmap(const size_type word) {
        if (word == 0) {
            return;
        }
        allocate_storage(word);
        set_iterators(word);
        _NEFORCE fill_n(storage_.get(), static_cast<ptrdiff_t>(storage_.capacity()), 0);
    }

    NEFORCE_CONSTEXPR20 explicit bitmap(const size_type word, const bool value) {
        if (word == 0) {
            return;
        }
        allocate_storage(word);
        set_iterators(word);
        _NEFORCE fill(storage_.get(), storage_.get() + storage_.capacity(), value ? ~0U : 0U);
    }

    NEFORCE_CONSTEXPR20 explicit bitmap(const int32_t word, const bool value) :
    bitmap(static_cast<size_type>(word), value) {}

    NEFORCE_CONSTEXPR20 explicit bitmap(const int64_t word, const bool value) :
    bitmap(static_cast<size_type>(word), value) {}

    NEFORCE_CONSTEXPR20 bitmap(const bitmap& other) {
        if (other.empty()) {
            return;
        }
 
        const size_type n = other.size();
        bit_storage tmp(word_count(n));
        const iterator tmp_start(tmp.get(), 0, this);
        const auto tmp_finish = bit_copy(other.cbegin(), other.cend(), tmp_start);
 
        storage_ = _NEFORCE move(tmp);
        start_ = tmp_start;
        finish_ = tmp_finish;
    }

    NEFORCE_CONSTEXPR20 bitmap& operator=(const bitmap& other) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        bitmap tmp(other);
        *this = _NEFORCE move(tmp);
        // NOLINTNEXTLINE(clang-analyzer-core.StackAddressEscape)
        return *this;
    }

    NEFORCE_CONSTEXPR20 bitmap(bitmap&& other) noexcept :
    start_(other.start_.ptr_, other.start_.off_, this),
    finish_(other.finish_.ptr_, other.finish_.off_, this),
    storage_(_NEFORCE move(other.storage_)) {
        other.start_ = iterator();
        other.finish_ = iterator();
    }

    NEFORCE_CONSTEXPR20 bitmap& operator=(bitmap&& other) noexcept {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        bitmap::swap(other);
        return *this;
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    NEFORCE_CONSTEXPR20 bitmap(Iterator first, Iterator last) {
        bitmap::range_init(first, last);
    }

    NEFORCE_CONSTEXPR20 ~bitmap() = default;

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 iterator begin() noexcept { return start_; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 iterator end() noexcept { return finish_; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_iterator begin() const noexcept { return cbegin(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_iterator end() const noexcept { return cend(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_iterator cbegin() const noexcept { return const_iterator{start_}; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_iterator cend() const noexcept { return const_iterator{finish_}; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reverse_iterator rend() noexcept { return reverse_iterator(begin()); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reverse_iterator rbegin() const noexcept { return crbegin(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reverse_iterator rend() const noexcept { return crend(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reverse_iterator crbegin() const noexcept {
        return const_reverse_iterator(cend());
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reverse_iterator crend() const noexcept {
        return const_reverse_iterator(cbegin());
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 size_type size() const noexcept { return cend() - cbegin(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 size_type max_size() const noexcept { return static_cast<size_type>(-1); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool empty() const noexcept { return start_ == finish_; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 size_type capacity() const noexcept {
        return storage_.capacity() * BITMAP_WORD_SIZE;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference operator[](const size_type n) {
        return *(begin() + static_cast<difference_type>(n));
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reference operator[](const size_type n) const {
        return *(cbegin() + static_cast<difference_type>(n));
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference front() { return *begin(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reference front() const { return *cbegin(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference back() { return *(end() - 1); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reference back() const { return *(cend() - 1); }

    NEFORCE_CONSTEXPR20 void reserve(const size_type n) {
        if (capacity() < n) {
            const size_type new_words = word_count(n);
            bit_storage new_storage(new_words);
            const iterator new_start(new_storage.get(), 0, this);
            const auto new_finish = bit_copy(begin(), end(), new_start);
 
            storage_ = _NEFORCE move(new_storage);
            start_ = new_start;
            finish_ = new_finish;
        }
    }

    NEFORCE_CONSTEXPR20 void push_back(const bool value) {
        if (finish_.ptr_ != storage_.get() + storage_.capacity()) {
            *finish_++ = value;
        } else {
            insert_aux(end(), value);
        }
    }

    NEFORCE_CONSTEXPR20 iterator insert(const iterator& position, const bool value) {
        const difference_type n = position - begin();
        if (finish_.ptr_ != storage_.get() + storage_.capacity() && position == end()) {
            *finish_++ = value;
        } else {
            insert_aux(position, value);
        }
        return begin() + n;
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 void insert(iterator position, Iterator first, Iterator last) {
        bitmap::insert_range(position, first, last);
    }

    NEFORCE_CONSTEXPR20 void insert(const iterator& position, const bool* first, const bool* last) {
        if (first == last) {
            return;
        }
        const size_type n = _NEFORCE distance(first, last);
        if (capacity() - size() >= n) {
            bitmap::bit_copy_backward(position, end(), finish_ + static_cast<difference_type>(n));
            bitmap::bit_copy(first, last, position);
            finish_ += static_cast<difference_type>(n);
        } else {
            bitmap::reallocate_insert_range(position, first, last, n);
        }
    }

    NEFORCE_CONSTEXPR20 void insert(const iterator& position, const size_type n, const bool value) {
        if (n == 0) {
            return;
        }
        if (capacity() - size() >= n) {
            bitmap::bit_copy_backward(position, end(), finish_ + static_cast<difference_type>(n));
            _NEFORCE fill(position, position + static_cast<difference_type>(n), value);
            finish_ += static_cast<difference_type>(n);
        } else {
            bitmap::reallocate_insert(position, n, value);
        }
    }

    NEFORCE_CONSTEXPR20 void insert(const iterator& pos, const int32_t n, const bool value) {
        bitmap::insert(pos, static_cast<size_type>(n), value);
    }

    NEFORCE_CONSTEXPR20 void insert(const iterator& pos, const int64_t n, const bool value) {
        bitmap::insert(pos, static_cast<size_type>(n), value);
    }

    NEFORCE_CONSTEXPR20 void pop_back() { --finish_; }

    NEFORCE_CONSTEXPR20 iterator erase(const iterator& position) {
        if (position + 1 != end()) {
            bitmap::bit_copy(position + 1, end(), position);
        }
        --finish_;
        return position;
    }

    NEFORCE_CONSTEXPR20 iterator erase(const iterator& first, const iterator& last) {
        finish_ = bitmap::bit_copy(last, end(), first);
        return first;
    }

    NEFORCE_CONSTEXPR20 void resize(const size_type n, const bool value = bool()) {
        if (n < size()) {
            bitmap::erase(begin() + static_cast<difference_type>(n), end());
        } else {
            bitmap::insert(end(), n - size(), value);
        }
    }

    NEFORCE_CONSTEXPR20 void clear() { bitmap::erase(begin(), end()); }

    NEFORCE_CONSTEXPR20 void swap(bitmap& other) noexcept {
        if (_NEFORCE addressof(other) == this) {
            return;
        }
        _NEFORCE swap(start_, other.start_);
        _NEFORCE swap(finish_, other.finish_);
        _NEFORCE swap(storage_, other.storage_);
        start_.container_ = this;
        finish_.container_ = this;
        other.start_.container_ = &other;
        other.finish_.container_ = &other;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool equal_to(const bitmap& rhs) const
            noexcept(noexcept(_NEFORCE equal(this->cbegin(), this->cend(), rhs.cbegin()))) {
        return this->size() == rhs.size() && _NEFORCE equal(this->cbegin(), this->cend(), rhs.cbegin());
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool less_than(const bitmap& rhs) const
            noexcept(noexcept(_NEFORCE lexicographical_compare(this->cbegin(), this->cend(), rhs.cbegin(),
                                                               rhs.cend()))) {
        return _NEFORCE lexicographical_compare(this->cbegin(), this->cend(), rhs.cbegin(), rhs.cend());
    }
};
 // BitManipulation
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_BITMAP_HPP__