-#ifndef __FPA__BASE__ALGORITHM__HXX__
-#define __FPA__BASE__ALGORITHM__HXX__
+#ifndef __fpa__Base__Algorithm__hxx__
+#define __fpa__Base__Algorithm__hxx__
#include <queue>
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-const _TVertexCompare fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-TNode::VertexCompare = _TVertexCompare( );
-
-// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-InvokeEvent( const itk::EventObject& e )
-{
- if( this->m_ThrowEvents )
- this->Superclass::InvokeEvent( e );
-}
-
-// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-InvokeEvent( const itk::EventObject& e ) const
+template < class _TFilter, class _TVertex, class _TOutput >
+fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
+_TQueueNode( )
{
- if( this->m_ThrowEvents )
- this->Superclass::InvokeEvent( e );
+ this->Vertex.Fill( 0 );
+ this->Parent.Fill( 0 );
+ this->Result = _TOutput( 0 );
+ this->FrontId = 0;
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-unsigned long fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-GetNumberOfSeeds( ) const
+template < class _TFilter, class _TVertex, class _TOutput >
+fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
+_TQueueNode( const _TVertex& v )
{
- return( this->m_Seeds.size( ) );
+ this->Vertex = v;
+ this->Parent = v;
+ this->Result = _TOutput( 0 );
+ this->FrontId = 0;
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-AddSeed( const TVertex& s, const TScalar& v )
+template < class _TFilter, class _TVertex, class _TOutput >
+fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
+_TQueueNode( const _TVertex& v, const _TQueueNode& n )
{
- TNode n;
- n.Vertex = s;
- n.Parent = s;
- n.Result = v;
- n.Label = Self::FrontLabel;
- this->AddSeed( n );
+ this->Vertex = v;
+ this->Parent = n.Vertex;
+ this->Result = n.Result;
+ this->FrontId = n.FrontId;
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-AddSeed( const TNode& n )
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
+ClearSeeds( )
{
- this->m_Seeds.insert( n );
+ this->m_Seeds.clear( );
this->Modified( );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-RemoveSeed( const TVertex& s )
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
+AddSeed( const _TVertex& seed, const TOutput& value )
{
- TNode n;
- n.Vertex = s;
- typename TNodes::iterator i = this->m_Seeds.find( n );
- if( i != this->m_Seeds.end( ) )
- {
- this->m_Seeds.erase( i );
- this->Modified( );
-
- } // fi
-}
-
-// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-RemoveAllSeeds( )
-{
- this->m_Seeds.clear( );
+ _TQueueNode node( seed );
+ node.FrontId = this->m_Seeds.size( ) + 1;
+ node.Result = value;
+ this->m_Seeds.push_back( node );
this->Modified( );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
Algorithm( )
: Superclass( ),
- m_StopAtOneFront( false ),
- m_ThrowEvents( false )
+ m_InitResult( _TOutput( 0 ) ),
+ m_StopAtOneFront( false )
{
}
-
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
~Algorithm( )
{
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
GenerateData( )
{
this->InvokeEvent( TStartEvent( ) );
this->_BeforeGenerateData( );
-
- unsigned int N = this->m_Seeds.size( );
- if( N > 0 )
+ this->m_NumberOfFronts = this->m_Seeds.size( );
+ if( this->m_NumberOfFronts > 0 )
{
- // Enumerate seeds
- typename TNodes::iterator nIt = this->m_Seeds.begin( );
- for( unsigned long i = 1; nIt != this->m_Seeds.end( ); ++nIt, ++i )
- nIt->FrontId = i;
-
// Prepare collisions
TCollision coll( TVertex( ), false );
- TCollisionsRow row( N, coll );
+ TCollisionsRow row( this->m_NumberOfFronts, coll );
this->m_Collisions.clear( );
- this->m_Collisions.resize( N, row );
+ this->m_Collisions.resize( this->m_NumberOfFronts, row );
// Put seeds on queue
this->_QueueClear( );
- for( nIt = this->m_Seeds.begin( ); nIt != this->m_Seeds.end( ); ++nIt )
+ 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->_InitResults( this->m_InitResult );
// Main loop
- this->_BeforeLoop( );
- this->_Loop( );
- this->_AfterLoop( );
-
- // Deallocate any memory
- this->_DeallocateAuxiliary( );
+ do
+ this->_Loop( );
+ while( this->_ContinueGenerateData( ) );
} // fi
-
this->_AfterGenerateData( );
this->InvokeEvent( TEndEvent( ) );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
+_ContinueGenerateData( )
+{
+ return( false );
+}
+
+// -------------------------------------------------------------------------
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
_Loop( )
{
this->InvokeEvent( TStartLoopEvent( ) );
this->_BeforeLoop( );
-
- while( !( this->_IsQueueEmpty( ) ) )
+ while( this->_ValidLoop( ) )
{
- // Extract next candidate
- TNode node = this->_QueuePop( );
+ _TQueueNode node = this->_QueuePop( );
+ this->InvokeEvent( TPopEvent( node.Vertex, node.FrontId ) );
- // Check if it has been visited
- if( this->_GetMark( node ) > 0 )
+ // Process actual vertex
+ if( this->_IsMarked( node.Vertex ) )
continue;
+ this->_Mark( node );
+ this->_UpdateResult( node );
+ this->InvokeEvent( TMarkEvent( node.Vertex, node.FrontId ) );
- // Mark it as visited
- this->_Visit( node );
- this->InvokeEvent( TAliveEvent( node.Vertex, node.FrontId ) );
-
- // Check if there is an external stop condition
- if( this->_NeedToStop( ) )
+ // Add neighbors to queue
+ TNeighborhood neighs = this->m_NeighborhoodFunction->Evaluate( node.Vertex );
+ for( auto it = neighs.begin( ); it != neighs.end( ); ++it )
{
- this->_QueueClear( );
- continue;
-
- } // fi
-
- // Get neighborhood
- TVertices neighborhood = this->_GetNeighborhood( node );
-
- // Update neighborhood
- auto neighIt = neighborhood.begin( );
- bool stop = false;
- for( ; neighIt != neighborhood.end( ); ++neighIt )
- {
- if( this->_GetMark( *neighIt ) == 0 )
+ if( !( this->_IsMarked( *it ) ) )
{
- TNode neigh;
- neigh.Vertex = *neighIt;
- neigh.Parent = node.Vertex;
- neigh.FrontId = node.FrontId;
- if( this->_Result( neigh, node ) )
+ _TQueueNode neigh( *it, node );
+ if( this->_UpdateValue( neigh, node ) )
{
this->_QueuePush( neigh );
- this->InvokeEvent( TFrontEvent( *neighIt, node.FrontId ) );
+ this->InvokeEvent( TPushEvent( node.Vertex, node.FrontId ) );
} // fi
}
else
- stop |= this->_UpdateCollisions( node.Vertex, *neighIt );
+ this->_UpdateCollisions( node.Vertex, *it );
} // rof
- if( stop )
- this->_QueueClear( );
-
} // elihw
-
this->_AfterLoop( );
this->InvokeEvent( TEndLoopEvent( ) );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
_BeforeGenerateData( )
{
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
_AfterGenerateData( )
{
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
_BeforeLoop( )
{
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-void fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
_AfterLoop( )
{
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-typename fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-TFrontId fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-_GetMark( const TNode& v )
+template < class _TFilter, class _TVertex, class _TOutput >
+bool fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
+_ValidLoop( ) const
{
- return( this->_GetMark( v.Vertex ) );
+ bool r = ( this->_QueueSize( ) > 0 );
+ if( this->m_StopAtOneFront )
+ r &= ( this->m_NumberOfFronts > 0 );
+ return( r );
}
// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-bool fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-_NeedToStop( )
-{
- return( false );
-}
-
-// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-typename fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-TVertices fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
-_GetNeighborhood( const TNode& n ) const
-{
- return( this->_GetNeighborhood( n.Vertex ) );
-}
-
-// -------------------------------------------------------------------------
-template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
-bool fpa::Base::
-Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
+template < class _TFilter, class _TVertex, class _TOutput >
+void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
_UpdateCollisions( const TVertex& a, const TVertex& b )
{
auto ma = this->_GetMark( a );
auto mb = this->_GetMark( b );
if( ma == mb || ma == 0 || mb == 0 )
- return( false );
- ma--;
- mb--;
+ 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;
this->m_Collisions[ mb ][ ma ].first = b;
this->m_Collisions[ mb ][ ma ].second = true;
- // Stop if one front is desired
- if( this->m_StopAtOneFront )
+ // 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( ) )
{
- // 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++;
+ unsigned long f = q.front( );
+ q.pop( );
- for( unsigned int n = 0; n < N; ++n )
- if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
- q.push( n );
+ if( m[ f ] )
+ continue;
+ m[ f ] = true;
+ count++;
- } // elihw
- ret = ( count == N );
- this->InvokeEvent( TCollisionEvent( a, ma + 1 ) );
- this->InvokeEvent( TCollisionEvent( b, mb + 1 ) );
+ for( unsigned int n = 0; n < N; ++n )
+ if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
+ q.push( n );
- } // fi
+ } // elihw
+ this->m_NumberOfFronts = N - count;
} // fi
- return( ret );
}
-#endif // __FPA__BASE__ALGORITHM__HXX__
+#endif // __fpa__Base__Algorithm__hxx__
// eof - $RCSfile$
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff