#ifndef __FPA__BASE__DIJKSTRA__H__
#define __FPA__BASE__DIJKSTRA__H__

#include <vector>
#include <itkFunctionBase.h>
#include <fpa/Base/Algorithm.h>
#include <fpa/Base/MinimumSpanningTree.h>

namespace fpa
{
  namespace Base
  {
    /**
     */
    template< class _TSuperclass >
    class Dijkstra
      : public _TSuperclass
    {
    public:
      typedef Dijkstra                        Self;
      typedef _TSuperclass                    Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

      // Template arguments
      typedef typename Superclass::TVertex        TVertex;
      typedef typename Superclass::TScalar        TScalar;
      typedef typename Superclass::TFilter        TFilter;
      typedef typename Superclass::TVertexCompare TVertexCompare;
      typedef typename Superclass::TFrontId       TFrontId;
      typedef typename Superclass::TCollision     TCollision;
      typedef typename Superclass::TCollisionsRow TCollisionsRow;
      typedef typename Superclass::TCollisions    TCollisions;
      typedef typename Superclass::TNodeLabel     TNodeLabel;
      typedef typename Superclass::TNode          TNode;
      typedef typename Superclass::TNodes         TNodes;
      typedef typename Superclass::TVertices      TVertices;

      typedef itk::FunctionBase< TScalar, TScalar > TCostConversionFunction;

      typedef
      fpa::Base::MinimumSpanningTree< TVertex, TScalar, TVertexCompare >
      TMinimumSpanningTree;

      struct TDijkstraCmp
      {
        bool operator()( const TNode& a, const TNode& b )
          { return( b.Result < a.Result ); }
      };
      static const TDijkstraCmp DijkstraCmp;

    public:
      itkTypeMacro( Dijkstra, Algorithm );

      itkGetObjectMacro( CostConversionFunction, TCostConversionFunction );
      itkSetObjectMacro( CostConversionFunction, TCostConversionFunction );

    public:
      TMinimumSpanningTree* GetMinimumSpanningTree( );
      const TMinimumSpanningTree* GetMinimumSpanningTree( ) const;
      void GraftMinimumSpanningTree( itk::DataObject* obj );

    protected:
      // Methods to extend itk-based architecture
      Dijkstra( );
      virtual ~Dijkstra( );

      // Front propagation methods to be overloaded
      virtual void _AfterGenerateData( ) fpa_OVERRIDE;
      virtual void _Visit( const TNode& n ) fpa_OVERRIDE;
      virtual bool _Result( TNode& node, const TNode& parent ) fpa_OVERRIDE;
      virtual void  _QueueClear( ) fpa_OVERRIDE;
      virtual void  _QueuePush( const TNode& node ) fpa_OVERRIDE;
      virtual TNode _QueuePop( ) fpa_OVERRIDE;
      virtual bool  _IsQueueEmpty( ) const fpa_OVERRIDE;

      // Dijkstra methods to be overloaded
      virtual TScalar _Cost( const TVertex& a, const TVertex& b ) const = 0;

    private:
      // Purposely not implemented
      Dijkstra( const Self& other );
      Self& operator=( const Self& other );

    protected:
      unsigned int m_MSTIdx;
      std::vector< TNode > m_Queue;
      typename TCostConversionFunction::Pointer m_CostConversionFunction;
    };

  } // ecapseman

} // ecapseman

#ifndef ITK_MANUAL_INSTANTIATION
#  include <fpa/Base/Dijkstra.hxx>
#endif

#endif // __FPA__BASE__DIJKSTRA__H__

// eof - $RCSfile$