1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___RANGES_SPLIT_VIEW_H
11#define _LIBCPP___RANGES_SPLIT_VIEW_H
12
13#include <__algorithm/ranges_search.h>
14#include <__concepts/constructible.h>
15#include <__config>
16#include <__functional/bind_back.h>
17#include <__functional/ranges_operations.h>
18#include <__iterator/indirectly_comparable.h>
19#include <__iterator/iterator_traits.h>
20#include <__memory/addressof.h>
21#include <__ranges/access.h>
22#include <__ranges/all.h>
23#include <__ranges/concepts.h>
24#include <__ranges/empty.h>
25#include <__ranges/non_propagating_cache.h>
26#include <__ranges/range_adaptor.h>
27#include <__ranges/single_view.h>
28#include <__ranges/subrange.h>
29#include <__ranges/view_interface.h>
30#include <__type_traits/decay.h>
31#include <__type_traits/is_nothrow_constructible.h>
32#include <__utility/forward.h>
33#include <__utility/move.h>
34
35#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
36# pragma GCC system_header
37#endif
38
39_LIBCPP_PUSH_MACROS
40#include <__undef_macros>
41
42_LIBCPP_BEGIN_NAMESPACE_STD
43
44#if _LIBCPP_STD_VER >= 20
45
46namespace ranges {
47
48template <forward_range _View, forward_range _Pattern>
49 requires view<_View> && view<_Pattern> &&
50 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
51class split_view : public view_interface<split_view<_View, _Pattern>> {
52private:
53 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
54 _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
55 using _Cache _LIBCPP_NODEBUG = __non_propagating_cache<subrange<iterator_t<_View>>>;
56 _Cache __cached_begin_ = _Cache();
57
58 template <class, class>
59 friend struct __iterator;
60
61 template <class, class>
62 friend struct __sentinel;
63
64 struct __iterator;
65 struct __sentinel;
66
67 _LIBCPP_HIDE_FROM_ABI constexpr subrange<iterator_t<_View>> __find_next(iterator_t<_View> __it) {
68 auto [__begin, __end] = ranges::search(subrange(__it, ranges::end(__base_)), __pattern_);
69 if (__begin != ranges::end(__base_) && ranges::empty(__pattern_)) {
70 ++__begin;
71 ++__end;
72 }
73 return {__begin, __end};
74 }
75
76public:
77 _LIBCPP_HIDE_FROM_ABI split_view()
78 requires default_initializable<_View> && default_initializable<_Pattern>
79 = default;
80
81 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 split_view(_View __base, _Pattern __pattern)
82 : __base_(std::move(__base)), __pattern_(std::move((__pattern))) {}
83
84 template <forward_range _Range>
85 requires constructible_from<_View, views::all_t<_Range>> &&
86 constructible_from<_Pattern, single_view<range_value_t<_Range>>>
87 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23
88 split_view(_Range&& __range, range_value_t<_Range> __elem)
89 : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {}
90
91 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
92 requires copy_constructible<_View>
93 {
94 return __base_;
95 }
96
97 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
98
99 _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() {
100 if (!__cached_begin_.__has_value()) {
101 __cached_begin_.__emplace(__find_next(it: ranges::begin(__base_)));
102 }
103 return {*this, ranges::begin(__base_), *__cached_begin_};
104 }
105
106 _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
107 if constexpr (common_range<_View>) {
108 return __iterator{*this, ranges::end(__base_), {}};
109 } else {
110 return __sentinel{*this};
111 }
112 }
113};
114
115template <class _Range, class _Pattern>
116split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
117
118template <forward_range _Range>
119split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
120
121template <forward_range _View, forward_range _Pattern>
122 requires view<_View> && view<_Pattern> &&
123 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
124struct split_view<_View, _Pattern>::__iterator {
125private:
126 split_view* __parent_ = nullptr;
127 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_ = iterator_t<_View>();
128 _LIBCPP_NO_UNIQUE_ADDRESS subrange<iterator_t<_View>> __next_ = subrange<iterator_t<_View>>();
129 bool __trailing_empty_ = false;
130
131 friend struct __sentinel;
132
133public:
134 using iterator_concept = forward_iterator_tag;
135 using iterator_category = input_iterator_tag;
136 using value_type = subrange<iterator_t<_View>>;
137 using difference_type = range_difference_t<_View>;
138
139 _LIBCPP_HIDE_FROM_ABI __iterator() = default;
140
141 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(
142 split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange<iterator_t<_View>> __next)
143 : __parent_(std::addressof(__parent)), __cur_(std::move(__current)), __next_(std::move(__next)) {}
144
145 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; }
146
147 _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; }
148
149 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
150 __cur_ = __next_.begin();
151 if (__cur_ != ranges::end(__parent_->__base_)) {
152 __cur_ = __next_.end();
153 if (__cur_ == ranges::end(__parent_->__base_)) {
154 __trailing_empty_ = true;
155 __next_ = {__cur_, __cur_};
156 } else {
157 __next_ = __parent_->__find_next(__cur_);
158 }
159 } else {
160 __trailing_empty_ = false;
161 }
162 return *this;
163 }
164
165 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) {
166 auto __tmp = *this;
167 ++*this;
168 return __tmp;
169 }
170
171 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) {
172 return __x.__cur_ == __y.__cur_ && __x.__trailing_empty_ == __y.__trailing_empty_;
173 }
174};
175
176template <forward_range _View, forward_range _Pattern>
177 requires view<_View> && view<_Pattern> &&
178 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
179struct split_view<_View, _Pattern>::__sentinel {
180private:
181 _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>();
182
183 _LIBCPP_HIDE_FROM_ABI static constexpr bool __equals(const __iterator& __x, const __sentinel& __y) {
184 return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_;
185 }
186
187public:
188 _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
189
190 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(split_view<_View, _Pattern>& __parent)
191 : __end_(ranges::end(__parent.__base_)) {}
192
193 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) {
194 return __equals(__x, __y);
195 }
196};
197
198namespace views {
199namespace __split_view {
200struct __fn {
201 // clang-format off
202 template <class _Range, class _Pattern>
203 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
204 constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
205 noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
206 -> decltype( split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))
207 { return split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); }
208 // clang-format on
209
210 template <class _Pattern>
211 requires constructible_from<decay_t<_Pattern>, _Pattern>
212 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const
213 noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
214 return __pipeable(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
215 }
216};
217} // namespace __split_view
218
219inline namespace __cpo {
220inline constexpr auto split = __split_view::__fn{};
221} // namespace __cpo
222} // namespace views
223
224} // namespace ranges
225
226#endif // _LIBCPP_STD_VER >= 20
227
228_LIBCPP_END_NAMESPACE_STD
229
230_LIBCPP_POP_MACROS
231
232#endif // _LIBCPP___RANGES_SPLIT_VIEW_H
233