#ifndef __FPA__BASE__DIJKSTRA__H__
#define __FPA__BASE__DIJKSTRA__H__

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

namespace fpa
{
  namespace Base
  {
    /**
     * Dijkstra is a front propagation algorithm that minimizes costs
     *
     * @param V   Vertex type.
     * @param C   Vertex value type.
     * @param R   Result value type.
     * @param S   Space type where vertices are.
     * @param VC  Vertex lexicographical compare.
     * @param MST Minimum spanning tree type.
     * @param B   Base class for this algorithm. It should be any itk-based
     *            filter (itk::ProcessObject).
     *
     */
    template< class V, class C, class R, class S, class VC, class MST, class B >
    class Dijkstra
      : public Algorithm< V, C, R, S, VC, B >
    {
    public:
      typedef Dijkstra                         Self;
      typedef Algorithm< V, C, R, S, VC, B >   Superclass;
      typedef itk::SmartPointer< Self >        Pointer;
      typedef itk::SmartPointer< const Self >  ConstPointer;

      typedef MST TMinimumSpanningTree;
      typedef typename Superclass::TVertex        TVertex;
      typedef typename Superclass::TValue         TValue;
      typedef typename Superclass::TResult        TResult;
      typedef typename Superclass::TSpace         TSpace;
      typedef typename Superclass::TVertexCompare TVertexCompare;

      typedef typename Superclass::TStartEvent     TStartEvent;
      typedef typename Superclass::TStartLoopEvent TStartLoopEvent;
      typedef typename Superclass::TEndEvent       TEndEvent;
      typedef typename Superclass::TEndLoopEvent   TEndLoopEvent;
      typedef typename Superclass::TAliveEvent     TAliveEvent;
      typedef typename Superclass::TFrontEvent     TFrontEvent;
      typedef typename Superclass::TFreezeEvent    TFreezeEvent;

      typedef typename Superclass::TStartBacktrackingEvent TStartBacktrackingEvent;
      typedef typename Superclass::TEndBacktrackingEvent TEndBacktrackingEvent;
      typedef typename Superclass::TBacktrackingEvent TBacktrackingEvent;

    protected:
      typedef typename Superclass::_TVertices      _TVertices;
      typedef typename Superclass::_TCollision     _TCollision;
      typedef typename Superclass::_TCollisionsRow _TCollisionsRow;
      typedef typename Superclass::_TCollisions    _TCollisions;
      typedef typename Superclass::_TNode          _TNode;
      typedef typename Superclass::_TNodes         _TNodes;

      struct _TQueueNode
      {
        TVertex Vertex;
        _TNode  Node;

        // Make the min-heap behave as a max-heap
        bool operator<( const _TQueueNode& other ) const
          { return( other.Node.Result < this->Node.Result ); }
      };
      typedef std::vector< _TQueueNode > _TQueue;

    public:
      itkTypeMacro( Dijkstra, Algorithm );

      itkBooleanMacro( LocalCosts );
      itkBooleanMacro( FillNodeQueue );
      itkGetConstMacro( LocalCosts, bool );
      itkGetConstMacro( FillNodeQueue, bool );
      itkSetMacro( LocalCosts, bool );
      itkSetMacro( FillNodeQueue, bool );

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

    protected:
      Dijkstra( );
      virtual ~Dijkstra( );

      virtual TResult _Cost( const TVertex& v, const TVertex& p ) const = 0;

      virtual void _BeforeGenerateData( ) ITK_OVERRIDE;

      // Results-related abstract methods
      virtual bool _ComputeNeighborResult(
        TResult& result, const TVertex& neighbor, const TVertex& parent
        ) const ITK_OVERRIDE;
      virtual void _SetResult( const TVertex& v, const _TNode& n ) ITK_OVERRIDE;

      // Queue-related abstract methods
      virtual bool _IsQueueEmpty( ) const ITK_OVERRIDE;
      virtual void _QueuePush( const TVertex& v, const _TNode& n ) ITK_OVERRIDE;
      virtual void _QueuePop( TVertex& v, _TNode& n ) ITK_OVERRIDE;
      virtual void _QueueClear( ) ITK_OVERRIDE;

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

    protected:
      bool m_LocalCosts;
      bool m_FillNodeQueue;
      _TQueue m_Queue;
      unsigned int m_MSTIdx;
    };

  } // ecapseman

} // ecapseman

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

#endif // __FPA__BASE__DIJKSTRA__H__

// eof - $RCSfile$