#ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__
#define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__

// -------------------------------------------------------------------------
template< class V, class C, class I >
typename cpExtensions::DataStructures::Graph< V, C, I >::
TVertices::iterator cpExtensions::DataStructures::Graph< V, C, I >::
BeginVertices( )
{
  return( this->m_Vertices.begin( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
typename cpExtensions::DataStructures::Graph< V, C, I >::
TVertices::iterator cpExtensions::DataStructures::Graph< V, C, I >::
EndVertices( )
{
  return( this->m_Vertices.end( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
typename cpExtensions::DataStructures::Graph< V, C, I >::
TVertices::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
BeginVertices( ) const
{
  return( this->m_Vertices.begin( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
typename cpExtensions::DataStructures::Graph< V, C, I >::
TVertices::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
EndVertices( ) const
{
  return( this->m_Vertices.end( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
typename cpExtensions::DataStructures::Graph< V, C, I >::
TMatrix::iterator cpExtensions::DataStructures::Graph< V, C, I >::
BeginEdgesRows( )
{
  return( this->m_Matrix.begin( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
typename cpExtensions::DataStructures::Graph< V, C, I >::
TMatrix::iterator cpExtensions::DataStructures::Graph< V, C, I >::
EndEdgetsRows( )
{
  return( this->m_Matrix.end( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
typename cpExtensions::DataStructures::Graph< V, C, I >::
TMatrix::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
BeginEdgesRows( ) const
{
  return( this->m_Matrix.begin( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
typename cpExtensions::DataStructures::Graph< V, C, I >::
TMatrix::const_iterator cpExtensions::DataStructures::Graph< V, C, I >::
EndEdgesRows( ) const
{
  return( this->m_Matrix.end( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
Clear( )
{
  this->m_Vertices.clear( );
  this->m_Matrix.clear( );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
bool cpExtensions::DataStructures::Graph< V, C, I >::
HasVertexIndex( const I& index ) const
{
  return( this->m_Vertices.find( index ) != this->m_Vertices.end( ) );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
SetVertex( const I& index, V& vertex )
{
  this->m_Vertices[ index ] = vertex;
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
bool cpExtensions::DataStructures::Graph< V, C, I >::
RenameVertex( const I& old_index, const I& new_index )
{
  auto old_v = this->m_Vertices.find( old_index );
  auto new_v = this->m_Vertices.find( new_index );
  if( old_v != this->m_Vertices.end( ) && new_v == this->m_Vertices.end( ) )
  {
    // Replace vertex
    typename TVertices::value_type new_entry( new_index, old_v->second );
    new_v = this->m_Vertices.insert( new_entry ).first;
    this->m_Vertices.erase( old_index );

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

      auto 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 )
    {
      auto 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 V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
RemoveVertex( const I& index )
{
#error REMOVE
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
V& cpExtensions::DataStructures::Graph< V, C, I >::
GetVertex( const I& index )
{
  return( this->m_Vertices[ index ] );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
const V& cpExtensions::DataStructures::Graph< V, C, I >::
GetVertex( const I& index ) const
{
  return( this->m_Vertices[ index ] );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
AddConnection( const I& orig, const I& dest, const C& cost )
{
  this->m_Matrix[ orig ][ dest ].push_back( cost );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
void cpExtensions::DataStructures::Graph< V, C, I >::
RemoveConnection( const I& orig, const I& dest, const C& cost )
{
#error remove connection
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
std::set< I > cpExtensions::DataStructures::Graph< V, C, I >::
GetSinks( ) const
{
  std::set< I > sinks;

  auto vIt = this->m_Vertices.begin( );
  for( ; vIt != this->m_Vertices.end( ); ++vIt )
    sinks.insert( vIt->first );
  auto mIt = this->m_Matrix.begin( );
  for( ; mIt != this->m_Matrix.end( ); ++mIt )
    sinks.erase( mIt->first );

  return( sinks );
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
cpExtensions::DataStructures::Graph< V, C, I >::
Graph( )
  : Superclass( )
{
}

// -------------------------------------------------------------------------
template< class V, class C, class I >
cpExtensions::DataStructures::Graph< V, C, I >::
~Graph( )
{
}

#endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__HXX__

// eof - $RCSfile$