1 // Copyright (c) 1997-2000
2 // Utrecht University (The Netherlands),
3 // ETH Zurich (Switzerland),
4 // INRIA Sophia-Antipolis (France),
5 // Max-Planck-Institute Saarbruecken (Germany),
6 // and Tel-Aviv University (Israel). All rights reserved.
7 //
8 // This file is part of CGAL (www.cgal.org)
9 //
10 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Union_find/include/CGAL/Union_find.h $
11 // $Id: Union_find.h fcd4e57 2020-05-22T11:29:03+02:00 Marc Glisse
12 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
13 //
14 //
15 // Author(s) : Michael Seel <seel@mpi-sb.mpg.de>,
16 // Lutz Kettner <kettner@mpi-sb.mpg.de>
17
18
19 #ifndef CGAL_UNION_FIND_H
20 #define CGAL_UNION_FIND_H
21
22 #include <CGAL/basic.h>
23 #include <CGAL/memory.h>
24 #include <cstddef>
25
26 namespace CGAL {
27
28 namespace internal {
29
30 template <class PTR_, class V_, class R_, class P_>
31 class UF_forward_iterator {
32 PTR_ m_p;
33 public:
34 // should be private and Union_find<...> a friend.
ptr()35 PTR_ ptr() const { return m_p; }
36
37 typedef UF_forward_iterator<PTR_, V_, R_, P_> Self;
38 typedef V_ value_type;
39 typedef R_ reference;
40 typedef P_ pointer;
41 typedef std::forward_iterator_tag iterator_category;
42
UF_forward_iterator()43 UF_forward_iterator() : m_p(0) {}
UF_forward_iterator(PTR_ p)44 UF_forward_iterator(PTR_ p) : m_p(p) {}
45
46 // Allows construction of const_iterator from iterator
47 template <class PPTR, class VV, class RR, class PP>
UF_forward_iterator(const UF_forward_iterator<PPTR,VV,RR,PP> & i)48 UF_forward_iterator(const UF_forward_iterator<PPTR, VV, RR, PP>& i)
49 : m_p(i.ptr()) {}
50
51 bool operator==( const Self& x) const { return m_p == x.m_p; }
52 bool operator!=( const Self& x) const { return !(*this == x); }
53 bool operator<(const Self& other) const{ return m_p<other.m_p; }
54 bool operator>(const Self& other) const{ return m_p>other.m_p; }
55 bool operator<=(const Self& other) const{ return m_p<=other.m_p; }
56 bool operator>=(const Self& other) const{ return m_p>=other.m_p; }
57
58 reference operator*() const { return m_p->value; }
59 pointer operator->() const { return &(m_p->value); }
60 Self& operator++() {
61 CGAL_assertion(m_p != 0);
62 m_p = m_p->next;
63 return *this;
64 }
65 Self operator++(int) {
66 Self tmp = *this;
67 ++*this;
68 return tmp;
69 }
70 };
71
72 } // internal
73
74
75 // Union-Find with path compression.
76 // --------------------------------------------------------------------
77 // An instance of the data type Union_find is a partition of values of
78 // type |T| into disjoint sets. The type |A| has to be a model of the
79 // allocator concept as defined in the C++ standard.
80
81 // Union_find is implemented with union by rank and path compression.
82 // The running time for $m$ set operations on $n$ elements is
83 // $O(n \alpha(m,n))$ where $\alpha(m,n)$ is the extremely slow
84 // growing inverse of Ackermann's function.
85
86 template <typename T, typename A = CGAL_ALLOCATOR(T) >
87 class Union_find {
88 struct Union_find_struct {
89 typedef Union_find_struct* pointer;
90 // friend class Union_find<T,A>;
91 mutable pointer up;
92 pointer next;
93 std::size_t size;
94 T value;
Union_find_structUnion_find_struct95 Union_find_struct( pointer n, const T& x)
96 : up(0), next(n), size(1), value(x) {}
97 };
98
99 public:
100 typedef Union_find<T,A> Self;
101 typedef Union_find_struct* pointer;
102 typedef const Union_find_struct* const_pointer;
103
104 typedef T value_type;
105 typedef T& reference;
106 typedef const T& const_reference;
107
108 typedef internal::UF_forward_iterator< pointer, T, T&, T*> iterator;
109 typedef iterator handle;
110 typedef internal::UF_forward_iterator< const_pointer, T, const T&, const T*>
111 const_iterator;
112 typedef const_iterator const_handle;
113
114 #ifdef _MSC_VER
115 typedef CGAL_ALLOCATOR(Union_find_struct) allocator;
116 #else
117 typedef typename std::allocator_traits<A>::template rebind_alloc<Union_find_struct> allocator;
118 #endif
119
120 private:
121 pointer m_first;
122 std::size_t sets;
123 std::size_t values;
124 allocator alloc;
125
126 // Private decl. and no definition, thus no copy constructor
127 // and no assignment for this class.
128 Union_find(const Self&);
129 Self& operator=(const Self&);
130
find(pointer p)131 pointer find( pointer p) const {
132 CGAL_assertion(p != 0);
133 pointer r = p;
134 while (r->up)
135 r = r->up; // now r is the root;
136 while (p->up) {
137 pointer u = p->up;
138 p->up = r; // path compression: assign root r as new parent
139 p = u; // this would need the 'mutable' for the up field
140 } // if we would have a const_pointer, see the cast
141 return r; // in the fct. below. We keep the mutable as reminder.
142 }
find(const_pointer p)143 const_pointer find( const_pointer p ) const {
144 return find( const_cast<pointer>(p));
145 }
is_valid(const_handle v)146 bool is_valid(const_handle v) const { return v != const_handle(0); }
147
148 public:
Union_find()149 Union_find() : m_first(0), sets(0), values(0) {}
~Union_find()150 ~Union_find() { clear(); }
151
get_allocator()152 allocator get_allocator() const { return alloc; }
153
number_of_sets()154 std::size_t number_of_sets() const { return sets; }
155 // returns the number of disjoint sets
156
size()157 std::size_t size() const { return values; }
158 // returns the number of values
159
bytes()160 std::size_t bytes() const {
161 // returns the memory consumed
162 return values * sizeof(Union_find_struct) + sizeof( Self);
163 }
164
size(const_handle p)165 std::size_t size( const_handle p) const { return find(p).ptr()->size; }
166 // returns the size of the set containing $p$
167
168 void clear();
169 // reinitializes to an empty partition
170
171 handle make_set(const T& x);
172 // creates a new singleton set containing |x| and returns a handle to it
173
push_back(const T & x)174 handle push_back(const T& x) { return make_set(x); }
175 // same as |make_set(x)|
176
177 template <class Forward_iterator>
insert(Forward_iterator first,Forward_iterator beyond)178 void insert( Forward_iterator first, Forward_iterator beyond) {
179 // insert the range of values referenced by |[first,beyond)|.
180 // Precond: value type of |Forward_iterator| is |T|.
181 while (first != beyond)
182 push_back(*first++);
183 }
184
find(handle p)185 handle find( handle p) const { return find(p.ptr()); }
186
find(const_handle p)187 const_handle find( const_handle p ) const {
188 // returns a canonical handle of the set that contains |p|,
189 // i.e., |P.same_set(p,q)| iff |P.find(p)| and |P.find(q)| return
190 // the same handle. Precond: |p| is a handle in the union find structure.
191 return find(p.ptr());
192 }
193
194 void unify_sets(handle p, handle q);
195 // unites the sets of partition containing $p$ and $q$.
196 // Precond: $p$ and $q$ are in the partition.
197
same_set(const_handle p,const_handle q)198 bool same_set( const_handle p, const_handle q) const {
199 // returns true iff $p$ and $q$ belong to the same set.
200 // Precond: $p$ and $q$ are in the partition.
201 return find(p) == find(q);
202 }
203
begin()204 iterator begin() { return iterator(m_first); }
end()205 iterator end() { return iterator(0); }
206
begin()207 const_iterator begin() const { return const_iterator(m_first); }
end()208 const_iterator end() const { return const_iterator(0); }
209 };
210
211 template <typename T, typename A>
make_set(const T & x)212 typename Union_find<T,A>::handle Union_find<T,A>::make_set(const T& x) {
213 pointer tmp = m_first;
214 m_first = alloc.allocate(1);
215 std::allocator_traits<allocator>::construct(alloc, m_first, tmp, x);
216 ++sets;
217 ++values;
218 return handle( m_first);
219 }
220
221 template <typename T, typename A>
clear()222 void Union_find<T,A>::clear() {
223 while (m_first) {
224 pointer tmp = m_first->next;
225 std::allocator_traits<allocator>::destroy(alloc, m_first);
226 alloc.deallocate(m_first,1);
227 m_first = tmp;
228 }
229 sets = 0;
230 values = 0;
231 }
232
233 template <typename T, typename A>
unify_sets(handle p,handle q)234 void Union_find<T,A>::unify_sets( handle p, handle q) {
235 CGAL_assertion( is_valid(p) && is_valid(q));
236 pointer pit = find( p.ptr());
237 pointer qit = find( q.ptr());
238 if (pit == qit)
239 return;
240 std::size_t sp = pit->size;
241 std::size_t sq = qit->size;
242 if (sp > sq)
243 std::swap(pit,qit); // now sp <= sq
244 pit->up = qit; // linking roots
245 qit->size += pit->size; // updating size
246 --sets;
247 }
248
249 } //namespace CGAL
250
251 #endif // CGAL_UNION_FIND_H
252