#ifndef __FPA__BASE__MINIMUMSPANNINGTREE__HXX__
#define __FPA__BASE__MINIMUMSPANNINGTREE__HXX__

#include <limits>

// -------------------------------------------------------------------------
template< class V, class C, class B >
const unsigned long fpa::Base::MinimumSpanningTree< V, C, B >::INF_VALUE =
  std::numeric_limits< unsigned long >::max( ) >> 1;

// -------------------------------------------------------------------------
template< class V, class C, class B >
void fpa::Base::MinimumSpanningTree< V, C, B >::
SetCollisions( const TCollisions& collisions )
{
  this->m_Collisions = collisions;

  // Prepare fronts graph using Floyd-Warshall
  unsigned long nSeeds = this->m_Collisions.size( );
  _TMatrix dist( nSeeds, _TRow( nSeeds, Self::INF_VALUE ) );
  this->m_FrontPaths = dist;

  for( unsigned long i = 0; i < nSeeds; ++i )
  {
    for( unsigned long j = 0; j < nSeeds; ++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
  for( unsigned long k = 0; k < nSeeds; ++k )
  {
    for( unsigned long i = 0; i < nSeeds; ++i )
    {
      for( unsigned long j = 0; j < nSeeds; ++j )
      {
        if( ( dist[ i ][ k ] + dist[ k ][ j ] ) < dist[ i ][ j ] )
        {
          dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
          this->m_FrontPaths[ i ][ j ] = this->m_FrontPaths[ i ][ k ];

        } // fi

      } // rof

    } // rof

  } // rof

  this->Modified( );
}

// -------------------------------------------------------------------------
template< class V, class C, class B >
void fpa::Base::MinimumSpanningTree< V, C, B >::
GetPath( std::vector< V >& path, const V& a, const V& b ) const
{
  long fa = this->_FrontId( a );
  long fb = this->_FrontId( b );

  if( fa == fb )
  {
    std::vector< V > ap, bp;
    this->_Path( ap, a );
    this->_Path( bp, b );

    // Ignore common part
    typename std::vector< V >::const_reverse_iterator raIt, rbIt;
    raIt = ap.rbegin( );
    rbIt = bp.rbegin( );
    while( *raIt == *rbIt && raIt != ap.rend( ) && rbIt != bp.rend( ) )
    {
      ++raIt;
      ++rbIt;

    } // elihw
    if( raIt != ap.rbegin( ) ) --raIt;
    if( rbIt != bp.rbegin( ) ) --rbIt;

    // Add part from a
    typename std::vector< V >::const_iterator iaIt = ap.begin( );
    for( ; iaIt != ap.end( ) && *iaIt != *raIt; ++iaIt )
      path.push_back( *iaIt );

    // Add part from b
    for( ; rbIt != bp.rend( ); ++rbIt )
      path.push_back( *rbIt );
  }
  else
  {
    // Use this->m_FrontPaths from Floyd-Warshall
    if( this->m_FrontPaths[ fa ][ fb ] != Self::INF_VALUE )
    {
      // Compute front path
      std::vector< long > fpath;
      fpath.push_back( fa );
      while( fa != fb )
      {
        fa = this->m_FrontPaths[ fa ][ fb ];
        fpath.push_back( fa );

      } // elihw

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

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

        } // rof

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

      } // fi

    } // fi

  } // fi
}

// -------------------------------------------------------------------------
template< class V, class C, class B >
fpa::Base::MinimumSpanningTree< V, C, B >::
MinimumSpanningTree( )
  : Superclass( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class B >
fpa::Base::MinimumSpanningTree< V, C, B >::
~MinimumSpanningTree( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class B >
void fpa::Base::MinimumSpanningTree< V, C, B >::
_Path( std::vector< V >& path, const V& a ) const
{
  V it = a;
  do
  {
    path.push_back( it );
    it = this->_Parent( it );

  } while( it != this->_Parent( it ) );
  path.push_back( it );
}

#endif // __FPA__BASE__MINIMUMSPANNINGTREE__HXX__

// eof - $RCSfile$