DepthFirstVisitor.h

#pragma once

#if defined(DepthFirstVisitor_RECURSES)
#error Recursive header files inclusion detected in DepthFirstVisitor.h
#else // defined(DepthFirstVisitor_RECURSES)

#define DepthFirstVisitor_RECURSES

#if !defined DepthFirstVisitor_h

#define DepthFirstVisitor_h

// Inclusions
#include <iostream>
#include <stack>
#include "DGtal/base/Common.h"
#include "DGtal/base/CountedPtr.h"
#include "DGtal/kernel/sets/DigitalSetSelector.h"
#include "DGtal/kernel/sets/DigitalSetDomain.h"
#include "DGtal/topology/DomainAdjacency.h"
#include "DGtal/topology/CUndirectedSimpleLocalGraph.h"

namespace DGtal
{

  // template class DepthFirstVisitor
  template < typename TGraph, 
             typename TMarkSet = typename TGraph::VertexSet >
  class DepthFirstVisitor
  {
    // ----------------------- Associated types ------------------------------
  public:
    typedef DepthFirstVisitor<TGraph,TMarkSet> Self;
    typedef TGraph Graph;
    typedef TMarkSet MarkSet;
    typedef typename Graph::Size Size;
    typedef typename Graph::Vertex Vertex;

    //BOOST_CONCEPT_ASSERT(( CUndirectedSimpleLocalGraph< Graph > ));
    // Cannot check this since some types using it are incomplete.
    //BOOST_CONCEPT_ASSERT(( CSet< MarkSet, Vertex > ));

    // ----------------------- defined types ------------------------------
  public:

    typedef std::pair< Vertex, Size > Node;
    typedef std::stack< Node > NodeQueue;
    typedef std::vector< Vertex > VertexList;

    struct NodeAccessor {
      typedef const Node value;
      typedef const Node value_type;
      typedef const Node* pointer;
      typedef const Node& reference;
      inline
      static reference get( const Node & node )
      { return node; }
    };

    struct VertexAccessor {
      typedef const Vertex value;
      typedef const Vertex value_type;
      typedef const Vertex* pointer;
      typedef const Vertex& reference;
      inline
      static reference get( const Node & node )
      { return node.first; }
    };

    template <typename TAccessor>
    struct ConstIterator 
    {
      typedef ConstIterator<TAccessor> Self;
      typedef DepthFirstVisitor<TGraph,TMarkSet> Visitor;
      typedef TAccessor Accessor;

      // stl iterator types.
      typedef std::input_iterator_tag iterator_category;
      typedef typename Accessor::value value_type;
      typedef std::ptrdiff_t difference_type; 
      typedef typename Accessor::pointer pointer;
      typedef typename Accessor::reference reference;

      CountedPtr< Visitor > myVisitor;

      inline
      ConstIterator() 
        : myVisitor( 0 ) {}
      inline
      ConstIterator( Visitor* ptrV ) 
        : myVisitor( ptrV ) {}
      inline
      ConstIterator( const Self & other ) 
        : myVisitor( other.myVisitor ) {}

      inline
      Self & operator=( const Self & other )
      {
        if ( this != &other )
          myVisitor = other.myVisitor;
        return *this;
      }

      inline
      reference
      operator*() const
      {
        ASSERT( ( myVisitor.get() != 0 )
                && "DGtal::DepthFirstVisitor<TGraph,TMarkSet>::ConstIterator::operator*(): you cannot dereferenced a null visitor (i.e. end()).");
        return Accessor::get( myVisitor->current() );
      }

      inline
      pointer
      operator->() const
      { 
        ASSERT( ( myVisitor.get() != 0 )
                && "DGtal::DepthFirstVisitor<TGraph,TMarkSet>::ConstIterator::operator->(): you cannot dereferenced a null visitor (i.e. end()).");
        return & Accessor::get( operator*() );
      }

      inline
      Self&
      operator++()
      {
        myVisitor->expand();
        return *this;
      }

      inline
      Self
      operator++(int)
      {
        Self __tmp = *this;
        myVisitor->expand();
        return __tmp;
      }
      
      inline
      bool operator==( const Self & other ) const
      {
        if ( ( myVisitor.get() == 0 ) || myVisitor->finished() )
          return ( other.myVisitor.get() == 0 ) || other.myVisitor->finished();
        else if ( other.myVisitor.get() == 0 )
          return false;
        else
          return &(myVisitor->current()) == &(other.myVisitor->current());
      }

      inline
      bool operator!=( const Self & other ) const
      {
        return ! ( this->operator==( other ) );
      }
    };

    typedef ConstIterator<VertexAccessor> VertexConstIterator;
    typedef ConstIterator<NodeAccessor> NodeConstIterator;

    // ----------------------- Standard services ------------------------------
  public:

    ~DepthFirstVisitor();

    DepthFirstVisitor( const Graph & graph );

    DepthFirstVisitor( const Graph & graph, const Vertex & p );

    template <typename VertexIterator>
    DepthFirstVisitor( const Graph & graph, 
                         VertexIterator b, VertexIterator e );


    const Graph & graph() const;

    // ----------------------- traversal services ------------------------------
  public:

    const Node & current() const; 

    void ignore();

    void expand();

    template <typename VertexPredicate>
    void expand( const VertexPredicate & authorized_vtx );
    
    bool finished() const;

    void terminate();

    const MarkSet & markedVertices() const;

    MarkSet visitedVertices() const;


    // ----------------------- Interface --------------------------------------
  public:

    void selfDisplay ( std::ostream & out ) const;

    bool isValid() const;

    // ------------------------- Protected Datas ------------------------------
  private:
    // ------------------------- Private Datas --------------------------------
  private:

    const Graph & myGraph;

    MarkSet myMarkedVertices;

    NodeQueue myQueue;

    // ------------------------- Hidden services ------------------------------
  protected:

    DepthFirstVisitor();

  private:

    DepthFirstVisitor ( const DepthFirstVisitor & other );

    DepthFirstVisitor & operator= ( const DepthFirstVisitor & other );

    // ------------------------- Internals ------------------------------------
  private:

  }; // end of class DepthFirstVisitor


  template <typename TGraph, typename TMarkSet >
  std::ostream&
  operator<< ( std::ostream & out, 
               const DepthFirstVisitor<TGraph, TMarkSet > & object );

} // namespace DGtal


// Includes inline functions.
#include "DGtal/topology/DepthFirstVisitor.ih"

//                                                                           //

#endif // !defined DepthFirstVisitor_h

#undef DepthFirstVisitor_RECURSES
#endif // else defined(DepthFirstVisitor_RECURSES)