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

#ifndef __fpa__Base__Graph__h__
#define __fpa__Base__Graph__h__

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

namespace fpa
{
  namespace Base
  {
    /** \brief A generic graph with templated index types.
     *
     *  @param _TVertex Vertex type.
     *  @param _TCost   Cost type.
     *  @param _TIndex  Index type (it should be a strict weak ordering type).
     */
    template< class _TVertex, class _TCost, class _TIndex = unsigned long, class _TIndexCompare = std::less< _TIndex > >
    class Graph
      : public itk::DataObject
    {
    public:
      typedef Graph                           Self;
      typedef itk::DataObject                 Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

      typedef _TVertex       TVertex;
      typedef _TCost         TCost;
      typedef _TIndex        TIndex;
      typedef _TIndexCompare TIndexCompare;

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

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

    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 TIndex& i ) const
        { return( this->m_Vertices.find( i ) != this->m_Vertices.end( ) ); }
      inline void SetVertex( const TIndex& index, TVertex& vertex )
        { this->m_Vertices[ index ] = vertex; }
      inline TVertex& GetVertex( const TIndex& index )
        { return( this->m_Vertices[ index ] ); }
      inline const TVertex& GetVertex( const TIndex& index ) const
        { return( this->m_Vertices[ index ] ); }
      bool RenameVertex( const TIndex& old_index, const TIndex& new_index );
      void RemoveVertex( const TIndex& index );

      /*! \brief Edge manipulation methods.
       *         Names are self-explanatory.
       */
      inline void AddEdge( const TIndex& orig, const TIndex& dest, const TCost& cost )
        { this->m_Matrix[ orig ][ dest ].push_back( cost ); }
      TEdges& GetEdges( const TIndex& orig, const TIndex& dest );
      const TEdges& GetEdges( const TIndex& orig, const TIndex& dest ) const;
      bool HasEdge( const TIndex& orig, const TIndex& dest ) const;
      void RemoveEdge( const TIndex& orig, const TIndex& dest, const TCost& cost );
      void RemoveEdges( const TIndex& orig, const TIndex& 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< TIndex, TIndexCompare > 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 <fpa/Base/Graph.hxx>
#endif // ITK_MANUAL_INSTANTIATION

#endif // __fpa__Base__Graph__h__

// eof - $RCSfile$