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
35namespace boost { namespace gil {
36
37//forward declarations
38template <typename P> ptrdiff_t memunit_step(const P*);
39template <typename P> P* memunit_advanced(const P* p, ptrdiff_t diff);
40template <typename P> P& memunit_advanced_ref(P* p, ptrdiff_t diff);
41template <typename Iterator, typename D> struct iterator_add_deref;
42template <typename T> class point2;
43namespace detail {
44 // helper class specialized for each axis of pixel_2d_locator
45 template <std::size_t D, typename Loc> class locator_axis;
46}
47template <typename T> struct dynamic_x_step_type;
48template <typename T> struct dynamic_y_step_type;
49
50template <typename T> struct channel_type;
51template <typename T> struct color_space_type;
52template <typename T> struct channel_mapping_type;
53template <typename T> struct is_planar;
54template <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
57template <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
120template <typename Loc, typename XIterator, typename YIterator> // The concrete subclass, the X-iterator and the Y-iterator
121class pixel_2d_locator_base {
122public:
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
171private:
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
179namespace 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
207template <typename Loc, typename XIt, typename YIt>
208struct channel_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public channel_type<XIt> {};
209
210template <typename Loc, typename XIt, typename YIt>
211struct color_space_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public color_space_type<XIt> {};
212
213template <typename Loc, typename XIt, typename YIt>
214struct channel_mapping_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public channel_mapping_type<XIt> {};
215
216template <typename Loc, typename XIt, typename YIt>
217struct 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
240template <typename StepIterator>
241class 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)
244public:
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
310private:
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
320template <typename SI>
321struct color_space_type<memory_based_2d_locator<SI> > : public color_space_type<typename memory_based_2d_locator<SI>::parent_t> {
322};
323
324template <typename SI>
325struct channel_mapping_type<memory_based_2d_locator<SI> > : public channel_mapping_type<typename memory_based_2d_locator<SI>::parent_t> {
326};
327
328template <typename SI>
329struct is_planar<memory_based_2d_locator<SI> > : public is_planar<typename memory_based_2d_locator<SI>::parent_t> {
330};
331
332template <typename SI>
333struct 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
341template <typename SI>
342struct dynamic_x_step_type<memory_based_2d_locator<SI> > {
343private:
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;
347public:
348 typedef memory_based_2d_locator<dynamic_step_base_t> type;
349};
350
351/////////////////////////////
352// HasDynamicYStepTypeConcept
353/////////////////////////////
354
355template <typename SI>
356struct 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

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