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_BEGIN_NAMESPACE_STD
40 
41 #if _LIBCPP_STD_VER >= 20
42 
43 namespace ranges {
44 
45 template <forward_range _View, forward_range _Pattern>
46   requires view<_View> && view<_Pattern> &&
47            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
48 class split_view : public view_interface<split_view<_View, _Pattern>> {
49 private:
50   _LIBCPP_NO_UNIQUE_ADDRESS _View __base_       = _View();
51   _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
52   using _Cache                                  = __non_propagating_cache<subrange<iterator_t<_View>>>;
53   _Cache __cached_begin_                        = _Cache();
54 
55   template <class, class>
56   friend struct __iterator;
57 
58   template <class, class>
59   friend struct __sentinel;
60 
61   struct __iterator;
62   struct __sentinel;
63 
64   _LIBCPP_HIDE_FROM_ABI constexpr subrange<iterator_t<_View>> __find_next(iterator_t<_View> __it) {
65     auto [__begin, __end] = ranges::search(subrange(__it, ranges::end(__base_)), __pattern_);
66     if (__begin != ranges::end(__base_) && ranges::empty(__pattern_)) {
67       ++__begin;
68       ++__end;
69     }
70     return {__begin, __end};
71   }
72 
73 public:
74   _LIBCPP_HIDE_FROM_ABI split_view()
75     requires default_initializable<_View> && default_initializable<_Pattern>
76   = default;
77 
78   _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 split_view(_View __base, _Pattern __pattern)
79       : __base_(std::move(__base)), __pattern_(std::move((__pattern))) {}
80 
81   template <forward_range _Range>
82     requires constructible_from<_View, views::all_t<_Range>> &&
83                  constructible_from<_Pattern, single_view<range_value_t<_Range>>>
84   _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23
85   split_view(_Range&& __range, range_value_t<_Range> __elem)
86       : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {}
87 
88   _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
89     requires copy_constructible<_View>
90   {
91     return __base_;
92   }
93 
94   _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
95 
96   _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() {
97     if (!__cached_begin_.__has_value()) {
98       __cached_begin_.__emplace(__find_next(ranges::begin(__base_)));
99     }
100     return {*this, ranges::begin(__base_), *__cached_begin_};
101   }
102 
103   _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
104     if constexpr (common_range<_View>) {
105       return __iterator{*this, ranges::end(__base_), {}};
106     } else {
107       return __sentinel{*this};
108     }
109   }
110 };
111 
112 template <class _Range, class _Pattern>
113 split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
114 
115 template <forward_range _Range>
116 split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
117 
118 template <forward_range _View, forward_range _Pattern>
119   requires view<_View> && view<_Pattern> &&
120            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
121 struct split_view<_View, _Pattern>::__iterator {
122 private:
123   split_view* __parent_                                         = nullptr;
124   _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_            = iterator_t<_View>();
125   _LIBCPP_NO_UNIQUE_ADDRESS subrange<iterator_t<_View>> __next_ = subrange<iterator_t<_View>>();
126   bool __trailing_empty_                                        = false;
127 
128   friend struct __sentinel;
129 
130 public:
131   using iterator_concept  = forward_iterator_tag;
132   using iterator_category = input_iterator_tag;
133   using value_type        = subrange<iterator_t<_View>>;
134   using difference_type   = range_difference_t<_View>;
135 
136   _LIBCPP_HIDE_FROM_ABI __iterator() = default;
137 
138   _LIBCPP_HIDE_FROM_ABI constexpr __iterator(
139       split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange<iterator_t<_View>> __next)
140       : __parent_(std::addressof(__parent)), __cur_(std::move(__current)), __next_(std::move(__next)) {}
141 
142   _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; }
143 
144   _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; }
145 
146   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
147     __cur_ = __next_.begin();
148     if (__cur_ != ranges::end(__parent_->__base_)) {
149       __cur_ = __next_.end();
150       if (__cur_ == ranges::end(__parent_->__base_)) {
151         __trailing_empty_ = true;
152         __next_           = {__cur_, __cur_};
153       } else {
154         __next_ = __parent_->__find_next(__cur_);
155       }
156     } else {
157       __trailing_empty_ = false;
158     }
159     return *this;
160   }
161 
162   _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) {
163     auto __tmp = *this;
164     ++*this;
165     return __tmp;
166   }
167 
168   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) {
169     return __x.__cur_ == __y.__cur_ && __x.__trailing_empty_ == __y.__trailing_empty_;
170   }
171 };
172 
173 template <forward_range _View, forward_range _Pattern>
174   requires view<_View> && view<_Pattern> &&
175            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
176 struct split_view<_View, _Pattern>::__sentinel {
177 private:
178   _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>();
179 
180   _LIBCPP_HIDE_FROM_ABI static constexpr bool __equals(const __iterator& __x, const __sentinel& __y) {
181     return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_;
182   }
183 
184 public:
185   _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
186 
187   _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(split_view<_View, _Pattern>& __parent)
188       : __end_(ranges::end(__parent.__base_)) {}
189 
190   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) {
191     return __equals(__x, __y);
192   }
193 };
194 
195 namespace views {
196 namespace __split_view {
197 struct __fn : __range_adaptor_closure<__fn> {
198   // clang-format off
199   template <class _Range, class _Pattern>
200   _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI
201   constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
202     noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
203     -> decltype(      split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))
204     { return          split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); }
205   // clang-format on
206 
207   template <class _Pattern>
208     requires constructible_from<decay_t<_Pattern>, _Pattern>
209   _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const
210       noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
211     return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
212   }
213 };
214 } // namespace __split_view
215 
216 inline namespace __cpo {
217 inline constexpr auto split = __split_view::__fn{};
218 } // namespace __cpo
219 } // namespace views
220 
221 } // namespace ranges
222 
223 #endif // _LIBCPP_STD_VER >= 20
224 
225 _LIBCPP_END_NAMESPACE_STD
226 
227 #endif // _LIBCPP___RANGES_SPLIT_VIEW_H
228