summaryrefslogtreecommitdiff
path: root/boost/gil/locator.hpp
blob: bae5c883d7a4e63f52fb04be43dfcd8174538930 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
/*
    Copyright 2005-2007 Adobe Systems Incorporated
   
    Use, modification and distribution are subject to the Boost Software License,
    Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt).

    See http://opensource.adobe.com/gil for most recent version including documentation.
*/

/*************************************************************************************************/

#ifndef GIL_LOCATOR_H
#define GIL_LOCATOR_H


////////////////////////////////////////////////////////////////////////////////////////
/// \file               
/// \brief pixel 2D locator
/// \author Lubomir Bourdev and Hailin Jin \n
///         Adobe Systems Incorporated
/// \date   2005-2007 \n September 20, 2006
///
////////////////////////////////////////////////////////////////////////////////////////

#include <cstddef>
#include <cassert>
#include "pixel_iterator.hpp"

////////////////////////////////////////////////////////////////////////////////////////
///                 Pixel 2D LOCATOR
////////////////////////////////////////////////////////////////////////////////////////


namespace boost { namespace gil {

//forward declarations
template <typename P> ptrdiff_t memunit_step(const P*);
template <typename P> P* memunit_advanced(const P* p, ptrdiff_t diff);
template <typename P> P& memunit_advanced_ref(P* p, ptrdiff_t diff);
template <typename Iterator, typename D> struct iterator_add_deref;
template <typename T> class point2;
namespace detail {
    // helper class specialized for each axis of pixel_2d_locator
    template <std::size_t D, typename Loc>  class locator_axis;
}
template <typename T> struct dynamic_x_step_type;
template <typename T> struct dynamic_y_step_type;

template <typename T> struct channel_type;
template <typename T> struct color_space_type;
template <typename T> struct channel_mapping_type;
template <typename T> struct is_planar;
template <typename T> struct num_channels;

// The type of a locator or a view that has X and Y swapped. By default it is the same
template <typename T> struct transposed_type {
    typedef T type;
};

/// \class pixel_2d_locator_base
/// \brief base class for models of PixelLocatorConcept
/// \ingroup PixelLocatorModel PixelBasedModel
///
/// Pixel locator is similar to a pixel iterator, but allows for 2D navigation of pixels within an image view. 
/// It has a 2D difference_type and supports random access operations like:
/// \code
///     difference_type offset2(2,3);
///     locator+=offset2;
///     locator[offset2]=my_pixel;
/// \endcode
///
/// In addition, each coordinate acts as a random-access iterator that can be modified separately:
/// "++locator.x()" or "locator.y()+=10" thereby moving the locator horizontally or vertically.
///
/// It is called a locator because it doesn't implement the complete interface of a random access iterator.
/// For example, increment and decrement operations don't make sense (no way to specify dimension).
/// Also 2D difference between two locators cannot be computed without knowledge of the X position within the image.
/// 
/// This base class provides most of the methods and typedefs needed to create a model of a locator. GIL provides two
/// locator models as subclasses of \p pixel_2d_locator_base. A memory-based locator, \p memory_based_2d_locator and a virtual
/// locator, \p virtual_2d_locator.
/// The minimum functionality a subclass must provide is this:
/// \code
/// class my_locator : public pixel_2d_locator_base<my_locator, ..., ...> {  // supply the types for x-iterator and y-iterator
///        typedef ... const_t;                      // read-only locator
///
///        template <typename Deref> struct add_deref {
///            typedef ... type;                     // locator that invokes the Deref dereference object upon pixel access
///            static type make(const my_locator& loc, const Deref& d);
///        };
///
///        my_locator();
///        my_locator(const my_locator& pl);
///
///        // constructors with dynamic step in y (and x). Only valid for locators with dynamic steps
///        my_locator(const my_locator& loc, coord_t y_step);
///        my_locator(const my_locator& loc, coord_t x_step, coord_t y_step, bool transpose);
///
///        bool              operator==(const my_locator& p) const;
///
///        // return _references_ to horizontal/vertical iterators. Advancing them moves this locator
///        x_iterator&       x();
///        y_iterator&       y();
///        x_iterator const& x() const;
///        y_iterator const& y() const;
///
///        // return the vertical distance to another locator. Some models need the horizontal distance to compute it
///        y_coord_t         y_distance_to(const my_locator& loc2, x_coord_t xDiff) const;
///
///        // return true iff incrementing an x-iterator located at the last column will position it at the first 
///        // column of the next row. Some models need the image width to determine that.
///        bool              is_1d_traversable(x_coord_t width) const;
/// };
/// \endcode
///
/// Models may choose to override some of the functions in the base class with more efficient versions.
///

template <typename Loc, typename XIterator, typename YIterator>    // The concrete subclass, the X-iterator and the Y-iterator
class pixel_2d_locator_base {
public:
    typedef XIterator           x_iterator;
    typedef YIterator           y_iterator;

    // typedefs required by ConstRandomAccessNDLocatorConcept
    static const std::size_t num_dimensions=2;
    typedef typename std::iterator_traits<x_iterator>::value_type       value_type;
    typedef typename std::iterator_traits<x_iterator>::reference        reference;    // result of dereferencing
    typedef typename std::iterator_traits<x_iterator>::difference_type  coord_t;      // 1D difference type (same for all dimensions)
    typedef point2<coord_t>                                             difference_type; // result of operator-(locator,locator)
    typedef difference_type                                             point_t;
    template <std::size_t D> struct axis {
        typedef typename detail::locator_axis<D,Loc>::coord_t           coord_t;
        typedef typename detail::locator_axis<D,Loc>::iterator          iterator;
    };

// typedefs required by ConstRandomAccess2DLocatorConcept
    typedef typename point_t::template axis<0>::coord_t                 x_coord_t;
    typedef typename point_t::template axis<1>::coord_t                 y_coord_t;

    bool              operator!=(const Loc& p)          const { return !(concrete()==p); }

    x_iterator        x_at(x_coord_t dx, y_coord_t dy)  const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp.x(); }
    x_iterator        x_at(const difference_type& d)    const { Loc tmp=concrete(); tmp+=d;              return tmp.x(); }
    y_iterator        y_at(x_coord_t dx, y_coord_t dy)  const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp.y(); }
    y_iterator        y_at(const difference_type& d)    const { Loc tmp=concrete(); tmp+=d;              return tmp.y(); }
    Loc               xy_at(x_coord_t dx, y_coord_t dy) const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp; }
    Loc               xy_at(const difference_type& d)   const { Loc tmp=concrete(); tmp+=d;              return tmp; }

    template <std::size_t D> typename axis<D>::iterator&       axis_iterator()                       { return detail::locator_axis<D,Loc>()(concrete()); }
    template <std::size_t D> typename axis<D>::iterator const& axis_iterator()                 const { return detail::locator_axis<D,Loc>()(concrete()); }
    template <std::size_t D> typename axis<D>::iterator        axis_iterator(const point_t& p) const { return detail::locator_axis<D,Loc>()(concrete(),p); }

    reference         operator()(x_coord_t dx, y_coord_t dy) const { return *x_at(dx,dy); }
    reference         operator[](const difference_type& d)   const { return *x_at(d.x,d.y); }

    reference         operator*()                            const { return *concrete().x(); }

    Loc&              operator+=(const difference_type& d)         { concrete().x()+=d.x; concrete().y()+=d.y; return concrete(); }
    Loc&              operator-=(const difference_type& d)         { concrete().x()-=d.x; concrete().y()-=d.y; return concrete(); }
    
    Loc               operator+(const difference_type& d)    const { return xy_at(d); }
    Loc               operator-(const difference_type& d)    const { return xy_at(-d); }

    // Some locators can cache 2D coordinates for faster subsequent access. By default there is no caching
    typedef difference_type    cached_location_t;    
    cached_location_t cache_location(const difference_type& d)  const { return d; }
    cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return difference_type(dx,dy); }

private:
    Loc&              concrete()       { return (Loc&)*this; }
    const Loc&        concrete() const { return (const Loc&)*this; }

    template <typename X> friend class pixel_2d_locator;
};

// helper classes for each axis of pixel_2d_locator_base
namespace detail {
    template <typename Loc> 
    class locator_axis<0,Loc> {
        typedef typename Loc::point_t                       point_t;
    public:
        typedef typename point_t::template axis<0>::coord_t coord_t;
        typedef typename Loc::x_iterator                    iterator;

        inline iterator&        operator()(      Loc& loc)                   const { return loc.x(); }
        inline iterator  const& operator()(const Loc& loc)                   const { return loc.x(); }
        inline iterator         operator()(      Loc& loc, const point_t& d) const { return loc.x_at(d); }
        inline iterator         operator()(const Loc& loc, const point_t& d) const { return loc.x_at(d); }
    };

    template <typename Loc> 
    class locator_axis<1,Loc> {
        typedef typename Loc::point_t                       point_t;
    public:
        typedef typename point_t::template axis<1>::coord_t coord_t;
        typedef typename Loc::y_iterator                    iterator;

        inline iterator&        operator()(      Loc& loc)               const { return loc.y(); }
        inline iterator const&  operator()(const Loc& loc)               const { return loc.y(); }
        inline iterator     operator()(      Loc& loc, const point_t& d) const { return loc.y_at(d); }
        inline iterator     operator()(const Loc& loc, const point_t& d) const { return loc.y_at(d); }
    };
}

template <typename Loc, typename XIt, typename YIt>
struct channel_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public channel_type<XIt> {};

template <typename Loc, typename XIt, typename YIt>
struct color_space_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public color_space_type<XIt> {};

template <typename Loc, typename XIt, typename YIt>
struct channel_mapping_type<pixel_2d_locator_base<Loc,XIt,YIt> > : public channel_mapping_type<XIt> {};

template <typename Loc, typename XIt, typename YIt>
struct is_planar<pixel_2d_locator_base<Loc,XIt,YIt> > : public is_planar<XIt> {};

/// \class memory_based_2d_locator
/// \brief Memory-based pixel locator. Models: PixelLocatorConcept,HasDynamicXStepTypeConcept,HasDynamicYStepTypeConcept,HasTransposedTypeConcept
/// \ingroup PixelLocatorModel PixelBasedModel
///
/// The class takes a step iterator as a parameter. The step iterator provides navigation along the vertical axis
/// while its base iterator provides horizontal navigation.
///
/// Each instantiation is optimal in terms of size and efficiency.
/// For example, xy locator over interleaved rgb image results in a step iterator consisting of 
/// one std::ptrdiff_t for the row size and one native pointer (8 bytes total). ++locator.x() resolves to pointer 
/// increment. At the other extreme, a 2D navigation of the even pixels of a planar CMYK image results in a step 
/// iterator consisting of one std::ptrdiff_t for the doubled row size, and one step iterator consisting of 
/// one std::ptrdiff_t for the horizontal step of two and a CMYK planar_pixel_iterator consisting of 4 pointers (24 bytes).
/// In this case ++locator.x() results in four native pointer additions.
///
/// Note also that \p memory_based_2d_locator does not require that its element type be a pixel. It could be
/// instantiated with an iterator whose \p value_type models only \p Regular. In this case the locator
/// models the weaker RandomAccess2DLocatorConcept, and does not model PixelBasedConcept.
/// Many generic algorithms don't require the elements to be pixels.
////////////////////////////////////////////////////////////////////////////////////////

template <typename StepIterator>
class memory_based_2d_locator : public pixel_2d_locator_base<memory_based_2d_locator<StepIterator>, typename iterator_adaptor_get_base<StepIterator>::type, StepIterator> {
    typedef memory_based_2d_locator<StepIterator>  this_t;
    GIL_CLASS_REQUIRE(StepIterator, boost::gil, StepIteratorConcept)
public:
    typedef pixel_2d_locator_base<memory_based_2d_locator<StepIterator>, typename iterator_adaptor_get_base<StepIterator>::type, StepIterator> parent_t;
    typedef memory_based_2d_locator<typename const_iterator_type<StepIterator>::type> const_t; // same as this type, but over const values

    typedef typename parent_t::coord_t          coord_t;
    typedef typename parent_t::x_coord_t        x_coord_t;
    typedef typename parent_t::y_coord_t        y_coord_t;
    typedef typename parent_t::x_iterator       x_iterator;
    typedef typename parent_t::y_iterator       y_iterator;
    typedef typename parent_t::difference_type  difference_type;
    typedef typename parent_t::reference        reference;

    template <typename Deref> struct add_deref {
        typedef memory_based_2d_locator<typename iterator_add_deref<StepIterator,Deref>::type> type;
        static type make(const memory_based_2d_locator<StepIterator>& loc, const Deref& nderef) { 
            return type(iterator_add_deref<StepIterator,Deref>::make(loc.y(),nderef)); 
        }
    };

    memory_based_2d_locator() {}
    memory_based_2d_locator(const StepIterator& yit) : _p(yit) {}
    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) {}
    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)
        : _p(make_step_iterator(loc.x(),(transpose ? loc.row_size() : loc.pixel_size())*x_step),
                                        (transpose ? loc.pixel_size() : loc.row_size())*y_step ) {}

    memory_based_2d_locator(x_iterator xit, std::ptrdiff_t row_bytes) : _p(xit,row_bytes) {}
    template <typename X> memory_based_2d_locator(const memory_based_2d_locator<X>& pl) : _p(pl._p) {}
    memory_based_2d_locator(const memory_based_2d_locator& pl) : _p(pl._p) {}

    bool                  operator==(const this_t& p)  const { return _p==p._p; }

    x_iterator const&     x()                          const { return _p.base(); }
    y_iterator const&     y()                          const { return _p; }
    x_iterator&           x()                                { return _p.base(); }
    y_iterator&           y()                                { return _p; }

    // These are faster versions of functions already provided in the superclass 
    x_iterator x_at      (x_coord_t dx, y_coord_t dy)  const { return memunit_advanced(x(), offset(dx,dy)); }    
    x_iterator x_at      (const difference_type& d)    const { return memunit_advanced(x(), offset(d.x,d.y)); }
    this_t     xy_at     (x_coord_t dx, y_coord_t dy)  const { return this_t(x_at( dx , dy ), row_size()); }
    this_t     xy_at     (const difference_type& d)    const { return this_t(x_at( d.x, d.y), row_size()); }
    reference  operator()(x_coord_t dx, y_coord_t dy)  const { return memunit_advanced_ref(x(),offset(dx,dy)); }
    reference  operator[](const difference_type& d)    const { return memunit_advanced_ref(x(),offset(d.x,d.y)); }
    this_t&    operator+=(const difference_type& d)          { memunit_advance(x(),offset(d.x,d.y)); return *this; }
    this_t&    operator-=(const difference_type& d)          { memunit_advance(x(),offset(-d.x,-d.y)); return *this; }

    // Memory-based locators can have 1D caching of 2D relative coordinates
    typedef std::ptrdiff_t cached_location_t; // type used to store relative location (to allow for more efficient repeated access)
    cached_location_t cache_location(const difference_type& d)  const { return offset(d.x,d.y); }
    cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return offset(dx,dy); }
    reference         operator[](const cached_location_t& loc)  const { return memunit_advanced_ref(x(),loc); }

    // Only make sense for memory-based locators
    std::ptrdiff_t         row_size()                           const { return memunit_step(y()); }    // distance in mem units (bytes or bits) between adjacent rows
    std::ptrdiff_t         pixel_size()                         const { return memunit_step(x()); }    // distance in mem units (bytes or bits) between adjacent pixels on the same row

    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?

    // Returns the vertical distance (it2.y-it1.y) between two x_iterators given the difference of their x positions
    std::ptrdiff_t y_distance_to(const this_t& p2, x_coord_t xDiff) const { 
        std::ptrdiff_t rowDiff=memunit_distance(x(),p2.x())-pixel_size()*xDiff;
        assert(( rowDiff % row_size())==0);
        return rowDiff / row_size();
    }

private:
    template <typename X> friend class memory_based_2d_locator;
    std::ptrdiff_t offset(x_coord_t x, y_coord_t y)        const { return y*row_size() + x*pixel_size(); }
    StepIterator _p;
};

/////////////////////////////
//  PixelBasedConcept
/////////////////////////////

template <typename SI>
struct color_space_type<memory_based_2d_locator<SI> > : public color_space_type<typename memory_based_2d_locator<SI>::parent_t> {
};

template <typename SI>
struct channel_mapping_type<memory_based_2d_locator<SI> > : public channel_mapping_type<typename memory_based_2d_locator<SI>::parent_t> {
};

template <typename SI>
struct is_planar<memory_based_2d_locator<SI> > : public is_planar<typename memory_based_2d_locator<SI>::parent_t> {
};

template <typename SI>
struct channel_type<memory_based_2d_locator<SI> > : public channel_type<typename memory_based_2d_locator<SI>::parent_t> {
};

/////////////////////////////
//  HasDynamicXStepTypeConcept
/////////////////////////////

// Take the base iterator of SI (which is typically a step iterator) and change it to have a step in x
template <typename SI>
struct dynamic_x_step_type<memory_based_2d_locator<SI> > {
private:
    typedef typename iterator_adaptor_get_base<SI>::type                        base_iterator_t;
    typedef typename dynamic_x_step_type<base_iterator_t>::type                 base_iterator_step_t;
    typedef typename iterator_adaptor_rebind<SI, base_iterator_step_t>::type    dynamic_step_base_t;
public:
    typedef memory_based_2d_locator<dynamic_step_base_t> type;
};

/////////////////////////////
//  HasDynamicYStepTypeConcept
/////////////////////////////

template <typename SI>
struct dynamic_y_step_type<memory_based_2d_locator<SI> > {
    typedef memory_based_2d_locator<SI> type;
};

} }  // namespace boost::gil

#endif