Обход бинарного дерева в ширину

#pragma once
#include "simple_binary_tree_node.h"
#include <vector>
 
template <typename KeyType, typename MappedType>
class simple_binary_tree
{
    using ValueType               = std::pair<KeyType, MappedType>;
    //using simple_binary_tree      = simple_binary_tree<KeyType, MappedType>;
    using simple_binary_tree_node = simple_binary_tree_node<KeyType, MappedType>;
 
 
    template <typename ItType>
    class basic_iterator
    {
        template <typename OtherItType>
        friend class basic_iterator;
        friend class simple_binary_tree;
 
    public:
        ValueType& operator*()
        {
            return this->m_pCurrentNode->m_Value;
        }
 
        ValueType* operator ->()
        {
            return &this->m_pCurrentNode->m_Value;
        }
 
        bool empty()
        {
            return !this->m_pCurrentNode;
        }
 
        ItType operator +(int otherStep) const
        {
            ItType tempIt = self();
            if (otherStep < 0)
            {
                return tempIt - (otherStep * (-1));
            }
            else
            {
                for (size_t i = 0; i < otherStep; i++)
                {
                    tempIt++;
                }
                return tempIt;
            }
        }
 
        ItType operator - (int otherStep) const
        {
            ItType tempIt = self();
            if (otherStep < 0)
            {
                return tempIt + (otherStep * (-1));
            }
            else
            {
                for (size_t i = 0; i < otherStep; i++)
                {
                    tempIt--;
                }
                return tempIt;
            }
        }
 
        basic_iterator& operator += (int otherStep)
        {
            *this = *this + otherStep;
            return *this;
        }
 
        basic_iterator& operator -= (int otherStep)
        {
            *this = *this - otherStep;
            return *this;
        }
 
        friend bool operator == (const ItType& leftIterator, const ItType& rightIterator)
        {
            return (leftIterator.m_pCurrentNode == rightIterator.m_pCurrentNode);
        }
 
        friend bool operator != (const ItType& leftIterator, const ItType& rightIterator)
        {
            return (leftIterator.m_pCurrentNode != rightIterator.m_pCurrentNode);
        }
 
 
    protected:
 
        bool is_end(simple_binary_tree_node* otherpNode)
        {
            simple_binary_tree_node* tempNode = otherpNode;
            while (!tempNode->pParent->m_isNil)
            {
                if (tempNode == tempNode->pParent->pLeft)
                {
                    return false;
                }
                tempNode = tempNode->pParent;
            }
            return true;
        }
 
        bool is_begin(simple_binary_tree_node* otherpNode)
        {
            simple_binary_tree_node* tempNode = otherpNode;
            while (!tempNode->pParent->m_isNil)
            {
                if (tempNode == tempNode->pParent->pRight)
                {
                    return false;
                }
                tempNode = tempNode->pParent;
            }
            return true;
        }
 
        ItType& self()
        {
            return static_cast<ItType&>(*this);
        }
 
        const ItType& self() const
        {
            return static_cast<const ItType&>(*this);
        }
 
        basic_iterator()
        {
            this->m_pCurrentNode = nullptr;
        }
 
        basic_iterator(simple_binary_tree_node* otherpValue)
        {
            this->m_pCurrentNode = otherpValue;
        }
 
        template <typename OtherItType>
        basic_iterator(const basic_iterator<OtherItType>& otherBase)
        {
            this->m_pCurrentNode = otherBase.m_pCurrentNode;
        }
 
        simple_binary_tree_node* m_pCurrentNode;
    };
 
public:
 
    class in_order_iterator : public basic_iterator<in_order_iterator>
    {
        friend class simple_binary_tree;
    private:
 
        in_order_iterator(simple_binary_tree_node* otherpNode) : basic_iterator<in_order_iterator>(otherpNode)
        {
        }
 
    public:
 
        in_order_iterator() : basic_iterator<in_order_iterator>()
        {
        }
 
        template <typename OtherItType>
        in_order_iterator(const basic_iterator<OtherItType>& otherBase) : basic_iterator<in_order_iterator>(otherBase)
        {
        }
 
        in_order_iterator& operator ++()
        {
            if (this->m_pCurrentNode->pRight && !this->m_pCurrentNode->pRight->m_isNil)
            {
                this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                while (!this->m_pCurrentNode->pLeft->m_isNil)
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pLeft;
                }
            }
            else
            {
                if (this->m_pCurrentNode->pRight && this->m_pCurrentNode->pRight->m_isNil && this->is_end(this->m_pCurrentNode))
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                }
                else
                {
                    while (this->m_pCurrentNode->pParent->pRight == this->m_pCurrentNode)
                    {
                        this->m_pCurrentNode = this->m_pCurrentNode->pParent;
                    }
                    this->m_pCurrentNode = this->m_pCurrentNode->pParent;
                }
            }
            return *this;
        }
 
        in_order_iterator operator ++(int)
        {
            in_order_iterator temp(*this);
            ++(*this);
            return temp;
        }
 
        in_order_iterator& operator --()
        {
            if (this->m_pCurrentNode->pLeft && !this->m_pCurrentNode->pLeft->m_isNil)
            {
                this->m_pCurrentNode = this->m_pCurrentNode->pLeft;
                while (!this->m_pCurrentNode->pRight->m_isNil)
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                }
            }
            else
            {
                if (this->m_pCurrentNode->pLeft && this->m_pCurrentNode->pLeft->m_isNil && this->is_begin(this->m_pCurrentNode))
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                }
                while (this->m_pCurrentNode->pParent->pLeft == this->m_pCurrentNode)
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pParent;
                } 
                this->m_pCurrentNode = this->m_pCurrentNode->pParent;
            }
            return *this;
        }
 
        in_order_iterator operator --(int)
        {
            in_order_iterator temp(*this);
            --(*this);
            return temp;
        }
 
    private:
    };
    class in_order_reverse_iterator : public basic_iterator<in_order_reverse_iterator>
    {
        friend class simple_binary_tree;
    private:
 
        in_order_reverse_iterator(simple_binary_tree_node* otherpNode) : basic_iterator<in_order_reverse_iterator>(otherpNode)
        {
        }
 
    public:
        in_order_reverse_iterator() : basic_iterator<in_order_reverse_iterator>()
        {
        }
 
        template <typename OtherItType>
        in_order_reverse_iterator(const basic_iterator<OtherItType>& otherBase) : basic_iterator<in_order_reverse_iterator>(otherBase)
        {
        }
 
        in_order_reverse_iterator& operator ++()
        {
            if (this->m_pCurrentNode->pLeft && !this->m_pCurrentNode->pLeft->m_isNil)
            {
                this->m_pCurrentNode = this->m_pCurrentNode->pLeft;
                while (!this->m_pCurrentNode->pRight->m_isNil)
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                }
            }
            else
            {
                if (this->m_pCurrentNode->pLeft && this->m_pCurrentNode->pLeft->m_isNil && this->is_begin(this->m_pCurrentNode))
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                }
                while (this->m_pCurrentNode->pParent->pLeft == this->m_pCurrentNode)
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pParent;
                }
                this->m_pCurrentNode = this->m_pCurrentNode->pParent;
            }
            return *this;
        }
 
        in_order_reverse_iterator operator ++(int)
        {
            in_order_reverse_iterator temp(*this);
            ++(*this);
            return temp;
        }
 
        in_order_reverse_iterator& operator --()
        {
            if (this->m_pCurrentNode->pRight && !this->m_pCurrentNode->pRight->m_isNil)
            {
                this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                while (!this->m_pCurrentNode->pLeft->m_isNil)
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pLeft;
                }
            }
            else
            {
                if (this->m_pCurrentNode->pRight && this->m_pCurrentNode->pRight->m_isNil && this->is_end(this->m_pCurrentNode))
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                }
                else
                {
                    while (this->m_pCurrentNode->pParent->pRight == this->m_pCurrentNode)
                    {
                        this->m_pCurrentNode = this->m_pCurrentNode->pParent;
                    }
                    this->m_pCurrentNode = this->m_pCurrentNode->pParent;
                }
            }
            return *this;
        }
 
        in_order_reverse_iterator operator --(int)
        {
            in_order_reverse_iterator temp(*this);
            --(*this);
            return temp;
        }
 
    private:
    };
    
    class in_wigth_iterator : public basic_iterator<in_wigth_iterator>
    {
        friend class simple_binary_tree;
    private:
 
        simple_binary_tree_node* next_node(simple_binary_tree_node* currentNode)
        {
            if (currentNode->pRight && currentNode->pRight->m_isNil && this->is_end(currentNode))
            {
                simple_binary_tree_node* temp = currentNode;
                while (!temp->pParent->m_isNil)
                {
                    temp = temp->pParent;
                }
                return currentNode->pRight;
            }
            else
            {
                std::vector<bool> node_pos;
                simple_binary_tree_node* temp = currentNode;
                while (!temp->pParent->m_isNil)
                {
                    node_pos.insert(node_pos.begin(), (temp == temp->pParent->pRight));
                    temp = temp->pParent;
                }
                simple_binary_tree_node* temp_ = temp;
 
                bool flag = true;
                while (flag)
                {
                    int count = 0;
                    for (size_t i = 0; i < node_pos.size(); i++)
                    {
                        if (!node_pos[i])
                        {
                            count++;
                        }
                    }
                    if (!count)
                    {
                        std::vector<bool> newPos(node_pos.size() + 1, 0);
                        node_pos = newPos;
                    }
                    else
                    {
                        for (auto i = 0; i < node_pos.size(); i++)
                        {
                            count = 0;
                            for (auto j = (i + 1); j < node_pos.size(); j++)
                            {
                                if (!node_pos[j])
                                {
                                    count++;
                                }
                            }
                            if (!count)
                            {
                                if (!node_pos[i])
                                {
                                    for (auto k = i; k < node_pos.size(); k++)
                                    {
                                        node_pos[k] = !node_pos[k];
                                    }
                                }
                                break;
                            }
                            else
                            {
                                continue;
                            }
                        }
                    }
                    flag = false;
                    for (size_t i = 0; i < node_pos.size(); i++)
                    {
                        if (node_pos[i])
                        {
                            if (temp && temp->pRight && temp->pRight->m_isNil)
                            {
                                flag = true;
                                temp = temp_;
                                break;
                            }
                            else
                            {
                                temp = temp->pRight;
                            }
                        }
                        else
                        {
                            if (temp && temp->pLeft && temp->pLeft->m_isNil)
                            {
                                flag = true;
                                temp = temp_;
                                break;
                            }
                            else
                            {
                                temp = temp->pLeft;
                            }
                        }
                    }
                    return temp;
                }
            }
        }
 
        in_wigth_iterator(simple_binary_tree_node* otherpNode) : basic_iterator<in_wigth_iterator>(otherpNode)
        {
        }
 
    public:
 
        in_wigth_iterator() : basic_iterator<in_wigth_iterator>()
        {
        }
 
        template <typename OtherItType>
        in_wigth_iterator(const basic_iterator<OtherItType>& otherBase) : basic_iterator<in_wigth_iterator>(otherBase)
        {
        }
 
        in_wigth_iterator& operator ++()
        {
            this->m_pCurrentNode = next_node(this->m_pCurrentNode);
            return *this;
        }
 
        in_wigth_iterator operator ++(int)
        {
            in_wigth_iterator temp(*this);
            ++(*this);
            return temp;
        }
 
        in_wigth_iterator& operator --()
        {
            if (this->m_pCurrentNode->pLeft && !this->m_pCurrentNode->pLeft->m_isNil)
            {
                this->m_pCurrentNode = this->m_pCurrentNode->pLeft;
                while (!this->m_pCurrentNode->pRight->m_isNil)
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                }
            }
            else
            {
                if (this->m_pCurrentNode->pLeft && this->m_pCurrentNode->pLeft->m_isNil && this->is_begin(this->m_pCurrentNode))
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pRight;
                }
                while (this->m_pCurrentNode->pParent->pLeft == this->m_pCurrentNode)
                {
                    this->m_pCurrentNode = this->m_pCurrentNode->pParent;
                }
                this->m_pCurrentNode = this->m_pCurrentNode->pParent;
            }
            return *this;
        }
 
        in_wigth_iterator operator --(int)
        {
            in_wigth_iterator temp(*this);
            --(*this);
            return temp;
        }
 
    private:
    };
 
    simple_binary_tree();
 
    ~simple_binary_tree();
 
    std::pair<in_order_iterator, bool> insert(const ValueType& otherValue)
    {
        return this->emplace(otherValue);
    }
 
    std::pair<in_order_iterator, bool> insert(ValueType&& otherValue)
    {
        return this->emplace(std::move(otherValue));
    }
    
    template< class InputIt >
    void insert(const InputIt& otherFirstIterator, const InputIt& otherLastIterator)
    {
        auto tempIt = otherFirstIterator;
        while (tempIt != otherLastIterator)
        {
            this->insert(*tempIt);
            tempIt++;
        }
    }
 
    void insert(std::initializer_list<ValueType> otherIList)
    {
        this->insert(otherIList.begin(), otherIList.end());
    }
 
    template< class... Args >
    std::pair<in_order_iterator, bool> emplace(Args&&... args)
    {
        simple_binary_tree_node* newNode = this->m_pRoot;
        for (const auto& value : { args... })
        {
            newNode = simple_binary_tree_node::get_allocated_new_node(value);
            simple_binary_tree_node* currentNode = this->m_pRoot->pRight;
 
            while (!currentNode->m_isNil)
            {
                if (newNode->m_Value.first < currentNode->m_Value.first)
                {
                    currentNode = currentNode->pLeft;
                }
                else if (newNode->m_Value.first > currentNode->m_Value.first)
                {
                    currentNode = currentNode->pRight;
                }
                else if (newNode->m_Value.first == currentNode->m_Value.first)
                {
                    delete newNode;
                    return { currentNode , false };;
                }
                else
                {
                    delete newNode;
                    return { currentNode , false };
                }
            }
 
            if (currentNode->pParent->pRight == currentNode)
            {
                currentNode->pParent->pRight = newNode;
                if (this->m_pMaxNode == currentNode->pParent || this->m_pMaxNode == currentNode)
                {
                    this->m_pMaxNode = newNode;
                }
                if (this->m_pMinNode == currentNode)
                {
                    this->m_pMinNode = newNode;
                }
            }
            else
            {
                currentNode->pParent->pLeft = newNode;
                if (this->m_pMinNode == currentNode->pParent || this->m_pMinNode == currentNode)
                {
                    this->m_pMinNode = newNode;
                }
                if (this->m_pMaxNode == currentNode)
                {
                    this->m_pMaxNode = newNode;
                }
            }
 
 
            newNode->pParent = currentNode->pParent;
            delete currentNode;
            this->m_iSize++;
        }
        return { in_order_iterator(newNode), true };
    }
 
    bool delete_by_key(KeyType otherKey);
 
    void clear();
 
    bool empty();
 
    int size();
 
    in_order_iterator begin()
    {
        return in_order_iterator(this->m_pMinNode);
    }
 
    in_order_iterator end()
    {
        return in_order_iterator(this->m_pMaxNode->pRight);
    }
 
    in_order_reverse_iterator rbegin()
    {
        return in_order_reverse_iterator(this->m_pMaxNode);
    }
 
    in_order_reverse_iterator rend()
    {
        return in_order_reverse_iterator(this->m_pMinNode->pLeft);
    }
 
    in_wigth_iterator iwbegin()
    {
        return in_wigth_iterator(this->m_pRoot->pRight);
    }
 
    in_wigth_iterator iwend()
    {
        return in_wigth_iterator(this->m_pMaxNode->pRight);
    }
 
private:
 
    simple_binary_tree_node* findNode(KeyType otherKey)
    {
        simple_binary_tree_node* currentNode = this->m_pRoot->pRight;
        while (!currentNode->m_isNil)
        {
            if (otherKey < currentNode->m_Value.second)
            {
                currentNode = currentNode->pLeft;
            }
            else if (otherKey > currentNode->m_Value.second)
            {
                currentNode = currentNode->pRight;
            }
            else if (otherKey == currentNode->m_Value.second)
            {
                break;
            }
            else
            {
                return this->m_pRoot;
            }
        }
        return currentNode;
    }
 
    bool deleteNode(simple_binary_tree_node* toDeleteNode)
    {
        if (toDeleteNode->m_isNil)
        {
            return false;
        }
        else
        {
            simple_binary_tree_node* deputyNode = toDeleteNode->pRight;
            if (this->m_pMaxNode == toDeleteNode)
            {
                if (toDeleteNode->pParent->m_isNil) this->m_pMaxNode = deputyNode;
                else this->m_pMaxNode = toDeleteNode->pParent;
            }
            if (this->m_pMinNode == toDeleteNode)
            {
                if (toDeleteNode->pParent->m_isNil) this->m_pMinNode = deputyNode;
                else this->m_pMinNode = toDeleteNode->pParent;
            }
            if (deputyNode->m_isNil)
            {
                delete deputyNode;
                deputyNode = toDeleteNode->pLeft;
 
                if (toDeleteNode->pParent->pLeft == toDeleteNode) toDeleteNode->pParent->pLeft = deputyNode;
                else toDeleteNode->pParent->pRight = deputyNode;
                deputyNode->pParent = toDeleteNode->pParent;
 
                delete toDeleteNode;
            }
            else
            {
                while (!deputyNode->pLeft->m_isNil)
                {
                    deputyNode = deputyNode->pLeft;
                }
                if (deputyNode->pRight->m_isNil)
                {
                    delete deputyNode->pRight;
                    deputyNode->pLeft->pParent = deputyNode->pParent;
                    if (deputyNode->pParent->pLeft == deputyNode) deputyNode->pParent->pLeft = deputyNode->pLeft;
                    else deputyNode->pParent->pRight = deputyNode->pLeft;
                }
                else
                {
                    delete deputyNode->pLeft;
                    deputyNode->pRight->pParent = deputyNode->pParent;
                    if (deputyNode->pParent->pLeft == deputyNode) deputyNode->pParent->pLeft = deputyNode->pRight;
                    else deputyNode->pParent->pRight = deputyNode->pRight;
                }
                deputyNode->pParent = toDeleteNode->pParent;
                deputyNode->pLeft = toDeleteNode->pLeft;
                deputyNode->pRight = toDeleteNode->pRight;
 
                if (toDeleteNode->pParent->pLeft == toDeleteNode) toDeleteNode->pParent->pLeft = deputyNode;
                else toDeleteNode->pParent->pRight = deputyNode;
                toDeleteNode->pLeft->pParent = deputyNode;
                toDeleteNode->pRight->pParent = deputyNode;
            }
            this->m_iSize--;
            return true;
        }
    }
 
    simple_binary_tree_node* m_pRoot;
    simple_binary_tree_node* m_pMinNode;
    simple_binary_tree_node* m_pMaxNode;
    int m_iSize;
};
 
template<typename KeyType, typename ValueType>
inline simple_binary_tree<KeyType, ValueType>::simple_binary_tree()
{
    this->m_iSize = 0;
    this->m_pRoot = simple_binary_tree_node::get_allocated_new_node();
    this->m_pRoot->m_isNil = true;
    this->m_pMinNode = this->m_pMaxNode = this->m_pRoot->pRight;
}
 
template<typename KeyType, typename ValueType>
inline simple_binary_tree<KeyType, ValueType>::~simple_binary_tree()
{
    this->clear();
    delete this->m_pRoot->pLeft;
    delete this->m_pRoot->pRight;
    delete this->m_pRoot;
}
 
 
 
template<typename KeyType, typename ValueType>
inline bool simple_binary_tree<KeyType, ValueType>::delete_by_key(KeyType otherKey)
{
    return this->deleteNode(this->findNode(otherKey));
}
 
template<typename KeyType, typename ValueType>
inline void simple_binary_tree<KeyType, ValueType>::clear()
{
    while (!this->m_pRoot->pRight->m_isNil)
    {
        deleteNode(this->m_pRoot->pRight);
    }
}
 
template<typename KeyType, typename MappedType>
inline bool simple_binary_tree<KeyType, MappedType>::empty()
{
    return this->m_pRoot->pRight->m_isNil;
}
 
template<typename KeyType, typename MappedType>
inline int simple_binary_tree<KeyType, MappedType>::size()
{
    return this->m_iSize;
}

#pragma once
#include <utility>
 
 
template <typename KeyType, typename MappedType>
class simple_binary_tree;
 
template <typename KeyType, typename MappedType>
class simple_binary_tree_node
{
    template <typename KeyType, typename MappedType>
    friend class simple_binary_tree;
public:
    using ValueType  = std::pair<KeyType, MappedType>;
 
private:
 
    enum isNil
    {
        NODE,
        Nil
    };
 
    simple_binary_tree_node(ValueType otherValue = ValueType(),
        simple_binary_tree_node<KeyType, MappedType>* otherpParent = nullptr,
        simple_binary_tree_node<KeyType, MappedType>* otherpLeft = nullptr,
        simple_binary_tree_node<KeyType, MappedType>* otherpRight = nullptr)
    {
        this->m_isNil = NODE;
        this->m_Value = otherValue;
        this->pParent = otherpParent;
        this->pLeft = otherpLeft;
        this->pRight = otherpRight;
    }
 
    static simple_binary_tree_node<KeyType, MappedType>* get_allocated_new_node(ValueType otherValue = ValueType())
    {
        simple_binary_tree_node<KeyType, MappedType>* newNode = new simple_binary_tree_node<KeyType, MappedType>(otherValue,
            nullptr,
            new simple_binary_tree_node<KeyType, MappedType>(),
            new simple_binary_tree_node<KeyType, MappedType>());
        newNode->pLeft->pParent = newNode;
        newNode->pRight->pParent = newNode;
        newNode->pLeft->m_isNil = true;
        newNode->pRight->m_isNil = true;
        return newNode;
    }
 
    char m_isNil;
    ValueType m_Value;
    simple_binary_tree_node* pParent;
    simple_binary_tree_node* pLeft;
    simple_binary_tree_node* pRight;
 
};