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

#ifndef __fpa__Base__Graph__hxx__
#define __fpa__Base__Graph__hxx__

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
Clear( )
{
  this->m_Vertices.clear( );
  this->m_Matrix.clear( );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
bool fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
RenameVertex( const TIndex& old_index, const TIndex& new_index )
{
  typename TVertices::iterator old_v = this->m_Vertices.find( old_index );
  typename TVertices::iterator new_v = this->m_Vertices.find( new_index );
  if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
  {
    // Replace vertex
    this->m_Vertices[ new_index ] = old_v->second;
    this->m_Vertices.erase( old_index );

    // Duplicate edges
    typename TMatrix::iterator mIt = this->m_Matrix.begin( );
    typename TMatrix::iterator found_row = this->m_Matrix.end( );
    for( ; mIt != this->m_Matrix.end( ); ++mIt )
    {
      if( mIt->first == old_index )
        found_row = mIt;

      typename TMatrixRow::iterator rIt = mIt->second.begin( );
      for( ; rIt != mIt->second.end( ); ++rIt )
      {
        if( mIt->first == old_index )
          this->m_Matrix[ new_index ][ rIt->first ] = rIt->second;
        else if( rIt->first == old_index )
          this->m_Matrix[ mIt->first ][ new_index ] = rIt->second;

      } // rof

    } // rof

    // Delete old edges
    if( found_row != this->m_Matrix.end( ) )
      this->m_Matrix.erase( found_row );

    mIt = this->m_Matrix.begin( );
    for( ; mIt != this->m_Matrix.end( ); ++mIt )
    {
      typename TMatrixRow::iterator rIt = mIt->second.begin( );
      while( rIt != mIt->second.end( ) )
      {
        if( rIt->first == old_index )
        {
          mIt->second.erase( rIt );
          rIt = mIt->second.begin( );
        }
        else
          ++rIt;

      } // elihw

    } // rof
    return( true );
  }
  else
    return( false );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
RemoveVertex( const TIndex& index )
{
  typename TVertices::iterator i = this->m_Vertices.find( index );
  if( i != this->m_Vertices.end( ) )
  {
    // Delete vertex
    this->m_Vertices.erase( i );

    // Delete edges starting from given vertex
    typename TMatrix::iterator mIt = this->m_Matrix.find( index );
    if( mIt != this->m_Matrix.end( ) )
      this->m_Matrix.erase( mIt );

    // Delete edges arriving to given vertex
    mIt = this->m_Matrix.begin( );
    for( ; mIt != this->m_Matrix.end( ); ++mIt )
    {
      typename TMatrixRow::iterator rIt = mIt->second.begin( );
      while( rIt != mIt->second.end( ) )
      {
        if( rIt->first == index )
        {
          mIt->second.erase( rIt );
          rIt = mIt->second.begin( );
        }
        else
          ++rIt;

      } // elihw

    } // rof

  } // fi
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
typename
fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
TEdges&
fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
GetEdges( const TIndex& orig, const TIndex& dest )
{
  static TEdges null_edges;
  typename TMatrix::iterator o = this->m_Matrix.find( orig );
  if( o != this->m_Matrix.find( orig ) )
  {
    typename TMatrixRow::iterator d = o->second.find( dest );
    if( d == o->second.end( ) )
    {
      null_edges.clear( );
      return( null_edges );
    }
    else
      return( d->second );
  }
  else
  {
    null_edges.clear( );
    return( null_edges );

  } // fi
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
const typename 
fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
TEdges&
fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
GetEdges( const TIndex& orig, const TIndex& dest ) const
{
  static const TEdges null_edges;
  typename TMatrix::iterator o = this->m_Matrix.find( orig );
  if( o != this->m_Matrix.find( orig ) )
  {
    typename TMatrixRow::iterator d = o->second.find( dest );
    if( d == o->second.end( ) )
      return( null_edges );
    else
      return( d->second );
  }
  else
    return( null_edges );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
bool fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
HasEdge( const TIndex& orig, const TIndex& dest ) const
{
  typename TMatrix::const_iterator mIt = this->m_Matrix.find( orig );
  if( mIt != this->m_Matrix.end( ) )
    return( mIt->second.find( dest ) != mIt->second.end( ) );
  else
    return( false );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
{
  typename TMatrix::iterator m = this->m_Matrix.find( orig );
  if( m != this->m_Matrix.end( ) )
  {
    typename TMatrixRow::iterator r = m->second.find( dest );
    if( r != m->second.end( ) )
    {
      typename TEdges::iterator e = r->second.end( );
      for(
        typename TEdges::iterator i = r->second.begin( );
        i != r->second.end( ) && e == r->second.end( );
        ++i
        )
        if( *i == cost )
          e = i;
      if( e != r->second.end( ) )
      {
        r->second.erase( e );
        if( r->second.size( ) == 0 )
        {
          m->second.erase( r );
          if( m->second.size( ) == 0 )
            this->m_Matrix.erase( m );

        } // fi

      } // fi

    } // fi

  } // fi
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
void fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
RemoveEdges( const TIndex& orig, const TIndex& dest )
{
  typename TMatrix::iterator m = this->m_Matrix.find( orig );
  if( m != this->m_Matrix.end( ) )
  {
    typename TMatrixRow::iterator r = m->second.find( dest );
    if( r != m->second.end( ) )
    {
      m->second.erase( r );
      if( m->second.size( ) == 0 )
        this->m_Matrix.erase( m );

    } // fi

  } // fi

}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
std::set< _TIndex, _TIndexCompare >
fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
GetSinks( ) const
{
  std::set< _TIndex, _TIndexCompare > sinks;

  typename TVertices::iterator vIt = this->m_Vertices.begin( );
  for( ; vIt != this->m_Vertices.end( ); ++vIt )
    sinks.insert( vIt->first );
  typename TMatrix::iterator mIt = this->m_Matrix.begin( );
  for( ; mIt != this->m_Matrix.end( ); ++mIt )
    sinks.erase( mIt->first );

  return( sinks );
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
Graph( )
  : Superclass( )
{
}

// -------------------------------------------------------------------------
template< class _TVertex, class _TCost, class _TIndex, class _TIndexCompare >
fpa::Base::Graph< _TVertex, _TCost, _TIndex, _TIndexCompare >::
~Graph( )
{
}

#endif // __fpa__Base__Graph__hxx__

// eof - $RCSfile$