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

diff --git a/lib/fpa/Base/Algorithm.hxx b/lib/fpa/Base/Algorithm.hxx
index 286343f..26729aa 100644
--- a/lib/fpa/Base/Algorithm.hxx
+++ b/lib/fpa/Base/Algorithm.hxx
@@ -1,300 +1,223 @@
-#ifndef __FPA__BASE__ALGORITHM__HXX__
-#define __FPA__BASE__ALGORITHM__HXX__
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
 
-#include <algorithm>
-#include <limits>
-#include <queue>
+#ifndef __fpa__Base__Algorithm__hxx__
+#define __fpa__Base__Algorithm__hxx__
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-InvokeEvent( const itk::EventObject& e )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+TEvent( )
+  : Superclass( )
 {
-  if( this->m_ThrowEvents )
-    this->Superclass::InvokeEvent( e );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-InvokeEvent( const itk::EventObject& e ) const
+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 )
 {
-  if( this->m_ThrowEvents )
-    this->Superclass::InvokeEvent( e );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-AddSeed( const TVertex& s, const TResult& v )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+~TEvent( )
 {
-  this->m_Seeds.push_back( _TNode( s, v, this->m_Seeds.size( ) ) );
-  this->Modified( );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-const typename fpa::Base::Algorithm< T, B >::
-TVertex& fpa::Base::Algorithm< T, B >::
-GetSeed( const unsigned long& i ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+const char* 
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+GetEventName( ) const
 {
-  return( this->m_Seeds[ i ].Vertex );
+  return( "fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent" );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-ClearSeeds( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+bool
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+CheckEvent( const itk::EventObject* e ) const
 {
-  this->m_Seeds.clear( );
-  this->Modified( );
+  return( dynamic_cast< const Self* >( e ) != NULL );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-unsigned long fpa::Base::Algorithm< T, B >::
-GetNumberOfSeeds( ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+itk::EventObject* 
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+MakeObject( ) const
 {
-  return( this->m_Seeds.size( ) );
+  return( new Self );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-fpa::Base::Algorithm< T, B >::
-Algorithm( )
-  : Superclass( ),
-    m_StopAtOneFront( false ),
-    m_ThrowEvents( false )
+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 T, class B >
-fpa::Base::Algorithm< T, B >::
-~Algorithm( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+InvokeEvent( const itk::EventObject& e ) const
 {
+  TEvent a;
+  if( a.CheckEvent( &e ) )
+  {
+    if( this->m_VisualDebug )
+      this->Superclass::InvokeEvent( e );
+  }
+  else
+    this->Superclass::InvokeEvent( e );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-GenerateData( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+Algorithm( )
+  : Superclass( ),
+    _TMarksInterface( this ),
+    _TSeedsInterface( this ),
+    m_VisualDebug( false )
 {
-  this->AllocateOutputs( );
-
-  unsigned long N = this->m_Seeds.size( );
-  if( N == 0 )
-    return;
-  this->m_CollisionSites.clear( );
-  this->m_CollisionSites.
-    resize( N, _TCollisionSitesRow( N, _TCollision( TVertex( ), false ) ) );
-  this->_BeforeLoop( );
-  this->_Loop( );
-  this->_AfterLoop( );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_BeforeLoop( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+~Algorithm( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_AfterLoop( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+GenerateData( )
 {
-}
+  this->InvokeEvent( itk::StartEvent( ) );
 
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_Loop( )
-{
-  this->_InitializeMarks( );
-  this->_InitializeResults( );
-  this->_InitializeQueue( );
-  while( !( this->_IsQueueEmpty( ) ) )
+  // 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 )
   {
-    _TNode n = this->_QueuePop( );
-    if( this->_IsMarked( n.Vertex ) )
-      continue;
+    this->_QueuePush( *sIt );
+    this->InvokeEvent( TEvent( sIt->Vertex, sIt->FrontId, true ) );
+
+  } // rof
 
-    this->_Mark( n );
-    this->InvokeEvent( TMarkEvent( n ) );
-    if( this->_UpdateResult( n ) )
+  // 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->_CheckStopCondition( ) ) )
+      // 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 )
       {
-        _TNodes N;
-        this->_Neighs( n, N );
-        typename _TNodes::iterator nnIt = N.begin( );
-        while( nnIt != N.end( ) )
+        // Add neighborhood
+        TNeighborhood neighbors = this->_GetNeighbors( node.Vertex );
+        typename TNeighborhood::const_iterator nIt = neighbors.begin( );
+        bool coll = false;
+        while( nIt != neighbors.end( ) && !coll )
         {
-          if( this->_IsMarked( nnIt->Vertex ) )
+          if( this->_IsMarked( *nIt ) )
           {
-            // Update real front identifier
-            nnIt->FrontId = this->_FrontId( nnIt->Vertex );
-
-            // Update collisions
-            if( this->_CheckCollisions( n, *nnIt ) )
+            // Invoke stop at collisions
+            if( this->_Collisions( node.Vertex, *nIt ) )
             {
-              if( this->m_StopAtOneFront )
-              {
-                this->_QueueClear( );
-                nnIt = N.end( );
-
-              } // fi
+              this->_QueueClear( );
+              coll = true;
 
             } // fi
           }
           else
           {
-            if( this->_UpdateNeigh( *nnIt, n ) )
-            {
-              nnIt->Parent = n.Vertex;
-              this->_QueuePush( *nnIt );
-              this->InvokeEvent( TFrontEvent( *nnIt ) );
-
-            } // fi
+            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
-          if( nnIt != N.end( ) )
-            nnIt++;
-
-        } // elihw
-      }
-      else
-        this->_QueueClear( );
-
-    } // fi
-
-  } // elihw
-  this->InvokeEvent( TEndEvent( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_CheckCollisions( const _TNode& a, const _TNode& b )
-{
-  bool ret = false;
-  if( a.FrontId != b.FrontId )
-  {
-    // Mark collision, if it is new
-    bool exists = this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second;
-    exists     &= this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second;
-    if( !exists )
-    {
-      this->m_CollisionSites[ a.FrontId ][ b.FrontId ].first = a.Vertex;
-      this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second = true;
-      this->m_CollisionSites[ b.FrontId ][ a.FrontId ].first = b.Vertex;
-      this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second = true;
-
-      // Stop if one front is desired
-      if( this->m_StopAtOneFront )
-      {
-        // Perform a depth-first iteration on front graph
-        unsigned long N = this->GetNumberOfSeeds( );
-        unsigned long C = 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;
-          C++;
-
-          for( unsigned int n = 0; n < N; ++n )
-            if( this->m_CollisionSites[ f ][ n ].second && !m[ n ] )
-              q.push( n );
+          ++nIt;
 
         } // elihw
-        ret = ( C == N );
 
       } // fi
 
     } // fi
+    this->_FinishOneLoop( );
 
-  } // fi
-  return( ret );
-}
-
-// -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_CheckStopCondition( )
-{
-  return( false );
-}
-
-// -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_UpdateResult( _TNode& n )
-{
-  return( true );
-}
+  } // elihw
 
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_InitializeMarks( )
-{
-  this->m_Marks.clear( );
+  // Finish
+  this->_AfterGenerateData( );
+  this->InvokeEvent( itk::EndEvent( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-bool  fpa::Base::Algorithm< T, B >::
-_IsMarked( const TVertex& v ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_BeforeGenerateData( )
 {
-  return( this->m_Marks.find( v ) != this->m_Marks.end( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-typename fpa::Base::Algorithm< T, B >::
-_TFrontId fpa::Base::Algorithm< T, B >::
-_FrontId( const TVertex& v ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_AfterGenerateData( )
 {
-  typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
-  if( mIt != this->m_Marks.end( ) )
-    return( mIt->second.FrontId );
-  else
-    return( std::numeric_limits< _TFrontId >::max( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-typename fpa::Base::Algorithm< T, B >::
-TVertex fpa::Base::Algorithm< T, B >::
-_Parent( const TVertex& v ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_FinishOneLoop( )
 {
-  typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
-  if( mIt == this->m_Marks.end( ) )
-  {
-    TVertex v;
-    return( v );
-  }
-  else
-    return( mIt->second.Parent );
 }
 
 // -------------------------------------------------------------------------
-template< class T, class B >
-void  fpa::Base::Algorithm< T, B >::
-_Mark( const _TNode& n )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_QueueInit( )
 {
-  this->m_Marks[ n.Vertex ] = n;
+  this->_QueueClear( );
 }
 
-#endif // __FPA__BASE__ALGORITHM__HXX__
+#endif // __fpa__Base__Algorithm__hxx__
 
 // eof - $RCSfile$