chain.h

Go to the documentation of this file.

#ifndef CHAIN_H
#define CHAIN_H
#pragma once
 
#include "doubleDirectionIterator.h"
#include "array.h"
#include "baseList.h"
#include "iterationStream.h"
 
namespace original {
    template <typename TYPE, typename ALLOC = allocator<TYPE>>
    class chain final : public baseList<TYPE, ALLOC>, public iterationStream<TYPE, chain<TYPE, ALLOC>>{
        class chainNode final : public wrapper<TYPE>{
            public:
                friend class iterator<TYPE>;
                friend class chain;
 
                explicit chainNode(const TYPE& data = TYPE{}, chainNode* prev = nullptr, chainNode* next = nullptr);
            private:
                TYPE data_;         
                chainNode* prev;    
                chainNode* next;    
            protected:
 
                chainNode(const chainNode& other);
 
                chainNode& operator=(const chainNode& other);
 
                TYPE& getVal() override;
 
                const TYPE& getVal() const override;
 
                void setVal(TYPE data) override;
 
                chainNode* getPPrev() const override;
 
                chainNode* getPNext() const override;
 
                void setPPrev(chainNode* new_prev);
 
                void setPNext(chainNode* new_next);
 
                static void connect(chainNode* prev, chainNode* next);
        };
 
        using rebind_alloc_node = ALLOC::template rebind_alloc<chainNode>;
 
        u_integer size_;         
        chainNode* begin_;      
        chainNode* end_;        
        rebind_alloc_node rebind_alloc{};
 
 
        chainNode* findNode(integer index) const;
 
        chainNode* createNode(const TYPE& value = TYPE{}, chainNode* prev = nullptr, chainNode* next = nullptr);
 
        void destroyNode(chainNode* node) noexcept;
 
        void chainInit();
 
        void firstAdd(chainNode* node);
 
        chainNode* lastDelete();
 
        void chainDestroy();
    public:
 
        class Iterator final : public doubleDirectionIterator<TYPE>
        {
 
            explicit Iterator(chainNode* ptr);
        public:
            friend chain;
 
            Iterator(const Iterator& other);
 
            Iterator& operator=(const Iterator& other);
 
            Iterator* clone() const override;
 
            bool atPrev(const iterator<TYPE> *other) const override;
 
            bool atNext(const iterator<TYPE> *other) const override;
 
            [[nodiscard]] std::string className() const override;
        };
 
        explicit chain(ALLOC alloc = ALLOC{});
 
        chain(const chain& other);
 
        chain(const std::initializer_list<TYPE>& list);
 
        explicit chain(const array<TYPE>& arr);
 
        chain& operator=(const chain& other);
 
        chain(chain&& other) noexcept;
 
        chain& operator=(chain&& other) noexcept;
 
        chain& operator+=(chain& other);
 
        [[nodiscard]] u_integer size() const override;
 
        TYPE get(integer index) const override;
 
        TYPE& operator[](integer index) override;
 
        void set(integer index, const TYPE &e) override;
 
        u_integer indexOf(const TYPE &e) const override;
 
        void pushBegin(const TYPE &e) override;
 
        void push(integer index, const TYPE &e) override;
 
        void pushEnd(const TYPE &e) override;
 
        TYPE popBegin() override;
 
        TYPE pop(integer index) override;
 
        TYPE popEnd() override;
 
        Iterator* begins() const override;
 
        Iterator* ends() const override;
 
        [[nodiscard]] std::string className() const override;
 
        ~chain() override;
    };
}
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::chainNode::chainNode(const TYPE& data, chainNode* prev, chainNode* next)
    : data_(data), prev(prev), next(next) {}
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::chainNode::chainNode(const chainNode& other)
            : data_(other.data_), prev(other.prev), next(other.next) {}
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::operator=(const chainNode& other) -> chainNode& {
        if (this != &other) {
            data_ = other.data_;
            prev = other.prev;
            next = other.next;
        }
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::getVal() -> TYPE&
    {
        return this->data_;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::getVal() const -> const TYPE&
    {
        return this->data_;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::setVal(TYPE data) -> void
    {
        this->data_ = data;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::getPPrev() const -> chainNode* {
        return this->prev;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::getPNext() const -> chainNode* {
        return this->next;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::setPPrev(chainNode* new_prev) -> void {
        this->prev = new_prev;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::setPNext(chainNode* new_next) -> void {
        this->next = new_next;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainNode::connect(chainNode* prev, chainNode* next) -> void
    {
        if (prev != nullptr) prev->setPNext(next);
        if (next != nullptr) next->setPPrev(prev);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::findNode(integer index) const -> chainNode* {
        const bool reverse_visit = index <= this->size() / 2 ? 0 : 1;
        chainNode* cur;
        if (!reverse_visit){
            cur = this->begin_;
            for(u_integer i = 0; i < index; i++)
            {
                cur = cur->getPNext();
            }
        } else{
            cur = this->end_;
            for(u_integer i = this->size() - 1; i > index; i -= 1)
            {
                cur = cur->getPPrev();
            }
        }
        return cur;
    }
 
    template<typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::createNode(const TYPE &value, chainNode* prev, chainNode* next) -> chainNode* {
        auto node = this->rebind_alloc.allocate(1);
        this->rebind_alloc.construct(node, value, prev, next);
        return node;
    }
 
    template<typename TYPE, typename ALLOC>
    void original::chain<TYPE, ALLOC>::destroyNode(chainNode *node) noexcept {
        this->rebind_alloc.destroy(node);
        this->rebind_alloc.deallocate(node, 1);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainInit() -> void
    {
        auto pivot = this->createNode();
        this->size_ = 0;
        this->begin_ = pivot->getPNext();
        this->end_ = pivot;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::firstAdd(chainNode* node) -> void
    {
        chainNode::connect(this->end_, node);
        this->begin_ = node;
        this->end_ = node;
        this->size_ += 1;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::lastDelete() -> chainNode*
    {
        auto last = this->end_;
        this->destroyNode(last->getPPrev());
        chainNode::connect(nullptr, last);
        this->chainInit();
        return last;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::chainDestroy() -> void
    {
        auto current = this->end_;
        while (current) {
            auto prev = current->getPPrev();
            this->destroyNode(current);
            current = prev;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::Iterator::Iterator(chainNode* ptr)
        : doubleDirectionIterator<TYPE>::doubleDirectionIterator(ptr) {}
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::Iterator::Iterator(const Iterator& other)
        : doubleDirectionIterator<TYPE>::doubleDirectionIterator(nullptr) {
        this->operator=(other);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::Iterator::operator=(const Iterator& other) -> Iterator& {
        if (this == &other) return *this;
        doubleDirectionIterator<TYPE>::operator=(other);
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::Iterator::clone() const -> Iterator* {
        return new Iterator(*this);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::Iterator::atPrev(const iterator<TYPE> *other) const -> bool {
        auto other_it = dynamic_cast<const Iterator*>(other);
        return other_it != nullptr && this->_ptr->getPNext() == other_it->_ptr;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::Iterator::atNext(const iterator<TYPE> *other) const -> bool {
        auto other_it = dynamic_cast<const Iterator*>(other);
        return other_it != nullptr && other_it->_ptr->getPNext() == this->_ptr;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::Iterator::className() const -> std::string {
        return "chain::Iterator";
    }
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::chain(ALLOC alloc) : baseList<TYPE, ALLOC>(std::move(alloc)), size_(0), rebind_alloc(std::move(rebind_alloc_node{}))
    {
        chainInit();
    }
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::chain(const chain& other) : chain(){
        this->operator=(other);
    }
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::chain(const std::initializer_list<TYPE>& list)
        : chain() {
        for (const auto& e : list) {
            auto cur_node = this->createNode(e);
            if (this->size() == 0)
            {
                this->firstAdd(cur_node);
            }else
            {
                chainNode::connect(this->end_, cur_node);
                this->end_ = cur_node;
                size_ += 1;
            }
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::chain(const array<TYPE>& arr)
        : chain() {
        for (u_integer i = 0; i < arr.size(); i++) {
            auto cur_node = this->createNode(arr.get(i));
            if (this->size() == 0)
            {
                this->firstAdd(cur_node);
            }else
            {
                chainNode::connect(this->end_, cur_node);
                this->end_ = cur_node;
                size_ += 1;
            }
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>& original::chain<TYPE, ALLOC>::operator=(const chain& other){
        if (this == &other) return *this;
        this->chainDestroy();
        this->size_ = other.size_;
        if (this->size() != 0){
            auto other_ = other.begin_->getPPrev();
            auto pivot = this->createNode(other_->getVal());
            other_ = other_->getPNext();
            chainNode::connect(pivot, this->createNode(other_->getVal()));
            this->begin_ = pivot->getPNext();
            auto this_ = this->begin_;
            while (other_ != other.end_){
                other_ = other_->getPNext();
                chainNode::connect(this_, this->createNode(other_->getVal()));
                this_ = this_->getPNext();
            }
            this->end_ = this_;
        } else{
            this->chainInit();
        }
        if constexpr (ALLOC::propagate_on_container_copy_assignment::value){
            this->allocator = other.allocator;
            this->rebind_alloc = other.rebind_alloc;
        }
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::chain(chain&& other) noexcept : chain()
    {
        this->operator=(std::move(other));
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::operator=(chain&& other) noexcept -> chain&
    {
        if (this == &other)
            return *this;
 
        this->chainDestroy();
        this->begin_ = other.begin_;
        this->end_ = other.end_;
        this->size_ = other.size_;
        if constexpr (ALLOC::propagate_on_container_move_assignment::value){
            this->allocator = std::move(other.allocator);
            this->rebind_alloc = std::move(other.rebind_alloc);
        }
        other.chainInit();
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::operator+=(chain& other) -> chain&
    {
        if (this == &other || other.empty()) return *this;
 
        this->size_ += other.size_;
        other.destroyNode(other.begin_->getPPrev());
        chainNode::connect(this->end_, other.begin_);
        this->end_ = other.end_;
        if constexpr (ALLOC::propagate_on_container_merge::value) {
            this->allocator += other.allocator;
            this->rebind_alloc += other.rebind_alloc;
        }
        other.chainInit();
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::size() const -> u_integer
    {
        return this->size_;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::className() const -> std::string
    {
        return "chain";
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::get(integer index) const -> TYPE
    {
        if (this->indexOutOfBound(index)){
            throw outOfBoundError("chain::get: Index " + printable::formatString(index) +
                                 " out of bounds for chain of size " + printable::formatString(this->size()));
        }
        chainNode* cur = this->findNode(this->parseNegIndex(index));
        return cur->getVal();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::operator[](const integer index) -> TYPE&
    {
        if (this->indexOutOfBound(index)){
            throw outOfBoundError("chain::operator[]: Index " + printable::formatString(index) +
                                 " out of bounds for chain of size " + printable::formatString(this->size()));
        }
        chainNode* cur = this->findNode(this->parseNegIndex(index));
        return cur->getVal();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::set(integer index, const TYPE &e) -> void
    {
        if (this->indexOutOfBound(index)){
            throw outOfBoundError("chain::set: Index " + printable::formatString(index) +
                                 " out of bounds for chain of size " + printable::formatString(this->size()));
        }
        auto cur = this->findNode(this->parseNegIndex(index));
        cur->setVal(e);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::indexOf(const TYPE &e) const -> u_integer {
        u_integer i = 0;
        for (chainNode* current = this->begin_; current != nullptr; current = current->getPNext()) {
            if (current->getVal() == e) {
                return i;
            }
            i += 1;
        }
        return this->size();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::pushBegin(const TYPE &e) -> void
    {
        auto new_node = this->createNode(e);
        if (this->size() == 0){
            this->firstAdd(new_node);
        } else{
            auto pivot = this->begin_->getPPrev();
            chainNode::connect(new_node, this->begin_);
            chainNode::connect(pivot, new_node);
            this->begin_ = new_node;
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::push(integer index, const TYPE &e) -> void
    {
        index = this->parseNegIndex(index);
        if (index == 0){
            this->pushBegin(e);
        } else if (index == this->size()){
            this->pushEnd(e);
        } else{
            if (this->indexOutOfBound(index)){
                throw outOfBoundError("chain::push: Index " + printable::formatString(index) +
                                     " out of bounds for chain of size " + printable::formatString(this->size()));
            }
            auto new_node = this->createNode(e);
            auto cur = this->findNode(index);
            auto prev = cur->getPPrev();
            chainNode::connect(prev, new_node);
            chainNode::connect(new_node, cur);
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::pushEnd(const TYPE &e) -> void
    {
        auto new_node = this->createNode(e);
        if (this->size() == 0){
            this->firstAdd(new_node);
        } else{
            chainNode::connect(this->end_, new_node);
            this->end_ = new_node;
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::popBegin() -> TYPE
    {
        TYPE res;
        if (this->size() == 0){
            throw noElementError("chain::popBegin: Cannot pop from empty chain");
        }
        if (this->size() == 1){
            auto del = this->lastDelete();
            res = del->getVal();
            this->destroyNode(del);
        } else{
            res = this->begin_->getVal();
            auto new_begin = this->begin_->getPNext();
            auto pivot = this->begin_->getPPrev();
            this->destroyNode(this->begin_);
            this->begin_ = new_begin;
            chainNode::connect(pivot, this->begin_);
            this->size_ -= 1;
        }
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::pop(integer index) -> TYPE
    {
        index = this->parseNegIndex(index);
        if (index == 0){
            return this->popBegin();
        }
        if (index == this->size() - 1){
            return this->popEnd();
        }
        if (this->indexOutOfBound(index)){
            throw outOfBoundError("chain::pop: Index " + printable::formatString(index) +
                                 " out of bounds for chain of size " + printable::formatString(this->size()));
        }
        TYPE res;
        chainNode* cur = this->findNode(index);
        res = cur->getVal();
        auto prev = cur->getPPrev();
        auto next = cur->getPNext();
        chainNode::connect(prev, next);
        this->destroyNode(cur);
        this->size_ -= 1;
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::popEnd() -> TYPE
    {
        TYPE res;
        if (this->size() == 0){
            throw noElementError("chain::popEnd: Cannot pop from empty chain");
        }
        if (this->size() == 1){
            auto del = this->lastDelete();
            res = del->getVal();
            this->destroyNode(del);
        } else{
            res = this->end_->getVal();
            auto new_end = this->end_->getPPrev();
            this->destroyNode(this->end_);
            this->end_ = new_end;
            chainNode::connect(this->end_, nullptr);
            this->size_ -= 1;
        }
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::begins() const -> Iterator* {
        return new Iterator(this->begin_);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::chain<TYPE, ALLOC>::ends() const -> Iterator* {
        return new Iterator(this->end_);
    }
 
    template <typename TYPE, typename ALLOC>
    original::chain<TYPE, ALLOC>::~chain() {
        this->chainDestroy();
    }
 
#endif //CHAIN_H