4
\$\begingroup\$

The code implements fully generic sliding window with linear complexity. It should usually be paired with transforming iterator to reach full potential.

Sliding window is a grouping of elements by exactly length of sliding window, then "sliding" the window by one element on each iteration.

Example: Given A = [0, 1, 2, 3], L=3, there are 2 windows: [0, 1, 2], [1, 2, 3].

But instead of working only on numbers, the code works on anything, given that user supplies their own add operation (adds an element into the window), and remove operation (removes the element from the window).

#ifndef SUNRISE_SLIDING_WINDOW_HPP
#define SUNRISE_SLIDING_WINDOW_HPP

#include <functional>
#include <stdexcept>
#include <iterator>

namespace shino
{
    template<typename BidirIt,
             typename OutputIt,
             typename T = typename std::iterator_traits<BidirIt>::value_type,
             typename BinaryDoOp = std::plus<>,
             typename BinaryUndoOp = std::minus<>>
    std::pair<BidirIt, OutputIt> sliding_window(BidirIt first,
                        BidirIt last,
                        OutputIt d_first,
                        typename std::iterator_traits<BidirIt>::difference_type length,
                        T init = {},
                        BinaryDoOp add_op = {},
                        BinaryUndoOp remove_op = {})
    {
        if (first == last || length == 0)
        {
            return std::make_pair(first, d_first);
        }

        BidirIt milestone(std::next(first, length)); //try to default construct
        auto tail = first;

        while (first != last && first != milestone)
        {
            init = add_op(init, *first);
            ++first;
        }

        if (first != milestone)
        {
            throw std::invalid_argument("Iterator range is smaller than length of the window");
        }

        *d_first = init;
        ++d_first;

        if (first == last)
        {
            return std::make_pair(first, d_first);
        }

        while (first != last)
        {
            init = remove_op(init, *tail);
            init = add_op(init, *first);
            *d_first = init;
            ++tail;
            ++first;
            ++d_first;
        }

        return std::make_pair(first, d_first);
    }
}

#endif //SUNRISE_SLIDING_WINDOW_HPP

So aim is to make a generic version of this code, providing some defaults to make it easy to use. Though the best way of using the generic sliding algorithm is to write more specialized ones, for the sake of clarity and narrowing down the error vectors. Also, using transform_iterator, it is possible to get full power over grouped manipulation.

So, here is example: the sliding average using generic sliding window:

template <typename InputIt, typename OutputIt>
std::pair<InputIt, OutputIt> sliding_average(InputIt first, InputIt last,
                    const typename std::iterator_traits<InputIt>::difference_type window_length,
                    OutputIt d_first)
{
    using value_type = typename std::iterator_traits<InputIt>::value_type;
    auto divide = [&window_length](const value_type& value)
    {
        return value / window_length;
    };

    auto iterator = shino::transformer(divide, d_first); //transform_iterator<Functor, Iterator>

    auto result = shino::sliding_window(first, last, iterator, window_length);

    return std::make_pair(result.first, result.second.internal_iterator());
}

The algorithm also warns if input type is int, and output type is double, e.g. compiler will warn if narrowing conversions are performed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.