#ifndef __FPA__BASE__DIJKSTRA__HXX__
#define __FPA__BASE__DIJKSTRA__HXX__

#include <algorithm>

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
typename fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
TMinimumSpanningTree* fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
GetMinimumSpanningTree( )
{
  return(
    dynamic_cast< TMinimumSpanningTree* >(
      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
      )
    );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
const typename fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
TMinimumSpanningTree* fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
GetMinimumSpanningTree( ) const
{
  return(
    dynamic_cast< const TMinimumSpanningTree* >(
      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
      )
    );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
GraftMinimumSpanningTree( itk::DataObject* obj )
{
  TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
  if( mst != NULL )
    this->GraftNthOutput( this->m_MSTIdx, mst );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
Dijkstra( )
  : Superclass( ),
    m_LocalCosts( false ),
    m_FillNodeQueue( false )
{
  this->m_MSTIdx = this->GetNumberOfRequiredOutputs( );
  this->SetNumberOfRequiredOutputs( this->m_MSTIdx + 1 );
  this->itk::ProcessObject::SetNthOutput(
    this->m_MSTIdx, TMinimumSpanningTree::New( )
    );
}

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

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
_BeforeGenerateData( )
{
  this->Superclass::_BeforeGenerateData( );
  this->GetMinimumSpanningTree( )->SetFillNodeQueue( this->m_FillNodeQueue );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
bool fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
_ComputeNeighborResult(
  TResult& result, const TVertex& neighbor, const TVertex& parent
  ) const
{
  result  = this->_Cost( neighbor, parent );
  result *= TResult( this->_Distance( neighbor, parent ) );

  // WARNING: Dijkstra does not work on negative values!
  if( result >= TResult( 0 ) )
  {
    _TNode pn = this->_Node( parent );
    if( pn.Label == Self::AliveLabel && !this->m_LocalCosts )
      result += pn.Result;
    return( true );
  }
  else
    return( false );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
_SetResult( const TVertex& v, const _TNode& n )
{
  this->GetMinimumSpanningTree( )->SetNode( v, n.Parent, n.FrontId, n.Result );
}

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

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
_QueuePush( const TVertex& v, const _TNode& n )
{
  _TQueueNode qn;
  qn.Vertex = v;
  qn.Node = n;
  this->m_Queue.push_back( qn );
  std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class R, class S, class VC, class MST, class B >
void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
_QueuePop( TVertex& v, _TNode& n )
{
  _TQueueNode qn = this->m_Queue.front( );
  std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
  this->m_Queue.pop_back( );
  v = qn.Vertex;
  n = qn.Node;
}

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

#endif // __FPA__BASE__DIJKSTRA__HXX__

// eof - $RCSfile$