[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

union_find.hxx
1/************************************************************************/
2/* */
3/* Copyright 2008-2009 by Ullrich Koethe */
4/* */
5/* This file is part of the VIGRA computer vision library. */
6/* The VIGRA Website is */
7/* http://hci.iwr.uni-heidelberg.de/vigra/ */
8/* Please direct questions, bug reports, and contributions to */
9/* ullrich.koethe@iwr.uni-heidelberg.de or */
10/* vigra@informatik.uni-hamburg.de */
11/* */
12/* Permission is hereby granted, free of charge, to any person */
13/* obtaining a copy of this software and associated documentation */
14/* files (the "Software"), to deal in the Software without */
15/* restriction, including without limitation the rights to use, */
16/* copy, modify, merge, publish, distribute, sublicense, and/or */
17/* sell copies of the Software, and to permit persons to whom the */
18/* Software is furnished to do so, subject to the following */
19/* conditions: */
20/* */
21/* The above copyright notice and this permission notice shall be */
22/* included in all copies or substantial portions of the */
23/* Software. */
24/* */
25/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27/* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28/* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29/* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30/* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32/* OTHER DEALINGS IN THE SOFTWARE. */
33/* */
34/************************************************************************/
35
36
37#ifndef VIGRA_UNION_FIND_HXX
38#define VIGRA_UNION_FIND_HXX
39
40/*std*/
41#include <map>
42
43/*vigra*/
44#include "config.hxx"
45#include "error.hxx"
46#include "array_vector.hxx"
47#include "iteratoradapter.hxx"
48
49 namespace vigra {
50
51 namespace detail {
52
53 template <class T, class IsSigned = VigraFalseType>
54 struct UnionFindAccessorImpl
55{
56 static const T max_label = NumericTraits<T>::maxConst >> 1;
57 static const T anchor_bit = ~max_label;
58
59 static T max()
60 {
61 return max_label;
62 }
63
64 static T deletedAnchor()
65 {
66 return NumericTraits<T>::maxConst;
67 }
68
69 static bool isAnchor(T const & t)
70 {
71 return (t & anchor_bit) != 0;
72 }
73
74 static bool isValidAnchor(T const & t)
75 {
76 return isAnchor(t) && t != deletedAnchor();
77 }
78
79 static bool notAnchor(T const & t)
80 {
81 return (t & anchor_bit) == 0;
82 }
83
84 static T toAnchor(T const & t)
85 {
86 return t | anchor_bit;
87 }
88
89 static T fromAnchor(T const & t)
90 {
91 return t & max_label;
92 }
93};
94
95 template <class T>
96 struct UnionFindAccessorImpl<T, VigraTrueType>
97{
98 static T max()
99 {
100 return NumericTraits<T>::max();
101 }
102
103 static T deletedAnchor()
104 {
105 return NumericTraits<T>::min();
106 }
107
108 static bool isAnchor(T const & t)
109 {
110 return t < 0;
111 }
112
113 static bool isValidAnchor(T const & t)
114 {
115 return isAnchor(t) && t != deletedAnchor();
116 }
117
118 static bool notAnchor(T const & t)
119 {
120 return t >= 0;
121 }
122
123 static T toAnchor(T const & t)
124 {
125 return -t - 1;
126 }
127
128 static T fromAnchor(T const & t)
129 {
130 return -(t + 1);
131 }
132};
133
134 template <class Array, class LabelAccessor>
135 class UnionFindIteratorPolicy
136{
137 public:
138 typedef UnionFindIteratorPolicy BaseType;
139 typedef typename Array::difference_type value_type;
140 typedef typename Array::difference_type difference_type;
141 typedef value_type const & reference;
142 typedef value_type const & index_reference;
143 typedef value_type const * pointer;
144 typedef typename std::forward_iterator_tag iterator_category;
145
146 Array const & array_;
147 value_type index_;
148
149 UnionFindIteratorPolicy(Array const & array, value_type index=0)
150 : array_(array)
151 , index_(index)
152 {}
153
154 static void initialize(BaseType & d)
155 {
156 advanceToAnchor(d);
157 }
158
159 static reference dereference(BaseType const & d)
160 {
161 return d.index_;
162 }
163
164 static bool equal(BaseType const & d1, BaseType const & d2)
165 {
166 return d1.index_ == d2.index_;
167 }
168
169 static bool less(BaseType const & d1, BaseType const & d2)
170 {
171 return d1.index_ < d2.index_;
172 }
173
174 static void increment(BaseType & d)
175 {
176 ++d.index_;
177 advanceToAnchor(d);
178 }
179
180 static void advanceToAnchor(BaseType & d)
181 {
182 while(d.index_ < (value_type)d.array_.size()-1 &&
183 !LabelAccessor::isValidAnchor(d.array_[d.index_]))
184 {
185 ++d.index_;
186 }
187 }
188};
189
190} // namespace detail
191
192 template <class T>
193 class UnionFindArray
194{
195 typedef ArrayVector<T> LabelArray;
196 typedef typename LabelArray::difference_type IndexType;
197 typedef detail::UnionFindAccessorImpl<T,
198 typename NumericTraits<T>::isSigned> LabelAccessor;
199 typedef detail::UnionFindIteratorPolicy<LabelArray, LabelAccessor> IteratorPolicy;
200 typedef IteratorAdaptor<IteratorPolicy> iterator;
201 typedef iterator const_iterator;
202
203 mutable ArrayVector<T> labels_;
204
205 public:
206 UnionFindArray(T next_free_label = 1)
207 {
208 vigra_precondition(next_free_label <= LabelAccessor::max(),
209 "UnionFindArray(): Need more labels than can be represented"
210 "in the destination type.");
211
212 for(T k=0; k < next_free_label; ++k)
213 labels_.push_back(LabelAccessor::toAnchor(k));
214 labels_.push_back(LabelAccessor::toAnchor(next_free_label));
215 }
216
217 const_iterator begin(unsigned int start_at=0) const
218 {
219 return const_iterator(IteratorPolicy(labels_, start_at));
220 }
221
222 const_iterator end() const
223 {
224 return const_iterator(IteratorPolicy(labels_, labels_.size()-1));
225 }
226
227 T nextFreeIndex() const
228 {
229 return T(labels_.size() - 1);
230 }
231
232 T findIndex(T index) const
233 {
234 IndexType root = index;
235 while(LabelAccessor::notAnchor(labels_[root]))
236 root = (IndexType)labels_[root];
237 // path compression
238 while((IndexType)index != root)
239 {
240 T next = labels_[(IndexType)index];
241 labels_[(IndexType)index] = root;
242 index = next;
243 }
244 return (T)root;
245 }
246
247 T findLabel(T index) const
248 {
249 return LabelAccessor::fromAnchor(labels_[findIndex(index)]);
250 }
251
252 void deleteIndex(T index)
253 {
254 labels_[findIndex(index)] = LabelAccessor::deletedAnchor();
255 }
256
257 // this function does not yet check for deletedIndex()
258 T makeUnion(T l1, T l2)
259 {
260 IndexType i1 = findIndex(l1);
261 IndexType i2 = findIndex(l2);
262 if(i1 == i2)
263 {
264 return i1;
265 }
266 else if(i1 < i2)
267 {
268 labels_[i2] = i1;
269 return (T)i1;
270 }
271 else
272 {
273 labels_[i1] = i2;
274 return (T)i2;
275 }
276 }
277
278 T finalizeIndex(T index)
279 {
280 if(index == (T)labels_.size()-1)
281 {
282 // indeed a new region
283 vigra_invariant(index < LabelAccessor::max(),
284 "connected components: Need more labels than can be represented in the destination type.");
285 // create new back entry
286 labels_.push_back(LabelAccessor::toAnchor((T)labels_.size()));
287 }
288 else
289 {
290 // no new index => reset the back entry of the index array
291 labels_.back() = LabelAccessor::toAnchor((T)labels_.size()-1);
292 }
293 return index;
294 }
295
296 T makeNewIndex()
297 {
298 T index = LabelAccessor::fromAnchor(labels_.back());
299 vigra_invariant(index < LabelAccessor::max(),
300 "connected components: Need more labels than can be represented in the destination type.");
301 labels_.push_back(LabelAccessor::toAnchor((T)labels_.size()));
302 return index;
303 }
304
305 unsigned int makeContiguous()
306 {
307 // compress trees
308 unsigned int count = 0;
309 for(IndexType i=0; i<(IndexType)(labels_.size()-1); ++i)
310 {
311 if(LabelAccessor::isValidAnchor(labels_[i]))
312 {
313 labels_[i] = LabelAccessor::toAnchor((T)count++);
314 }
315 else
316 {
317 labels_[i] = findIndex(i); // path compression
318 }
319 }
320 return count-1;
321 }
322};
323
324} // namespace vigra
325
326#endif // VIGRA_UNION_FIND_HXX
vigra

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.12.1