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.
 *
 *
 * Class Descriptions:
 * tree:
 *  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 tree_iterator, a wrapper to wrap different kinds of iterators with different increment and decrement behaviour.
 *
 * Iterators:
 *  Different types of Iterators to navigate through the tree and get access to the values of the node or alter the values.
 *  The only public iterator is the wrapper tree_iterator. tree_iterator provides the functions to navigate through the tree and
 *  getting access to stored values of the nodes. tree_iterator wraps different kinds of iterators with different increment an decrement behaviour.
 *
 *  Iterator types:
 *  node_iterator:                iterates through all nodes of the tree.
 *  const_node_iterator:          const version of node_iterator
 *
 *  reverse_node_iterator:        iterates reverse through all nodes of the tree.
 *  const_reverse_node_iterator:  const version of reverse_node_iterator
 *
 *  child_iterator:               iterates through all childnodes of a node. Ignores the chilren of the children.
 *  const_child_iterator:         const version of child_iterator
 *
 *  reverse_child_iterator:       iterates reverse through all childnodes of a node. Ignores the chilren of the children.
 *  const_reverse_child_iterator: const version of reverse_child_iterator
 *
 *
 *
 * API:
 *
 * 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> tree_iterator find(const tree_iterator& start,                 Find the first node in range. If end of tree is reached the search is continued
 *                                          const tree_iterator& end, const T& value);  at the beginning of the tree.
 *
 *  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> tree_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
 *
 *  tree_iterator remove(const tree_iterator& node);        Remove the node from tree
 *  tree_iterator remove(const tree_iterator& first,        Remove all children in range
 *                       const tree_iterator& last);
 *
 *  int getDepth(const tree_iterator& node);    Returns the depth of the node. The Childnodes of Root have depth = 0;
 *
 *
 *  tree_iterator begin();          Returns a tree_iterator of type node_iterator to the beginning of the tree
 *  tree_iterator cbegin() const;   Returns a tree_iterator of type const_node_iterator to the beginning of the tree
 *
 *  tree_iterator rbegin();         Returns a tree_iterator of type reverse_node_iterator to the reverse beginning of the tree
 *  tree_iterator crbegin() const;  Returns a tree_iterator of type const_reverse_node_iterator to the reverse beginning of the tree
 *
 *  tree_iterator begin(const tree_iterator& parent);           Returns a tree_iterator of type child_iterator to the beginning of the children of the node
 *  tree_iterator cbegin(const tree_iterator& parent) const;    Returns a tree_iterator of type const_child_iterator to the beginning of the children of the node
 *
 *  tree_iterator rbegin(const tree_iterator& parent);          Returns a tree_iterator of type reverse_child_iterator to the reverse beginning of the children of the node
 *  tree_iterator crbegin(const tree_iterator& parent) const;   Returns a tree_iterator of type const_reverse_child_iterator to the reverse beginning of the children of the node
 *
 *  tree_iterator end();            Returns a tree_iterator of type node_iterator to the end of the tree
 *  tree_iterator cend() const;     Returns a tree_iterator of type const_node_iterator to the end of the tree
 *
 *  tree_iterator rend();           Returns a tree_iterator of type reverse_node_iterator to the reverse end of the tree
 *  tree_iterator crend() const;    Returns a tree_iterator of type const_reverse_node_iterator to the reverse end of the tree
 *
 *  tree_iterator end(const tree_iterator& parent);         Returns a tree_iterator of type child_iterator to the end of the children
 *  tree_iterator cend(const tree_iterator& parent) const;  Returns a tree_iterator of type const_child_iterator to the end of the children
 *
 *  tree_iterator rend(const tree_iterator& parent);        Returns a tree_iterator of type reverse_child_iterator to the reverse end of the children
 *  tree_iterator crend(const tree_iterator& parent) const; Returns a tree_iterator of type const_reverse_child_iterator to the reverse end of the children
 *
 *
 *  tree_iterator node_iterator(const tree_iterator& pos);               Returns a tree_iterator of type node_iterator to the position
 *  tree_iterator const_node_iterator(const tree_iterator& pos);         Returns a tree_iterator of type const_node_iterator to the position
 *  tree_iterator reverse_node_iterator(const tree_iterator& pos);       Returns a tree_iterator of type reverse_node_iterator to the position
 *  tree_iterator const_reverse_node_iterator(const tree_iterator& pos); Returns a tree_iterator of type const_reverse_node_iterator to the position
 *  tree_iterator child_iterator(const tree_iterator& pos);              Returns a tree_iterator of type child_iterator to the position
 *  tree_iterator const_child_iterator(const tree_iterator& pos);        Returns a tree_iterator of type const_child_iterator to the position
 *  tree_iterator reverse_child_iterator(const tree_iterator& pos);      Returns a tree_iterator of type reverse_child_iterator to the position
 *  tree_iterator const_reverse_child_iterator(const tree_iterator& pos);Returns a tree_iterator of type const_reverse_child_iterator to the position
 *
 *
 *
 * tree-iterator:
 *
 * Public methods:
 *  tree_iterator(const tree_iterator& it):     Constructor, initialize the tree_iterator with an other tree_iterator
 *
 *  operator =(const tree_iterator& rhs):       Assign an iterator to the tree_iterator
 *  bool operator ==(const tree_iterator& rhs): Compare if the passed iterator and this pointing to the same node
 *  bool operator !=(const tree_iterator& rhs): Compare if the passed iterator and this are not pointing to the same node
 *  tree_iterator& operator ++():               Pre-increment operator. Behaviour depends on wrapped iterator
 *  const tree_iterator operator ++(int junk):  Post-increment operator. Behaviour depends on wrapped iterator
 *  tree_iterator& operator --():               Pre-decrement operator. Behaviour depends on wrapped iterator
 *  const tree_iterator operator --(int junk):  Post-decrement operator. Behaviour depends on wrapped iterator
 *
 *  void Next():    Set the iterator to the next sibling.
 *  void Prev():    Set the iterator to the previous sibling
 *  void First():   Set the iterator to the first child
 *  void Last():    Set the iterator to the last child
 *  void Parent():  Set the iterator to the parent
 *
 *  bool hasChildren(): Returns true, if the node the iterator is pointing to has children
 *
 *  template<typename T> void setValue(T value):    Assign a value to node the iterator is pointing to
 *  template<typename T> T getValue():              Get the value of the node the iterator is pointing to
 *  std::type_index getValueType():                 get the type of the value of the node the iterator is pointing to
 *
 */


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

namespace treeContainer {

class tree{
private:
    class _Node;

public:
    class tree_iterator;

//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. If no node match, end() is returned */
    template<typename T> tree_iterator find(const T& value);

    /* Description: find first node with value in range
     * Parameters:  tree_iterator "pos", "value" of type T
     * Return:      node_iterator to first node with value of type T. If no node match, end() is returned   */
    template<typename T> tree_iterator find(const tree_iterator& start, const tree_iterator& end, 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& node);

    /* 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> tree_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 pos
     * Return:      node_iterator to previous or in case first is the first children to the parent node   */
    tree_iterator remove(const tree_iterator& pos);

    /* Description: delete nodes. All nodes from first to last will be deleted
     * Parameters:  tree_iterator first, tree_iterator last
     * Return:      node_iterator to previous or in case first is the first children to the parent node   */
    tree_iterator remove(const tree_iterator& first, const tree_iterator& last);

    /* 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);


    //Functions iterating

    /* 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 to parent
     * Return:      tree_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   */
    tree_iterator begin();
    tree_iterator cbegin() const;

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

    /* Description: returns (const_)child_iterator to beginning of childnodes of node for const an non-const child_node_iterators */
    tree_iterator begin(const tree_iterator& parent);
    tree_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 */
    tree_iterator rbegin(const tree_iterator& parent);
    tree_iterator crbegin(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 */
    tree_iterator end();
    tree_iterator cend() const;

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

    /* Description: returns (const_)child_iterator to end of childnodes of node for const an non-const child_node_iterators */
    tree_iterator end(const tree_iterator& parent);
    tree_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 */
    tree_iterator rend(const tree_iterator& parent);
    tree_iterator crend(const tree_iterator& parent) const;


    //Functions get Iterator of type

    /*Description: Returns a tree_iterator which wraps an iterator of called type pointing to the node of the passed tree_iterator */
    tree_iterator node_iterator(const tree_iterator& pos);
    tree_iterator const_node_iterator(const tree_iterator& pos);

    tree_iterator reverse_node_iterator(const tree_iterator& pos);
    tree_iterator const_reverse_node_iterator(const tree_iterator& pos);

    tree_iterator child_iterator(const tree_iterator& pos);
    tree_iterator const_child_iterator(const tree_iterator& pos);

    tree_iterator reverse_child_iterator(const tree_iterator& pos);
    tree_iterator const_reverse_child_iterator(const tree_iterator& pos);

//Classes

//Iterators:

private:
    class _iterator_impl
    {
        friend class tree;
    public:
        virtual ~_iterator_impl() {}

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

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

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

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

        /*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(Node->NextNode) Node = Node->NextNode;
            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(Node->PrevNode) Node = Node->PrevNode;
            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(Node->FirstNode) Node = Node->FirstNode;
        }

        /*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(Node->LastNode) Node = Node->LastNode;
        }

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

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

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

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

        /*Description: Returns true, if the node has one or more children, else false */
        bool hasChildren()
        {
            if(Node->FirstNode) return true;
            else return false;
        }
        virtual _iterator_impl& operator ++() = 0;
        virtual const std::shared_ptr<_iterator_impl> operator ++(int) = 0;

        virtual _iterator_impl& operator --() = 0;
        virtual const std::shared_ptr<_iterator_impl> operator --(int) = 0;
    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(Node->FirstNode) Node = Node->FirstNode;
            else
            {
                while(!Node->NextNode) Node = Node->ParentNode;
                Node = Node->NextNode;
            }
        }

        /*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(Node->PrevNode)
            {
                Node = Node->PrevNode;
                while(Node->LastNode) Node = Node->LastNode;
            }
            else Node = Node->ParentNode;
        }

    protected:
        tree::_Node* Node;
    };
    class _node_iterator_impl : public _iterator_impl
    {
    public:
        _node_iterator_impl() {}
        _node_iterator_impl(tree::_Node* node) { Node = node; }
        _node_iterator_impl(const _iterator_impl* it) { Node = it->Node; }
        _node_iterator_impl(const tree_iterator& it) {Node = it.iterator->Node; }

        ~_node_iterator_impl() {}

        /*Description:  Increment an decrement operators. Behaviour depends on type of the iterator */
        _iterator_impl& operator ++()
        {
            increment();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator ++(int)
        {
            std::shared_ptr<_node_iterator_impl> ret = std::make_shared<_node_iterator_impl>(*this);
            ++(*this);
            return ret;
        }
        _iterator_impl& operator --()
        {
            decrement();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator --(int)
        {
            std::shared_ptr<_node_iterator_impl> ret = std::make_shared<_node_iterator_impl>(this);
            --(*this);
            return ret;
        }
    };
    class _const_node_iterator_impl : public _iterator_impl
    {
    public:
        _const_node_iterator_impl() {}
        _const_node_iterator_impl(tree::_Node* node) { Node = node; }
        _const_node_iterator_impl(const _iterator_impl* it) { Node = it->Node; }
        _const_node_iterator_impl(const tree_iterator& it) {Node = it.iterator->Node; }

        ~_const_node_iterator_impl() {}

        /*Description:  Increment an decrement operators. Behaviour depends on type of the iterator */
        _iterator_impl& operator ++()
        {
            increment();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator ++(int)
        {
            std::shared_ptr<_const_node_iterator_impl> ret = std::make_shared<_const_node_iterator_impl>(*this);
            ++(*this);
            return ret;
        }
        _iterator_impl& operator --()
        {
            decrement();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator --(int)
        {
            std::shared_ptr<_const_node_iterator_impl> ret = std::make_shared<_const_node_iterator_impl>(this);
            --(*this);
            return ret;
        }
    };
    class _reverse_node_iterator_impl : public _iterator_impl
    {
    public:
        _reverse_node_iterator_impl() {}
        _reverse_node_iterator_impl(tree::_Node* node) { Node = node; }
        _reverse_node_iterator_impl(const _iterator_impl* it) { Node = it->Node; }
        _reverse_node_iterator_impl(const tree_iterator& it) {Node = it.iterator->Node; }

        ~_reverse_node_iterator_impl() {}

        /*Description:  Increment an decrement operators. Behaviour depends on type of the iterator */
        _iterator_impl& operator ++()
        {
            decrement();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator ++(int)
        {
            std::shared_ptr<_reverse_node_iterator_impl> ret = std::make_shared<_reverse_node_iterator_impl>(this);
            ++(*this);
            return ret;
        }
        _iterator_impl& operator --()
        {
            increment();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator --(int)
        {
            std::shared_ptr<_reverse_node_iterator_impl> ret = std::make_shared<_reverse_node_iterator_impl>(this);
            --(*this);
            return ret;
        }
    };
    class _const_reverse_node_iterator_impl : public _iterator_impl
    {
    public:
        _const_reverse_node_iterator_impl() {}
        _const_reverse_node_iterator_impl(tree::_Node* node) { Node = node; }
        _const_reverse_node_iterator_impl(const _iterator_impl* it) { Node = it->Node; }
        _const_reverse_node_iterator_impl(const tree_iterator& it) {Node = it.iterator->Node; }

        ~_const_reverse_node_iterator_impl() {}

        /*Description:  Increment an decrement operators. Behaviour depends on type of the iterator */
        _iterator_impl& operator ++()
        {
            decrement();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator ++(int)
        {
            std::shared_ptr<_const_reverse_node_iterator_impl> ret = std::make_shared<_const_reverse_node_iterator_impl>(this);
            ++(*this);
            return ret;
        }
        _iterator_impl& operator --()
        {
            increment();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator --(int)
        {
            std::shared_ptr<_const_reverse_node_iterator_impl> ret = std::make_shared<_const_reverse_node_iterator_impl>(this);
            --(*this);
            return ret;
        }
    };
    class _child_iterator_impl : public _iterator_impl
    {
    public:
        _child_iterator_impl() {}
        _child_iterator_impl(tree::_Node* node) { Node = node; }
        _child_iterator_impl(const _iterator_impl* it) { Node = it->Node; }
        _child_iterator_impl(const tree_iterator& it) {Node = it.iterator->Node->FirstNode; }

        ~_child_iterator_impl() {}

        /*Description:  Increment an decrement operators. Behaviour depends on type of the iterator */
        _iterator_impl& operator ++()
        {
            if(Node->NextNode) Node = Node->NextNode;
            else increment();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator ++(int)
        {
            std::shared_ptr<_child_iterator_impl> ret = std::make_shared<_child_iterator_impl>(this);
            ++(*this);
            return ret;
        }
        _iterator_impl& operator --()
        {
            if(Node->PrevNode) Node = Node->PrevNode;
            else decrement();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator --(int)
        {
            std::shared_ptr<_child_iterator_impl> ret = std::make_shared<_child_iterator_impl>(this);
            --(*this);
            return ret;
        }
    };
    class _const_child_iterator_impl : public _iterator_impl
    {
    public:
        _const_child_iterator_impl() {}
        _const_child_iterator_impl(tree::_Node* node) { Node = node; }
        _const_child_iterator_impl(const _iterator_impl* it) { Node = it->Node; }
        _const_child_iterator_impl(const tree_iterator& it) {Node = it.iterator->Node->FirstNode; }

        ~_const_child_iterator_impl() {}

        /*Description:  Increment an decrement operators. Behaviour depends on type of the iterator */
        _iterator_impl& operator ++()
        {
            if(Node->NextNode) Node = Node->NextNode;
            else increment();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator ++(int)
        {
            std::shared_ptr<_const_child_iterator_impl> ret = std::make_shared<_const_child_iterator_impl>(this);
            ++(*this);
            return ret;
        }
        _iterator_impl& operator --()
        {
            if(Node->PrevNode) Node = Node->PrevNode;
            else decrement();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator --(int)
        {
            std::shared_ptr<_const_child_iterator_impl> ret = std::make_shared<_const_child_iterator_impl>(this);
            --(*this);
            return ret;
        }
    };
    class _reverse_child_iterator_impl : public _iterator_impl
    {
    public:
        _reverse_child_iterator_impl() {}
        _reverse_child_iterator_impl(tree::_Node* node) { Node = node; }
        _reverse_child_iterator_impl(const _iterator_impl* it) { Node = it->Node; }
        _reverse_child_iterator_impl(const tree_iterator& it) { Node = it.iterator->Node->LastNode; }

        ~_reverse_child_iterator_impl() {}

        /*Description:  Increment an decrement operators. Behaviour depends on type of the iterator */
        _iterator_impl& operator ++()
        {
            if(Node->PrevNode) Node = Node->PrevNode;
            else decrement();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator ++(int)
        {
            std::shared_ptr<_reverse_child_iterator_impl> ret = std::make_shared<_reverse_child_iterator_impl>(this);
            ++(*this);
            return ret;
        }
        _iterator_impl& operator --()
        {
            if(Node->NextNode) Node = Node->NextNode;
            else increment();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator --(int)
        {
            std::shared_ptr<_reverse_child_iterator_impl> ret = std::make_shared<_reverse_child_iterator_impl>(this);
            --(*this);
            return ret;
        }
    };
    class _const_reverse_child_iterator_impl : public _iterator_impl
    {
    public:
        _const_reverse_child_iterator_impl() {}
        _const_reverse_child_iterator_impl(tree::_Node* node) { Node = node; }
        _const_reverse_child_iterator_impl(const _iterator_impl* it) { Node = it->Node; }
        _const_reverse_child_iterator_impl(const tree_iterator& it) { Node = it.iterator->Node->LastNode; }

        ~_const_reverse_child_iterator_impl() {}

        /*Description:  Increment an decrement operators. Behaviour depends on type of the iterator */
        _iterator_impl& operator ++()
        {
            if(Node->PrevNode) Node = Node->PrevNode;
            else decrement();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator ++(int)
        {
            std::shared_ptr<_const_reverse_child_iterator_impl> ret = std::make_shared<_const_reverse_child_iterator_impl>(this);
            ++(*this);
            return ret;
        }
        _iterator_impl& operator --()
        {
            if(Node->NextNode) Node = Node->NextNode;
            else increment();
            return *this;
        }
        const std::shared_ptr<_iterator_impl> operator --(int)
        {
            std::shared_ptr<_const_reverse_child_iterator_impl> ret = std::make_shared<_const_reverse_child_iterator_impl>(this);
            --(*this);
            return ret;
        }
    };

public:
    class tree_iterator
    {
        friend class tree;
    private:
        tree_iterator(const std::shared_ptr<_iterator_impl>& it) { iterator = it; }
    public:
        tree_iterator(const tree_iterator& it) : iterator(it.iterator) {}
        ~tree_iterator() {}

        /*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() { iterator->Next(); }

        /*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() { iterator->Prev(); }

        /*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() { iterator->First(); }

        /*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() { iterator->Last(); }

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

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

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

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

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

        /*Description: Assign an iterator to this */
        void operator =(const tree_iterator& rhs) { iterator = rhs.iterator; }

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

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

        /*Description: pre-increment operator. Behaviour depends on wrappes iterator. */
        tree_iterator& operator ++()
        {
            iterator->operator ++();
            return *this;
        }

        /*Description: post-increment operator. Behaviour depends on wrappes iterator. */
        const tree_iterator operator ++(int junk)
        {
            return tree_iterator(iterator->operator ++(junk));
        }

        /*Description: pre-decrement operator. Behaviour depends on wrappes iterator. */
        tree_iterator& operator --()
        {
            iterator->operator --();
            return *this;
        }

        /*Description: post-decrement operator. Behaviour depends on wrappes iterator. */
        const tree_iterator operator --(int junk)
        {
            return tree_iterator(iterator->operator --(junk));
        }

    private:
        std::shared_ptr<_iterator_impl> iterator;
    };

//Node
private:
    class _Node{
        /* Description:
         * This class provides the Nodes and the methods of the Nodes. */

        /* ---------------------------------------------------------------------------------------------------------
         *
         * CAUTION: The following class descriptions contain the descriptions of internal class _Node.
         *          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:
         *
         *  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
         *
         *  std::shared_ptr<_Node> getPtr();         Returns a shared_ptr of this
         *
         *  node_iterator appendNode(const std::shared_ptr<_Node>& node);       Internal function to append a node to children of this
         *  node_iterator insertAfter(const std::shared_ptr<_Node>& node);      Internal function to append node to parent of this at position after this
         *  node_iterator insertPrevious(const std::shared_ptr<_Node>& node);   Internal function to append node to parent of this at position previous to this
         *
         * void remove();                                     Internal function to remove 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> Value = nullptr;             Pointer to the stored value of this node
         *
         *  Node* ParentNode = nullptr;                               Pointer to the parent node. If node is Root, it points to itself
         *  Node* PrevNode = nullptr;                                 Pointer to the previous siblings node
         *  Node* NextNode = nullptr;                                 Pointer to the next siblings node
         *  Node* FirstNode = nullptr;                                Pointer to the first child node. Is NULL if no children exist.
         *  Node* LastNode = nullptr;                                 Pointer to the last child node. Is NULL if no children exist.

         *  std::vector<std::shared_ptr<Node>> Children;              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
         *
         * ---------------------------------------------------------------------------------------------------------
        */
        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) : Value(value) {}

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

                T Value;
            };
    private:
        //Members
        std::unique_ptr<placeholder> Value;

        _Node* ParentNode = nullptr;
        _Node* PrevNode = nullptr;
        _Node* NextNode = nullptr;
        _Node* FirstNode = nullptr;
        _Node* LastNode = nullptr;

        std::vector<std::shared_ptr<_Node>> Children;

    public:
        //structors
        _Node();
        template<typename T> _Node(T value);
        ~_Node();

    public:
        //Public Methods

        /* 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_impl appendNode(const 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_impl insertAfter(const 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_impl insertPrevious(const std::shared_ptr<_Node>& node);

        /* Description: Remove this node
         * Parameters:  None
         * Return:      None    */
        void remove();

        /* 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    */
        void pushNewNode(const std::shared_ptr<_Node>& node);

        /* 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);
    }; //end class Node
//Member
private:
    std::shared_ptr<_Node> Root;
}; //end class tree

} // end namespace treeContainer

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

//Functions

//Find value in tree
template<typename T> treeContainer::tree::tree_iterator treeContainer::tree::find(const T& value)
{
    return find(tree_iterator(std::make_shared<_node_iterator_impl>(Root.get())),
                tree_iterator(std::make_shared<_node_iterator_impl>(Root.get())), value);
}

//Find values in children of passed node
template<typename T> treeContainer::tree::tree_iterator treeContainer::tree::find(const tree_iterator& start, const tree_iterator& end, const T& value)
{
    _node_iterator_impl ret(start);
    bool found = false;

    ++ret;

    while(!found && ret != end){
        if(ret.Node->getValueType() == typeid(T) && ret.Node->getValue<T>() == value) found = true;
        else ++ret;
    }
    if(!found) ret = Root.get();

    return tree_iterator(std::make_shared<_node_iterator_impl>(ret));
}

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

    if(parent.iterator->Node == Root.get()) ret = Root->appendNode(std::make_shared<_Node>(value));
    else ret = parent.iterator->Node->appendNode(std::make_shared<_Node>(value));

    return tree_iterator(std::make_shared<_node_iterator_impl>(ret));
}

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

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

//functions

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

//Returns the stored value of type T
template<typename T> T treeContainer::tree::_Node::getValue()
{
    return ((holder<T>*)Value.get())->Value;
}

//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(Value));
}

#endif // TREECONTAINER_H