lib/fpa/Base/Algorithm.h

   1 #ifndef __FPA__BASE__ALGORITHM__H__
   2 #define __FPA__BASE__ALGORITHM__H__
   3
   4 #include <map>
   5 #include <vector>
   6 #include <utility>
   7 #include <fpa/Base/Events.h>
   8
   9 namespace fpa
  10 {
  11   namespace Base
  12   {
  13     /**
  14      * Base front propagation algorithm. From a series of start seeds with
  15      * costs, a priority queue is filled and emptied updating costs. Each
  16      * vertex could be marked as "visited", "in the front", "not yet there"
  17      * or "freezed".
  18      *
  19      * @param T Traits used for this algorithm
  20      */
  21     template< class T, class B >
  22     class Algorithm
  23       : public B
  24     {
  25     public:
  26       // Standard class typdedefs
  27       typedef Algorithm                       Self;
  28       typedef B                               Superclass;
  29       typedef itk::SmartPointer< Self >       Pointer;
  30       typedef itk::SmartPointer< const Self > ConstPointer;
  31
  32       /// Templated types
  33       typedef T TTraits;
  34       typedef B TBaseFilter;
  35       typedef typename T::TCost        TCost;
  36       typedef typename T::TResult      TResult;
  37       typedef typename T::TVertex      TVertex;
  38       typedef typename T::TVertexValue TVertexValue;
  39
  40     protected:
  41       typedef typename T::TFrontId   _TFrontId;
  42       typedef typename T::TNode      _TNode;
  43       typedef typename T::TNodes     _TNodes;
  44       typedef typename T::TVertexCmp _TVertexCmp;
  45
  46       typedef std::map< TVertex, _TNode, _TVertexCmp >   _TMarks;
  47
  48       typedef std::pair< TVertex, bool >         _TCollision;
  49       typedef std::vector< _TCollision >         _TCollisionSitesRow;
  50       typedef std::vector< _TCollisionSitesRow > _TCollisionSites;
  51
  52     public:
  53       typedef BaseEvent< _TNode >          TEvent;
  54       typedef FrontEvent< _TNode >         TFrontEvent;
  55       typedef MarkEvent< _TNode >          TMarkEvent;
  56       typedef CollisionEvent< _TNode >     TCollisionEvent;
  57       typedef EndEvent< _TNode >           TEndEvent;
  58       typedef BacktrackingEvent< TVertex > TBacktrackingEvent;
  59
  60     public:
  61       itkTypeMacro( Algorithm, itkProcessObject );
  62
  63       itkBooleanMacro( StopAtOneFront );
  64       itkBooleanMacro( ThrowEvents );
  65
  66       itkGetConstMacro( StopAtOneFront, bool );
  67       itkGetConstMacro( ThrowEvents, bool );
  68
  69       itkSetMacro( StopAtOneFront, bool );
  70       itkSetMacro( ThrowEvents, bool );
  71
  72     public:
  73       virtual void InvokeEvent( const itk::EventObject& e );
  74       virtual void InvokeEvent( const itk::EventObject& e ) const;
  75
  76       /// Seeds manipulation
  77       void AddSeed( const TVertex& s, const TResult& v );
  78       const TVertex& GetSeed( const unsigned long& i ) const;
  79       void ClearSeeds( );
  80       unsigned long GetNumberOfSeeds( ) const;
  81
  82     protected:
  83       Algorithm( );
  84       virtual ~Algorithm( );
  85
  86       /// itk::ProcessObject
  87       virtual void GenerateData( );
  88
  89       /// Base interface
  90       virtual void _BeforeMainLoop     ( );
  91       virtual void _AfterMainLoop      ( );
  92       virtual void _BeforeLoop         ( );
  93       virtual void _AfterLoop          ( );
  94       virtual void _Loop               ( );
  95       virtual bool _CheckCollisions    ( const _TNode& a, const _TNode& b );
  96       virtual bool _CheckStopCondition ( );
  97       virtual bool _UpdateResult       ( _TNode& n );
  98
  99       /// Marks management
 100       virtual      void _InitializeMarks ( );
 101       virtual      bool _IsMarked        ( const TVertex& v ) const;
 102       virtual _TFrontId _FrontId         ( const TVertex& v ) const;
 103       virtual   TVertex _Parent          ( const TVertex& v ) const;
 104       virtual      void _Mark            ( const _TNode& n );
 105
 106       /// Pure virtual interface: vertices
 107       virtual unsigned long _NumberOfVertices ( ) const = 0;
 108       virtual  TVertexValue _Value            ( const TVertex& v ) const = 0;
 109       virtual       TResult _Result           ( const TVertex& v ) const = 0;
 110
 111       /// Pure virtual interface: edges
 112       virtual double _Norm ( const TVertex& a, const TVertex& b ) const = 0;
 113       virtual   bool _Edge ( const TVertex& a, const TVertex& b ) const = 0;
 114       virtual  TCost _Cost ( const TVertex& a, const TVertex& b ) const = 0;
 115
 116       /// Pure virtual interface: neighborhood
 117       virtual void _Neighs      ( const _TNode& n, _TNodes& N ) const = 0;
 118       virtual bool _UpdateNeigh ( _TNode& nn, const _TNode& n ) = 0;
 119       virtual void _NeighsInDim ( const _TNode& n,
 120                                   const unsigned int& d,
 121                                   _TNodes& N ) = 0;
 122
 123       /// Pure virtual interface: queue
 124       virtual   void _InitializeQueue ( ) = 0;
 125       virtual   bool _IsQueueEmpty    ( ) const = 0;
 126       virtual   void _QueuePush       ( const _TNode& n ) = 0;
 127       virtual _TNode _QueuePop        ( ) = 0;
 128       virtual   void _QueueClear      ( ) = 0;
 129
 130       /// Pure virtual interface: results
 131       virtual void _InitializeResults ( ) = 0;
 132
 133     private:
 134       // Purposely not implemented
 135       Algorithm( const Self& );
 136       void operator=( const Self& );
 137
 138     protected:
 139       bool m_StopAtOneFront;
 140       bool m_ThrowEvents;
 141
 142       _TNodes m_Seeds;
 143       _TMarks m_Marks;
 144
 145       _TCollisionSites m_CollisionSites;
 146     };
 147
 148   } // ecapseman
 149
 150 } // ecapseman
 151
 152 #include <fpa/Base/Algorithm.hxx>
 153
 154 #endif // __FPA__BASE__ALGORITHM__H__
 155
 156 // eof - $RCSfile$