#ifndef __FPA__BASE__MINIMUMSPANNINGTREE__H__
#define __FPA__BASE__MINIMUMSPANNINGTREE__H__

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

namespace fpa
{
  namespace Base
  {
    /**
     */
    template< class V, class C, class VC >
    class MinimumSpanningTree
      : public itk::SimpleDataObjectDecorator< std::map< V, std::pair< V, short >, VC > >
    {
    public:
      typedef std::pair< V, short >                        TNodeInfo;
      typedef std::map< V, TNodeInfo, VC >                 TDecorated;
      typedef MinimumSpanningTree                          Self;
      typedef itk::SimpleDataObjectDecorator< TDecorated > Superclass;
      typedef itk::SmartPointer< Self >                    Pointer;
      typedef itk::SmartPointer< const Self >              ConstPointer;

      typedef V  TVertex;
      typedef C  TCollisions;
      typedef VC TVertexCompare;

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

    public:
      itkNewMacro( Self );
      itkTypeMacro( MinimumSpanningTree, itkSimpleDataObjectDecorator );

      itkGetConstMacro( Collisions, TCollisions );

    public:
      void SetCollisions( const TCollisions& collisions );
      void SetParent( const TVertex& v, const TVertex& p, const short& fid )
        {
          this->Get( )[ v ] = TNodeInfo( p, fid );
          this->Modified( );
        }
      void Clear( )
        {
          this->Get( ).clear( );
          this->m_Collisions.clear( );
          this->m_FrontPaths.clear( );
        }
      virtual void GetPath(
        std::vector< V >& path, const V& a, const V& b
        ) const;

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

      virtual void _Path( std::vector< V >& path, const V& a ) const;

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

    protected:
      TCollisions m_Collisions;
      _TMatrix    m_FrontPaths;
      static const unsigned long INF_VALUE;
    };

  } // ecapseman

} // ecapseman

#include <fpa/Base/MinimumSpanningTree.hxx>

#endif // __FPA__BASE__MINIMUMSPANNINGTREE__H__

// eof - $RCSfile$