1 #ifndef TERRACES_UNION_FIND_HPP
2 #define TERRACES_UNION_FIND_HPP
3 
4 #include <algorithm>
5 
6 #include <terraces/trees.hpp>
7 
8 #include "stack_allocator.hpp"
9 
10 namespace terraces {
11 
12 class union_find {
13 public:
14 	using value_type = index;
15 
16 private:
17 	std::vector<index, utils::stack_allocator<index>> m_parent;
18 #ifndef NDEBUG
19 	bool m_compressed;
20 #endif // NDEBUG
21 
22 public:
23 	union_find(index, utils::stack_allocator<index> a);
24 	index find(index);
simple_find(index x) const25 	index simple_find(index x) const {
26 		assert(m_compressed);
27 		return is_representative(x) ? x : m_parent[x];
28 	}
size() const29 	index size() const { return m_parent.size(); }
30 	void compress();
31 	void merge(index, index);
is_representative(index x) const32 	bool is_representative(index x) const { return m_parent[x] >= m_parent.size(); }
33 
34 	static union_find make_bipartition(const std::vector<bool>& split,
35 	                                   utils::stack_allocator<index> alloc);
36 };
37 
38 } // namespace terraces
39 
40 #endif // TERRACES_UNION_FIND_HPP
41