forwardChain.h

Go to the documentation of this file.

#ifndef FORWARDCHAIN_H
#define FORWARDCHAIN_H
 
#include "singleDirectionIterator.h"
#include "array.h"
#include "baseList.h"
 
namespace original {
 
    template <typename TYPE, typename ALLOC = allocator<TYPE>>
    class forwardChain final : public baseList<TYPE, ALLOC>, public iterationStream<TYPE, forwardChain<TYPE, ALLOC>>{
 
        class forwardChainNode final : public wrapper<TYPE>{
            public:
                friend class iterator<TYPE>;
                friend class forwardChain;
 
                explicit forwardChainNode(const TYPE& data = TYPE{}, forwardChainNode* next = nullptr);
            private:
                TYPE data_;         
                forwardChainNode* next; 
            protected:
 
                forwardChainNode(const forwardChainNode& other);
 
                forwardChainNode& operator=(const forwardChainNode& other);
 
                TYPE& getVal() override;
 
                const TYPE& getVal() const override;
 
                void setVal(TYPE data) override;
 
                forwardChainNode* getPPrev() const override;
 
                forwardChainNode* getPNext() const override;
 
                void setPNext(forwardChainNode* new_next);
 
                static void connect(forwardChainNode* prev, forwardChainNode* next);
        };
 
        using rebind_alloc_node = ALLOC::template rebind_alloc<forwardChainNode>;
 
        u_integer size_;         
        forwardChainNode* begin_; 
        rebind_alloc_node rebind_alloc{}; 
 
 
        forwardChainNode* beginNode() const;
 
        forwardChainNode* findNode(integer index) const;
 
        forwardChainNode* createNode(const TYPE& value = TYPE{}, forwardChainNode* next = nullptr);
 
        void destroyNode(forwardChainNode* node) noexcept;
 
        void chainInit();
 
        void firstAdd(forwardChainNode* node);
 
        forwardChainNode* lastDelete();
 
        void chainDestroy();
    public:
 
        class Iterator final : public singleDirectionIterator<TYPE>
        {
            explicit Iterator(forwardChainNode* ptr);
        public:
            friend forwardChain;
 
            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 forwardChain(ALLOC alloc = ALLOC{});
 
        forwardChain(const forwardChain& other);
 
        forwardChain(std::initializer_list<TYPE> list);
 
        explicit forwardChain(const array<TYPE>& arr);
 
        forwardChain& operator=(const forwardChain& other);
 
        forwardChain(forwardChain&& other) noexcept;
 
        forwardChain& operator=(forwardChain&& other) noexcept;
 
        [[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;
 
        ~forwardChain() override;
    };
}
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::forwardChainNode::forwardChainNode(const TYPE& data, forwardChainNode* next)
        : data_(data), next(next) {}
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::forwardChainNode::forwardChainNode(const forwardChainNode &other)
        : data_(other.data_), next(other.next) {}
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::forwardChainNode::operator=(
        const forwardChainNode &other) -> forwardChainNode & {
        if (this != &other) {
            data_ = other.data_;
            next = other.next;
        }
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::forwardChainNode::getVal() -> TYPE& {
        return this->data_;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::forwardChainNode::getVal() const -> const TYPE& {
        return this->data_;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::forwardChainNode::setVal(TYPE data) -> void {
        this->data_ = data;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::forwardChainNode::getPPrev() const -> forwardChainNode* {
        throw unSupportedMethodError();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::forwardChainNode::getPNext() const -> forwardChainNode* {
        return this->next;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::forwardChainNode::setPNext(forwardChainNode *new_next) -> void {
        this->next = new_next;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::forwardChainNode::connect(
        forwardChainNode *prev, forwardChainNode *next) -> void {
        if (prev != nullptr) prev->setPNext(next);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::beginNode() const -> forwardChainNode*
    {
        return this->begin_->getPNext();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::findNode(const integer index) const -> forwardChainNode* {
        if (this->size() == 0) return this->begin_;
        auto cur = this->beginNode();
        for(u_integer i = 0; i < index; i++)
        {
            cur = cur->getPNext();
        }
        return cur;
    }
 
    template<typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::createNode(const TYPE &value, forwardChainNode *next) -> forwardChainNode* {
        auto node = this->rebind_alloc.allocate(1);
        this->rebind_alloc.construct(node, value, next);
        return node;
    }
 
    template<typename TYPE, typename ALLOC>
    void original::forwardChain<TYPE, ALLOC>::destroyNode(forwardChainNode *node) noexcept {
        this->rebind_alloc.destroy(node);
        this->rebind_alloc.deallocate(node, 1);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::chainInit() -> void
    {
        auto pivot = this->createNode();
        this->size_ = 0;
        this->begin_ = pivot;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::firstAdd(forwardChainNode* node) -> void
    {
        forwardChainNode::connect(this->findNode(0), node);
        this->size_ += 1;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::lastDelete() -> forwardChainNode*
    {
        auto last = this->beginNode();
        this->destroyNode(this->begin_);
        this->chainInit();
        return last;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::chainDestroy() -> void
    {
        auto cur = this->begin_;
        while (cur)
        {
            auto next = cur->getPNext();
            this->destroyNode(cur);
            cur = next;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::Iterator::Iterator(forwardChainNode *ptr)
        : singleDirectionIterator<TYPE>(ptr) {}
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::Iterator::Iterator(const Iterator &other)
        : singleDirectionIterator<TYPE>(nullptr) {
        this->operator=(other);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::Iterator::operator=(const Iterator &other) -> Iterator & {
        if (this == &other) return *this;
        singleDirectionIterator<TYPE>::operator=(other);
        return *this;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::Iterator::clone() const -> Iterator* {
        return new Iterator(*this);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<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::forwardChain<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::forwardChain<TYPE, ALLOC>::Iterator::className() const -> std::string {
        return "forwardChain::Iterator";
    }
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::forwardChain(ALLOC alloc)
    : baseList<TYPE, ALLOC>(std::move(alloc)),
      size_(0),
      begin_(nullptr),
      rebind_alloc(std::move(rebind_alloc_node{}))
    {
        this->chainInit();
    }
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::forwardChain(const forwardChain &other) : forwardChain() {
        this->operator=(other);
    }
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::forwardChain(std::initializer_list<TYPE> list) : forwardChain() {
        for (auto e: list) {
            auto cur_node = this->createNode(e);
            if (this->size() == 0)
            {
                this->firstAdd(cur_node);
            }else
            {
                auto end = this->findNode(this->size() - 1);
                forwardChainNode::connect(end, cur_node);
                this->size_ += 1;
            }
        }
    }
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::forwardChain(const array<TYPE>& arr) : forwardChain() {
        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
            {
                auto end = this->findNode(this->size() - 1);
                forwardChainNode::connect(end, cur_node);
                this->size_ += 1;
            }
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::operator=(const forwardChain &other) -> forwardChain& {
        if (this == &other) return *this;
        this->chainDestroy();
        this->size_ = other.size_;
        if (this->size() != 0){
            auto other_ = other.begin_;
            this->begin_ = this->createNode(other_->getVal());
            auto this_ = this->begin_;
            while (other_->getPNext() != nullptr){
                other_ = other_->getPNext();
                forwardChainNode::connect(this_, this->createNode(other_->getVal()));
                this_ = this_->getPNext();
            }
        } 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::forwardChain<TYPE, ALLOC>::forwardChain(forwardChain &&other) noexcept : forwardChain() {
        this->operator=(std::move(other));
    }
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC> & original::forwardChain<TYPE, ALLOC>::operator=(forwardChain &&other) noexcept {
        if (this == &other)
            return *this;
 
        this->chainDestroy();
        this->begin_ = other.begin_;
        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::forwardChain<TYPE, ALLOC>::size() const -> u_integer
    {
        return this->size_;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::get(integer index) const -> TYPE {
        if (this->indexOutOfBound(index)){
            throw outOfBoundError();
        }
        auto cur = this->findNode(this->parseNegIndex(index));
        return cur->getVal();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::operator[](integer index) -> TYPE& {
        if (this->indexOutOfBound(index)){
            throw outOfBoundError();
        }
        auto cur = this->findNode(this->parseNegIndex(index));
        return cur->getVal();
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::set(integer index, const TYPE &e) -> void {
        if (this->indexOutOfBound(index)){
            throw outOfBoundError();
        }
        auto cur = this->findNode(this->parseNegIndex(index));
        cur->setVal(e);
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::indexOf(const TYPE &e) const -> u_integer {
        u_integer i = 0;
        for (auto 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::forwardChain<TYPE, ALLOC>::pushBegin(const TYPE &e) -> void {
        auto new_node = this->createNode(e);
        if (this->size() == 0){
            this->firstAdd(new_node);
        } else{
            auto next = this->beginNode();
            forwardChainNode::connect(this->begin_, new_node);
            forwardChainNode::connect(new_node, next);
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<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();
            }
            auto new_node = this->createNode(e);
            auto prev = this->findNode(index - 1);
            auto cur = prev->getPNext();
            forwardChainNode::connect(prev, new_node);
            forwardChainNode::connect(new_node, cur);
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::pushEnd(const TYPE &e) -> void {
        auto new_node = this->createNode(e);
        if (this->size() == 0){
            this->firstAdd(new_node);
        } else{
            auto end = this->findNode(this->size() - 1);
            forwardChainNode::connect(end, new_node);
            this->size_ += 1;
        }
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::popBegin() -> TYPE {
        TYPE res;
        if (this->size() == 0){
            throw noElementError();
        }
 
        res = this->beginNode()->getVal();
        if (this->size() == 1){
            this->destroyNode(this->lastDelete());
        } else{
            auto del = this->beginNode();
            auto new_begin = del->getPNext();
            this->destroyNode(del);
            forwardChainNode::connect(this->begin_, new_begin);
            this->size_ -= 1;
        }
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<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();
        }
        TYPE res;
        auto prev = this->findNode(index - 1);
        auto cur = prev->getPNext();
        res = cur->getVal();
        auto next = cur->getPNext();
        forwardChainNode::connect(prev, next);
        this->destroyNode(cur);
        this->size_ -= 1;
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::popEnd() -> TYPE {
        TYPE res;
        if (this->size() == 0){
            throw noElementError();
        }
        if (this->size() == 1){
            res = this->beginNode()->getVal();
            this->destroyNode(this->lastDelete());
        } else{
            auto new_end = this->findNode(this->size() - 2);
            auto end = new_end->getPNext();
            res = end->getVal();
            this->destroyNode(end);
            forwardChainNode::connect(new_end, nullptr);
            this->size_ -= 1;
        }
        return res;
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::begins() const -> Iterator* {
        return new Iterator(this->beginNode());
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::ends() const -> Iterator* {
        return new Iterator(this->findNode(this->size() - 1));
    }
 
    template <typename TYPE, typename ALLOC>
    auto original::forwardChain<TYPE, ALLOC>::className() const -> std::string {
        return "forwardChain";
    }
 
    template <typename TYPE, typename ALLOC>
    original::forwardChain<TYPE, ALLOC>::~forwardChain() {
        this->chainDestroy();
    }
 
#endif //FORWARDCHAIN_H