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

diff --git a/lib/fpa/Base/Algorithm.hxx b/lib/fpa/Base/Algorithm.hxx
index eb30758..26729aa 100644
--- a/lib/fpa/Base/Algorithm.hxx
+++ b/lib/fpa/Base/Algorithm.hxx
@@ -1,312 +1,223 @@
-#ifndef __FPA__BASE__ALGORITHM__HXX__
-#define __FPA__BASE__ALGORITHM__HXX__
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
 
-#include <queue>
+#ifndef __fpa__Base__Algorithm__hxx__
+#define __fpa__Base__Algorithm__hxx__
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-fpa::Base::Algorithm< V, C, R, B >::_TNode::
-_TNode( )
-  : Result( TResult( 0 ) ),
-    FrontId( -1 ),
-    Label( Self::FarLabel )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+TEvent( )
+  : Superclass( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-fpa::Base::Algorithm< V, C, R, B >::_TNode::
-~_TNode( )
+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 )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-InvokeEvent( const itk::EventObject& e )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+~TEvent( )
 {
-  if( this->m_ThrowEvents )
-    this->Superclass::InvokeEvent( e );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-InvokeEvent( const itk::EventObject& e ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+const char* 
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+GetEventName( ) const
 {
-  if( this->m_ThrowEvents )
-    this->Superclass::InvokeEvent( e );
+  return( "fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent" );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-AddSeed( const TVertex& s, const TResult& r )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+bool
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+CheckEvent( const itk::EventObject* e ) const
 {
-  _TNode ns;
-  ns.Vertex = s;
-  ns.Parent = s;
-  ns.Result = r;
-  ns.FrontId = this->m_Seeds.size( );
-  ns.Label = Self::FrontLabel;
-  this->m_Seeds.push_back( ns );
-  this->Modified( );
+  return( dynamic_cast< const Self* >( e ) != NULL );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-const typename fpa::Base::Algorithm< V, C, R, B >::
-TVertex& fpa::Base::Algorithm< V, C, R, B >::
-GetSeed( const unsigned int& id ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+itk::EventObject* 
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+MakeObject( ) const
 {
-  return( this->m_Seeds[ id ].Vertex );
+  return( new Self );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-ClearSeeds( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+InvokeEvent( const itk::EventObject& e )
 {
-  this->m_Seeds.clear( );
-  this->Modified( );
+  TEvent a;
+  if( a.CheckEvent( &e ) )
+  {
+    if( this->m_VisualDebug )
+      this->Superclass::InvokeEvent( e );
+  }
+  else
+    this->Superclass::InvokeEvent( e );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-unsigned long fpa::Base::Algorithm< V, C, R, B >::
-GetNumberOfSeeds( ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+InvokeEvent( const itk::EventObject& e ) const
 {
-  return( this->m_Seeds.size( ) );
+  TEvent a;
+  if( a.CheckEvent( &e ) )
+  {
+    if( this->m_VisualDebug )
+      this->Superclass::InvokeEvent( e );
+  }
+  else
+    this->Superclass::InvokeEvent( e );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-fpa::Base::Algorithm< V, C, R, B >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
 Algorithm( )
   : Superclass( ),
-    m_ThrowEvents( false ),
-    m_StopAtOneFront( false )
+    _TMarksInterface( this ),
+    _TSeedsInterface( this ),
+    m_VisualDebug( false )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-fpa::Base::Algorithm< V, C, R, B >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
 ~Algorithm( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
 GenerateData( )
 {
-  unsigned long N = this->m_Seeds.size( );
-  if( N == 0 )
-    return;
+  this->InvokeEvent( itk::StartEvent( ) );
 
-  this->InvokeEvent( TStartEvent( ) );
+  // 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 )
+  {
+    this->_QueuePush( *sIt );
+    this->InvokeEvent( TEvent( sIt->Vertex, sIt->FrontId, true ) );
 
-  this->m_Collisions.clear( );
-  this->m_Collisions.
-    resize( N, _TCollisionsRow( N, _TCollision( TVertex( ), false ) ) );
-  this->_InitResults( );
-  this->_InitMarks( );
-  this->_InitQueue( );
-  this->_Loop( );
-  this->_AfterGenerateData( );
-  this->InvokeEvent( TEndEvent( ) );
-}
+  } // rof
 
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-_Loop( )
-{
-  this->InvokeEvent( TStartLoopEvent( ) );
-  this->_BeforeLoop( );
-  while( !( this->_IsQueueEmpty( ) ) )
+  // Main loop
+  while( this->_QueueSize( ) > 0 )
   {
     // Get next candidate
-    _TNode candidate = this->_QueuePop( );
-    if( this->_Node( candidate.Vertex ).Label == Self::AliveLabel )
-      continue;
-
-    // Mark it as "Alive" and update final result
-    candidate.Label = Self::AliveLabel;
-    this->_Mark( candidate );
-    this->_SetResult( candidate.Vertex, candidate.Result );
-    this->InvokeEvent( TAliveEvent( candidate.Vertex, candidate.FrontId ) );
-
-    // Check if a forced stop condition arises
-    if( !( this->_NeedToStop( ) ) )
+    TNode node = this->_QueuePop( );
+    this->InvokeEvent( TEvent( node.Vertex, node.FrontId, false ) );
+    if( !( this->_IsMarked( node.Vertex ) ) )
     {
-      // Compute neighborhood
-      _TVertices neighborhood;
-      this->_Neighborhood( neighborhood, candidate.Vertex );
+      // Update output value and mark vertex
+      this->_UpdateOutputValue( node );
+      this->_Mark( node.Vertex, node.FrontId );
 
-      // Iterate over neighbors
-      typename _TVertices::iterator nIt = neighborhood.begin( );
-      while( nIt != neighborhood.end( ) )
+      // The actual node was effectively marked?
+      if( node.FrontId > 0 )
       {
-        _TNode neighbor = this->_Node( *nIt );
-        neighbor.Vertex = *nIt;
-        if( neighbor.Label == Self::AliveLabel )
+        // Add neighborhood
+        TNeighborhood neighbors = this->_GetNeighbors( node.Vertex );
+        typename TNeighborhood::const_iterator nIt = neighbors.begin( );
+        bool coll = false;
+        while( nIt != neighbors.end( ) && !coll )
         {
-          // Update collisions
-          if( this->_UpdateCollisions( candidate.Vertex, *nIt ) )
+          if( this->_IsMarked( *nIt ) )
           {
-            this->_QueueClear( );
-            nIt = neighborhood.end( );
-            continue;
+            // Invoke stop at collisions
+            if( this->_Collisions( node.Vertex, *nIt ) )
+            {
+              this->_QueueClear( );
+              coll = true;
 
-          } // fi
-        }
-        else
-        {
-          // Add new candidate to queue
-          if(
-            this->_ComputeNeighborResult(
-              neighbor.Result, *nIt, candidate.Vertex
-              )
-            )
-          {
-            neighbor.FrontId = candidate.FrontId;
-            neighbor.Parent = candidate.Vertex;
-            neighbor.Label = Self::FrontLabel;
-            this->_QueuePush( neighbor );
-            this->_Mark( neighbor );
-            this->InvokeEvent( TFrontEvent( *nIt, candidate.FrontId ) );
+            } // fi
           }
           else
-            this->InvokeEvent( TFreezeEvent( *nIt, candidate.FrontId ) );
+          {
+            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;
+          } // fi
+          ++nIt;
 
-      } // elihw
-    }
-    else
-      this->_QueueClear( );
+        } // elihw
 
-  } // elihw
-  this->_AfterLoop( );
-  this->InvokeEvent( TEndLoopEvent( ) );
-}
+      } // fi
 
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-_BeforeGenerateData( )
-{
-}
+    } // fi
+    this->_FinishOneLoop( );
 
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-_AfterGenerateData( )
-{
-}
+  } // elihw
 
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-_BeforeLoop( )
-{
+  // Finish
+  this->_AfterGenerateData( );
+  this->InvokeEvent( itk::EndEvent( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-_AfterLoop( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_BeforeGenerateData( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-bool fpa::Base::Algorithm< V, C, R, B >::
-_UpdateCollisions( const TVertex& a, const TVertex& b )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_AfterGenerateData( )
 {
-  bool ret = false;
-  _TNode na = this->_Node( a );
-  _TNode nb = this->_Node( b );
-  long fa = na.FrontId;
-  long fb = nb.FrontId;
-
-  if( fa != fb )
-  {
-    // Mark collision, if it is new
-    bool exists = this->m_Collisions[ fa ][ fb ].second;
-    exists     &= this->m_Collisions[ fb ][ fa ].second;
-        
-    if( !exists )
-    {
-      this->m_Collisions[ fa ][ fb ].first = na.Vertex;
-      this->m_Collisions[ fa ][ fb ].second = true;
-      this->m_Collisions[ fb ][ fa ].first = nb.Vertex;
-      this->m_Collisions[ fb ][ fa ].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 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
-        ret = ( count == N );
-
-      } // fi
-
-    } // fi
-
-  } // fi
-  return( ret );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-bool fpa::Base::Algorithm< V, C, R, B >::
-_NeedToStop( ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_FinishOneLoop( )
 {
-  return( false );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Algorithm< V, C, R, B >::
-_InitQueue( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_QueueInit( )
 {
   this->_QueueClear( );
-  for(
-    typename _TNodes::const_iterator sIt = this->m_Seeds.begin( );
-    sIt != this->m_Seeds.end( );
-    sIt++
-    )
-  {
-    this->_QueuePush( *sIt );
-    this->_Mark( *sIt );
-
-  } // rof
 }
 
-#endif // __FPA__BASE__ALGORITHM__HXX__
+#endif // __fpa__Base__Algorithm__hxx__
 
 // eof - $RCSfile$