#include <algorithm>
#include <cassert>
#include <iterator>
#include <vector>
#include <forward_list>

template <typename It>
class sliding_average_iterator
{
public:

    sliding_average_iterator(It iterator, std::size_t N)
        : curr { iterator }, prev { iterator }, N { N }, count {  }, average { }
    {
    }
    
    using difference_type = void;
    using value_type = typename It::value_type;
    using pointer = value_type*;
    using reference = value_type&;
    using iterator_category = std::input_iterator_tag;

    typename It::value_type operator*() const
    {
        if (count < N) 
            return (average * count + *curr) / (count + 1);
        return (average * N + *curr - *prev) / N;
    }

    sliding_average_iterator& operator++()
    {
        average = *(*this);

        ++curr;
        if (count < N)
            ++count;
        else
            ++prev;
        return *this;
    }

    sliding_average_iterator operator++(int)
    {
        sliding_average_iterator old { *this };
        ++(*this);
        return old;
    }

    bool operator==(sliding_average_iterator const& other) const
    {
        return curr == other.curr;
    }

    bool operator!=(sliding_average_iterator const& other) const
    {
        return !(*this == other);
    }

private:

    It curr;
    It prev;

    std::size_t N;
    std::size_t count;

    typename It::value_type average;

};

template <typename It>
sliding_average_iterator<It> make_sliding_average_iterator(It current, std::size_t N)
{
    return sliding_average_iterator<It> { current, N };
}

int main()
{
    // basic test of the functionality, N = 2
    {
        std::vector<double> values { 1.0, 2.5, 3.5, 4.75, 5.25 };

        std::vector<double> answers { 1.0, 1.75, 3.0, 4.125, 5.0 };
        std::vector<double> averages { };

        auto begin = make_sliding_average_iterator(values.begin(), 2);
        auto end   = make_sliding_average_iterator(values.end(), 2);
        for (auto it = begin; it != end; ++it)
            averages.push_back(*it);

        // averages[0] = 1.0 / 1
        // averages[1] = (1.0 + 2.5) / 2
        // averages[2] = (2.5 + 3.5) / 2
        // averages[3] = (3.5 + 4.75) / 2
        // averages[4] = (4.75 + 5.25) / 2
        assert(( averages == answers ));
    }

    // test that it works for forward iterators, N = 3
    {
        std::forward_list<int> values { 2, 4, 6, 5, 7, 9, 8 };

        std::vector<int> answers { 2, 3, 4, 5, 6, 7, 8 };
        std::vector<int> averages { };

        auto begin = make_sliding_average_iterator(values.begin(), 3);
        auto end   = make_sliding_average_iterator(values.end(), 3);
        for (auto it = begin; it != end; ++it)
            averages.push_back(*it);

        // averages[0] = 2 / 1
        // averages[1] = (2 + 4) / 2
        // averages[2] = (2 + 4 + 6) / 3
        // averages[3] = (4 + 6 + 5) / 3
        // averages[4] = (6 + 5 + 7) / 3
        // averages[5] = (5 + 7 + 9) / 3
        // averages[6] = (7 + 9 + 8) / 3
        assert(( averages == answers ));
    }

    // test that it is compatible with STL.
    // A sliding average with N = 1 should be equal to the original values
    {
        std::vector<float> values { 1.125f, 2.25f, 3.5f, 4.0f };
        std::vector<float> averages {
            make_sliding_average_iterator(values.begin(), 1),
            make_sliding_average_iterator(values.end(), 1)
        };

        assert(( values == averages ));
    }
}