master
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_JOIN_WITH_VIEW_H
11#define _LIBCPP___RANGES_JOIN_WITH_VIEW_H
12
13#include <__concepts/common_reference_with.h>
14#include <__concepts/common_with.h>
15#include <__concepts/constructible.h>
16#include <__concepts/convertible_to.h>
17#include <__concepts/derived_from.h>
18#include <__concepts/equality_comparable.h>
19#include <__config>
20#include <__functional/bind_back.h>
21#include <__iterator/concepts.h>
22#include <__iterator/incrementable_traits.h>
23#include <__iterator/iter_move.h>
24#include <__iterator/iter_swap.h>
25#include <__iterator/iterator_traits.h>
26#include <__memory/addressof.h>
27#include <__ranges/access.h>
28#include <__ranges/all.h>
29#include <__ranges/concepts.h>
30#include <__ranges/non_propagating_cache.h>
31#include <__ranges/range_adaptor.h>
32#include <__ranges/single_view.h>
33#include <__ranges/view_interface.h>
34#include <__type_traits/conditional.h>
35#include <__type_traits/decay.h>
36#include <__type_traits/is_reference.h>
37#include <__type_traits/maybe_const.h>
38#include <__utility/as_const.h>
39#include <__utility/as_lvalue.h>
40#include <__utility/empty.h>
41#include <__utility/forward.h>
42#include <__utility/move.h>
43#include <variant>
44
45#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
46# pragma GCC system_header
47#endif
48
49_LIBCPP_PUSH_MACROS
50#include <__undef_macros>
51
52_LIBCPP_BEGIN_NAMESPACE_STD
53
54#if _LIBCPP_STD_VER >= 23
55
56namespace ranges {
57template <class _Range>
58concept __bidirectional_common = bidirectional_range<_Range> && common_range<_Range>;
59
60template <input_range _View, forward_range _Pattern>
61 requires view<_View> && input_range<range_reference_t<_View>> && view<_Pattern> &&
62 __concatable<range_reference_t<_View>, _Pattern>
63class join_with_view : public view_interface<join_with_view<_View, _Pattern>> {
64 using _InnerRng _LIBCPP_NODEBUG = range_reference_t<_View>;
65
66 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
67
68 static constexpr bool _UseOuterItCache = !forward_range<_View>;
69 using _OuterItCache _LIBCPP_NODEBUG =
70 _If<_UseOuterItCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
71 _LIBCPP_NO_UNIQUE_ADDRESS _OuterItCache __outer_it_;
72
73 static constexpr bool _UseInnerCache = !is_reference_v<_InnerRng>;
74 using _InnerCache _LIBCPP_NODEBUG =
75 _If<_UseInnerCache, __non_propagating_cache<remove_cvref_t<_InnerRng>>, __empty_cache>;
76 _LIBCPP_NO_UNIQUE_ADDRESS _InnerCache __inner_;
77
78 _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
79
80 template <bool _Const>
81 struct __iterator;
82
83 template <bool _Const>
84 struct __sentinel;
85
86public:
87 _LIBCPP_HIDE_FROM_ABI join_with_view()
88 requires default_initializable<_View> && default_initializable<_Pattern>
89 = default;
90
91 _LIBCPP_HIDE_FROM_ABI constexpr explicit join_with_view(_View __base, _Pattern __pattern)
92 : __base_(std::move(__base)), __pattern_(std::move(__pattern)) {}
93
94 template <input_range _Range>
95 requires constructible_from<_View, views::all_t<_Range>> &&
96 constructible_from<_Pattern, single_view<range_value_t<_InnerRng>>>
97 _LIBCPP_HIDE_FROM_ABI constexpr explicit join_with_view(_Range&& __r, range_value_t<_InnerRng> __e)
98 : __base_(views::all(std::forward<_Range>(__r))), __pattern_(views::single(std::move(__e))) {}
99
100 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
101 requires copy_constructible<_View>
102 {
103 return __base_;
104 }
105
106 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
107
108 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin() {
109 if constexpr (forward_range<_View>) {
110 constexpr bool __use_const = __simple_view<_View> && is_reference_v<_InnerRng> && __simple_view<_Pattern>;
111 return __iterator<__use_const>{*this, ranges::begin(__base_)};
112 } else {
113 __outer_it_.__emplace(ranges::begin(__base_));
114 return __iterator<false>{*this};
115 }
116 }
117
118 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
119 requires forward_range<const _View> && forward_range<const _Pattern> &&
120 is_reference_v<range_reference_t<const _View>> && input_range<range_reference_t<const _View>> &&
121 __concatable<range_reference_t<const _View>, const _Pattern>
122 {
123 return __iterator<true>{*this, ranges::begin(__base_)};
124 }
125
126 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
127 constexpr bool __use_const = __simple_view<_View> && __simple_view<_Pattern>;
128 if constexpr (forward_range<_View> && is_reference_v<_InnerRng> && forward_range<_InnerRng> &&
129 common_range<_View> && common_range<_InnerRng>)
130 return __iterator<__use_const>{*this, ranges::end(__base_)};
131 else
132 return __sentinel<__use_const>{*this};
133 }
134
135 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
136 requires forward_range<const _View> && forward_range<const _Pattern> &&
137 is_reference_v<range_reference_t<const _View>> && input_range<range_reference_t<const _View>> &&
138 __concatable<range_reference_t<const _View>, const _Pattern>
139 {
140 using _InnerConstRng = range_reference_t<const _View>;
141 if constexpr (forward_range<_InnerConstRng> && common_range<const _View> && common_range<_InnerConstRng>)
142 return __iterator<true>{*this, ranges::end(__base_)};
143 else
144 return __sentinel<true>{*this};
145 }
146};
147
148template <class _Range, class _Pattern>
149join_with_view(_Range&&, _Pattern&&) -> join_with_view<views::all_t<_Range>, views::all_t<_Pattern>>;
150
151template <input_range _Range>
152join_with_view(_Range&&, range_value_t<range_reference_t<_Range>>)
153 -> join_with_view<views::all_t<_Range>, single_view<range_value_t<range_reference_t<_Range>>>>;
154
155template <class _Base, class _PatternBase, class _InnerBase = range_reference_t<_Base>>
156struct __join_with_view_iterator_category {};
157
158template <class _Base, class _PatternBase, class _InnerBase>
159 requires is_reference_v<_InnerBase> && forward_range<_Base> && forward_range<_InnerBase>
160struct __join_with_view_iterator_category<_Base, _PatternBase, _InnerBase> {
161private:
162 static consteval auto __get_iterator_category() noexcept {
163 using _OuterC = iterator_traits<iterator_t<_Base>>::iterator_category;
164 using _InnerC = iterator_traits<iterator_t<_InnerBase>>::iterator_category;
165 using _PatternC = iterator_traits<iterator_t<_PatternBase>>::iterator_category;
166
167 if constexpr (!is_reference_v<common_reference_t<iter_reference_t<iterator_t<_InnerBase>>,
168 iter_reference_t<iterator_t<_PatternBase>>>>)
169 return input_iterator_tag{};
170 else if constexpr (derived_from<_OuterC, bidirectional_iterator_tag> &&
171 derived_from<_InnerC, bidirectional_iterator_tag> &&
172 derived_from<_PatternC, bidirectional_iterator_tag> && common_range<_InnerBase> &&
173 common_range<_PatternBase>)
174 return bidirectional_iterator_tag{};
175 else if constexpr (derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag> &&
176 derived_from<_PatternC, forward_iterator_tag>)
177 return forward_iterator_tag{};
178 else
179 return input_iterator_tag{};
180 }
181
182public:
183 using iterator_category = decltype(__get_iterator_category());
184};
185
186template <input_range _View, forward_range _Pattern>
187 requires view<_View> && input_range<range_reference_t<_View>> && view<_Pattern> &&
188 __concatable<range_reference_t<_View>, _Pattern>
189template <bool _Const>
190struct join_with_view<_View, _Pattern>::__iterator
191 : public __join_with_view_iterator_category<__maybe_const<_Const, _View>, __maybe_const<_Const, _Pattern>> {
192private:
193 friend join_with_view;
194
195 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, join_with_view>;
196 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>;
197 using _InnerBase _LIBCPP_NODEBUG = range_reference_t<_Base>;
198 using _PatternBase _LIBCPP_NODEBUG = __maybe_const<_Const, _Pattern>;
199
200 using _OuterIter _LIBCPP_NODEBUG = iterator_t<_Base>;
201 using _InnerIter _LIBCPP_NODEBUG = iterator_t<_InnerBase>;
202 using _PatternIter _LIBCPP_NODEBUG = iterator_t<_PatternBase>;
203
204 static_assert(!_Const || forward_range<_Base>, "Const can only be true when Base models forward_range.");
205
206 static constexpr bool __ref_is_glvalue = is_reference_v<_InnerBase>;
207
208 _Parent* __parent_ = nullptr;
209
210 static constexpr bool _OuterIterPresent = forward_range<_Base>;
211 using _OuterIterType _LIBCPP_NODEBUG = _If<_OuterIterPresent, _OuterIter, std::__empty>;
212 _LIBCPP_NO_UNIQUE_ADDRESS _OuterIterType __outer_it_ = _OuterIterType();
213
214 variant<_PatternIter, _InnerIter> __inner_it_;
215
216 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent& __parent, _OuterIter __outer)
217 requires forward_range<_Base>
218 : __parent_(std::addressof(__parent)), __outer_it_(std::move(__outer)) {
219 if (__get_outer() != ranges::end(__parent_->__base_)) {
220 __inner_it_.template emplace<1>(ranges::begin(__update_inner()));
221 __satisfy();
222 }
223 }
224
225 _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(_Parent& __parent)
226 requires(!forward_range<_Base>)
227 : __parent_(std::addressof(__parent)) {
228 if (__get_outer() != ranges::end(__parent_->__base_)) {
229 __inner_it_.template emplace<1>(ranges::begin(__update_inner()));
230 __satisfy();
231 }
232 }
233
234 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _OuterIter& __get_outer() {
235 if constexpr (forward_range<_Base>)
236 return __outer_it_;
237 else
238 return *__parent_->__outer_it_;
239 }
240
241 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr const _OuterIter& __get_outer() const {
242 if constexpr (forward_range<_Base>)
243 return __outer_it_;
244 else
245 return *__parent_->__outer_it_;
246 }
247
248 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto& __update_inner() {
249 if constexpr (__ref_is_glvalue)
250 return std::__as_lvalue(*__get_outer());
251 else
252 return __parent_->__inner_.__emplace_from([this]() -> decltype(auto) { return *__get_outer(); });
253 }
254
255 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto& __get_inner() {
256 if constexpr (__ref_is_glvalue)
257 return std::__as_lvalue(*__get_outer());
258 else
259 return *__parent_->__inner_;
260 }
261
262 _LIBCPP_HIDE_FROM_ABI constexpr void __satisfy() {
263 while (true) {
264 if (__inner_it_.index() == 0) {
265 if (std::get<0>(__inner_it_) != ranges::end(__parent_->__pattern_))
266 break;
267
268 __inner_it_.template emplace<1>(ranges::begin(__update_inner()));
269 } else {
270 if (std::get<1>(__inner_it_) != ranges::end(__get_inner()))
271 break;
272
273 if (++__get_outer() == ranges::end(__parent_->__base_)) {
274 if constexpr (__ref_is_glvalue)
275 __inner_it_.template emplace<0>();
276
277 break;
278 }
279
280 __inner_it_.template emplace<0>(ranges::begin(__parent_->__pattern_));
281 }
282 }
283 }
284
285 [[nodiscard]] static consteval auto __get_iterator_concept() noexcept {
286 if constexpr (__ref_is_glvalue && bidirectional_range<_Base> && __bidirectional_common<_InnerBase> &&
287 __bidirectional_common<_PatternBase>)
288 return bidirectional_iterator_tag{};
289 else if constexpr (__ref_is_glvalue && forward_range<_Base> && forward_range<_InnerBase>)
290 return forward_iterator_tag{};
291 else
292 return input_iterator_tag{};
293 }
294
295public:
296 using iterator_concept = decltype(__get_iterator_concept());
297 using value_type = common_type_t<iter_value_t<_InnerIter>, iter_value_t<_PatternIter>>;
298 using difference_type =
299 common_type_t<iter_difference_t<_OuterIter>, iter_difference_t<_InnerIter>, iter_difference_t<_PatternIter>>;
300
301 _LIBCPP_HIDE_FROM_ABI __iterator() = default;
302
303 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i)
304 requires _Const && convertible_to<iterator_t<_View>, _OuterIter> &&
305 convertible_to<iterator_t<_InnerRng>, _InnerIter> && convertible_to<iterator_t<_Pattern>, _PatternIter>
306 : __parent_(__i.__parent_), __outer_it_(std::move(__i.__outer_it_)) {
307 if (__i.__inner_it_.index() == 0) {
308 __inner_it_.template emplace<0>(std::get<0>(std::move(__i.__inner_it_)));
309 } else {
310 __inner_it_.template emplace<1>(std::get<1>(std::move(__i.__inner_it_)));
311 }
312 }
313
314 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const {
315 using __reference = common_reference_t<iter_reference_t<_InnerIter>, iter_reference_t<_PatternIter>>;
316 return std::visit([](auto& __it) -> __reference { return *__it; }, __inner_it_);
317 }
318
319 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
320 std::visit([](auto& __it) { ++__it; }, __inner_it_);
321 __satisfy();
322 return *this;
323 }
324
325 _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; }
326
327 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)
328 requires __ref_is_glvalue && forward_iterator<_OuterIter> && forward_iterator<_InnerIter>
329 {
330 __iterator __tmp = *this;
331 ++*this;
332 return __tmp;
333 }
334
335 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()
336 requires __ref_is_glvalue
337 && bidirectional_range<_Base> && __bidirectional_common<_InnerBase> && __bidirectional_common<_PatternBase>
338 {
339 if (__outer_it_ == ranges::end(__parent_->__base_)) {
340 auto&& __inner = *--__outer_it_;
341 __inner_it_.template emplace<1>(ranges::end(__inner));
342 }
343
344 while (true) {
345 if (__inner_it_.index() == 0) {
346 auto& __it = std::get<0>(__inner_it_);
347 if (__it == ranges::begin(__parent_->__pattern_)) {
348 auto&& __inner = *--__outer_it_;
349 __inner_it_.template emplace<1>(ranges::end(__inner));
350 } else
351 break;
352 } else {
353 auto& __it = std::get<1>(__inner_it_);
354 auto&& __inner = *__outer_it_;
355 if (__it == ranges::begin(__inner))
356 __inner_it_.template emplace<0>(ranges::end(__parent_->__pattern_));
357 else
358 break;
359 }
360 }
361
362 std::visit([](auto& __it) { --__it; }, __inner_it_);
363 return *this;
364 }
365
366 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)
367 requires __ref_is_glvalue
368 && bidirectional_range<_Base> && __bidirectional_common<_InnerBase> && __bidirectional_common<_PatternBase>
369 {
370 __iterator __tmp = *this;
371 --*this;
372 return __tmp;
373 }
374
375 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
376 requires __ref_is_glvalue && forward_range<_Base> && equality_comparable<_InnerIter>
377 {
378 return __x.__outer_it_ == __y.__outer_it_ && __x.__inner_it_ == __y.__inner_it_;
379 }
380
381 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto) iter_move(const __iterator& __x) {
382 using __rvalue_reference =
383 common_reference_t<iter_rvalue_reference_t<_InnerIter>, iter_rvalue_reference_t<_PatternIter>>;
384 return std::visit<__rvalue_reference>(ranges::iter_move, __x.__inner_it_);
385 }
386
387 _LIBCPP_HIDE_FROM_ABI friend constexpr void iter_swap(const __iterator& __x, const __iterator& __y)
388 requires indirectly_swappable<_InnerIter, _PatternIter>
389 {
390 std::visit(ranges::iter_swap, __x.__inner_it_, __y.__inner_it_);
391 }
392};
393
394template <input_range _View, forward_range _Pattern>
395 requires view<_View> && input_range<range_reference_t<_View>> && view<_Pattern> &&
396 __concatable<range_reference_t<_View>, _Pattern>
397template <bool _Const>
398struct join_with_view<_View, _Pattern>::__sentinel {
399private:
400 friend join_with_view;
401
402 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, join_with_view>;
403 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>;
404
405 _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_Base> __end_ = sentinel_t<_Base>();
406
407 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {}
408
409 template <bool _OtherConst>
410 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto& __get_outer_of(const __iterator<_OtherConst>& __x) {
411 return __x.__get_outer();
412 }
413
414public:
415 _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
416
417 _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __s)
418 requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
419 : __end_(std::move(__s.__end_)) {}
420
421 template <bool _OtherConst>
422 requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
423 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr bool
424 operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
425 return __get_outer_of(__x) == __y.__end_;
426 }
427};
428
429namespace views {
430namespace __join_with_view {
431struct __fn {
432 template <class _Range, class _Pattern>
433 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
434 noexcept(noexcept(/**/ join_with_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
435 -> decltype(/*--*/ join_with_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))) {
436 return /*-------------*/ join_with_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern));
437 }
438
439 template <class _Pattern>
440 requires constructible_from<decay_t<_Pattern>, _Pattern>
441 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const
442 noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
443 return __pipeable(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
444 }
445};
446} // namespace __join_with_view
447
448inline namespace __cpo {
449inline constexpr auto join_with = __join_with_view::__fn{};
450} // namespace __cpo
451} // namespace views
452} // namespace ranges
453
454#endif // _LIBCPP_STD_VER >= 23
455
456_LIBCPP_END_NAMESPACE_STD
457
458_LIBCPP_POP_MACROS
459
460#endif // _LIBCPP___RANGES_JOIN_WITH_VIEW_H