#ifndef __fpa__Base__MinimumSpanningTree__h__
#define __fpa__Base__MinimumSpanningTree__h__

#include <fpa/Config.h>
#include <vector>
#include <utility>
#include <itkObject.h>

namespace fpa
{
  namespace Base
  {
    /**
     */
    template< class _TVertex, class _TPath, class _TSuperclass >
    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 _TPath                        TPath;
      typedef std::pair< _TVertex, bool >   TCollision;
      typedef std::vector< TCollision >     TCollisionsRow;
      typedef std::vector< TCollisionsRow > TCollisions;

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

    public:
      itkTypeMacro( MinimumSpanningTree, _TSuperclass );

    public:
      const TCollisions& GetCollisions( ) const;
      void SetCollisions( const TCollisions& collisions );

      void ClearSeeds( );
      void AddSeed( const _TVertex& seed );

      virtual _TVertex GetParent( const _TVertex& v ) const = 0;
      virtual void SetParent( const _TVertex& v, const _TVertex& p ) = 0;

      virtual void GetPath(
        typename _TPath::Pointer& path, const _TVertex& a
        ) const;
      virtual void GetPath(
        typename _TPath::Pointer& path, const _TVertex& a, const _TVertex& b
        ) const;

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

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

    protected:
      TCollisions m_Collisions;
      _TMatrix    m_FrontPaths;
      std::vector< _TVertex > m_Seeds;
    };

  } // ecapseman

} // ecapseman

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

#endif // __fpa__Base__MinimumSpanningTree__h__

// eof - $RCSfile$