lib/fpa/Base/Dijkstra.hxx

   1 #ifndef __FPA__BASE__DIJKSTRA__HXX__
   2 #define __FPA__BASE__DIJKSTRA__HXX__
   3
   4 #include <algorithm>
   5
   6 // -------------------------------------------------------------------------
   7 template< class V, class C, class R, class B >
   8 fpa::Base::Dijkstra< V, C, R, B >::
   9 Dijkstra( )
  10   : Superclass( )
  11 {
  12 }
  13
  14 // -------------------------------------------------------------------------
  15 template< class V, class C, class R, class B >
  16 fpa::Base::Dijkstra< V, C, R, B >::
  17 ~Dijkstra( )
  18 {
  19 }
  20
  21 // -------------------------------------------------------------------------
  22 template< class V, class C, class R, class B >
  23 bool fpa::Base::Dijkstra< V, C, R, B >::
  24 _ComputeNeighborResult(
  25   TResult& result, const TVertex& neighbor, const TVertex& parent
  26   ) const
  27 {
  28   result  = this->_Cost( neighbor, parent );
  29   result *= TResult( this->_Distance( neighbor, parent ) );
  30
  31   _TNode pn = this->_Node( parent );
  32   if( pn.Label == Self::AliveLabel )
  33     result += pn.Result;
  34
  35   return( true );
  36 }
  37
  38 // -------------------------------------------------------------------------
  39 template< class V, class C, class R, class B >
  40 bool fpa::Base::Dijkstra< V, C, R, B >::
  41 _IsQueueEmpty( ) const
  42 {
  43   return( this->m_Queue.empty( ) );
  44 }
  45
  46 // -------------------------------------------------------------------------
  47 template< class V, class C, class R, class B >
  48 void fpa::Base::Dijkstra< V, C, R, B >::
  49 _QueuePush( const _TNode& n )
  50 {
  51   this->m_Queue.push_back( n );
  52   std::push_heap(
  53     this->m_Queue.begin( ), this->m_Queue.end( ), Self::m_NodeCompare
  54     );
  55 }
  56
  57 // -------------------------------------------------------------------------
  58 template< class V, class C, class R, class B >
  59 typename fpa::Base::Dijkstra< V, C, R, B >::
  60 _TNode fpa::Base::Dijkstra< V, C, R, B >::
  61 _QueuePop( )
  62 {
  63   _TNode n = this->m_Queue.front( );
  64   std::pop_heap(
  65     this->m_Queue.begin( ), this->m_Queue.end( ), Self::m_NodeCompare
  66     );
  67   this->m_Queue.pop_back( );
  68   return( n );
  69 }
  70
  71 // -------------------------------------------------------------------------
  72 template< class V, class C, class R, class B >
  73 void fpa::Base::Dijkstra< V, C, R, B >::
  74 _QueueClear( )
  75 {
  76   this->m_Queue.clear( );
  77 }
  78
  79 #endif // __FPA__BASE__DIJKSTRA__HXX__
  80
  81 // eof - $RCSfile$