---

nodeiterator.h

Go to the documentation of this file.

/***************************************************************************
*  @file    nodeiterator.h
*  @version 1.1
*
*  @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 NODEITERATOR_H
#define NODEITERATOR_H

//#include <stack>
#include <set>
#include <list>
//#include <iterator>
#include "node.h"
#include "nodeutil.h"

namespace treecomp
{

/*
template<class _TContent>
class Node;
*/

/*
#if defined(__GNUC__) && defined(__STL_NO_NAMESPACES)
    #define BaseIterator forward_iterator<Node<_TContent>, ptrdiff_t >
#else
    #define BaseIterator iterator<forward_iterator_tag, Node<_TContent> >
#endif
*/

/**
 * @interface NodeIterator
 * @ingroup nodeiterator
 *
 * @brief This iterator iterates in preorder over all nodes that belong to
 * a given node (have the same root).
 *
 * That means, it visits first a root
 * node and then its children.
 * It doesn't iterate
 * over subtree nodes. The default constructor makes a
 * 'past the end NodeIterator'.
 * It is the base class of all iterators and inherits from forward_iterator.
 * Template-parameter _TContent: see Node class.
 */
template<class _Node, class _Ref=_Node&, class _Ptr=_Node*>
class NodeIterator //: public BaseIterator
{
public:
    typedef typename NodeTraits<_Node>::_NonConstNode _NonConstNode;

    typedef NodeIterator<_Node> iterator;
    typedef NodeIterator<const _Node > const_iterator;
    typedef NodeIterator<_Node, _Ref,_Ptr> _Self;

//  typedef bidirectional_iterator_tag iterator_category; // not yet supported
    typedef std::forward_iterator_tag iterator_category;
    typedef _Node value_type;
    typedef _Ptr pointer;
    typedef _Ref reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
    /** The default constructor makes a 'past the end NodeIterator'. */
    NodeIterator() : m_currentNode(0), m_root(0), m_end(true) {}
    //NodeIterator(const _Self& it) {m_currentNode=it.m_currentNode; m_root=it.m_root;m_end=it.m_end;}
    //NodeIterator(const const_iterator& it) {m_currentNode=it.m_currentNode; m_root=it.m_root;}

    /** Construct a NodeIterator beginning at the given Node.
      * @param start The Node to start at */
    NodeIterator(_Node* start) { setStart(start); }
    virtual _Self* construct() const { return new _Self(); }
    virtual _Self* clone(_Node* start=0) const ;
    virtual ~NodeIterator() {}

    /**Dereference operator */
    virtual reference operator*() const { return *m_currentNode; }
    /**Dereference operator */
    virtual pointer operator->() const { return m_currentNode; }
    /** use like this: @code nodepointer=iter(); @endcode */
    virtual pointer operator()() const { return m_currentNode; }
    virtual bool operator==(const _Self& rhs);
    virtual bool operator!=(const _Self& rhs);
    virtual _Self operator++(int);
    virtual _Self& operator++();
    const bool& isEnd() const { return m_end; }

    virtual void setStart(_Node* start);

protected:
    _Node* m_currentNode;
    _Node* m_root;
    std::list<_Node*> m_nodeList;
    std::set<_Node*> m_seenNodeSet;

    void setEnd(bool end=true) { m_end=end; }
    void addToNodeList(const std::list<_NonConstNode*>* values);
    
private:
    bool m_end;
};

/**
 * @class PostOrderNodeIterator
 * @ingroup nodeiterator
 *
 * @brief This iterator iterates over all nodes in post order that belong to
 * a given node (have the same root) and are not fixed.
 *
 * \par It doesn't iterate over subtree nodes.
 * The default constructor makes a 'past the end VariableNodeIterator'.
 *
 * \note For pre and postorder iterators the
 * corresponding traversal classes are more
 * specialised and efficient.
 */
template<class _Node, class _Ref=_Node&, class _Ptr=_Node*>
class PostOrderNodeIterator : public NodeIterator<_Node,_Ref,_Ptr>
{
public:
    typedef PostOrderNodeIterator<_Node> iterator;
    typedef PostOrderNodeIterator<const _Node > const_iterator;
    typedef PostOrderNodeIterator<_Node, _Ref,_Ptr> _Self;
    typedef NodeIterator<_Node,_Ref,_Ptr> _Base;
    typedef typename NodeTraits<_Node>::_NonConstNode _NonConstNode;

    PostOrderNodeIterator() : _Base() {}
    /** Construct a PostOrderNodeIterator beginning at the given Node.
      * @param start The Node to start at */
    PostOrderNodeIterator(_Node* start) : _Base() { setStart(start); }
    virtual _Self* construct() const { return new _Self(); }
    virtual _Self* clone(_Node* start=0) const ;
    virtual ~PostOrderNodeIterator() {}

    virtual bool operator==(const _Self& rhs);
    virtual bool operator!=(const _Self& rhs);
    virtual _Self& operator++();
    
    virtual void setStart(_Node* start);
};


/**
 * @class VariableNodeIterator
 * @ingroup nodeiterator
 *
 * This iterator iterates over all nodes that belong to
 * a given node (have the same root) and are not fixed. It doesn't iterate
 * over subtree nodes.
 * The default constructor makes a 'past the end VariableNodeIterator'
 */
template<class _Node, class _Ref=_Node&, class _Ptr=_Node*>
class VariableNodeIterator : public NodeIterator<_Node,_Ref,_Ptr>
{
public:
    typedef VariableNodeIterator<_Node> iterator;
    typedef VariableNodeIterator<const _Node > const_iterator;
    typedef VariableNodeIterator<_Node, _Ref,_Ptr> _Self;
    typedef NodeIterator<_Node,_Ref,_Ptr> _Base;
//  typedef typename NodeTraits<_Node>::_NonConstNode _NonConstNode;
    
    VariableNodeIterator() : _Base() {}
    /** Construct a VariableNodeIterator beginning at the given Node.
      * @param start The Node to start at */
    VariableNodeIterator(_Node* start) : _Base() { setStart(start); }
    virtual _Self* construct() const { return new _Self(); }
    virtual _Self* clone(_Node* start=0) const ;
    virtual ~VariableNodeIterator() {}
    virtual void setStart(_Node* start) { _Base::setStart(start); operator++(); }

    virtual bool operator==(const _Self& rhs);
    virtual bool operator!=(const _Self& rhs);
    virtual _Self& operator++();
};


/**
 * @class LeaveIterator
 * @ingroup nodeiterator
 *
 * @brief This iterator iterates over all leaves that belong to
 * a given node (have the same root).
 *
 * It doesn't iterate
 * over subtree nodes.
 * The default constructor makes a 'past the end LeaveIterator'.
 */

template<class _Node, class _Ref=_Node&, class _Ptr=_Node*>
class LeaveIterator : public NodeIterator<_Node,_Ref,_Ptr>
{
public: 
    typedef LeaveIterator<_Node> iterator;
    typedef LeaveIterator<const _Node > const_iterator;
    typedef LeaveIterator<_Node, _Ref,_Ptr> _Self;
    typedef NodeIterator<_Node,_Ref,_Ptr> _Base;
//  typedef typename NodeTraits<_Node>::_NonConstNode _NonConstNode;
    
    LeaveIterator() : _Base() {}
    /** Construct a LeaveIterator beginning at the given Node.
      * @param start The Node to start at */
    LeaveIterator(_Node* start) : _Base() { setStart(start); }
    virtual _Self* construct() const { return new _Self(); }
    virtual _Self* clone(_Node* start=0) const;
    virtual ~LeaveIterator() {}
    virtual void setStart(_Node* start) { _Base::setStart(start); operator++(); }

    virtual bool operator==(const _Self& rhs);
    virtual bool operator!=(const _Self& rhs);
    virtual _Self& operator++();
};


/**
 * @class AllNodeIterator
 * @ingroup nodeiterator
 *
 * @brief This iterator iterates over all nodes that follow
 * a given node (with no respect to the root of node).
 *
 * The default constructor makes a 'past the end AllNodeIterator'
 */
template<class _Node, class _Ref=_Node&, class _Ptr=_Node*>
class AllNodeIterator : public NodeIterator<_Node,_Ref,_Ptr>
{
public:
    typedef AllNodeIterator<_Node> iterator;
    typedef AllNodeIterator<const _Node > const_iterator;
    typedef AllNodeIterator<_Node, _Ref,_Ptr> _Self;
    typedef NodeIterator<_Node,_Ref,_Ptr> _Base;
//  typedef typename NodeTraits<_Node>::_NonConstNode _NonConstNode;

    AllNodeIterator() : _Base() {}
//  AllNodeIterator(const _Self& it) : _Base(it) {}
//  AllNodeIterator(const const_iterator& it) : _Base(it) {}
    AllNodeIterator(_Node* start) : _Base() { setStart(start); }
    virtual _Self* construct() const { return new _Self(); }
    virtual _Self* clone(_Node* start=0) const;
    virtual ~AllNodeIterator() {}

    virtual bool operator==(const _Self& rhs);
    virtual bool operator!=(const _Self& rhs);
    virtual _Self& operator++();
};

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

// ====================
// === NodeIterator ===
// ====================



/**
 * Copy constructor
 * @param start Node to start with (if not given make identical copy)
 */
template<class _Node, class _Ref, class _Ptr>
typename NodeIterator<_Node,_Ref,_Ptr>::_Self* 
NodeIterator<_Node,_Ref,_Ptr>::clone(_Node* start) const
{
    if (start)
        return new _Self(start);
    else
        return new _Self(*this);
}

/**
 * Set start node for next iteration
 * @param start The Node to start at
 */
template<class _Node, class _Ref, class _Ptr>
void 
NodeIterator<_Node,_Ref,_Ptr>::setStart(_Node* start)
{
    if (!start)
        return;
    m_seenNodeSet.clear();
    m_seenNodeSet.insert(start);
    m_nodeList.clear();
    m_end = false;
    m_currentNode = start;
    m_root = start;
}


/**
 * Equality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool 
NodeIterator<_Node,_Ref,_Ptr>::operator==(const _Self& rhs)
{
    return (isEnd() && rhs.isEnd());
}

/**
 * Inequality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool 
NodeIterator<_Node,_Ref,_Ptr>::operator!=(const _Self& rhs)
{
    return (!isEnd() || !rhs.isEnd());
}

/**
 * Prefix proceed operator
 */
template<class _Node, class _Ref, class _Ptr>
typename NodeIterator<_Node,_Ref,_Ptr>::_Self&
NodeIterator<_Node,_Ref,_Ptr>::operator++()
{
    addToNodeList( m_currentNode->getChildren() );

    if (!m_nodeList.empty())
    {
        m_currentNode = m_nodeList.back();
        m_nodeList.pop_back();

        // proceed if current node's root is not m_root
        if (m_currentNode->getRoot() != m_root)
            operator++();
    }
    else
        setEnd();
    return *this;
}

/**
 * Postfix proceed operator
 */
template<class _Node, class _Ref, class _Ptr>
typename NodeIterator<_Node,_Ref,_Ptr>::_Self
NodeIterator<_Node,_Ref,_Ptr>::operator++(int n)
{
//  _Self temp = *this;
    int i;
    for (i=0;i<n;i++)
        this->operator++();
    return *this;
}


/**
 * Add Nodes from a NodeList to the list, if they aren't
 * already visited.
 * @param values NodeList to add to the list
 */
template<class _Node, class _Ref, class _Ptr>
void 
NodeIterator<_Node,_Ref,_Ptr>::addToNodeList(const std::list<_NonConstNode*>* values)
{
    typename std::list<_NonConstNode*>::const_reverse_iterator it = values->rbegin();

    _Node* currentValue;
    while(it != values->rend())
    {
        currentValue = *it;
        if(m_seenNodeSet.count(currentValue) == 0)
        {
            m_seenNodeSet.insert(currentValue);
            m_nodeList.push_back(currentValue);
        }
        ++it;
    }
}

// ============================
// === PostOrderNodeIterator ===
// ============================


/**
 * Copy constructor
 * @param start Node to start with (if not given make identical copy)
 */
template<class _Node, class _Ref, class _Ptr>
typename PostOrderNodeIterator<_Node,_Ref,_Ptr>::_Self*
PostOrderNodeIterator<_Node,_Ref,_Ptr>::clone(_Node* start) const
{
    if (start)
        return new _Self(start);
    else
        return new _Self(*this);
}

/**
 * Equality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool
PostOrderNodeIterator<_Node,_Ref,_Ptr>::operator==(const _Self& rhs)
{
    return (isEnd() && rhs.isEnd());
}

/**
 * Inequality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool
PostOrderNodeIterator<_Node,_Ref,_Ptr>::operator!=(const _Self& rhs)
{
    return (!isEnd() || !rhs.isEnd());
}


template<class _Node, class _Ref, class _Ptr>
void
PostOrderNodeIterator<_Node,_Ref,_Ptr>::setStart(_Node* start)
{
    _Base::setStart(start);
    
    // as long as nodes have children, step down to leftmost child
    while (m_currentNode->getChildren()->size()>0)
        m_currentNode = *(m_currentNode->getChildren()->begin());
    return;
}


/**
 * Prefix proceed operator
 */
template<class _Node, class _Ref, class _Ptr>
typename PostOrderNodeIterator<_Node,_Ref,_Ptr>::_Self&
PostOrderNodeIterator<_Node,_Ref,_Ptr>::operator++()
{   
    _Node* travelnode=0;
    const std::list<_NonConstNode*>* children=0;

    // we are ready
    if (m_currentNode==m_root)
    {
        setEnd();
        return *this;
    }
    
    // we cannot move right -> move up -> print parent
    travelnode=m_currentNode->getRightSibling();
    if (!travelnode)
    {
        if (!(m_currentNode=m_currentNode->getParent()))
        {   
            cerr << "Error in postorder algorithm";
            exit(-1);
        }
        return *this;
    }
    else
    {
        // move right worked -> check for children
        // as long as nodes have children, step down to leftmost child
        children = travelnode->getChildren();
        while (children->size()>0)
        {
            travelnode = *(children->begin());
            children = travelnode->getChildren();
        }
        m_currentNode = travelnode; // no more children
    }
    return *this;
}


// ============================
// === VariableNodeIterator ===
// ============================


/**
 * Copy constructor
 * @param start Node to start with (if not given make identical copy)
 */
template<class _Node, class _Ref, class _Ptr>
typename VariableNodeIterator<_Node,_Ref,_Ptr>::_Self*
VariableNodeIterator<_Node,_Ref,_Ptr>::clone(_Node* start) const
{
    if (start)
        return new _Self(start);
    else
        return new _Self(*this);
}

/**
 * Equality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool 
VariableNodeIterator<_Node,_Ref,_Ptr>::operator==(const _Self& rhs)
{
    return (isEnd() && rhs.isEnd());
}

/**
 * Inequality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool 
VariableNodeIterator<_Node,_Ref,_Ptr>::operator!=(const _Self& rhs)
{
    return (!isEnd() || !rhs.isEnd());
}


/**
 * Prefix proceed operator
 */
template<class _Node, class _Ref, class _Ptr>
typename VariableNodeIterator<_Node,_Ref,_Ptr>::_Self&
VariableNodeIterator<_Node,_Ref,_Ptr>::operator++()
{
    addToNodeList(m_currentNode->getChildren());

    if (!m_nodeList.empty())
    {
        m_currentNode = m_nodeList.back();
        m_nodeList.pop_back();

        // proceed if current node is not child of root or current node is fixed
        if ((m_currentNode->getRoot() != m_root) || m_currentNode->isFixed())
            operator++();
    }
    else
        setEnd();
    return *this;
}



// =====================
// === LeaveIterator ===
// =====================


/**
 * Copy constructor
 * @param start Node to start with (if not given make identical copy)
 */
template<class _Node, class _Ref, class _Ptr>
typename LeaveIterator<_Node,_Ref,_Ptr>::_Self*
LeaveIterator<_Node,_Ref,_Ptr>::clone(_Node* start) const
{
    if (start)
        return new _Self(start);
    else
        return new _Self(*this);
}

/**
 * Equality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool 
LeaveIterator<_Node,_Ref,_Ptr>::operator==(const _Self& rhs)
{
    return (isEnd() && rhs.isEnd());
}

/**
 * Inequality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool 
LeaveIterator<_Node,_Ref,_Ptr>::operator!=(const _Self& rhs)
{
    return (!isEnd() || !rhs.isEnd());
}


/**
 * Prefix proceed operator
 */
template<class _Node, class _Ref, class _Ptr>
typename LeaveIterator<_Node,_Ref,_Ptr>::_Self&
LeaveIterator<_Node,_Ref,_Ptr>::operator++()
{
    addToNodeList(m_currentNode->getChildren());

    if (!m_nodeList.empty())
    {
        m_currentNode = m_nodeList.back();
        m_nodeList.pop_back();

        // proceed if current node has children
        if (m_currentNode->getNumChildren() > 0)
            operator++();
    }
    else
        setEnd();
    return *this;
}


// =======================
// === AllNodeIterator ===
// =======================


/**
 * Copy constructor
 * @param start Node to start with (if not given make identical copy)
 */
template<class _Node, class _Ref, class _Ptr>
typename AllNodeIterator<_Node,_Ref,_Ptr>::_Self*
AllNodeIterator<_Node,_Ref,_Ptr>::clone(_Node* start) const
{
    if (start)
        return new _Self(start);
    else
        return new _Self(*this);
}

/**
 * Equality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool 
AllNodeIterator<_Node,_Ref,_Ptr>::operator==(const _Self& rhs)
{
    return (isEnd() && rhs.isEnd());
}

/**
 * Inequality operator
 * @warning Compares only 'past the end'
 */
template<class _Node, class _Ref, class _Ptr>
bool 
AllNodeIterator<_Node,_Ref,_Ptr>::operator!=(const _Self& rhs)
{
    return (!isEnd() || !rhs.isEnd());
}


/**
 * Prefix proceed operator
 */
template<class _Node, class _Ref, class _Ptr>
AllNodeIterator<_Node,_Ref,_Ptr>& 
AllNodeIterator<_Node,_Ref,_Ptr>::operator++()
{
    addToNodeList(m_currentNode->getChildren());

    if (!m_nodeList.empty())
    {
        m_currentNode = m_nodeList.back();
        m_nodeList.pop_back();
    }
    else
        setEnd();
    return *this;
}


} // namespace treecomp

#endif //NODEITERATOR_H

---