GCC Code Coverage Report

Directory: ./
File: lib/geogram/basic/range.h
Date: 2026-09-07 02:28:19
Exec Total Coverage
Lines: 25 26 96.2%
Functions: 2 2 100.0%
Branches: 4 4 100.0%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2000-2022 Inria
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the ALICE Project-Team nor the names of its
14 * contributors may be used to endorse or promote products derived from this
15 * software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Contact: Bruno Levy
30 *
31 * https://www.inria.fr/fr/bruno-levy
32 *
33 * Inria,
34 * Domaine de Voluceau,
35 * 78150 Le Chesnay - Rocquencourt
36 * FRANCE
37 *
38 */
39
40 #ifndef GEOGRAM_BASIC_RANGE
41 #define GEOGRAM_BASIC_RANGE
42
43 #include <geogram/basic/numeric.h>
44 #include <geogram/basic/memory.h>
45 #include <geogram/basic/assert.h>
46 #include <geogram/basic/argused.h>
47
48 /**
49 * \file geogram/basic/range.h
50 * \brief C++-20 like helpers for manipulating ranges of integers.
51 * \note transform() not implemented yet, I need c++14 for that
52 * (auto return type).
53 */
54
55 namespace GEO {
56
57 /**
58 * \brief Wraps an integer to be used with the range-based for construct.
59 * \details Not really an iterator, rather a pseudo-index.
60 * Geogram mostly uses index-based data structures,
61 * where an element is an index in an array (whereas the
62 * STL uses pointer-like semantics). With indices, there
63 * is no indirection (an index is an element), so operator*
64 * does nothing (returns the stored index).
65 */
66 class index_as_iterator {
67 public:
68 index_as_iterator(index_t val) : val_(val) {
69 }
70
71 void operator++() {
72 128178032 ++val_;
73 116203081 }
74
75 bool operator==(index_as_iterator rhs) const {
76 return val_ == rhs.val_;
77 }
78
79 bool operator!=(index_as_iterator rhs) const {
80
4/4
✓ Branch 0 taken 845663 times.
✓ Branch 1 taken 830303 times.
✓ Branch 2 taken 2647993 times.
✓ Branch 3 taken 2647993 times.
 6971952 return val_ != rhs.val_;
81 }
82
83 bool operator<(index_as_iterator rhs) const {
84 return val_ < rhs.val_;
85 }
86
87 index_t operator*() const {
88 3493656 return val_;
89 }
90
91 index_t operator-(index_as_iterator it) const {
92 return val_ - it.val_;
93 }
94
95 index_as_iterator operator+(index_t i) const {
96 return index_as_iterator(val_ + i);
97 }
98
99 private:
100 index_t val_;
101 };
102
103 /**
104 * \brief A generic index_range bounded by two "non-iterators".
105 */
106 class index_range {
107 public:
108
109 typedef index_as_iterator iterator;
110 typedef index_as_iterator const_iterator;
111
112 /**
113 * \brief index_range constructor
114 * \param[in] b first index
115 * \param[in] e one position past the last index
116 */
117 index_range(
118 index_as_iterator b, index_as_iterator e
119 ) : begin_(b), end_(e) {
120 }
121
122 /**
123 * \brief gets the first index
124 * \return a index_as_iterator corresponding to the first index
125 */
126 index_as_iterator begin() const {
127 3334227 return begin_;
128 }
129
130 /**
131 * \brief gets one position past the last index
132 * \return a index_as_iterator corresponding to
133 * one position past the last index
134 */
135 index_as_iterator end() const {
136 2844099 return end_;
137 }
138
139 /**
140 * \brief gets the number of elements in the index_range
141 */
142 index_t nb() const {
143 return end_ - begin_;
144 }
145
146 /**
147 * \brief direct access to an arbitrary element in the index_range
148 * \param[in] i the index of the element
149 * \return an index_as_iterator corresponding to the \p i th element
150 */
151 index_t operator[](index_t i) const {
152 geo_debug_assert(i < nb());
153 return *(begin_ + i);
154 }
155
156 private:
157 index_as_iterator begin_;
158 index_as_iterator end_;
159 };
160
161 /*************************************************************************/
162
163 /**
164 * \brief Encapsulates a const pointer to an element in an index_t array
165 * \details In debug mode, checks bounds on indirection
166 */
167 class const_index_ptr_in_array {
168 public:
169 const_index_ptr_in_array(
170 const index_t* ptr, const index_t* begin, const index_t* end
171 ) : ptr_(ptr)
172 #ifdef GEO_DEBUG
173 ,begin_(begin),
174 end_(end)
175 #endif
176 {
177 geo_argused(begin);
178 geo_argused(end);
179 }
180
181 void operator++() {
182 342448 ++ptr_;
183 342448 }
184
185 bool operator==(const_index_ptr_in_array rhs) const {
186 return ptr_ == rhs.ptr_;
187 }
188
189 bool operator!=(const_index_ptr_in_array rhs) const {
190 return ptr_ != rhs.ptr_;
191 }
192
193 bool operator<(const_index_ptr_in_array rhs) const {
194 return ptr_ < rhs.ptr_;
195 }
196
197 const index_t& operator*() const {
198 geo_debug_assert(ptr_ >= begin_ && ptr_ < end_);
199 return *ptr_;
200 }
201
202 index_t operator-(const_index_ptr_in_array it) const {
203 return index_t(ptr_ - it.ptr_);
204 }
205
206 const_index_ptr_in_array operator+(index_t i) const {
207 #ifdef GEO_DEBUG
208 return const_index_ptr_in_array(ptr_ + i, begin_, end_);
209 #else
210 return const_index_ptr_in_array(ptr_ + i, nullptr, nullptr);
211 #endif
212 }
213
214 private:
215 const index_t* ptr_;
216 #ifdef GEO_DEBUG
217 const index_t* begin_;
218 const index_t* end_;
219 #endif
220 };
221
222 /*************************************************************************/
223
224 /**
225 * \brief Encapsulates a pointer to an element in an index_t array
226 * \details In debug mode, checks bounds on indirection
227 */
228 class index_ptr_in_array {
229 public:
230 index_ptr_in_array(
231 index_t* ptr, index_t* begin, index_t* end
232 ) : ptr_(ptr)
233 #ifdef GEO_DEBUG
234 ,begin_(begin),
235 end_(end)
236 #endif
237 {
238 geo_argused(begin);
239 geo_argused(end);
240 }
241
242 void operator++() {
243 81889 ++ptr_;
244 81889 }
245
246 bool operator==(index_ptr_in_array rhs) const {
247 return ptr_ == rhs.ptr_;
248 }
249
250 bool operator!=(index_ptr_in_array rhs) const {
251 return ptr_ != rhs.ptr_;
252 }
253
254 bool operator<(index_ptr_in_array rhs) const {
255 return ptr_ < rhs.ptr_;
256 }
257
258 const index_t& operator*() const {
259 geo_debug_assert(ptr_ >= begin_ && ptr_ < end_);
260 return *ptr_;
261 }
262
263 index_t& operator*() {
264 geo_debug_assert(ptr_ >= begin_ && ptr_ < end_);
265 return *ptr_;
266 }
267
268 index_t operator-(index_ptr_in_array it) const {
269 return index_t(ptr_ - it.ptr_);
270 }
271
272 index_ptr_in_array operator+(index_t i) const {
273 #ifdef GEO_DEBUG
274 return index_ptr_in_array(ptr_ + i, begin_, end_);
275 #else
276 return index_ptr_in_array(ptr_ + i, nullptr, nullptr);
277 #endif
278 }
279
280 operator const_index_ptr_in_array() const {
281 #ifdef GEO_DEBUG
282 return const_index_ptr_in_array(ptr_, begin_, end_);
283 #else
284 return const_index_ptr_in_array(ptr_, nullptr, nullptr);
285 #endif
286 }
287
288 private:
289 index_t* ptr_;
290 #ifdef GEO_DEBUG
291 index_t* begin_;
292 index_t* end_;
293 #endif
294 };
295
296 /*************************************************************************/
297
298 class index_ptr_range {
299 public:
300 typedef index_ptr_in_array iterator;
301 typedef const_index_ptr_in_array const_iterator;
302
303 index_ptr_range(index_t* begin, index_t* end) :
304 begin_(begin, begin, end),
305 end_(end,begin,end) {
306 }
307
308 index_ptr_range(vector<index_t>& V, index_t b, index_t e) :
309 21836 begin_(V.data()+b, V.data() + b, V.data() + e),
310 21836 end_(V.data()+e, V.data() + b, V.data() + e) {
311 }
312
313 iterator begin() {
314 return begin_;
315 }
316
317 iterator end() {
318 21836 return end_;
319 }
320
321 const_iterator begin() const {
322 return begin_;
323 }
324
325 const_iterator end() const {
326 return end_;
327 }
328
329 private:
330 iterator begin_;
331 iterator end_;
332 };
333
334 /*************************************************************************/
335
336 class const_index_ptr_range {
337 public:
338 typedef const_index_ptr_in_array iterator;
339 typedef const_index_ptr_in_array const_iterator;
340
341 const_index_ptr_range(const index_t* begin, const index_t* end) :
342 begin_(begin, begin, end),
343 end_(end,begin,end) {
344 }
345
346 const_index_ptr_range(const vector<index_t>& V, index_t b, index_t e) :
347 92820 begin_(V.data()+b, V.data() + b, V.data() + e),
348 92820 end_(V.data()+e, V.data() + b, V.data() + e) {
349 }
350
351 const_iterator begin() const {
352 return begin_;
353 }
354
355 const_iterator end() const {
356 92820 return end_;
357 }
358
359 private:
360 const_iterator begin_;
361 const_iterator end_;
362 };
363
364
365 /***********************************************************************/
366
367 #ifndef GOMGEN
368
369 /**
370 * \brief An iterator that applies a user-defined function when deferenced
371 * \details Used internally by transform_range()
372 * \tparam IT iterator type
373 * \tparam XFORM functor type
374 * \see transform_range()
375 */
376 template<class IT, typename XFORM> class transformed_iterator {
377 public:
378 typedef transformed_iterator<IT, XFORM> thisclass;
379
380 3478296 transformed_iterator(const IT& it, XFORM xform) :
381 3478296 wrapped_(it), xform_(xform) {
382 }
383
384 6011223 auto operator*() const {
385 6011223 return xform_(*wrapped_);
386 }
387
388 bool operator==(const thisclass& rhs) const {
389 return wrapped_ == rhs.wrapped_;
390 }
391
392 bool operator!=(const thisclass& rhs) const {
393 return wrapped_ != rhs.wrapped_;
394 }
395
396 bool operator<(const thisclass& rhs) const {
397 return wrapped_ < rhs.wrapped_;
398 }
399
400 void operator++() {
401 ++wrapped_;
402 12147642 }
403
404 private:
405 IT wrapped_;
406 XFORM xform_;
407 };
408
409 /**
410 * \brief An iterator that applies a user-defined function when deferenced
411 * \details Used internally by transform_range_ref()
412 * \tparam IT iterator type
413 * \tparam XFORM functor type
414 * \see transform_range_ref()
415 */
416 template<class IT, typename XFORM> class transformed_iterator_ref {
417 public:
418 typedef transformed_iterator_ref<IT, XFORM> thisclass;
419
420 transformed_iterator_ref(const IT& it, XFORM xform) :
421 wrapped_(it), xform_(xform) {
422 }
423
424 auto& operator*() {
425 return xform_(*wrapped_);
426 }
427
428 const auto& operator*() const {
429 return xform_(*wrapped_);
430 }
431
432 bool operator==(const thisclass& rhs) const {
433 return wrapped_ == rhs.wrapped_;
434 }
435
436 bool operator!=(const thisclass& rhs) const {
437 return wrapped_ != rhs.wrapped_;
438 }
439
440 bool operator<(const thisclass& rhs) const {
441 return wrapped_ < rhs.wrapped_;
442 }
443
444 void operator++() {
445 ++wrapped_;
446 955798 }
447
448 private:
449 IT wrapped_;
450 XFORM xform_;
451 };
452
453 /***********************************************************************/
454
455 /**
456 * \brief A range composed with a user-defined function
457 * \see transform_range()
458 * \tparam RANGE range class
459 * \tparam XFORM functor type
460 */
461 template<class RANGE, typename XFORM> class transformed_range {
462 public:
463 typedef transformed_iterator<typename RANGE::iterator, XFORM> iterator;
464
465 typedef transformed_iterator<
466 typename RANGE::const_iterator, XFORM
467 > const_iterator;
468
469 3968424 transformed_range(const RANGE& range, XFORM xform) :
470 7446720 wrapped_(range), xform_(xform) {
471 }
472
473 iterator begin() {
474 return iterator(wrapped_.begin(), xform_);
475 }
476
477 iterator end() {
478 3968424 return iterator(wrapped_.end(), xform_);
479 }
480
481 const_iterator begin() const {
482 return const_iterator(wrapped_.begin(), xform_);
483 }
484
485 const_iterator end() const {
486 return const_iterator(wrapped_.end(), xform_);
487 }
488
489 private:
490 RANGE wrapped_;
491 XFORM xform_;
492 };
493
494 /***********************************************************************/
495
496 /**
497 * \brief A range composed with a user-defined function
498 * \details This version is used when user-defined function
499 * returns a reference
500 * \see transform_range()
501 * \tparam RANGE range class
502 * \tparam XFORM functor type
503 */
504 template<class RANGE, typename XFORM> class transformed_range_ref {
505 public:
506 typedef transformed_iterator_ref<
507 typename RANGE::iterator, XFORM
508 > iterator;
509
510 typedef transformed_iterator_ref<
511 typename RANGE::const_iterator, XFORM
512 > const_iterator;
513
514 transformed_range_ref(const RANGE& range, XFORM xform) :
515 ✗ wrapped_(range), xform_(xform) {
516 }
517
518 iterator begin() {
519 return iterator(wrapped_.begin(), xform_);
520 }
521
522 iterator end() {
523 return iterator(wrapped_.end(), xform_);
524 }
525
526 const_iterator begin() const {
527 return const_iterator(wrapped_.begin(), xform_);
528 }
529
530 const_iterator end() const {
531 return const_iterator(wrapped_.end(), xform_);
532 }
533
534 private:
535 RANGE wrapped_;
536 XFORM xform_;
537 };
538
539 /***********************************************************************/
540
541 /**
542 * \brief Creates a range that applies a user-defined function to each
543 * element when accessed
544 * \param[in] range the range
545 * \param[in] xform the transform to be applied to each range element when
546 * accessed. \p xform is supposed to return a value. If \p xform returns
547 * a reference, use transform_range_ref() instead
548 * \return a new range object, with special iterators that call \p xform
549 * when deferenced
550 */
551 template <class RANGE, typename XFORM> inline auto
552 transform_range(const RANGE& range, XFORM xform) {
553 return transformed_range<RANGE,XFORM>(range, xform);
554 }
555
556 /***********************************************************************/
557
558 /**
559 * \brief Creates a range that applies a user-defined function to each
560 * element when accessed
561 * \param[in] range the range
562 * \param[in] xform the transform to be applied to each range element when
563 * accessed. \p xform is supposed to return a reference. If \p xform returns
564 * a value, use transform_range() instead
565 * \return a new range object, with special iterators that call \p xform
566 * when deferenced
567 */
568 template <class RANGE, typename XFORM> inline auto
569 transform_range_ref(const RANGE& range, XFORM xform) {
570 return transformed_range_ref<RANGE,XFORM>(range, xform);
571 }
572
573 /***********************************************************************/
574
575 #endif
576 }
577
578 #endif
579