DistanceBreadthFirstVisitor.h

#pragma once

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

#define DistanceBreadthFirstVisitor_RECURSES

#if !defined DistanceBreadthFirstVisitor_h

#define DistanceBreadthFirstVisitor_h

// Inclusions
#include <iostream>
#include <queue>
#include "DGtal/base/Common.h"
#include "DGtal/base/ConstAlias.h"
#include "DGtal/base/CountedPtr.h"
#include "DGtal/graph/CUndirectedSimpleLocalGraph.h"

namespace DGtal
{

  // template class DistanceBreadthFirstVisitor
  template < typename TGraph, 
             typename TVertexFunctor,
             typename TMarkSet = typename TGraph::VertexSet >
  class DistanceBreadthFirstVisitor
  {
    // ----------------------- Associated types ------------------------------
  public:
    typedef DistanceBreadthFirstVisitor<TGraph,TVertexFunctor,TMarkSet> Self;
    typedef TGraph Graph;
    typedef TVertexFunctor VertexFunctor;
    typedef TMarkSet MarkSet;
    typedef typename Graph::Size Size;
    typedef typename Graph::Vertex Vertex;
    typedef typename VertexFunctor::Value Scalar;
    typedef Scalar Data;

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

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

    struct Node : public std::pair< Vertex, Scalar > 
    {
      typedef std::pair< Vertex, Scalar > Base;
      using Base::first;
      using Base::second;

      inline Node()
        : std::pair< Vertex, Scalar >()
      {}
      inline Node( const Node & other )
        : std::pair< Vertex, Scalar >( other )
      {}
      inline Node( const Vertex & v, Scalar d )
        : std::pair< Vertex, Scalar >( v, d )
      {}
      inline bool operator<( const Node & other ) const
      {
        return other.second < second;
      }
      inline bool operator<=( const Node & other ) const
      {
        return other.second <= second;
      }
      inline bool operator==( const Node & other ) const
      {
        return other.second == second;
      }
      inline bool operator!=( const Node & other ) const
      {
        return other.second != second;
      }
    };

    typedef std::priority_queue< Node > NodeQueue;
    typedef std::vector< Vertex > VertexList;

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

    ~DistanceBreadthFirstVisitor();

    DistanceBreadthFirstVisitor ( const DistanceBreadthFirstVisitor & other );


    DistanceBreadthFirstVisitor( ConstAlias<Graph> graph, 
                     const VertexFunctor & distance,
                     const Vertex & p );

    template <typename VertexIterator>
    DistanceBreadthFirstVisitor( const Graph & graph, 
                     const VertexFunctor & distance,
                     VertexIterator b, VertexIterator e );


    const Graph & graph() const;

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

    const Node & current() const; 

    template <typename TBackInsertionSequence>
    void getCurrentLayer( TBackInsertionSequence & layer );

    void ignore();

    void ignoreLayer();

    void expand();

    void expandLayer();

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

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

    void terminate();

    const MarkSet & markedVertices() const;

    MarkSet visitedVertices() const;

    void pushAgain( const Node & node );


    void swap( DistanceBreadthFirstVisitor & other );

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

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

    bool isValid() const;

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

    const Graph* myGraph;

    VertexFunctor myDistance;

    MarkSet myMarkedVertices;

    NodeQueue myQueue;

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

    DistanceBreadthFirstVisitor();

  private:

    DistanceBreadthFirstVisitor & operator= ( const DistanceBreadthFirstVisitor & other );

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

  }; // end of class DistanceBreadthFirstVisitor


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

} // namespace DGtal


// Includes inline functions.
#include "DGtal/graph/DistanceBreadthFirstVisitor.ih"

//                                                                           //

#endif // !defined DistanceBreadthFirstVisitor_h

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