forward_split.hpp

#include <algorithm>
#include <ranges>

namespace rx {

namespace rng = std::ranges;

template <rng::forward_range V, rng::forward_range Pattern>
    requires rng::view<V> && rng::view<Pattern> &&
             std::indirectly_comparable<rng::iterator_t<V>,
                                        rng::iterator_t<Pattern>,
                                        rng::equal_to>
struct forward_split_view : rng::view_interface<forward_split_view<V, Pattern>>
{
private:
    struct sentinel {
        rng::sentinel_t<V> s;
    };

    struct iterator {
    private:
        forward_split_view* parent_ = nullptr;
        rng::iterator_t<V> cur_ = rng::iterator_t<V>();
        rng::iterator_t<V> next_ = rng::iterator_t<V>();

        constexpr rng::iterator_t<V> lookup_next()
        {
            return rng::search(cur_, rng::end(parent_->base_),
                               rng::begin(parent_->pattern_),
                               rng::end(parent_->pattern_)).begin();
        }

    public:
        using iterator_category = std::input_iterator_tag;
        using iterator_concept = std::forward_iterator_tag;
        using value_type = rng::subrange<rng::iterator_t<V>>;
        using difference_type = std::ptrdiff_t;

        iterator() = default;

        constexpr iterator(forward_split_view& parent, rng::iterator_t<V> cur)
            : parent_(std::addressof(parent)),
              cur_(std::move(cur)),
              next_(lookup_next())
        {}

        constexpr value_type operator*() const
        {
            return {cur_, next_};
        }

        constexpr iterator& operator++()
        {
            cur_ = next_;
            if (cur_ != rng::end(parent_->base_)) {
                rng::advance(cur_, parent_->pattern_size_, rng::end(parent_->base_));
                next_ = lookup_next();
            }
            return *this;
        }

        constexpr iterator operator++(int)
        {
            auto tmp = *this;
            ++*this;
            return tmp;
        }

        friend constexpr bool operator==(const iterator& lhs, const iterator& rhs)
        {
            return lhs.parent_ == rhs.parent_ &&
                    lhs.cur_ == rhs.cur_ &&
                    lhs.next_ == rhs.next_;
        }

        friend constexpr bool operator==(const iterator& lhs, const sentinel& rhs)
        {
            return lhs.cur_ == rhs.s;
        }
    };

    V base_ = V();
    Pattern pattern_= Pattern();
    std::optional<iterator> cached_begin_{};
    rng::range_difference_t<Pattern> pattern_size_ = rng::distance(pattern_);

public:
    forward_split_view() = default;

    constexpr forward_split_view(V base, Pattern pattern)
        : base_(std::move(base)),
          pattern_(std::move(pattern))
    {}

    constexpr forward_split_view(V base, rng::range_value_t<V> e)
        requires std::constructible_from<Pattern, rng::single_view<rng::range_value_t<V>>>
        : base_(std::move(base)),
          pattern_(rng::single_view{std::move(e)})
    {}

    constexpr V base() const& requires std::copy_constructible<V> { return base_; }
    constexpr V base() && { return std::move(base_); }

    constexpr iterator begin()
    {
        /* We can't update the cache during constexpr evaluation */
        if (std::is_constant_evaluated()) {
            return iterator{*this, rng::begin(base_)};
        } else {
            if (!cached_begin_) {
                cached_begin_ = iterator{*this, rng::begin(base_)};
            }
            return *cached_begin_;
        }
    }

    constexpr auto end() {
        if constexpr (rng::common_range<V>) {
            return iterator{*this, rng::end(base_)};
        } else if constexpr (rng::random_access_range<V>) {
            return iterator{*this, rng::next(rng::begin(base_), rng::end(base_))};
        } else {
            return sentinel{rng::end(base_)}; }
        }
};

template <class R, class P>
forward_split_view(R&&, P&&) -> forward_split_view<rng::views::all_t<R>, rng::views::all_t<P>>;

template <rng::input_range R>
forward_split_view(R&& r, rng::range_value_t<R>)
    -> forward_split_view<rng::views::all_t<R>, rng::single_view<rng::range_value_t<R>>>;


namespace views {

    struct _forward_split_fn {
        template <typename E, typename F>
        constexpr auto operator()(E&& e, F&& f) const
            -> decltype(forward_split_view{std::forward<E>(e), std::forward<F>(f)})
        {
            return forward_split_view{std::forward<E>(e), std::forward<F>(f)};
        }
    };

// Hack: hook into libstdc++'s pipe operator
#ifdef __GLIBCXX__
    inline constexpr rng::views::__adaptor::_RangeAdaptor forward_split = _forward_split_fn{};
#else
    inline constexpr auto forward_split = _forward_split_fn{};
#endif
}

constexpr bool test_forward_split()
{
    using namespace std::string_view_literals;

    auto to_string_view = [](rng::contiguous_range auto v) {
        return std::string_view{v.data(), v.size()};
    };

    auto v = "something something something dark side"sv
                | views::forward_split(' ')
                | std::views::transform(to_string_view);

    return rng::equal(v, std::array{
        "something"sv, "something"sv, "something"sv, "dark"sv, "side"sv});
}
static_assert(test_forward_split());

}