#ifndef __FPA__BASE__ALGORITHM__H__
#define __FPA__BASE__ALGORITHM__H__

#include <map>
#include <vector>
#include <utility>
#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 T Traits used for this algorithm
     */
    template< class T, class B >
    class Algorithm
      : public B
    {
    public:
      // Standard class typdedefs
      typedef Algorithm                       Self;
      typedef B                               Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

      /// Templated types
      typedef T TTraits;
      typedef B TBaseFilter;
      typedef typename T::TCost        TCost;
      typedef typename T::TResult      TResult;
      typedef typename T::TVertex      TVertex;
      typedef typename T::TVertexValue TVertexValue;

    protected:
      typedef typename T::TFrontId   _TFrontId;
      typedef typename T::TNode      _TNode;
      typedef typename T::TNodes     _TNodes;
      typedef typename T::TVertexCmp _TVertexCmp;

      typedef std::map< TVertex, _TNode, _TVertexCmp >   _TMarks;

      typedef std::pair< TVertex, bool >         _TCollision;
      typedef std::vector< _TCollision >         _TCollisionSitesRow;
      typedef std::vector< _TCollisionSitesRow > _TCollisionSites;

    public:
      typedef BaseEvent< _TNode >          TEvent;
      typedef FrontEvent< _TNode >         TFrontEvent;
      typedef MarkEvent< _TNode >          TMarkEvent;
      typedef CollisionEvent< _TNode >     TCollisionEvent;
      typedef EndEvent< _TNode >           TEndEvent;
      typedef BacktrackingEvent< TVertex > TBacktrackingEvent;

    public:
      itkTypeMacro( Algorithm, itkProcessObject );

      itkBooleanMacro( StopAtOneFront );
      itkBooleanMacro( ThrowEvents );

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

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

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

      /// Seeds manipulation
      void AddSeed( const TVertex& s, const TResult& v );
      const TVertex& GetSeed( const unsigned long& i ) const;
      void ClearSeeds( );
      unsigned long GetNumberOfSeeds( ) const;

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

      /// itk::ProcessObject
      virtual void GenerateData( );

      /// Base interface
      virtual void _BeforeMainLoop     ( );
      virtual void _AfterMainLoop      ( );
      virtual void _BeforeLoop         ( );
      virtual void _AfterLoop          ( );
      virtual void _Loop               ( );
      virtual bool _CheckCollisions    ( const _TNode& a, const _TNode& b );
      virtual bool _CheckStopCondition ( );
      virtual bool _UpdateResult       ( _TNode& n );

      /// Marks management
      virtual      void _InitializeMarks ( );
      virtual      bool _IsMarked        ( const TVertex& v ) const;
      virtual _TFrontId _FrontId         ( const TVertex& v ) const;
      virtual   TVertex _Parent          ( const TVertex& v ) const;
      virtual      void _Mark            ( const _TNode& n );

      /// Pure virtual interface: vertices
      virtual unsigned long _NumberOfVertices ( ) const = 0;
      virtual  TVertexValue _Value            ( const TVertex& v ) const = 0;
      virtual       TResult _Result           ( const TVertex& v ) const = 0;

      /// Pure virtual interface: edges
      virtual double _Norm ( const TVertex& a, const TVertex& b ) const = 0;
      virtual   bool _Edge ( const TVertex& a, const TVertex& b ) const = 0;
      virtual  TCost _Cost ( const TVertex& a, const TVertex& b ) const = 0;

      /// Pure virtual interface: neighborhood
      virtual void _Neighs      ( const _TNode& n, _TNodes& N ) const = 0;
      virtual bool _UpdateNeigh ( _TNode& nn, const _TNode& n ) = 0;
      virtual void _NeighsInDim ( const _TNode& n,
                                  const unsigned int& d,
                                  _TNodes& N ) = 0;

      /// Pure virtual interface: queue
      virtual   void _InitializeQueue ( ) = 0;
      virtual   bool _IsQueueEmpty    ( ) const = 0;
      virtual   void _QueuePush       ( const _TNode& n ) = 0;
      virtual _TNode _QueuePop        ( ) = 0;
      virtual   void _QueueClear      ( ) = 0;

      /// Pure virtual interface: results
      virtual void _InitializeResults ( ) = 0;

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

    protected:
      bool m_StopAtOneFront;
      bool m_ThrowEvents;

      _TNodes m_Seeds;
      _TMarks m_Marks;

      _TCollisionSites m_CollisionSites;
    };

  } // ecapseman

} // ecapseman

#include <fpa/Base/Algorithm.hxx>

#endif // __FPA__BASE__ALGORITHM__H__

// eof - $RCSfile$