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
  59     public:
  60       itkTypeMacro( Algorithm, itkProcessObject );
  61
  62       itkBooleanMacro( StopAtOneFront );
  63       itkBooleanMacro( ThrowEvents );
  64
  65       itkGetConstMacro( StopAtOneFront, bool );
  66       itkGetConstMacro( ThrowEvents, bool );
  67
  68       itkSetMacro( StopAtOneFront, bool );
  69       itkSetMacro( ThrowEvents, bool );
  70
  71     public:
  72       virtual void InvokeEvent( const itk::EventObject& e );
  73       virtual void InvokeEvent( const itk::EventObject& e ) const;
  74
  75       /// Seeds manipulation
  76       void AddSeed( const TVertex& s, const TResult& v );
  77       const TVertex& GetSeed( const unsigned long& i ) const;
  78       void ClearSeeds( );
  79       unsigned long GetNumberOfSeeds( ) const;
  80
  81     protected:
  82       Algorithm( );
  83       virtual ~Algorithm( );
  84
  85       /// itk::ProcessObject
  86       virtual void GenerateData( );
  87
  88       /// Base interface
  89       virtual void _BeforeMainLoop     ( );
  90       virtual void _AfterMainLoop      ( );
  91       virtual void _BeforeLoop         ( );
  92       virtual void _AfterLoop          ( );
  93       virtual void _Loop               ( );
  94       virtual bool _CheckCollisions    ( const _TNode& a, const _TNode& b );
  95       virtual bool _CheckStopCondition ( );
  96       virtual bool _UpdateResult       ( _TNode& n );
  97
  98       /// Marks management
  99       virtual      void _InitializeMarks ( );
 100       virtual      bool _IsMarked        ( const TVertex& v ) const;
 101       virtual _TFrontId _FrontId         ( const TVertex& v ) const;
 102       virtual   TVertex _Parent          ( const TVertex& v ) const;
 103       virtual      void _Mark            ( const _TNode& n );
 104
 105       /// Pure virtual interface: vertices
 106       virtual unsigned long _NumberOfVertices ( ) const = 0;
 107       virtual  TVertexValue _Value            ( const TVertex& v ) const = 0;
 108       virtual       TResult _Result           ( const TVertex& v ) const = 0;
 109
 110       /// Pure virtual interface: edges
 111       virtual double _Norm ( const TVertex& a, const TVertex& b ) const = 0;
 112       virtual   bool _Edge ( const TVertex& a, const TVertex& b ) const = 0;
 113       virtual  TCost _Cost ( const TVertex& a, const TVertex& b ) const = 0;
 114
 115       /// Pure virtual interface: neighborhood
 116       virtual void _Neighs      ( const _TNode& n, _TNodes& N ) const = 0;
 117       virtual bool _UpdateNeigh ( _TNode& nn, const _TNode& n ) = 0;
 118       virtual void _NeighsInDim ( const _TNode& n,
 119                                   const unsigned int& d,
 120                                   _TNodes& N ) = 0;
 121
 122       /// Pure virtual interface: queue
 123       virtual   void _InitializeQueue ( ) = 0;
 124       virtual   bool _IsQueueEmpty    ( ) const = 0;
 125       virtual   void _QueuePush       ( const _TNode& n ) = 0;
 126       virtual _TNode _QueuePop        ( ) = 0;
 127       virtual   void _QueueClear      ( ) = 0;
 128
 129       /// Pure virtual interface: results
 130       virtual void _InitializeResults ( ) = 0;
 131
 132     private:
 133       // Purposely not implemented
 134       Algorithm( const Self& );
 135       void operator=( const Self& );
 136
 137     protected:
 138       bool m_StopAtOneFront;
 139       bool m_ThrowEvents;
 140
 141       _TNodes m_Seeds;
 142       _TMarks m_Marks;
 143
 144       _TCollisionSites m_CollisionSites;
 145     };
 146
 147   } // ecapseman
 148
 149 } // ecapseman
 150
 151 #include <fpa/Base/Algorithm.hxx>
 152
 153 #endif // __FPA__BASE__ALGORITHM__H__
 154
 155 // eof - $RCSfile$