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 |
321 | |