-#ifndef __FPA__BASE__ALGORITHM__H__
-#define __FPA__BASE__ALGORITHM__H__
+#ifndef __fpa__Base__Algorithm__h__
+#define __fpa__Base__Algorithm__h__
-#include <functional>
-#include <set>
-#include <utility>
#include <vector>
+#include <itkFunctionBase.h>
#include <fpa/Config.h>
#include <fpa/Base/Events.h>
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 _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 _TVertex, class _TScalar, class _TFilter, class _TVertexCompare = std::less< _TVertex > >
+ template< class _TFilter, class _TVertex, class _TOutput >
class Algorithm
: public _TFilter
{
typedef itk::SmartPointer< Self > Pointer;
typedef itk::SmartPointer< const Self > ConstPointer;
- // Template arguments
- typedef _TVertex TVertex;
- typedef _TScalar TScalar;
- typedef _TFilter TFilter;
- typedef _TVertexCompare TVertexCompare;
-
- // Some useful types
+ typedef _TVertex TVertex;
+ typedef _TOutput TOutput;
typedef unsigned long TFrontId;
+ // Different functions
+ typedef std::vector< TVertex > TNeighborhood;
+ typedef itk::FunctionBase< TVertex, TNeighborhood > TNeighborhoodFunction;
+
// Minigraph to represent collisions
- typedef std::pair< TVertex, bool > TCollision;
+ 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
+ protected:
+ struct _TQueueNode
{
- 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 ) ); }
+ TVertex Vertex;
+ TVertex Parent;
+ TOutput Result;
+ TFrontId FrontId;
+ _TQueueNode( );
+ _TQueueNode( const TVertex& v );
+ _TQueueNode( const TVertex& v, const _TQueueNode& n );
};
- typedef std::set< TNode > TNodes;
- typedef std::vector< TVertex > TVertices;
public:
- itkTypeMacro( Algorithm, _TFilter );
+ itkTypeMacro( Self, _TFilter );
+
+ fpa_Base_NewEvent( TStartEvent );
+ fpa_Base_NewEvent( TEndEvent );
+ fpa_Base_NewEvent( TStartLoopEvent );
+ fpa_Base_NewEvent( TEndLoopEvent );
+ fpa_Base_NewEventWithVertex( TPushEvent, TVertex );
+ fpa_Base_NewEventWithVertex( TPopEvent, TVertex );
+ fpa_Base_NewEventWithVertex( TMarkEvent, TVertex );
+
+ itkGetConstMacro( InitResult, _TOutput );
+ itkSetMacro( InitResult, _TOutput );
itkBooleanMacro( StopAtOneFront );
itkGetConstMacro( StopAtOneFront, 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 );
+ itkGetObjectMacro( NeighborhoodFunction, TNeighborhoodFunction );
+ itkSetObjectMacro( NeighborhoodFunction, TNeighborhoodFunction );
public:
- virtual void InvokeEvent( const itk::EventObject& e );
- virtual void InvokeEvent( const itk::EventObject& e ) const;
-
- 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( );
+ void AddSeed( const TVertex& seed, const TOutput& value );
protected:
- // Methods to extend itk-based architecture
Algorithm( );
virtual ~Algorithm( );
+
virtual void GenerateData( ) fpa_OVERRIDE;
- // Front propagation generic methods
+ // Particular methods
+ virtual bool _ContinueGenerateData( );
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 bool _ValidLoop( ) const;
+ virtual void _UpdateCollisions( const TVertex& a, const TVertex& b );
- virtual TFrontId _GetMark( const TVertex& v ) = 0;
- virtual TFrontId _GetMark( const TNode& v );
-
- 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 );
+ virtual void _InitMarks( ) = 0;
+ virtual void _InitResults( const TOutput& init_value ) = 0;
+ virtual bool _IsMarked( const _TVertex& v ) const = 0;
+ virtual void _Mark( const _TQueueNode& n ) = 0;
+ virtual TFrontId _GetMark( const _TVertex& v ) const = 0;
+ virtual void _UpdateResult( const _TQueueNode& n ) = 0;
+
+ virtual bool _UpdateValue( _TQueueNode& v, const _TQueueNode& p ) = 0;
+ virtual unsigned long _QueueSize( ) const = 0;
+ virtual void _QueueClear( ) = 0;
+ virtual void _QueuePush( const _TQueueNode& node ) = 0;
+ virtual _TQueueNode _QueuePop( ) = 0;
private:
- // Purposely not implemented
+ // Purposely not implemented.
Algorithm( const Self& other );
Self& operator=( const Self& other );
protected:
- TNodes m_Seeds;
+ _TOutput m_InitResult;
+ bool m_StopAtOneFront;
+ typename TNeighborhoodFunction::Pointer m_NeighborhoodFunction;
+ std::vector< _TQueueNode > m_Seeds;
TCollisions m_Collisions;
- bool m_StopAtOneFront;
- bool m_ThrowEvents;
+ unsigned int m_NumberOfFronts;
};
- } // ecapseman
+ } // ecaseman
-} // ecapseman
+} // ecaseman
#ifndef ITK_MANUAL_INSTANTIATION
# include <fpa/Base/Algorithm.hxx>
-#endif
+#endif // ITK_MANUAL_INSTANTIATION
-#endif // __FPA__BASE__ALGORITHM__H__
+#endif // __fpa__Base__Algorithm__h__
// eof - $RCSfile$