lib/fpa/Filters/PriorityQueueAlgorithm.hxx

   1 // =========================================================================
   2 // @author Leonardo Florez Valencia
   3 // @email florez-l@javeriana.edu.co
   4 // =========================================================================
   5 #ifndef __fpa__Filters__PriorityQueueAlgorithm__hxx__
   6 #define __fpa__Filters__PriorityQueueAlgorithm__hxx__
   7
   8 // -------------------------------------------------------------------------
   9 template< class _TDataInterface >
  10 fpa::Filters::PriorityQueueAlgorithm< _TDataInterface >::
  11 PriorityQueueAlgorithm( bool double_buffer )
  12   : Superclass( ),
  13     m_CurrQueue( 0 ),
  14     m_DoubleBuffer( double_buffer )
  15 {
  16 }
  17
  18 // -------------------------------------------------------------------------
  19 template< class _TDataInterface >
  20 fpa::Filters::PriorityQueueAlgorithm< _TDataInterface >::
  21 ~PriorityQueueAlgorithm( )
  22 {
  23 }
  24
  25 // -------------------------------------------------------------------------
  26 template< class _TDataInterface >
  27 void fpa::Filters::PriorityQueueAlgorithm< _TDataInterface >::
  28 _QueueSwap( )
  29 {
  30   if( this->m_DoubleBuffer )
  31     this->m_CurrQueue = ( this->m_CurrQueue + 1 ) % 2;
  32   else
  33     this->m_CurrQueue = 0;
  34 }
  35
  36 // -------------------------------------------------------------------------
  37 template< class _TDataInterface >
  38 void fpa::Filters::PriorityQueueAlgorithm< _TDataInterface >::
  39 _QueueClear( )
  40 {
  41   this->m_Queues[ 0 ].clear( );
  42   this->m_Queues[ 1 ].clear( );
  43   this->m_CurrQueue = 0;
  44 }
  45
  46 // -------------------------------------------------------------------------
  47 template< class _TDataInterface >
  48 typename fpa::Filters::PriorityQueueAlgorithm< _TDataInterface >::
  49 TNode fpa::Filters::PriorityQueueAlgorithm< _TDataInterface >::
  50 _QueuePop( )
  51 {
  52   std::pop_heap(
  53     this->m_Queues[ this->m_CurrQueue ].begin( ),
  54     this->m_Queues[ this->m_CurrQueue ].end( ),
  55     this->m_QueueOrder
  56     );
  57   TNode n = this->m_Queues[ this->m_CurrQueue ].back( );
  58   this->m_Queues[ this->m_CurrQueue ].pop_back( );
  59   return( n );
  60 }
  61
  62 // -------------------------------------------------------------------------
  63 template< class _TDataInterface >
  64 void fpa::Filters::PriorityQueueAlgorithm< _TDataInterface >::
  65 _QueuePush( const TNode& n )
  66 {
  67   bool push_needed =  ( n.Parent == n.Vertex );
  68   push_needed     |= !( n.Value < this->_GetOutputValue( n.Parent ) );
  69   if( push_needed )
  70   {
  71     this->m_Queues[ this->m_CurrQueue ].push_back( n );
  72     std::push_heap(
  73       this->m_Queues[ this->m_CurrQueue ].begin( ),
  74       this->m_Queues[ this->m_CurrQueue ].end( ),
  75       this->m_QueueOrder
  76       );
  77
  78   } // fi
  79 }
  80
  81 // -------------------------------------------------------------------------
  82 template< class _TDataInterface >
  83 unsigned long fpa::Filters::PriorityQueueAlgorithm< _TDataInterface >::
  84 _QueueSize( ) const
  85 {
  86   return( this->m_Queues[ this->m_CurrQueue ].size( ) );
  87 }
  88
  89 #endif // __fpa__Filters__PriorityQueueAlgorithm__hxx__
  90 // eof - $RCSfile$