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