#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
{
  if( this->m_ThrowEvents )
    this->Superclass::InvokeEvent( e );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
unsigned long fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
GetNumberOfSeeds( ) const
{
  return( this->m_Seeds.size( ) );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
void fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
AddSeed( const TVertex& s, const TScalar& v )
{
  TNode n;
  n.Vertex = s;
  n.Parent = s;
  n.Result = v;
  n.Label = Self::FrontLabel;
  this->AddSeed( n );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
void fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
AddSeed( const TNode& n )
{
  this->m_Seeds.insert( n );
  this->Modified( );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
void fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
RemoveSeed( const TVertex& s )
{
  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( );
  this->Modified( );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
Algorithm( )
  : Superclass( ),
    m_StopAtOneFront( false ),
    m_ThrowEvents( false )
{
}


// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
~Algorithm( )
{
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
void fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
GenerateData( )
{
  this->InvokeEvent( TStartEvent( ) );
  this->_BeforeGenerateData( );

  unsigned int N = this->m_Seeds.size( );
  if( N > 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 );
    this->m_Collisions.clear( );
    this->m_Collisions.resize( N, row );

    // Put seeds on queue
    this->_QueueClear( );
    for( nIt = this->m_Seeds.begin( ); nIt != this->m_Seeds.end( ); ++nIt )
      this->_QueuePush( *nIt );

    // Init marks and results
    this->_InitMarks( );
    this->_InitResults( );

    // Main loop
    this->_BeforeLoop( );
    this->_Loop( );
    this->_AfterLoop( );

    // Deallocate any memory
    this->_DeallocateAuxiliary( );

  } // fi

  this->_AfterGenerateData( );
  this->InvokeEvent( TEndEvent( ) );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
void fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
_Loop( )
{
  this->InvokeEvent( TStartLoopEvent( ) );
  this->_BeforeLoop( );

  while( !( this->_IsQueueEmpty( ) ) )
  {
    // Extract next candidate
    TNode node = this->_QueuePop( );

    // Check if it has been visited
    if( this->_GetMark( node ) > 0 )
      continue;

    // 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( ) )
    {
      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 )
      {
        TNode neigh;
        neigh.Vertex = *neighIt;
        neigh.Parent = node.Vertex;
        neigh.FrontId = node.FrontId;
        if( this->_Result( neigh, node ) )
        {
          this->_QueuePush( neigh );
          this->InvokeEvent( TFrontEvent( *neighIt, node.FrontId ) );

        } // fi
      }
      else
        stop |= this->_UpdateCollisions( node.Vertex, *neighIt );

    } // 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 >::
_BeforeGenerateData( )
{
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
void fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
_AfterGenerateData( )
{
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
void fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
_BeforeLoop( )
{
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare >
void fpa::Base::
Algorithm< _TVertex, _TScalar, _TFilter, _TVertexCompare >::
_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 )
{
  return( this->_GetMark( v.Vertex ) );
}

// -------------------------------------------------------------------------
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 >::
_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--;

  // Mark collision, if it is new
  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;

    // 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 );
      this->InvokeEvent( TCollisionEvent( a, ma + 1 ) );
      this->InvokeEvent( TCollisionEvent( b, mb + 1 ) );

    } // fi

  } // fi
  return( ret );
}

#endif // __FPA__BASE__ALGORITHM__HXX__

// eof - $RCSfile$