---

node.h

Go to the documentation of this file.

/***************************************************************************
*  @file    node.h
*  @version 1.0
*  
*  @author  Ingo Herwig, TU Darmstadt, FG Regelsystemtheorie und Robotik
*  @author  Eva Brucherseifer, TU Darmstadt, FG Regelsystemtheorie und Robotik
*  @date    2001
* 
***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Library Public License as       *
 *   published by the Free Software Foundation; either version 2 of the    *
 *   License, or (at your option) any later version.                       *
 *                                                                         *
 ***************************************************************************/



#ifndef NODE_H
#define NODE_H

#include <list>
#include <vector>
#include <string>
#include <map>

#include <cassert>
#include <algorithm>
#include "nodevisitor.h"
#include "nodeiterator.h"


namespace treecomp
{


template<class _TContent>
class Node;

template<class _TContent>
class NormalNode;

template<class _TContent>
class RootNode;

/*
template<   class _Node,    class _NormalNode, class _RootNode  >
class NodeVisitorBase;

template<class _TContent, class _TIter>
class DepthVisitor;
*/

// ============
// === Node ===
// ============
/**
 * @interface Node
 * @ingroup node
 *
 * @brief This class provides the basic interface to the node-classes.
 *
 * Together with NormalNode and RootNode it implements the 'composite pattern'
 * in an extended way, which means that any node could be a leave.
 *
 * RootNodes are used as the root of a tree. Trees constructed in this way are recognized as a unit after insertion
 * into another tree.
 * NormalNodes are the basic parts of the tree.
 *
 * Applicationspecific content of the node is added by the template-parameter _TContent (which must have a public constructor,
 * destructor and copy-constructor).
 *
 * For copying trees use the function cloneTree(), which gives back a pointer to the copied tree.
 * The assignement operator is only the default version and should _never be used_. It only makes a copy of the data in the
 * copied class, but doesn't copy, what the pointer point to.
 * The Copy Contructor is made protected, so that it cannot be used.
 */
template<class _TContent>
class Node
{
public:
    // Node types
    typedef _TContent                   value_type;
    typedef value_type&             reference;
    typedef const value_type&       const_reference;
    typedef value_type*             pointer;
    typedef const value_type*       const_pointer;
    
    typedef NodeIterator<Node<value_type> > iterator;
    typedef NodeIterator<const Node<value_type> >    const_iterator;
    typedef AllNodeIterator<Node<value_type> >  all_iterator;   
    typedef AllNodeIterator<const Node<value_type> > const_all_iterator;    
    typedef PostOrderNodeIterator<Node<value_type> >    post_iterator;
    typedef PostOrderNodeIterator<const Node<value_type> > const_post_iterator;
    typedef VariableNodeIterator<Node<value_type> > var_iterator;   
    typedef VariableNodeIterator<const Node<value_type> > const_var_iterator;   
    typedef LeaveIterator<Node<value_type> > leave_iterator;    
    typedef LeaveIterator<const Node<value_type> > const_leave_iterator;    
    typedef size_t                              size_type;
    typedef ptrdiff_t                           difference_type;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
    
    friend class NormalNode<_TContent>;
    friend class RootNode<_TContent>;

    explicit Node();
    explicit Node(const Node<_TContent>& node);
    explicit Node(const _TContent& content);
    virtual ~Node();

    virtual Node* construct() const = 0;
    virtual Node* cloneTree() const = 0;
    virtual Node* cloneNode() const = 0;

    /** Get the parent of this node. */
    virtual Node<_TContent>* getParent() { return m_parent; }
    virtual const Node<_TContent>* getParent() const { return m_parent; }
    /** Get the enclosing (sub-)trees root. */
    virtual Node<_TContent>* getRoot() { return m_root; }
    virtual const Node<_TContent>* getRoot() const { return m_root; }
    /** Get the left neighbor (or sister) of this node. */
    virtual Node<_TContent>* getLeftSibling() { return m_left_sibling; }
    virtual const Node<_TContent>* getLeftSibling() const { return m_left_sibling; }
    /** Get the right neighbor (or sister) of this node. */
    virtual Node<_TContent>* getRightSibling() { return m_right_sibling; }
    virtual const Node<_TContent>* getRightSibling() const { return m_right_sibling; }
    /** Get a list of children of this node. */
    virtual const std::list<Node<_TContent>*>* getChildren() const { return &m_children; }
    /** Get a list of leaves of this node. The list differs from the list
     * obtained by 'getChildren()' only if the node is root of a (sub-)
     * tree (= RootNode). */
    virtual const std::list<Node*>* getLeaves() const { return &m_children; }
    /** Get the number of direct children of this node. */
    virtual size_type getNumChildren() const { return m_children.size(); }
    /** Get the number of descendants of this node. The number differs from the number
     * obtained by 'getNumChildren()' only if the node is root of a (sub-)
     * tree (= RootNode). */
    virtual size_type getNumDescendants() const { return m_children.size(); }
    /** Get the maximal depth of the tree. */
    virtual int getDepth() const;
    /** Get the name of the node. */
    virtual std::string getName() const { return m_name; }
    /** Return fixed state */
    virtual bool isFixed() const { return m_fixed; }

    /** Update the list of leaves of this node
     * Does nothing for NormalNodes */
    virtual void recalcLeaves() {}
    /** Make the node fixed. Protect from deleting.
     *  @parem b True/False */
    virtual void setFixed(bool b) { m_fixed = b; }
    /** Set the name of the node. */
    virtual void setName(std::string name) { m_name = name; }

    /** Get a STL conform iterator to traverse the tree structure
        * beginning with this node (nodes of subtrees n o t included). */
    virtual iterator begin() { return iterator(this); }
    virtual const_iterator begin() const { return const_iterator(this); }
    /** Get the 'past the end' iterator */
    virtual iterator end() { return iterator();}
    virtual const_iterator end() const { return const_iterator();}

    /** Get an STL conform iterator to traverse the tree structure
     * beginning with this node (nodes of subtrees included). */
    virtual all_iterator beginAll() { return this; }
    virtual const_all_iterator beginAll() const { return this; }
    /** don't have a glue why the compiler doesn't pick the right const function, so
       here is an explicit call to get the const iterator*/
    virtual const_all_iterator beginAllConst() const { return this; }
    /** Get the 'past the end' iterator */
    virtual all_iterator endAll() { return all_iterator(); }
    virtual const_all_iterator endAll() const { return const_all_iterator(); }

    virtual bool addChildFront(Node* node);
    virtual bool addChildBack(Node* node);
    virtual bool addChild(Node* node);
    virtual bool addChild(Node* node, unsigned int index);
    virtual bool addChild(Node* node, typename std::list<Node*>::iterator& iter);
    virtual std::list<Node*> deleteChild(Node* node);
    virtual bool cutChild(Node* node);
    
    virtual void acceptVisitor(
        NodeVisitorBase<Node<_TContent>,NormalNode<_TContent>,RootNode<_TContent> >*
        visitor) = 0;
    virtual void acceptVisitor(
        NodeVisitorBase<const Node<_TContent>,const NormalNode<_TContent>,const RootNode<_TContent> >*
        visitor) const = 0;

    virtual void reduce();

    virtual pointer getContent() { return m_content; }
    virtual const_pointer getContent() const { return m_content; }
    
    /** Return true is the node is a RootNode
     *  This method is nescessary to distinguisch normal and super nodes inside node */
    virtual bool isRootNode() const { return false; }

protected:  
    typedef std::map<const Node<_TContent>*, Node<_TContent>*> OldNewMap;

    virtual Node* copy(OldNewMap& nodeMap) const = 0;
    virtual void linkSiblings();
    virtual void setParent(Node* node);
    virtual void deleteParent();
    virtual void disconnectChildren();
    /** Set true to make the RootNode a unit in the enclosing tree
     * Does nothing for NormalNodes */
    virtual void setProtected(bool) {}
    /** Returns protection state */
    virtual bool isProtected() const { return m_protected; }
    virtual bool isInner() const;

    //! tree layout
    Node* m_parent;
    //! tree layout
    Node* m_root;
    //! tree layout
    Node* m_right_sibling;
    //! tree layout
    Node* m_left_sibling;
    //! tree layout
    std::list<Node<_TContent>*> m_children;

    //! node configuration
    _TContent* m_content;
    //! node configuration
    bool m_protected;   
    //! node configuration : if m_fixed is true, connection to parent node cannot be removed
    bool m_fixed;
    //! node configuration
    std::string m_name;

    /** this iterator points after every delete action
     * to the child in front of which was deleted
     * so its possible to use insert to repair  */
    typename std::list<Node*>::iterator m_repairIter;
};



// ==================
// === NormalNode ===
// ==================
/**
 * @class NormalNode
 * @ingroup node
 *
 * This class is the basic part of the tree (see Node class).
 */
template<class _TContent>
class NormalNode : public Node<_TContent>
{
public:
    // Node types
/*
    typedef NodeIterator<_TContent>     iterator;
    typedef const NodeIterator<_TContent>       const_iterator;
    typedef AllNodeIterator<_TContent>  alliterator;    
*/
    typedef size_t                              size_type;
    typedef ptrdiff_t                           difference_type;
    typedef Node<_TContent>&                reference;
    typedef const Node<_TContent>&      const_reference;
    typedef _TContent                           value_type;
    typedef Node<_TContent>*                pointer;
    typedef const Node<_TContent>*      const_pointer;
//  typedef std::reverse_iterator<iterator> reverse_iterator;
//  typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
    
//  NormalNode();
    virtual ~NormalNode() {}
        
    /** virtual default constructor */
    virtual NormalNode<_TContent>* construct() const { return new NormalNode<_TContent>;}
    virtual NormalNode<_TContent>* cloneTree() const;
    virtual NormalNode<_TContent>* cloneNode() const;

    virtual void acceptVisitor(
        NodeVisitorBase<Node<_TContent>,NormalNode<_TContent>,RootNode<_TContent> >*
        visitor);
    virtual void acceptVisitor(
        NodeVisitorBase<const Node<_TContent>,const NormalNode<_TContent>,const RootNode<_TContent> >*
        visitor) const;

protected:  
    typedef std::map<const Node<_TContent>*, Node<_TContent>*> OldNewMap;
    virtual Node<_TContent>* copy(OldNewMap& nodeMap) const;
    
private:
    /** use cloneTree() or cloneNode() instead */
    //NormalNode(const NormalNode& node) {}
    //NormalNode& operator=(const NormalNode& node) {return *this;}
};


// =================
// === RootNode ===
// =================
/**
 * @class RootNode
 * @ingroup node
 *
 * This class is the root class of the tree (see Node class).
 */
template<class _TContent>
class RootNode : public Node<_TContent>
{
public:
    // Node types
  //typedef NodeIterator<_Tp,_Tp&,_Tp*>             iterator;
  //typedef NodeIterator<_Tp,const _Tp&,const _Tp*> const_iterator;
/*
    typedef NodeIterator<_TContent>     iterator;
    typedef AllNodeIterator<_TContent>  alliterator;    
*/
    typedef size_t                              size_type;
    typedef ptrdiff_t                           difference_type;
    typedef Node<_TContent>&                reference;
    typedef const Node<_TContent>&      const_reference;
    typedef _TContent                           value_type;
    typedef Node<_TContent>*                pointer;
    typedef const Node<_TContent>*      const_pointer;
//  typedef std::reverse_iterator<iterator> reverse_iterator;
//  typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
    
    RootNode();
    /** virtual default constructor */
    virtual RootNode<_TContent>* construct() const { return new RootNode<_TContent>;}
    virtual RootNode<_TContent>* cloneTree() const;
    virtual RootNode<_TContent>* cloneNode() const;
    //virtual ~RootNode() {}

    virtual const std::list<Node<_TContent>*>* getLeaves() const { return &m_leaves; }
    virtual size_type getNumDescendants() const;
    virtual void recalcLeaves();
    virtual void acceptVisitor(
        NodeVisitorBase<Node<_TContent>,NormalNode<_TContent>,RootNode<_TContent> >*
        visitor);
    virtual void acceptVisitor(
        NodeVisitorBase<const Node<_TContent>,const NormalNode<_TContent>,const RootNode<_TContent> >*
        visitor) const;
    virtual bool isRootNode() const { return true; }

protected:
    typedef std::map<const Node<_TContent>*, Node<_TContent>*> OldNewMap;
    virtual Node<_TContent>* copy(OldNewMap& nodeMap) const;

    virtual void deleteParent();
    virtual void setProtected(bool b);

    std::list<Node<_TContent>*> m_leaves;
private:
    /** use cloneTree() or cloneNode() instead */
    //RootNode(const RootNode& node) {}
    //RootNode& operator=(const RootNode& node) {return *this;} 
};

// =================== Template definition =================================

// ============
// === Node ===
// ============


template<class _TContent>
Node<_TContent>::Node()
    :   m_parent(0), m_root(0),
        m_right_sibling(0), m_left_sibling(0),
        m_content(0),
        m_protected(false), m_fixed(false),
        m_name("no name"), m_repairIter(0)
{
    m_content = new _TContent();
}   

template<class _TContent>
Node<_TContent>::Node(const _TContent& content)
    :   m_parent(0), m_root(0),
        m_right_sibling(0), m_left_sibling(0),
        m_content(0),
        m_protected(false), m_fixed(false),
        m_name("no name"), m_repairIter(0)
{
    m_content = new _TContent(content);
}

/**
  * Copy Constructor.
  * only content is a real copy. For parent, root and children only the
  * pointer is copied. For a real copy use cloneTree()
  */
template<class _TContent>
Node<_TContent>::Node(const Node<_TContent>& node)
    :   m_parent(node.m_parent), m_root(node.m_root),
        m_right_sibling(node.m_right_sibling), m_left_sibling(node.m_left_sibling),
        m_children(node.m_children),
        m_content(0),
        m_protected(node.m_protected), m_fixed(node.m_fixed),
        m_name(node.m_name,0,std::string::npos),
        m_repairIter(node.m_repairIter)
{
    m_content = new _TContent(*node.m_content);
}



/**
 * Destructor. Works recursivly.
 */
template<class _TContent>
Node<_TContent>::~Node()
{
    delete m_content;

    typename std::list<Node*>::iterator nlIter;
    for(nlIter = m_children.begin(); nlIter != m_children.end(); ++nlIter)
        if (*nlIter)
            delete (*nlIter);
}


/** Get the maximal depth of the tree. */
template<class _TContent>
int Node<_TContent>::getDepth() const
{
    const_all_iterator anIter(this);
    DepthVisitor<_TContent, const_all_iterator > depthvisitor;
    depthvisitor( anIter );
    return depthvisitor.getDepth();
}


/**
 * Add a pointer to a child to the node (insert in front)
 * @param node The node to add
 */
template<class _TContent>
bool Node<_TContent>::addChildFront(Node* node)
{
    assert(node != 0);
    // add is only possible if 'this' is not inner node of a protected tree
    if (isInner())
        return false;

    node->m_left_sibling = 0;
    if (m_children.size()==0)
        node->m_right_sibling = 0;
    else
    {
//      node->m_left_sibling = m_children.front()->m_left_sibling;
        node->m_right_sibling = m_children.front();
//      node->m_left_sibling->right_sibling = node;
        node->m_right_sibling->m_left_sibling = node;
    }


    m_children.push_front(node);
//  if (m_children.size()==1)
//      node->recalcSiblings();
    node->setProtected(true);
    node->setParent(this);
    node->recalcLeaves();
    return true;
}

/**
 * Add a pointer to a child node to the node (add to back)
 * @param node The node to add
 */
template<class _TContent>
bool Node<_TContent>::addChildBack(Node* node)
{
    assert(node != 0);
    // add is only possible if 'this' is not inner node of a protected tree
    if (isInner())
        return false;

    if (m_children.size()==0)
        node->m_left_sibling = 0;
    else
    {
        node->m_left_sibling = m_children.back();
//      node->m_right_sibling = m_children.back()->m_right_sibling;
        node->m_left_sibling->m_right_sibling = node;
//      node->m_right_sibling->m_left_sibling = node;
    }
    node->m_right_sibling = 0;

    m_children.push_back(node);

//  if (m_children.size()==1)
//      node->recalcSiblings();
    node->setProtected(true);
    node->setParent(this);
    node->recalcLeaves();
    return true;
}

/**
 * Add a pointer to a child node to the node (insert it where the last one was deleted)
 * @param node The node to add
 */
template<class _TContent>
bool Node<_TContent>::addChild(Node* node)
{
    assert(node != 0);
    // add is only possible if 'this' is not inner node of a protected tree
    if (isInner())
        return false;
    if (m_repairIter==0 )
        return addChildBack(node);

    if (!addChild(node,m_repairIter))
        return false;
    m_repairIter=0;
    return true;
}

/**
 * Add a pointer to a child to the node (insert it at position index)
 + index 0: push_front
 + index > number of children: push_back
 * @param node The node to add
 * @param index The position where to add, the child at that position is moved to the back
 */
template<class _TContent>
bool Node<_TContent>::addChild(Node* node, unsigned int index)
{
    assert(node != 0);
    // add is only possible if 'this' is not inner node of a protected tree
    if (isInner())
        return false;
    if (index >= m_children.size())
        return addChildBack(node);
    if (index == 0)
        return addChildFront(node);

    typename std::list<Node<_TContent>*>::iterator nlIter = m_children.begin();
    unsigned int i;
    for (i=0 ; i<index; ++i)
        nlIter++;
    return addChild(node,nlIter);
}

/**
 * Add a child to the node (insert it before the position the iterator points to)
 * @param node The node to add
 * @param iter The iterator that gives the position
 */
template<class _TContent>
bool Node<_TContent>::addChild(Node* node, typename std::list<Node*>::iterator& iter)
{
    assert(node != 0);
    // add is only possible if 'this' is not inner node of a protected tree
    if (isInner())
        return false;

    if (m_children.size()==0 || iter==m_children.begin())
        return addChildFront(node);
    if (iter==m_children.end())
        return addChildBack(node);

    node->m_left_sibling = *iter;
    node->m_right_sibling = (*iter)->m_right_sibling;
    node->m_left_sibling->m_right_sibling = node;
    node->m_right_sibling->m_left_sibling = node;
    node->setProtected(true);
    node->setParent(this);

    m_children.insert(iter, node);
    node->recalcLeaves();
    return true;
}

/**
 * Check if the node is inner node of a protected tree.
 * Returns 'True' if yes, 'False' if not.
 */
template<class _TContent>
bool Node<_TContent>::isInner() const
{
    if (m_root)
    {
        // 'this' is already part of a tree
        const std::list<Node<_TContent>*>* leaves = m_root->getLeaves();
        bool isInLeaves = std::find( leaves->begin(),leaves->end(),this ) != leaves->end();
        if (m_root->isProtected() && !isInLeaves )
            return true;
    }
    return false;
}

/**
 * Delete a child from the node
 * Returns a list of the children of the deleted node.
 * (the list is empty if node is fixed and therefore not deleted, or if the node was a leave)
 * @param node The node to delete
 */
template<class _TContent>
std::list<Node<_TContent>*> Node<_TContent>::deleteChild(Node* node)
{
    assert(node != 0);

    std::list<Node<_TContent>*> nodechildren;
    if (cutChild(node))
    {
        // get the node's children to return them
        nodechildren = node->m_children;
        typename std::list<Node<_TContent>*>::const_iterator nlIter;
        if (node->isRootNode())
        {
            // node is RootNode
            // -> nodechildren are the leaves children
            const std::list<Node<_TContent>*> leaves = *(node->getLeaves());
            nodechildren.clear();
            for (nlIter = leaves.begin(); nlIter != leaves.end(); ++nlIter)
                nodechildren.merge((*nlIter)->m_children);
        }
        // disconnect nodechildren from node
        for (nlIter = nodechildren.begin(); nlIter != nodechildren.end(); ++nlIter)
            (*nlIter)->deleteParent();
        node->disconnectChildren();
    }
    return nodechildren;
}

/**
 * Delete a child from the node
 * Doesn't delete the child.
 * @param node The node to delete
 */
template<class _TContent>
bool Node<_TContent>::cutChild(Node* node)
{
    assert(node != 0);

    if (!node->isFixed() && !m_children.empty())
    {
        // set repair iterator to the next child after node
        m_repairIter = std::find( m_children.begin(),m_children.end(),node );
        ++m_repairIter;
        m_children.remove(node);
        node->deleteParent();
        if (node->m_left_sibling)
            node->m_left_sibling->m_right_sibling = node->m_right_sibling;
        if (node->m_right_sibling)
            node->m_right_sibling->m_left_sibling = node->m_left_sibling;
        node->m_left_sibling=0;
        node->m_right_sibling=0;
        return true;
    }
    return false;
}



/**
 * Set the nodes parent.
 * This method is called if the node is added as
 * child.
 * @param node The node to add as parent
 */
template<class _TContent>
void Node<_TContent>::setParent(Node* node)
{
    if (node==0)
    {
        deleteParent();
        return;
    }
    m_parent = node;

    if (node != 0)
    {
        // set root to the next root that's not protected
        Node* root = node->getRoot();
        if (root)
        {
            while (root->isProtected())
                root = root->getRoot();
            m_root = root;
            // if 'this' is a normalNode then all of its children get the same root
            if (!isRootNode())
                for (iterator nIter = begin(); nIter != end(); ++nIter)
                    (*nIter).m_root = root;
        }
        else
            m_root = node;
    }
}

/**
 * Delete the nodes parent.
 * This method is called if the node as child is removed.
 */
template<class _TContent>
void Node<_TContent>::deleteParent()
{
    m_parent = 0;
    // set root value to default
    if (isRootNode())
        m_root = this;
    else
        m_root = 0;
}

/**
 * Delete references to the nodes children.
 * This method is called if the node as child is removed.
 */
template<class _TContent>
void Node<_TContent>::disconnectChildren()
{
    m_children.clear();
}

/**
 * Reduce connected fixed parts of the tree to RootNodes
 */
template<class _TContent>
void Node<_TContent>::reduce()
{}


/**
 * Sets the sibling links of node's children right
 */
template<class _TContent>
void Node<_TContent>::linkSiblings()
{
    Node<_TContent>* before;
    Node<_TContent>* after;
    typename std::list<Node<_TContent>*>::const_iterator nlIter,afterIter;
    nlIter = m_children.begin();
    nlIter++;
    nlIter++;
    before = 0;
    after = *nlIter;
    afterIter = nlIter;

    for (nlIter=m_children.begin(); nlIter!=m_children.end(); nlIter++,afterIter++)
    {
        (*nlIter)->m_left_sibling = before;
        (*nlIter)->m_left_sibling = after;      
        before = *nlIter;
        if (afterIter!=m_children.end())
            after = *afterIter;
        else
            after = 0;
    }
}



// ==================
// === NormalNode ===
// ==================


/**
* Simulated Copy Constructor
* All children are duplicated, pointers to root and parent are preserved
*/
template<class _TContent>
NormalNode<_TContent>* NormalNode<_TContent>::cloneTree() const
{
    NormalNode<_TContent>* newNode = new NormalNode<_TContent>(*this);
    newNode->m_children.clear();

    // nodeMap holds the relation between new nodes and old ones
    // so by using nodeMap[nodeX] you get the newNode equivalent to nodeX
    OldNewMap nodeMap;
    nodeMap.insert( typename OldNewMap::value_type(this, newNode) );

    // duplicate children
    typename std::list<Node<_TContent>*>::const_iterator nlIter;
    for (nlIter = m_children.begin(); nlIter != m_children.end(); ++nlIter)
        newNode->m_children.push_back( (*nlIter)->copy(nodeMap) );
    newNode->linkSiblings();
    return newNode;
}

/**
* Simulated Copy Constructor for the Node,
* pointer to root, parent and children are preserved, but the children
* are not duplicated
*/
template<class _TContent>
NormalNode<_TContent>* NormalNode<_TContent>::cloneNode() const
{
    NormalNode<_TContent>* newNode = new NormalNode<_TContent>(*this);
//  newNode->m_content = new _TContent(*m_content);
    return newNode;
}


/**
 * Copy Node and its children recursively (is used by cloneTree)
 * @param nodeMap This map holds old-new node pairs of the ancestors of this
 */
template<class _TContent>
Node<_TContent>* NormalNode<_TContent>::copy(OldNewMap& nodeMap) const
{
    NormalNode<_TContent>* newNode = new NormalNode<_TContent>(*this);
    newNode->m_root = nodeMap[m_root];
    newNode->m_parent = nodeMap[m_parent];
    newNode->m_children.clear();
    
    nodeMap.insert( typename OldNewMap::value_type(this, newNode) );

    // duplicate children
    typename std::list<Node<_TContent>*>::const_iterator nlIter;
    for (nlIter = m_children.begin(); nlIter != m_children.end(); ++nlIter)
        newNode->m_children.push_back( (*nlIter)->copy(nodeMap) );
    newNode->linkSiblings();
    return newNode;
}

/**
 * Accept a visitor. Calls the visitors visitNormalNode
 * method with this node.
 * @param visitor The visitor to visit
 */
template<class _TContent>
void
NormalNode<_TContent>::acceptVisitor(
    NodeVisitorBase<Node<_TContent>,NormalNode<_TContent>,RootNode<_TContent> >*
    visitor)
{
    visitor->visitNormalNode(this);
}

/**
 * Accept a const visitor. Calls the visitors visitNormalNode
 * method with this node.
 * @param visitor The visitor to visit
 */
template<class _TContent>
void
NormalNode<_TContent>::acceptVisitor(
    NodeVisitorBase<const Node<_TContent>,const NormalNode<_TContent>,const RootNode<_TContent> >*
    visitor) const
{
    visitor->visitNormalNode(this);
}



// =================
// === RootNode ===
// =================
/**
 * Constructor
 */
template<class _TContent>
RootNode<_TContent>::RootNode()
    : Node<_TContent>()
{
    m_root = this;
}

/**
* Simulated Copy Constructor for the tree.
* All children are duplicated, pointers to root and parent are preserved
*/
template<class _TContent>
RootNode<_TContent>* RootNode<_TContent>::cloneTree() const
{
    RootNode<_TContent>* newNode = new RootNode<_TContent>(*this);
    newNode->m_root = newNode;
    newNode->m_children.clear();

    // nodeMap holds the relation between new nodes and old ones
    // so by using nodeMap[nodeX] you get the newNode equivalent to nodeX
    OldNewMap nodeMap;
    nodeMap.insert( typename OldNewMap::value_type(this, newNode) );

    // duplicate children
    typename std::list<Node<_TContent>*>::const_iterator nlIter;
    for (nlIter = m_children.begin(); nlIter != m_children.end(); ++nlIter)
        newNode->m_children.push_back( (*nlIter)->copy(nodeMap) );
    newNode->linkSiblings();
    return newNode;
}

/**
* Simulated Copy Constructor for the Node,
* pointer to root, parent and children are preserved, but the children
* are not duplicated
*/
template<class _TContent>
RootNode<_TContent>* RootNode<_TContent>::cloneNode() const
{
    RootNode<_TContent>* newNode = new RootNode<_TContent>(*this);
    newNode->m_content = new _TContent(*m_content);
    return newNode;
}


/**
 * Copy Node and its children recursively (is used by cloneTree)
 * @param nodeMap This map holds old-new node pairs of the ancestors of this
 */
template<class _TContent>
Node<_TContent>* RootNode<_TContent>::copy(OldNewMap& nodeMap) const
{
    RootNode<_TContent>* newNode = new RootNode<_TContent>(*this);
    newNode->m_root = nodeMap[m_root];
    newNode->m_parent = nodeMap[m_parent];
    newNode->m_children.clear();
    
    nodeMap.insert( typename OldNewMap::value_type(this, newNode) );

    // duplicate children
    typename std::list<Node<_TContent>*>::const_iterator nlIter;
    for (nlIter = m_children.begin(); nlIter != m_children.end(); ++nlIter)
        newNode->m_children.push_back( (*nlIter)->copy(nodeMap) );
    newNode->linkSiblings();
    return newNode;
}

/**
 * Accept a visitor. Calls the visitors visitRootNode
 * method with this node.
 * @param visitor Visitor to visit
 */
template<class _TContent>
void
RootNode<_TContent>::acceptVisitor(
    NodeVisitorBase<Node<_TContent>,NormalNode<_TContent>,RootNode<_TContent> >*
    visitor)
{
    visitor->visitRootNode(this);
}

/**
 * Accept a const visitor. Calls the visitors visitRootNode
 * method with this node.
 * @param visitor Visitor to visit
 */
template<class _TContent>
void
RootNode<_TContent>::acceptVisitor(
    NodeVisitorBase<const Node<_TContent>,const NormalNode<_TContent>,const RootNode<_TContent> >*
    visitor) const
{
    visitor->visitRootNode(this);
}


/**
 * Get the number of descendants of this node.
 */
template<class _TContent>
size_t RootNode<_TContent>::getNumDescendants() const
{
    int count = 0;
    typename Node<_TContent>::const_iterator nIter(this);
    for (; !nIter.isEnd(); ++nIter)
        ++count;
    return count-1;
}

/**
 * Update the list of leaves of this node.
 * Call this function after building a subtree that should later
 * be recognized as such.
 * Is automatically called if the node is added to another
 */
template<class _TContent>
void RootNode<_TContent>::recalcLeaves()
{
    m_leaves.clear();
    typename Node<_TContent>::leave_iterator lIter(this);
    for (; !lIter.isEnd(); ++lIter)
        m_leaves.push_back(lIter());
}

/**
 * Make the RootNode a unit in the enclosing tree
 * Is automatically called with parameter 'true' if the node is added to another
 */
template<class _TContent>
void RootNode<_TContent>::setProtected(bool b)
{
    m_protected = b;
}

/**
 * Delete the nodes parent.
 * This method is called if the node as child is removed.
 */
template<class _TContent>
void RootNode<_TContent>::deleteParent()
{
    m_parent = 0;
    m_root = this;
}


} // namespace treecomp

#endif //NODE_H

---