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
33namespace 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
40namespace 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
49template <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
53class step_iterator_adaptor : public iterator_adaptor<Derived, Iterator, use_default, use_default, use_default, typename SFn::difference_type> {
54public:
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
65protected:
66 SFn _step_fn;
67private:
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
78template <typename D,typename Iterator,typename SFn> inline
79bool 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
83template <typename D,typename Iterator,typename SFn> inline
84bool 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
88template <typename D,typename Iterator,typename SFn> inline
89bool 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
93template <typename D,typename Iterator,typename SFn> inline
94bool 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
98template <typename D,typename Iterator,typename SFn> inline
99bool 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
103template <typename D,typename Iterator,typename SFn> inline
104bool 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)
132template <typename Iterator>
133struct 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; }
143private:
144 GIL_CLASS_REQUIRE(Iterator, boost::gil, MemoryBasedIteratorConcept)
145 difference_type _step;
146};
147
148template <typename Iterator>
149class 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)
153public:
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
177template <typename Iterator>
178struct const_iterator_type<memory_based_step_iterator<Iterator> > {
179 typedef memory_based_step_iterator<typename const_iterator_type<Iterator>::type> type;
180};
181
182template <typename Iterator>
183struct iterator_is_mutable<memory_based_step_iterator<Iterator> > : public iterator_is_mutable<Iterator> {};
184
185
186/////////////////////////////
187// IteratorAdaptorConcept
188/////////////////////////////
189
190template <typename Iterator>
191struct is_iterator_adaptor<memory_based_step_iterator<Iterator> > : public mpl::true_{};
192
193template <typename Iterator>
194struct iterator_adaptor_get_base<memory_based_step_iterator<Iterator> > {
195 typedef Iterator type;
196};
197
198template <typename Iterator, typename NewBaseIterator>
199struct iterator_adaptor_rebind<memory_based_step_iterator<Iterator>,NewBaseIterator> {
200 typedef memory_based_step_iterator<NewBaseIterator> type;
201};
202
203/////////////////////////////
204// PixelBasedConcept
205/////////////////////////////
206
207template <typename Iterator>
208struct color_space_type<memory_based_step_iterator<Iterator> > : public color_space_type<Iterator> {};
209
210template <typename Iterator>
211struct channel_mapping_type<memory_based_step_iterator<Iterator> > : public channel_mapping_type<Iterator> {};
212
213template <typename Iterator>
214struct is_planar<memory_based_step_iterator<Iterator> > : public is_planar<Iterator> {};
215
216template <typename Iterator>
217struct channel_type<memory_based_step_iterator<Iterator> > : public channel_type<Iterator> {};
218
219/////////////////////////////
220// MemoryBasedIteratorConcept
221/////////////////////////////
222template <typename Iterator>
223struct byte_to_memunit<memory_based_step_iterator<Iterator> > : public byte_to_memunit<Iterator> {};
224
225template <typename Iterator>
226inline std::ptrdiff_t memunit_step(const memory_based_step_iterator<Iterator>& p) { return p.step(); }
227
228template <typename Iterator>
229inline 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
234template <typename Iterator>
235inline void memunit_advance(memory_based_step_iterator<Iterator>& p,
236 std::ptrdiff_t diff) {
237 memunit_advance(p.base(), diff);
238}
239
240template <typename Iterator>
241inline memory_based_step_iterator<Iterator>
242memunit_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
247template <typename Iterator>
248inline typename std::iterator_traits<Iterator>::reference
249memunit_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
258template <typename Iterator>
259struct 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
264template <typename Iterator, typename Deref>
265struct 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
277template <typename I> typename dynamic_x_step_type<I>::type make_step_iterator(const I& it, std::ptrdiff_t step);
278
279namespace detail {
280
281// if the iterator is a plain base iterator (non-adaptor), wraps it in memory_based_step_iterator
282template <typename I>
283typename 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
288template <typename I>
289typename 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
294template <typename BaseIt>
295memory_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.
313template <typename I> // Models MemoryBasedIteratorConcept, HasDynamicXStepTypeConcept
314typename 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
321

source code of boost/boost/gil/step_iterator.hpp