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