13 #ifndef LIMBO_CONTAINERS_DISJOINTSET_H
14 #define LIMBO_CONTAINERS_DISJOINTSET_H
35 template <
typename SubsetHelperType>
36 static typename SubsetHelperType::element_type
const&
find_set(SubsetHelperType
const& gp,
typename SubsetHelperType::element_type
const& e)
38 if (gp.get_parent(e) == e)
40 return find_set(gp, gp.get_parent(e));
48 template <
typename SubsetHelperType>
49 static void union_set(SubsetHelperType& gp,
typename SubsetHelperType::element_type
const& e1,
typename SubsetHelperType::element_type
const& e2)
51 typename SubsetHelperType::element_type
const& root1 =
find_set(gp, e1);
52 typename SubsetHelperType::element_type
const& root2 =
find_set(gp, e2);
54 if (gp.get_rank(root1) < gp.get_rank(root2))
55 gp.set_parent(root1, root2);
56 else if (gp.get_rank(root1) > gp.get_rank(root2))
57 gp.set_parent(root2, root1);
60 gp.set_parent(root2, root1);
61 gp.set_rank(root1, gp.get_rank(root1)+1);
68 template <
typename SubsetHelperType>
69 static std::size_t
count_sets(SubsetHelperType
const& gp)
71 std::size_t count = 0;
72 for (
typename SubsetHelperType::element_type i = 0, ie = gp.size(); i != ie; ++i)
73 if (gp.get_parent(i) == i)
82 template <
typename ElementType,
typename RankType>
86 typedef ElementType element_type;
87 typedef RankType rank_type;
96 SubsetHelper(std::vector<element_type>& vp, std::vector<rank_type>& vr)
101 for (
unsigned int i = 0, ie = vParent.size(); i != ie; ++i)
103 std::fill(vRank.begin(), vRank.end(), 0);
108 inline element_type
const&
get_parent(element_type
const& e)
const {
return vParent[e];}
112 inline void set_parent(element_type
const& e, element_type
const& p) {vParent[e] = p;}
116 inline rank_type
const&
get_rank(element_type
const& e)
const {
return vRank[e];}
120 inline void set_rank(element_type
const& e, rank_type
const& r) {vRank[e] = r;}
122 inline std::size_t
size()
const {
return vParent.size();}
static void union_set(SubsetHelperType &gp, typename SubsetHelperType::element_type const &e1, typename SubsetHelperType::element_type const &e2)
union two subsets represented by element e1 and e2
SubsetHelper(std::vector< element_type > &vp, std::vector< rank_type > &vr)
constructor
simply used for scope control
static std::size_t count_sets(SubsetHelperType const &gp)
a sample implementation of SubsetHelper that uses std::vector as the container. It needs to store par...
element_type const & get_parent(element_type const &e) const
get parent element
std::vector< rank_type > & vRank
reference to rank array
std::vector< element_type > & vParent
reference to parent array
static SubsetHelperType::element_type const & find_set(SubsetHelperType const &gp, typename SubsetHelperType::element_type const &e)
find the subset of an element e
void set_rank(element_type const &e, rank_type const &r)
set rank
rank_type const & get_rank(element_type const &e) const
get rank
void set_parent(element_type const &e, element_type const &p)
set parent element