#ifndef __FPA__BASE__ALGORITHM__H__
#define __FPA__BASE__ALGORITHM__H__

#include <map>
#include <utility>
#include <vector>
#include <fpa/Base/Events.h>

namespace fpa
{
  namespace Base
  {
    /**
     * Base front propagation algorithm. From a series of start seeds with
     * costs, a priority queue is filled and emptied updating costs. Each
     * vertex could be marked as "visited", "in the front", "not yet there"
     * or "freezed".
     *
     * @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 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 B >
    class Algorithm
      : public B
    {
    public:
      typedef Algorithm                       Self;
      typedef B                               Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

      typedef V  TVertex;
      typedef C  TValue;
      typedef R  TResult;
      typedef S  TSpace;
      typedef VC TVertexCompare;

      fpa_Base_NewEvent( TStartEvent );
      fpa_Base_NewEvent( TStartLoopEvent );
      fpa_Base_NewEvent( TStartBacktrackingEvent );
      fpa_Base_NewEvent( TEndEvent );
      fpa_Base_NewEvent( TEndLoopEvent );
      fpa_Base_NewEvent( TEndBacktrackingEvent );
      fpa_Base_NewEventWithVertex( TAliveEvent, TVertex );
      fpa_Base_NewEventWithVertex( TFrontEvent, TVertex );
      fpa_Base_NewEventWithVertex( TFreezeEvent, TVertex );
      fpa_Base_NewEventWithVertex( TBacktrackingEvent, TVertex );

    protected:
      typedef std::vector< TVertex >         _TVertices;
      typedef std::pair< TVertex, bool >     _TCollision;
      typedef std::vector< _TCollision >     _TCollisionsRow;
      typedef std::vector< _TCollisionsRow > _TCollisions;

      /**
       */
      enum _TNodeLabel
      {
        FarLabel = 0,
        FrontLabel,
        AliveLabel
      };

      /**
       */
      class _TNode
      {
      public:
        _TNode( );
        virtual ~_TNode( );

      public:
        TVertex Parent;
        TResult Result;
        short   FrontId;
        char    Label;
      };
      typedef std::map< TVertex, _TNode, TVertexCompare > _TNodes;

    public:
      itkTypeMacro( Algorithm, B );

      itkBooleanMacro( ThrowEvents );
      itkBooleanMacro( StopAtOneFront );

      itkGetConstMacro( ThrowEvents, bool );
      itkGetConstMacro( StopAtOneFront, bool );

      itkSetMacro( ThrowEvents, bool );
      itkSetMacro( StopAtOneFront, bool );

    public:
      virtual void InvokeEvent( const itk::EventObject& e );
      virtual void InvokeEvent( const itk::EventObject& e ) const;

      void AddSeed( const TVertex& s, const TResult& r );
      const TVertex& GetSeed( const unsigned int& id ) const;
      void ClearSeeds( );
      unsigned long GetNumberOfSeeds( ) const;

    protected:
      Algorithm( );
      virtual ~Algorithm( );

      // Connection with itk's pipeline
      virtual void GenerateData( );

      // Main loop algorithm
      virtual void _Loop( );

      // Supporting methods for loop
      virtual void _BeforeGenerateData( );
      virtual void _AfterGenerateData( );
      virtual void _BeforeLoop( );
      virtual void _AfterLoop( );

      // Methods to control forced stops
      virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
      virtual bool _NeedToStop( ) const;

      // Graph-related abstract methods
      virtual unsigned long _NumberOfVertices( ) const = 0;
      virtual const TValue& _VertexValue( const TVertex& v ) const = 0;
      virtual double _Distance(
        const TVertex& a, const TVertex& b
        ) const = 0;
      virtual bool _HasEdge( const TVertex& a, const TVertex& b ) const = 0;
      virtual void _Neighborhood(
        _TVertices& neighborhood, const TVertex& v
        ) const = 0;

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

      // Marks-related abstract methods
      virtual _TNode& _Node( const TVertex& v );
      virtual const _TNode& _Node( const TVertex& v ) const;
      virtual void _InitMarks( );
      virtual void _Mark( const TVertex& v, const _TNode& node );

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

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

    protected:
      bool         m_ThrowEvents;
      bool         m_StopAtOneFront;
      _TNodes      m_Seeds;
      _TVertices   m_SeedVertices;
      _TNodes      m_Marks;
      _TCollisions m_Collisions;
    };

  } // ecapseman

} // ecapseman

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

#endif // __FPA__BASE__ALGORITHM__H__

// eof - $RCSfile$