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 
46 namespace ranges {
47 
48 template <forward_range _View, forward_range _Pattern>
49   requires view<_View> && view<_Pattern> &&
50            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
51 class split_view : public view_interface<split_view<_View, _Pattern>> {
52 private:
53   _LIBCPP_NO_UNIQUE_ADDRESS _View __base_       = _View();
54   _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
55   using _Cache                                  = __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 
76 public:
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(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 
115 template <class _Range, class _Pattern>
116 split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
117 
118 template <forward_range _Range>
119 split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
120 
121 template <forward_range _View, forward_range _Pattern>
122   requires view<_View> && view<_Pattern> &&
123            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
124 struct split_view<_View, _Pattern>::__iterator {
125 private:
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 
133 public:
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 
176 template <forward_range _View, forward_range _Pattern>
177   requires view<_View> && view<_Pattern> &&
178            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
179 struct split_view<_View, _Pattern>::__sentinel {
180 private:
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 
187 public:
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 
198 namespace views {
199 namespace __split_view {
200 struct __fn {
201   // clang-format off
202   template <class _Range, class _Pattern>
203   _LIBCPP_NODISCARD_EXT _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   _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const
213       noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
214     return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
215   }
216 };
217 } // namespace __split_view
218 
219 inline namespace __cpo {
220 inline 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