#ifndef __FPA__BASE__ALGORITHM__H__
#define __FPA__BASE__ALGORITHM__H__

#include <functional>
#include <set>
#include <utility>
#include <vector>
#include <fpa/Config.h>
#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 _TVertex Vertex type.
     * @param _TScalar Scalar (real computations) type.
     * @param _TFilter Base class for this algorithm. It should be any
     *                 itk-based filter (itk::ProcessObject).
     * @param _TVertexCompare Vertex lexicographical compare.
     *
     */
    template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare = std::less< _TVertex > >
    class Algorithm
      : public _TFilter
    {
    public:
      typedef Algorithm                       Self;
      typedef _TFilter                        Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

      // Template arguments
      typedef _TVertex        TVertex;
      typedef _TScalar        TScalar;
      typedef _TFilter        TFilter;
      typedef _TVertexCompare TVertexCompare;

      // Some useful types
      typedef unsigned long TFrontId;

      // Minigraph to represent collisions
      typedef std::pair< TVertex, bool >    TCollision;
      typedef std::vector< TCollision >     TCollisionsRow;
      typedef std::vector< TCollisionsRow > TCollisions;

      enum TNodeLabel
      {
        FarLabel = 0,
        FrontLabel,
        AliveLabel
      };

      /**
       * WARNING: std::set< T > objects are immutable
       */
      struct TNode
      {
        static const TVertexCompare VertexCompare;
        TVertex            Vertex;
        mutable TVertex    Parent;
        mutable TScalar    Result;
        mutable TFrontId   FrontId;
        mutable TNodeLabel Label;
        bool operator<( const TNode& other ) const
          { return( VertexCompare( this->Vertex, other.Vertex ) ); }
      };
      typedef std::set< TNode >      TNodes;
      typedef std::vector< TVertex > TVertices;

    public:
      itkTypeMacro( Algorithm, _TFilter );

      itkBooleanMacro( StopAtOneFront );
      itkGetConstMacro( StopAtOneFront, bool );
      itkSetMacro( StopAtOneFront, bool );

      itkBooleanMacro( ThrowEvents );
      itkGetConstMacro( ThrowEvents, bool );
      itkSetMacro( ThrowEvents, bool );

      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( TCollisionEvent, TVertex );
      fpa_Base_NewEventWithVertex( TAliveEvent, TVertex );
      fpa_Base_NewEventWithVertex( TFrontEvent, TVertex );
      fpa_Base_NewEventWithVertex( TFreezeEvent, TVertex );
      fpa_Base_NewEventWithVertex( TBacktrackingEvent, TVertex );

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

      unsigned long GetNumberOfSeeds( ) const;
      void AddSeed( const TVertex& s, const TScalar& v = TScalar( 0 ) );
      void AddSeed( const TNode& n );
      void RemoveSeed( const TVertex& s );
      void RemoveAllSeeds( );

    protected:
      // Methods to extend itk-based architecture
      Algorithm( );
      virtual ~Algorithm( );
      virtual void GenerateData( ) fpa_OVERRIDE;

      // Front propagation generic methods
      virtual void _Loop( );

      // Front propagation methods to be overloaded
      virtual void _BeforeGenerateData( );
      virtual void _AfterGenerateData( );
      virtual void _BeforeLoop( );
      virtual void _AfterLoop( );

      virtual void _InitMarks( ) = 0;
      virtual void _InitResults( ) = 0;
      virtual void _DeallocateAuxiliary( ) = 0;

      virtual TFrontId _GetMark( const TVertex& v ) = 0;
      virtual TFrontId _GetMark( const TNode& v );

      virtual void _Visit( const TNode& n ) = 0;
      virtual bool _NeedToStop( );

      virtual TVertices _GetNeighborhood( const TVertex& v ) const = 0;
      virtual TVertices _GetNeighborhood( const TNode& n ) const;

      virtual bool _Result( TNode& node, const TNode& parent ) = 0;

      virtual void  _QueueClear( ) = 0;
      virtual void  _QueuePush( const TNode& node ) = 0;
      virtual TNode _QueuePop( ) = 0;
      virtual bool  _IsQueueEmpty( ) const = 0;

      virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );

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

    protected:
      TNodes      m_Seeds;
      TCollisions m_Collisions;
      bool        m_StopAtOneFront;
      bool        m_ThrowEvents;
    };

  } // ecapseman

} // ecapseman

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

#endif // __FPA__BASE__ALGORITHM__H__

// eof - $RCSfile$