QtHybrid/generator/common/depth1stiterator.h

#ifndef DEPTH1STITERATOR_H
#define DEPTH1STITERATOR_H

#include <iterator>
#include <functional>
#include <list>
#include <set>
#include <stack>


/**
  * Graph searches provide the feature to colore nodes as they
  * are explored / visited.
  */
enum NodeColor
{
    /**
      * A node colored white means that it is not explored
      * by the search algorithm yet.
      */
    NC_WHITE = 0,

    /**
      * A node colored gray means that it has been noticed by
      * the search, but not exhaustively dealt with yet.
      */
    NC_GRAY,

    /**
      * A node has been explored exhaustively, that is all its
      * adjacents nodes are at least gray.
      */
    NC_BLACK
};


/**
  * A struct to decorate a node with color.
  */
template<typename NODE>
struct ColoredNode
{
    NODE      m_node;
    NodeColor m_color;

    ColoredNode()
        : m_color(NC_WHITE)
    {
        ;
    }


    ColoredNode(NODE      node,
                NodeColor color)
       : m_node(node)
        , m_color(color)
    {
        ;
    }
};

template<typename NODE>
bool operator==(const ColoredNode<NODE> & first,
                const ColoredNode<NODE> & second)
{
    return first.m_node == second.m_node
            && first.m_color == second.m_color;
}


template<typename NODE>
bool operator!=(const ColoredNode<NODE> & first,
                const ColoredNode<NODE> & second)
{
    return first.m_node != second.m_node
            || first.m_color != second.m_color;
}


/**
  * Deapth1stIterator is an STL compliant forward iterator.
  *
  * Given a proper graph / node implementation, it is capable of
  * visiting the nodes (in depth-first manner). The visiting happens
  * in the manner of iteration.
  *
  * The value type of this iterator is *not* node, but colored node.
  * One can iterate nodes in a preorder manner, that is, a node
  * is given to the iterating client before its adjacents are explored
  * (accompanying color will be gray).
  *
  * One can iterate npodes in postorder manner, that is, a node
  * is given to the iterating client after its adjacents are
  * explored (accompanying color will be black).
  *
  * One can configure this iterator to emit the same node both before
  * (with gray color) and after (with black color) its adjacents are
  * explored.
  *
  * Concepts required by Depth1stIterator.
  *
  * GRAPH:
  *   o should implement syntax "graph.getAdjacents(node, OUTITER);"
  *     with an arbitrary output iterator given. The method should
  *     give all adjacents of node through OUTITER.
  *
  *
  * NODE:
  *   o Default Constructible
  *   o Assignable
  *   o Equality Comparable
  */
template<typename GRAPH,
         typename NODE,
         typename COMPARE = std::less<NODE> >
class Depth1stIterator : public std::iterator<std::forward_iterator_tag, ColoredNode<NODE> >
{
public:
    //
    // public types
    //
    typedef GRAPH             Graph;
    typedef NODE              Node;
    typedef ColoredNode<NODE> CNode;


    /**
      * Flags to control when we should meet an item
      * during iteration. Before visiting its adjacents
      * (pre visit), after visiting its adjacents (post
      * visit). You can combine them with bitwise or
      * to receive the items both before and after.
      */
    enum Flag
    {
        /**
          * The value of PreVisit coincides with the value of
          * NC_GRAY. It's not a coincidence. They are actually the
          * same thing, but used in different context / sentences.
          */
        PreVisit = 1,


        /**
          * The value of PostVisit coincides with the value of
          * NC_BLACK. It's not a coincidence. They are actually the
          * same thing, but used in different context / sentences.
          */
        PostVisit = 2
    };


private:
    //
    // private members
    //
    Graph                    * m_graph;
    std::stack<CNode>          m_nodesToVisit;
    std::set<Node, COMPARE>    m_visitedNodes;
    CNode                      m_currentNode;
    int                        m_flags;


public:
    //
    // public operators
    //

    /**
      * Constructs an "end" iterator.
      */
    Depth1stIterator()
        : m_graph(NULL)
    {
        ;
    }


    /**
      * Constructs a "begin" iterator that iterates through elements in
      * a depth-first search manner, starting with a single node.
      */
    Depth1stIterator(Graph & graph,
                     NODE    node,
                     int     flags = PreVisit)
        : m_graph(&graph)
        , m_flags(flags)
    {
        m_nodesToVisit.push(CNode(node,
                                  NC_GRAY));
        next();
    }



    /**
      * Constructs a "begin" iterator that iterates through elements
      * in depth-first search manner, starting with all the nodes
      * given here via the input iterators.
      */
    template<typename NODE_IITER>
    Depth1stIterator(Graph      & graph,
                     NODE_IITER   first,
                     NODE_IITER   last,
                     int          flags = PreVisit)
        : m_graph(&graph)
        , m_flags(flags)
    {
        for (; first != last; ++first)
        {
            m_nodesToVisit.push(CNode(*first,
                                      NC_GRAY));
        }
        next();
    }


    CNode operator*()
    {
        return m_currentNode;
    }


    CNode * operator->()
    {
        return &m_currentNode;
    }


    Depth1stIterator & operator++()
    {
        next();
        return *this;
    }


    Depth1stIterator operator++(int)
    {
        Depth1stIterator
            rv(*this);
        next();
        return rv;
    }


private:
    //
    // implementation details
    //
    bool allowedColor(NodeColor color) const
    {
        bool
            rv = static_cast<bool>(m_flags & (static_cast<int>(color)));

        return rv;
    }


#define __yield_return(cn) {if(allowedColor(cn.m_color))return;}
    void next()
    {
        if (m_graph == NULL)
            return;

        while (!m_nodesToVisit.empty())
        {
            m_currentNode = m_nodesToVisit.top();

            if (m_currentNode.m_color == NC_BLACK)
            {
                m_nodesToVisit.pop();
            }
            else // NC_GRAY
            {
                m_nodesToVisit.top().m_color = NC_BLACK;

                std::list<Node>
                    adjacents;
                m_graph->getAdjacents(m_currentNode.m_node,
                                      std::inserter(adjacents,
                                                    adjacents.end()));
                typename std::list<Node>::const_reverse_iterator
                    it = adjacents.rbegin(),
                    end = adjacents.rend();
                for (; it != end; ++it)
                {
                    Node
                        adjacent = *it;
                    if (m_visitedNodes.find(adjacent) == m_visitedNodes.end())
                    {
                        m_visitedNodes.insert(adjacent);
                        m_nodesToVisit.push(CNode(adjacent,
                                                  NC_GRAY));
                    }
                }
            }
            __yield_return(m_currentNode);
        }

        m_graph = NULL;
    }
#undef __yield_return

    template<typename G,
             typename N,
             typename C>
    friend bool operator==(const Depth1stIterator<G, N, C> & first,
                           const Depth1stIterator<G, N, C> & second);
    template<typename G,
             typename N,
             typename C>
    friend bool operator!=(const Depth1stIterator<G, N, C> & first,
                           const Depth1stIterator<G, N, C> & second);
};


template<typename GRAPH,
         typename NODE,
         typename COMPARE>
bool operator==(const Depth1stIterator<GRAPH, NODE, COMPARE> & first,
                const Depth1stIterator<GRAPH, NODE, COMPARE> & second)
{
    bool
        rv(false);

    if (first.m_graph == NULL && second.m_graph == NULL)
    {
        rv = true;
    }
    else
    {
        rv = first.m_graph == second.m_graph
            && first.m_flags == second.m_flags
            && first.m_currentNode == second.m_currentNode
            && first.m_nodesToVisit == second.m_nodesToVisit
            && first.m_visitedNodes == second.m_visitedNodes;
    }

    return rv;
}



template<typename GRAPH,
         typename NODE,
         typename COMPARE>
bool operator!=(const Depth1stIterator<GRAPH, NODE, COMPARE> & first,
                const Depth1stIterator<GRAPH, NODE, COMPARE> & second)
{
    return !(first == second);
}

#endif // DEPTH1STITERATOR_H