boost/gil/locator.hpp

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