// Copyright David Abrahams 2008. Distributed under the Boost
// Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#define _GLIBCXX_DEBUG 1

#include "boost/iterator/iterator_adaptor.hpp"
#include "boost/iterator/counting_iterator.hpp"
//#include <algorithm>
#include <numeric>
#include <cassert>
#include <iostream>
#include <iterator>

template <class RandomAccessIterator, std::size_t N>
struct strided_iterator
  : boost::iterator_adaptor<
        strided_iterator<RandomAccessIterator,N>,
        RandomAccessIterator
    >
{
    strided_iterator() {}
    
    explicit strided_iterator(
        RandomAccessIterator p,
        RandomAccessIterator start,
        RandomAccessIterator finish
    )
      : strided_iterator::iterator_adaptor_(p),
        start(start), finish(finish)
    {
    }
 private:
    friend class boost::iterator_core_access;
    
    void increment()
    {
        this->advance(1);
    }
    
    void decrement()
    {
        this->advance(-1);
    }

    typename strided_iterator::difference_type
    distance_to(strided_iterator const& rhs) const
    {
        return (rhs.base() - this->base() + N - 1) / N;
    }
    
    void advance(typename strided_iterator::difference_type x)
    {
        if (x > 0)
        {
            if (finish - this->base() >= N*x)
                this->base_reference() += N*x;
            else
                this->base_reference() = finish;
        }
        else
        {
            if (this->base() - start >= x*N)
                this->base_reference() -= x*N;
            else
                this->base_reference() = start;
        }
    }
    
    RandomAccessIterator start, finish;
};

template <std::size_t N, class I>
strided_iterator<I,N> make_strided_iterator(I pos, I start, I finish)
{
    return strided_iterator<I,N>(pos, start, finish);
}

int main()
{
    boost::counting_iterator<int> start(0);
    boost::counting_iterator<int> finish(13*7);

    int total = std::accumulate(
        make_strided_iterator<5>(start, start, finish),
        make_strided_iterator<5>(finish, start, finish), 0);

    int t2 = 0;
    for (int i = 0; i < 13*7; i+=5)
        t2 += i;

    assert(total == t2);

    std::copy(
        make_strided_iterator<5>(start, start, finish),
        make_strided_iterator<5>(finish, start, finish),
        std::ostream_iterator<int>(std::cout, " "));
}