DGtal 1.3.0
Loading...
Searching...
No Matches
IteratorFunctions.ih
1/**
2 * This program is free software: you can redistribute it and/or modify
3 * it under the terms of the GNU Lesser General Public License as
4 * published by the Free Software Foundation, either version 3 of the
5 * License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program. If not, see <http://www.gnu.org/licenses/>.
14 *
15 **/
16
17/**
18 * @file IteratorFunctions.ih
19 * @author Tristan Roussillon (\c tristan.roussillon@liris.cnrs.fr )
20 * Laboratoire d'InfoRmatique en Image et Systèmes d'information - LIRIS (CNRS, UMR 5205), CNRS, France
21 *
22 * @date 2012/06/18
23 *
24 * Implementation of inline methods defined in IteratorFunctions.h
25 *
26 * This file is part of the DGtal library.
27 */
28
29
30//////////////////////////////////////////////////////////////////////////////
31#include <cstdlib>
32//////////////////////////////////////////////////////////////////////////////
33
34///////////////////////////////////////////////////////////////////////////////
35// IMPLEMENTATION of inline methods.
36///////////////////////////////////////////////////////////////////////////////
37
38//-----------------------------------------------------------------------------
39template< typename IC>
40bool DGtal::isEmpty( const IC& itb, const IC& ite )
41{
42 return !detail::isNotEmpty<IC>( itb, ite, typename IteratorCirculatorTraits<IC>::Type() );
43}
44
45//-----------------------------------------------------------------------------
46template< typename IC>
47bool DGtal::isNotEmpty( const IC& itb, const IC& ite )
48{
49 return detail::isNotEmpty<IC>( itb, ite, typename IteratorCirculatorTraits<IC>::Type() );
50}
51
52//-----------------------------------------------------------------------------
53template< typename IC >
54bool DGtal::detail::isNotEmpty( const IC& itb, const IC& ite, IteratorType )
55{
56 return (itb != ite);
57}
58
59//-----------------------------------------------------------------------------
60template< typename IC >
61bool DGtal::detail::isNotEmpty( const IC& c1, const IC& c2, CirculatorType )
62{
63 // Using isValid method does not work adapters of circulators
64 // (eg. reverse circulators), which does not have any isValid method
65 // That's why we choose the following method:
66 IC c; //c is necessarily not valid
67 //if c1 or c2 is equal to a not valid circulator,
68 //then the underlying range is necessarily empty
69 return ( (c1 != c) && (c2 != c) );
70}
71
72//-----------------------------------------------------------------------------
73template<typename IC>
74void DGtal::advanceIterator(IC& ic,
75 typename IteratorCirculatorTraits<IC>::Difference n)
76{
77 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<IC> ));
78
79 typedef typename IteratorCirculatorTraits<IC>::Category Category;
80 DGtal::detail::advanceIterator( ic, n, Category() );
81}
82
83//-----------------------------------------------------------------------------
84template<typename IC>
85void DGtal::detail::advanceIterator(IC& ic,
86 typename IteratorCirculatorTraits<IC>::Difference n,
87 ForwardCategory)
88{
89 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<IC> ));
90 ASSERT(n >= 0);
91
92 int counter = 0;
93 while(counter < n)
94 {
95 ++ic;
96 ++counter;
97 }
98}
99
100//-----------------------------------------------------------------------------
101template<typename IC>
102void DGtal::detail::advanceIterator(IC& ic,
103 typename IteratorCirculatorTraits<IC>::Difference n,
104 RandomAccessCategory)
105{
106 BOOST_CONCEPT_ASSERT(( boost_concepts::RandomAccessTraversalConcept<IC> ));
107 ASSERT(n >= 0);
108 ic += n;
109}
110
111//-----------------------------------------------------------------------------
112template<typename IC>
113typename DGtal::IteratorCirculatorTraits<IC>::Difference
114DGtal::rangeSize(const IC& itb, const IC& ite)
115{
116 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<IC> ));
117
118 typedef typename IteratorCirculatorTraits<IC>::Type Type;
119 typedef typename IteratorCirculatorTraits<IC>::Category Category;
120 return DGtal::detail::rangeSize( itb, ite, Type(), Category() );
121}
122
123//-----------------------------------------------------------------------------
124template<typename IC>
125typename DGtal::IteratorCirculatorTraits<IC>::Difference
126DGtal::subRangeSize(const IC& itb, const IC& ite)
127{
128 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<IC> ));
129
130 typedef typename IteratorCirculatorTraits<IC>::Category Category;
131 return DGtal::detail::rangeSize( itb, ite, IteratorType(), Category() );
132}
133
134//-----------------------------------------------------------------------------
135template<typename I>
136typename DGtal::IteratorCirculatorTraits<I>::Difference
137DGtal::detail::rangeSize(const I& itb, const I& ite, IteratorType, ForwardCategory)
138{
139 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<I> ));
140
141 //size of the range
142 I i( itb );
143 typename DGtal::IteratorCirculatorTraits<I>::Difference counter = 0;
144 while (i != ite) {
145 ++i;
146 ++counter;
147 }
148
149 return counter;
150}
151
152//-----------------------------------------------------------------------------
153template<typename C>
154typename DGtal::IteratorCirculatorTraits<C>::Difference
155DGtal::detail::rangeSize(const C& cb, const C& ce, CirculatorType, ForwardCategory)
156{
157 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<C> ));
158
159 if (isNotEmpty(cb, ce))
160 {
161 //size of the range
162 C c( cb );
163 typename DGtal::IteratorCirculatorTraits<C>::Difference counter = 0;
164 do {
165 ++c;
166 ++counter;
167 } while (c != ce);
168
169 return counter;
170 }
171 else
172 {
173 return 0;
174 }
175}
176
177//-----------------------------------------------------------------------------
178template<typename I>
179typename DGtal::IteratorCirculatorTraits<I>::Difference
180DGtal::detail::rangeSize(const I& itb, const I& ite, IteratorType, RandomAccessCategory)
181{
182 BOOST_CONCEPT_ASSERT(( boost_concepts::RandomAccessTraversalConcept<I> ));
183 ASSERT( itb <= ite );
184
185 return (ite - itb);
186}
187
188//-----------------------------------------------------------------------------
189template<typename C>
190typename DGtal::IteratorCirculatorTraits<C>::Difference
191DGtal::detail::rangeSize(const C& cb, const C& ce, CirculatorType, RandomAccessCategory)
192{
193 BOOST_CONCEPT_ASSERT(( boost_concepts::RandomAccessTraversalConcept<C> ));
194
195 if (isNotEmpty(cb, ce))
196 {
197 if (cb == ce)
198 {//whole range
199 C c(cb);
200 ++c;
201 return ( (ce - c) + 1 );
202 }
203 else
204 {//subrange
205 return (ce - cb);
206 }
207 }
208 else
209 {
210 return 0;
211 }
212}
213
214//-----------------------------------------------------------------------------
215template<typename IC>
216IC DGtal::rangeMiddle(const IC& itb, const IC& ite)
217{
218 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<IC> ));
219
220 typedef typename IteratorCirculatorTraits<IC>::Type Type;
221 typedef typename IteratorCirculatorTraits<IC>::Category Category;
222 return DGtal::detail::rangeMiddle( itb, ite, Type(), Category() );
223}
224
225//-----------------------------------------------------------------------------
226template<typename IC>
227IC DGtal::subRangeMiddle(const IC& itb, const IC& ite)
228{
229 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<IC> ));
230
231 typedef typename IteratorCirculatorTraits<IC>::Category Category;
232 return DGtal::detail::rangeMiddle( itb, ite, IteratorType(), Category() );
233}
234
235//-----------------------------------------------------------------------------
236template<typename I>
237I DGtal::detail::rangeMiddle(const I& itb, const I& ite, IteratorType, ForwardCategory)
238{
239 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<I> ));
240
241 //size of the range
242 typename DGtal::IteratorCirculatorTraits<I>::Difference s
243 = DGtal::detail::rangeSize(itb, ite, IteratorType(), ForwardCategory());
244 //middle position
245 typename DGtal::IteratorCirculatorTraits<I>::Difference m
246 = s/2;
247 //advance until the middle
248 I i = itb;
249 DGtal::detail::advanceIterator(i, m, ForwardCategory());
250 return i;
251}
252
253//-----------------------------------------------------------------------------
254template<typename C>
255C DGtal::detail::rangeMiddle(const C& cb, const C& ce, CirculatorType, ForwardCategory)
256{
257 BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<C> ));
258
259 //size of the range
260 typename DGtal::IteratorCirculatorTraits<C>::Difference s
261 = DGtal::detail::rangeSize(cb, ce, CirculatorType(), ForwardCategory());
262 //middle position
263 typename DGtal::IteratorCirculatorTraits<C>::Difference m
264 = s/2;
265 //advance until the middle
266 C c = cb;
267 DGtal::detail::advanceIterator(c, m, ForwardCategory());
268 return c;
269}
270
271//-----------------------------------------------------------------------------
272template<typename I>
273I DGtal::detail::rangeMiddle(const I& itb, const I& ite, IteratorType, BidirectionalCategory)
274{
275 BOOST_CONCEPT_ASSERT(( boost_concepts::BidirectionalTraversalConcept<I> ));
276
277 I b( itb );
278 I e( ite );
279
280 bool flag = true;
281 while (b != e) {
282 if (flag) {
283 --e;
284 flag = false;
285 } else {
286 ++b;
287 flag = true;
288 }
289 }
290 return b;
291}
292
293//-----------------------------------------------------------------------------
294template<typename C>
295C DGtal::detail::rangeMiddle(const C& cb, const C& ce, CirculatorType, BidirectionalCategory)
296{
297 BOOST_CONCEPT_ASSERT(( boost_concepts::BidirectionalTraversalConcept<C> ));
298
299 if (isNotEmpty(cb, ce))
300 {
301 C b( cb );
302 C e( ce );
303 bool flag = true;
304 do {
305 if (flag) {
306 --e;
307 flag = false;
308 } else {
309 ++b;
310 flag = true;
311 }
312 } while (b != e);
313 return b;
314 }
315 else
316 {
317 return cb;
318 }
319}
320
321//-----------------------------------------------------------------------------
322template<typename I>
323I DGtal::detail::rangeMiddle(const I& itb, const I& ite, IteratorType, RandomAccessCategory)
324{
325 BOOST_CONCEPT_ASSERT(( boost_concepts::RandomAccessTraversalConcept<I> ));
326 ASSERT( itb <= ite );
327
328 return ( itb + (ite-itb)/2 );
329}
330
331//-----------------------------------------------------------------------------
332template<typename C>
333C DGtal::detail::rangeMiddle(const C& cb, const C& ce, CirculatorType, RandomAccessCategory)
334{
335 BOOST_CONCEPT_ASSERT(( boost_concepts::RandomAccessTraversalConcept<C> ));
336
337 typename DGtal::IteratorCirculatorTraits<C>::Difference s
338 = DGtal::detail::rangeSize(cb, ce, CirculatorType(), RandomAccessCategory());
339 return ( cb + (s/2) );
340}
341
342// //
343///////////////////////////////////////////////////////////////////////////////
344
345
Generated on Sun Nov 27 2022 15:15:35 for DGtal by doxygen 1.9.5