DGtal  1.2.0
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 //-----------------------------------------------------------------------------
39 template< typename IC>
40 bool DGtal::isEmpty( const IC& itb, const IC& ite )
41 {
42  return !detail::isNotEmpty<IC>( itb, ite, typename IteratorCirculatorTraits<IC>::Type() );
43 }
44 
45 //-----------------------------------------------------------------------------
46 template< typename IC>
47 bool DGtal::isNotEmpty( const IC& itb, const IC& ite )
48 {
49  return detail::isNotEmpty<IC>( itb, ite, typename IteratorCirculatorTraits<IC>::Type() );
50 }
51 
52 //-----------------------------------------------------------------------------
53 template< typename IC >
54 bool DGtal::detail::isNotEmpty( const IC& itb, const IC& ite, IteratorType )
55 {
56  return (itb != ite);
57 }
58 
59 //-----------------------------------------------------------------------------
60 template< typename IC >
61 bool 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 //-----------------------------------------------------------------------------
73 template<typename IC>
74 void 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 //-----------------------------------------------------------------------------
84 template<typename IC>
85 void 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 //-----------------------------------------------------------------------------
101 template<typename IC>
102 void 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 //-----------------------------------------------------------------------------
112 template<typename IC>
113 typename DGtal::IteratorCirculatorTraits<IC>::Difference
114 DGtal::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 //-----------------------------------------------------------------------------
124 template<typename IC>
125 typename DGtal::IteratorCirculatorTraits<IC>::Difference
126 DGtal::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 //-----------------------------------------------------------------------------
135 template<typename I>
136 typename DGtal::IteratorCirculatorTraits<I>::Difference
137 DGtal::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 //-----------------------------------------------------------------------------
153 template<typename C>
154 typename DGtal::IteratorCirculatorTraits<C>::Difference
155 DGtal::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 //-----------------------------------------------------------------------------
178 template<typename I>
179 typename DGtal::IteratorCirculatorTraits<I>::Difference
180 DGtal::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 //-----------------------------------------------------------------------------
189 template<typename C>
190 typename DGtal::IteratorCirculatorTraits<C>::Difference
191 DGtal::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 //-----------------------------------------------------------------------------
215 template<typename IC>
216 IC 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 //-----------------------------------------------------------------------------
226 template<typename IC>
227 IC 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 //-----------------------------------------------------------------------------
236 template<typename I>
237 I 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 //-----------------------------------------------------------------------------
254 template<typename C>
255 C 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 //-----------------------------------------------------------------------------
272 template<typename I>
273 I 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 //-----------------------------------------------------------------------------
294 template<typename C>
295 C 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 //-----------------------------------------------------------------------------
322 template<typename I>
323 I 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 //-----------------------------------------------------------------------------
332 template<typename C>
333 C 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 Tue Jun 1 2021 17:05:29 for DGtal by doxygen 1.9.1