#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 >::
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
    this->_Loop( );

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

// -------------------------------------------------------------------------
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
}

#endif // __fpa__Base__Algorithm__hxx__

// eof - $RCSfile$