// =========================================================================
// @author Leonardo Florez Valencia
// @email florez-l@javeriana.edu.co
// =========================================================================

#ifndef __fpa__Base__DijkstraBase__hxx__
#define __fpa__Base__DijkstraBase__hxx__

#include <algorithm>
#include <limits>

// -------------------------------------------------------------------------
template< class _TAlgorithm >
itk::ModifiedTimeType fpa::Base::DijkstraBase< _TAlgorithm >::
GetMTime( ) const
{
  itk::ModifiedTimeType t = this->Superclass::GetMTime( );
  if( this->m_WeightFunction.IsNotNull( ) )
  {
    itk::ModifiedTimeType q = this->m_WeightFunction->GetMTime( );
    t = ( q < t )? q: t;

  } // fi
  return( t );
}

// -------------------------------------------------------------------------
template< class _TAlgorithm >
fpa::Base::DijkstraBase< _TAlgorithm >::
DijkstraBase( )
  : Superclass( )
{
  this->SetInitValue( std::numeric_limits< TOutputValue >::max( ) );
}

// -------------------------------------------------------------------------
template< class _TAlgorithm >
fpa::Base::DijkstraBase< _TAlgorithm >::
~DijkstraBase( )
{
}

// -------------------------------------------------------------------------
template< class _TAlgorithm >
void fpa::Base::DijkstraBase< _TAlgorithm >::
_ComputeOutputValue( TNode& n )
{
  TOutputValue c = this->m_WeightFunction->Evaluate( n.Vertex, n.Parent );
  n.Value = c + this->_GetOutputValue( n.Parent );
}

// -------------------------------------------------------------------------
template< class _TAlgorithm >
void fpa::Base::DijkstraBase< _TAlgorithm >::
_QueueClear( )
{
  this->m_Queue.clear( );
}

// -------------------------------------------------------------------------
template< class _TAlgorithm >
typename fpa::Base::DijkstraBase< _TAlgorithm >::
TNode fpa::Base::DijkstraBase< _TAlgorithm >::
_QueuePop( )
{
  std::pop_heap(
    this->m_Queue.begin( ), this->m_Queue.end( ), this->m_QueueOrder
    );
  TNode n = this->m_Queue.back( );
  this->m_Queue.pop_back( );
  return( n );
}

// -------------------------------------------------------------------------
template< class _TAlgorithm >
void fpa::Base::DijkstraBase< _TAlgorithm >::
_QueuePush( const TNode& node )
{
  bool push_needed =  ( node.Parent == node.Vertex );
  push_needed     |= !( node.Value < this->_GetOutputValue( node.Parent ) );
  if( push_needed )
  {
    this->m_Queue.push_back( node );
    std::push_heap(
      this->m_Queue.begin( ), this->m_Queue.end( ), this->m_QueueOrder
      );

  } // fi
}

// -------------------------------------------------------------------------
template< class _TAlgorithm >
unsigned long fpa::Base::DijkstraBase< _TAlgorithm >::
_QueueSize( ) const
{
  return( this->m_Queue.size( ) );
}

// -------------------------------------------------------------------------
template< class _TAlgorithm >
void fpa::Base::DijkstraBase< _TAlgorithm >::
_PrepareSeeds( TNodes& nodes )
{
  typename TNodes::iterator nIt = nodes.begin( );
  for( ; nIt != nodes.end( ); ++nIt )
    nIt->Value = TOutputValue( 0 );
}

#endif // __fpa__Base__DijkstraBase__hxx__

// eof - $RCSfile$