-#ifndef __fpa__Base__Algorithm__hxx__
-#define __fpa__Base__Algorithm__hxx__
-
-#include <queue>
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::_TQueueNode::
-_TQueueNode( )
-{
- 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 )
-{
- 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 )
-{
- this->Vertex = v;
- this->Parent = n.Vertex;
- this->Result = n.Result;
- this->FrontId = n.FrontId;
-}
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-ClearSeeds( )
-{
- this->m_Seeds.clear( );
- this->Modified( );
-}
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-AddSeed( const _TVertex& seed, const TOutput& value )
-{
- _TQueueNode node( seed );
- node.FrontId = this->m_Seeds.size( ) + 1;
- node.Result = value;
- this->m_Seeds.push_back( node );
- this->Modified( );
-}
-
-// -------------------------------------------------------------------------
-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 _TVertex, class _TOutput >
-fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-~Algorithm( )
-{
-}
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-GenerateData( )
-{
- this->InvokeEvent( TStartEvent( ) );
- this->_BeforeGenerateData( );
- this->m_NumberOfFronts = this->m_Seeds.size( );
- if( this->m_NumberOfFronts > 0 )
- {
- // 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( ) );
-}
-
-// -------------------------------------------------------------------------
-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->_ValidLoop( ) )
- {
- _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 )
- {
- if( !( this->_IsMarked( *it ) ) )
- {
- _TQueueNode neigh( *it, node );
- if( this->_UpdateValue( neigh, node ) )
- {
- this->_QueuePush( neigh );
- this->InvokeEvent( TPushEvent( node.Vertex, node.FrontId ) );
-
- } // fi
- }
- else
- this->_UpdateCollisions( node.Vertex, *it );
-
- } // rof
-
- } // elihw
- this->_AfterLoop( );
- this->InvokeEvent( TEndLoopEvent( ) );
-}
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_BeforeGenerateData( )
-{
-}
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-void fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_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
-{
- 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 )
-{
- 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
-}
-
-// -------------------------------------------------------------------------
-template < class _TFilter, class _TVertex, class _TOutput >
-_TOutput fpa::Base::Algorithm< _TFilter, _TVertex, _TOutput >::
-_GetInputValue( const _TQueueNode& v, const _TQueueNode& p )
-{
- _TOutput res = this->m_InitResult;
- if( this->m_VertexFunction.IsNotNull( ) )
- res = this->m_VertexFunction->Evaluate( v.Vertex, p.Vertex );
- if( this->m_ConversionFunction.IsNotNull( ) )
- res = this->m_ConversionFunction->Evaluate( res );
- return( res );
-}
-
-#endif // __fpa__Base__Algorithm__hxx__
-
-// eof - $RCSfile$