#ifndef __fpa__Base__MinimumSpanningTree__hxx__
#define __fpa__Base__MinimumSpanningTree__hxx__

#include <limits>

// -------------------------------------------------------------------------
template< class _TVertex, class _TSuperclass >
const typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
TCollisions& fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
GetCollisions( ) const
{
  return( this->m_Collisions );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TSuperclass >
void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
SetCollisions( const TCollisions& collisions )
{
  static const unsigned long _inf =
    std::numeric_limits< unsigned long >::max( );
  if( this->m_Collisions == collisions )
    return;

  this->m_Collisions = collisions;

  // Prepare a front graph
  unsigned long N = this->m_Collisions.size( );
  _TMatrix dist( N, _TRow( N, _inf ) );
  this->m_FrontPaths = dist;
  for( unsigned long i = 0; i < N; ++i )
  {
    for( unsigned long j = 0; j < N; ++j )
    {
      if( this->m_Collisions[ i ][ j ].second )
      {
        dist[ i ][ j ] = 1;
        dist[ j ][ i ] = 1;
        this->m_FrontPaths[ i ][ j ] = j;
        this->m_FrontPaths[ j ][ i ] = i;

      } // fi

    } // rof
    dist[ i ][ i ] = 0;
    this->m_FrontPaths[ i ][ i ] = i;

  } // rof

  // Use Floyd-Warshall to compute all possible paths between fronts
  for( unsigned long k = 0; k < N; ++k )
  {
    for( unsigned long i = 0; i < N; ++i )
    {
      for( unsigned long j = 0; j < N; ++j )
      {
        // WARNING: you don't want a numeric overflow!!!
        unsigned long dik = dist[ i ][ k ];
        unsigned long dkj = dist[ k ][ j ];
        unsigned long sum = _inf;
        if( dik < _inf && dkj < _inf )
          sum = dik + dkj;

        // Ok, continue Floyd-Warshall
        if( sum < dist[ i ][ j ] )
        {
          dist[ i ][ j ] = sum;
          this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];

        } // fi

      } // rof

    } // rof

  } // rof
  this->Modified( );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TSuperclass >
void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
ClearSeeds( )
{
  this->m_Seeds.clear( );
  this->Modified( );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TSuperclass >
void fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
AddSeed( const _TVertex& seed )
{
  this->m_Seeds.push_back( seed );
  this->Modified( );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TSuperclass >
typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
TVertices fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
GetPath( const _TVertex& a ) const
{
  TVertices path;
  _TVertex it = a;
  _TVertex p = this->GetParent( it );
  while( it != p )
  {
    path.push_front( it );
    it = p;
    p = this->GetParent( it );

  } // elihw
  path.push_front( it );
  return( path );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TSuperclass >
typename fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
TVertices fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
GetPath( const _TVertex& a, const _TVertex& b ) const
{
  static const unsigned long _inf =
    std::numeric_limits< unsigned long >::max( );

  TVertices path;
  TVertices pa = this->GetPath( a );
  TVertices pb = this->GetPath( b );
  if( pa.size( ) > 0 && pb.size( ) > 0 )
  {
    // Find front identifiers
    unsigned long ia = _inf, ib = _inf;
    unsigned long N = this->m_Seeds.size( );
    for( unsigned long i = 0; i < N; ++i )
    {
      if( this->m_Seeds[ i ] == pa.front( ) )
        ia = i;
      if( this->m_Seeds[ i ] == pb.front( ) )
        ib = i;

    } // rof

    if( ia != ib )
    {
      // Use this->m_FrontPaths from Floyd-Warshall
      if( this->m_FrontPaths[ ia ][ ib ] < _inf )
      {
        // Compute front path
        std::vector< long > fpath;
        fpath.push_back( ia );
        while( ia != ib )
        {
          ia = this->m_FrontPaths[ ia ][ ib ];
          fpath.push_back( ia );

        } // elihw

        // Continue only if both fronts are connected
        unsigned int N = fpath.size( );
        if( N > 0 )
        {
          // First path: from start vertex to first collision
          path = this->GetPath(
            a, this->m_Collisions[ fpath[ 0 ] ][ fpath[ 1 ] ].first
            );

          // Intermediary paths
          for( unsigned int i = 1; i < N - 1; ++i )
          {
            TVertices ipath =
              this->GetPath(
                this->m_Collisions[ fpath[ i ] ][ fpath[ i - 1 ] ].first,
                this->m_Collisions[ fpath[ i ] ][ fpath[ i + 1 ] ].first
                );
            path.insert( path.end( ), ipath.begin( ), ipath.end( ) );

          } // rof

          // Final path: from last collision to end point
          TVertices lpath =
            this->GetPath(
              this->m_Collisions[ fpath[ N - 1 ] ][ fpath[ N - 2 ] ].first, b
              );
          path.insert( path.end( ), lpath.begin( ), lpath.end( ) );

        } // fi

      } // fi
    }
    else
    {
      // Ignore common part: find common ancestor
      auto aIt = pa.begin( );
      auto bIt = pb.begin( );
      while( *aIt == *bIt && aIt != pa.end( ) && bIt != pb.end( ) )
      {
        ++aIt;
        ++bIt;

      } // elihw

      // Glue both parts
      for( --aIt; aIt != pa.end( ); ++aIt )
        path.push_front( *aIt );
      for( ; bIt != pb.end( ); ++bIt )
        path.push_back( *bIt );

    } // fi

  } // fi
  return( path );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TSuperclass >
fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
MinimumSpanningTree( )
  : Superclass( )
{
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TSuperclass >
fpa::Base::MinimumSpanningTree< _TVertex, _TSuperclass >::
~MinimumSpanningTree( )
{
}

#endif // __fpa__Base__MinimumSpanningTree__hxx__

// eof - $RCSfile$