TreeContainer.h

#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;
class deep_child_iterator;
class reverse_deep_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;
typedef const deep_child_iterator const_deep_child_iterator;
typedef const reverse_deep_child_iterator const_reverse_deep_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;
    friend class deep_child_iterator;
    friend class reverse_deep_child_iterator;

    class Node;

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

//functions
public:
    //find "value" in tree
    template<typename T> node_iterator find(T value);
    //find "value" in childnodes of "it"
    template<typename T> node_iterator find(tree_iterator it, T value);

    //clear tree
    void clear();
    //clear node
    void clear(tree_iterator it);

    //append node with value "value" to "it"
    template<typename T> node_iterator appendNode(tree_iterator it, T value);

    //append existing "node" to "it"
    node_iterator move(tree_iterator it, tree_iterator node);

    //append existing "node" to parent of "it" at position after "it"
    node_iterator insertAfter(tree_iterator it, tree_iterator node);
    //append existing "node" to parent of "it" at position previous to "it"
    node_iterator insertPrevious(tree_iterator it, tree_iterator node);

    //swap nodes of "it_1" and "it_2"
    void swap(tree_iterator it_1, tree_iterator it_2);

    //delete node
    void remove(tree_iterator it);
    //delete all nodes from "it" to end
    void removeToEnd(tree_iterator it);
    //delete all nodes from "it" to start
    void removeToStart(tree_iterator it);

    //get depth of node, children of Root has Deep = 0
    int getDepth(tree_iterator it);

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 it);
    const_child_iterator cbegin(tree_iterator it) const;

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

    deep_child_iterator dbegin(tree_iterator it);
    const_deep_child_iterator cdbegin(tree_iterator it) const;

    reverse_deep_child_iterator rdbegin(tree_iterator it);
    const_reverse_deep_child_iterator crdbegin(tree_iterator it) const;

    node_iterator end();
    const_node_iterator cend() const;

    reverse_node_iterator rend();
    const_reverse_node_iterator crend() const;

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

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

    deep_child_iterator dend(tree_iterator it);
    const_deep_child_iterator cdend(tree_iterator it) const;

    reverse_deep_child_iterator rdend(tree_iterator it);
    const_reverse_deep_child_iterator crdend(tree_iterator it) 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;
        std::shared_ptr<Node> mySentinelStart = nullptr;
        std::shared_ptr<Node> mySentinelEnd = nullptr;

        Node* myParentNode = nullptr;
        Node* myPrevNode = nullptr;
        Node* myNextNode = nullptr;
        Node* myFirstNode = nullptr;
        Node* myLastNode = nullptr;

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

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

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

        std::shared_ptr<Node> getPtr();

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

        node_iterator insertAfter(std::shared_ptr<Node> node);
        node_iterator insertPrevious(std::shared_ptr<Node> node);

        void remove(int 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 setParent(Node* parent);
        void setPrev(Node* prev);
        void setNext(Node* next);
        void setFirst(Node* first);
        void setLast(Node* last);

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

        //Helper functions
        std::shared_ptr<Node> pushNewNode(std::shared_ptr<Node> node);
        void checkSentinels();
        void linkNodes(Node* first, Node* second);
    };

    class SentinelNode : public Node{
    /* Values:
     * 0: Root
     * 1: Start
     * 2: End
    */
        friend class tree;
    public:
        SentinelNode(int value);
        ~SentinelNode();
    };

//Storage
private:
    std::shared_ptr<Node> myRoot = nullptr;
    //std::shared_ptr<Node> myStart = nullptr;
    //std::shared_ptr<Node> 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;
    friend class deep_child_iterator;
    friend class reverse_deep_child_iterator;
public:
    virtual ~tree_iterator() {}

    void operator =(tree::Node* node)
    {
        myNode = node;
    }
    void operator =(tree_iterator rhs)
    {
        myNode = rhs.myNode;
    }
    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->getParent()->getEnd()) myNode = myNode->getNext();
        else Parent();
    }
    void Prev()
    {
        if(myNode->getPrev() != myNode->getParent()->getStart()) myNode = myNode->getPrev();
        else Parent();
    }
    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();
    }

    bool hasChildren()
    {
        if(myNode->getFirst()) return true;
        else return false;
    }

protected:
    void increment()
    {
        if(myNode->getFirst()) myNode = myNode->getFirst();
        else if(myNode->getNext())
        {
            myNode = myNode->getNext();
            if(!myNode->getNext()) getNext();
        }
        else getNext();
    }
    void decrement()
    {
        if(myNode->getLast()) myNode = myNode->getLast();
        else if(myNode->getPrev())
        {
            myNode = myNode->getPrev();
            if(!myNode->getPrev()) getPrev();
        }
        else getPrev();
    }
    void getNext()
    {
        if(myNode->getParent() == myNode) myNode = myNode->getEnd(); //is root?
        else
        {
            if(myNode->getParent()->getNext()) myNode = myNode->getParent()->getNext();
            else
            {
                myNode = myNode->getParent();
                getNext();
                return;
            }
            if(!myNode->getNext()) getNext();
        }
    }
    void getPrev()
    {
        if(myNode->getParent() == myNode) myNode = myNode->getStart(); //is root?
        else
        {
            if(myNode->getParent()->getPrev()) myNode = myNode->getParent()->getPrev();
            else
            {
                myNode = myNode->getParent();
                getPrev();
                return;
            }
            if(!myNode->getPrev()) 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;
    }
};
class deep_child_iterator : public tree_iterator
{
private:
    friend class tree;
    deep_child_iterator(tree::Node* node)
    {
        myNode = node;
        myEndNode = node->getEnd();
        myStartNode = node->getStart();
    }
public:
    deep_child_iterator() {}
    deep_child_iterator(tree_iterator it)
    {
        myNode = it.myNode->getFirst();
        myEndNode = it.myNode->getEnd();
        myStartNode = it.myNode->getStart();
    }

    ~deep_child_iterator() {}

    deep_child_iterator& operator ++()
    {
        if(myNode->getFirst()) myNode = myNode->getFirst();
        else if(myNode->getNext() == myNode->getParent()->getEnd() && myNode->getNext() != myEndNode) myNode = myNode->getParent()->getNext();
        else myNode = myNode->getNext();

        return *this;
    }
    const deep_child_iterator operator ++(int)
    {
        deep_child_iterator ret(*this);
        ++(*this);
        return ret;
    }
    deep_child_iterator& operator --()
    {
        if(myNode->getLast()) myNode = myNode->getLast();
        else if(myNode->getPrev() == myNode->getParent()->getStart() && myNode->getPrev() != myStartNode) myNode = myNode->getParent()->getPrev();
        else myNode = myNode->getPrev();
        return *this;
    }
    const deep_child_iterator operator --(int)
    {
        deep_child_iterator ret(*this);
        --(*this);
        return ret;
    }
private:
    tree::Node* myEndNode;
    tree::Node* myStartNode;
};
class reverse_deep_child_iterator : public tree_iterator
{
private:
    friend class tree;
    reverse_deep_child_iterator(tree::Node* node)
    {
        myNode = node;
        myEndNode = node->getEnd();
        myStartNode = node->getStart();
    }
public:
    reverse_deep_child_iterator() {}
    reverse_deep_child_iterator(tree_iterator& it)
    {
        myNode = it.myNode->getFirst();
        myEndNode = it.myNode->getEnd();
        myStartNode = it.myNode->getStart();
    }

    ~reverse_deep_child_iterator() {}

    reverse_deep_child_iterator& operator ++()
    {
        if(myNode->getLast()) myNode = myNode->getLast();
        else if(myNode->getPrev() == myNode->getParent()->getStart() && myNode->getPrev() != myStartNode) myNode = myNode->getParent()->getPrev();
        else myNode = myNode->getPrev();
        return *this;
    }
    const reverse_deep_child_iterator operator ++(int)
    {
        reverse_child_iterator ret(*this);
        ++(*this);
        return ret;
    }
    reverse_deep_child_iterator& operator --()
    {
        if(myNode->getLast()) myNode = myNode->getLast();
        else if(myNode->getPrev() == myNode->getParent()->getStart() && myNode->getPrev() != myStartNode) myNode = myNode->getParent()->getNext();
        else myNode = myNode->getPrev();
        return *this;
    }
    const reverse_deep_child_iterator operator --(int)
    {
        reverse_deep_child_iterator ret(*this);
        --(*this);
        return ret;
    }
private:
    tree::Node* myEndNode;
    tree::Node* myStartNode;
};
}


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

//Functions
template<typename T> treeContainer::node_iterator treeContainer::tree::find(T value)
{
    Node* ret = find(value, myRoot->getFirst());
    if(!ret) ret = myRoot->getEnd();

    return node_iterator(ret);
}

template<typename T> treeContainer::node_iterator treeContainer::tree::find(treeContainer::tree_iterator it, T value)
{
    Node* ret = find(value, it.myNode);
    if(!ret) ret = myRoot->getEnd();

    return node_iterator(ret);
}
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() && node->getNext() != node->getParent()->getEnd()) ret = find(value, node->getNext());

    return ret;
}

template<typename T> treeContainer::node_iterator treeContainer::tree::appendNode(tree_iterator it, T value)
{
    if(it.myNode == myRoot->getEnd()) it = myRoot.get();

    node_iterator ret = it.myNode->appendNode(std::make_shared<Node>(value));
    return ret;
}

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

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

    //Add SentinalNodes
    mySentinelStart = pushNewNode(std::make_shared<SentinelNode>(1));
    mySentinelEnd = pushNewNode(std::make_shared<SentinelNode>(2));

    linkNodes(mySentinelStart.get(), mySentinelEnd.get());
}

//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