boost/gil/step_iterator.hpp

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