ceph/src/boost/boost/gil/step_iterator.hpp

   1 /*
   2     Copyright 2005-2007 Adobe Systems Incorporated
   3
   4     Use, modification and distribution are subject to the Boost Software License,
   5     Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt).
   7
   8     See http://opensource.adobe.com/gil for most recent version including documentation.
   9 */
  10
  11 /*************************************************************************************************/
  12
  13 #ifndef GIL_STEP_ITERATOR_H
  14 #define GIL_STEP_ITERATOR_H
  15
  16 ////////////////////////////////////////////////////////////////////////////////////////
  17 /// \file
  18 /// \brief pixel step iterator
  19 /// \author Lubomir Bourdev and Hailin Jin \n
  20 ///         Adobe Systems Incorporated
  21 /// \date   2005-2007 \n Last updated on September 18, 2007
  22 ///
  23 ////////////////////////////////////////////////////////////////////////////////////////
  24
  25 #include <cstddef>
  26 #include <iterator>
  27 #include <boost/iterator/iterator_facade.hpp>
  28 #include "gil_config.hpp"
  29 #include "utilities.hpp"
  30 #include "pixel_iterator.hpp"
  31 #include "pixel_iterator_adaptor.hpp"
  32
  33 namespace boost { namespace gil {
  34
  35 /// \defgroup PixelIteratorModelStepPtr step iterators
  36 /// \ingroup PixelIteratorModel
  37 /// \brief Iterators that allow for specifying the step between two adjacent values
  38
  39
  40 namespace detail {
  41
  42 /// \ingroup PixelIteratorModelStepPtr
  43 /// \brief An adaptor over an existing iterator that changes the step unit
  44 ///
  45 /// (i.e. distance(it,it+1)) by a given predicate. Instead of calling base's
  46 /// operators ++, --, +=, -=, etc. the adaptor is using the passed policy object SFn
  47 /// for advancing and for computing the distance between iterators.
  48
  49 template <typename Derived,  // type of the derived class
  50           typename Iterator, // Models Iterator
  51           typename SFn>      // A policy object that can compute the distance between two iterators of type Iterator
  52                              // and can advance an iterator of type Iterator a given number of Iterator's units
  53 class step_iterator_adaptor : public iterator_adaptor<Derived, Iterator, use_default, use_default, use_default, typename SFn::difference_type> {
  54 public:
  55     typedef iterator_adaptor<Derived, Iterator, use_default, use_default, use_default, typename SFn::difference_type> parent_t;
  56     typedef typename std::iterator_traits<Iterator>::difference_type base_difference_type;
  57     typedef typename SFn::difference_type                           difference_type;
  58     typedef typename std::iterator_traits<Iterator>::reference       reference;
  59
  60     step_iterator_adaptor() {}
  61     step_iterator_adaptor(const Iterator& it, SFn step_fn=SFn()) : parent_t(it), _step_fn(step_fn) {}
  62
  63     difference_type step() const { return _step_fn.step(); }
  64
  65 protected:
  66     SFn _step_fn;
  67 private:
  68     friend class boost::iterator_core_access;
  69
  70     void increment() { _step_fn.advance(this->base_reference(),1); }
  71     void decrement() { _step_fn.advance(this->base_reference(),-1); }
  72     void advance(base_difference_type d) { _step_fn.advance(this->base_reference(),d); }
  73     difference_type distance_to(const step_iterator_adaptor& it) const { return _step_fn.difference(this->base_reference(),it.base_reference()); }
  74 };
  75
  76 // although iterator_adaptor defines these, the default implementation computes distance and compares for zero.
  77 // it is often faster to just apply the relation operator to the base
  78 template <typename D,typename Iterator,typename SFn> inline
  79 bool operator>(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
  80     return p1.step()>0 ? p1.base()> p2.base() : p1.base()< p2.base();
  81 }
  82
  83 template <typename D,typename Iterator,typename SFn> inline
  84 bool operator<(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
  85     return p1.step()>0 ? p1.base()< p2.base() : p1.base()> p2.base();
  86 }
  87
  88 template <typename D,typename Iterator,typename SFn> inline
  89 bool operator>=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
  90     return p1.step()>0 ? p1.base()>=p2.base() : p1.base()<=p2.base();
  91 }
  92
  93 template <typename D,typename Iterator,typename SFn> inline
  94 bool operator<=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
  95     return p1.step()>0 ? p1.base()<=p2.base() : p1.base()>=p2.base();
  96 }
  97
  98 template <typename D,typename Iterator,typename SFn> inline
  99 bool operator==(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
 100     return p1.base()==p2.base();
 101 }
 102
 103 template <typename D,typename Iterator,typename SFn> inline
 104 bool operator!=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
 105     return p1.base()!=p2.base();
 106 }
 107
 108 } // namespace detail
 109
 110 ////////////////////////////////////////////////////////////////////////////////////////
 111 ///                 MEMORY-BASED STEP ITERATOR
 112 ////////////////////////////////////////////////////////////////////////////////////////
 113
 114 /// \class memory_based_step_iterator
 115 /// \ingroup PixelIteratorModelStepPtr PixelBasedModel
 116 /// \brief Iterator with dynamically specified step in memory units (bytes or bits). Models StepIteratorConcept, IteratorAdaptorConcept, MemoryBasedIteratorConcept, PixelIteratorConcept, HasDynamicXStepTypeConcept
 117 ///
 118 /// A refinement of step_iterator_adaptor that uses a dynamic parameter for the step
 119 /// which is specified in memory units, such as bytes or bits
 120 ///
 121 /// Pixel step iterators are used to provide iteration over non-adjacent pixels.
 122 /// Common use is a vertical traversal, where the step is the row stride.
 123 ///
 124 /// Another application is as a sub-channel view. For example, a red intensity image over
 125 /// interleaved RGB data would use a step iterator adaptor with step sizeof(channel_t)*3
 126 /// In the latter example the step size could be fixed at compile time for efficiency.
 127 /// Compile-time fixed step can be implemented by providing a step function object that takes the step as a template
 128 ////////////////////////////////////////////////////////////////////////////////////////
 129
 130 /// \ingroup PixelIteratorModelStepPtr
 131 /// \brief function object that returns the memory unit distance between two iterators and advances a given iterator a given number of mem units (bytes or bits)
 132 template <typename Iterator>
 133 struct memunit_step_fn {
 134     typedef std::ptrdiff_t difference_type;
 135
 136     memunit_step_fn(difference_type step=memunit_step(Iterator())) : _step(step) {}
 137
 138     difference_type difference(const Iterator& it1, const Iterator& it2) const { return memunit_distance(it1,it2)/_step; }
 139     void            advance(Iterator& it, difference_type d)             const { memunit_advance(it,d*_step); }
 140     difference_type step()                                               const { return _step; }
 141
 142     void            set_step(std::ptrdiff_t step) { _step=step; }
 143 private:
 144     GIL_CLASS_REQUIRE(Iterator, boost::gil, MemoryBasedIteratorConcept)
 145     difference_type _step;
 146 };
 147
 148 template <typename Iterator>
 149 class memory_based_step_iterator : public detail::step_iterator_adaptor<memory_based_step_iterator<Iterator>,
 150                                                                             Iterator,
 151                                                                             memunit_step_fn<Iterator> > {
 152     GIL_CLASS_REQUIRE(Iterator, boost::gil, MemoryBasedIteratorConcept)
 153 public:
 154     typedef detail::step_iterator_adaptor<memory_based_step_iterator<Iterator>,
 155                                           Iterator,
 156                                           memunit_step_fn<Iterator> > parent_t;
 157     typedef typename parent_t::reference                            reference;
 158     typedef typename parent_t::difference_type                      difference_type;
 159     typedef Iterator                                                x_iterator;
 160
 161     memory_based_step_iterator() : parent_t(Iterator()) {}
 162     memory_based_step_iterator(Iterator it, std::ptrdiff_t memunit_step) : parent_t(it, memunit_step_fn<Iterator>(memunit_step)) {}
 163     template <typename I2>
 164     memory_based_step_iterator(const memory_based_step_iterator<I2>& it)
 165         : parent_t(it.base(), memunit_step_fn<Iterator>(it.step())) {}
 166
 167     /// For some reason operator[] provided by iterator_adaptor returns a custom class that is convertible to reference
 168     /// We require our own reference because it is registered in iterator_traits
 169     reference operator[](difference_type d) const { return *(*this+d); }
 170
 171     void set_step(std::ptrdiff_t memunit_step) { this->_step_fn.set_step(memunit_step); }
 172
 173     x_iterator& base()              { return parent_t::base_reference(); }
 174     x_iterator const& base() const  { return parent_t::base_reference(); }
 175 };
 176
 177 template <typename Iterator>
 178 struct const_iterator_type<memory_based_step_iterator<Iterator> > {
 179     typedef memory_based_step_iterator<typename const_iterator_type<Iterator>::type>  type;
 180 };
 181
 182 template <typename Iterator>
 183 struct iterator_is_mutable<memory_based_step_iterator<Iterator> > : public iterator_is_mutable<Iterator> {};
 184
 185
 186 /////////////////////////////
 187 //  IteratorAdaptorConcept
 188 /////////////////////////////
 189
 190 template <typename Iterator>
 191 struct is_iterator_adaptor<memory_based_step_iterator<Iterator> > : public mpl::true_{};
 192
 193 template <typename Iterator>
 194 struct iterator_adaptor_get_base<memory_based_step_iterator<Iterator> > {
 195     typedef Iterator type;
 196 };
 197
 198 template <typename Iterator, typename NewBaseIterator>
 199 struct iterator_adaptor_rebind<memory_based_step_iterator<Iterator>,NewBaseIterator> {
 200     typedef memory_based_step_iterator<NewBaseIterator> type;
 201 };
 202
 203 /////////////////////////////
 204 //  PixelBasedConcept
 205 /////////////////////////////
 206
 207 template <typename Iterator>
 208 struct color_space_type<memory_based_step_iterator<Iterator> > : public color_space_type<Iterator> {};
 209
 210 template <typename Iterator>
 211 struct channel_mapping_type<memory_based_step_iterator<Iterator> > : public channel_mapping_type<Iterator> {};
 212
 213 template <typename Iterator>
 214 struct is_planar<memory_based_step_iterator<Iterator> > : public is_planar<Iterator> {};
 215
 216 template <typename Iterator>
 217 struct channel_type<memory_based_step_iterator<Iterator> > : public channel_type<Iterator> {};
 218
 219 /////////////////////////////
 220 //  MemoryBasedIteratorConcept
 221 /////////////////////////////
 222 template <typename Iterator>
 223 struct byte_to_memunit<memory_based_step_iterator<Iterator> > : public byte_to_memunit<Iterator> {};
 224
 225 template <typename Iterator>
 226 inline std::ptrdiff_t memunit_step(const memory_based_step_iterator<Iterator>& p) { return p.step(); }
 227
 228 template <typename Iterator>
 229 inline std::ptrdiff_t memunit_distance(const memory_based_step_iterator<Iterator>& p1,
 230                                     const memory_based_step_iterator<Iterator>& p2) {
 231     return memunit_distance(p1.base(),p2.base());
 232 }
 233
 234 template <typename Iterator>
 235 inline void memunit_advance(memory_based_step_iterator<Iterator>& p,
 236                          std::ptrdiff_t diff) {
 237     memunit_advance(p.base(), diff);
 238 }
 239
 240 template <typename Iterator>
 241 inline memory_based_step_iterator<Iterator>
 242 memunit_advanced(const memory_based_step_iterator<Iterator>& p,
 243               std::ptrdiff_t diff) {
 244     return memory_based_step_iterator<Iterator>(memunit_advanced(p.base(), diff),p.step());
 245 }
 246
 247 template <typename Iterator>
 248 inline typename std::iterator_traits<Iterator>::reference
 249 memunit_advanced_ref(const memory_based_step_iterator<Iterator>& p,
 250                   std::ptrdiff_t diff) {
 251     return memunit_advanced_ref(p.base(), diff);
 252 }
 253
 254 /////////////////////////////
 255 //  HasDynamicXStepTypeConcept
 256 /////////////////////////////
 257
 258 template <typename Iterator>
 259 struct dynamic_x_step_type<memory_based_step_iterator<Iterator> > {
 260     typedef memory_based_step_iterator<Iterator> type;
 261 };
 262
 263 // For step iterators, pass the function object to the base
 264 template <typename Iterator, typename Deref>
 265 struct iterator_add_deref<memory_based_step_iterator<Iterator>,Deref> {
 266     GIL_CLASS_REQUIRE(Deref, boost::gil, PixelDereferenceAdaptorConcept)
 267
 268     typedef memory_based_step_iterator<typename iterator_add_deref<Iterator, Deref>::type> type;
 269
 270     static type make(const memory_based_step_iterator<Iterator>& it, const Deref& d) { return type(iterator_add_deref<Iterator, Deref>::make(it.base(),d),it.step()); }
 271 };
 272
 273 ////////////////////////////////////////////////////////////////////////////////////////
 274 /// make_step_iterator
 275 ////////////////////////////////////////////////////////////////////////////////////////
 276
 277 template <typename I> typename dynamic_x_step_type<I>::type make_step_iterator(const I& it, std::ptrdiff_t step);
 278
 279 namespace detail {
 280
 281 // if the iterator is a plain base iterator (non-adaptor), wraps it in memory_based_step_iterator
 282 template <typename I>
 283 typename dynamic_x_step_type<I>::type make_step_iterator_impl(const I& it, std::ptrdiff_t step, mpl::false_) {
 284     return memory_based_step_iterator<I>(it, step);
 285 }
 286
 287 // If the iterator is compound, put the step in its base
 288 template <typename I>
 289 typename dynamic_x_step_type<I>::type make_step_iterator_impl(const I& it, std::ptrdiff_t step, mpl::true_) {
 290     return make_step_iterator(it.base(), step);
 291 }
 292
 293 // If the iterator is memory_based_step_iterator, change the step
 294 template <typename BaseIt>
 295 memory_based_step_iterator<BaseIt> make_step_iterator_impl(const memory_based_step_iterator<BaseIt>& it, std::ptrdiff_t step, mpl::true_) {
 296     return memory_based_step_iterator<BaseIt>(it.base(), step);
 297 }
 298 }
 299
 300 /// \brief Constructs a step iterator from a base iterator and a step.
 301 ///
 302 /// To construct a step iterator from a given iterator Iterator and a given step, if Iterator does not
 303 /// already have a dynamic step, we wrap it in a memory_based_step_iterator. Otherwise we
 304 /// do a compile-time traversal of the chain of iterator adaptors to locate the step iterator
 305 /// and then set it step to the new one.
 306 ///
 307 /// The step iterator of Iterator is not always memory_based_step_iterator<Iterator>. For example, Iterator may
 308 /// already be a memory_based_step_iterator, in which case it will be inefficient to stack them;
 309 /// we can obtain the same result by multiplying their steps. Note that for Iterator to be a
 310 /// step iterator it does not necessarily have to have the form memory_based_step_iterator<J>.
 311 /// The step iterator can be wrapped inside another iterator. Also, it may not have the
 312 /// type memory_based_step_iterator, but it could be a user-provided type.
 313 template <typename I>  // Models MemoryBasedIteratorConcept, HasDynamicXStepTypeConcept
 314 typename dynamic_x_step_type<I>::type make_step_iterator(const I& it, std::ptrdiff_t step) {
 315     return detail::make_step_iterator_impl(it, step, typename is_iterator_adaptor<I>::type());
 316 }
 317
 318 } }  // namespace boost::gil
 319
 320 #endif