DisjointSets.hpp

Go to the documentation of this file.

#ifndef GL_DISJOINT_SETS_HPP
#define GL_DISJOINT_SETS_HPP

#include "../gl_base.hpp"

#include <vector>

namespace gl
{
class DisjointSets {
using idx_t = gl::index_type;
public:
  DisjointSets() = default;
  explicit DisjointSets (idx_t numElems);
  // other constructors
  DisjointSets(const DisjointSets &) = default;                
  DisjointSets(DisjointSets &&) noexcept = default;            
  DisjointSets &operator=(const DisjointSets &) = default;     
  DisjointSets &operator=(DisjointSets &&) noexcept = default; 
  ~DisjointSets() = default;                            

  idx_t find (idx_t elem);
  void merge (idx_t one, idx_t two);    

private:
  idx_t numElems_;            
  std::vector<idx_t> parent_; 
  std::vector<idx_t> rank_;   
};

//    Member function implementations

DisjointSets::DisjointSets (idx_t numElems) :
numElems_(numElems), rank_(numElems,0), parent_(numElems) {
  for (idx_t i = 0; i < numElems; ++i) {
    parent_[i] = i;
  }
}

typename DisjointSets::idx_t DisjointSets::find (idx_t elem) {
  GL_ASSERT(elem < numElems_,std::string(std::string("DisjointSets::find || Element ")+std::to_string(elem)+std::string(" is larger than the max: ")+std::to_string(numElems_-1)));
  if (elem != parent_[elem])
    parent_[elem] = find(parent_[elem]);
  return parent_[elem];
}

void DisjointSets::merge (idx_t one, idx_t two) {
  GL_ASSERT(one < numElems_,std::string(std::string("DisjointSets::find || Element ")+std::to_string(one)+std::string(" is larger than the max: ")+std::to_string(numElems_-1)));
  GL_ASSERT(two < numElems_,std::string(std::string("DisjointSets::find || Element ")+std::to_string(two)+std::string(" is larger than the max: ")+std::to_string(numElems_-1)));

  one = find(one);
  two = find(two); 
  if (rank_[one] > rank_[two]) {
    parent_[two] = one;
  }
  else {
    parent_[one] = two;
  }
  if (rank_[one] == rank_[two])
    ++rank_[two]; 
}

} // namespace gl

#endif // GL_DISJOINT_SETS_HPP