10 #ifndef CPROVER_UTIL_UNION_FIND_H 11 #define CPROVER_UTIL_UNION_FIND_H 35 explicit nodet(size_type index):count(1), parent(index)
41 mutable std::vector<nodet>
nodes;
48 size_type
find(size_type a)
const;
61 other.
nodes.swap(nodes);
67 assert(nodes.size()<=
size);
69 while(nodes.size()<
size)
70 nodes.push_back(
nodet(nodes.size()));
84 return nodes[a].parent==a;
104 return nodes[
find(a)].count;
118 for(size_type i=0; i<nodes.size(); i++)
125 void re_root(size_type old, size_type new_root);
131 template <
typename T>
142 size_type na=number(a), nb=number(b);
143 bool is_union=find_number(na)==find_number(nb);
144 uuf.make_union(na, nb);
153 bool is_union=find_number(na)==find_number(nb);
154 uuf.make_union(na, nb);
161 typedef typename subt::number_type subt_number_typet;
162 subt_number_typet na=subt_number_typet(), nb=subt_number_typet();
163 bool have_na=!subt::get_number(a, na),
164 have_nb=!subt::get_number(b, nb);
166 if(have_na && have_nb)
167 return uuf.same_set(na, nb);
168 else if(!have_na && !have_nb)
203 return uuf.find(number(a));
208 return uuf.is_root(a);
213 typename subt::number_type na;
215 if(subt::get_number(a, na))
218 return uuf.is_root(na);
228 size_type n=subt::number(a);
231 uuf.resize(this->size());
233 assert(uuf.size()==this->
size());
251 uuf.isolate(number(a));
259 #endif // CPROVER_UTIL_UNION_FIND_H
size_type find_number(typename numbering< T >::const_iterator it) const
bool is_root(typename numbering< T >::const_iterator it) const
const T & find(const T &a)
void isolate(typename numbering< T >::const_iterator it)
size_type count_roots() const
void resize(size_type size)
const T & find(typename numbering< T >::const_iterator it) const
void make_union(size_type a, size_type b)
bool is_root(size_type a) const
bool same_set(const T &a, const T &b) const
size_type find(size_type a) const
size_type number(const T &a)
bool make_union(typename numbering< T >::const_iterator it_a, typename numbering< T >::const_iterator it_b)
size_type count(size_type a) const
void re_root(size_type old, size_type new_root)
void isolate(size_type a)
void check_index(size_type a)
void swap(unsigned_union_find &other)
size_type find_number(size_type a) const
std::vector< nodet > nodes
numbering< T >::size_type size_type
bool is_root(const T &a) const
size_type find_number(const T &a)
bool make_union(const T &a, const T &b)
void intersection(const unsigned_union_find &other)
bool same_set(size_type a, size_type b) const
size_type get_other(size_type a)
bool same_set(typename numbering< T >::const_iterator it_a, typename numbering< T >::const_iterator it_b) const
bool is_root_number(size_type a) const