TreeContainer.h

#ifndef TREECONTAINER_H
#define TREECONTAINER_H

/* API & Description:
 *
 * This Container provides the abillity to store values of any type.
 * The structure of the Container is a tree. Each node of the tree stores a value of type T and can have N children.
 * It provides different kinds of iterators to navigate through the tree. Access to the stored value of a node is only possible with an iterator.
 * The tree has always a root-node with two sentinels: Start and End of the children.
 *
 * Class Description:
 *
 * treeContainer:
 * Description:
 * The main class. It provides the functions to modify the tree like creating new nodes, removing them or move them to another position.
 * It also provides the function to search in the tree.
 *
 * Public methods:
 *  template<typename T> node_iterator find(const T& value);                            Find the first node with the value in the tree
 *  template<typename T> node_iterator find(const tree_iterator& it, const T& value);   Find the first node with the value in the children of the node
 *
 *  void clear();                           Remove all nodes from the tree
 *  void clear(const tree_iterator& it);    Remove all nodes from the children of the node
 *
 *  template<typename T> node_iterator createNode(const tree_iterator& parent, const T& value); Create a new Node with value and type of value T and
 *                                                                                              append it to the parent
 *
 *  void move(const tree_iterator& parent, const tree_iterator& node);          Move an existing node to the end of the children of a node
 *  void insertAfter(const tree_iterator& pos, const tree_iterator& node);      Append an existing node to the parent of a node at position after node
 *  void insertPrevious(const tree_iterator& pos, const tree_iterator& node);   Append an existing node to the parent of a node at position previous to node
 *  void swap(const tree_iterator& it_1, const tree_iterator& it_2);            Swap two Nodes
 *
 *  node_iterator remove(const tree_iterator& node);        Remove the node from tree
 *  node_iterator removeToEnd(const tree_iterator& pos);    Remove all childnodes of the parent of the node from this node to the end of the children, including this node
 *  node_iterator removeToStart(const tree_iterator& pos);  Remove all childnodes of the parent of the node from this node to the Start of the children, including this node
 *
 *  int getDepth(const tree_iterator& node);    Returns the depth of the node. The Childnodes of Root have depth = 0;
 *
 *  begin() & end()     Different begin()- and end()-functions for the different iterators. See the description of the functions for more information
 *
 * Classes:
 *  Node
 *  SentinelNode
 *
 * Members:
 *  std::shared_ptr myRoot
 *
 * Iterators:
 *
 * Description:
 * Different Iterators to navigate through the tree and get access to the values of the node or alter the values.
 * Each Iterator has a reverse equivalent, which iterates reverse and is provided as const and non const iterator.
 *
 * node_iterator:
 * Description:
 * The standard iterator of the tree. It iterates through all node until it reaches the end of the tree.
 *
 * child_iterator:
 * Description:
 * This iterator iterates through the children of a node and ignores the children of the children.
 *
 * deep_child_iterator:
 * Description:
 * Same as the child_iterator beside it doesn't ignore the children of the children.
 *
 */

/* ---------------------------------------------------------------------------------------------------------
 *
 * CAUTION: The following class descriptions contain the descriptions of internal classes or methods.
 *          The descriptions provide more information about how the tree works in detail.
 *
 * Node:
 * Description:
 * The nodes of the tree, can be nodes and leafs.
 * Providing the storage for values of any kind.
 * Each node have to have a stored value.
 * Users should not be able to access this class to ensure correct linking between the nodes in the tree.
 *
 * Linking between the Nodes:
 * CAUTION: The parent of Root is Root
 *
 *
 * Parent                            (Node)
 *                                     |
 *                                   Parent
 *                                     |
 * Siblings        (Node)---Prev---(Node)---Next---(Node)
 *                            ______/ /  \ \_______
 *                           /       /    \        \
 *                         Start   First  Last     End
 *                         /       /        \        \
 * Children:  (Sentinal-Start) (Node) ... (Node)   (Sentinel-End)
 *
 *
 * Public methods:
 *  Node* getParent();      Returns the parent node
 *  Node* getPrev();        Returns the previous siblings node
 *  Node* getNext();        Returns the next sibling node
 *  Node* getFirst();       Returns the first child of this node
 *  Node* getLast();        Returns the last child of this node
 *  Node* getStart();       Returns the sentinelnode for start of children of this node
 *  Node* getEnd();         Returns the sentinelnode for end of children of this node
 *
 *  void setParent(Node* parent);   Set the parent of this node
 *  void setPrev(Node* prev);       Set the previous siblings node
 *  void setNext(Node* next);       Set the next siblings node
 *  void setFirst(Node* first);     Set the first child of this node
 *  void setLast(Node* last);       Set the last child of this node
 *
 *  void extract();                         Extract the Node. Deletes the links to relatives, ensure the siblings are correctly linked and
 *                                          ensure the first/last-link of the parent is correct if necessary.
 *                                          Does NOT delete the node from the children of the parent
 *
 *  void erase(Node* node);                 Erase the node from the childred of the parent. Make sure to call extract() after calling erase() to ensure correct linking
 *  void erase(std::shared_ptr<Node> node);
 *
 *  std::shared_ptr<Node> getPtr();         Returns a shared_ptr of this
 *
 *  node_iterator appendNode(std::shared_ptr<Node> node);       Internal function to append a node to children of this
 *  node_iterator insertAfter(std::shared_ptr<Node> node);      Internal function to append node to parent of this at position after this
 *  node_iterator insertPrevious(std::shared_ptr<Node> node);   Internal function to append node to parent of this at position previous to this
 *  void remove(int param);                                     Internal function to remove this node. Also call remove for the next or previous node
 *                                                              to end/start if param is set. The parameters are:
 *                                                              0 = remove only this node,
 *                                                              1 = remove all nodes to the end of children of parent of this, including this node
 *                                                              2 = remove all nodes to the start of children of parent of this, including this node
 *
 *  template<typename T> void setValue(T value);                Set the stored value of type T
 *  template<typename T> T getValue();                          Get the stored value of type T
 *  std::type_index getValueType();                             Get the value type of the stored value
 *
 * Members:
 *  std::shared_ptr<placeholder> myValue = nullptr;             Pointer to the stored value of this node
 *  std::shared_ptr<Node> mySentinelStart = nullptr;            Pointer to the sentinel node at start of the children
 *  std::shared_ptr<Node> mySentinelEnd = nullptr;              Pointer to the sentinel node at end of the children

 *  Node* myParentNode = nullptr;                               Pointer to the parent node. If node is Root, it points to itself
 *  Node* myPrevNode = nullptr;                                 Pointer to the previous siblings node
 *  Node* myNextNode = nullptr;                                 Pointer to the next siblings node
 *  Node* myFirstNode = nullptr;                                Pointer to the first child node. Is NULL if no children exist.
 *  Node* myLastNode = nullptr;                                 Pointer to the last child node. Is NULL if no children exist.

 *  std::vector<std::shared_ptr<Node>> myChildren;              Vector of Pointers of the owned children
 *
 * classes:
 * - placeholder        Abstract class to provide an abstract type for storing values of any type
 * - holder             Template class, provides the storage for values of any type
 *
 *
 * Iterators:
 *
 * tree_iterator:
 * Description:
 * An abstract class each iterator inheritates from to get an abstract type for iterators,
 *
 * Public Methods:
 *  void operator =(tree::Node* node)           =Operator to set the iterator on a node
 *  void operator =(const tree_iterator& rhs)   =Operstor to set the iterator to the same node as an other iterator
 *  bool operator ==(tree_iterator rhs)         ==Operator to compare if the position of this iterator is the same as the position of an other itertor
 *  bool operator !=(tree_iterator rhs)         !=Operator to compare if the position of this iterator is the not same as the position of an other itertor
 *
 *  void Next()     Set the iterator to the next siblings node. If the end the children of the parent is reached it will be set on the parent
 *  void Prev()     Set the iterator to the previous siblings node. If the start the children of the parent is reached it will be set on the parent
 *  void First()    Set the iterator to the first child of the node. If node has no child, the iterator is not set on an other node
 *  void Last()     Set the iterator to the last child of the node. If node has no child, the iterator is not set on an other node
 *  void Parent()   Set the iterator to the parent of this node.
 *
 *  template<typename T> void setValue(T value)  Store a new value of type T in the node
 *  template<typename T> T getValue()            Get the stored value of the node
 *  std::type_index getValueType()               Get the type of the stored value
 *
 *  bool hasChildren()      Returns true, if the node has one or more children
 *
 * Member:
 *  Node* myNode    A raw pointer to the Node the iterator points to
 *
 * Other Iterators:
 * Description: see above
 *
 * Public Methods:
 *  node_iterator& operator ++()            increment the iterator depending the type of the iterator before returning
 *  const node_iterator operator ++(int)    increment the iterator depending the type of the iterator after returning
 *  node_iterator& operator --()            decrement the iterator depending the type of the iterator before returning
 *  const node_iterator operator --(int)    decrement the iterator depending the type of the iterator after returning
 *
 * Members:
 *  inherated myNode
 *  deep_child_iterator: myStart, myEnd     save the positions where the iterator has to stop
 *
 * ---------------------------------------------------------------------------------------------------------
*/
#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:
    /* Description: find first node with value in tree
     * Parameters:  "value" of type T
     * Return:      node_iterator to first node with value of type T  */
    template<typename T> node_iterator find(const T& value);

    /* Description: find first node with value in childnodes of node
     * Parameters:  tree_iterator "it", "value" of type T
     * Return:      node_iterator to first node with value of type T   */
    template<typename T> node_iterator find(const tree_iterator& it, const T& value);

    /* Description: Remove all nodes from tree
     * Parameters:  None
     * Return:      None    */
    void clear();

    /* Description: Remove all childnodes from node
     * Parameters:  tree_iterator "it"
     * Return:      None    */
    void clear(const tree_iterator& it);

    /* Description: Create new node with value of type T and append it to childnodes of parent
     * CAUTION:     Use the end()-method to append the node to Root
     * Parameters:  tree_iterator "it", "value" of type T
     * Return:      node_iterator to created node    */
    template<typename T> node_iterator createNode(const tree_iterator& parent, const T& value);

    /* Description: Append existing node to childnodes of the new parent
     * Parameters:  new parent: tree_iterator "parent", moved node: tree_iterator "node"
     * Return:      None    */
    void move(const tree_iterator& parent, const tree_iterator& node);

    /* Description: Append existing node to childnodes of parent of node at position after node
     * Parameters:  tree_iterator "pos", tree_iterator "node"
     * Return:      None    */
    void insertAfter(const tree_iterator& pos, const tree_iterator& node);

    /* Description: Append existing node to childnodes of parent of node at position previous to node
     * Parameters:  tree_iterator "pos", tree_iterator "node"
     * Return:      None    */
    void insertPrevious(const tree_iterator& pos, const tree_iterator& node);

    /* Description: swap nodes of "it_1" and "it_2"
     * Parameters:  tree_iterator "it_1", tree_iterator "it_2"
     * Return:      None    */
    void swap(const tree_iterator& it_1, const tree_iterator& it_2);

    /* Description: delete node
     * Parameters:  tree_iterator "node"
     * Return:      node_iterator to previous or in case node is the first children to the parent node   */
    node_iterator remove(const tree_iterator& node);

    /* Description: delete all nodes from node at position to end of the childnodes of parent of node including node at position.
     * Parameters:  tree_iterator "pos"
     * Return:      node_iterator to previous or in case node is the first children to the parent node.   */

    node_iterator removeToEnd(const tree_iterator& pos);

    /* Description: delete all nodes from node at position to start of the childnodes of parent of node including node at position.
     * Parameters:  tree_iterator "pos"
     * Return:      node_iterator to next or in case node is the last children to the parent node.   */
    node_iterator removeToStart(const tree_iterator& pos);

    /* Description: get depth of node in tree, children of Root has Deep = 0
     * Parameters:  tree_iterator "node"
     * Return:      depth of type int    */
    int getDepth(const tree_iterator& node);

private:
    /* Description: Internal recursive function to search in the tree
     * Parameters:  T value: value to find, Node* node: raw pointer to the actual Node
     * Return:      raw pointer to the first node with the value, nullptr if the value was not found    */
    template<typename T> Node* find(const T& value, Node* node);

//Functions iterating
public:
    /* Description: returns iterator to beginning of tree/childnodes
     * CAUTION:     use the function which belongs to the used iterator to ensure correctly iterating
     * Parameters:  node_iterators: None, child_iterators: tree_iterator "child"
     * Return:      iterator to the beginning of tree/childnodes    */

    /* Description: returns (const_)node_iterator to beginning of tree for const an non-const node_iterators
     *              In case the tree is empty it returns an node_iterator to root, als to the first child   */
    node_iterator begin();
    const_node_iterator cbegin() const;

    /* Description: returns (const_)reverse_node_iterator to reverse beginning of tree for const an non-const reverse_node_iterators */
    reverse_node_iterator rbegin();
    const_reverse_node_iterator crbegin() const;

    /* Description: returns (const_)child_iterator to beginning of childnodes of node for const an non-const child_node_iterators */
    child_iterator begin(const tree_iterator& parent);
    const_child_iterator cbegin(const tree_iterator& parent) const;

    /* Description: returns (const_)reverse_child_iterator to reverse beginning of childnodes of node for const an non-const reverse_child_node_iterators */
    reverse_child_iterator rbegin(const tree_iterator& parent);
    const_reverse_child_iterator crbegin(const tree_iterator& parent) const;

    /* Description: returns (const_)deep_child_iterator to beginning of childnodes of node for const an non-const deep_child_node_iterators */
    deep_child_iterator dbegin(const tree_iterator& parent);
    const_deep_child_iterator cdbegin(const tree_iterator& parent) const;

    /* Description: returns (const_)reverse_deep_child_iterator to reverse beginning of childnodes of node for const an non-const reverse_deep_child_node_iterators */
    reverse_deep_child_iterator rdbegin(const tree_iterator& parent);
    const_reverse_deep_child_iterator crdbegin(const tree_iterator& parent) const;

    /* Description: returns iterator to end of tree/childnodes
     * CAUTION:     use the function which belongs to the used iterator to ensure correctly iterating
     * Parameters:  node_iterators: None, child_iterators: tree_iterator "child"
     * Return:      iterator to the end of tree/childnodes    */

    /* Description: returns (const_)node_iterator to end of tree for const an non-const node_iterators */
    node_iterator end();
    const_node_iterator cend() const;

    /* Description: returns (const_)reverse_node_iterator to reverse end of tree for const an non-const reverse_node_iterators */
    reverse_node_iterator rend();
    const_reverse_node_iterator crend() const;

    /* Description: returns (const_)child_iterator to end of childnodes of node for const an non-const child_node_iterators */
    child_iterator end(const tree_iterator& parent);
    const_child_iterator cend(const tree_iterator& parent) const;

    /* Description: returns (const_)reverse_child_iterator to reverse end of childnodes of node for const an non-const reverse_child_node_iterators */
    reverse_child_iterator rend(const tree_iterator& parent);
    const_reverse_child_iterator crend(const tree_iterator& parent) const;

    /* Description: returns (const_)deep_child_iterator to end of childnodes of node for const an non-const deep_child_node_iterators */
    deep_child_iterator dend(const tree_iterator& parent);
    const_deep_child_iterator cdend(const tree_iterator& parent) const;

    /* Description: returns (const_)reverse_deep_child_iterator to reverse end of childnodes of node for const an non-const reverse_deep_child_node_iterators */
    reverse_deep_child_iterator rdend(const tree_iterator& parent);
    const_reverse_deep_child_iterator crdend(const tree_iterator& parent) const;

//Classes
private:
    class Node{
        /* Description:
         * This class provides the Nodes and the methods of the Nodes. */
        friend class tree;
    private:

            class placeholder{
                /* Description:
                 * Abstract class for providing an abstract type for any type of value  */
            public:
                virtual ~placeholder() {}

                //Description: virtual function to get access to type of stored value
                virtual std::type_index getType() = 0;
            };

            template<typename T>
            class holder : public placeholder{
                /* Description:
                 * Template class to provide the abillity to store values of any type, inherits from placeholder*/
            public:
                holder(T value) : myValue(value) {}

                /* Description: Returns the type_index of the value which is stored
                 * Parameters:  None
                 * Return:      std::type_index   */
                std::type_index getType();

                T myValue;
            };
    private:
        //Members
        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:
        //structors
        Node();
        template<typename T> Node(T value);
        ~Node();

    public:
        //Public Methods

        /* Description: Get a raw pointer to the related node
         * Parameters:  None
         * Return:      Node*    */
        Node* getParent();
        Node* getPrev();
        Node* getNext();
        Node* getFirst();
        Node* getLast();
        Node* getStart();
        Node* getEnd();

        /* Description: Set a raw pointer to the related node
         * Parameters:  Pointer Node* to relative
         * Return:      None    */
        void setParent(Node* parent);
        void setPrev(Node* prev);
        void setNext(Node* next);
        void setFirst(Node* first);
        void setLast(Node* last);

        /* Description: Extract this node. See class description for details
         * Parameters:  None
         * Return:      None    */
        void extract();

        /* Description: Erase node from children of this. If node is not a sentinel call extract() after erase() to ensure correct linking,
         * Parameters:  None
         * Return:      None    */
        void erase(Node* node);

        /* Description: Get the shared_ptr of this. The shared_ptr is get from the parent node.
         * Parameters:  None
         * Return:      shared_ptr of this    */
        std::shared_ptr<Node> getPtr();

        /* Description: Append a node to the children of this
         * Parameters:  shared_ptr to appending node
         * Return:      node_iterator to appended node    */
        node_iterator appendNode(std::shared_ptr<Node> node);

        /* Description: Append a node to the children of parent of this at position after this
         * Parameters:  shared_ptr to appending node
         * Return:      node_iterator to appended node    */
        node_iterator insertAfter(std::shared_ptr<Node> node);

        /* Description: Append a node to the children of parent of this at position previous to this
         * Parameters:  shared_ptr to appending node
         * Return:      node_iterator to appended node    */
        node_iterator insertPrevious(std::shared_ptr<Node> node);

        /* Description: Remove this node and if param is set all nodes to start or end of children of parent of this. See the class description for parameterlist
         * Parameters:  type of removing as int
         * Return:      None    */
        void remove(int param);

        /* Description: Template function to set the stored value of this node
         * Parameters:  value with type T
         * Return:      None    */
        template<typename T> void setValue(T value);

        /* Description: Get the stored value of this node of type T
         * Parameters:  None
         * Return:      value of type T   */
        template<typename T> T getValue();

        /* Description: Get the type of the stored value
         * Parameters:  None
         * Return:      type of the stored value as type_index    */
        std::type_index getValueType();

        /* Description: Operator to set the stored value of this node
         * Parameters:  value of type T
         * Return:      None    */
        template<typename T> void operator =(T value) { setValue(value); }

    private:
        //Helper functions

        /* Description: push new node to the list of children of this
         * Parameters:  shared_ptr to the new child
         * Return:      shared_ptr of the new child    */
        std::shared_ptr<Node> pushNewNode(std::shared_ptr<Node> node);

        /* Description: Check, if the sentinel nodes and the first/last pointer of this are correctly linked
         * Parameters:  None
         * Return:      None    */
        void checkSentinels();

        /* Description: Link to nodes as siblings. First is linked as the previous node of second and second is linked as the next of first.
         *              Pointer can be NULL
         * Parameters:  first: raw pointer to previous node, second: raw pointer to next node
         * Return:      None    */
        void linkNodes(Node* first, Node* second);
    };

    class SentinelNode : public Node{
        /* Description: Simpel inhertated class from Node to get an another type of node to provide an own type for sentinel nodes.
         *              Stored values are always int.
         *              List of values and meanings:
         *              0: Root
         *              1: Start
         *              2: End
         *              Different values to the list have no effect on the correct function of the tree. The different values are just for debugging
         *              and because the nodes have to have a value.
         */
        friend class tree;
    public:
        SentinelNode(int value);
        ~SentinelNode();
    };

//Storage
private:
    std::shared_ptr<Node> myRoot = nullptr;
};


//Iterators
class tree_iterator
{
    /* Description:
     * Abstract class to provide an abstract type for all iterators. Provides the methods to iterate through the tree */
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() {}

    /*Description: Set the iterator to the node. Only used internaly */
    void operator =(tree::Node* node)
    {
        myNode = node;
    }

    /*Description: Set the iterator to the node the passed iterator is pointing to */
    void operator =(const tree_iterator& rhs)
    {
        myNode = rhs.myNode;
    }

    /*Description: Compare if the nodes the passed iterator and this are pointing to are the same */
    bool operator ==(const tree_iterator& rhs)
    {
        return myNode == rhs.myNode;
    }

    /*Description: Compare if the nodes the passed iterator and this are pointing to are not the same */
    bool operator !=(const tree_iterator& rhs)
    {
        return !(myNode == rhs.myNode);
    }

    /*Description: Set the iterator to the next sibling.
     * If the next sibling is the end of the children of the parent, the iterator is set to the parent */
    void Next()
    {
        if(myNode->getNext() != myNode->getParent()->getEnd()) myNode = myNode->getNext();
        else Parent();
    }

    /*Description: Set the iterator to the previous sibling.
     * If the previous sibling is the start of the children of the parent, the iterator is set to the parent */
    void Prev()
    {
        if(myNode->getPrev() != myNode->getParent()->getStart()) myNode = myNode->getPrev();
        else Parent();
    }

    /*Description: Set the iterator to the first child of the node.
     * If the node has no children, the iterator is not set to an other node */
    void First()
    {
        if(myNode->getFirst()) myNode = myNode->getFirst();
    }

    /*Description: Set the iterator to the last child of the node.
     * If the node has no children, the iterator is not set to an other node */
    void Last()
    {
        if(myNode->getLast()) myNode = myNode->getLast();
    }

    /*Description: Set the iterator to the parent of the node */
    void Parent()
    {
        myNode = myNode->getParent();
    }

    /*Description: Assigns a new value to the node */
    template<typename T> void setValue(T value)
    {
        myNode->setValue(value);
    }

    /*Description: Get the value of the node */
    template<typename T> T getValue()
    {
        return myNode->getValue<T>();
    }

    /*Description:  Get the type of the value of the node. Returns as type_index*/
    std::type_index getValueType()
    {
        return myNode->getValueType();
    }

    /*Description: Returns true, if the node has one or more children, else false */
    bool hasChildren()
    {
        if(myNode->getFirst()) return true;
        else return false;
    }

protected:
    /*Description:  Internal method. Set the iterator to the next node. If the actual node has children the iterator is set to the first child
                    At the end of the children getNext() is called to get the next node which is not a sentinel Node*/
    void increment()
    {
        if(myNode->getFirst()) myNode = myNode->getFirst();
        else if(myNode->getNext())
        {
            myNode = myNode->getNext();
            if(!myNode->getNext()) getNext();
        }
        else getNext();
    }

    /*Description:  Internal method. Set the iterator to the previus node. If the actual node has children the iterator is set to the last child
                    At the Start of the children getPrev() is called to get the previus node which is not a sentinel node*/
    void decrement()
    {
        if(myNode->getLast()) myNode = myNode->getLast();
        else if(myNode->getPrev())
        {
            myNode = myNode->getPrev();
            if(!myNode->getPrev()) getPrev();
        }
        else getPrev();
    }

    /*Description:  Internal method. Searches recursive for the next node which is not a sentinel an set the iterator to this*/
    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();
        }
    }

    /*Description:  Internal method. Searches recursive for the previous node which is not a sentinel an set the iterator to this*/
    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(const tree_iterator& it) {myNode = it.myNode; }

    ~node_iterator() {}

    /*Description:  Increment an decrement operators. Behaviour depends on type of the 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(const tree_iterator& it) {myNode = it.myNode; }

    ~reverse_node_iterator() {}

    /*Description:  Increment an decrement operators. Behaviour depends on type of the 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(const tree_iterator& it) {myNode = it.myNode->getFirst(); }

    ~child_iterator() {}

    /*Description:  Increment an decrement operators. Behaviour depends on type of the 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(const tree_iterator& it) { myNode = it.myNode->getLast(); }

    ~reverse_child_iterator() {}

    /*Description:  Increment an decrement operators. Behaviour depends on type of the 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(const tree_iterator& it)
    {
        myNode = it.myNode->getFirst();
        myEndNode = it.myNode->getEnd();
        myStartNode = it.myNode->getStart();
    }

    ~deep_child_iterator() {}

    /*Description:  Increment an decrement operators. Behaviour depends on type of the 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(const tree_iterator& it)
    {
        myNode = it.myNode->getFirst();
        myEndNode = it.myNode->getEnd();
        myStartNode = it.myNode->getStart();
    }

    ~reverse_deep_child_iterator() {}

    /*Description:  Increment an decrement operators. Behaviour depends on type of the 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

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

    return node_iterator(ret);
}

//Find values in children of passed node
template<typename T> treeContainer::node_iterator treeContainer::tree::find(const tree_iterator& it, const T& value)
{
    Node* ret = find(value, it.myNode);
    if(!ret) ret = myRoot->getEnd();

    return node_iterator(ret);
}

//Internal recursive method to search in the tree
template<typename T> treeContainer::tree::Node* treeContainer::tree::find(const 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;
}

//create a new node with value of type T and append it to the children of passed node
template<typename T> treeContainer::node_iterator treeContainer::tree::createNode(const tree_iterator& parent, const T& value)
{
    node_iterator ret;

    if(parent.myNode == myRoot->getEnd()) ret = myRoot->appendNode(std::make_shared<Node>(value));
    else ret = parent.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

//Store passed value of type T an store it in newly created holder
template<typename T> void treeContainer::tree::Node::setValue(T value)
{
    myValue = std::shared_ptr<placeholder>(new holder<T>(value));
}

//Returns the stored value of type T
template<typename T> T treeContainer::tree::Node::getValue()
{
    return std::static_pointer_cast<holder<T>>(myValue)->myValue;
}

//Returns the type of stored value as type_index
template<typename T>
std::type_index treeContainer::tree::Node::holder<T>::getType()
{
    return std::type_index(typeid(myValue));
}

#endif // TREECONTAINER_H