#ifndef TREECONTAINER_H
#define TREECONTAINER_H

#include <map>
#include <vector>
#include <typeinfo>
#include <typeindex>
#include <memory>


namespace treeContainer {
class tree_iterator;
class node_iterator;
class reverse_node_iterator;
class child_iterator;
class reverse_child_iterator;
typedef const node_iterator const_node_iterator;
typedef const reverse_node_iterator const_reverse_node_iterator;
typedef const child_iterator const_child_iterator;
typedef const reverse_child_iterator const_reverse_child_iterator;

class tree{
private:
    friend class tree_iterator;
    friend class node_iterator;
    friend class reverse_node_iterator;
    friend class child_iterator;
    friend class reverse_child_iterator;

    class Node;
    typedef std::shared_ptr<Node> ptrNode;

public:
    enum Parameter
    {
        APPENDNEXT,
        REMOVENEXT,

        ROOT,
        END
    };

//structors
public:
    tree();
    ~tree();

//functions
public:
    template<typename T> node_iterator find(T value);
    void clear();

    template<typename T> node_iterator appendNode(tree_iterator it, T value);

    node_iterator move(tree_iterator it, tree_iterator node);

    void remove(tree_iterator it);
    void remove(tree_iterator it, Parameter param);

private:
    template<typename T> Node* find(T value, Node* node);

//Functions iterating
public:
    //begin() & end()
    node_iterator begin();
    const_node_iterator cbegin() const;

    reverse_node_iterator rbegin();
    const_reverse_node_iterator crbegin() const;

    child_iterator begin(tree_iterator node);
    const_child_iterator cbegin(tree_iterator node) const;

    reverse_child_iterator rbegin(tree_iterator node);
    const_reverse_child_iterator crbegin(tree_iterator node) const;

    node_iterator end();
    const_node_iterator cend() const;

    reverse_node_iterator rend();
    const_reverse_node_iterator crend() const;

    child_iterator end(tree_iterator node);
    const_child_iterator cend(tree_iterator node) const;

    reverse_child_iterator rend(tree_iterator node);
    const_reverse_child_iterator crend(tree_iterator node) const;

//Classes
private:
    class Node{
        friend class tree;
    private:
            class placeholder{
            public:
                virtual ~placeholder() {}
                virtual std::type_index getType() = 0;
            };

            template<typename T>
            class holder : public placeholder{
            public:
                holder(T value) : myValue(value) {}

                std::type_index getType();

                T myValue;
            };
    private:
        std::shared_ptr<placeholder> myValue = nullptr;

        Node* myParentNode = nullptr;

        Node* myPrevNode = nullptr;
        Node* myNextNode = nullptr;

        Node* myFirstNode = nullptr;
        Node* myLastNode = nullptr;

        std::vector<std::shared_ptr<Node>> myChildren;

    private:

    public:
        Node();
        template<typename T> Node(T value);
        ~Node();

    public:
        Node* getPrev();
        Node* getNext();
        Node* getFirst();
        Node* getLast();
        Node* getParent();

        node_iterator appendNode(std::shared_ptr<Node> node);
        template<typename T> node_iterator appendNode(T value);

        void remove(Parameter param);

        template<typename T> void setValue(T value);
        template<typename T> T getValue();
        std::type_index getValueType();

        template<typename T> void operator =(T value) { setValue(value); }
    private:
        void setPrev(Node* prev);
        void setNext(Node* next);
        void setFirst(Node* first);
        void setLast(Node* last);
        void setParent(Node* parent);

        void extract();
        void erase(Node* node);
        void erase(std::shared_ptr<Node> node);
    };

//Storage
private:
    ptrNode myRoot = nullptr;
    ptrNode myEnd = nullptr;

};


//Iterators
class tree_iterator
{
private:
    friend class tree;
    friend class node_iterator;
    friend class reverse_node_iterator;
    friend class child_iterator;
    friend class reverse_child_iterator;
public:
    virtual ~tree_iterator() {}

    void operator =(tree::Node* node)
    {
        myNode = node;
    }
    void operator =(tree_iterator rhs)
    {
        myNode = rhs.myNode;
    }

    bool operator ==(tree_iterator& rhs)
    {
        return myNode == rhs.myNode;
    }
    bool operator !=(tree_iterator rhs)
    {
        return !(myNode == rhs.myNode);
    }

    void Next()
    {
        if(myNode->getNext()) myNode = myNode->getNext();
    }
    void Prev()
    {
        if(myNode->getPrev()) myNode = myNode->getPrev();
    }
    void First()
    {
        if(myNode->getFirst()) myNode = myNode->getFirst();
    }
    void Last()
    {
        if(myNode->getLast()) myNode = myNode->getLast();
    }
    void Parent()
    {
        myNode = myNode->getParent();
    }

    template<typename T> void setValue(T value)
    {
        myNode->setValue(value);
    }

    template<typename T> T getValue()
    {
        return myNode->getValue<T>();
    }

    std::type_index getValueType()
    {
        return myNode->getValueType();
    }

protected:
    void increment()
    {
        if(myNode->getFirst()) myNode = myNode->getFirst();
        else if(myNode->getNext()) myNode = myNode->getNext();
        else getNext();
    }
    void decrement()
    {
        if(myNode->getLast()) myNode = myNode->getLast();
        else if(myNode->getPrev()) myNode = myNode->getPrev();
        else getPrev();
    }
    void getNext()
    {
        if(myNode->getParent() == myNode) return; //is root?
        else
        {
            if(!myNode->getParent()->getNext())
            {
                myNode = myNode->getParent();
                getNext();
            }
            else myNode = myNode->getParent()->getNext();
        }
    }
    void getPrev()
    {
        if(myNode->getParent() == myNode) return; //is root?
        else
        {
            if(!myNode->getParent()->getPrev())
            {
                myNode = myNode->getParent();
                getPrev();
            }
            else myNode = myNode->getParent()->getPrev();
        }
    }

protected:
    tree::Node* myNode;
};

class node_iterator : public tree_iterator
{
private:
    friend class tree;
    node_iterator(tree::Node* node) { myNode = node; }

public:
    node_iterator() {}
    node_iterator(tree_iterator& it) {myNode = it.myNode; }

    ~node_iterator() {}

    node_iterator& operator ++()
    {
        increment();
        return *this;
    }
    const node_iterator operator ++(int)
    {
        node_iterator ret(myNode);
        ++(*this);
        return ret;
    }
    node_iterator& operator --()
    {
        decrement();
        return *this;
    }
    const node_iterator operator --(int)
    {
        node_iterator ret(myNode);
        --(*this);
        return ret;
    }
};
class reverse_node_iterator : public tree_iterator
{
private:
    friend class tree;
    reverse_node_iterator(tree::Node* node) { myNode = node; }
public:
    reverse_node_iterator() {}
    reverse_node_iterator(tree_iterator& it) {myNode = it.myNode; }

    ~reverse_node_iterator() {}

    reverse_node_iterator& operator ++()
    {
        decrement();
        return *this;
    }
    const reverse_node_iterator operator ++(int)
    {
        reverse_node_iterator ret(myNode);
        ++(*this);
        return ret;
    }
    reverse_node_iterator& operator --()
    {
        increment();
        return *this;
    }
    const reverse_node_iterator operator --(int)
    {
        reverse_node_iterator ret(myNode);
        --(*this);
        return ret;
    }
};
class child_iterator : public tree_iterator
{
private:
    friend class tree;
    child_iterator(tree::Node* node) { myNode = node; }
public:
    child_iterator() {}
    child_iterator(tree_iterator it) {myNode = it.myNode->getFirst(); }

    ~child_iterator() {}

    child_iterator& operator ++()
    {
        myNode = myNode->getNext();
        return *this;
    }
    const child_iterator operator ++(int)
    {
        child_iterator ret(*this);
        ++(*this);
        return ret;
    }
    child_iterator& operator --()
    {
        myNode = myNode->getPrev();
        return *this;
    }
    const child_iterator operator --(int)
    {
        child_iterator ret(*this);
        --(*this);
        return ret;
    }
};
class reverse_child_iterator : public tree_iterator
{
private:
    friend class tree;
    reverse_child_iterator(tree::Node* node) { myNode = node; }
public:
    reverse_child_iterator() {}
    reverse_child_iterator(tree_iterator& it) { myNode = it.myNode->getLast(); }

    ~reverse_child_iterator() {}

    reverse_child_iterator& operator ++()
    {
        myNode = myNode->getPrev();
        return *this;
    }
    const reverse_child_iterator operator ++(int)
    {
        reverse_child_iterator ret(*this);
        ++(*this);
        return ret;
    }
    reverse_child_iterator& operator --()
    {
        myNode = myNode->getNext();
        return *this;
    }
    const reverse_child_iterator operator --(int)
    {
        reverse_child_iterator ret(*this);
        --(*this);
        return ret;
    }
};
}


/*--------------------------------------------------------------------------------------------------------------------------------------*/

//Functions
template<typename T> treeContainer::node_iterator treeContainer::tree::find(T value)
{
    return node_iterator(find(value, myRoot.get()));
}

template<typename T> treeContainer::tree::Node* treeContainer::tree::find(T value, Node* node)
{
    Node* ret = nullptr;
    if(node->getValueType() == typeid(T) && node->getValue<T>() == value) ret = node;
    else if(node->getFirst()) ret = find(value, node->getFirst());
    if(!ret && node->getNext()) ret = find(value, node->getNext());

    return ret;
}

template<typename T> treeContainer::node_iterator treeContainer::tree::appendNode(tree_iterator it, T value)
{
    node_iterator ret = it.myNode->appendNode(std::make_shared<Node>(value));
    if(it.myNode == myRoot.get()) it.myNode->appendNode(myEnd);
    return ret;
}

/*--------------------------------------------------------------------------------------------------------------------------------------*/

//class Node
//structors
template<typename T> treeContainer::tree::Node::Node(T value)
{
    setValue(value);
}

//functions
template<typename T> treeContainer::node_iterator treeContainer::tree::Node::appendNode(T value)
{
    std::shared_ptr<Node> node = std::make_shared<Node>(value);
    return appendNode(node);
}

template<typename T> void treeContainer::tree::Node::setValue(T value)
{
    myValue = std::shared_ptr<placeholder>(new holder<T>(value));
}

template<typename T> T treeContainer::tree::Node::getValue()
{
    return std::static_pointer_cast<holder<T>>(myValue)->myValue;
}

template<typename T>
std::type_index treeContainer::tree::Node::holder<T>::getType()
{
    return std::type_index(typeid(myValue));
}

#endif // TREECONTAINER_H