X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FAlgorithm.hxx;h=26729aaa37e77fdad63c16d4d207fa7bf66e9ba7;hb=89393f2267e42e921571c0184320d6c6382f34ab;hp=30f42b7008e29eb45cd98bcd17bfb78afc36da3e;hpb=6585142e69f2ff5e4fceb21320ab3795c3e82218;p=FrontAlgorithms.git

diff --git a/lib/fpa/Base/Algorithm.hxx b/lib/fpa/Base/Algorithm.hxx
index 30f42b7..26729aa 100644
--- a/lib/fpa/Base/Algorithm.hxx
+++ b/lib/fpa/Base/Algorithm.hxx
@@ -1,245 +1,221 @@
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
+
 #ifndef __fpa__Base__Algorithm__hxx__
 #define __fpa__Base__Algorithm__hxx__
 
-#include <queue>
+// -------------------------------------------------------------------------
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+TEvent( )
+  : Superclass( )
+{
+}
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
-_TQueueNode( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+TEvent( const TVertex& v, unsigned long fid, bool intoq )
+  : Superclass( ),
+    Vertex( v ),
+    FrontId( fid ),
+    IntoQueue( intoq )
 {
-  this->Vertex.Fill( 0 );
-  this->Parent.Fill( 0 );
-  this->Result = _TOutput( 0 );
-  this->FrontId = 0;
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
-_TQueueNode( const _TVertex& v )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+~TEvent( )
 {
-  this->Vertex = v;
-  this->Parent = v;
-  this->Result = _TOutput( 0 );
-  this->FrontId = 0;
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
-_TQueueNode( const _TVertex& v, const _TQueueNode& n )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+const char* 
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+GetEventName( ) const
 {
-  this->Vertex = v;
-  this->Parent = n.Vertex;
-  this->Result = n.Result;
-  this->FrontId = n.FrontId;
+  return( "fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent" );
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-AddSeed( const _TVertex& seed, const TOutput& value )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+bool
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+CheckEvent( const itk::EventObject* e ) const
 {
-  _TQueueNode node( seed );
-  node.FrontId = this->m_Seeds.size( ) + 1;
-  node.Result = value;
-  this->m_Seeds.push_back( node );
-  this->Modified( );
+  return( dynamic_cast< const Self* >( e ) != NULL );
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-Algorithm( )
-  : Superclass( ),
-    m_InitResult( _TOutput( 0 ) ),
-    m_StopAtOneFront( false )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+itk::EventObject* 
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+MakeObject( ) const
 {
+  return( new Self );
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-~Algorithm( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+InvokeEvent( const itk::EventObject& e )
 {
+  TEvent a;
+  if( a.CheckEvent( &e ) )
+  {
+    if( this->m_VisualDebug )
+      this->Superclass::InvokeEvent( e );
+  }
+  else
+    this->Superclass::InvokeEvent( e );
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-GenerateData( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+InvokeEvent( const itk::EventObject& e ) const
 {
-  this->InvokeEvent( TStartEvent( ) );
-  this->_BeforeGenerateData( );
-  this->m_NumberOfFronts = this->m_Seeds.size( );
-  if( this->m_NumberOfFronts > 0 )
+  TEvent a;
+  if( a.CheckEvent( &e ) )
   {
-    // Prepare collisions
-    TCollision coll( TVertex( ), false );
-    TCollisionsRow row( this->m_NumberOfFronts, coll );
-    this->m_Collisions.clear( );
-    this->m_Collisions.resize( this->m_NumberOfFronts, row );
-
-    // Put seeds on queue
-    this->_QueueClear( );
-    for(
-      auto nIt = this->m_Seeds.begin( );
-      nIt != this->m_Seeds.end( );
-      ++nIt
-      )
-      this->_QueuePush( *nIt );
-
-    // Init marks and results
-    this->_InitMarks( );
-    this->_InitResults( this->m_InitResult );
-
-    // Main loop
-    do
-      this->_Loop( );
-    while( this->_ContinueGenerateData( ) );
-
-  } // fi
-  this->_AfterGenerateData( );
-  this->InvokeEvent( TEndEvent( ) );
+    if( this->m_VisualDebug )
+      this->Superclass::InvokeEvent( e );
+  }
+  else
+    this->Superclass::InvokeEvent( e );
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_ContinueGenerateData( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+Algorithm( )
+  : Superclass( ),
+    _TMarksInterface( this ),
+    _TSeedsInterface( this ),
+    m_VisualDebug( false )
 {
-  return( false );
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_Loop( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+~Algorithm( )
 {
-  this->InvokeEvent( TStartLoopEvent( ) );
-  this->_BeforeLoop( );
-  while( this->_ValidLoop( ) )
+}
+
+// -------------------------------------------------------------------------
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+GenerateData( )
+{
+  this->InvokeEvent( itk::StartEvent( ) );
+
+  // Init objects
+  this->_BeforeGenerateData( );
+  this->_ConfigureOutput( this->m_InitValue );
+  this->_InitMarks( this->GetSeeds( ).size( ) );
+  TNodes seeds = this->_UnifySeeds( );
+  this->_PrepareSeeds( seeds );
+
+  // Init queue
+  this->_QueueInit( );
+  typename TNodes::const_iterator sIt = seeds.begin( );
+  for( ; sIt != seeds.end( ); ++sIt )
   {
-    _TQueueNode node = this->_QueuePop( );
-    this->InvokeEvent( TPopEvent( node.Vertex, node.FrontId ) );
-
-    // Process actual vertex
-    if( this->_IsMarked( node.Vertex ) )
-      continue;
-    this->_Mark( node );
-    this->_UpdateResult( node );
-    this->InvokeEvent( TMarkEvent( node.Vertex, node.FrontId ) );
-
-    // Add neighbors to queue
-    TNeighborhood neighs = this->m_NeighborhoodFunction->Evaluate( node.Vertex );
-    for( auto it = neighs.begin( ); it != neighs.end( ); ++it )
+    this->_QueuePush( *sIt );
+    this->InvokeEvent( TEvent( sIt->Vertex, sIt->FrontId, true ) );
+
+  } // rof
+
+  // Main loop
+  while( this->_QueueSize( ) > 0 )
+  {
+    // Get next candidate
+    TNode node = this->_QueuePop( );
+    this->InvokeEvent( TEvent( node.Vertex, node.FrontId, false ) );
+    if( !( this->_IsMarked( node.Vertex ) ) )
     {
-      if( !( this->_IsMarked( *it ) ) )
+      // Update output value and mark vertex
+      this->_UpdateOutputValue( node );
+      this->_Mark( node.Vertex, node.FrontId );
+
+      // The actual node was effectively marked?
+      if( node.FrontId > 0 )
       {
-        _TQueueNode neigh( *it, node );
-        if( this->_UpdateValue( neigh, node ) )
+        // Add neighborhood
+        TNeighborhood neighbors = this->_GetNeighbors( node.Vertex );
+        typename TNeighborhood::const_iterator nIt = neighbors.begin( );
+        bool coll = false;
+        while( nIt != neighbors.end( ) && !coll )
         {
-          this->_QueuePush( neigh );
-          this->InvokeEvent( TPushEvent( node.Vertex, node.FrontId ) );
-
-        } // fi
-      }
-      else
-        this->_UpdateCollisions( node.Vertex, *it );
-
-    } // rof
+          if( this->_IsMarked( *nIt ) )
+          {
+            // Invoke stop at collisions
+            if( this->_Collisions( node.Vertex, *nIt ) )
+            {
+              this->_QueueClear( );
+              coll = true;
+
+            } // fi
+          }
+          else
+          {
+            TNode nnode;
+            nnode.Vertex = *nIt;
+            nnode.Parent = node.Vertex;
+            nnode.FrontId = node.FrontId;
+            this->_ComputeOutputValue( nnode );
+            this->_QueuePush( nnode );
+            this->InvokeEvent( TEvent( nnode.Vertex, nnode.FrontId, true ) );
+
+          } // fi
+          ++nIt;
+
+        } // elihw
+
+      } // fi
+
+    } // fi
+    this->_FinishOneLoop( );
 
   } // elihw
-  this->_AfterLoop( );
-  this->InvokeEvent( TEndLoopEvent( ) );
+
+  // Finish
+  this->_AfterGenerateData( );
+  this->InvokeEvent( itk::EndEvent( ) );
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
 _BeforeGenerateData( )
 {
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
 _AfterGenerateData( )
 {
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_BeforeLoop( )
-{
-}
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_AfterLoop( )
-{
-}
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_ValidLoop( ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_FinishOneLoop( )
 {
-  bool r = ( this->_QueueSize( ) > 0 );
-  if( this->m_StopAtOneFront )
-    r &= ( this->m_NumberOfFronts > 0 );
-  return( r );
 }
 
 // -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_UpdateCollisions( const TVertex& a, const TVertex& b )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_QueueInit( )
 {
-  auto ma = this->_GetMark( a );
-  auto mb = this->_GetMark( b );
-  if( ma == mb || ma == 0 || mb == 0 )
-    return;
-
-  // Mark collision, if it is new
-  ma--; mb--;
-  bool ret = false;
-  bool exists = this->m_Collisions[ ma ][ mb ].second;
-  exists     &= this->m_Collisions[ mb ][ ma ].second;
-  if( !exists )
-  {
-    this->m_Collisions[ ma ][ mb ].first = a;
-    this->m_Collisions[ ma ][ mb ].second = true;
-    this->m_Collisions[ mb ][ ma ].first = b;
-    this->m_Collisions[ mb ][ ma ].second = true;
-
-    // Update number of fronts
-    unsigned long N = this->m_Seeds.size( );
-    unsigned long count = 0;
-    std::vector< bool > m( N, false );
-    std::queue< unsigned long > q;
-    q.push( 0 );
-    while( !q.empty( ) )
-    {
-      unsigned long f = q.front( );
-      q.pop( );
-
-      if( m[ f ] )
-        continue;
-      m[ f ] = true;
-      count++;
-
-      for( unsigned int n = 0; n < N; ++n )
-        if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
-          q.push( n );
-
-    } // elihw
-    this->m_NumberOfFronts = N - count;
-
-  } // fi
+  this->_QueueClear( );
 }
 
 #endif // __fpa__Base__Algorithm__hxx__