11 #ifndef smtk_common_UnionFind_h
12 #define smtk_common_UnionFind_h
34 m_parent = other.m_parent;
35 m_rank = other.m_rank;
68 void collapseIds(std::map<T, T>& collapsedIds, T startCount);
70 T
size()
const {
return static_cast<T
>(m_sets.size()); }
72 std::vector<UnionFindSet<T>> m_sets;
78 T setId = this->size();
80 m_sets.push_back(entry);
87 T aRoot = this->find(a);
88 T bRoot = this->find(b);
95 if (aRoot < 0 || bRoot < 0)
100 T aRank = m_sets[aRoot].m_rank;
101 T bRank = m_sets[bRoot].m_rank;
104 m_sets[aRoot].m_parent = bRoot;
107 else if (bRank == aRank)
109 ++m_sets[aRoot].m_rank;
111 m_sets[bRoot].m_parent = aRoot;
118 if (src < 0 || src >= this->size())
122 T parent = m_sets[src].m_parent;
125 m_sets[src].m_parent = this->find(parent);
127 return m_sets[src].m_parent;
133 typename std::set<T> roots;
134 typename std::vector<UnionFindSet<T>>::iterator it;
136 for (it = m_sets.begin(); it != m_sets.end(); ++it, ++i)
138 if (i == it->m_parent)
149 std::set<T> roots = this->roots();
150 typename std::set<T>::iterator it;
151 for (it = roots.begin(); it != roots.end(); ++it)
154 typename std::map<T, T>::iterator cit = collapsedIds.find(*it);
155 if (cit == collapsedIds.end())
158 collapsedIds[*it] = startCount++;
166 #endif // smtk_common_UnionFind_h