blocksList.h

Go to the documentation of this file.

#ifndef BLOCKSLIST_H
#define BLOCKSLIST_H
 
#include "baseList.h"
#include "couple.h"
#include "vector.h"
 
namespace original {
    template <typename TYPE, typename ALLOC = allocator<TYPE>>
    class blocksList final : public baseList<TYPE, ALLOC>, public iterationStream<TYPE, blocksList<TYPE, ALLOC>> {
        static constexpr u_integer BLOCK_MAX_SIZE = 16; 
        static constexpr u_integer POS_INIT = (BLOCK_MAX_SIZE - 1) / 2 + 1; 
 
        vector<TYPE*> map;
 
        u_integer size_; 
        u_integer first_; 
        u_integer last_; 
        u_integer first_block; 
        u_integer last_block; 
 
 
        TYPE* blockArrayInit();
 
        void blocksListInit();
 
        void blocksListDestroy() noexcept;
 
        [[nodiscard]] static u_integer innerIdxToAbsIdx(u_integer block, u_integer pos);
 
        [[nodiscard]] u_integer firstAbsIdx() const;
 
        [[nodiscard]] u_integer lastAbsIdx() const;
 
        [[nodiscard]] integer absIdxToOuterIdx(u_integer absIdx) const;
 
        [[nodiscard]] u_integer outerIdxToAbsIdx(integer outerIdx) const;
 
        [[nodiscard]] static couple<u_integer, u_integer> absIdxToInnerIdx(u_integer absIdx);
 
        [[nodiscard]] static couple<u_integer, u_integer> innerIdxOffset(u_integer block, u_integer pos, integer offset);
 
        [[nodiscard]] couple<u_integer, u_integer> outerIdxToInnerIdx(integer outerIdx) const;
 
        [[nodiscard]] integer innerIdxToOuterIdx(u_integer block, u_integer pos) const;
 
        TYPE& getElem(u_integer block, u_integer pos) const;
 
        void setElem(u_integer block, u_integer pos, const TYPE& e);
 
        [[nodiscard]] bool growNeeded(u_integer increment, bool is_first) const;
 
        void moveElements(u_integer start_block, u_integer start_pos, u_integer len, integer offset);
 
        void addBlock(bool is_first);
 
        void adjust(u_integer increment, bool is_first);
 
    public:
        class Iterator final : public baseIterator<TYPE> {
            mutable integer cur_pos; 
            mutable integer cur_block; 
            mutable TYPE** data_; 
            const blocksList* container_; 
 
            explicit Iterator(integer pos, integer block, TYPE** data_ptr, const blocksList* container);
 
            bool equalPtr(const iterator<TYPE>* other) const override;
 
        public:
            friend blocksList;
 
            Iterator(const Iterator& other);
 
            Iterator& operator=(const Iterator& other);
 
            Iterator* clone() const override;
 
            [[nodiscard]] bool hasNext() const override;
 
            [[nodiscard]] bool hasPrev() const override;
 
            void next() const override;
 
            void prev() const override;
 
            void operator+=(integer steps) const override;
 
            void operator-=(integer steps) const override;
 
            integer operator-(const iterator<TYPE>& other) const override;
 
            Iterator* getPrev() const override;
 
            Iterator* getNext() const override;
 
            TYPE& get() override;
 
            TYPE get() const override;
 
            void set(const TYPE& data) override;
 
            [[nodiscard]] bool isValid() const override;
 
            bool atPrev(const iterator<TYPE>* other) const override;
 
            bool atNext(const iterator<TYPE>* other) const override;
 
            [[nodiscard]] std::string className() const override;
        };
 
        friend Iterator;
 
        explicit blocksList(ALLOC alloc = ALLOC{});
 
        blocksList(const std::initializer_list<TYPE>& lst);
 
        explicit blocksList(const array<TYPE>& arr);
 
        blocksList(const blocksList& other);
 
        blocksList& operator=(const blocksList& other);
 
        blocksList(blocksList&& other) noexcept;
 
        blocksList& operator=(blocksList&& other) noexcept;
 
        void swap(blocksList& other) noexcept;
 
        TYPE get(integer index) const override;
 
        [[nodiscard]] u_integer size() const override;
 
        Iterator* begins() const override;
 
        Iterator* ends() const override;
 
        TYPE& operator[](integer index) override;
 
        void set(integer index, const TYPE& e) override;
 
        u_integer indexOf(const TYPE& e) const override;
 
        void push(integer index, const TYPE& e) override;
 
        TYPE pop(integer index) override;
 
        void pushBegin(const TYPE& e) override;
 
        TYPE popBegin() override;
 
        void pushEnd(const TYPE& e) override;
 
        TYPE popEnd() override;
 
        [[nodiscard]] std::string className() const override;
 
        ~blocksList() override;
    };
}// namespace original
 
namespace std {
    template<typename TYPE, typename ALLOC>
    void swap(original::blocksList<TYPE, ALLOC>& lhs, original::blocksList<TYPE, ALLOC>& rhs) noexcept; // NOLINT
}
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::blocksListInit() -> void
    {
        this->map = vector({this->blockArrayInit()});
        this->size_ = 0;
        this->first_ = POS_INIT + 1;
        this->last_ = POS_INIT;
        this->first_block = this->map.size() / 2;
        this->last_block = this->map.size() / 2;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::blocksListDestroy() noexcept -> void
    {
        for (auto* block : this->map) {
            for (u_integer i = 0; i < BLOCK_MAX_SIZE; ++i) {
                this->destroy(&block[i]);
            }
            this->deallocate(block, BLOCK_MAX_SIZE);
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::blockArrayInit() -> TYPE* {
        auto arr = this->allocate(BLOCK_MAX_SIZE);
        for (u_integer i = 0; i < BLOCK_MAX_SIZE; i++) {
            this->construct(&arr[i]);
        }
        return arr;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::innerIdxToAbsIdx(const u_integer block, const u_integer pos) -> u_integer
    {
        return block * BLOCK_MAX_SIZE + pos;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::firstAbsIdx() const -> u_integer
    {
        return innerIdxToAbsIdx(this->first_block, this->first_);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::lastAbsIdx() const -> u_integer
    {
        return innerIdxToAbsIdx(this->last_block, this->last_);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::absIdxToOuterIdx(const u_integer absIdx) const -> integer
    {
        return absIdx - this->firstAbsIdx();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::outerIdxToAbsIdx(const integer outerIdx) const -> u_integer
    {
        return this->firstAbsIdx() + outerIdx;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::absIdxToInnerIdx(const u_integer absIdx) -> couple<u_integer, u_integer>
    {
        return {absIdx / BLOCK_MAX_SIZE, absIdx % BLOCK_MAX_SIZE};
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::innerIdxOffset(const u_integer block, const u_integer pos,
                                                    const integer offset) -> couple<u_integer, u_integer>
    {
        return absIdxToInnerIdx(static_cast<u_integer>(static_cast<integer>(innerIdxToAbsIdx(block, pos)) + offset));
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::outerIdxToInnerIdx(const integer outerIdx) const -> couple<u_integer, u_integer>
    {
        return absIdxToInnerIdx(this->outerIdxToAbsIdx(outerIdx));
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::innerIdxToOuterIdx(const u_integer block, const u_integer pos) const -> integer
    {
        return this->absIdxToOuterIdx(innerIdxToAbsIdx(block, pos));
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::getElem(u_integer block, u_integer pos) const -> TYPE&
    {
        return this->map.get(block)[pos];
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::setElem(u_integer block, u_integer pos, const TYPE& e) -> void
    {
        this->map.get(block)[pos] = e;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::growNeeded(const u_integer increment, bool is_first) const -> bool
    {
        return is_first ? firstAbsIdx() < increment
        : lastAbsIdx() + increment > innerIdxToAbsIdx(this->map.size() - 1, BLOCK_MAX_SIZE - 1);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::moveElements(const u_integer start_block, const u_integer start_pos,
                                                  const u_integer len, const integer offset) -> void
    {
        if (offset > 0)
        {
            for (u_integer i = 0; i < len; i++)
            {
                auto idx = innerIdxOffset(start_block, start_pos, len - 1 - i);
                auto idx_offset = innerIdxOffset(start_block, start_pos, len - 1 - i + offset);
                this->setElem(idx_offset.first(), idx_offset.second(),
                              this->getElem(idx.first(), idx.second()));
            }
        }else
        {
            for (u_integer i = 0; i < len; i++)
            {
                auto idx = innerIdxOffset(start_block, start_pos, i);
                auto idx_offset = innerIdxOffset(start_block, start_pos, i + offset);
                this->setElem(idx_offset.first(), idx_offset.second(),
                              this->getElem(idx.first(), idx.second()));
            }
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::addBlock(bool is_first) -> void
    {
        auto* new_block = this->blockArrayInit();
        is_first ? this->map.pushBegin(new_block) : this->map.pushEnd(new_block);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::adjust(const u_integer increment, const bool is_first) -> void
    {
        if (this->growNeeded(increment, is_first)){
            u_integer new_blocks_cnt = increment / BLOCK_MAX_SIZE + 1;
            for (u_integer i = 0; i < new_blocks_cnt; ++i) {
                this->addBlock(is_first);
            }
            if (is_first){
                this->first_block += new_blocks_cnt;
                this->last_block += new_blocks_cnt;
            }
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>::Iterator::Iterator(const integer pos, const integer block, TYPE** data_ptr, const blocksList* container)
        : cur_pos(pos), cur_block(block), data_(data_ptr), container_(container) {}
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::equalPtr(const iterator<TYPE>* other) const -> bool
    {
        auto* other_it = dynamic_cast<const Iterator*>(other);
        return other_it != nullptr
               && this->cur_pos == other_it->cur_pos
               && this->cur_block == other_it->cur_block
               && this->data_ == other_it->data_
               && this->container_ == other_it->container_;
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>::Iterator::Iterator(const Iterator& other) : Iterator(0, 0, nullptr, nullptr)
    {
        this->operator=(other);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::operator=(const Iterator& other) -> Iterator&
    {
        if (this == &other)
            return *this;
 
        this->cur_pos = other.cur_pos;
        this->cur_block = other.cur_block;
        this->data_ = other.data_;
        this->container_ = other.container_;
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::clone() const -> Iterator*
    {
        return new Iterator(*this);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::hasNext() const -> bool
    {
        return blocksList::innerIdxToAbsIdx(this->cur_block, this->cur_pos) < this->container_->lastAbsIdx();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::hasPrev() const -> bool
    {
        return blocksList::innerIdxToAbsIdx(this->cur_block, this->cur_pos) > this->container_->firstAbsIdx();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::next() const -> void
    {
        this->operator+=(1);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::prev() const -> void
    {
        this->operator-=(1);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::operator+=(const integer steps) const -> void
    {
        auto new_idx = innerIdxOffset(this->cur_block, this->cur_pos, steps);
        this->cur_block = new_idx.first();
        this->cur_pos = new_idx.second();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::operator-=(const integer steps) const -> void
    {
        auto new_idx = innerIdxOffset(this->cur_block, this->cur_pos, -steps);
        this->cur_block = new_idx.first();
        this->cur_pos = new_idx.second();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::operator-(const iterator<TYPE>& 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 static_cast<integer>(innerIdxToAbsIdx(this->cur_block, this->cur_pos)) -
               static_cast<integer>(innerIdxToAbsIdx(other_it->cur_block, other_it->cur_pos));
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::getPrev() const -> Iterator*
    {
        if (!this->isValid()) throw outOfBoundError();
        auto* it = this->clone();
        it->prev();
        return it;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::getNext() const -> Iterator*
    {
        if (!this->isValid()) throw outOfBoundError();
        auto* it = this->clone();
        it->next();
        return it;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::get() -> TYPE&
    {
        if (!this->isValid()) throw outOfBoundError();
        return this->data_[this->cur_block][this->cur_pos];
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::get() const -> TYPE
    {
        if (!this->isValid()) throw outOfBoundError();
        return this->data_[this->cur_block][this->cur_pos];
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::set(const TYPE& data) -> void
    {
        if (!this->isValid()) throw outOfBoundError();
        this->data_[this->cur_block][this->cur_pos] = data;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::isValid() const -> bool
    {
        return this->container_->innerIdxToOuterIdx(this->cur_block, this->cur_pos) >= 0 &&
               this->container_->innerIdxToOuterIdx(this->cur_block, this->cur_pos) < this->container_->size();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::atPrev(const iterator<TYPE>* 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 TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::atNext(const iterator<TYPE>* 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 TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::Iterator::className() const -> std::string {
        return "blocksList::Iterator";
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>::blocksList(ALLOC alloc)
        : baseList<TYPE, ALLOC>(std::move(alloc)), map(), size_(), first_(), last_(), first_block(), last_block()
    {
        this->blocksListInit();
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>::blocksList(const std::initializer_list<TYPE>& lst) : blocksList() {
        this->adjust(lst.size(), false);
        for (const auto& e : lst) {
            auto new_idx = innerIdxOffset(this->last_block, this->last_, 1);
            this->last_block = new_idx.first();
            this->last_ = new_idx.second();
            this->setElem(this->last_block, this->last_, e);
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>::blocksList(const array<TYPE>& arr) : blocksList() {
        this->adjust(arr.size(), false);
        for (const auto& e : arr) {
            auto new_idx = innerIdxOffset(this->last_block, this->last_, 1);
            this->last_block = new_idx.first();
            this->last_ = new_idx.second();
            this->setElem(this->last_block, this->last_, e);
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>::blocksList(const blocksList& other) : blocksList() {
        this->operator=(other);
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>& original::blocksList<TYPE, ALLOC>::operator=(const blocksList& other) {
        if (this == &other) return *this;
 
        this->blocksListDestroy();
        this->map = vector<TYPE*>{};
 
        for (integer i = 0; i < other.map.size(); ++i) {
            auto* block = this->blockArrayInit();
            for (u_integer j = 0; j < BLOCK_MAX_SIZE; ++j) {
                block[j] = other.getElem(i, j);
            }
            this->map.pushEnd(block);
        }
 
        this->first_ = other.first_;
        this->last_ = other.last_;
        this->size_ = other.size_;
        this->first_block = other.first_block;
        this->last_block = other.last_block;
        if constexpr (ALLOC::propagate_on_container_copy_assignment::value){
            this->allocator = other.allocator;
        }
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>::blocksList(blocksList&& other) noexcept : blocksList()
    {
        this->operator=(std::move(other));
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::operator=(blocksList&& other) noexcept -> blocksList&
    {
        if (this == &other)
            return *this;
 
        this->blocksListDestroy();
 
        this->map = std::move(other.map);
        this->first_ = other.first_;
        this->last_ = other.last_;
        this->first_block = other.first_block;
        this->last_block = other.last_block;
        this->size_ = other.size_;
        if constexpr (ALLOC::propagate_on_container_move_assignment::value){
            this->allocator = std::move(other.allocator);
        }
        other.blocksListInit();
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    void original::blocksList<TYPE, ALLOC>::swap(blocksList& other) noexcept
    {
        if (this == &other)
            return;
 
        std::swap(this->map, other.map);
        std::swap(this->size_, other.size_);
        std::swap(this->first_, other.first_);
        std::swap(this->last_, other.last_);
        std::swap(this->first_block, other.first_block);
        std::swap(this->last_block, other.last_block);
        if constexpr (ALLOC::propagate_on_container_swap::value) {
            std::swap(this->allocator, other.allocator);
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::get(integer index) const -> TYPE {
        if (this->indexOutOfBound(this->parseNegIndex(index))) throw outOfBoundError();
        index = this->parseNegIndex(index);
        auto inner_idx = this->outerIdxToInnerIdx(index);
        return this->getElem(inner_idx.first(), inner_idx.second());
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::size() const -> u_integer
    {
        return this->size_;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::begins() const -> Iterator* {
        return new Iterator(this->first_, this->first_block, &this->map.data(), this);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::ends() const -> Iterator* {
        return new Iterator(this->last_, this->last_block, &this->map.data(), this);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::operator[](integer index) -> TYPE& {
        if (this->indexOutOfBound(this->parseNegIndex(index))) throw outOfBoundError();
        index = this->parseNegIndex(index);
        auto inner_idx = this->outerIdxToInnerIdx(index);
        return this->getElem(inner_idx.first(), inner_idx.second());
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::set(integer index, const TYPE &e) -> void {
        if (this->indexOutOfBound(index)) throw outOfBoundError();
        index = this->parseNegIndex(index);
        auto inner_idx = this->outerIdxToInnerIdx(index);
        this->setElem(inner_idx.first(), inner_idx.second(), e);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::indexOf(const TYPE &e) const -> u_integer {
        for (u_integer i = 0; i < this->size(); ++i) {
            if (auto idx = this->outerIdxToInnerIdx(i);
                this->getElem(idx.first(), idx.second()) == e)
                    return i;
        }
        return this->size();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::push(integer index, const TYPE& e) -> void
    {
        if (this->parseNegIndex(index) == this->size())
        {
            this->pushEnd(e);
        } else if (this->parseNegIndex(index) == 0)
        {
            this->pushBegin(e);
        } else{
            if (this->indexOutOfBound(index))
                throw outOfBoundError();
 
            index = this->parseNegIndex(index);
            const bool is_first = index <= (this->size() - 1) / 2;
            this->adjust(1, is_first);
            if (is_first){
                this->moveElements(this->first_block, this->first_, index + 1, -1);
                auto new_idx = innerIdxOffset(this->first_block, this->first_, -1);
                this->first_block = new_idx.first();
                this->first_ = new_idx.second();
            } else{
                auto idx = outerIdxToInnerIdx(index);
                this->moveElements(idx.first(), idx.second(), this->size() - index, 1);
                auto new_idx = innerIdxOffset(this->last_block, this->last_, 1);
                this->last_block = new_idx.first();
                this->last_ = new_idx.second();
            }
            this->size_ += 1;
            auto idx = outerIdxToInnerIdx(index);
            this->setElem(idx.first(), idx.second(), e);
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::pop(integer index) -> TYPE
    {
        if (this->parseNegIndex(index) == 0)
            return this->popBegin();
        if (this->parseNegIndex(index) == this->size() - 1)
            return this->popEnd();
        if (this->indexOutOfBound(index))
            throw outOfBoundError();
 
        index = this->parseNegIndex(index);
        auto idx = outerIdxToInnerIdx(index);
        TYPE res = this->getElem(idx.first(), idx.second());
        if (index <= (this->size() - 1) / 2){
            moveElements(this->first_block, this->first_, index, 1);
            auto new_idx = innerIdxOffset(this->first_block, this->first_, 1);
            this->first_block = new_idx.first();
            this->first_ = new_idx.second();
        } else{
            auto idx_offset = innerIdxOffset(idx.first(), idx.second(), 1);
            moveElements(idx_offset.first(), idx_offset.second(), this->size() - 1 - index, -1);
            auto new_idx = innerIdxOffset(this->last_block, this->last_, -1);
            this->last_block = new_idx.first();
            this->last_ = new_idx.second();
        }
        this->size_ -= 1;
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::pushBegin(const TYPE& e) -> void
    {
        this->adjust(1, true);
        auto new_idx = innerIdxOffset(this->first_block, this->first_, -1);
        this->first_block = new_idx.first();
        this->first_ = new_idx.second();
        this->setElem(this->first_block, this->first_, e);
        this->size_ += 1;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::popBegin() -> TYPE
    {
        if (this->empty()) throw noElementError();
 
        TYPE res = this->getElem(this->first_block, this->first_);
        auto new_idx = innerIdxOffset(this->first_block, this->first_, 1);
        this->first_block = new_idx.first();
        this->first_ = new_idx.second();
        this->size_ -= 1;
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::pushEnd(const TYPE& e) -> void
    {
        this->adjust(1, false);
        auto new_idx = innerIdxOffset(this->last_block, this->last_, 1);
        this->last_block = new_idx.first();
        this->last_ = new_idx.second();
        this->setElem(this->last_block, this->last_, e);
        this->size_ += 1;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::popEnd() -> TYPE
    {
        if (this->empty()) throw noElementError();
 
        TYPE res = this->getElem(this->last_block, this->last_);
        auto new_idx = innerIdxOffset(this->last_block, this->last_, -1);
        this->last_block = new_idx.first();
        this->last_ = new_idx.second();
        this->size_ -= 1;
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::blocksList<TYPE, ALLOC>::className() const -> std::string {
        return "blocksList";
    }
 
    template <typename TYPE, typename ALLOC>
    original::blocksList<TYPE, ALLOC>::~blocksList() {
        this->blocksListDestroy();
    }
 
    template <typename TYPE, typename ALLOC>
    void std::swap(original::blocksList<TYPE, ALLOC>& lhs, original::blocksList<TYPE, ALLOC>& rhs) noexcept // NOLINT
    {
        lhs.swap(rhs);
    }
 
#endif //BLOCKSLIST_H