#ifndef __FPA__BASE__DIJKSTRA__HXX__
#define __FPA__BASE__DIJKSTRA__HXX__

#include <algorithm>

// -------------------------------------------------------------------------
template< class _TSuperclass >
const typename fpa::Base::Dijkstra< _TSuperclass >::TDijkstraCmp
fpa::Base::Dijkstra< _TSuperclass >::DijkstraCmp =
fpa::Base::Dijkstra< _TSuperclass >::TDijkstraCmp( );

// -------------------------------------------------------------------------
template< class _TSuperclass >
typename fpa::Base::Dijkstra< _TSuperclass >::
TMinimumSpanningTree* fpa::Base::Dijkstra< _TSuperclass >::
GetMinimumSpanningTree( )
{
  return(
    dynamic_cast< TMinimumSpanningTree* >(
      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
      )
    );
}

// -------------------------------------------------------------------------
template< class _TSuperclass >
const typename fpa::Base::Dijkstra< _TSuperclass >::
TMinimumSpanningTree* fpa::Base::Dijkstra< _TSuperclass >::
GetMinimumSpanningTree( ) const
{
  return(
    dynamic_cast< const TMinimumSpanningTree* >(
      this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
      )
    );
}

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

// -------------------------------------------------------------------------
template< class _TSuperclass >
fpa::Base::Dijkstra< _TSuperclass >::
Dijkstra( )
  : Superclass( ),
    m_CostConversionFunction( NULL )
{
  this->m_MSTIdx = this->GetNumberOfRequiredOutputs( );
  this->SetNumberOfRequiredOutputs( this->m_MSTIdx + 1 );
  typename TMinimumSpanningTree::Pointer mst = TMinimumSpanningTree::New( );
  this->itk::ProcessObject::SetNthOutput( this->m_MSTIdx, mst );
}

// -------------------------------------------------------------------------
template< class _TSuperclass >
fpa::Base::Dijkstra< _TSuperclass >::
~Dijkstra( )
{
}

// -------------------------------------------------------------------------
template< class _TSuperclass >
void fpa::Base::Dijkstra< _TSuperclass >::
_AfterGenerateData( )
{
  this->Superclass::_AfterGenerateData( );
  this->GetMinimumSpanningTree( )->SetCollisions( this->m_Collisions );
}

// -------------------------------------------------------------------------
template< class _TSuperclass >
void fpa::Base::Dijkstra< _TSuperclass >::
_Visit( const TNode& n )
{
  this->Superclass::_Visit( n );
  this->GetMinimumSpanningTree( )->SetNode(
    n.Vertex, n.Parent, n.FrontId, n.Result
    );
}

// -------------------------------------------------------------------------
template< class _TSuperclass >
bool fpa::Base::Dijkstra< _TSuperclass >::
_Result( TNode& node, const TNode& parent )
{
  node.Result = this->_Cost( node.Vertex, parent.Vertex );
  if( node.Result >= TScalar( 0 ) )
  {
    if( this->m_CostConversionFunction.IsNotNull( ) )
      node.Result = this->m_CostConversionFunction->Evaluate( node.Result );
    node.Result += parent.Result;
    return( true );
  }
  else
    return( false );
}

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

// -------------------------------------------------------------------------
template< class _TSuperclass >
void fpa::Base::Dijkstra< _TSuperclass >::
_QueuePush( const TNode& node )
{
  this->m_Queue.push_back( node );
  std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ), DijkstraCmp );
}

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

// -------------------------------------------------------------------------
template< class _TSuperclass >
bool fpa::Base::Dijkstra< _TSuperclass >::
_IsQueueEmpty( ) const
{
  return( this->m_Queue.size( ) == 0 );
}

#endif // __FPA__BASE__DIJKSTRA__HXX__

// eof - $RCSfile$