#ifndef __FPA__BASE__MINIMUMSPANNINGTREE__H__
#define __FPA__BASE__MINIMUMSPANNINGTREE__H__

#include <functional>
#include <map>
#include <utility>
#include <vector>
#include <itkSimpleDataObjectDecorator.h>

namespace fpa
{
  namespace Base
  {
    /**
     */
    template< class _TVertex, class _TScalar, class _TVertexCompare = std::less< _TVertex > >
    class MinimumSpanningTree
      : public itk::SimpleDataObjectDecorator< std::map< _TVertex, std::pair< _TVertex, std::pair< _TScalar, long > >, _TVertexCompare > >
    {
    public:
      typedef std::pair< _TScalar, long >                    TData;
      typedef std::pair< _TVertex, TData >                   TParent;
      typedef std::map< _TVertex, TParent, _TVertexCompare > TContainer;
      typedef itk::SimpleDataObjectDecorator< TContainer >   Superclass;
      typedef MinimumSpanningTree                            Self;
      typedef itk::SmartPointer< Self >                      Pointer;
      typedef itk::SmartPointer< const Self >                ConstPointer;

      typedef _TVertex        TVertex;
      typedef _TScalar        TScalar;
      typedef _TVertexCompare TVertexCompare;

      typedef std::vector< TVertex >        TVertices;
      typedef std::pair< TVertex, bool >    TCollision;
      typedef std::vector< TCollision >     TCollisionsRow;
      typedef std::vector< TCollisionsRow > TCollisions;

      typedef std::multimap< double, _TVertex > TNodeQueue;

    protected:
      typedef std::vector< unsigned long >  _TRow;
      typedef std::vector< _TRow > _TMatrix;

    public:
      itkNewMacro( Self );
      itkTypeMacro( MinimumSpanningTree, itk::SimpleDataObjectDecorator );

      itkBooleanMacro( FillNodeQueue );

      itkGetConstReferenceMacro( Collisions, TCollisions );
      itkGetConstReferenceMacro( NodeQueue, TNodeQueue );
      itkGetConstMacro( FillNodeQueue, bool );

      itkSetMacro( FillNodeQueue, bool );

    public:
      void SetCollisions( const TCollisions& collisions );
      TVertices GetPath( const _TVertex& a ) const;
      TVertices GetPath( const _TVertex& a, const _TVertex& b ) const;

      virtual void SetNode(
        const _TVertex& vertex,
        const _TVertex& parent,
        const long& fid = -1,
        const _TScalar& result = _TScalar( 0 )
        );
      virtual void Clear( );

    protected:
      MinimumSpanningTree( );
      virtual ~MinimumSpanningTree( );

      virtual bool _HasVertex( const _TVertex& a ) const;
      virtual long _FrontId( const _TVertex& a ) const;
      virtual void _Path( TVertices& path, const _TVertex& a ) const;

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

    protected:
      TCollisions m_Collisions;
      _TMatrix    m_FrontPaths;
      TNodeQueue  m_NodeQueue;
      bool        m_FillNodeQueue;

      static const unsigned long INF_VALUE;
    };

  } // ecapseman

} // ecapseman

#ifndef ITK_MANUAL_INSTANTIATION
#  include <fpa/Base/MinimumSpanningTree.hxx>
#endif

#endif // __FPA__BASE__MINIMUMSPANNINGTREE__H__

// eof - $RCSfile$