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 operator !=(const Loc & p) const142 bool operator!=(const Loc& p) const { return !(concrete()==p); } 143 x_at(x_coord_t dx,y_coord_t dy) const144 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_at(const difference_type & d) const145 x_iterator x_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp.x(); } y_at(x_coord_t dx,y_coord_t dy) const146 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_at(const difference_type & d) const147 y_iterator y_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp.y(); } xy_at(x_coord_t dx,y_coord_t dy) const148 Loc xy_at(x_coord_t dx, y_coord_t dy) const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp; } xy_at(const difference_type & d) const149 Loc xy_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp; } 150 axis_iterator()151 template <std::size_t D> typename axis<D>::iterator& axis_iterator() { return detail::locator_axis<D,Loc>()(concrete()); } axis_iterator() const152 template <std::size_t D> typename axis<D>::iterator const& axis_iterator() const { return detail::locator_axis<D,Loc>()(concrete()); } axis_iterator(const point_t & p) const153 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 operator ()(x_coord_t dx,y_coord_t dy) const155 reference operator()(x_coord_t dx, y_coord_t dy) const { return *x_at(dx,dy); } operator [](const difference_type & d) const156 reference operator[](const difference_type& d) const { return *x_at(d.x,d.y); } 157 operator *() const158 reference operator*() const { return *concrete().x(); } 159 operator +=(const difference_type & d)160 Loc& operator+=(const difference_type& d) { concrete().x()+=d.x; concrete().y()+=d.y; return concrete(); } operator -=(const difference_type & d)161 Loc& operator-=(const difference_type& d) { concrete().x()-=d.x; concrete().y()-=d.y; return concrete(); } 162 operator +(const difference_type & d) const163 Loc operator+(const difference_type& d) const { return xy_at(d); } operator -(const difference_type & d) const164 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; cache_location(const difference_type & d) const168 cached_location_t cache_location(const difference_type& d) const { return d; } cache_location(x_coord_t dx,y_coord_t dy) const169 cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return difference_type(dx,dy); } 170 171 private: concrete()172 Loc& concrete() { return (Loc&)*this; } concrete() const173 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 operator ()(Loc & loc) const187 inline iterator& operator()( Loc& loc) const { return loc.x(); } operator ()(const Loc & loc) const188 inline iterator const& operator()(const Loc& loc) const { return loc.x(); } operator ()(Loc & loc,const point_t & d) const189 inline iterator operator()( Loc& loc, const point_t& d) const { return loc.x_at(d); } operator ()(const Loc & loc,const point_t & d) const190 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 operator ()(Loc & loc) const200 inline iterator& operator()( Loc& loc) const { return loc.y(); } operator ()(const Loc & loc) const201 inline iterator const& operator()(const Loc& loc) const { return loc.y(); } operator ()(Loc & loc,const point_t & d) const202 inline iterator operator()( Loc& loc, const point_t& d) const { return loc.y_at(d); } operator ()(const Loc & loc,const point_t & d) const203 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; makeboost::gil::memory_based_2d_locator::add_deref258 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 memory_based_2d_locator()263 memory_based_2d_locator() {} memory_based_2d_locator(const StepIterator & yit)264 memory_based_2d_locator(const StepIterator& yit) : _p(yit) {} memory_based_2d_locator(const memory_based_2d_locator<SI> & loc,coord_t y_step)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) {} memory_based_2d_locator(const memory_based_2d_locator<SI> & loc,coord_t x_step,coord_t y_step,bool transpose=false)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 memory_based_2d_locator(x_iterator xit,std::ptrdiff_t row_bytes)270 memory_based_2d_locator(x_iterator xit, std::ptrdiff_t row_bytes) : _p(xit,row_bytes) {} memory_based_2d_locator(const memory_based_2d_locator<X> & pl)271 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)272 memory_based_2d_locator(const memory_based_2d_locator& pl) : _p(pl._p) {} 273 operator ==(const this_t & p) const274 bool operator==(const this_t& p) const { return _p==p._p; } 275 x() const276 x_iterator const& x() const { return _p.base(); } y() const277 y_iterator const& y() const { return _p; } x()278 x_iterator& x() { return _p.base(); } y()279 y_iterator& y() { return _p; } 280 281 // These are faster versions of functions already provided in the superclass x_at(x_coord_t dx,y_coord_t dy) const282 x_iterator x_at (x_coord_t dx, y_coord_t dy) const { return memunit_advanced(x(), offset(dx,dy)); } x_at(const difference_type & d) const283 x_iterator x_at (const difference_type& d) const { return memunit_advanced(x(), offset(d.x,d.y)); } xy_at(x_coord_t dx,y_coord_t dy) const284 this_t xy_at (x_coord_t dx, y_coord_t dy) const { return this_t(x_at( dx , dy ), row_size()); } xy_at(const difference_type & d) const285 this_t xy_at (const difference_type& d) const { return this_t(x_at( d.x, d.y), row_size()); } operator ()(x_coord_t dx,y_coord_t dy) const286 reference operator()(x_coord_t dx, y_coord_t dy) const { return memunit_advanced_ref(x(),offset(dx,dy)); } operator [](const difference_type & d) const287 reference operator[](const difference_type& d) const { return memunit_advanced_ref(x(),offset(d.x,d.y)); } operator +=(const difference_type & d)288 this_t& operator+=(const difference_type& d) { memunit_advance(x(),offset(d.x,d.y)); return *this; } operator -=(const difference_type & d)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) cache_location(const difference_type & d) const293 cached_location_t cache_location(const difference_type& d) const { return offset(d.x,d.y); } cache_location(x_coord_t dx,y_coord_t dy) const294 cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return offset(dx,dy); } operator [](const cached_location_t & loc) const295 reference operator[](const cached_location_t& loc) const { return memunit_advanced_ref(x(),loc); } 296 297 // Only make sense for memory-based locators row_size() const298 std::ptrdiff_t row_size() const { return memunit_step(y()); } // distance in mem units (bytes or bits) between adjacent rows pixel_size() const299 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 is_1d_traversable(x_coord_t width) const301 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 y_distance_to(const this_t & p2,x_coord_t xDiff) const304 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; offset(x_coord_t x,y_coord_t y) const312 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