#ifndef __FPA__BASE__ALGORITHM__HXX__
#define __FPA__BASE__ALGORITHM__HXX__

#include <queue>

// -------------------------------------------------------------------------
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 V, class C, class R, class B >
fpa::Base::Algorithm< V, C, R, B >::_TNode::
~_TNode( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
void fpa::Base::Algorithm< V, C, R, B >::
InvokeEvent( const itk::EventObject& e )
{
  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
{
  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 >::
AddSeed( const TVertex& s, const TResult& r )
{
  _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( );
}

// -------------------------------------------------------------------------
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
{
  return( this->m_Seeds[ id ].Vertex );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
void fpa::Base::Algorithm< V, C, R, B >::
ClearSeeds( )
{
  this->m_Seeds.clear( );
  this->Modified( );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
unsigned long fpa::Base::Algorithm< V, C, R, B >::
GetNumberOfSeeds( ) const
{
  return( this->m_Seeds.size( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
fpa::Base::Algorithm< V, C, R, B >::
Algorithm( )
  : Superclass( ),
    m_ThrowEvents( false ),
    m_StopAtOneFront( false )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
fpa::Base::Algorithm< V, C, R, B >::
~Algorithm( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
void fpa::Base::Algorithm< V, C, R, B >::
GenerateData( )
{
  unsigned long N = this->m_Seeds.size( );
  if( N == 0 )
    return;

  this->InvokeEvent( TStartEvent( ) );
  this->_BeforeGenerateData( );

  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( ) );
}

// -------------------------------------------------------------------------
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( ) ) )
  {
    // 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( ) ) )
    {
      // Compute neighborhood
      _TVertices neighborhood;
      this->_Neighborhood( neighborhood, candidate.Vertex );

      // Iterate over neighbors
      typename _TVertices::iterator nIt = neighborhood.begin( );
      for( ; nIt != neighborhood.end( ); ++nIt )
      {
        _TNode neighbor = this->_Node( *nIt );
        neighbor.Vertex = *nIt;
        if( neighbor.Label == Self::AliveLabel )
        {
          // Update collisions
          if( this->_UpdateCollisions( candidate.Vertex, *nIt ) )
          {
            this->_QueueClear( );
            nIt = neighborhood.end( );

          } // 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 ) );
          }
          else
            this->InvokeEvent( TFreezeEvent( *nIt, candidate.FrontId ) );

        } // fi

      } // rof
    }
    else
      this->_QueueClear( );

  } // elihw
  this->_AfterLoop( );
  this->InvokeEvent( TEndLoopEvent( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
void fpa::Base::Algorithm< V, C, R, B >::
_BeforeGenerateData( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
void fpa::Base::Algorithm< V, C, R, B >::
_AfterGenerateData( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
void fpa::Base::Algorithm< V, C, R, B >::
_BeforeLoop( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
void fpa::Base::Algorithm< V, C, R, B >::
_AfterLoop( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
bool fpa::Base::Algorithm< V, C, R, B >::
_UpdateCollisions( const TVertex& a, const TVertex& b )
{
  bool ret = false;
  _TNode na = this->_Node( a );
  _TNode nb = this->_Node( b );
  long fa = na.FrontId;
  long fb = na.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
{
  return( false );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class B >
void fpa::Base::Algorithm< V, C, R, B >::
_InitQueue( )
{
  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__

// eof - $RCSfile$