iterator.h

Go to the documentation of this file.

/******************************************************************************
 Copyright (c) 2012-2016 Institut für Nachrichtentechnik, Universität Rostock
 Copyright (c) 2006-2012 Quality & Usability Lab
                         Deutsche Telekom Laboratories, TU Berlin
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:
 
 The above copyright notice and this permission notice shall be included in
 all copies or substantial portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 THE SOFTWARE.
*******************************************************************************/
 
// https://AudioProcessingFramework.github.io/
 
 
#ifndef APF_ITERATOR_H
#define APF_ITERATOR_H
 
#include <cassert>  // for assert()
#include <iterator>  // for std::iterator_traits, std::output_iterator_tag, ...
#include <type_traits>  // for std::remove_reference, std::result_of
 
#include "apf/math.h"  // for wrap()
 
namespace apf
{
template<typename T> bool no_nullptr(T* in) { return in != nullptr; }
 
template<typename T> bool no_nullptr(T&) { return true; }
}
 
#define APF_ITERATOR_CONSTRUCTORS(iterator_name, base_iterator_type, base_member) \
 \
  explicit iterator_name(base_iterator_type base_iterator) \
    : base_member(base_iterator) {} \
 \
  iterator_name() : base_member() {}
 
#define APF_ITERATOR_BASE(base_iterator_type, base_member) \
 \
  base_iterator_type base() const { assert(apf::no_nullptr(base_member)); \
    return (base_member); }
 
// Output Iterator Requirements
 
#define APF_ITERATOR_OUTPUT_DEREFERENCE(base_member) \
 \
  reference operator*() const { assert(apf::no_nullptr(base_member)); \
    return *(base_member); }
 
#define APF_ITERATOR_OUTPUT_PREINCREMENT(base_member) \
 \
  self& operator++() { assert(apf::no_nullptr(base_member)); \
    ++(base_member); return *this; }
 
#define APF_ITERATOR_OUTPUT_POSTINCREMENT \
 \
  self operator++(int) { self tmp = *this; ++(*this); return tmp; }
 
// Input Iterator Requirements
 
#define APF_ITERATOR_INPUT_DEREFERENCE APF_ITERATOR_OUTPUT_DEREFERENCE
 
#define APF_ITERATOR_INPUT_ARROW(base_member) \
 \
  pointer operator->() const { assert(apf::no_nullptr(base_member)); \
    return (base_member); }
 
#define APF_ITERATOR_INPUT_EQUAL(base_member) \
 \
  bool operator==(const self& rhs) const { \
    return ((base_member) == (rhs.base_member)); }
 
#define APF_ITERATOR_INPUT_PREINCREMENT APF_ITERATOR_OUTPUT_PREINCREMENT
 
#define APF_ITERATOR_INPUT_POSTINCREMENT APF_ITERATOR_OUTPUT_POSTINCREMENT
 
#define APF_ITERATOR_INPUT_UNEQUAL \
 \
  bool operator!=(const self& rhs) const { return !operator==(rhs); } \
 
// Forward Iterator Requirements
 
#define APF_ITERATOR_FORWARD_EQUAL APF_ITERATOR_INPUT_EQUAL
#define APF_ITERATOR_FORWARD_DEREFERENCE APF_ITERATOR_INPUT_DEREFERENCE
#define APF_ITERATOR_FORWARD_ARROW APF_ITERATOR_INPUT_ARROW
#define APF_ITERATOR_FORWARD_PREINCREMENT APF_ITERATOR_INPUT_PREINCREMENT
 
#define APF_ITERATOR_FORWARD_POSTINCREMENT APF_ITERATOR_INPUT_POSTINCREMENT
#define APF_ITERATOR_FORWARD_UNEQUAL APF_ITERATOR_INPUT_UNEQUAL
 
// Bidirectional Iterator Requirements
 
#define APF_ITERATOR_BIDIRECTIONAL_EQUAL APF_ITERATOR_FORWARD_EQUAL
#define APF_ITERATOR_BIDIRECTIONAL_DEREFERENCE APF_ITERATOR_FORWARD_DEREFERENCE
#define APF_ITERATOR_BIDIRECTIONAL_ARROW APF_ITERATOR_FORWARD_ARROW
#define APF_ITERATOR_BIDIRECTIONAL_PREINCREMENT APF_ITERATOR_FORWARD_PREINCREMENT
 
#define APF_ITERATOR_BIDIRECTIONAL_PREDECREMENT(base_member) \
 \
  self& operator--() { assert(apf::no_nullptr(base_member)); \
    --(base_member); return *this; }
 
#define APF_ITERATOR_BIDIRECTIONAL_POSTINCREMENT APF_ITERATOR_FORWARD_POSTINCREMENT
#define APF_ITERATOR_BIDIRECTIONAL_UNEQUAL APF_ITERATOR_FORWARD_UNEQUAL
 
#define APF_ITERATOR_BIDIRECTIONAL_POSTDECREMENT \
 \
  self operator--(int) { self tmp = *this; --(*this); return tmp; }
 
// Random Access Iterator Requirements
 
#define APF_ITERATOR_RANDOMACCESS_EQUAL APF_ITERATOR_BIDIRECTIONAL_EQUAL
#define APF_ITERATOR_RANDOMACCESS_DEREFERENCE APF_ITERATOR_BIDIRECTIONAL_DEREFERENCE
#define APF_ITERATOR_RANDOMACCESS_ARROW APF_ITERATOR_BIDIRECTIONAL_ARROW
#define APF_ITERATOR_RANDOMACCESS_PREINCREMENT APF_ITERATOR_BIDIRECTIONAL_PREINCREMENT
#define APF_ITERATOR_RANDOMACCESS_PREDECREMENT APF_ITERATOR_BIDIRECTIONAL_PREDECREMENT
 
#define APF_ITERATOR_RANDOMACCESS_ADDITION_ASSIGNMENT(base_member) \
 \
  self& operator+=(difference_type n) { \
    assert(!n || apf::no_nullptr(base_member)); \
    (base_member) += n; return *this; }
 
#define APF_ITERATOR_RANDOMACCESS_DIFFERENCE(base_member) \
 \
  friend difference_type operator-(const self& lhs, const self& rhs) { \
    assert(apf::no_nullptr(lhs.base_member) \
        && apf::no_nullptr(rhs.base_member)); \
    return ((lhs.base_member) - (rhs.base_member)); }
 
#define APF_ITERATOR_RANDOMACCESS_SUBSCRIPT \
 \
  reference operator[](difference_type n) const { \
    return *(*this + n); }
 
#define APF_ITERATOR_RANDOMACCESS_LESS(base_member) \
 \
  friend bool operator<(const self& lhs, const self& rhs) { \
    assert(apf::no_nullptr(lhs.base_member) \
        && apf::no_nullptr(rhs.base_member)); \
    return (lhs.base_member) < (rhs.base_member); }
 
#define APF_ITERATOR_RANDOMACCESS_UNEQUAL APF_ITERATOR_BIDIRECTIONAL_UNEQUAL
 
#define APF_ITERATOR_RANDOMACCESS_OTHER_COMPARISONS \
 \
  friend bool operator>(const self& lhs, const self& rhs) \
    { return rhs < lhs; } \
 \
  friend bool operator<=(const self& lhs, const self& rhs) \
    { return !(rhs < lhs); } \
\
  friend bool operator>=(const self& lhs, const self& rhs) \
    { return !(lhs < rhs); }
 
#define APF_ITERATOR_RANDOMACCESS_POSTINCREMENT APF_ITERATOR_BIDIRECTIONAL_POSTINCREMENT
 
#define APF_ITERATOR_RANDOMACCESS_POSTDECREMENT APF_ITERATOR_BIDIRECTIONAL_POSTDECREMENT
 
#define APF_ITERATOR_RANDOMACCESS_THE_REST \
 \
  self operator+(difference_type n) const { self tmp(*this); return tmp += n; }\
 \
  friend self operator+(difference_type n, const self& it) { \
    self temp(it); return temp += n; } \
 \
  self& operator-=(difference_type n) { *this += -n; return *this; } \
 \
  self operator-(difference_type n) const { self tmp(*this); return tmp += -n; }
 
namespace apf
{
 
template<typename I>
class has_begin_and_end
{
  public:
    using iterator = I;
    using reference = typename std::iterator_traits<I>::reference;
    using difference_type = typename std::iterator_traits<I>::difference_type;
 
    has_begin_and_end() : _begin(), _end() {}
 
    has_begin_and_end(iterator b, iterator e) : _begin(b), _end(e) {}
 
    template<typename Distance>
    has_begin_and_end(iterator b, Distance length)
      : _begin(b)
      , _end(b)
    {
      std::advance(_end, static_cast<std::make_signed_t<Distance>>(length));
    }
 
    // auto-generated copy constructor is used
 
    iterator begin() const { return _begin; }
 
    iterator end() const { return _end; }
 
    reference operator[](difference_type n) const { return _begin[n]; }
 
  protected:
    iterator _begin, _end;
};
 
template<typename I, typename... Args>
has_begin_and_end<I> make_begin_and_end(I first, Args&&... args)
{
  return {first, std::forward<Args>(args)...};
}
 
template<typename I, typename Container>
class iterator_proxy
{
  public:
    using iterator = I;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using size_type = typename Container::size_type;
    using value_type = typename std::iterator_traits<I>::value_type;
 
    // implicit conversion is desired, therefore no "explicit" keyword
    iterator_proxy(Container& l) : _l(l) {}
 
    iterator begin() const { return iterator(_l.begin()); }
    iterator end() const { return iterator(_l.end()); }
    reverse_iterator
    rbegin() const { return reverse_iterator(iterator(_l.end())); }
    reverse_iterator
    rend() const { return reverse_iterator(iterator(_l.begin())); }
    size_type size() const { return _l.size(); }
 
  private:
    Container& _l;
};
 
template<typename I, typename Container>
class iterator_proxy_const
{
  public:
    using iterator = I;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using size_type = typename Container::size_type;
    using value_type = typename std::iterator_traits<I>::value_type;
 
    // implicit conversion is desired, therefore no "explicit" keyword
    iterator_proxy_const(const Container& l) : _l(l) {}
 
    iterator begin() const { return iterator(_l.begin()); }
    iterator end() const { return iterator(_l.end()); }
    reverse_iterator
    rbegin() const { return reverse_iterator(iterator(_l.end())); }
    reverse_iterator
    rend() const { return reverse_iterator(iterator(_l.begin())); }
    size_type size() const { return _l.size(); }
 
  private:
    const Container& _l;
};
 
template<typename I>
class accumulating_iterator
{
  private:
    using self = accumulating_iterator;
 
  public:
    using iterator_category = std::output_iterator_tag;
    using value_type = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;
 
    APF_ITERATOR_CONSTRUCTORS(accumulating_iterator, I, _base_iterator)
 
    
    class output_proxy
    {
      public:
        explicit output_proxy(I& i) : _i(i) {}
 
        template<typename V>
        output_proxy& operator=(const V& v) { *_i += v; return *this; }
 
      private:
        I& _i;
    };
 
    output_proxy operator*()
    {
      assert(no_nullptr(_base_iterator));
      return output_proxy(_base_iterator);
    }
 
    // operator-> doesn't make sense!
 
    // straightforward operators:
    APF_ITERATOR_OUTPUT_PREINCREMENT(_base_iterator)
    APF_ITERATOR_OUTPUT_POSTINCREMENT
 
    APF_ITERATOR_BASE(I, _base_iterator)
 
  private:
    I _base_iterator;
};
 
template<typename I>
accumulating_iterator<I>
make_accumulating_iterator(I base_iterator)
{
  return accumulating_iterator<I>(base_iterator);
}
 
template<typename T, typename I>
class cast_iterator
{
  private:
    using self = cast_iterator;
 
  public:
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    using difference_type = typename std::iterator_traits<I>::difference_type;
    using iterator_category
      = typename std::iterator_traits<I>::iterator_category;
 
    APF_ITERATOR_CONSTRUCTORS(cast_iterator, I, _base_iterator)
 
    // auto-generated copy ctor and assignment operator are OK.
 
    
    reference operator*() const
    {
      assert(no_nullptr(_base_iterator));
      return *this->operator->();
    }
 
    pointer operator->() const
    {
      assert(no_nullptr(_base_iterator));
      // I::value_type must be a pointer to something!
      return _cast_helper(*_base_iterator);
    }
 
    reference operator[](difference_type n) const
    {
      assert(no_nullptr(_base_iterator));
      return *_cast_helper(_base_iterator[n]);
    }
 
    // straightforward operators:
    APF_ITERATOR_RANDOMACCESS_EQUAL(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_LESS(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_PREINCREMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_PREDECREMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_ADDITION_ASSIGNMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_DIFFERENCE(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_POSTINCREMENT
    APF_ITERATOR_RANDOMACCESS_POSTDECREMENT
    APF_ITERATOR_RANDOMACCESS_UNEQUAL
    APF_ITERATOR_RANDOMACCESS_OTHER_COMPARISONS
    APF_ITERATOR_RANDOMACCESS_THE_REST
 
    APF_ITERATOR_BASE(I, _base_iterator)
 
  private:
    template<typename X>
    pointer _cast_helper(X* ptr) const
    {
      return static_cast<pointer>(ptr);
    }
 
    I _base_iterator;
};
 
template<typename T, typename I>
cast_iterator<T, I>
make_cast_iterator(I base_iterator)
{
  return cast_iterator<T, I>(base_iterator);
}
 
template<typename T, typename Container>
struct cast_proxy : iterator_proxy<
                      cast_iterator<T, typename Container::iterator>, Container>
{
  using value_type = T;
 
  cast_proxy(Container& l)
    : iterator_proxy<cast_iterator<
        T, typename Container::iterator>, Container>(l)
  {}
};
 
template<typename T, typename Container>
cast_proxy<T, Container>
make_cast_proxy(Container& l)
{
  return cast_proxy<T, Container>(l);
}
 
template<typename T, typename Container>
struct cast_proxy_const : iterator_proxy_const<
          cast_iterator<const T, typename Container::const_iterator>, Container>
{
  using value_type = T;
 
  cast_proxy_const(const Container& l)
    : iterator_proxy_const<cast_iterator<
        const T, typename Container::const_iterator>, Container>(l)
  {}
};
 
template<typename T, typename Container>
cast_proxy_const<T, Container>
make_cast_proxy_const(Container& l)
{
  return cast_proxy_const<T, Container>(l);
}
 
template<typename I>
class circular_iterator
{
  private:
    using self = circular_iterator;
 
  public:
 
    using iterator_category
      = typename std::iterator_traits<I>::iterator_category;
    using value_type = typename std::iterator_traits<I>::value_type;
    using difference_type = typename std::iterator_traits<I>::difference_type;
    using pointer = typename std::iterator_traits<I>::pointer;
    using reference = typename std::iterator_traits<I>::reference;
 
 
 
    circular_iterator(I begin, I end, I current)
      : _begin(begin)
      , _end(end)
      , _current((current == end) ? begin : current)  // wrap around
    {
      assert(no_nullptr(_begin) && no_nullptr(_end) && no_nullptr(_current));
      assert(_begin != _end);
      assert(_current != _end);
    }
 
    circular_iterator(I begin, I end)
      : _begin(begin)
      , _end(end)
      , _current(begin)
    {
      assert(no_nullptr(_begin) && no_nullptr(_end) && no_nullptr(_current));
      assert(_begin != _end);
    }
 
    // Although this constructor is normally useless, it's good for unit tests.
    explicit circular_iterator(I begin)
      : _begin(begin)
      , _end(begin + 1)
      , _current(begin)
    {
      assert(no_nullptr(_begin) && no_nullptr(_end) && no_nullptr(_current));
      assert(_begin != _end);
    }
 
    circular_iterator()
      : _begin()
      , _end()
      , _current()
    {}
 
 
 
 
    self&
    operator++()
    {
      assert(no_nullptr(_begin) && no_nullptr(_end) && no_nullptr(_current));
      ++_current;
      if (_current == _end) _current = _begin;
      return *this;
    }
 
    self&
    operator--()
    {
      assert(no_nullptr(_begin) && no_nullptr(_end) && no_nullptr(_current));
      if (_current == _begin) _current = _end;
      --_current;
      return *this;
    }
 
    self&
    operator+=(difference_type n)
    {
      assert(!n
          || (no_nullptr(_begin) && no_nullptr(_end) && no_nullptr(_current)));
      difference_type length = _end     - _begin;
      difference_type index  = _current - _begin;
      index += n;
      _current = _begin + apf::math::wrap(index, length);
      return *this;
    }
 
    friend
    difference_type
    operator-(const self& lhs, const self& rhs)
    {
      assert(no_nullptr(lhs._begin)   && no_nullptr(rhs._begin));
      assert(no_nullptr(lhs._end)     && no_nullptr(rhs._end));
      assert(no_nullptr(lhs._current) && no_nullptr(rhs._current));
      assert(lhs._begin == rhs._begin);
      assert(lhs._end   == rhs._end  );
 
      difference_type d = lhs._current - rhs._current;
 
      if (d < 0)
      {
        d = lhs._current - lhs._begin + rhs._end - rhs._current;
      }
      // if lhs and rhs are the same, the difference is of course zero.
      return d;
    }
 
    // straightforward operators:
    APF_ITERATOR_RANDOMACCESS_DEREFERENCE(_current)
    APF_ITERATOR_RANDOMACCESS_ARROW(_current)
    APF_ITERATOR_RANDOMACCESS_EQUAL(_current)
    APF_ITERATOR_RANDOMACCESS_UNEQUAL
    APF_ITERATOR_RANDOMACCESS_SUBSCRIPT
    APF_ITERATOR_RANDOMACCESS_POSTINCREMENT
    APF_ITERATOR_RANDOMACCESS_POSTDECREMENT
    APF_ITERATOR_RANDOMACCESS_THE_REST
 
 
    APF_ITERATOR_BASE(I, _current)
 
  private:
    I _begin;   
    I _end;     
    I _current; 
};
 
template<typename I>
circular_iterator<I>
make_circular_iterator(I begin, I end)
{
  return circular_iterator<I>(begin, end);
}
 
template<typename I>
circular_iterator<I>
make_circular_iterator(I begin, I end, I current)
{
  return circular_iterator<I>(begin, end, current);
}
 
template<typename I, typename F>
class transform_iterator
{
  private:
    using self = transform_iterator;
    // NOTE: value_type& works for by-value, by-reference and by-const-reference
    using _signature = F(typename std::iterator_traits<I>::value_type&);
 
  public:
    using iterator_category
      = typename std::iterator_traits<I>::iterator_category;
    using reference = typename std::result_of<_signature>::type;
    using value_type = typename std::remove_reference<reference>::type;
    using pointer = value_type*;
    using difference_type = typename std::iterator_traits<I>::difference_type;
 
    explicit transform_iterator(I base_iterator = I(), F f = F())
      : _base_iterator(base_iterator)
      , _f(f)
    {}
 
    reference operator*() { return _f(*_base_iterator); }
 
    pointer operator->()
    {
      return &this->operator*();
    }
 
    APF_ITERATOR_RANDOMACCESS_EQUAL(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_PREINCREMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_LESS(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_PREDECREMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_ADDITION_ASSIGNMENT(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_DIFFERENCE(_base_iterator)
    APF_ITERATOR_RANDOMACCESS_POSTINCREMENT
    APF_ITERATOR_RANDOMACCESS_UNEQUAL
    APF_ITERATOR_RANDOMACCESS_SUBSCRIPT
    APF_ITERATOR_RANDOMACCESS_POSTDECREMENT
    APF_ITERATOR_RANDOMACCESS_OTHER_COMPARISONS
    APF_ITERATOR_RANDOMACCESS_THE_REST
 
    APF_ITERATOR_BASE(I, _base_iterator)
 
  private:
    I _base_iterator;
    F _f;
};
 
template<typename I, typename F>
transform_iterator<I, F>
make_transform_iterator(I base_iterator, F f)
{
  return transform_iterator<I, F>(base_iterator, f);
}
 
template<typename F, typename Container>
struct transform_proxy : iterator_proxy<
                 transform_iterator<typename Container::iterator, F>, Container>
{
  transform_proxy(Container& l)
    : iterator_proxy<transform_iterator<
        typename Container::iterator, F>, Container>(l)
  {}
};
 
template<typename F, typename Container>
struct transform_proxy_const : iterator_proxy_const<
           transform_iterator<typename Container::const_iterator, F>, Container>
{
  transform_proxy_const(const Container& l)
    : iterator_proxy_const<transform_iterator<
      typename Container::const_iterator, F>, Container>(l)
  {}
};
 
template<typename T>
class index_iterator
{
  private:
    using self = index_iterator;
 
  public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using reference = T;
    using difference_type = T;
    using pointer = void;
 
    explicit index_iterator(T start = T())
      : _number(start)
    {}
 
    reference operator*() const { return _number; }
 
    // operator-> doesn't make sense!
 
    APF_ITERATOR_RANDOMACCESS_EQUAL(_number)
    APF_ITERATOR_RANDOMACCESS_PREINCREMENT(_number)
    APF_ITERATOR_RANDOMACCESS_PREDECREMENT(_number)
    APF_ITERATOR_RANDOMACCESS_ADDITION_ASSIGNMENT(_number)
    APF_ITERATOR_RANDOMACCESS_DIFFERENCE(_number)
    APF_ITERATOR_RANDOMACCESS_LESS(_number)
    APF_ITERATOR_RANDOMACCESS_SUBSCRIPT
    APF_ITERATOR_RANDOMACCESS_UNEQUAL
    APF_ITERATOR_RANDOMACCESS_OTHER_COMPARISONS
    APF_ITERATOR_RANDOMACCESS_POSTINCREMENT
    APF_ITERATOR_RANDOMACCESS_POSTDECREMENT
    APF_ITERATOR_RANDOMACCESS_THE_REST
 
  private:
    T _number;
};
 
template<typename T>
index_iterator<T>
make_index_iterator(T start)
{
  return index_iterator<T>(start);
}
 
template<class I>
class stride_iterator
{
  private:
    using self = stride_iterator;
 
  public:
 
    using iterator_category
      = typename std::iterator_traits<I>::iterator_category;
    using value_type = typename std::iterator_traits<I>::value_type;
    using difference_type = typename std::iterator_traits<I>::difference_type;
    using reference = typename std::iterator_traits<I>::reference;
    using pointer = typename std::iterator_traits<I>::pointer;
 
    explicit stride_iterator(I base_iterator, difference_type step
#ifdef APF_STRIDE_ITERATOR_DEFAULT_STRIDE
        = APF_STRIDE_ITERATOR_DEFAULT_STRIDE
#endif
        )
      : _iter(base_iterator)
      , _step(step)
    {}
 
    stride_iterator(stride_iterator<I> base_iterator, difference_type step)
      : _iter(base_iterator.base())
      , _step(base_iterator.step_size() * step)
    {}
 
    stride_iterator()
      : _iter()
      , _step(0)
    {}
 
    bool
    operator==(const self& rhs) const
    {
      return _iter == rhs._iter && _step == rhs._step;
    }
 
    self&
    operator++()
    {
      assert(no_nullptr(_iter));
      std::advance(_iter, _step);
      return *this;
    }
 
    self&
    operator--()
    {
      assert(no_nullptr(_iter));
      std::advance(_iter, -_step);
      return *this;
    }
 
    reference
    operator[](difference_type n) const
    {
      assert(no_nullptr(_iter));
      return _iter[n * _step];
    }
 
    self&
    operator+=(difference_type n)
    {
      assert(!n || no_nullptr(_iter));
      std::advance(_iter, n * _step);
      return *this;
    }
 
    friend
    difference_type
    operator-(const self& lhs, const self& rhs)
    {
      assert(no_nullptr(lhs._iter) && no_nullptr(rhs._iter));
      assert(lhs._step == rhs._step);
      return (lhs._iter - rhs._iter) / lhs._step;
    }
 
    friend
    bool
    operator<(const self& lhs, const self& rhs)
    {
      assert(no_nullptr(lhs._iter) && no_nullptr(rhs._iter));
      assert(lhs._step == rhs._step);
      return lhs._iter < rhs._iter;
    }
 
    friend
    bool
    operator<=(const self& lhs, const self& rhs)
    {
      assert(no_nullptr(lhs._iter) && no_nullptr(rhs._iter));
      assert(lhs._step == rhs._step);
      return lhs._iter <= rhs._iter;
    }
 
    friend
    bool
    operator>(const self& lhs, const self& rhs)
    {
      assert(no_nullptr(lhs._iter) && no_nullptr(rhs._iter));
      assert(lhs._step == rhs._step);
      return lhs._iter > rhs._iter;
    }
 
    friend
    bool
    operator>=(const self& lhs, const self& rhs)
    {
      assert(no_nullptr(lhs._iter) && no_nullptr(rhs._iter));
      assert(lhs._step == rhs._step);
      return lhs._iter >= rhs._iter;
    }
 
    // straightforward operators:
    APF_ITERATOR_RANDOMACCESS_DEREFERENCE(_iter)
    APF_ITERATOR_RANDOMACCESS_ARROW(_iter)
    APF_ITERATOR_RANDOMACCESS_UNEQUAL
    APF_ITERATOR_RANDOMACCESS_POSTINCREMENT
    APF_ITERATOR_RANDOMACCESS_POSTDECREMENT
    APF_ITERATOR_RANDOMACCESS_THE_REST
 
    APF_ITERATOR_BASE(I, _iter)
 
    difference_type step_size() const { return _step; }
 
  private:
    I _iter; 
    // This has to be non-const to allow automatic assignment operator:
    difference_type _step; 
};
 
template<typename I1, typename I2 = I1>
class dual_iterator
{
  private:
    using self = dual_iterator;
 
  public:
    // TODO: what if I1 or I2 are only input or output iterators?
    // TODO: some witty metaprogram to find the greatest common denominator?
    using iterator_category = std::forward_iterator_tag;
 
    using value_type = std::pair<typename std::iterator_traits<I1>::value_type
                               , typename std::iterator_traits<I2>::value_type>;
 
    class output_proxy;  // For implementation see below
    using reference = output_proxy;
 
    using difference_type = std::ptrdiff_t;
    using pointer = void;
 
    dual_iterator() = default;
 
    dual_iterator(I1 i1, I2 i2) : _i1(i1), _i2(i2) {}
 
    reference operator*()
    {
      assert(no_nullptr(_i1) && no_nullptr(_i2));
      return reference(_i1, _i2);
    }
 
    // operator-> doesn't really make sense
 
    self& operator++()
    {
      assert(no_nullptr(_i1) && no_nullptr(_i2));
      ++_i1;
      ++_i2;
      return *this;
    }
 
    bool operator==(const self& rhs) const
    {
      return (_i1 == rhs._i1) && (_i2 == rhs._i2);
    }
 
    APF_ITERATOR_FORWARD_POSTINCREMENT
    APF_ITERATOR_FORWARD_UNEQUAL
 
  private:
    I1 _i1;
    I2 _i2;
};
 
template<typename I1, typename I2>
class dual_iterator<I1, I2>::output_proxy
{
  public:
    explicit output_proxy(I1& i1, I2& i2) : _i1(i1), _i2(i2) {}
 
    template<typename T1, typename T2>
    operator std::pair<T1, T2>()
    {
      return {*_i1, *_i2};
    }
 
    template<typename T1, typename T2>
    output_proxy& operator=(const std::pair<T1, T2>& rhs)
    {
      *_i1 = rhs.first;
      *_i2 = rhs.second;
      return *this;
    }
 
    template<typename T>
    output_proxy& operator=(const T& rhs)
    {
      *_i1 = rhs;
      *_i2 = rhs;
      return *this;
    }
 
    template<typename T1, typename T2>
    output_proxy& operator+=(const std::pair<T1, T2>& rhs)
    {
      *_i1 += rhs.first;
      *_i2 += rhs.second;
      return *this;
    }
 
    template<typename T>
    output_proxy& operator+=(const T& rhs)
    {
      *_i1 += rhs;
      *_i2 += rhs;
      return *this;
    }
 
  private:
    I1& _i1;
    I2& _i2;
};
 
template<typename I1, typename I2>
dual_iterator<I1, I2>
make_dual_iterator(I1 i1, I2 i2)
{
  return dual_iterator<I1, I2>(i1, i2);
}
 
class discard_iterator
{
  private:
    using self = discard_iterator;
 
  public:
    using iterator_category = std::output_iterator_tag;
    using value_type = void;
    using difference_type = void;
    using pointer = void;
 
    struct output_proxy
    {
      template<typename T>
      output_proxy& operator=(const T&) { return *this; }
 
      template<typename T>
      output_proxy& operator+=(const T&) { return *this; }
    };
 
    using reference = output_proxy;
 
    reference operator*()
    {
      return reference();
    }
 
    self& operator++() { return *this; }
 
    bool operator==(const self&) const { return true; }
 
    APF_ITERATOR_OUTPUT_POSTINCREMENT
    APF_ITERATOR_FORWARD_UNEQUAL
};
 
}  // namespace apf
 
#endif