boost/gil/step_iterator.hpp

0001 //
0002 // Copyright 2005-2007 Adobe Systems Incorporated
0003 //
0004 // Distributed under the Boost Software License, Version 1.0
0005 // See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt
0007 //
0008 #ifndef BOOST_GIL_STEP_ITERATOR_HPP
0009 #define BOOST_GIL_STEP_ITERATOR_HPP
0010
0011 #include <boost/gil/dynamic_step.hpp>
0012 #include <boost/gil/pixel_iterator.hpp>
0013 #include <boost/gil/pixel_iterator_adaptor.hpp>
0014 #include <boost/gil/utilities.hpp>
0015
0016 #include <boost/iterator/iterator_facade.hpp>
0017
0018 #include <cstddef>
0019 #include <iterator>
0020 #include <type_traits>
0021
0022 namespace boost { namespace gil {
0023
0024 /// \defgroup PixelIteratorModelStepPtr step iterators
0025 /// \ingroup PixelIteratorModel
0026 /// \brief Iterators that allow for specifying the step between two adjacent values
0027
0028 namespace detail {
0029
0030 /// \ingroup PixelIteratorModelStepPtr
0031 /// \brief An adaptor over an existing iterator that changes the step unit
0032 ///
0033 /// (i.e. distance(it,it+1)) by a given predicate. Instead of calling base's
0034 /// operators ++, --, +=, -=, etc. the adaptor is using the passed policy object SFn
0035 /// for advancing and for computing the distance between iterators.
0036
0037 template <typename Derived,  // type of the derived class
0038           typename Iterator, // Models Iterator
0039           typename SFn>      // A policy object that can compute the distance between two iterators of type Iterator
0040                              // and can advance an iterator of type Iterator a given number of Iterator's units
0041 class step_iterator_adaptor : public iterator_adaptor<Derived, Iterator, use_default, use_default, use_default, typename SFn::difference_type>
0042 {
0043 public:
0044     using parent_t = iterator_adaptor<Derived, Iterator, use_default, use_default, use_default, typename SFn::difference_type>;
0045     using base_difference_type = typename std::iterator_traits<Iterator>::difference_type;
0046     using difference_type = typename SFn::difference_type;
0047     using reference = typename std::iterator_traits<Iterator>::reference;
0048
0049     step_iterator_adaptor() {}
0050     step_iterator_adaptor(Iterator const& it, SFn step_fn=SFn()) : parent_t(it), _step_fn(step_fn) {}
0051
0052     auto step() const -> difference_type { return _step_fn.step(); }
0053
0054 protected:
0055     SFn _step_fn;
0056 private:
0057     friend class boost::iterator_core_access;
0058
0059     void increment() { _step_fn.advance(this->base_reference(),1); }
0060     void decrement() { _step_fn.advance(this->base_reference(),-1); }
0061     void advance(base_difference_type d) { _step_fn.advance(this->base_reference(),d); }
0062
0063     auto distance_to(step_iterator_adaptor const& it) const -> difference_type
0064     {
0065         return _step_fn.difference(this->base_reference(),it.base_reference());
0066     }
0067 };
0068
0069 // although iterator_adaptor defines these, the default implementation computes distance and compares for zero.
0070 // it is often faster to just apply the relation operator to the base
0071 template <typename D,typename Iterator,typename SFn> inline
0072 bool operator>(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
0073     return p1.step()>0 ? p1.base()> p2.base() : p1.base()< p2.base();
0074 }
0075
0076 template <typename D,typename Iterator,typename SFn> inline
0077 bool operator<(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
0078     return p1.step()>0 ? p1.base()< p2.base() : p1.base()> p2.base();
0079 }
0080
0081 template <typename D,typename Iterator,typename SFn> inline
0082 bool operator>=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
0083     return p1.step()>0 ? p1.base()>=p2.base() : p1.base()<=p2.base();
0084 }
0085
0086 template <typename D,typename Iterator,typename SFn> inline
0087 bool operator<=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
0088     return p1.step()>0 ? p1.base()<=p2.base() : p1.base()>=p2.base();
0089 }
0090
0091 template <typename D,typename Iterator,typename SFn> inline
0092 bool operator==(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
0093     return p1.base()==p2.base();
0094 }
0095
0096 template <typename D,typename Iterator,typename SFn> inline
0097 bool operator!=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) {
0098     return p1.base()!=p2.base();
0099 }
0100
0101 } // namespace detail
0102
0103 ////////////////////////////////////////////////////////////////////////////////////////
0104 ///                 MEMORY-BASED STEP ITERATOR
0105 ////////////////////////////////////////////////////////////////////////////////////////
0106
0107 /// \class memory_based_step_iterator
0108 /// \ingroup PixelIteratorModelStepPtr PixelBasedModel
0109 /// \brief Iterator with dynamically specified step in memory units (bytes or bits). Models StepIteratorConcept, IteratorAdaptorConcept, MemoryBasedIteratorConcept, PixelIteratorConcept, HasDynamicXStepTypeConcept
0110 ///
0111 /// A refinement of step_iterator_adaptor that uses a dynamic parameter for the step
0112 /// which is specified in memory units, such as bytes or bits
0113 ///
0114 /// Pixel step iterators are used to provide iteration over non-adjacent pixels.
0115 /// Common use is a vertical traversal, where the step is the row stride.
0116 ///
0117 /// Another application is as a sub-channel view. For example, a red intensity image over
0118 /// interleaved RGB data would use a step iterator adaptor with step sizeof(channel_t)*3
0119 /// In the latter example the step size could be fixed at compile time for efficiency.
0120 /// Compile-time fixed step can be implemented by providing a step function object that takes the step as a template
0121 ////////////////////////////////////////////////////////////////////////////////////////
0122
0123 /// \ingroup PixelIteratorModelStepPtr
0124 /// \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)
0125 template <typename Iterator>
0126 struct memunit_step_fn {
0127     using difference_type = std::ptrdiff_t;
0128
0129     memunit_step_fn(difference_type step=memunit_step(Iterator())) : _step(step) {}
0130
0131     auto difference(Iterator const& it1, Iterator const& it2) const -> difference_type
0132     {
0133         return memunit_distance(it1,it2)/_step;
0134     }
0135
0136     void advance(Iterator& it, difference_type d) const { memunit_advance(it,d*_step); }
0137     auto step() const -> difference_type { return _step; }
0138
0139     void set_step(std::ptrdiff_t step) { _step=step; }
0140 private:
0141     BOOST_GIL_CLASS_REQUIRE(Iterator, boost::gil, MemoryBasedIteratorConcept)
0142     difference_type _step;
0143 };
0144
0145 template <typename Iterator>
0146 class memory_based_step_iterator : public detail::step_iterator_adaptor<memory_based_step_iterator<Iterator>,
0147                                                                             Iterator,
0148                                                                             memunit_step_fn<Iterator>>
0149 {
0150     BOOST_GIL_CLASS_REQUIRE(Iterator, boost::gil, MemoryBasedIteratorConcept)
0151 public:
0152     using parent_t = detail::step_iterator_adaptor<memory_based_step_iterator<Iterator>,
0153                                           Iterator,
0154                                           memunit_step_fn<Iterator>>;
0155     using reference = typename parent_t::reference;
0156     using difference_type = typename parent_t::difference_type;
0157     using x_iterator = Iterator;
0158
0159     memory_based_step_iterator() : parent_t(Iterator()) {}
0160     memory_based_step_iterator(Iterator it, std::ptrdiff_t memunit_step) : parent_t(it, memunit_step_fn<Iterator>(memunit_step)) {}
0161     template <typename I2>
0162     memory_based_step_iterator(const memory_based_step_iterator<I2>& it)
0163         : parent_t(it.base(), memunit_step_fn<Iterator>(it.step())) {}
0164
0165     /// For some reason operator[] provided by iterator_adaptor returns a custom class that is convertible to reference
0166     /// We require our own reference because it is registered in iterator_traits
0167     auto operator[](difference_type d) const -> reference { return *(*this+d); }
0168
0169     void set_step(std::ptrdiff_t memunit_step) { this->_step_fn.set_step(memunit_step); }
0170
0171     auto base() -> x_iterator& { return parent_t::base_reference(); }
0172     auto base() const -> x_iterator const& { return parent_t::base_reference(); }
0173 };
0174
0175 template <typename Iterator>
0176 struct const_iterator_type<memory_based_step_iterator<Iterator>> {
0177     using type = memory_based_step_iterator<typename const_iterator_type<Iterator>::type>;
0178 };
0179
0180 template <typename Iterator>
0181 struct iterator_is_mutable<memory_based_step_iterator<Iterator>> : public iterator_is_mutable<Iterator> {};
0182
0183
0184 /////////////////////////////
0185 //  IteratorAdaptorConcept
0186 /////////////////////////////
0187
0188 template <typename Iterator>
0189 struct is_iterator_adaptor<memory_based_step_iterator<Iterator>> : std::true_type {};
0190
0191 template <typename Iterator>
0192 struct iterator_adaptor_get_base<memory_based_step_iterator<Iterator>>
0193 {
0194     using type = Iterator;
0195 };
0196
0197 template <typename Iterator, typename NewBaseIterator>
0198 struct iterator_adaptor_rebind<memory_based_step_iterator<Iterator>, NewBaseIterator>
0199 {
0200     using type = memory_based_step_iterator<NewBaseIterator>;
0201 };
0202
0203 /////////////////////////////
0204 //  PixelBasedConcept
0205 /////////////////////////////
0206
0207 template <typename Iterator>
0208 struct color_space_type<memory_based_step_iterator<Iterator>> : public color_space_type<Iterator> {};
0209
0210 template <typename Iterator>
0211 struct channel_mapping_type<memory_based_step_iterator<Iterator>> : public channel_mapping_type<Iterator> {};
0212
0213 template <typename Iterator>
0214 struct is_planar<memory_based_step_iterator<Iterator>> : public is_planar<Iterator> {};
0215
0216 template <typename Iterator>
0217 struct channel_type<memory_based_step_iterator<Iterator>> : public channel_type<Iterator> {};
0218
0219 /////////////////////////////
0220 //  MemoryBasedIteratorConcept
0221 /////////////////////////////
0222 template <typename Iterator>
0223 struct byte_to_memunit<memory_based_step_iterator<Iterator>> : public byte_to_memunit<Iterator> {};
0224
0225 template <typename Iterator>
0226 inline auto memunit_step(memory_based_step_iterator<Iterator> const& p) -> std::ptrdiff_t { return p.step(); }
0227
0228 template <typename Iterator>
0229 inline auto memunit_distance(memory_based_step_iterator<Iterator> const& p1, memory_based_step_iterator<Iterator> const& p2)
0230     -> std::ptrdiff_t
0231 {
0232     return memunit_distance(p1.base(),p2.base());
0233 }
0234
0235 template <typename Iterator>
0236 inline void memunit_advance(memory_based_step_iterator<Iterator>& p,
0237                          std::ptrdiff_t diff) {
0238     memunit_advance(p.base(), diff);
0239 }
0240
0241 template <typename Iterator>
0242 inline auto memunit_advanced(const memory_based_step_iterator<Iterator>& p, std::ptrdiff_t diff)
0243     -> memory_based_step_iterator<Iterator>
0244 {
0245     return memory_based_step_iterator<Iterator>(memunit_advanced(p.base(), diff),p.step());
0246 }
0247
0248 template <typename Iterator>
0249 inline auto memunit_advanced_ref(const memory_based_step_iterator<Iterator>& p, std::ptrdiff_t diff)
0250     -> typename std::iterator_traits<Iterator>::reference
0251 {
0252     return memunit_advanced_ref(p.base(), diff);
0253 }
0254
0255 /////////////////////////////
0256 //  HasDynamicXStepTypeConcept
0257 /////////////////////////////
0258
0259 template <typename Iterator>
0260 struct dynamic_x_step_type<memory_based_step_iterator<Iterator>> {
0261     using type = memory_based_step_iterator<Iterator>;
0262 };
0263
0264 // For step iterators, pass the function object to the base
0265 template <typename Iterator, typename Deref>
0266 struct iterator_add_deref<memory_based_step_iterator<Iterator>,Deref> {
0267     BOOST_GIL_CLASS_REQUIRE(Deref, boost::gil, PixelDereferenceAdaptorConcept)
0268
0269     using type = memory_based_step_iterator<typename iterator_add_deref<Iterator, Deref>::type>;
0270
0271     static type make(const memory_based_step_iterator<Iterator>& it, const Deref& d)
0272     {
0273         return type(iterator_add_deref<Iterator, Deref>::make(it.base(),d),it.step());
0274     }
0275 };
0276
0277 ////////////////////////////////////////////////////////////////////////////////////////
0278 /// make_step_iterator
0279 ////////////////////////////////////////////////////////////////////////////////////////
0280
0281 template <typename I> typename dynamic_x_step_type<I>::type make_step_iterator(const I& it, std::ptrdiff_t step);
0282
0283 namespace detail {
0284
0285 // if the iterator is a plain base iterator (non-adaptor), wraps it in memory_based_step_iterator
0286 template <typename I>
0287 auto make_step_iterator_impl(I const& it, std::ptrdiff_t step, std::false_type)
0288     -> typename dynamic_x_step_type<I>::type
0289 {
0290     return memory_based_step_iterator<I>(it, step);
0291 }
0292
0293 // If the iterator is compound, put the step in its base
0294 template <typename I>
0295 auto make_step_iterator_impl(I const& it, std::ptrdiff_t step, std::true_type)
0296     -> typename dynamic_x_step_type<I>::type
0297 {
0298     return make_step_iterator(it.base(), step);
0299 }
0300
0301 // If the iterator is memory_based_step_iterator, change the step
0302 template <typename BaseIt>
0303 auto make_step_iterator_impl(
0304     memory_based_step_iterator<BaseIt> const& it,
0305     std::ptrdiff_t step,
0306     std::true_type)
0307     -> memory_based_step_iterator<BaseIt>
0308 {
0309     return memory_based_step_iterator<BaseIt>(it.base(), step);
0310 }
0311
0312 } // namespace detail
0313
0314 /// \brief Constructs a step iterator from a base iterator and a step.
0315 ///
0316 /// To construct a step iterator from a given iterator Iterator and a given step, if Iterator does not
0317 /// already have a dynamic step, we wrap it in a memory_based_step_iterator. Otherwise we
0318 /// do a compile-time traversal of the chain of iterator adaptors to locate the step iterator
0319 /// and then set it step to the new one.
0320 ///
0321 /// The step iterator of Iterator is not always memory_based_step_iterator<Iterator>. For example, Iterator may
0322 /// already be a memory_based_step_iterator, in which case it will be inefficient to stack them;
0323 /// we can obtain the same result by multiplying their steps. Note that for Iterator to be a
0324 /// step iterator it does not necessarily have to have the form memory_based_step_iterator<J>.
0325 /// The step iterator can be wrapped inside another iterator. Also, it may not have the
0326 /// type memory_based_step_iterator, but it could be a user-provided type.
0327 template <typename I>  // Models MemoryBasedIteratorConcept, HasDynamicXStepTypeConcept
0328 inline auto make_step_iterator(I const& it, std::ptrdiff_t step)
0329     -> typename dynamic_x_step_type<I>::type
0330 {
0331     return detail::make_step_iterator_impl(it, step, typename is_iterator_adaptor<I>::type());
0332 }
0333
0334 }}  // namespace boost::gil
0335
0336 #endif