#ifndef __FPA__BASE__DIJKSTRA__H__
#define __FPA__BASE__DIJKSTRA__H__

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

namespace fpa
{
  namespace Base
  {
    /**
     */
    template< class V, class C, class VV, class VC >
    class DijkstraTraits
    {
    public:
      typedef V TVertex;
      typedef C TResult;
      typedef C TCost;
      typedef VV TVertexValue;
      typedef VC TVertexCmp;
      typedef long TFrontId;

      class TNode
      {
      public:
        TNode( )
          : Cost( 0 )
          { }
        TNode( const TVertex& v, const TFrontId& f )
          : Vertex( v ),
            Parent( v ),
            Result( TResult( 0 ) ),
            FrontId( f ),
            Cost( TCost( 0 ) )
          { }
        TNode( const TVertex& v, const TResult& r, const TFrontId& f )
          : Vertex( v ),
            Parent( v ),
            Result( r ),
            FrontId( f ),
            Cost( TCost( 0 ) )
          { }
        virtual ~TNode( )
          { }

        // NOTE: stl::heaps work as maximum priority queues
        bool operator<( const TNode& other ) const
          { return( other.Cost < this->Cost ); }

        TVertex Vertex;
        TVertex Parent;
        TResult Result;
        TFrontId FrontId;
        TCost Cost;
      };

      typedef std::vector< TNode > TNodes;
    };

    /**
     * Dijkstra is a front propagation algorithm that minimizes costs
     */
    template< class V, class C, class VV, class VC, class B >
    class Dijkstra
      : public Algorithm< DijkstraTraits< V, C, VV, VC >, B >
    {
    public:
      // Templated types
      typedef V TVertex;
      typedef C TCost;
      typedef VV TVertexValue;
      typedef B  TBaseFilter;
      typedef DijkstraTraits< V, C, VV, VC > TTraits;

      // Standard class typdedefs
      typedef Dijkstra                        Self;
      typedef Algorithm< TTraits, B >         Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

    protected:
      typedef typename TTraits::TFrontId  _TFrontId;
      typedef typename TTraits::TNode     _TNode;
      typedef typename TTraits::TNodes    _TNodes;

      typedef std::vector< _TNode > _TQueue;

    public:
      itkTypeMacro( Dijkstra, Base );

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

      virtual   void _InitializeQueue ( );
      virtual   bool _IsQueueEmpty    ( ) const;
      virtual   void _QueuePush       ( const _TNode& n );
      virtual _TNode _QueuePop        ( );
      virtual   void _QueueClear      ( );
      virtual   bool _UpdateNeigh     ( _TNode& nn, const _TNode& n );

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

    private:
      _TQueue m_Queue;
    };

  } // ecapseman

} // ecapseman

#include <fpa/Base/Dijkstra.hxx>

#endif // __FPA__BASE__DIJKSTRA__H__

// eof - $RCSfile$