#ifndef __FPA__IMAGE__DIJKSTRAWITHSPHEREBACKTRACKING__H__
#define __FPA__IMAGE__DIJKSTRAWITHSPHEREBACKTRACKING__H__

#include <map>
#include <deque>
#include <utility>
#include <fpa/Image/Dijkstra.h>

namespace fpa
{
  namespace Image
  {
    /**
     * @param I Input image type
     */
    template< class I, class C >
    class DijkstraWithSphereBacktracking
      : public fpa::Image::Dijkstra< I, C >
    {
    public:
      typedef DijkstraWithSphereBacktracking  Self;
      typedef fpa::Image::Dijkstra< I, C >    Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

      typedef typename Superclass::TCost          TCost;
      typedef typename Superclass::TVertex        TVertex;
      typedef typename Superclass::InputImageType TImage;
      typedef std::deque< TVertex >               TVertices;

      typedef typename Superclass::TTraits::TVertexCmp TVertexCmp;
      typedef std::map< TVertex, TVertex, TVertexCmp > TTree;

      typedef typename Superclass::TEndEvent             TEndEvent;
      typedef typename Superclass::TBacktrackingEvent    TBacktrackingEvent;
      typedef typename Superclass::TEndBacktrackingEvent TEndBacktrackingEvent;

    protected:
      typedef std::pair< TCost, TVertex >     _TCandidate;
      typedef std::multimap< TCost, TVertex > _TCandidates;
      typedef typename Superclass::_TNode     _TNode;

      typedef typename I::PixelType  _TPixel;
      typedef typename I::RegionType _TRegion;
      typedef typename I::SizeType   _TSize;

    public:
      itkNewMacro( Self );
      itkTypeMacro( DijkstraWithSphereBacktracking, Dijkstra );

      itkGetConstMacro( FinalTree, TTree );
      itkGetConstMacro( EndPoints, TVertices );

    protected:
      DijkstraWithSphereBacktracking( );
      virtual ~DijkstraWithSphereBacktracking( );

      virtual void _BeforeMainLoop( );
      virtual void _AfterMainLoop( );
      virtual bool _UpdateNeigh( _TNode& nn, const _TNode& n );
      virtual bool _UpdateResult( _TNode& n );

      _TRegion _Region( const TVertex& c, const double& r );

    private:
      DijkstraWithSphereBacktracking( const Self& other );
      Self& operator=( const Self& other );

    protected:
      _TCandidates m_Candidates;
      TTree        m_FinalTree;
      TVertices    m_EndPoints;
    };

  } // ecapseman

} // ecapseman

#include <fpa/Image/DijkstraWithSphereBacktracking.hxx>

#endif // __FPA__IMAGE__DIJKSTRAWITHSPHEREBACKTRACKING__H__

// eof - $RCSfile$