Re: [boost] stride_iterator_policy

From: Kresimir Fresl (fresl_at_[hidden])
Date: 2001-08-27 09:57:54

On Monday 27 August 2001 16:12, David Abrahams wrote:

[[ Toon Knapen wrote:
[[   template < int N >
[[   class stride_iterator_policy : public boost::default_iterator_policies
[[...]
[[      static void increment(BaseType& x) { std::advance( x, N ); }

> This is a good idea, but it is common to need to select the stride at
> runtime.

I agree.

AFAIK, in the latest version of iterator_policies increment() is not 
a static member function; I think that stride can therefore be a 
member of stride_iterator_policy.

> An intersting fact about striding over matrices: to avoid undefined
> behavior you usually need to allocate an extra row (or column) so that
> there's a valid end iterator position.

Here is my strided_iterator which addresses this problem. It was 
written before iterator_adaptors were added to boost and 
therefore uses iterator helpers from operators.hpp.
Also, it is restricted to random access iterators. But I hope
that some ideas can be helpful. 

================================================

  #include <iterator> 
  #include <boost/operators.hpp> 

  template <typename RndAIt> 
  class strided_iterator 
    : public boost::random_access_iterator_helper<
      strided_iterator<RndAIt>, 
      typename std::iterator_traits<RndAIt>::value_type, 
      typename std::iterator_traits<RndAIt>::difference_type, 
      typename std::iterator_traits<RndAIt>::pointer,
      typename std::iterator_traits<RndAIt>::reference
  > {
  public:

    typedef strided_iterator<RndAIt> self_t; 
    typedef RndAIt base_iterator; 
    typedef std::random_access_iterator_tag iterator_category; 
    typedef typename std::iterator_traits<RndAIt>::difference_type
                                                   difference_type; 
    typedef typename std::iterator_traits<RndAIt>::value_type value_type;
    typedef typename std::iterator_traits<RndAIt>::pointer pointer; 
    typedef typename std::iterator_traits<RndAIt>::reference reference; 

    strided_iterator() {}

    explicit strided_iterator (base_iterator from, 
                     difference_type step = 1)
      : first (from), curr (0), strd (step) {}

    reference operator*() const { return first[curr]; }

    self_t& operator++() { curr += strd; return *this; }
    self_t& operator--() { curr -= strd; return *this; }
    self_t& operator+= (difference_type n) { 
      curr += n * strd; 
      return *this; 
    }
    self_t& operator-= (difference_type n) { 
      curr -= n * strd; 
      return *this; 
    }

    friend bool operator== (self_t const& l, self_t const& r) { 
      return l.curr == r.curr
        && l.first == r.first
        && l.strd == r.strd; 
    }
    friend bool operator< (self_t const& l, self_t const& r) { 
      return l.curr < r.curr
        && l.first == r.first
        && l.strd == r.strd; 
    }
  
    friend difference_type operator- (self_t const& x, self_t const& y) {
      // if (x.first == y.first  && x.strd != y.strd)  
      //   throw something; 
      return (x.curr - y.curr) / x.strd;
    }

    base_iterator base() const { return first+curr; }
    base_iterator base_first() const { return first; }
    difference_type stride() const { return strd; }
    difference_type current() const { return curr; }

  protected:
    base_iterator first; 
    difference_type curr, strd;
  }; 

  // helper functions to construct sequence end:

  // .. n steps after the first, ie. current == n * stride

  template <typename RndAIt> 
  strided_iterator<RndAIt> strided_iterator_nth 
  (RndAIt from, 
   typename std::iterator_traits<RndAIt>::difference_type n, 
   typename std::iterator_traits<RndAIt>::difference_type step = 1
   ) {
    strided_iterator<RndAIt> sit (from, step); 
    sit += n; 
    return sit; 
  } 

  template <typename RndAIt> 
  strided_iterator<RndAIt> strided_iterator_nth 
  (strided_iterator<RndAIt> from, 
   typename std::iterator_traits<RndAIt>::difference_type n
   ) {
    from += n;
    return from; 
  } 

  // .. adjust current so that the it has right offset after the 
  // .... end of sequence (given by sequence::iterator to) 

  template <typename RndAIt> 
  strided_iterator<RndAIt> strided_iterator_to
  (RndAIt from, 
   RndAIt to, 
   typename std::iterator_traits<RndAIt>::difference_type step = 1
   ) {
    typedef typename std::iterator_traits<RndAIt>::difference_type d_t;
    d_t rdist = to - from; 
    d_t dist = rdist / step;
    d_t rem = rdist % step; 
    // caution: sign (rem)  is implementation-defined (ISO 83/4)
    if (rem != 0) 
      dist += 1; 
    return strided_iterator_nth (from, dist, step); 
  }

  template <typename RndAIt> 
  strided_iterator<RndAIt> 
  strided_iterator_to (strided_iterator<RndAIt> from, RndAIt to) {
    return 
      strided_iterator_to (from.base_first(), to, from.stride()); 
  }