ceph/src/boost/libs/gil/include/boost/gil/locator.hpp

   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(dx,dy)); }
 283     x_iterator x_at      (const difference_type& d)    const { return memunit_advanced(x(), offset(d.x,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(dx,dy)); }
 287     reference  operator[](const difference_type& d)    const { return memunit_advanced_ref(x(),offset(d.x,d.y)); }
 288     this_t&    operator+=(const difference_type& d)          { memunit_advance(x(),offset(d.x,d.y)); return *this; }
 289     this_t&    operator-=(const difference_type& d)          { memunit_advance(x(),offset(-d.x,-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(d.x,d.y); }
 294     cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return offset(dx,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