#ifndef __FPA__BASE__ALGORITHM__HXX__
#define __FPA__BASE__ALGORITHM__HXX__

#include <algorithm>
#include <limits>
#include <queue>

// -------------------------------------------------------------------------
template< class T, class B >
void fpa::Base::Algorithm< T, B >::
InvokeEvent( const itk::EventObject& e )
{
  if( this->m_ThrowEvents )
    this->Superclass::InvokeEvent( e );
}

// -------------------------------------------------------------------------
template< class T, class B >
void fpa::Base::Algorithm< T, B >::
InvokeEvent( const itk::EventObject& e ) const
{
  if( this->m_ThrowEvents )
    this->Superclass::InvokeEvent( e );
}

// -------------------------------------------------------------------------
template< class T, class B >
void fpa::Base::Algorithm< T, B >::
AddSeed( const TVertex& s, const TResult& v )
{
  this->m_Seeds.push_back( _TNode( s, v, this->m_Seeds.size( ) ) );
  this->Modified( );
}

// -------------------------------------------------------------------------
template< class T, class B >
const typename fpa::Base::Algorithm< T, B >::
TVertex& fpa::Base::Algorithm< T, B >::
GetSeed( const unsigned long& i ) const
{
  return( this->m_Seeds[ i ].Vertex );
}

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

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

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

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

// -------------------------------------------------------------------------
template< class T, class B >
void fpa::Base::Algorithm< T, B >::
GenerateData( )
{
  this->AllocateOutputs( );

  unsigned long N = this->m_Seeds.size( );
  if( N == 0 )
    return;
  this->m_CollisionSites.clear( );
  this->m_CollisionSites.
    resize( N, _TCollisionSitesRow( N, _TCollision( TVertex( ), false ) ) );

  this->_BeforeMainLoop( );
  this->_InitializeMarks( );
  this->_InitializeResults( );
  this->_InitializeQueue( );
  this->_Loop( );
  this->_AfterMainLoop( );
  this->InvokeEvent( TEndEvent( ) );
}

// -------------------------------------------------------------------------
template< class T, class B >
void fpa::Base::Algorithm< T, B >::
_BeforeMainLoop( )
{
}

// -------------------------------------------------------------------------
template< class T, class B >
void fpa::Base::Algorithm< T, B >::
_AfterMainLoop( )
{
}

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

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

// -------------------------------------------------------------------------
template< class T, class B >
void fpa::Base::Algorithm< T, B >::
_Loop( )
{
  this->_BeforeLoop( );
  while( !( this->_IsQueueEmpty( ) ) )
  {
    _TNode n = this->_QueuePop( );
    if( this->_IsMarked( n.Vertex ) )
      continue;

    this->_Mark( n );
    this->InvokeEvent( TMarkEvent( n ) );
    if( this->_UpdateResult( n ) )
    {
      if( !( this->_CheckStopCondition( ) ) )
      {
        _TNodes N;
        this->_Neighs( n, N );
        typename _TNodes::iterator nnIt = N.begin( );
        while( nnIt != N.end( ) )
        {
          if( this->_IsMarked( nnIt->Vertex ) )
          {
            // Update real front identifier
            nnIt->FrontId = this->_FrontId( nnIt->Vertex );

            // Update collisions
            if( this->_CheckCollisions( n, *nnIt ) )
            {
              if( this->m_StopAtOneFront )
              {
                this->_QueueClear( );
                nnIt = N.end( );

              } // fi

            } // fi
          }
          else
          {
            if( this->_UpdateNeigh( *nnIt, n ) )
            {
              nnIt->Parent = n.Vertex;
              this->_QueuePush( *nnIt );
              this->InvokeEvent( TFrontEvent( *nnIt ) );

            } // fi

          } // fi
          if( nnIt != N.end( ) )
            nnIt++;

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

    } // fi

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

// -------------------------------------------------------------------------
template< class T, class B >
bool fpa::Base::Algorithm< T, B >::
_CheckCollisions( const _TNode& a, const _TNode& b )
{
  bool ret = false;
  if( a.FrontId != b.FrontId )
  {
    // Mark collision, if it is new
    bool exists = this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second;
    exists     &= this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second;
    if( !exists )
    {
      this->m_CollisionSites[ a.FrontId ][ b.FrontId ].first = a.Vertex;
      this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second = true;
      this->m_CollisionSites[ b.FrontId ][ a.FrontId ].first = b.Vertex;
      this->m_CollisionSites[ b.FrontId ][ a.FrontId ].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 C = 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;
          C++;

          for( unsigned int n = 0; n < N; ++n )
            if( this->m_CollisionSites[ f ][ n ].second && !m[ n ] )
              q.push( n );

        } // elihw
        ret = ( C == N );

      } // fi

    } // fi

  } // fi
  return( ret );
}

// -------------------------------------------------------------------------
template< class T, class B >
bool fpa::Base::Algorithm< T, B >::
_CheckStopCondition( )
{
  return( false );
}

// -------------------------------------------------------------------------
template< class T, class B >
bool fpa::Base::Algorithm< T, B >::
_UpdateResult( _TNode& n )
{
  return( true );
}

// -------------------------------------------------------------------------
template< class T, class B >
void fpa::Base::Algorithm< T, B >::
_InitializeMarks( )
{
  this->m_Marks.clear( );
}

// -------------------------------------------------------------------------
template< class T, class B >
bool  fpa::Base::Algorithm< T, B >::
_IsMarked( const TVertex& v ) const
{
  return( this->m_Marks.find( v ) != this->m_Marks.end( ) );
}

// -------------------------------------------------------------------------
template< class T, class B >
typename fpa::Base::Algorithm< T, B >::
_TFrontId fpa::Base::Algorithm< T, B >::
_FrontId( const TVertex& v ) const
{
  typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
  if( mIt != this->m_Marks.end( ) )
    return( mIt->second.FrontId );
  else
    return( std::numeric_limits< _TFrontId >::max( ) );
}

// -------------------------------------------------------------------------
template< class T, class B >
typename fpa::Base::Algorithm< T, B >::
TVertex fpa::Base::Algorithm< T, B >::
_Parent( const TVertex& v ) const
{
  typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
  if( mIt == this->m_Marks.end( ) )
    return( TVertex( ) );
  else
    return( mIt->second.Parent );
}

// -------------------------------------------------------------------------
template< class T, class B >
void  fpa::Base::Algorithm< T, B >::
_Mark( const _TNode& n )
{
  this->m_Marks[ n.Vertex ] = n;
}

#endif // __FPA__BASE__ALGORITHM__HXX__

// eof - $RCSfile$