stlab.adobe.com Adobe Systems Incorporated

iterator.hpp

Go to the documentation of this file.
00001 /*
00002     Copyright 2005-2007 Adobe Systems Incorporated
00003     Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
00004     or a copy at http://stlab.adobe.com/licenses.html)
00005 */
00006 
00007 /*************************************************************************************************/
00008 
00009 #ifndef ADOBE_ITERATOR_HPP
00010 #define ADOBE_ITERATOR_HPP
00011 
00012 #include <adobe/config.hpp>
00013 
00014 /*
00015     NOTE (sparent) : GCC 3.1 defines std::distance in <algorithm> instead of <iterator> so we go
00016     ahead and include both here to work around the issue.
00017 */
00018 
00019 #include <algorithm>
00020 #include <cassert>
00021 #include <iterator>
00022 #include <utility>
00023 
00024 #include <boost/range.hpp>
00025 
00026 #include <boost/iterator/iterator_facade.hpp>
00027 #include <boost/iterator/iterator_traits.hpp>
00028 
00029 #include <adobe/typeinfo.hpp>
00030 #include <adobe/empty.hpp>
00031 
00032 #include <adobe/implementation/swap.hpp>
00033 
00034 namespace adobe {
00035 
00036 /*************************************************************************************************/
00037 
00038 /*
00039     Just counts the number of outputs; doesn't copy anything. More efficient than a
00040     back_insert_iterator into a container if all you're interested in is the size of
00041     the result.
00042 */
00043 
00044 /*************************************************************************************************/
00045 
00050 class counting_output_iterator
00051 {
00052 public:
00053     typedef std::output_iterator_tag        iterator_category;
00054     typedef counting_output_iterator                value_type;
00055     typedef counting_output_iterator&           reference;
00056     typedef std::size_t                     size_type;
00057 
00058     counting_output_iterator() :
00059         count_m(0)
00060         { }
00061 
00062     counting_output_iterator(const counting_output_iterator& x) :
00063         count_m(x.count_m)
00064         { }
00065 
00066     size_type count() const
00067         { return count_m; }
00068 
00069     template <typename T>
00070     reference operator = (const T&)
00071         { return *this; }
00072 
00073     reference operator * ()
00074         { return *this; }
00075 
00076     bool operator == (counting_output_iterator const& rhs) const
00077         { return this == &rhs; }
00078 
00079     counting_output_iterator operator ++ (int)
00080         { ++count_m; return *this; }
00081 
00082     reference operator ++ ()
00083         { ++count_m; return *this; }
00084 
00085 private:
00086     std::size_t     count_m;
00087 };
00088 
00089 /*************************************************************************************************/
00090 
00091 /*
00092     top iterator            bottom iterator
00093     
00094     random access           random access           bidirectional
00095     bidirectional           random access           bidirectional
00096     forward                 random access           forward
00097     input                   random access           forward
00098     output                  random access           ???
00099     
00100     random access           bidirectional           bidirectional
00101     bidirectional           bidirectional           bidirectional
00102     forward                 bidirectional           forward
00103     input                   bidirectional           forward
00104     output                  bidirectional           ???
00105     
00106     random access           forward                 forward
00107     bidirectional           forward                 forward
00108     forward                 forward                 forward
00109     input                   forward                 forward
00110     output                  forward                 ???
00111     
00112     random access           input                   input
00113     bidirectional           input                   input
00114     forward                 input                   input
00115     input                   input                   input
00116     output                  input                   ???
00117     
00118     random access           output                  output
00119     bidirectional           output                  output
00120     forward                 output                  output
00121     input                   output                  output
00122     output                  output                  ???
00123     
00124     
00125     if (catgory(bottom) == bidirectional && catgory(top) == bidirectional) return bidirectional
00126     else if (catgory(bottom) == forward) return forward
00127     else return category(bottom)
00128 */
00129 
00130 template <typename I> // I models an InputIterator where value_type(I) models Range
00131 class segmented_iterator : public boost::iterator_facade<segmented_iterator<I>,
00132     typename boost::range_value<typename boost::iterator_value<I>::type>::type,
00133     std::bidirectional_iterator_tag,
00134     typename boost::iterator_reference<typename boost::range_iterator<typename boost::iterator_value<I>::type>::type>::type,
00135     typename boost::iterator_difference<typename boost::range_iterator<typename boost::iterator_value<I>::type>::type>::type>
00136 {
00137  public:
00138     segmented_iterator() : bucket_m(), end_m(), current_m() { }
00139     segmented_iterator(I first, I last): bucket_m(first), end_m(last)
00140     {
00141         while(bucket_m != end_m && boost::empty(*bucket_m))
00142         {
00143             ++bucket_m;
00144         }
00145         if (bucket_m != end_m) current_m = boost::begin(*bucket_m);
00146     }
00147     
00148     segmented_iterator(const segmented_iterator& x) :
00149         bucket_m(x.bucket_m),
00150         end_m(x.end_m),
00151         current_m(x.current_m)
00152     { }
00153     
00154     segmented_iterator& operator=(segmented_iterator x)
00155     {
00156         swap(*this, x); return *this;
00157     }
00158     
00159     friend inline void swap(segmented_iterator& x, segmented_iterator& y)
00160     {
00161         swap(x.bucket_m, y.bucket_m);
00162         swap(x.end_m, y.end_m);
00163         swap(x.curent_m, y.curent_m);
00164     }
00165     
00166  private:
00167     typedef typename boost::iterator_reference<typename boost::range_iterator<
00168         typename boost::iterator_value<I>::type>::type>::type   reference_t;
00169     typedef I top_iterator_t;
00170     typedef typename boost::range_iterator<typename boost::iterator_value<I>::type>::type bottom_iterator_t;
00171  
00172     top_iterator_t      bucket_m;
00173     top_iterator_t      end_m;
00174     bottom_iterator_t   current_m;
00175     
00176 // boost iterator_facade access functions
00177 
00178     friend class boost::iterator_core_access;
00179                 
00180     reference_t dereference() const { return *current_m; }
00181 
00182     bool equal(const segmented_iterator& x) const
00183     {
00184         /*
00185         If the end of the top sequences are the same and we are in the same bucket then if we are
00186         at the very end or we are at the same local position then we are equal.
00187         */
00188         
00189         return end_m == x.end_m && bucket_m == x.bucket_m
00190             && (bucket_m == end_m || current_m == x.current_m);
00191     }
00192 
00193     void increment()
00194     {
00195         ++current_m;
00196         
00197         while (current_m == boost::end(*bucket_m))
00198         {
00199             ++bucket_m;
00200             if (bucket_m == end_m) break;
00201             current_m = boost::begin(*bucket_m);
00202         }
00203     }
00204     void decrement()
00205     {
00206         while (bucket_m == end_m || current_m == boost::begin(*bucket_m))
00207         {
00208             --bucket_m;
00209             current_m = boost::end(*bucket_m);
00210         }
00211         
00212         --current_m;
00213     }
00214 };
00215 
00216 
00217 template <typename R> // R models ConvertibleToRange
00218 inline boost::iterator_range<segmented_iterator<typename boost::range_iterator<R>::type> >
00219     make_segmented_range(R& r)
00220 {
00221     typedef segmented_iterator<typename boost::range_iterator<R>::type> iterator;
00222 
00223     return boost::make_iterator_range(iterator(boost::begin(r), boost::end(r)),
00224         iterator(boost::end(r), boost::end(r)));
00225 }
00226 
00227 
00228 template <typename R> // R models ConvertibleToRange
00229 inline segmented_iterator<typename boost::range_iterator<R>::type> make_segmented_iterator(R& r)
00230 {
00231     typedef segmented_iterator<typename boost::range_iterator<R>::type> iterator;
00232     
00233     return iterator(boost::begin(r), boost::end(r));
00234 }
00235 
00236 /*************************************************************************************************/
00237 
00238 /*
00239     NOTE (sparent) : The asserts are comment only because we don't require that our function
00240     object be equality comparable.
00241 */
00242 
00243 
00244 template <  typename F, // F models Unary Function object
00245             typename T, // T models Regular Type
00246             typename R = T&, // R models Reference Type of T
00247             typename I = std::size_t, // I models Unsigned Integer
00248             typename D = std::ptrdiff_t // D models Signed Integer
00249         >
00250 // I is convertible to argument[1] of F
00251 // result of F is R
00252 // D is the difference type of I (must be signed)
00253 
00254 class index_iterator : public boost::iterator_facade<index_iterator<F, T, R, I, D>, T,
00255     std::random_access_iterator_tag, R, D>
00256 {
00257  public:
00258     index_iterator() : index_m(0) { }
00259     index_iterator(F f, I i): dereference_m(f), index_m(i) { }
00260     
00261     index_iterator(const index_iterator& x) :
00262         dereference_m(x.dereference_m),
00263         index_m(x.index_m)
00264     { }
00265     
00266     index_iterator& operator=(const index_iterator& x)
00267     {
00268         index_iterator temp(x);
00269         swap(temp, *this);
00270         return *this;
00271     }
00272     
00273     friend inline void swap(index_iterator& x, index_iterator& y)
00274     {
00275         swap(x.dereference_m, y.dereference_m);
00276         swap(x.index_m, y.index_m);
00277     }
00278     
00279     I base() const { return index_m; }
00280     
00281  private:
00282     F dereference_m;
00283     I index_m;
00284     
00285 // boost iterator_facade access functions
00286 
00287     friend class boost::iterator_core_access;
00288                 
00289     R dereference() const { return dereference_m(this->index_m); }
00290 
00291     bool equal(const index_iterator& x) const
00292     {
00293         // assert(dereference_m == x.dereference_m);
00294         
00295         return index_m == x.index_m;
00296     }
00297 
00298     void increment() { ++index_m; }
00299     void decrement() { --index_m; }
00300     void advance(D x) { index_m += x; }
00301     
00302     D distance_to(const index_iterator& x) const
00303     {
00304         // assert(dereference_m == x.dereference_m);
00305         
00306         /*
00307             REVISIT (sparent) : There isn't a difference type for unsigned integers - because an
00308             index is usually denoted by an unsigned type, but a difference is signed we should
00309             have some mechanism to peform the subtraction and guarantee a valid result. We don't
00310             currently have said mechanism, so we simply cast from (possibly)unsigned to signed.
00311             
00312             This limits the range within which we can perform this operation, but practically it
00313             shouldn't be an issue.
00314         */
00315         return D(x.index_m) - D(index_m);
00316     }
00317 };
00318 
00321 //                  STEP ITERATOR ADAPTOR
00330 
00331 
00332 template <typename DERIVED, // type of the derived class
00333         typename IT,    // Models Iterator
00334         typename S_FN>  // A policy object that can compute the distance between two iterators of type IT
00335                         // and can advance an iterator of type IT a given number of IT's units  
00336 class step_iterator_adaptor : public boost::iterator_adaptor<DERIVED, IT, boost::use_default, boost::use_default, boost::use_default, typename S_FN::difference_type> {
00337 public:
00338     typedef boost::iterator_adaptor<DERIVED, IT, boost::use_default, boost::use_default, boost::use_default, typename S_FN::difference_type> parent_type;
00339     typedef typename std::iterator_traits<IT>::difference_type base_difference_type;
00340     typedef typename S_FN::difference_type                     difference_type;
00341     typedef typename std::iterator_traits<IT>::reference       reference;
00342 
00343     step_iterator_adaptor() {}
00344     step_iterator_adaptor(const IT& it, S_FN step_fn=S_FN()) : parent_type(it), _step_fn(step_fn) {}
00345 
00346     difference_type step() const { return _step_fn.step(); }
00347 
00348 protected:
00349     S_FN _step_fn;
00350 private:
00351     friend class boost::iterator_core_access;
00352 
00353     void increment() { _step_fn.advance(this->base_reference(),1); }
00354     void decrement() { _step_fn.advance(this->base_reference(),-1); }
00355     void advance(base_difference_type d) { _step_fn.advance(this->base_reference(),d); }
00356     difference_type distance_to(const step_iterator_adaptor& it) const { return _step_fn.difference(this->base_reference(),it.base_reference()); }
00357 };
00358 
00359 // although boost::iterator_adaptor defines these, the default implementation computes distance and compares for zero.
00360 // it is often faster to just apply the relation operator to the base
00364 template <typename D,typename IT,typename S_FN> inline
00365 bool operator>(const step_iterator_adaptor<D,IT,S_FN>& p1, const step_iterator_adaptor<D,IT,S_FN>& p2) 
00366 { 
00367     return p1.step()>0 ? p1.base()> p2.base() : p1.base()< p2.base(); 
00368 }
00369 
00370 
00371 template <typename D,typename IT,typename S_FN> inline
00372 bool operator<(const step_iterator_adaptor<D,IT,S_FN>& p1, const step_iterator_adaptor<D,IT,S_FN>& p2) 
00373 { 
00374     return p1.step()>0 ? p1.base()< p2.base() : p1.base()> p2.base(); 
00375 }
00376 
00377 template <typename D,typename IT,typename S_FN> inline
00378 bool operator>=(const step_iterator_adaptor<D,IT,S_FN>& p1, const step_iterator_adaptor<D,IT,S_FN>& p2) 
00379 { 
00380     return p1.step()>0 ? p1.base()>=p2.base() : p1.base()<=p2.base(); 
00381 }
00382 
00383 
00384 template <typename D,typename IT,typename S_FN> inline
00385 bool operator<=(const step_iterator_adaptor<D,IT,S_FN>& p1, const step_iterator_adaptor<D,IT,S_FN>& p2) 
00386 { 
00387     return p1.step()>0 ? p1.base()<=p2.base() : p1.base()>=p2.base(); 
00388 }
00389 
00390 
00391 template <typename D,typename IT,typename S_FN> inline
00392 bool operator==(const step_iterator_adaptor<D,IT,S_FN>& p1, const step_iterator_adaptor<D,IT,S_FN>& p2) 
00393 { 
00394     return p1.base()==p2.base(); 
00395 }
00396 
00397 
00398 template <typename D,typename IT,typename S_FN> inline
00399 bool operator!=(const step_iterator_adaptor<D,IT,S_FN>& p1, const step_iterator_adaptor<D,IT,S_FN>& p2) 
00400 { 
00401     return p1.base()!=p2.base(); 
00402 }
00403 
00404 /*************************************************************************************************/
00405 
00409 struct null_output_iterator_t
00410 {
00411     typedef std::output_iterator_tag iterator_category;
00412     typedef null_output_iterator_t   value_type;
00413     typedef std::ptrdiff_t           difference_type;
00414     typedef value_type*              pointer;
00415     typedef value_type&              reference;
00416 
00417     null_output_iterator_t& operator ++ (int) { return *this; }
00418     null_output_iterator_t& operator ++ () { return *this; }
00419     reference               operator * () { return *this; }
00420 
00421     template <typename T>
00422     null_output_iterator_t& operator = (const T&) { return *this; }
00423 };
00424 
00426 
00427 /*************************************************************************************************/
00428 
00429 } // namespace adobe
00430 
00431 /*************************************************************************************************/
00432 
00433 #endif
00434 
00435 /*************************************************************************************************/

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