]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |