#ifndef __FPA__BASE__DIJKSTRA__HXX__
#define __FPA__BASE__DIJKSTRA__HXX__

#include <algorithm>

// -------------------------------------------------------------------------
template< class V, class C, class VV, class VC, class B >
fpa::Base::Dijkstra< V, C, VV, VC, B >::
Dijkstra( )
  : Superclass( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class VV, class VC, class B >
fpa::Base::Dijkstra< V, C, VV, VC, B >::
~Dijkstra( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class VV, class VC, class B >
void fpa::Base::Dijkstra< V, C, VV, VC, B >::
_InitializeQueue( )
{
  for(
    typename _TNodes::const_iterator vIt = this->m_Seeds.begin( );
    vIt != this->m_Seeds.end( );
    vIt++
    )
    this->_QueuePush( *vIt );
}

// -------------------------------------------------------------------------
template< class V, class C, class VV, class VC, class B >
bool fpa::Base::Dijkstra< V, C, VV, VC, B >::
_IsQueueEmpty( ) const
{
  return( this->m_Queue.empty( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class VV, class VC, class B >
void fpa::Base::Dijkstra< V, C, VV, VC, B >::
_QueuePush( const _TNode& n )
{
  this->m_Queue.push_back( n );
  std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class VV, class VC, class B >
typename fpa::Base::Dijkstra< V, C, VV, VC, B >::
_TNode fpa::Base::Dijkstra< V, C, VV, VC, B >::
_QueuePop( )
{
  _TNode n;
  if( !( this->m_Queue.empty( ) ) )
  {
    // n = *( this->m_Queue.begin( ) );
    n = this->m_Queue.front( );
    std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
    this->m_Queue.pop_back( );

  } // fi
  return( n );
}

// -------------------------------------------------------------------------
template< class V, class C, class VV, class VC, class B >
void fpa::Base::Dijkstra< V, C, VV, VC, B >::
_QueueClear( )
{
  this->m_Queue.clear( );
}

// -------------------------------------------------------------------------
template< class V, class C, class VV, class VC, class B >
bool fpa::Base::Dijkstra< V, C, VV, VC, B >::
_UpdateNeigh( _TNode& nn, const _TNode& n )
{
  TCost nc = this->_Cost( nn.Vertex, n.Vertex );
  if( C( 0 ) <= nc )
  {
    nn.Cost = n.Cost + nc;
    nn.Result = nn.Cost;
    return( true );
  }
  else
    return( false );
}

#endif // __FPA__BASE__DIJKSTRA__HXX__

// eof - $RCSfile$