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_LOCATOR_H |
14 | #define GIL_LOCATOR_H |
15 | |
16 | |
17 | //////////////////////////////////////////////////////////////////////////////////////// |
18 | /// \file |
19 | /// \brief pixel 2D locator |
20 | /// \author Lubomir Bourdev and Hailin Jin \n |
21 | /// Adobe Systems Incorporated |
22 | /// \date 2005-2007 \n September 20, 2006 |
23 | /// |
24 | //////////////////////////////////////////////////////////////////////////////////////// |
25 | |
26 | #include <cstddef> |
27 | #include <cassert> |
28 | #include "pixel_iterator.hpp" |
29 | |
30 | //////////////////////////////////////////////////////////////////////////////////////// |
31 | /// Pixel 2D LOCATOR |
32 | //////////////////////////////////////////////////////////////////////////////////////// |
33 | |
34 | |
35 | namespace boost { namespace gil { |
36 | |
37 | //forward declarations |
38 | template <typename P> ptrdiff_t memunit_step(const P*); |
39 | template <typename P> P* memunit_advanced(const P* p, ptrdiff_t diff); |
40 | template <typename P> P& memunit_advanced_ref(P* p, ptrdiff_t diff); |
41 | template <typename Iterator, typename D> struct iterator_add_deref; |
42 | template <typename T> class point2; |
43 | namespace detail { |
44 | // helper class specialized for each axis of pixel_2d_locator |
45 | template <std::size_t D, typename Loc> class locator_axis; |
46 | } |
47 | template <typename T> struct dynamic_x_step_type; |
48 | template <typename T> struct dynamic_y_step_type; |
49 | |
50 | template <typename T> struct channel_type; |
51 | template <typename T> struct color_space_type; |
52 | template <typename T> struct channel_mapping_type; |
53 | template <typename T> struct is_planar; |
54 | template <typename T> struct num_channels; |
55 | |
56 | // The type of a locator or a view that has X and Y swapped. By default it is the same |
57 | template <typename T> struct transposed_type { |
58 | typedef T type; |
59 | }; |
60 | |
61 | /// \class pixel_2d_locator_base |
62 | /// \brief base class for models of PixelLocatorConcept |
63 | /// \ingroup PixelLocatorModel PixelBasedModel |
64 | /// |
65 | /// Pixel locator is similar to a pixel iterator, but allows for 2D navigation of pixels within an image view. |
66 | /// It has a 2D difference_type and supports random access operations like: |
67 | /// \code |
68 | /// difference_type offset2(2,3); |
69 | /// locator+=offset2; |
70 | /// locator[offset2]=my_pixel; |
71 | /// \endcode |
72 | /// |
73 | /// In addition, each coordinate acts as a random-access iterator that can be modified separately: |
74 | /// "++locator.x()" or "locator.y()+=10" thereby moving the locator horizontally or vertically. |
75 | /// |
76 | /// It is called a locator because it doesn't implement the complete interface of a random access iterator. |
77 | /// For example, increment and decrement operations don't make sense (no way to specify dimension). |
78 | /// Also 2D difference between two locators cannot be computed without knowledge of the X position within the image. |
79 | /// |
80 | /// This base class provides most of the methods and typedefs needed to create a model of a locator. GIL provides two |
81 | /// locator models as subclasses of \p pixel_2d_locator_base. A memory-based locator, \p memory_based_2d_locator and a virtual |
82 | /// locator, \p virtual_2d_locator. |
83 | /// The minimum functionality a subclass must provide is this: |
84 | /// \code |
85 | /// class my_locator : public pixel_2d_locator_base<my_locator, ..., ...> { // supply the types for x-iterator and y-iterator |
86 | /// typedef ... const_t; // read-only locator |
87 | /// |
88 | /// template <typename Deref> struct add_deref { |
89 | /// typedef ... type; // locator that invokes the Deref dereference object upon pixel access |
90 | /// static type make(const my_locator& loc, const Deref& d); |
91 | /// }; |
92 | /// |
93 | /// my_locator(); |
94 | /// my_locator(const my_locator& pl); |
95 | /// |
96 | /// // constructors with dynamic step in y (and x). Only valid for locators with dynamic steps |
97 | /// my_locator(const my_locator& loc, coord_t y_step); |
98 | /// my_locator(const my_locator& loc, coord_t x_step, coord_t y_step, bool transpose); |
99 | /// |
100 | /// bool operator==(const my_locator& p) const; |
101 | /// |
102 | /// // return _references_ to horizontal/vertical iterators. Advancing them moves this locator |
103 | /// x_iterator& x(); |
104 | /// y_iterator& y(); |
105 | /// x_iterator const& x() const; |
106 | /// y_iterator const& y() const; |
107 | /// |
108 | /// // return the vertical distance to another locator. Some models need the horizontal distance to compute it |
109 | /// y_coord_t y_distance_to(const my_locator& loc2, x_coord_t xDiff) const; |
110 | /// |
111 | /// // return true iff incrementing an x-iterator located at the last column will position it at the first |
112 | /// // column of the next row. Some models need the image width to determine that. |
113 | /// bool is_1d_traversable(x_coord_t width) const; |
114 | /// }; |
115 | /// \endcode |
116 | /// |
117 | /// Models may choose to override some of the functions in the base class with more efficient versions. |
118 | /// |
119 | |
120 | template <typename Loc, typename XIterator, typename YIterator> // The concrete subclass, the X-iterator and the Y-iterator |
121 | class pixel_2d_locator_base { |
122 | public: |
123 | typedef XIterator x_iterator; |
124 | typedef YIterator y_iterator; |
125 | |
126 | // typedefs required by ConstRandomAccessNDLocatorConcept |
127 | static const std::size_t num_dimensions=2; |
128 | typedef typename std::iterator_traits<x_iterator>::value_type value_type; |
129 | typedef typename std::iterator_traits<x_iterator>::reference reference; // result of dereferencing |
130 | typedef typename std::iterator_traits<x_iterator>::difference_type coord_t; // 1D difference type (same for all dimensions) |
131 | typedef point2<coord_t> difference_type; // result of operator-(locator,locator) |
132 | typedef difference_type point_t; |
133 | template <std::size_t D> struct axis { |
134 | typedef typename detail::locator_axis<D,Loc>::coord_t coord_t; |
135 | typedef typename detail::locator_axis<D,Loc>::iterator iterator; |
136 | }; |
137 | |
138 | // typedefs required by ConstRandomAccess2DLocatorConcept |
139 | typedef typename point_t::template axis<0>::coord_t x_coord_t; |
140 | typedef typename point_t::template axis<1>::coord_t y_coord_t; |
141 | |
142 | bool operator!=(const Loc& p) const { return !(concrete()==p); } |
143 | |
144 | x_iterator x_at(x_coord_t dx, y_coord_t dy) const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp.x(); } |
145 | x_iterator x_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp.x(); } |
146 | y_iterator y_at(x_coord_t dx, y_coord_t dy) const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp.y(); } |
147 | y_iterator y_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp.y(); } |
148 | Loc xy_at(x_coord_t dx, y_coord_t dy) const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp; } |
149 | Loc xy_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp; } |
150 | |
151 | template <std::size_t D> typename axis<D>::iterator& axis_iterator() { return detail::locator_axis<D,Loc>()(concrete()); } |
152 | template <std::size_t D> typename axis<D>::iterator const& axis_iterator() const { return detail::locator_axis<D,Loc>()(concrete()); } |
153 | template <std::size_t D> typename axis<D>::iterator axis_iterator(const point_t& p) const { return detail::locator_axis<D,Loc>()(concrete(),p); } |
154 | |
155 | reference operator()(x_coord_t dx, y_coord_t dy) const { return *x_at(dx,dy); } |
156 | reference operator[](const difference_type& d) const { return *x_at(d.x,d.y); } |
157 | |
158 | reference operator*() const { return *concrete().x(); } |
159 | |
160 | Loc& operator+=(const difference_type& d) { concrete().x()+=d.x; concrete().y()+=d.y; return concrete(); } |
161 | Loc& operator-=(const difference_type& d) { concrete().x()-=d.x; concrete().y()-=d.y; return concrete(); } |
162 | |
163 | Loc operator+(const difference_type& d) const { return xy_at(d); } |
164 | Loc operator-(const difference_type& d) const { return xy_at(-d); } |
165 | |
166 | // Some locators can cache 2D coordinates for faster subsequent access. By default there is no caching |
167 | typedef difference_type cached_location_t; |
168 | cached_location_t cache_location(const difference_type& d) const { return d; } |
169 | cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return difference_type(dx,dy); } |
170 | |
171 | private: |
172 | Loc& concrete() { return (Loc&)*this; } |
173 | const Loc& concrete() const { return (const Loc&)*this; } |
174 | |
175 | template <typename X> friend class pixel_2d_locator; |
176 | }; |
177 | |
178 | // helper classes for each axis of pixel_2d_locator_base |
179 | namespace detail { |
180 | template <typename Loc> |
181 | class locator_axis<0,Loc> { |
182 | typedef typename Loc::point_t point_t; |
183 | public: |
184 | typedef typename point_t::template axis<0>::coord_t coord_t; |
185 | typedef typename Loc::x_iterator iterator; |
186 | |
187 | inline iterator& operator()( Loc& loc) const { return loc.x(); } |
188 | inline iterator const& operator()(const Loc& loc) const { return loc.x(); } |
189 | inline iterator operator()( Loc& loc, const point_t& d) const { return loc.x_at(d); } |
190 | inline iterator operator()(const Loc& loc, const point_t& d) const { return loc.x_at(d); } |
191 | }; |
192 | |
193 | template <typename Loc> |
194 | class locator_axis<1,Loc> { |
195 | typedef typename Loc::point_t point_t; |
196 | public: |
197 | typedef typename point_t::template axis<1>::coord_t coord_t; |
198 | typedef typename Loc::y_iterator iterator; |
199 | |
200 | inline iterator& operator()( Loc& loc) const { return loc.y(); } |
201 | inline iterator const& operator()(const Loc& loc) const { return loc.y(); } |
202 | inline iterator operator()( Loc& loc, const point_t& d) const { return loc.y_at(d); } |
203 | inline iterator operator()(const Loc& loc, const point_t& d) const { return loc.y_at(d); } |
204 | }; |
205 | } |
206 | |
207 | template <typename Loc, typename XIt, typename YIt> |
208 | struct channel_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public channel_type<XIt> {}; |
209 | |
210 | template <typename Loc, typename XIt, typename YIt> |
211 | struct color_space_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public color_space_type<XIt> {}; |
212 | |
213 | template <typename Loc, typename XIt, typename YIt> |
214 | struct channel_mapping_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public channel_mapping_type<XIt> {}; |
215 | |
216 | template <typename Loc, typename XIt, typename YIt> |
217 | struct is_planar<pixel_2d_locator_base<Loc,XIt,YIt> > : public is_planar<XIt> {}; |
218 | |
219 | /// \class memory_based_2d_locator |
220 | /// \brief Memory-based pixel locator. Models: PixelLocatorConcept,HasDynamicXStepTypeConcept,HasDynamicYStepTypeConcept,HasTransposedTypeConcept |
221 | /// \ingroup PixelLocatorModel PixelBasedModel |
222 | /// |
223 | /// The class takes a step iterator as a parameter. The step iterator provides navigation along the vertical axis |
224 | /// while its base iterator provides horizontal navigation. |
225 | /// |
226 | /// Each instantiation is optimal in terms of size and efficiency. |
227 | /// For example, xy locator over interleaved rgb image results in a step iterator consisting of |
228 | /// one std::ptrdiff_t for the row size and one native pointer (8 bytes total). ++locator.x() resolves to pointer |
229 | /// increment. At the other extreme, a 2D navigation of the even pixels of a planar CMYK image results in a step |
230 | /// iterator consisting of one std::ptrdiff_t for the doubled row size, and one step iterator consisting of |
231 | /// one std::ptrdiff_t for the horizontal step of two and a CMYK planar_pixel_iterator consisting of 4 pointers (24 bytes). |
232 | /// In this case ++locator.x() results in four native pointer additions. |
233 | /// |
234 | /// Note also that \p memory_based_2d_locator does not require that its element type be a pixel. It could be |
235 | /// instantiated with an iterator whose \p value_type models only \p Regular. In this case the locator |
236 | /// models the weaker RandomAccess2DLocatorConcept, and does not model PixelBasedConcept. |
237 | /// Many generic algorithms don't require the elements to be pixels. |
238 | //////////////////////////////////////////////////////////////////////////////////////// |
239 | |
240 | template <typename StepIterator> |
241 | class memory_based_2d_locator : public pixel_2d_locator_base<memory_based_2d_locator<StepIterator>, typename iterator_adaptor_get_base<StepIterator>::type, StepIterator> { |
242 | typedef memory_based_2d_locator<StepIterator> this_t; |
243 | GIL_CLASS_REQUIRE(StepIterator, boost::gil, StepIteratorConcept) |
244 | public: |
245 | typedef pixel_2d_locator_base<memory_based_2d_locator<StepIterator>, typename iterator_adaptor_get_base<StepIterator>::type, StepIterator> parent_t; |
246 | typedef memory_based_2d_locator<typename const_iterator_type<StepIterator>::type> const_t; // same as this type, but over const values |
247 | |
248 | typedef typename parent_t::coord_t coord_t; |
249 | typedef typename parent_t::x_coord_t x_coord_t; |
250 | typedef typename parent_t::y_coord_t y_coord_t; |
251 | typedef typename parent_t::x_iterator x_iterator; |
252 | typedef typename parent_t::y_iterator y_iterator; |
253 | typedef typename parent_t::difference_type difference_type; |
254 | typedef typename parent_t::reference reference; |
255 | |
256 | template <typename Deref> struct add_deref { |
257 | typedef memory_based_2d_locator<typename iterator_add_deref<StepIterator,Deref>::type> type; |
258 | static type make(const memory_based_2d_locator<StepIterator>& loc, const Deref& nderef) { |
259 | return type(iterator_add_deref<StepIterator,Deref>::make(loc.y(),nderef)); |
260 | } |
261 | }; |
262 | |
263 | memory_based_2d_locator() {} |
264 | memory_based_2d_locator(const StepIterator& yit) : _p(yit) {} |
265 | template <typename SI> memory_based_2d_locator(const memory_based_2d_locator<SI>& loc, coord_t y_step) : _p(loc.x(), loc.row_size()*y_step) {} |
266 | template <typename SI> memory_based_2d_locator(const memory_based_2d_locator<SI>& loc, coord_t x_step, coord_t y_step, bool transpose=false) |
267 | : _p(make_step_iterator(loc.x(),(transpose ? loc.row_size() : loc.pixel_size())*x_step), |
268 | (transpose ? loc.pixel_size() : loc.row_size())*y_step ) {} |
269 | |
270 | memory_based_2d_locator(x_iterator xit, std::ptrdiff_t row_bytes) : _p(xit,row_bytes) {} |
271 | template <typename X> memory_based_2d_locator(const memory_based_2d_locator<X>& pl) : _p(pl._p) {} |
272 | memory_based_2d_locator(const memory_based_2d_locator& pl) : _p(pl._p) {} |
273 | |
274 | bool operator==(const this_t& p) const { return _p==p._p; } |
275 | |
276 | x_iterator const& x() const { return _p.base(); } |
277 | y_iterator const& y() const { return _p; } |
278 | x_iterator& x() { return _p.base(); } |
279 | y_iterator& y() { return _p; } |
280 | |
281 | // These are faster versions of functions already provided in the superclass |
282 | x_iterator x_at (x_coord_t dx, y_coord_t dy) const { return memunit_advanced(x(), offset(x: dx,y: dy)); } |
283 | x_iterator x_at (const difference_type& d) const { return memunit_advanced(x(), offset(x: d.x,y: d.y)); } |
284 | this_t xy_at (x_coord_t dx, y_coord_t dy) const { return this_t(x_at( dx , dy ), row_size()); } |
285 | this_t xy_at (const difference_type& d) const { return this_t(x_at( d.x, d.y), row_size()); } |
286 | reference operator()(x_coord_t dx, y_coord_t dy) const { return memunit_advanced_ref(x(),offset(x: dx,y: dy)); } |
287 | reference operator[](const difference_type& d) const { return memunit_advanced_ref(x(),offset(x: d.x,y: d.y)); } |
288 | this_t& operator+=(const difference_type& d) { memunit_advance(x(),offset(x: d.x,y: d.y)); return *this; } |
289 | this_t& operator-=(const difference_type& d) { memunit_advance(x(),offset(x: -d.x,y: -d.y)); return *this; } |
290 | |
291 | // Memory-based locators can have 1D caching of 2D relative coordinates |
292 | typedef std::ptrdiff_t cached_location_t; // type used to store relative location (to allow for more efficient repeated access) |
293 | cached_location_t cache_location(const difference_type& d) const { return offset(x: d.x,y: d.y); } |
294 | cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return offset(x: dx,y: dy); } |
295 | reference operator[](const cached_location_t& loc) const { return memunit_advanced_ref(x(),loc); } |
296 | |
297 | // Only make sense for memory-based locators |
298 | std::ptrdiff_t row_size() const { return memunit_step(y()); } // distance in mem units (bytes or bits) between adjacent rows |
299 | std::ptrdiff_t pixel_size() const { return memunit_step(x()); } // distance in mem units (bytes or bits) between adjacent pixels on the same row |
300 | |
301 | bool is_1d_traversable(x_coord_t width) const { return row_size()-pixel_size()*width==0; } // is there no gap at the end of each row? |
302 | |
303 | // Returns the vertical distance (it2.y-it1.y) between two x_iterators given the difference of their x positions |
304 | std::ptrdiff_t y_distance_to(const this_t& p2, x_coord_t xDiff) const { |
305 | std::ptrdiff_t rowDiff=memunit_distance(x(),p2.x())-pixel_size()*xDiff; |
306 | assert(( rowDiff % row_size())==0); |
307 | return rowDiff / row_size(); |
308 | } |
309 | |
310 | private: |
311 | template <typename X> friend class memory_based_2d_locator; |
312 | std::ptrdiff_t offset(x_coord_t x, y_coord_t y) const { return y*row_size() + x*pixel_size(); } |
313 | StepIterator _p; |
314 | }; |
315 | |
316 | ///////////////////////////// |
317 | // PixelBasedConcept |
318 | ///////////////////////////// |
319 | |
320 | template <typename SI> |
321 | struct color_space_type<memory_based_2d_locator<SI> > : public color_space_type<typename memory_based_2d_locator<SI>::parent_t> { |
322 | }; |
323 | |
324 | template <typename SI> |
325 | struct channel_mapping_type<memory_based_2d_locator<SI> > : public channel_mapping_type<typename memory_based_2d_locator<SI>::parent_t> { |
326 | }; |
327 | |
328 | template <typename SI> |
329 | struct is_planar<memory_based_2d_locator<SI> > : public is_planar<typename memory_based_2d_locator<SI>::parent_t> { |
330 | }; |
331 | |
332 | template <typename SI> |
333 | struct channel_type<memory_based_2d_locator<SI> > : public channel_type<typename memory_based_2d_locator<SI>::parent_t> { |
334 | }; |
335 | |
336 | ///////////////////////////// |
337 | // HasDynamicXStepTypeConcept |
338 | ///////////////////////////// |
339 | |
340 | // Take the base iterator of SI (which is typically a step iterator) and change it to have a step in x |
341 | template <typename SI> |
342 | struct dynamic_x_step_type<memory_based_2d_locator<SI> > { |
343 | private: |
344 | typedef typename iterator_adaptor_get_base<SI>::type base_iterator_t; |
345 | typedef typename dynamic_x_step_type<base_iterator_t>::type base_iterator_step_t; |
346 | typedef typename iterator_adaptor_rebind<SI, base_iterator_step_t>::type dynamic_step_base_t; |
347 | public: |
348 | typedef memory_based_2d_locator<dynamic_step_base_t> type; |
349 | }; |
350 | |
351 | ///////////////////////////// |
352 | // HasDynamicYStepTypeConcept |
353 | ///////////////////////////// |
354 | |
355 | template <typename SI> |
356 | struct dynamic_y_step_type<memory_based_2d_locator<SI> > { |
357 | typedef memory_based_2d_locator<SI> type; |
358 | }; |
359 | |
360 | } } // namespace boost::gil |
361 | |
362 | #endif |
363 | |