// N4317 "New Safer Functions to Advance Iterators" paper can be found at
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4317.pdf

namespace detail {
    template<class InputIter>
    inline void do_advance(InputIter& it, InputIter end, typename std::iterator_traits<InputIter>::difference_type n, std::input_iterator_tag)
    {
        assert(n >= 0);
        for (; (n > 0) && (it != end); --n)
            ++it;
    }

    template<class BiDirIter>
    inline void do_advance(BiDirIter& it, BiDirIter end, typename std::iterator_traits<BiDirIter>::difference_type n, std::bidirectional_iterator_tag)
    {
        if (n >= 0) {
            for (; (n > 0) && (it != end); --n)
                ++it;
        } else {
            for (; (n < 0) && (it != end); ++n)
                --it;
        }
    }

    template<class RandIter>
    inline void do_advance(RandIter& it, RandIter end, typename std::iterator_traits<RandIter>::difference_type n, std::random_access_iterator_tag)
    {
        it += std::min(n, end - it);
    }
}

template<class InputIter>
inline void advance(InputIter& it, InputIter end, typename std::iterator_traits<InputIter>::difference_type n)
{
    detail::do_advance(it, end, n, typename std::iterator_traits<InputIter>::iterator_category{});
}

template<class InputIter>
inline InputIter next(InputIter it, InputIter end, typename std::iterator_traits<InputIter>::difference_type n = 1)
{
    advance(it, end, n);
    return it;
}

template<class BidirectionalIter>
inline BidirectionalIter prev(BidirectionalIter it, BidirectionalIter end, typename std::iterator_traits<BidirectionalIter>::difference_type n = 1)
{
    static_assert(std::is_base_of<std::bidirectional_iterator_tag, typename std::iterator_traits<BidirectionalIter>::iterator_category>::value,
                  "Bidirectional iterator required");
    advance(it, end, -n);
    return it;
}