#ifndef __FPA__BASE__ALGORITHM__H__
#define __FPA__BASE__ALGORITHM__H__
-#include <map>
-#include <vector>
+#include <functional>
+#include <set>
#include <utility>
+#include <vector>
+#include <fpa/Config.h>
#include <fpa/Base/Events.h>
namespace fpa
* vertex could be marked as "visited", "in the front", "not yet there"
* or "freezed".
*
- * @param T Traits used for this algorithm
+ * @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 T, class B >
+ template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare = std::less< _TVertex > >
class Algorithm
- : public B
+ : public _TFilter
{
public:
- // Standard class typdedefs
typedef Algorithm Self;
- typedef B Superclass;
+ typedef _TFilter 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;
+ // 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:
- 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 );
+ itkTypeMacro( Algorithm, _TFilter );
itkBooleanMacro( StopAtOneFront );
- itkBooleanMacro( ThrowEvents );
-
itkGetConstMacro( StopAtOneFront, bool );
- itkGetConstMacro( ThrowEvents, 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;
- /// Seeds manipulation
- void AddSeed( const TVertex& s, const TResult& v );
- const TVertex& GetSeed( const unsigned long& i ) const;
- void ClearSeeds( );
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 );
- /// 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;
+ 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& );
- void operator=( const Self& );
+ Algorithm( const Self& other );
+ Self& operator=( const Self& other );
protected:
- bool m_StopAtOneFront;
- bool m_ThrowEvents;
-
- _TNodes m_Seeds;
- _TMarks m_Marks;
-
- _TCollisionSites m_CollisionSites;
+ TNodes m_Seeds;
+ TCollisions m_Collisions;
+ bool m_StopAtOneFront;
+ bool m_ThrowEvents;
};
} // ecapseman
} // ecapseman
-#include <fpa/Base/Algorithm.hxx>
+#ifndef ITK_MANUAL_INSTANTIATION
+# include <fpa/Base/Algorithm.hxx>
+#endif
#endif // __FPA__BASE__ALGORITHM__H__