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

counting_iterator.hxx
1/************************************************************************/
2/* */
3/* Copyright 2015 by Thorsten Beier */
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#ifndef VIGRA_COUNTING_ITERATOR_HXX
37#define VIGRA_COUNTING_ITERATOR_HXX
38
39
40#include <cmath>
41#include <iterator>
42#include <limits>
43#include <type_traits>
44#include "error.hxx"
45#include "tinyvector.hxx"
46
47 namespace vigra {
48
49 namespace detail {
50
51 template <class T, bool is_float=false>
52 struct CountingIteratorCompare
53{
54 // use exact comparison for integer counting
55 static bool equal(T left, T right, T /* step */)
56 {
57 return left == right;
58 }
59 static bool not_equal(T left, T right, T /* step */)
60 {
61 return left != right;
62 }
63 static bool less(T left, T right, T step)
64 {
65 // NOTE: the more efficient '(right - left)*step > 0'
66 // fails for unsigned arguments
67 return step > 0
68 ? left < right
69 : left > right;
70 }
71 static bool less_equal(T left, T right, T step)
72 {
73 return step > 0
74 ? left <= right
75 : left >= right;
76 }
77 static bool greater(T left, T right, T step)
78 {
79 return step > 0
80 ? left > right
81 : left < right;
82 }
83 static bool greater_equal(T left, T right, T step)
84 {
85 return step > 0
86 ? left >= right
87 : left <= right;
88 }
89 // integer counting: if the raw distance is not divisible by step,
90 // we must round upwards
91 static std::ptrdiff_t distance(T from, T to, T step)
92 {
93 const double diff = (double(to) - double(from)) / double(step);
94 return diff > 0.0
95 ? (std::ptrdiff_t)std::ceil(diff)
96 : (std::ptrdiff_t)std::floor(diff);
97 }
98};
99
100 template <class T>
101 struct CountingIteratorCompare<T, true>
102{
103 typedef std::numeric_limits<T> limit;
104
105 // use comparison with tolerance for floating-point counting
106 // (the natural epsilon is 0.5*step)
107 static bool equal(T left, T right, T step)
108 {
109 return std::fabs(right-left) <= 0.5*std::fabs(step);
110 }
111 static bool not_equal(T left, T right, T step)
112 {
113 return std::fabs(right-left) > 0.5*std::fabs(step);
114 }
115 static bool less(T left, T right, T step)
116 {
117 return step > 0.0
118 ? right - left > 0.5*step
119 : right - left < 0.5*step;
120 }
121 static bool less_equal(T left, T right, T step)
122 {
123 return step > 0.0
124 ? left - right < 0.5*step
125 : left - right > 0.5*step;
126 }
127 static bool greater(T left, T right, T step)
128 {
129 return step > 0.0
130 ? left - right > 0.5*step
131 : left - right < 0.5*step;
132 }
133 static bool greater_equal(T left, T right, T step)
134 {
135 return step > 0.0
136 ? right - left < 0.5*step
137 : right - left > 0.5*step;
138 }
139 // floating-point counting: if the raw distance is not divisible by step,
140 // we round to nearest if the difference is small, otherwise upwards
141 static std::ptrdiff_t distance(T from, T to, T step)
142 {
143 const double diff = (double(to) - double(from)) / double(step);
144 return diff > 0.0
145 ? (std::ptrdiff_t)std::ceil(diff*(1.0-2.0*limit::epsilon()))
146 : (std::ptrdiff_t)std::floor(diff*(1.0-2.0*limit::epsilon()));
147 }
148};
149
150} // namespace detail
151
152/** \addtogroup RangesAndPoints
153*/
154//@{
155
156 /** \brief Iterator that counts upwards or downwards with a given step size.
157
158 This iterator replicates the functionality of Python's
159 well-known range-function. It is especially convenient in
160 range-based for-loops. <tt>CountingIterator</tt> also works for
161 floating-point counting.
162
163 <b>Usage:</b>
164
165 <b>\#include</b> <vigra/counting_iterator.hxx><br>
166 Namespace: vigra
167
168 You will normally construct instances of this iterator with
169 one of the <tt>range()</tt> factory functions. There are three versions
170 of this function <tt>range(end)</tt>, <tt>range(begin, end)</tt>, and
171 <tt>range(begin, end, step)</tt>.
172 \code
173 // count upwards from 0 to 4
174 for(int i: range(5))
175 std::cout << i << " "; // prints '0 1 2 3 4'
176
177 // count upwards from 4 to 7
178 for(int i: range(4, 8))
179 std::cout << i << " "; // prints '4 5 6 7'
180
181 // count upwards from 0 to 9 with step 3
182 for(int i: range(0, 9, 3))
183 std::cout << i << " "; // prints '0 3 6'
184
185 // likewise (note upper bound)
186 for(int i: range(0, 7, 3))
187 std::cout << i << " "; // prints '0 3 6'
188
189 // count downwards from 4 to 1 with step -1
190 for(int i: range(4, 0))
191 std::cout << i << " "; // prints '4 3 2 1'
192
193 // count downwards from 8 to 2 with step -2
194 for(int i: range(8, 0, -2))
195 std::cout << i << " "; // prints '8 6 4 2'
196 \endcode
197
198 Alternatively, you can create a traditional random-access iterator pair.
199 The end iterator can be conveniently constructed by the begin iterator's
200 <tt>end()</tt> function:
201 \code
202 auto iter = range(5),
203 end = iter.end();
204 std::cout << std::accumulate(iter, end, 0) << std::endl; // prints '10'
205 \endcode
206
207 <tt>range()</tt> and <tt>CountingIterator</tt> also work for floating-point
208 arguments. As in the integer case, the upper bound is excluded from the range
209 if it can be reached by an integer multiple of the step (within machine
210 epsilon):
211 \code
212 for(auto i: range(1.0, 1.6, 0.1)) // 1.6 is excluded
213 std::cout << i << " "; // prints '1 1.1 1.2 1.3 1.4 1.5'
214
215 for(auto i: range(1.0, 1.61, 0.1)) // 1.6 is included
216 std::cout << i << " "; // prints '1 1.1 1.2 1.3 1.4 1.5 1.6'
217 \endcode
218
219 If you use an iterator pair, you can make clear which behavior you want
220 by using either <tt>iter < end</tt> or <tt>iter <= end</tt> to terminate
221 the loop:
222 \code
223 auto iter = range(1.0, 1.6, 0.1),
224 end = iter.end();
225 for(; iter < end; ++iter) // exclude upper bound
226 std::cout << *iter << " "; // prints '1 1.1 1.2 1.3 1.4 1.5'
227
228 iter = range(1.0, 1.6, 0.1);
229 for(; iter <= end; ++iter) // include upper bound
230 std::cout << *iter << " "; // prints '1 1.1 1.2 1.3 1.4 1.5 1.6'
231 \endcode
232
233 Note that the termination condition is still <tt>iter <= end</tt>, even
234 when the iterator counts downwards:
235 \code
236 auto iter = range(1.6, 1.0, -0.1),
237 end = iter.end();
238 for(; iter <= end; ++iter)
239 std::cout << *iter << " "; // prints '1.6 1.5 1.4 1.3 1.2 1.1 1'
240 \endcode
241 */
242 template<class T = std::ptrdiff_t>
243 class CountingIterator
244{
245 public:
246 typedef std::random_access_iterator_tag iterator_category;
247 typedef T value_type;
248 typedef std::ptrdiff_t difference_type;
249 typedef T const* pointer;
250 typedef T reference;
251
252 CountingIterator()
253 : begin_(0)
254 , end_(0)
255 , step_(1)
256 {}
257
258 CountingIterator(T begin, T end)
259 : begin_(begin)
260 , end_(end)
261 , step_(1)
262 {
263 vigra_precondition(begin <= end,
264 "CountingIterator(): begin must be less or equal to end.");
265 }
266
267 CountingIterator(T begin, T end, T step)
268 : begin_(begin)
269 , end_(end)
270 , step_(step)
271 {
272 vigra_precondition(step != 0,
273 "CountingIterator(): step must be non-zero.");
274 vigra_precondition((step > 0 && begin <= end) || (step < 0 && begin >= end),
275 "CountingIterator(): sign mismatch between step and (end-begin).");
276 }
277
278 CountingIterator(CountingIterator const & other, ReverseCopyTag)
279 : begin_(other.end_)
280 , end_(other.begin_)
281 , step_(-other.step_)
282 {}
283
284 public:
285
286 CountingIterator begin() const
287 {
288 return *this;
289 }
290
291 CountingIterator end() const
292 {
293 // since the range-based for-loop checks "iter != end",
294 // (end - begin) must be a multiple of step to avoid infinite loops
295 T end = begin_ + step_*Compare::distance(begin_, end_, step_);
296 return CountingIterator(end, end, step_);
297 }
298
299 bool empty() const
300 {
301 return Compare::greater_equal(begin_, end_, step_);
302 }
303
304 CountingIterator& operator++() {begin_ += step_; return *this;} // prefix++
305 CountingIterator operator++(int) {CountingIterator tmp(*this); ++(*this); return tmp;} // postfix++
306 CountingIterator& operator--() {begin_ -= step_; return *this;} // prefix--
307 CountingIterator operator--(int) {CountingIterator tmp(*this); --(*this); return tmp;} // postfix--
308
309 CountingIterator& operator+=(std::ptrdiff_t n)
310 {
311 begin_ += n*step_;
312 return *this;
313 }
314
315 CountingIterator operator+(std::ptrdiff_t n) const
316 {
317 return CountingIterator(*this) += n;
318 }
319
320 CountingIterator& operator-=(std::ptrdiff_t n)
321 {
322 begin_ -= n*step_;
323 return *this;
324 }
325
326 CountingIterator operator-(std::ptrdiff_t n) const
327 {
328 return CountingIterator(*this) -= n;
329 }
330
331 std::ptrdiff_t operator-(const CountingIterator& other) const
332 {
333 return Compare::distance(other.begin_, begin_, step_);
334 }
335
336 bool operator<(CountingIterator const & other) const
337 {
338 return Compare::less(begin_, other.begin_, step_);
339 }
340
341 bool operator<=(CountingIterator const & other) const
342 {
343 return Compare::less_equal(begin_, other.begin_, step_);
344 }
345
346 bool operator>(CountingIterator const & other) const
347 {
348 return Compare::greater(begin_, other.begin_, step_);
349 }
350
351 bool operator>=(CountingIterator const & other) const
352 {
353 return Compare::greater_equal(begin_, other.begin_, step_);
354 }
355
356 bool operator==(const CountingIterator& other) const
357 {
358 return Compare::equal(begin_, other.begin_, step_);
359 }
360
361 bool operator!=(const CountingIterator& other) const
362 {
363 return Compare::not_equal(begin_, other.begin_, step_);
364 }
365
366 T operator[](std::ptrdiff_t n) const {
367 return begin_ + n*step_;
368 }
369
370 T operator*() const {
371 return begin_;
372 }
373
374 T const * operator->() const{
375 return &begin_;
376 }
377
378 private:
379
380 typedef detail::CountingIteratorCompare<T, std::is_floating_point<T>::value> Compare;
381
382 T begin_, end_, step_;
383};
384
385
386 template <class T1, class T2, class T3>
387 inline CountingIterator<T1>
388range(T1 begin, T2 end, T3 step)
389{
390 return CountingIterator<T1>(begin, end, step);
391}
392
393 template <class T1, class T2>
394 inline CountingIterator<T1>
395range(T1 begin, T2 end)
396{
397 return CountingIterator<T1>(begin, end, 1);
398}
399
400 template <class T>
401 inline CountingIterator<T>
402range(T end)
403{
404 return CountingIterator<T>(0, end, 1);
405}
406
407//@}
408
409} // namespace vigra
410
411 template <typename T>
412 struct std::iterator_traits<typename vigra::CountingIterator<T>>
413{
414 typedef typename vigra::CountingIterator<T>::iterator_category iterator_category;
415 typedef typename vigra::CountingIterator<T>::value_type value_type;
416 typedef typename vigra::CountingIterator<T>::difference_type difference_type;
417 typedef typename vigra::CountingIterator<T>::pointer pointer;
418 typedef typename vigra::CountingIterator<T>::reference reference;
419};
420
421#endif
vigra::CountingIterator
Iterator that counts upwards or downwards with a given step size.
Definition counting_iterator.hxx:244
vigra::RGBValue
Class for a single RGB value.
Definition rgbvalue.hxx:128
vigra
vigra::floor
int floor(FixedPoint< IntBits, FracBits > v)
rounding down.
Definition fixedpoint.hxx:667

© 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.2