cmtkUnionFind.h

Go to the documentation of this file.

/*
//
//  Copyright 1997-2010 Torsten Rohlfing
//
//  This file is part of the Computational Morphometry Toolkit.
//
//  http://www.nitrc.org/projects/cmtk/
//
//  The Computational Morphometry Toolkit is free software: you can
//  redistribute it and/or modify it under the terms of the GNU General Public
//  License as published by the Free Software Foundation, either version 3 of
//  the License, or (at your option) any later version.
//
//  The Computational Morphometry Toolkit is distributed in the hope that it
//  will be useful, but WITHOUT ANY WARRANTY; without even the implied
//  warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License along
//  with the Computational Morphometry Toolkit.  If not, see
//  <http://www.gnu.org/licenses/>.
//
//  $Revision: 2199 $
//
//  $LastChangedDate: 2010-08-12 14:20:39 -0700 (Thu, 12 Aug 2010) $
//
//  $LastChangedBy: torstenrohlfing $
//
*/

#ifndef __cmtkUnionFind_h_included_
#define __cmtkUnionFind_h_included_

#include <cmtkconfig.h>

#include <set>
#include <list>

namespace
cmtk
{


template<class T>
class UnionFind
{
public:
  typedef std::set<T> SetType;

  typedef std::list<SetType> ListType;

  typedef typename ListType::iterator FindResultType;

  FindResultType Find( const T& key )
  {
    for ( FindResultType it = this->m_List.begin(); it != this->m_List.end(); ++it )
      {
      if ( it->find( key ) != it->end() )
        return it;
      }
    return this->End();
  }

  const T FindKey( const T& key )
  {
    return *(this->Find( key )->begin());
  }

  FindResultType End()
  {
    return this->m_List.end();
  }

  void Union( const FindResultType& s1, const FindResultType& s2 )
  {
    if ( s1 != s2 )
      {
      s1->insert( s2->begin(), s2->end() );
      this->m_List.erase( s2 );
      }
  }

  void Insert( const T& key )
  {
    SetType newSet;
    newSet.insert( key );
    this->m_List.push_back( newSet );
  }
  
private:
  ListType m_List;
};


} // namespace cmtk

#endif // #ifndef __cmtkUnionFind_h_included_