#ifndef __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__
#define __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__

#include <map>
#include <set>
#include <vector>
#include <itkLightObject.h>
#include <itkObjectFactory.h>

namespace cpExtensions
{
  namespace DataStructures
  {
    /** \brief A generic graph with templated index types.
     *
     *  @param V Vertex type.
     *  @param C Cost type.
     *  @param I Index type (it should be a strict weak ordering type).
     */
    template< class V, class C, class I = unsigned long >
    class Graph
      : public itk::LightObject
    {
    public:
      typedef Graph                           Self;
      typedef itk::LightObject                Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

      typedef V TVertex;
      typedef C TCost;
      typedef I TIndex;

      // Base types
      typedef std::map< TIndex, TVertex >    TVertices;
      typedef std::vector< TCost >           TEdges;
      typedef std::map< TIndex, TEdges >     TMatrixRow;
      typedef std::map< TIndex, TMatrixRow > TMatrix;

    public:
      itkNewMacro( Self );
      itkTypeMacro( Graph, itk::LightObject );

    public:
      /*! \brief Iterators over vertices.
       *         These allow you to iterate over all of graph's vertices.
       *
       * Typical iteration should be done as:
       *
       *  TGraph g;
       *  ...
       *  TGraph::TVertices::[const_]iterator vIt = g.BeginVertices( );
       *  for( ; vIt != g.EndVertices( ); ++vIt )
       *  {
       *    vIt->first;  --> this is the vertex's index <--
       *    vIt->second; --> this is the vertex's value <--
       *  }
       */
      inline typename TVertices::iterator BeginVertices( )
        { return( this->m_Vertices.begin( ) ); }
      inline typename TVertices::iterator EndVertices( )
        { return( this->m_Vertices.end( ) ); }
      inline typename TVertices::const_iterator BeginVertices( ) const
        { return( this->m_Vertices.begin( ) ); }
      inline typename TVertices::const_iterator EndVertices( ) const
        { return( this->m_Vertices.end( ) ); }

      /*! \brief Iterators over edges.
       *         These allow you to iterate over all of graph's edges.
       *
       * Typical iteration should be done as:
       *
       *  TGraph g;
       *  ...
       *  TGraph::TMatrix::[const_]iterator mIt = g.BeginEdgesRows( );
       *  for( ; mIt != g.EndEdgesRows( ); ++mIt )
       *  {
       *    mIt->first; --> this is the row index. <--
       *    TGraph::TMatrixRow::[const_]iterator rIt = mIt->second.begin( );
       *    for( ; rIt != mIt->second.end( ); ++rIt )
       *    {
       *      rIt->first;  --> this is the column index.
       *      TGraph::TEdges::[const_]iterator eIt = rIt->second.begin( );
       *      for( ; eIt != rIt->second.end( ); ++eIt )
       *        *eIt; --> this is the cost between mIt->first and rIt->first
       *    }
       *  }
       */
      inline typename TMatrix::iterator BeginEdgesRows( )
        { return( this->m_Matrix.begin( ) ); }
      inline typename TMatrix::iterator EndEdgetsRows( )
        { return( this->m_Matrix.end( ) ); }
      inline typename TMatrix::const_iterator BeginEdgesRows( ) const
        { return( this->m_Matrix.begin( ) ); }
      inline typename TMatrix::const_iterator EndEdgesRows( ) const
        { return( this->m_Matrix.end( ) ); }

      /*! \brief Clear all vertices and edges.
       */
      void Clear( );

      /*! \brief Clear all edges.
       */
      inline void ClearEdges( )
        { this->m_Matrix.clear( ); }

      /*! \brief Vertex manipulation methods.
       *         Names are self-explanatory.
       */
      inline bool HasVertexIndex( const I& i ) const
        { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
      inline void SetVertex( const I& index, V& vertex )
        { this->m_Vertices[ index ] = vertex; }
      inline V& GetVertex( const I& index )
        { return( this->m_Vertices[ index ] ); }
      inline const V& GetVertex( const I& index ) const
        { return( this->m_Vertices[ index ] ); }
      bool RenameVertex( const I& old_index, const I& new_index );
      void RemoveVertex( const I& index );

      /*! \brief Edge manipulation methods.
       *         Names are self-explanatory.
       */
      inline void AddEdge( const I& orig, const I& dest, const C& cost )
        { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
      inline TEdges& GetEdges( const I& orig, const I& dest )
        { return( this->m_Matrix[ orig ][ dest ] ); }
      inline const TEdges& GetEdges( const I& orig, const I& dest ) const
        { return( this->m_Matrix[ orig ][ dest ] ); }
      bool HasEdge( const I& orig, const I& dest ) const;
      void RemoveEdge( const I& orig, const I& dest, const C& cost );
      void RemoveEdges( const I& orig, const I& dest );

      /*! \brief Returns graph's sinks.
       *
       *  A sink is a special vertex which does not have any "exiting" edges.
       *
       *  @return Sinks ordered by their index.
       */
      std::set< I > GetSinks( ) const;

    protected:
      Graph( );
      virtual ~Graph( );

    private:
      // Purposely not implemented
      Graph( const Self& other );
      Self& operator=( const Self& other );

    protected:
      TVertices m_Vertices;
      TMatrix   m_Matrix;
    };

  } // ecapseman

} // ecapseman

#ifndef ITK_MANUAL_INSTANTIATION
#include <cpExtensions/DataStructures/Graph.hxx>
#endif // ITK_MANUAL_INSTANTIATION

#endif // __CPEXTENSIONS__DATASTRUCTURES__GRAPH__H__

// eof - $RCSfile$