stlab.adobe.com Adobe Systems Incorporated
iterator.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 
7 /*************************************************************************************************/
8 
9 #ifndef ADOBE_ITERATOR_HPP
10 #define ADOBE_ITERATOR_HPP
11 
12 #include <adobe/config.hpp>
13 
14 /*
15  NOTE (sparent) : GCC 3.1 defines std::distance in <algorithm> instead of <iterator> so we go
16  ahead and include both here to work around the issue.
17 */
18 
19 #include <algorithm>
20 #include <cassert>
21 #include <iterator>
22 #include <utility>
23 
24 #include <boost/range.hpp>
25 
26 #include <boost/iterator/iterator_facade.hpp>
27 #include <boost/iterator/iterator_traits.hpp>
28 
29 #include <adobe/typeinfo.hpp>
30 #include <adobe/empty.hpp>
31 
32 #include <adobe/implementation/swap.hpp>
33 
34 namespace adobe {
35 
36 /*************************************************************************************************/
37 
38 /*
39  Just counts the number of outputs; doesn't copy anything. More efficient than a
40  back_insert_iterator into a container if all you're interested in is the size of
41  the result.
42 */
43 
44 /*************************************************************************************************/
45 
51 {
52 public:
53  typedef std::output_iterator_tag iterator_category;
56  typedef std::size_t size_type;
57 
59  count_m(0)
60  { }
61 
63  count_m(x.count_m)
64  { }
65 
66  size_type count() const
67  { return count_m; }
68 
69  template <typename T>
70  reference operator = (const T&)
71  { return *this; }
72 
73  reference operator * ()
74  { return *this; }
75 
76  bool operator == (counting_output_iterator const& rhs) const
77  { return this == &rhs; }
78 
80  { ++count_m; return *this; }
81 
82  reference operator ++ ()
83  { ++count_m; return *this; }
84 
85 private:
86  std::size_t count_m;
87 };
88 
89 /*************************************************************************************************/
90 
91 /*
92  top iterator bottom iterator
93 
94  random access random access bidirectional
95  bidirectional random access bidirectional
96  forward random access forward
97  input random access forward
98  output random access ???
99 
100  random access bidirectional bidirectional
101  bidirectional bidirectional bidirectional
102  forward bidirectional forward
103  input bidirectional forward
104  output bidirectional ???
105 
106  random access forward forward
107  bidirectional forward forward
108  forward forward forward
109  input forward forward
110  output forward ???
111 
112  random access input input
113  bidirectional input input
114  forward input input
115  input input input
116  output input ???
117 
118  random access output output
119  bidirectional output output
120  forward output output
121  input output output
122  output output ???
123 
124 
125  if (catgory(bottom) == bidirectional && catgory(top) == bidirectional) return bidirectional
126  else if (catgory(bottom) == forward) return forward
127  else return category(bottom)
128 */
129 
130 template <typename I> // I models an InputIterator where value_type(I) models Range
131 class segmented_iterator : public boost::iterator_facade<segmented_iterator<I>,
132  typename boost::range_value<typename boost::iterator_value<I>::type>::type,
133  std::bidirectional_iterator_tag,
134  typename boost::iterator_reference<typename boost::range_iterator<typename boost::iterator_value<I>::type>::type>::type,
135  typename boost::iterator_difference<typename boost::range_iterator<typename boost::iterator_value<I>::type>::type>::type>
136 {
137  public:
138  segmented_iterator() : bucket_m(), end_m(), current_m() { }
139  segmented_iterator(I first, I last): bucket_m(first), end_m(last)
140  {
141  while(bucket_m != end_m && boost::empty(*bucket_m))
142  {
143  ++bucket_m;
144  }
145  if (bucket_m != end_m) current_m = boost::begin(*bucket_m);
146  }
147 
149  bucket_m(x.bucket_m),
150  end_m(x.end_m),
151  current_m(x.current_m)
152  { }
153 
155  {
156  swap(*this, x); return *this;
157  }
158 
159  friend inline void swap(segmented_iterator& x, segmented_iterator& y)
160  {
161  swap(x.bucket_m, y.bucket_m);
162  swap(x.end_m, y.end_m);
163  swap(x.curent_m, y.curent_m);
164  }
165 
166  private:
167  typedef typename boost::iterator_reference<typename boost::range_iterator<
168  typename boost::iterator_value<I>::type>::type>::type reference_t;
169  typedef I top_iterator_t;
170  typedef typename boost::range_iterator<typename boost::iterator_value<I>::type>::type bottom_iterator_t;
171 
172  top_iterator_t bucket_m;
173  top_iterator_t end_m;
174  bottom_iterator_t current_m;
175 
176 // boost iterator_facade access functions
177 
178  friend class boost::iterator_core_access;
179 
180  reference_t dereference() const { return *current_m; }
181 
182  bool equal(const segmented_iterator& x) const
183  {
184  /*
185  If the end of the top sequences are the same and we are in the same bucket then if we are
186  at the very end or we are at the same local position then we are equal.
187  */
188 
189  return end_m == x.end_m && bucket_m == x.bucket_m
190  && (bucket_m == end_m || current_m == x.current_m);
191  }
192 
193  void increment()
194  {
195  ++current_m;
196 
197  while (current_m == boost::end(*bucket_m))
198  {
199  ++bucket_m;
200  if (bucket_m == end_m) break;
201  current_m = boost::begin(*bucket_m);
202  }
203  }
204  void decrement()
205  {
206  while (bucket_m == end_m || current_m == boost::begin(*bucket_m))
207  {
208  --bucket_m;
209  current_m = boost::end(*bucket_m);
210  }
211 
212  --current_m;
213  }
214 };
215 
216 
217 template <typename R> // R models ConvertibleToRange
218 inline boost::iterator_range<segmented_iterator<typename boost::range_iterator<R>::type> >
220 {
222 
223  return boost::make_iterator_range(iterator(boost::begin(r), boost::end(r)),
224  iterator(boost::end(r), boost::end(r)));
225 }
226 
227 
228 template <typename R> // R models ConvertibleToRange
230 {
232 
233  return iterator(boost::begin(r), boost::end(r));
234 }
235 
236 /*************************************************************************************************/
237 
238 /*
239  NOTE (sparent) : The asserts are comment only because we don't require that our function
240  object be equality comparable.
241 */
242 
243 
244 template < typename F, // F models Unary Function object
245  typename T, // T models Regular Type
246  typename R = T&, // R models Reference Type of T
247  typename I = std::size_t, // I models Unsigned Integer
248  typename D = std::ptrdiff_t // D models Signed Integer
249  >
250 // I is convertible to argument[1] of F
251 // result of F is R
252 // D is the difference type of I (must be signed)
253 
254 class index_iterator : public boost::iterator_facade<index_iterator<F, T, R, I, D>, T,
255  std::random_access_iterator_tag, R, D>
256 {
257  public:
258  index_iterator() : index_m(0) { }
259  index_iterator(F f, I i): dereference_m(f), index_m(i) { }
260 
262  dereference_m(x.dereference_m),
263  index_m(x.index_m)
264  { }
265 
267  {
268  index_iterator temp(x);
269  swap(temp, *this);
270  return *this;
271  }
272 
273  friend inline void swap(index_iterator& x, index_iterator& y)
274  {
275  swap(x.dereference_m, y.dereference_m);
276  swap(x.index_m, y.index_m);
277  }
278 
279  I base() const { return index_m; }
280 
281  private:
282  F dereference_m;
283  I index_m;
284 
285 // boost iterator_facade access functions
286 
287  friend class boost::iterator_core_access;
288 
289  R dereference() const { return dereference_m(this->index_m); }
290 
291  bool equal(const index_iterator& x) const
292  {
293  // assert(dereference_m == x.dereference_m);
294 
295  return index_m == x.index_m;
296  }
297 
298  void increment() { ++index_m; }
299  void decrement() { --index_m; }
300  void advance(D x) { index_m += x; }
301 
302  D distance_to(const index_iterator& x) const
303  {
304  // assert(dereference_m == x.dereference_m);
305 
306  /*
307  REVISIT (sparent) : There isn't a difference type for unsigned integers - because an
308  index is usually denoted by an unsigned type, but a difference is signed we should
309  have some mechanism to peform the subtraction and guarantee a valid result. We don't
310  currently have said mechanism, so we simply cast from (possibly)unsigned to signed.
311 
312  This limits the range within which we can perform this operation, but practically it
313  shouldn't be an issue.
314  */
315  return D(x.index_m) - D(index_m);
316  }
317 };
318 
321 // STEP ITERATOR ADAPTOR
330 
331 
332 template <typename DERIVED, // type of the derived class
333  typename IT, // Models Iterator
334  typename S_FN> // A policy object that can compute the distance between two iterators of type IT
335  // and can advance an iterator of type IT a given number of IT's units
336 class step_iterator_adaptor : public boost::iterator_adaptor<DERIVED, IT, boost::use_default, boost::use_default, boost::use_default, typename S_FN::difference_type> {
337 public:
338  typedef boost::iterator_adaptor<DERIVED, IT, boost::use_default, boost::use_default, boost::use_default, typename S_FN::difference_type> parent_type;
339  typedef typename std::iterator_traits<IT>::difference_type base_difference_type;
340  typedef typename S_FN::difference_type difference_type;
341  typedef typename std::iterator_traits<IT>::reference reference;
342 
344  step_iterator_adaptor(const IT& it, S_FN step_fn=S_FN()) : parent_type(it), _step_fn(step_fn) {}
345 
346  difference_type step() const { return _step_fn.step(); }
347 
348 protected:
349  S_FN _step_fn;
350 private:
351  friend class boost::iterator_core_access;
352 
353  void increment() { _step_fn.advance(this->base_reference(),1); }
354  void decrement() { _step_fn.advance(this->base_reference(),-1); }
355  void advance(base_difference_type d) { _step_fn.advance(this->base_reference(),d); }
356  difference_type distance_to(const step_iterator_adaptor& it) const { return _step_fn.difference(this->base_reference(),it.base_reference()); }
357 };
358 
359 // although boost::iterator_adaptor defines these, the default implementation computes distance and compares for zero.
360 // it is often faster to just apply the relation operator to the base
364 template <typename D,typename IT,typename S_FN> inline
366 {
367  return p1.step()>0 ? p1.base()> p2.base() : p1.base()< p2.base();
368 }
369 
370 
371 template <typename D,typename IT,typename S_FN> inline
372 bool operator<(const step_iterator_adaptor<D,IT,S_FN>& p1, const step_iterator_adaptor<D,IT,S_FN>& p2)
373 {
374  return p1.step()>0 ? p1.base()< p2.base() : p1.base()> p2.base();
375 }
376 
377 template <typename D,typename IT,typename S_FN> inline
379 {
380  return p1.step()>0 ? p1.base()>=p2.base() : p1.base()<=p2.base();
381 }
382 
383 
384 template <typename D,typename IT,typename S_FN> inline
385 bool operator<=(const step_iterator_adaptor<D,IT,S_FN>& p1, const step_iterator_adaptor<D,IT,S_FN>& p2)
386 {
387  return p1.step()>0 ? p1.base()<=p2.base() : p1.base()>=p2.base();
388 }
389 
390 
391 template <typename D,typename IT,typename S_FN> inline
393 {
394  return p1.base()==p2.base();
395 }
396 
397 
398 template <typename D,typename IT,typename S_FN> inline
400 {
401  return p1.base()!=p2.base();
402 }
403 
404 /*************************************************************************************************/
405 
410 {
411  typedef std::output_iterator_tag iterator_category;
413  typedef std::ptrdiff_t difference_type;
414  typedef value_type* pointer;
415  typedef value_type& reference;
416 
417  null_output_iterator_t& operator ++ (int) { return *this; }
419  reference operator * () { return *this; }
420 
421  template <typename T>
422  null_output_iterator_t& operator = (const T&) { return *this; }
423 };
424 
426 
427 /*************************************************************************************************/
428 
429 } // namespace adobe
430 
431 /*************************************************************************************************/
432 
433 #endif
434 
435 /*************************************************************************************************/
friend void swap(index_iterator &x, index_iterator &y)
Definition: iterator.hpp:273
segmented_iterator(const segmented_iterator &x)
Definition: iterator.hpp:148
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred)
Definition: equal.hpp:38
index_iterator & operator=(const index_iterator &x)
Definition: iterator.hpp:266
std::output_iterator_tag iterator_category
Definition: iterator.hpp:53
index_iterator(const index_iterator &x)
Definition: iterator.hpp:261
difference_type step() const
Definition: iterator.hpp:346
std::iterator_traits< IT >::difference_type base_difference_type
Definition: iterator.hpp:339
boost::iterator_adaptor< DERIVED, IT, boost::use_default, boost::use_default, boost::use_default, typename S_FN::difference_type > parent_type
Definition: iterator.hpp:338
counting_output_iterator & reference
Definition: iterator.hpp:55
step iterator adaptor
Definition: iterator.hpp:336
segmented_iterator(I first, I last)
Definition: iterator.hpp:139
bool operator!=(const forest< T > &x, const forest< T > &y)
Definition: forest.hpp:719
reference operator=(const T &)
Definition: iterator.hpp:70
An iterator over elements which are the result of applying a function to an index.
Definition: iterator.hpp:254
std::iterator_traits< IT >::reference reference
Definition: iterator.hpp:341
segmented_iterator< typename boost::range_iterator< R >::type > make_segmented_iterator(R &r)
Definition: iterator.hpp:229
index_iterator(F f, I i)
Definition: iterator.hpp:259
std::output_iterator_tag iterator_category
Definition: iterator.hpp:411
step_iterator_adaptor(const IT &it, S_FN step_fn=S_FN())
Definition: iterator.hpp:344
counting_output_iterator value_type
Definition: iterator.hpp:54
segmented_iterator & operator=(segmented_iterator x)
Definition: iterator.hpp:154
std::ptrdiff_t difference_type
Definition: iterator.hpp:413
void swap(circular_queue< T > &, circular_queue< T > &)
counting_output_iterator(const counting_output_iterator &x)
Definition: iterator.hpp:62
S_FN::difference_type difference_type
Definition: iterator.hpp:340
bool operator==(counting_output_iterator const &rhs) const
Definition: iterator.hpp:76
null_output_iterator_t value_type
Definition: iterator.hpp:412
friend void swap(segmented_iterator &x, segmented_iterator &y)
Definition: iterator.hpp:159
bool operator>(const step_iterator_adaptor< D, IT, S_FN > &p1, const step_iterator_adaptor< D, IT, S_FN > &p2)
Definition: iterator.hpp:365
boost::iterator_range< segmented_iterator< typename boost::range_iterator< R >::type > > make_segmented_range(R &r)
Definition: iterator.hpp:219
bool operator>=(const step_iterator_adaptor< D, IT, S_FN > &p1, const step_iterator_adaptor< D, IT, S_FN > &p2)
Definition: iterator.hpp:378
A stub iterator that models OutputIterator and outputs nothing.
Definition: iterator.hpp:409

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google