v1/__ranges/split_view.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___RANGES_SPLIT_VIEW_H
0011 #define _LIBCPP___RANGES_SPLIT_VIEW_H
0012
0013 #include <__algorithm/ranges_search.h>
0014 #include <__concepts/constructible.h>
0015 #include <__config>
0016 #include <__functional/bind_back.h>
0017 #include <__functional/ranges_operations.h>
0018 #include <__iterator/indirectly_comparable.h>
0019 #include <__iterator/iterator_traits.h>
0020 #include <__memory/addressof.h>
0021 #include <__ranges/access.h>
0022 #include <__ranges/all.h>
0023 #include <__ranges/concepts.h>
0024 #include <__ranges/empty.h>
0025 #include <__ranges/non_propagating_cache.h>
0026 #include <__ranges/range_adaptor.h>
0027 #include <__ranges/single_view.h>
0028 #include <__ranges/subrange.h>
0029 #include <__ranges/view_interface.h>
0030 #include <__type_traits/decay.h>
0031 #include <__type_traits/is_nothrow_constructible.h>
0032 #include <__utility/forward.h>
0033 #include <__utility/move.h>
0034
0035 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0036 #  pragma GCC system_header
0037 #endif
0038
0039 _LIBCPP_PUSH_MACROS
0040 #include <__undef_macros>
0041
0042 _LIBCPP_BEGIN_NAMESPACE_STD
0043
0044 #if _LIBCPP_STD_VER >= 20
0045
0046 namespace ranges {
0047
0048 template <forward_range _View, forward_range _Pattern>
0049   requires view<_View> && view<_Pattern> &&
0050            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
0051 class split_view : public view_interface<split_view<_View, _Pattern>> {
0052 private:
0053   _LIBCPP_NO_UNIQUE_ADDRESS _View __base_       = _View();
0054   _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
0055   using _Cache _LIBCPP_NODEBUG                  = __non_propagating_cache<subrange<iterator_t<_View>>>;
0056   _Cache __cached_begin_                        = _Cache();
0057
0058   template <class, class>
0059   friend struct __iterator;
0060
0061   template <class, class>
0062   friend struct __sentinel;
0063
0064   struct __iterator;
0065   struct __sentinel;
0066
0067   _LIBCPP_HIDE_FROM_ABI constexpr subrange<iterator_t<_View>> __find_next(iterator_t<_View> __it) {
0068     auto [__begin, __end] = ranges::search(subrange(__it, ranges::end(__base_)), __pattern_);
0069     if (__begin != ranges::end(__base_) && ranges::empty(__pattern_)) {
0070       ++__begin;
0071       ++__end;
0072     }
0073     return {__begin, __end};
0074   }
0075
0076 public:
0077   _LIBCPP_HIDE_FROM_ABI split_view()
0078     requires default_initializable<_View> && default_initializable<_Pattern>
0079   = default;
0080
0081   _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 split_view(_View __base, _Pattern __pattern)
0082       : __base_(std::move(__base)), __pattern_(std::move((__pattern))) {}
0083
0084   template <forward_range _Range>
0085     requires constructible_from<_View, views::all_t<_Range>> &&
0086                  constructible_from<_Pattern, single_view<range_value_t<_Range>>>
0087   _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23
0088   split_view(_Range&& __range, range_value_t<_Range> __elem)
0089       : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {}
0090
0091   _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
0092     requires copy_constructible<_View>
0093   {
0094     return __base_;
0095   }
0096
0097   _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
0098
0099   _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() {
0100     if (!__cached_begin_.__has_value()) {
0101       __cached_begin_.__emplace(__find_next(ranges::begin(__base_)));
0102     }
0103     return {*this, ranges::begin(__base_), *__cached_begin_};
0104   }
0105
0106   _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
0107     if constexpr (common_range<_View>) {
0108       return __iterator{*this, ranges::end(__base_), {}};
0109     } else {
0110       return __sentinel{*this};
0111     }
0112   }
0113 };
0114
0115 template <class _Range, class _Pattern>
0116 split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
0117
0118 template <forward_range _Range>
0119 split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
0120
0121 template <forward_range _View, forward_range _Pattern>
0122   requires view<_View> && view<_Pattern> &&
0123            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
0124 struct split_view<_View, _Pattern>::__iterator {
0125 private:
0126   split_view* __parent_                                         = nullptr;
0127   _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_            = iterator_t<_View>();
0128   _LIBCPP_NO_UNIQUE_ADDRESS subrange<iterator_t<_View>> __next_ = subrange<iterator_t<_View>>();
0129   bool __trailing_empty_                                        = false;
0130
0131   friend struct __sentinel;
0132
0133 public:
0134   using iterator_concept  = forward_iterator_tag;
0135   using iterator_category = input_iterator_tag;
0136   using value_type        = subrange<iterator_t<_View>>;
0137   using difference_type   = range_difference_t<_View>;
0138
0139   _LIBCPP_HIDE_FROM_ABI __iterator() = default;
0140
0141   _LIBCPP_HIDE_FROM_ABI constexpr __iterator(
0142       split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange<iterator_t<_View>> __next)
0143       : __parent_(std::addressof(__parent)), __cur_(std::move(__current)), __next_(std::move(__next)) {}
0144
0145   _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; }
0146
0147   _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; }
0148
0149   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
0150     __cur_ = __next_.begin();
0151     if (__cur_ != ranges::end(__parent_->__base_)) {
0152       __cur_ = __next_.end();
0153       if (__cur_ == ranges::end(__parent_->__base_)) {
0154         __trailing_empty_ = true;
0155         __next_           = {__cur_, __cur_};
0156       } else {
0157         __next_ = __parent_->__find_next(__cur_);
0158       }
0159     } else {
0160       __trailing_empty_ = false;
0161     }
0162     return *this;
0163   }
0164
0165   _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) {
0166     auto __tmp = *this;
0167     ++*this;
0168     return __tmp;
0169   }
0170
0171   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) {
0172     return __x.__cur_ == __y.__cur_ && __x.__trailing_empty_ == __y.__trailing_empty_;
0173   }
0174 };
0175
0176 template <forward_range _View, forward_range _Pattern>
0177   requires view<_View> && view<_Pattern> &&
0178            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
0179 struct split_view<_View, _Pattern>::__sentinel {
0180 private:
0181   _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>();
0182
0183   _LIBCPP_HIDE_FROM_ABI static constexpr bool __equals(const __iterator& __x, const __sentinel& __y) {
0184     return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_;
0185   }
0186
0187 public:
0188   _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
0189
0190   _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(split_view<_View, _Pattern>& __parent)
0191       : __end_(ranges::end(__parent.__base_)) {}
0192
0193   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) {
0194     return __equals(__x, __y);
0195   }
0196 };
0197
0198 namespace views {
0199 namespace __split_view {
0200 struct __fn {
0201   // clang-format off
0202   template <class _Range, class _Pattern>
0203   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
0204   constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
0205     noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
0206     -> decltype(      split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))
0207     { return          split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); }
0208   // clang-format on
0209
0210   template <class _Pattern>
0211     requires constructible_from<decay_t<_Pattern>, _Pattern>
0212   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const
0213       noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
0214     return __pipeable(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
0215   }
0216 };
0217 } // namespace __split_view
0218
0219 inline namespace __cpo {
0220 inline constexpr auto split = __split_view::__fn{};
0221 } // namespace __cpo
0222 } // namespace views
0223
0224 } // namespace ranges
0225
0226 #endif // _LIBCPP_STD_VER >= 20
0227
0228 _LIBCPP_END_NAMESPACE_STD
0229
0230 _LIBCPP_POP_MACROS
0231
0232 #endif // _LIBCPP___RANGES_SPLIT_VIEW_H