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_STEP_ITERATOR_H
Chris@16: #define GIL_STEP_ITERATOR_H
Chris@16: 
Chris@16: ////////////////////////////////////////////////////////////////////////////////////////
Chris@16: /// \file               
Chris@16: /// \brief pixel step iterator
Chris@16: /// \author Lubomir Bourdev and Hailin Jin \n
Chris@16: ///         Adobe Systems Incorporated
Chris@16: /// \date   2005-2007 \n Last updated on September 18, 2007
Chris@16: ///
Chris@16: ////////////////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: #include <cstddef>
Chris@16: #include <iterator>
Chris@16: #include <boost/iterator/iterator_facade.hpp>
Chris@16: #include "gil_config.hpp"
Chris@16: #include "utilities.hpp"
Chris@16: #include "pixel_iterator.hpp"
Chris@16: #include "pixel_iterator_adaptor.hpp"
Chris@16: 
Chris@16: namespace boost { namespace gil {
Chris@16: 
Chris@16: /// \defgroup PixelIteratorModelStepPtr step iterators
Chris@16: /// \ingroup PixelIteratorModel
Chris@16: /// \brief Iterators that allow for specifying the step between two adjacent values
Chris@16: 
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: /// \ingroup PixelIteratorModelStepPtr
Chris@16: /// \brief An adaptor over an existing iterator that changes the step unit
Chris@16: ///
Chris@16: /// (i.e. distance(it,it+1)) by a given predicate. Instead of calling base's 
Chris@16: /// operators ++, --, +=, -=, etc. the adaptor is using the passed policy object SFn
Chris@16: /// for advancing and for computing the distance between iterators.
Chris@16: 
Chris@16: template <typename Derived,  // type of the derived class
Chris@16:           typename Iterator, // Models Iterator
Chris@16:           typename SFn>      // A policy object that can compute the distance between two iterators of type Iterator
Chris@16:                              // and can advance an iterator of type Iterator a given number of Iterator's units  
Chris@16: class step_iterator_adaptor : public iterator_adaptor<Derived, Iterator, use_default, use_default, use_default, typename SFn::difference_type> {
Chris@16: public:
Chris@16:     typedef iterator_adaptor<Derived, Iterator, use_default, use_default, use_default, typename SFn::difference_type> parent_t;
Chris@16:     typedef typename std::iterator_traits<Iterator>::difference_type base_difference_type;
Chris@16:     typedef typename SFn::difference_type                           difference_type;
Chris@16:     typedef typename std::iterator_traits<Iterator>::reference       reference;
Chris@16: 
Chris@16:     step_iterator_adaptor() {}
Chris@16:     step_iterator_adaptor(const Iterator& it, SFn step_fn=SFn()) : parent_t(it), _step_fn(step_fn) {}
Chris@16: 
Chris@16:     difference_type step() const { return _step_fn.step(); }
Chris@16: 
Chris@16: protected:
Chris@16:     SFn _step_fn;
Chris@16: private:
Chris@16:     friend class boost::iterator_core_access;
Chris@16: 
Chris@16:     void increment() { _step_fn.advance(this->base_reference(),1); }
Chris@16:     void decrement() { _step_fn.advance(this->base_reference(),-1); }
Chris@16:     void advance(base_difference_type d) { _step_fn.advance(this->base_reference(),d); }
Chris@16:     difference_type distance_to(const step_iterator_adaptor& it) const { return _step_fn.difference(this->base_reference(),it.base_reference()); }
Chris@16: };
Chris@16: 
Chris@16: // although iterator_adaptor defines these, the default implementation computes distance and compares for zero.
Chris@16: // it is often faster to just apply the relation operator to the base
Chris@16: template <typename D,typename Iterator,typename SFn> inline
Chris@16: bool operator>(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) { 
Chris@16:     return p1.step()>0 ? p1.base()> p2.base() : p1.base()< p2.base(); 
Chris@16: }
Chris@16: 
Chris@16: template <typename D,typename Iterator,typename SFn> inline
Chris@16: bool operator<(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) { 
Chris@16:     return p1.step()>0 ? p1.base()< p2.base() : p1.base()> p2.base(); 
Chris@16: }
Chris@16: 
Chris@16: template <typename D,typename Iterator,typename SFn> inline
Chris@16: bool operator>=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) { 
Chris@16:     return p1.step()>0 ? p1.base()>=p2.base() : p1.base()<=p2.base(); 
Chris@16: }
Chris@16: 
Chris@16: template <typename D,typename Iterator,typename SFn> inline
Chris@16: bool operator<=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) { 
Chris@16:     return p1.step()>0 ? p1.base()<=p2.base() : p1.base()>=p2.base(); 
Chris@16: }
Chris@16: 
Chris@16: template <typename D,typename Iterator,typename SFn> inline
Chris@16: bool operator==(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) { 
Chris@16:     return p1.base()==p2.base(); 
Chris@16: }
Chris@16: 
Chris@16: template <typename D,typename Iterator,typename SFn> inline
Chris@16: bool operator!=(const step_iterator_adaptor<D,Iterator,SFn>& p1, const step_iterator_adaptor<D,Iterator,SFn>& p2) { 
Chris@16:     return p1.base()!=p2.base(); 
Chris@16: }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16: ////////////////////////////////////////////////////////////////////////////////////////
Chris@16: ///                 MEMORY-BASED STEP ITERATOR
Chris@16: ////////////////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: /// \class memory_based_step_iterator
Chris@16: /// \ingroup PixelIteratorModelStepPtr PixelBasedModel
Chris@16: /// \brief Iterator with dynamically specified step in memory units (bytes or bits). Models StepIteratorConcept, IteratorAdaptorConcept, MemoryBasedIteratorConcept, PixelIteratorConcept, HasDynamicXStepTypeConcept
Chris@16: ///
Chris@16: /// A refinement of step_iterator_adaptor that uses a dynamic parameter for the step 
Chris@16: /// which is specified in memory units, such as bytes or bits
Chris@16: ///
Chris@16: /// Pixel step iterators are used to provide iteration over non-adjacent pixels. 
Chris@16: /// Common use is a vertical traversal, where the step is the row stride.
Chris@16: ///
Chris@16: /// Another application is as a sub-channel view. For example, a red intensity image over 
Chris@16: /// interleaved RGB data would use a step iterator adaptor with step sizeof(channel_t)*3
Chris@16: /// In the latter example the step size could be fixed at compile time for efficiency.
Chris@16: /// Compile-time fixed step can be implemented by providing a step function object that takes the step as a template
Chris@16: ////////////////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: /// \ingroup PixelIteratorModelStepPtr
Chris@16: /// \brief function object that returns the memory unit distance between two iterators and advances a given iterator a given number of mem units (bytes or bits)
Chris@16: template <typename Iterator>
Chris@16: struct memunit_step_fn {
Chris@16:     typedef std::ptrdiff_t difference_type;
Chris@16: 
Chris@16:     memunit_step_fn(difference_type step=memunit_step(Iterator())) : _step(step) {}
Chris@16: 
Chris@16:     difference_type difference(const Iterator& it1, const Iterator& it2) const { return memunit_distance(it1,it2)/_step; }
Chris@16:     void            advance(Iterator& it, difference_type d)             const { memunit_advance(it,d*_step); } 
Chris@16:     difference_type step()                                               const { return _step; }
Chris@16: 
Chris@16:     void            set_step(std::ptrdiff_t step) { _step=step; }
Chris@16: private:
Chris@16:     GIL_CLASS_REQUIRE(Iterator, boost::gil, MemoryBasedIteratorConcept)
Chris@16:     difference_type _step;
Chris@16: };
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: class memory_based_step_iterator : public detail::step_iterator_adaptor<memory_based_step_iterator<Iterator>, 
Chris@16:                                                                             Iterator, 
Chris@16:                                                                             memunit_step_fn<Iterator> > {
Chris@16:     GIL_CLASS_REQUIRE(Iterator, boost::gil, MemoryBasedIteratorConcept)
Chris@16: public:
Chris@16:     typedef detail::step_iterator_adaptor<memory_based_step_iterator<Iterator>, 
Chris@16:                                           Iterator, 
Chris@16:                                           memunit_step_fn<Iterator> > parent_t;
Chris@16:     typedef typename parent_t::reference                            reference;
Chris@16:     typedef typename parent_t::difference_type                      difference_type;
Chris@16:     typedef Iterator                                                x_iterator;
Chris@16: 
Chris@16:     memory_based_step_iterator() : parent_t(Iterator()) {}
Chris@16:     memory_based_step_iterator(Iterator it, std::ptrdiff_t memunit_step) : parent_t(it, memunit_step_fn<Iterator>(memunit_step)) {}
Chris@16:     template <typename I2> 
Chris@16:     memory_based_step_iterator(const memory_based_step_iterator<I2>& it)
Chris@16:         : parent_t(it.base(), memunit_step_fn<Iterator>(it.step())) {}
Chris@16: 
Chris@16:     /// For some reason operator[] provided by iterator_adaptor returns a custom class that is convertible to reference
Chris@16:     /// We require our own reference because it is registered in iterator_traits
Chris@16:     reference operator[](difference_type d) const { return *(*this+d); }
Chris@16: 
Chris@16:     void set_step(std::ptrdiff_t memunit_step) { this->_step_fn.set_step(memunit_step); }
Chris@16: 
Chris@16:     x_iterator& base()              { return parent_t::base_reference(); }
Chris@16:     x_iterator const& base() const  { return parent_t::base_reference(); }
Chris@16: };
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct const_iterator_type<memory_based_step_iterator<Iterator> > {
Chris@16:     typedef memory_based_step_iterator<typename const_iterator_type<Iterator>::type>  type;
Chris@16: };
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct iterator_is_mutable<memory_based_step_iterator<Iterator> > : public iterator_is_mutable<Iterator> {};
Chris@16: 
Chris@16: 
Chris@16: /////////////////////////////
Chris@16: //  IteratorAdaptorConcept
Chris@16: /////////////////////////////
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct is_iterator_adaptor<memory_based_step_iterator<Iterator> > : public mpl::true_{};
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct iterator_adaptor_get_base<memory_based_step_iterator<Iterator> > {
Chris@16:     typedef Iterator type;
Chris@16: };
Chris@16: 
Chris@16: template <typename Iterator, typename NewBaseIterator>
Chris@16: struct iterator_adaptor_rebind<memory_based_step_iterator<Iterator>,NewBaseIterator> {
Chris@16:     typedef memory_based_step_iterator<NewBaseIterator> type;
Chris@16: };
Chris@16: 
Chris@16: /////////////////////////////
Chris@16: //  PixelBasedConcept
Chris@16: /////////////////////////////
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct color_space_type<memory_based_step_iterator<Iterator> > : public color_space_type<Iterator> {};
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct channel_mapping_type<memory_based_step_iterator<Iterator> > : public channel_mapping_type<Iterator> {};
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct is_planar<memory_based_step_iterator<Iterator> > : public is_planar<Iterator> {};
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct channel_type<memory_based_step_iterator<Iterator> > : public channel_type<Iterator> {};
Chris@16: 
Chris@16: /////////////////////////////
Chris@16: //  MemoryBasedIteratorConcept
Chris@16: /////////////////////////////
Chris@16: template <typename Iterator>
Chris@16: struct byte_to_memunit<memory_based_step_iterator<Iterator> > : public byte_to_memunit<Iterator> {};
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: inline std::ptrdiff_t memunit_step(const memory_based_step_iterator<Iterator>& p) { return p.step(); }
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: inline std::ptrdiff_t memunit_distance(const memory_based_step_iterator<Iterator>& p1, 
Chris@16:                                     const memory_based_step_iterator<Iterator>& p2) { 
Chris@16:     return memunit_distance(p1.base(),p2.base()); 
Chris@16: }
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: inline void memunit_advance(memory_based_step_iterator<Iterator>& p, 
Chris@16:                          std::ptrdiff_t diff) { 
Chris@16:     memunit_advance(p.base(), diff);
Chris@16: }
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: inline memory_based_step_iterator<Iterator> 
Chris@16: memunit_advanced(const memory_based_step_iterator<Iterator>& p, 
Chris@16:               std::ptrdiff_t diff) {
Chris@16:     return memory_based_step_iterator<Iterator>(memunit_advanced(p.base(), diff),p.step());
Chris@16: }
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: inline typename std::iterator_traits<Iterator>::reference 
Chris@16: memunit_advanced_ref(const memory_based_step_iterator<Iterator>& p, 
Chris@16:                   std::ptrdiff_t diff) { 
Chris@16:     return memunit_advanced_ref(p.base(), diff);
Chris@16: }
Chris@16: 
Chris@16: /////////////////////////////
Chris@16: //  HasDynamicXStepTypeConcept
Chris@16: /////////////////////////////
Chris@16: 
Chris@16: template <typename Iterator>
Chris@16: struct dynamic_x_step_type<memory_based_step_iterator<Iterator> > {
Chris@16:     typedef memory_based_step_iterator<Iterator> type;
Chris@16: };
Chris@16: 
Chris@16: // For step iterators, pass the function object to the base
Chris@16: template <typename Iterator, typename Deref>
Chris@16: struct iterator_add_deref<memory_based_step_iterator<Iterator>,Deref> {
Chris@16:     GIL_CLASS_REQUIRE(Deref, boost::gil, PixelDereferenceAdaptorConcept)
Chris@16: 
Chris@16:     typedef memory_based_step_iterator<typename iterator_add_deref<Iterator, Deref>::type> type;
Chris@16: 
Chris@16:     static type make(const memory_based_step_iterator<Iterator>& it, const Deref& d) { return type(iterator_add_deref<Iterator, Deref>::make(it.base(),d),it.step()); }
Chris@16: };
Chris@16: 
Chris@16: ////////////////////////////////////////////////////////////////////////////////////////
Chris@16: /// make_step_iterator
Chris@16: ////////////////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: template <typename I> typename dynamic_x_step_type<I>::type make_step_iterator(const I& it, std::ptrdiff_t step);
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: // if the iterator is a plain base iterator (non-adaptor), wraps it in memory_based_step_iterator
Chris@16: template <typename I> 
Chris@16: typename dynamic_x_step_type<I>::type make_step_iterator_impl(const I& it, std::ptrdiff_t step, mpl::false_) {
Chris@16:     return memory_based_step_iterator<I>(it, step);
Chris@16: }
Chris@16: 
Chris@16: // If the iterator is compound, put the step in its base
Chris@16: template <typename I> 
Chris@16: typename dynamic_x_step_type<I>::type make_step_iterator_impl(const I& it, std::ptrdiff_t step, mpl::true_) {
Chris@16:     return make_step_iterator(it.base(), step);
Chris@16: }
Chris@16: 
Chris@16: // If the iterator is memory_based_step_iterator, change the step
Chris@16: template <typename BaseIt> 
Chris@16: memory_based_step_iterator<BaseIt> make_step_iterator_impl(const memory_based_step_iterator<BaseIt>& it, std::ptrdiff_t step, mpl::true_) {
Chris@16:     return memory_based_step_iterator<BaseIt>(it.base(), step);
Chris@16: }
Chris@16: }
Chris@16: 
Chris@16: /// \brief Constructs a step iterator from a base iterator and a step.
Chris@16: ///
Chris@16: /// To construct a step iterator from a given iterator Iterator and a given step, if Iterator does not
Chris@16: /// already have a dynamic step, we wrap it in a memory_based_step_iterator. Otherwise we 
Chris@16: /// do a compile-time traversal of the chain of iterator adaptors to locate the step iterator
Chris@16: /// and then set it step to the new one.
Chris@16: ///
Chris@16: /// The step iterator of Iterator is not always memory_based_step_iterator<Iterator>. For example, Iterator may
Chris@16: /// already be a memory_based_step_iterator, in which case it will be inefficient to stack them;
Chris@16: /// we can obtain the same result by multiplying their steps. Note that for Iterator to be a
Chris@16: /// step iterator it does not necessarily have to have the form memory_based_step_iterator<J>.
Chris@16: /// The step iterator can be wrapped inside another iterator. Also, it may not have the
Chris@16: /// type memory_based_step_iterator, but it could be a user-provided type.
Chris@16: template <typename I>  // Models MemoryBasedIteratorConcept, HasDynamicXStepTypeConcept
Chris@16: typename dynamic_x_step_type<I>::type make_step_iterator(const I& it, std::ptrdiff_t step) {
Chris@16:     return detail::make_step_iterator_impl(it, step, typename is_iterator_adaptor<I>::type());
Chris@16: }
Chris@16: 
Chris@16: } }  // namespace boost::gil
Chris@16: 
Chris@16: #endif