Chris@16: /* Chris@16: Copyright 2005-2007 Adobe Systems Incorporated Chris@16: Chris@16: Use, modification and distribution are subject to the Boost Software License, Chris@16: Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at Chris@16: http://www.boost.org/LICENSE_1_0.txt). Chris@16: Chris@16: See http://opensource.adobe.com/gil for most recent version including documentation. Chris@16: */ Chris@16: Chris@16: /*************************************************************************************************/ Chris@16: Chris@16: #ifndef GIL_LOCATOR_H Chris@16: #define GIL_LOCATOR_H Chris@16: Chris@16: Chris@16: //////////////////////////////////////////////////////////////////////////////////////// Chris@16: /// \file Chris@16: /// \brief pixel 2D locator Chris@16: /// \author Lubomir Bourdev and Hailin Jin \n Chris@16: /// Adobe Systems Incorporated Chris@16: /// \date 2005-2007 \n September 20, 2006 Chris@16: /// Chris@16: //////////////////////////////////////////////////////////////////////////////////////// Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include "pixel_iterator.hpp" Chris@16: Chris@16: //////////////////////////////////////////////////////////////////////////////////////// Chris@16: /// Pixel 2D LOCATOR Chris@16: //////////////////////////////////////////////////////////////////////////////////////// Chris@16: Chris@16: Chris@16: namespace boost { namespace gil { Chris@16: Chris@16: //forward declarations Chris@16: template ptrdiff_t memunit_step(const P*); Chris@16: template P* memunit_advanced(const P* p, ptrdiff_t diff); Chris@16: template P& memunit_advanced_ref(P* p, ptrdiff_t diff); Chris@16: template struct iterator_add_deref; Chris@16: template class point2; Chris@16: namespace detail { Chris@16: // helper class specialized for each axis of pixel_2d_locator Chris@16: template class locator_axis; Chris@16: } Chris@16: template struct dynamic_x_step_type; Chris@16: template struct dynamic_y_step_type; Chris@16: Chris@16: template struct channel_type; Chris@16: template struct color_space_type; Chris@16: template struct channel_mapping_type; Chris@16: template struct is_planar; Chris@16: template struct num_channels; Chris@16: Chris@16: // The type of a locator or a view that has X and Y swapped. By default it is the same Chris@16: template struct transposed_type { Chris@16: typedef T type; Chris@16: }; Chris@16: Chris@16: /// \class pixel_2d_locator_base Chris@16: /// \brief base class for models of PixelLocatorConcept Chris@16: /// \ingroup PixelLocatorModel PixelBasedModel Chris@16: /// Chris@16: /// Pixel locator is similar to a pixel iterator, but allows for 2D navigation of pixels within an image view. Chris@16: /// It has a 2D difference_type and supports random access operations like: Chris@16: /// \code Chris@16: /// difference_type offset2(2,3); Chris@16: /// locator+=offset2; Chris@16: /// locator[offset2]=my_pixel; Chris@16: /// \endcode Chris@16: /// Chris@16: /// In addition, each coordinate acts as a random-access iterator that can be modified separately: Chris@16: /// "++locator.x()" or "locator.y()+=10" thereby moving the locator horizontally or vertically. Chris@16: /// Chris@16: /// It is called a locator because it doesn't implement the complete interface of a random access iterator. Chris@16: /// For example, increment and decrement operations don't make sense (no way to specify dimension). Chris@16: /// Also 2D difference between two locators cannot be computed without knowledge of the X position within the image. Chris@16: /// Chris@16: /// This base class provides most of the methods and typedefs needed to create a model of a locator. GIL provides two Chris@16: /// locator models as subclasses of \p pixel_2d_locator_base. A memory-based locator, \p memory_based_2d_locator and a virtual Chris@16: /// locator, \p virtual_2d_locator. Chris@16: /// The minimum functionality a subclass must provide is this: Chris@16: /// \code Chris@16: /// class my_locator : public pixel_2d_locator_base { // supply the types for x-iterator and y-iterator Chris@16: /// typedef ... const_t; // read-only locator Chris@16: /// Chris@16: /// template struct add_deref { Chris@16: /// typedef ... type; // locator that invokes the Deref dereference object upon pixel access Chris@16: /// static type make(const my_locator& loc, const Deref& d); Chris@16: /// }; Chris@16: /// Chris@16: /// my_locator(); Chris@16: /// my_locator(const my_locator& pl); Chris@16: /// Chris@16: /// // constructors with dynamic step in y (and x). Only valid for locators with dynamic steps Chris@16: /// my_locator(const my_locator& loc, coord_t y_step); Chris@16: /// my_locator(const my_locator& loc, coord_t x_step, coord_t y_step, bool transpose); Chris@16: /// Chris@16: /// bool operator==(const my_locator& p) const; Chris@16: /// Chris@16: /// // return _references_ to horizontal/vertical iterators. Advancing them moves this locator Chris@16: /// x_iterator& x(); Chris@16: /// y_iterator& y(); Chris@16: /// x_iterator const& x() const; Chris@16: /// y_iterator const& y() const; Chris@16: /// Chris@16: /// // return the vertical distance to another locator. Some models need the horizontal distance to compute it Chris@16: /// y_coord_t y_distance_to(const my_locator& loc2, x_coord_t xDiff) const; Chris@16: /// Chris@16: /// // return true iff incrementing an x-iterator located at the last column will position it at the first Chris@16: /// // column of the next row. Some models need the image width to determine that. Chris@16: /// bool is_1d_traversable(x_coord_t width) const; Chris@16: /// }; Chris@16: /// \endcode Chris@16: /// Chris@16: /// Models may choose to override some of the functions in the base class with more efficient versions. Chris@16: /// Chris@16: Chris@16: template // The concrete subclass, the X-iterator and the Y-iterator Chris@16: class pixel_2d_locator_base { Chris@16: public: Chris@16: typedef XIterator x_iterator; Chris@16: typedef YIterator y_iterator; Chris@16: Chris@16: // typedefs required by ConstRandomAccessNDLocatorConcept Chris@16: static const std::size_t num_dimensions=2; Chris@16: typedef typename std::iterator_traits::value_type value_type; Chris@16: typedef typename std::iterator_traits::reference reference; // result of dereferencing Chris@16: typedef typename std::iterator_traits::difference_type coord_t; // 1D difference type (same for all dimensions) Chris@16: typedef point2 difference_type; // result of operator-(locator,locator) Chris@16: typedef difference_type point_t; Chris@16: template struct axis { Chris@16: typedef typename detail::locator_axis::coord_t coord_t; Chris@16: typedef typename detail::locator_axis::iterator iterator; Chris@16: }; Chris@16: Chris@16: // typedefs required by ConstRandomAccess2DLocatorConcept Chris@16: typedef typename point_t::template axis<0>::coord_t x_coord_t; Chris@16: typedef typename point_t::template axis<1>::coord_t y_coord_t; Chris@16: Chris@16: bool operator!=(const Loc& p) const { return !(concrete()==p); } Chris@16: Chris@16: x_iterator x_at(x_coord_t dx, y_coord_t dy) const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp.x(); } Chris@16: x_iterator x_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp.x(); } Chris@16: y_iterator y_at(x_coord_t dx, y_coord_t dy) const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp.y(); } Chris@16: y_iterator y_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp.y(); } Chris@16: Loc xy_at(x_coord_t dx, y_coord_t dy) const { Loc tmp=concrete(); tmp+=point_t(dx,dy); return tmp; } Chris@16: Loc xy_at(const difference_type& d) const { Loc tmp=concrete(); tmp+=d; return tmp; } Chris@16: Chris@16: template typename axis::iterator& axis_iterator() { return detail::locator_axis()(concrete()); } Chris@16: template typename axis::iterator const& axis_iterator() const { return detail::locator_axis()(concrete()); } Chris@16: template typename axis::iterator axis_iterator(const point_t& p) const { return detail::locator_axis()(concrete(),p); } Chris@16: Chris@16: reference operator()(x_coord_t dx, y_coord_t dy) const { return *x_at(dx,dy); } Chris@16: reference operator[](const difference_type& d) const { return *x_at(d.x,d.y); } Chris@16: Chris@16: reference operator*() const { return *concrete().x(); } Chris@16: Chris@16: Loc& operator+=(const difference_type& d) { concrete().x()+=d.x; concrete().y()+=d.y; return concrete(); } Chris@16: Loc& operator-=(const difference_type& d) { concrete().x()-=d.x; concrete().y()-=d.y; return concrete(); } Chris@16: Chris@16: Loc operator+(const difference_type& d) const { return xy_at(d); } Chris@16: Loc operator-(const difference_type& d) const { return xy_at(-d); } Chris@16: Chris@16: // Some locators can cache 2D coordinates for faster subsequent access. By default there is no caching Chris@16: typedef difference_type cached_location_t; Chris@16: cached_location_t cache_location(const difference_type& d) const { return d; } Chris@16: cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return difference_type(dx,dy); } Chris@16: Chris@16: private: Chris@16: Loc& concrete() { return (Loc&)*this; } Chris@16: const Loc& concrete() const { return (const Loc&)*this; } Chris@16: Chris@16: template friend class pixel_2d_locator; Chris@16: }; Chris@16: Chris@16: // helper classes for each axis of pixel_2d_locator_base Chris@16: namespace detail { Chris@16: template Chris@16: class locator_axis<0,Loc> { Chris@16: typedef typename Loc::point_t point_t; Chris@16: public: Chris@16: typedef typename point_t::template axis<0>::coord_t coord_t; Chris@16: typedef typename Loc::x_iterator iterator; Chris@16: Chris@16: inline iterator& operator()( Loc& loc) const { return loc.x(); } Chris@16: inline iterator const& operator()(const Loc& loc) const { return loc.x(); } Chris@16: inline iterator operator()( Loc& loc, const point_t& d) const { return loc.x_at(d); } Chris@16: inline iterator operator()(const Loc& loc, const point_t& d) const { return loc.x_at(d); } Chris@16: }; Chris@16: Chris@16: template Chris@16: class locator_axis<1,Loc> { Chris@16: typedef typename Loc::point_t point_t; Chris@16: public: Chris@16: typedef typename point_t::template axis<1>::coord_t coord_t; Chris@16: typedef typename Loc::y_iterator iterator; Chris@16: Chris@16: inline iterator& operator()( Loc& loc) const { return loc.y(); } Chris@16: inline iterator const& operator()(const Loc& loc) const { return loc.y(); } Chris@16: inline iterator operator()( Loc& loc, const point_t& d) const { return loc.y_at(d); } Chris@16: inline iterator operator()(const Loc& loc, const point_t& d) const { return loc.y_at(d); } Chris@16: }; Chris@16: } Chris@16: Chris@16: template Chris@16: struct channel_type > : public channel_type {}; Chris@16: Chris@16: template Chris@16: struct color_space_type > : public color_space_type {}; Chris@16: Chris@16: template Chris@16: struct channel_mapping_type > : public channel_mapping_type {}; Chris@16: Chris@16: template Chris@16: struct is_planar > : public is_planar {}; Chris@16: Chris@16: /// \class memory_based_2d_locator Chris@16: /// \brief Memory-based pixel locator. Models: PixelLocatorConcept,HasDynamicXStepTypeConcept,HasDynamicYStepTypeConcept,HasTransposedTypeConcept Chris@16: /// \ingroup PixelLocatorModel PixelBasedModel Chris@16: /// Chris@16: /// The class takes a step iterator as a parameter. The step iterator provides navigation along the vertical axis Chris@16: /// while its base iterator provides horizontal navigation. Chris@16: /// Chris@16: /// Each instantiation is optimal in terms of size and efficiency. Chris@16: /// For example, xy locator over interleaved rgb image results in a step iterator consisting of Chris@16: /// one std::ptrdiff_t for the row size and one native pointer (8 bytes total). ++locator.x() resolves to pointer Chris@16: /// increment. At the other extreme, a 2D navigation of the even pixels of a planar CMYK image results in a step Chris@16: /// iterator consisting of one std::ptrdiff_t for the doubled row size, and one step iterator consisting of Chris@16: /// one std::ptrdiff_t for the horizontal step of two and a CMYK planar_pixel_iterator consisting of 4 pointers (24 bytes). Chris@16: /// In this case ++locator.x() results in four native pointer additions. Chris@16: /// Chris@16: /// Note also that \p memory_based_2d_locator does not require that its element type be a pixel. It could be Chris@16: /// instantiated with an iterator whose \p value_type models only \p Regular. In this case the locator Chris@16: /// models the weaker RandomAccess2DLocatorConcept, and does not model PixelBasedConcept. Chris@16: /// Many generic algorithms don't require the elements to be pixels. Chris@16: //////////////////////////////////////////////////////////////////////////////////////// Chris@16: Chris@16: template Chris@16: class memory_based_2d_locator : public pixel_2d_locator_base, typename iterator_adaptor_get_base::type, StepIterator> { Chris@16: typedef memory_based_2d_locator this_t; Chris@16: GIL_CLASS_REQUIRE(StepIterator, boost::gil, StepIteratorConcept) Chris@16: public: Chris@16: typedef pixel_2d_locator_base, typename iterator_adaptor_get_base::type, StepIterator> parent_t; Chris@16: typedef memory_based_2d_locator::type> const_t; // same as this type, but over const values Chris@16: Chris@16: typedef typename parent_t::coord_t coord_t; Chris@16: typedef typename parent_t::x_coord_t x_coord_t; Chris@16: typedef typename parent_t::y_coord_t y_coord_t; Chris@16: typedef typename parent_t::x_iterator x_iterator; Chris@16: typedef typename parent_t::y_iterator y_iterator; Chris@16: typedef typename parent_t::difference_type difference_type; Chris@16: typedef typename parent_t::reference reference; Chris@16: Chris@16: template struct add_deref { Chris@16: typedef memory_based_2d_locator::type> type; Chris@16: static type make(const memory_based_2d_locator& loc, const Deref& nderef) { Chris@16: return type(iterator_add_deref::make(loc.y(),nderef)); Chris@16: } Chris@16: }; Chris@16: Chris@16: memory_based_2d_locator() {} Chris@16: memory_based_2d_locator(const StepIterator& yit) : _p(yit) {} Chris@16: template memory_based_2d_locator(const memory_based_2d_locator& loc, coord_t y_step) : _p(loc.x(), loc.row_size()*y_step) {} Chris@16: template memory_based_2d_locator(const memory_based_2d_locator& loc, coord_t x_step, coord_t y_step, bool transpose=false) Chris@16: : _p(make_step_iterator(loc.x(),(transpose ? loc.row_size() : loc.pixel_size())*x_step), Chris@16: (transpose ? loc.pixel_size() : loc.row_size())*y_step ) {} Chris@16: Chris@16: memory_based_2d_locator(x_iterator xit, std::ptrdiff_t row_bytes) : _p(xit,row_bytes) {} Chris@16: template memory_based_2d_locator(const memory_based_2d_locator& pl) : _p(pl._p) {} Chris@16: memory_based_2d_locator(const memory_based_2d_locator& pl) : _p(pl._p) {} Chris@16: Chris@16: bool operator==(const this_t& p) const { return _p==p._p; } Chris@16: Chris@16: x_iterator const& x() const { return _p.base(); } Chris@16: y_iterator const& y() const { return _p; } Chris@16: x_iterator& x() { return _p.base(); } Chris@16: y_iterator& y() { return _p; } Chris@16: Chris@16: // These are faster versions of functions already provided in the superclass Chris@16: x_iterator x_at (x_coord_t dx, y_coord_t dy) const { return memunit_advanced(x(), offset(dx,dy)); } Chris@16: x_iterator x_at (const difference_type& d) const { return memunit_advanced(x(), offset(d.x,d.y)); } Chris@16: this_t xy_at (x_coord_t dx, y_coord_t dy) const { return this_t(x_at( dx , dy ), row_size()); } Chris@16: this_t xy_at (const difference_type& d) const { return this_t(x_at( d.x, d.y), row_size()); } Chris@16: reference operator()(x_coord_t dx, y_coord_t dy) const { return memunit_advanced_ref(x(),offset(dx,dy)); } Chris@16: reference operator[](const difference_type& d) const { return memunit_advanced_ref(x(),offset(d.x,d.y)); } Chris@16: this_t& operator+=(const difference_type& d) { memunit_advance(x(),offset(d.x,d.y)); return *this; } Chris@16: this_t& operator-=(const difference_type& d) { memunit_advance(x(),offset(-d.x,-d.y)); return *this; } Chris@16: Chris@16: // Memory-based locators can have 1D caching of 2D relative coordinates Chris@16: typedef std::ptrdiff_t cached_location_t; // type used to store relative location (to allow for more efficient repeated access) Chris@16: cached_location_t cache_location(const difference_type& d) const { return offset(d.x,d.y); } Chris@16: cached_location_t cache_location(x_coord_t dx, y_coord_t dy)const { return offset(dx,dy); } Chris@16: reference operator[](const cached_location_t& loc) const { return memunit_advanced_ref(x(),loc); } Chris@16: Chris@16: // Only make sense for memory-based locators Chris@16: std::ptrdiff_t row_size() const { return memunit_step(y()); } // distance in mem units (bytes or bits) between adjacent rows Chris@16: std::ptrdiff_t pixel_size() const { return memunit_step(x()); } // distance in mem units (bytes or bits) between adjacent pixels on the same row Chris@16: Chris@16: 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? Chris@16: Chris@16: // Returns the vertical distance (it2.y-it1.y) between two x_iterators given the difference of their x positions Chris@16: std::ptrdiff_t y_distance_to(const this_t& p2, x_coord_t xDiff) const { Chris@16: std::ptrdiff_t rowDiff=memunit_distance(x(),p2.x())-pixel_size()*xDiff; Chris@16: assert(( rowDiff % row_size())==0); Chris@16: return rowDiff / row_size(); Chris@16: } Chris@16: Chris@16: private: Chris@16: template friend class memory_based_2d_locator; Chris@16: std::ptrdiff_t offset(x_coord_t x, y_coord_t y) const { return y*row_size() + x*pixel_size(); } Chris@16: StepIterator _p; Chris@16: }; Chris@16: Chris@16: ///////////////////////////// Chris@16: // PixelBasedConcept Chris@16: ///////////////////////////// Chris@16: Chris@16: template Chris@16: struct color_space_type > : public color_space_type::parent_t> { Chris@16: }; Chris@16: Chris@16: template Chris@16: struct channel_mapping_type > : public channel_mapping_type::parent_t> { Chris@16: }; Chris@16: Chris@16: template Chris@16: struct is_planar > : public is_planar::parent_t> { Chris@16: }; Chris@16: Chris@16: template Chris@16: struct channel_type > : public channel_type::parent_t> { Chris@16: }; Chris@16: Chris@16: ///////////////////////////// Chris@16: // HasDynamicXStepTypeConcept Chris@16: ///////////////////////////// Chris@16: Chris@16: // Take the base iterator of SI (which is typically a step iterator) and change it to have a step in x Chris@16: template Chris@16: struct dynamic_x_step_type > { Chris@16: private: Chris@16: typedef typename iterator_adaptor_get_base::type base_iterator_t; Chris@16: typedef typename dynamic_x_step_type::type base_iterator_step_t; Chris@16: typedef typename iterator_adaptor_rebind::type dynamic_step_base_t; Chris@16: public: Chris@16: typedef memory_based_2d_locator type; Chris@16: }; Chris@16: Chris@16: ///////////////////////////// Chris@16: // HasDynamicYStepTypeConcept Chris@16: ///////////////////////////// Chris@16: Chris@16: template Chris@16: struct dynamic_y_step_type > { Chris@16: typedef memory_based_2d_locator type; Chris@16: }; Chris@16: Chris@16: } } // namespace boost::gil Chris@16: Chris@16: #endif