#ifndef __FPA__BASE__MINIMUMSPANNINGTREE__H__
#define __FPA__BASE__MINIMUMSPANNINGTREE__H__

#include <map>
#include <vector>
#include <utility>
#include <itkPoint.h>
#include <itkSmartPointer.h>

namespace fpa
{
  namespace Base
  {
    /**
     */
    template< class _TSuperclass, class _TVertex >
    class MinimumSpanningTree
      : public _TSuperclass
    {
    public:
      typedef MinimumSpanningTree             Self;
      typedef _TSuperclass                    Superclass;
      typedef itk::SmartPointer< Self >       Pointer;
      typedef itk::SmartPointer< const Self > ConstPointer;

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

      typedef itk::Point< double, TVertex::Dimension > TPoint;
      typedef std::vector< TPoint >                    TPoints;
      typedef std::multimap< double, TVertex >         TNodeQueue;

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

    public:
      itkTypeMacro( MinimumSpanningTree, _TSuperclass );

      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 TPoints GetEuclideanPath( const TVertex& a ) const;
      virtual TPoints GetEuclideanPath(
        const TVertex& a, const TVertex& b
        ) const;
      virtual bool IsDefinedInEuclideanSpace( ) const;

      virtual void SetNode(
        const TVertex& v,
        const TVertex& p,
        const short& fid,
        const double& cost
        );
      virtual void Clear( );

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

      virtual bool _HasVertex( const TVertex& a ) const = 0;
      virtual short _FrontId( const TVertex& a ) const = 0;
      virtual void _Path( TVertices& path, const TVertex& a ) const = 0;

    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 // ITK_MANUAL_INSTANTIATION

#endif // __FPA__BASE__MINIMUMSPANNINGTREE__H__

// eof - $RCSfile$