---

nodetraversal.h

Go to the documentation of this file.

/***************************************************************************
    @file       nodetraversal.h  -  description
                         -------------------
    @date       Fri Feb 15 2002
    copyright            : (C) 2002 by Eva Brucherseifer
    email                : eva@rt.e-technik.tu-darmstadt.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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 NODETRAVERSAL_H
#define NODETRAVERSAL_H

#include <vector>
#include "node.h"

namespace treecomp
{

/**
  * @interface NodeTraversal
  * @author Eva Brucherseifer
  * @ingroup nodetraversal
  *
  * @brief Base class for Traversal classes, that walks through a tree
  * and returns a container with all visited nodes.
  *
  * @param _Node: nodes type that are traversed
  * @param _Container: container type that is used to collect the nodes. Default is vector<_Node*>.
  * The container class must support the function push_back(node) and must be assignable.
  *
  * \par Usage:
    \code
    vector<Node<string> > traversal = PreNodeTraversal()(pointer_to_tree);
    \endcode
    or
    \code
    PreNodeTraversal pretraversal;
    vector<Node<string> > nodevector = pretraversal(pointer_to_tree);
    \endcode
  *
  * To create a new traversal type, reimplement the protected walk() method.
  */
template<class _Node, class _Container=std::vector<_Node*> >
class NodeTraversal : public NonCopyable
{
public: 
    virtual ~NodeTraversal(){}
    /** start function */
    _Container& operator()(_Node*);
//  const _Container getTraversal() const {m_traversal;}
    
protected:
    virtual void walk(_Node*)=0;
    
    _Container m_traversal;
};


/**
  * @class IterNodeTraversal
  * @ingroup nodetraversal
  * @brief Produces a traversal using the given Iterator.
  *
  * @note For pre and postorder iterators the
  * corresponding traversal classes are more
  * specialised and efficient
  * @author Eva Brucherseifer
  */
template<class _Node, class _TIterator, class _Container=std::vector<_Node*> >
class IterNodeTraversal : public NodeTraversal<_Node,_Container>
{
protected:
    virtual void walk(_Node*);
};




/**
  * @class PreOrderNodeTraversal
  * @author Eva Brucherseifer
  * @ingroup nodetraversal
  *
  * @brief Produces a traversal in preorder.
  * Visits node first and descends then recursively.
  */
template<class _Node, class _Container=std::vector<_Node*> >
class PreOrderNodeTraversal : public NodeTraversal<_Node,_Container>
{
protected:
    virtual void walk(_Node*);
};


/**
  * @class PostOrderNodeTraversal
  * @author Eva Brucherseifer
  * @ingroup nodetraversal
  *
  * @brief Produces a traversal in postorder.
  * Descends first recursively and visits node then.
  */
template<class _Node, class _Container=std::vector<_Node*> >
class PostOrderNodeTraversal : public NodeTraversal<_Node,_Container>
{
protected:
    virtual void walk(_Node*);
};


/*
class MultipleOrderNodeTraversal : public NodeTraversal
{
};
*/


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

// =====================
// === NodeTraversal ===
// =====================

template<class _Node, class _Container>
_Container& NodeTraversal<_Node,_Container>::operator()(_Node* startnode)
{
    m_traversal.clear();    
    walk(startnode);
    return m_traversal;
}

// ==============================
// === IterNodeTraversal ===
// ==============================

template<class _Node, class _TIterator, class _Container>
void IterNodeTraversal<_Node,_TIterator,_Container>::walk(_Node* node)
{
    assert(node!=0);
    _TIterator niter;
    niter.setStart(node);

    while(!niter.isEnd())
    {
        m_traversal.push_back(niter());
        ++niter;
    }
}

// ==============================
// === PostOrderNodeTraversal ===
// ==============================

template<class _Node, class _Container>
void PostOrderNodeTraversal<_Node,_Container>::walk(_Node* node)
{
    assert(node!=0);
    typename std::list<typename NodeTraits<_Node>::_NonConstNode*>::const_iterator nlIter;
    for (nlIter = node->getChildren()->begin(); nlIter != node->getChildren()->end(); ++nlIter)
        walk(*nlIter);
    m_traversal.push_back(node);    
}


// ==============================
// === PostOrderNodeTraversal ===
// ==============================

template<class _Node, class _Container>
void PreOrderNodeTraversal<_Node,_Container>::walk(_Node* node)
{
    assert(node!=0);
    m_traversal.push_back(node);    
    typename std::list<typename NodeTraits<_Node>::_NonConstNode*>::const_iterator nlIter;
    for (nlIter = node->getChildren()->begin(); nlIter != node->getChildren()->end(); ++nlIter)
        walk(*nlIter);
}


} // namespace treecomp

#endif

---