---

nodevisitor.h

Go to the documentation of this file.

/***************************************************************************
*  @file    visitor.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 NODEVISITOR_H
#define NODEVISITOR_H

#include <vector>
//#include <algorithm>
#include "node.h"
#include "nodeiterator.h"
#include "nodeutil.h"
#include "nodeoutputstrategy.h"


namespace treecomp
{

                  
template<class _TContent>
class Node;
template<class _TContent>
class NormalNode;
template<class _TContent>
class RootNode;

template<class _TContent>
class OutputStrategy;
template<class _TContent>
class NullOutputStrategy;


// =======================
// === NodeVisitorBase ===
// =======================
/**
 * @interface NodeVisitorBase
 * @ingroup nodevisitor
 *
 * @brief Visitors are used to extend the Node classes without changing their implementation ('visitor pattern')
 * NodeVisitor is the base class of all visitors.
 * Visitors use an iterator to traverse the tree. So the result depends on the given iteration algorithm.
 * If set to non-recursive they only visit one node. The default value is true, so the visitor works
 * recursively.
 */
template<class _Node, class _NormalNode,    class _RootNode>
class NodeVisitorBase
{
public: 
    typedef NodeVisitorBase<_Node,_NormalNode,_RootNode> _Self;

    explicit NodeVisitorBase() {}
    
//  virtual _Self* construct() const = 0;
//  virtual _Self* clone() const = 0;
    virtual ~NodeVisitorBase(){}
    
    virtual void visitNormalNode(_NormalNode* node) = 0;
    virtual void visitRootNode(_RootNode* node) = 0;
};


// ===================
// === NodeVisitor ===
// ===================
/**
 * @interface NodeVisitor
 * @ingroup nodevisitor
 *
 * @brief Visitors are used to extend the Node classes without changing their implementation ('visitor pattern')
 * NodeVisitor is the base class of all visitors.
 * Visitors use an iterator to traverse the tree. So the result depends on the given iteration algorithm.
 * If set to non-recursive they only visit one node. The default value is true, so the visitor works
 * recursively
 */
template<class _TIter,
    class _Node,
    class _NormalNode,
    class _RootNode>
class NodeVisitor : public NodeVisitorBase<_Node, _NormalNode, _RootNode>
{
public:
    typedef NodeVisitor<_TIter,_Node,_NormalNode,_RootNode> _Self;
    typedef NodeVisitorBase<_Node,_NormalNode,_RootNode> _Base;
//  typedef _TIter iterator_type;

    explicit NodeVisitor()
        : _Base(), m_start(0), m_iter(new _TIter), m_recursive(true)
        {}
        
    /** no copying allowed, use clone() instead */
    explicit NodeVisitor(const _Self& nv)
        : _Base(), m_start(nv.m_start), m_iter(nv.m_iter->clone()), m_recursive(nv.m_recursive)
        {}
    
//  virtual _Self* construct() const {return new _Self(); }
//  virtual _Self* clone() const { return new _Self(*this); }
    virtual ~NodeVisitor();
    
    /** Start function. Derived implementations MUST call the init method!  */
    virtual void operator()(_TIter& iter) = 0;
    virtual void operator()(_Node* node) { _TIter iter(node); this->operator()(iter); } 
//  virtual void operator()(_Node& node) { _TIter iter(&node); this->operator()(iter); }
    virtual void visitNormalNode(_NormalNode* node) = 0;
    virtual void visitRootNode(_RootNode* node) = 0;
    /** 'True' the Visitor iterates over children too.
     *  'False' the Visitor only visits the start node */
    virtual void setRecursive(bool recursive) { m_recursive = recursive; }
    virtual bool isRecursive() const { return m_recursive; }

protected:
    /** The visit iteration, should be called by start */
    virtual void iterate(NodeVisitorBase<_Node,_NormalNode,_RootNode>* self);
//  virtual void init(NodeIterator<_TContent>* iter);
    virtual void init(_TIter& iter);
        
    _Node* m_start;
    //NodeIterator<_TContent>* m_iter;
    _TIter* m_iter; //!< local copy
    
private:
    /** no assignment allowed, use clone() instead */
    _Self& operator=(const _Self& nv){return *this;}
    
    bool m_recursive;
};



// =====================
// === OutputVisitor ===
// =====================

/**
 * @class OutputVisitor
 * @ingroup nodevisitor
 *
 * @brief OutputVisitor is used for output of the tree.
 * It uses an configurable OutputStrategy (see OutputStrategy),
 * 'DefaultOutputStrategy' if none is given.
 */
template<class _TContent, class _TIter>
class OutputVisitor
    : public NodeVisitor<typename _TIter::const_iterator,const Node<_TContent>,
        const NormalNode<_TContent>,const RootNode<_TContent> >
{
public:
    typedef OutputVisitor<_TContent,_TIter> _Self;
    typedef NodeVisitor<typename _TIter::const_iterator,
            const Node<_TContent>,const NormalNode<_TContent>,const RootNode<_TContent> >
        _Base;
    typedef OutputStrategy<_TContent> strategy_type;
//  typedef typename _TIter::const_iterator iterator_type;

//  OutputVisitor() : _Base(), m_outputStrategy(0) {}
    explicit OutputVisitor(strategy_type* os=0);
    virtual ~OutputVisitor() {}
    
    virtual _Self* construct() const { return new _Self; }
    virtual _Self* clone() const { return new _Self(*this); }

    virtual void operator()(const Node<_TContent>* node) { typename _TIter::const_iterator iter(node); this->operator()(iter); }
    /** start function */
    virtual void operator()(_TIter& iter);
    virtual void visitNormalNode(const NormalNode<_TContent>* node);
    virtual void visitRootNode(const RootNode<_TContent>* node);
    
    void setOutputStrategy(strategy_type* os);
    void setNullOutputStrategy();   
    virtual strategy_type* outputStrategy() { return m_outputStrategy; }

protected:
    explicit OutputVisitor(const OutputVisitor& ov)
        : _Base(ov), m_outputStrategy(ov.m_outputStrategy) {}
        
    strategy_type* m_outputStrategy;
    NullOutputStrategy<_TContent> m_nulloutputstrategy;
    
private:
    virtual OutputVisitor& operator=(const OutputVisitor&) {return *this;}
};



// ======================
// === CollectVisitor ===
// ======================
/**
 * @class CollectVisitor
 * @ingroup nodevisitor
 *
 * @brief This visitor collects all nodes into a vector which is provided through 'getList()'.
 */
template<class _TContent, class _TIter, class _TContainer=std::vector<Node<_TContent>*> >
class CollectVisitor
    : public NodeVisitor<_TIter, Node<_TContent>,   NormalNode<_TContent>, RootNode<_TContent> >
{
public:
    typedef CollectVisitor<_TContent,_TIter,_TContainer> _Self;
    typedef NodeVisitor<_TIter,Node<_TContent>, NormalNode<_TContent>, RootNode<_TContent> >
        _Base;
//  typedef _TIter iterator_type;

    explicit CollectVisitor() : _Base() {}
    virtual _Self* construct() const { return new _Self(); }
    virtual _Self* clone() const { return new _Self(*this); }

    virtual void operator()(_TIter& iter);
    virtual void visitNormalNode(NormalNode<_TContent>* node);
    virtual void visitRootNode(RootNode<_TContent>* node);

    virtual _TContainer getCollected() { return m_container; }

protected:
    explicit CollectVisitor(const CollectVisitor& cv)
        : _Base(cv) {}
    void addNode(Node<_TContent>* node);
    _TContainer m_container;
private:
    virtual CollectVisitor& operator=(const CollectVisitor&) {return *this;}
};



// ====================
// === DepthVisitor ===
// ====================
/**
 * @class DepthVisitor
 * @ingroup nodevisitor
 *
 * @brief This visitor measures the maximum depth of the tree, which is the distance from the given node
 * to the farest leave. The distance is provided through 'getDepth()'.
 */
template<class _TContent, class _TIter>
class DepthVisitor
    : public NodeVisitor<typename _TIter::const_iterator,const Node<_TContent>,
        const NormalNode<_TContent>,const RootNode<_TContent> >
{
public:
    typedef DepthVisitor<_TContent,_TIter> _Self;
    typedef NodeVisitor<typename _TIter::const_iterator,
            const Node<_TContent>,const NormalNode<_TContent>,const RootNode<_TContent> >
        _Base;
//  typedef typename _TIter::const_iterator iterator_type;

    explicit DepthVisitor()
        : _Base(), m_curDepth(0), m_maxDepth(0), m_curParent(0), m_isLeave(false)
        {}

    virtual _Self* construct() const { return new _Self(); }
    virtual _Self* clone() const { return new _Self(*this); }

    virtual void operator()(_TIter& iter);
    virtual void visitNormalNode(const NormalNode<_TContent>* node);
    virtual void visitRootNode(const RootNode<_TContent>* node);

    virtual int getDepth() { return m_maxDepth; }

protected:
    explicit DepthVisitor(const DepthVisitor& cv)
        : _Base(cv) {}
    void measure(const Node<_TContent>* node);
    int m_curDepth;
    int m_maxDepth;
    const Node<_TContent>* m_curParent;
    bool m_isLeave;
private:
    virtual DepthVisitor& operator=(const DepthVisitor&) {return *this;}
};


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

// ===================
// === Nodevisitor ===
// ===================
template<class _TIter, class _Node, class _NormalNode, class _RootNode>
void
NodeVisitor<_TIter,_Node,_NormalNode,_RootNode>::iterate(
    NodeVisitorBase<_Node,_NormalNode,_RootNode>* self)
{
    _Node* node=0;
    if (m_recursive && m_iter)
        while(!m_iter->isEnd())
        {
            node = &(m_iter->operator*());
            assert(node!=0);
            node->acceptVisitor(self);
//          node->acceptVisitor(this);
            m_iter->operator++();
        }
    else
    {
        assert(m_start!=0);
        m_start->acceptVisitor(self);
//      m_start->acceptVisitor(this);
    }
}

template<class _TIter, class _Node, class _NormalNode, class _RootNode>
//void NodeVisitor<_TContent>::init(NodeIterator<_TContent>* iter)
void
NodeVisitor<_TIter,_Node,_NormalNode,_RootNode>::init(_TIter& iter)
{

    if (m_iter)
    {
        delete m_iter;
        m_iter=0;
    }
    m_iter = new _TIter(iter);
    m_start = &(m_iter->operator*());
    assert(m_start!=0);
}

/**
 * Start the output process
 * @param node The Node to start with
 */
 /*
template<class _TContent, class _TIter, class _Node, class _NormalNode, class _RootNode>
void NodeVisitor<_TContent,_TIter>::start(_Node* node)
{
    _TIter iter(node);
    start(iter);
}

*/

template<class _TIter, class _Node, class _NormalNode, class _RootNode>
NodeVisitor<_TIter,_Node,_NormalNode,_RootNode>::~NodeVisitor<_TIter,_Node,_NormalNode,_RootNode>()
{
    if (m_iter)
        delete m_iter;
}




// =====================
// === OutputVisitor ===
// =====================
/**
 * Constructor
 * If no outputstrategy is given the visitor uses NullOutputStrategy
 * that writes to stdout.
 * @param os The OutputStrategy to use
 */
template<class _TContent, class _TIter>
OutputVisitor<_TContent,_TIter>::OutputVisitor(strategy_type* os)
    : _Base(), m_nulloutputstrategy(&cout)
{
    if (os == 0)
        m_outputStrategy = &m_nulloutputstrategy;
    else
        m_outputStrategy = os;
    assert(m_outputStrategy!=0);
}



/**
 * Start the output process
 * @param iter The NodeIterator that iterates over all nodes to visit
 */
template<class _TContent, class _TIter>
void OutputVisitor<_TContent,_TIter>::operator()(_TIter& iter)
{
    init(iter);
    assert(m_outputStrategy!=0);
    m_outputStrategy->writeHeader();
    iterate(this);
    m_outputStrategy->writeFooter();
}


/**
 * Take a NormalNode and output its content
 * @param node The NormalNode to visit
 */
template<class _TContent, class _TIter>
void OutputVisitor<_TContent,_TIter>::visitNormalNode(const NormalNode<_TContent>* node)
{
    assert(m_outputStrategy!=0);
    m_outputStrategy->writeNormalNode(node);
}

/**
 * Take a RootNode and output its content
 * @param node The RootNode to visit
 */
template<class _TContent, class _TIter>
void OutputVisitor<_TContent,_TIter>::visitRootNode(const RootNode<_TContent>* node)
{
    assert(m_outputStrategy!=0);
    m_outputStrategy->writeRootNode(node);
}

/**
 * Set the OutputStrategy for the node content output
 * @param os The OutputStrategy to use
 */
template<class _TContent, class _TIter>
void OutputVisitor<_TContent,_TIter>::setOutputStrategy(strategy_type* os)
{
    if (os)
        m_outputStrategy = os;
    else
        m_outputStrategy = &m_nulloutputstrategy;
    assert(m_outputStrategy!=0);
}

/**
 * Reset the OutputStrategy to a NullOutputStrategy
 */
template<class _TContent, class _TIter>
void OutputVisitor<_TContent,_TIter>::setNullOutputStrategy()
{

    setOutputStrategy(0);
    assert(m_outputStrategy->isNull()==true);
}

// ======================
// === CollectVisitor ===
// ======================


/**
 * Start the collection process
 * @param iter The NodeIterator that iterates over all nodes to visit
 */
template<class _TContent, class _TIter, class _TContainer>
void CollectVisitor<_TContent,_TIter,_TContainer>::operator()(_TIter& iter)
{
    init(iter);
    m_container.clear();
    iterate(this);
}

/**
 * Take a NormalNode and put it in the list
 * @param node The NormalNode to visit
 */
template<class _TContent, class _TIter, class _TContainer>
void CollectVisitor<_TContent,_TIter,_TContainer>::visitNormalNode(NormalNode<_TContent>* node)
{
    addNode(node);
}

/**
 * Take a RootNode and put its subtree in the list
 * @param node The RootNode to visit
 */
template<class _TContent, class _TIter, class _TContainer>
void CollectVisitor<_TContent,_TIter,_TContainer>::visitRootNode(RootNode<_TContent>* node)
{
    addNode(node);
}

/**
 * Take a Node and put it in the list
 * @param node The Node to add
 */
template<class _TContent, class _TIter, class _TContainer>
void CollectVisitor<_TContent,_TIter,_TContainer>::addNode(Node<_TContent>* node)
{
    m_container.push_back(node);
}



// ====================
// === DepthVisitor ===
// ====================


/**
 * Start the measurement process
 * @param iter The NodeIterator that iterates over all nodes to visit
 */
template<class _TContent, class _TIter>
//void DepthVisitor<_TContent,_TIter>::start(NodeIterator<_TContent>* iter)
void DepthVisitor<_TContent,_TIter>::operator()(_TIter& iter)
{
    init(iter);
    m_curDepth = 1;
    m_maxDepth = 1;
    m_isLeave = false;
    m_curParent = 0;

    iterate(this);
}

/**
 * Take a NormalNode and calculate depth
 * @param node The NormalNode to visit
 */
template<class _TContent, class _TIter>
void DepthVisitor<_TContent,_TIter>::visitNormalNode(const NormalNode<_TContent>* node)
{
    measure(node);
}

/**
 * Take a RootNode and calculate depth
 * @param node The RootNode to visit
 */
template<class _TContent, class _TIter>
void DepthVisitor<_TContent,_TIter>::visitRootNode(const RootNode<_TContent>* node)
{
    measure(node);
}

/**
 * Take a Node and calculate depth
 * @param node The Node
 */
template<class _TContent, class _TIter>
void DepthVisitor<_TContent,_TIter>::measure(const Node<_TContent>* node)
{
    if (node->getParent() != m_curParent)
    {
        // changed depth
        if (!m_isLeave)
        {
            // former node was no leave
            // so we descended one step
            ++m_curDepth;
        }
        else
        {
            // former node was leave
            // so we ascended one step
            --m_curDepth;
        }
        if (m_curDepth > m_maxDepth)
            m_maxDepth = m_curDepth;
        m_curParent = node->getParent();
    }
    if (node->getNumChildren())
        m_isLeave = false;
    else
        m_isLeave = true;
}

} // namespace treecomp

#endif //NODEVISITOR_H

---