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 #ifndef _LIBCPP___RANGES_ZIP_VIEW_H
10 #define _LIBCPP___RANGES_ZIP_VIEW_H
11
12 #include <__config>
13
14 #include <__algorithm/ranges_min.h>
15 #include <__compare/three_way_comparable.h>
16 #include <__concepts/convertible_to.h>
17 #include <__concepts/equality_comparable.h>
18 #include <__functional/invoke.h>
19 #include <__functional/operations.h>
20 #include <__iterator/concepts.h>
21 #include <__iterator/incrementable_traits.h>
22 #include <__iterator/iter_move.h>
23 #include <__iterator/iter_swap.h>
24 #include <__iterator/iterator_traits.h>
25 #include <__ranges/access.h>
26 #include <__ranges/all.h>
27 #include <__ranges/concepts.h>
28 #include <__ranges/empty_view.h>
29 #include <__ranges/enable_borrowed_range.h>
30 #include <__ranges/size.h>
31 #include <__ranges/view_interface.h>
32 #include <__utility/forward.h>
33 #include <__utility/integer_sequence.h>
34 #include <__utility/move.h>
35 #include <tuple>
36 #include <type_traits>
37
38 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
39 # pragma GCC system_header
40 #endif
41
42 _LIBCPP_PUSH_MACROS
43 #include <__undef_macros>
44
45 _LIBCPP_BEGIN_NAMESPACE_STD
46
47 #if _LIBCPP_STD_VER > 20 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
48
49 namespace ranges {
50
51 template <class... _Ranges>
52 concept __zip_is_common = (sizeof...(_Ranges) == 1 && (common_range<_Ranges> && ...)) ||
53 (!(bidirectional_range<_Ranges> && ...) && (common_range<_Ranges> && ...)) ||
54 ((random_access_range<_Ranges> && ...) && (sized_range<_Ranges> && ...));
55
56 template <typename _Tp, typename _Up>
57 auto __tuple_or_pair_test() -> pair<_Tp, _Up>;
58
59 template <typename... _Types>
60 requires(sizeof...(_Types) != 2)
61 auto __tuple_or_pair_test() -> tuple<_Types...>;
62
63 template <class... _Types>
64 using __tuple_or_pair = decltype(__tuple_or_pair_test<_Types...>());
65
66 template <class _Fun, class _Tuple>
__tuple_transform(_Fun && __f,_Tuple && __tuple)67 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_transform(_Fun&& __f, _Tuple&& __tuple) {
68 return std::apply(
69 [&]<class... _Types>(_Types&&... __elements) {
70 return __tuple_or_pair<invoke_result_t<_Fun&, _Types>...>(
71 std::invoke(__f, std::forward<_Types>(__elements))...);
72 },
73 std::forward<_Tuple>(__tuple));
74 }
75
76 template <class _Fun, class _Tuple>
__tuple_for_each(_Fun && __f,_Tuple && __tuple)77 _LIBCPP_HIDE_FROM_ABI constexpr void __tuple_for_each(_Fun&& __f, _Tuple&& __tuple) {
78 std::apply(
79 [&]<class... _Types>(_Types&&... __elements) { (std::invoke(__f, std::forward<_Types>(__elements)), ...); },
80 std::forward<_Tuple>(__tuple));
81 }
82
83 template <class _Fun, class _Tuple1, class _Tuple2, size_t... _Indices>
84 _LIBCPP_HIDE_FROM_ABI constexpr __tuple_or_pair<
85 invoke_result_t<_Fun&, typename tuple_element<_Indices, remove_cvref_t<_Tuple1>>::type,
86 typename tuple_element<_Indices, remove_cvref_t<_Tuple2>>::type>...>
__tuple_zip_transform(_Fun && __f,_Tuple1 && __tuple1,_Tuple2 && __tuple2,index_sequence<_Indices...>)87 __tuple_zip_transform(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2, index_sequence<_Indices...>) {
88 return {std::invoke(__f, std::get<_Indices>(std::forward<_Tuple1>(__tuple1)),
89 std::get<_Indices>(std::forward<_Tuple2>(__tuple2)))...};
90 }
91
92 template <class _Fun, class _Tuple1, class _Tuple2>
__tuple_zip_transform(_Fun && __f,_Tuple1 && __tuple1,_Tuple2 && __tuple2)93 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_zip_transform(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2) {
94 return ranges::__tuple_zip_transform(__f, std::forward<_Tuple1>(__tuple1), std::forward<_Tuple2>(__tuple2),
95 std::make_index_sequence<tuple_size<remove_cvref_t<_Tuple1>>::value>());
96 }
97
98 template <class _Fun, class _Tuple1, class _Tuple2, size_t... _Indices>
__tuple_zip_for_each(_Fun && __f,_Tuple1 && __tuple1,_Tuple2 && __tuple2,index_sequence<_Indices...>)99 _LIBCPP_HIDE_FROM_ABI constexpr void __tuple_zip_for_each(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2,
100 index_sequence<_Indices...>) {
101 (std::invoke(__f, std::get<_Indices>(std::forward<_Tuple1>(__tuple1)),
102 std::get<_Indices>(std::forward<_Tuple2>(__tuple2))),
103 ...);
104 }
105
106 template <class _Fun, class _Tuple1, class _Tuple2>
__tuple_zip_for_each(_Fun && __f,_Tuple1 && __tuple1,_Tuple2 && __tuple2)107 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_zip_for_each(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2) {
108 return ranges::__tuple_zip_for_each(__f, std::forward<_Tuple1>(__tuple1), std::forward<_Tuple2>(__tuple2),
109 std::make_index_sequence<tuple_size<remove_cvref_t<_Tuple1>>::value>());
110 }
111
112 template <class _Tuple1, class _Tuple2>
__tuple_any_equals(const _Tuple1 & __tuple1,const _Tuple2 & __tuple2)113 _LIBCPP_HIDE_FROM_ABI constexpr bool __tuple_any_equals(const _Tuple1& __tuple1, const _Tuple2& __tuple2) {
114 const auto __equals = ranges::__tuple_zip_transform(std::equal_to<>(), __tuple1, __tuple2);
115 return std::apply([](auto... __bools) { return (__bools || ...); }, __equals);
116 }
117
118 // abs in cstdlib is not constexpr
119 // TODO : remove __abs once P0533R9 is implemented.
120 template <class _Tp>
__abs(_Tp __t)121 _LIBCPP_HIDE_FROM_ABI constexpr _Tp __abs(_Tp __t) {
122 return __t < 0 ? -__t : __t;
123 }
124
125 template <input_range... _Views>
requires(view<_Views> &&...)126 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
127 class zip_view : public view_interface<zip_view<_Views...>> {
128
129 _LIBCPP_NO_UNIQUE_ADDRESS tuple<_Views...> __views_;
130
131 template <bool>
132 class __iterator;
133
134 template <bool>
135 class __sentinel;
136
137 public:
138 _LIBCPP_HIDE_FROM_ABI
139 zip_view() = default;
140
141 _LIBCPP_HIDE_FROM_ABI
142 constexpr explicit zip_view(_Views... __views) : __views_(std::move(__views)...) {}
143
144 _LIBCPP_HIDE_FROM_ABI
145 constexpr auto begin()
146 requires(!(__simple_view<_Views> && ...)) {
147 return __iterator<false>(ranges::__tuple_transform(ranges::begin, __views_));
148 }
149
150 _LIBCPP_HIDE_FROM_ABI
151 constexpr auto begin() const
152 requires(range<const _Views> && ...) {
153 return __iterator<true>(ranges::__tuple_transform(ranges::begin, __views_));
154 }
155
156 _LIBCPP_HIDE_FROM_ABI
157 constexpr auto end()
158 requires(!(__simple_view<_Views> && ...)) {
159 if constexpr (!__zip_is_common<_Views...>) {
160 return __sentinel<false>(ranges::__tuple_transform(ranges::end, __views_));
161 } else if constexpr ((random_access_range<_Views> && ...)) {
162 return begin() + iter_difference_t<__iterator<false>>(size());
163 } else {
164 return __iterator<false>(ranges::__tuple_transform(ranges::end, __views_));
165 }
166 }
167
168 _LIBCPP_HIDE_FROM_ABI
169 constexpr auto end() const
170 requires(range<const _Views> && ...) {
171 if constexpr (!__zip_is_common<const _Views...>) {
172 return __sentinel<true>(ranges::__tuple_transform(ranges::end, __views_));
173 } else if constexpr ((random_access_range<const _Views> && ...)) {
174 return begin() + iter_difference_t<__iterator<true>>(size());
175 } else {
176 return __iterator<true>(ranges::__tuple_transform(ranges::end, __views_));
177 }
178 }
179
180 _LIBCPP_HIDE_FROM_ABI
181 constexpr auto size()
182 requires(sized_range<_Views> && ...) {
183 return std::apply(
184 [](auto... __sizes) {
185 using _CT = make_unsigned_t<common_type_t<decltype(__sizes)...>>;
186 return ranges::min({_CT(__sizes)...});
187 },
188 ranges::__tuple_transform(ranges::size, __views_));
189 }
190
191 _LIBCPP_HIDE_FROM_ABI
192 constexpr auto size() const
193 requires(sized_range<const _Views> && ...) {
194 return std::apply(
195 [](auto... __sizes) {
196 using _CT = make_unsigned_t<common_type_t<decltype(__sizes)...>>;
197 return ranges::min({_CT(__sizes)...});
198 },
199 ranges::__tuple_transform(ranges::size, __views_));
200 }
201 };
202
203 template <class... _Ranges>
204 zip_view(_Ranges&&...) -> zip_view<views::all_t<_Ranges>...>;
205
206 template <bool _Const, class... _Views>
207 concept __zip_all_random_access = (random_access_range<__maybe_const<_Const, _Views>> && ...);
208
209 template <bool _Const, class... _Views>
210 concept __zip_all_bidirectional = (bidirectional_range<__maybe_const<_Const, _Views>> && ...);
211
212 template <bool _Const, class... _Views>
213 concept __zip_all_forward = (forward_range<__maybe_const<_Const, _Views>> && ...);
214
215 template <bool _Const, class... _Views>
__get_zip_view_iterator_tag()216 consteval auto __get_zip_view_iterator_tag() {
217 if constexpr (__zip_all_random_access<_Const, _Views...>) {
218 return random_access_iterator_tag();
219 } else if constexpr (__zip_all_bidirectional<_Const, _Views...>) {
220 return bidirectional_iterator_tag();
221 } else if constexpr (__zip_all_forward<_Const, _Views...>) {
222 return forward_iterator_tag();
223 } else {
224 return input_iterator_tag();
225 }
226 }
227
228 template <bool _Const, class... _Views>
229 struct __zip_view_iterator_category_base {};
230
231 template <bool _Const, class... _Views>
232 requires __zip_all_forward<_Const, _Views...>
233 struct __zip_view_iterator_category_base<_Const, _Views...> {
234 using iterator_category = input_iterator_tag;
235 };
236
237 template <input_range... _Views>
238 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
239 template <bool _Const>
240 class zip_view<_Views...>::__iterator : public __zip_view_iterator_category_base<_Const, _Views...> {
241
242 __tuple_or_pair<iterator_t<__maybe_const<_Const, _Views>>...> __current_;
243
244 _LIBCPP_HIDE_FROM_ABI
245 constexpr explicit __iterator(__tuple_or_pair<iterator_t<__maybe_const<_Const, _Views>>...> __current)
246 : __current_(std::move(__current)) {}
247
248 template <bool>
249 friend class zip_view<_Views...>::__iterator;
250
251 template <bool>
252 friend class zip_view<_Views...>::__sentinel;
253
254 friend class zip_view<_Views...>;
255
256 public:
257 using iterator_concept = decltype(__get_zip_view_iterator_tag<_Const, _Views...>());
258 using value_type = __tuple_or_pair<range_value_t<__maybe_const<_Const, _Views>>...>;
259 using difference_type = common_type_t<range_difference_t<__maybe_const<_Const, _Views>>...>;
260
261 _LIBCPP_HIDE_FROM_ABI
262 __iterator() = default;
263
264 _LIBCPP_HIDE_FROM_ABI
265 constexpr __iterator(__iterator<!_Const> __i)
266 requires _Const && (convertible_to<iterator_t<_Views>, iterator_t<__maybe_const<_Const, _Views>>> && ...)
267 : __current_(std::move(__i.__current_)) {}
268
269 _LIBCPP_HIDE_FROM_ABI
270 constexpr auto operator*() const {
271 return ranges::__tuple_transform([](auto& __i) -> decltype(auto) { return *__i; }, __current_);
272 }
273
274 _LIBCPP_HIDE_FROM_ABI
275 constexpr __iterator& operator++() {
276 ranges::__tuple_for_each([](auto& __i) { ++__i; }, __current_);
277 return *this;
278 }
279
280 _LIBCPP_HIDE_FROM_ABI
281 constexpr void operator++(int) { ++*this; }
282
283 _LIBCPP_HIDE_FROM_ABI
284 constexpr __iterator operator++(int)
285 requires __zip_all_forward<_Const, _Views...> {
286 auto __tmp = *this;
287 ++*this;
288 return __tmp;
289 }
290
291 _LIBCPP_HIDE_FROM_ABI
292 constexpr __iterator& operator--()
293 requires __zip_all_bidirectional<_Const, _Views...> {
294 ranges::__tuple_for_each([](auto& __i) { --__i; }, __current_);
295 return *this;
296 }
297
298 _LIBCPP_HIDE_FROM_ABI
299 constexpr __iterator operator--(int)
300 requires __zip_all_bidirectional<_Const, _Views...> {
301 auto __tmp = *this;
302 --*this;
303 return __tmp;
304 }
305
306 _LIBCPP_HIDE_FROM_ABI
307 constexpr __iterator& operator+=(difference_type __x)
308 requires __zip_all_random_access<_Const, _Views...> {
309 ranges::__tuple_for_each([&]<class _Iter>(_Iter& __i) { __i += iter_difference_t<_Iter>(__x); }, __current_);
310 return *this;
311 }
312
313 _LIBCPP_HIDE_FROM_ABI
314 constexpr __iterator& operator-=(difference_type __x)
315 requires __zip_all_random_access<_Const, _Views...> {
316 ranges::__tuple_for_each([&]<class _Iter>(_Iter& __i) { __i -= iter_difference_t<_Iter>(__x); }, __current_);
317 return *this;
318 }
319
320 _LIBCPP_HIDE_FROM_ABI
321 constexpr auto operator[](difference_type __n) const
322 requires __zip_all_random_access<_Const, _Views...> {
323 return ranges::__tuple_transform(
324 [&]<class _Iter>(_Iter& __i) -> decltype(auto) { return __i[iter_difference_t<_Iter>(__n)]; }, __current_);
325 }
326
327 _LIBCPP_HIDE_FROM_ABI
328 friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
329 requires(equality_comparable<iterator_t<__maybe_const<_Const, _Views>>> && ...) {
330 if constexpr (__zip_all_bidirectional<_Const, _Views...>) {
331 return __x.__current_ == __y.__current_;
332 } else {
333 return ranges::__tuple_any_equals(__x.__current_, __y.__current_);
334 }
335 }
336
337 _LIBCPP_HIDE_FROM_ABI
338 friend constexpr bool operator<(const __iterator& __x, const __iterator& __y)
339 requires __zip_all_random_access<_Const, _Views...> {
340 return __x.__current_ < __y.__current_;
341 }
342
343 _LIBCPP_HIDE_FROM_ABI
344 friend constexpr bool operator>(const __iterator& __x, const __iterator& __y)
345 requires __zip_all_random_access<_Const, _Views...> {
346 return __y < __x;
347 }
348
349 _LIBCPP_HIDE_FROM_ABI
350 friend constexpr bool operator<=(const __iterator& __x, const __iterator& __y)
351 requires __zip_all_random_access<_Const, _Views...> {
352 return !(__y < __x);
353 }
354
355 _LIBCPP_HIDE_FROM_ABI
356 friend constexpr bool operator>=(const __iterator& __x, const __iterator& __y)
357 requires __zip_all_random_access<_Const, _Views...> {
358 return !(__x < __y);
359 }
360
361 _LIBCPP_HIDE_FROM_ABI
362 friend constexpr auto operator<=>(const __iterator& __x, const __iterator& __y)
363 requires __zip_all_random_access<_Const, _Views...> &&
364 (three_way_comparable<iterator_t<__maybe_const<_Const, _Views>>> && ...) {
365 return __x.__current_ <=> __y.__current_;
366 }
367
368 _LIBCPP_HIDE_FROM_ABI
369 friend constexpr __iterator operator+(const __iterator& __i, difference_type __n)
370 requires __zip_all_random_access<_Const, _Views...> {
371 auto __r = __i;
372 __r += __n;
373 return __r;
374 }
375
376 _LIBCPP_HIDE_FROM_ABI
377 friend constexpr __iterator operator+(difference_type __n, const __iterator& __i)
378 requires __zip_all_random_access<_Const, _Views...> {
379 return __i + __n;
380 }
381
382 _LIBCPP_HIDE_FROM_ABI
383 friend constexpr __iterator operator-(const __iterator& __i, difference_type __n)
384 requires __zip_all_random_access<_Const, _Views...> {
385 auto __r = __i;
386 __r -= __n;
387 return __r;
388 }
389
390 _LIBCPP_HIDE_FROM_ABI
391 friend constexpr difference_type operator-(const __iterator& __x, const __iterator& __y)
392 requires(sized_sentinel_for<iterator_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_Const, _Views>>> &&
393 ...) {
394 const auto __diffs = ranges::__tuple_zip_transform(minus<>(), __x.__current_, __y.__current_);
395 return std::apply(
396 [](auto... __ds) {
397 return ranges::min({difference_type(__ds)...},
398 [](auto __a, auto __b) { return ranges::__abs(__a) < ranges::__abs(__b); });
399 },
400 __diffs);
401 }
402
403 _LIBCPP_HIDE_FROM_ABI
404 friend constexpr auto iter_move(const __iterator& __i) noexcept(
405 (noexcept(ranges::iter_move(declval<const iterator_t<__maybe_const<_Const, _Views>>&>())) && ...) &&
406 (is_nothrow_move_constructible_v<range_rvalue_reference_t<__maybe_const<_Const, _Views>>> && ...)) {
407 return ranges::__tuple_transform(ranges::iter_move, __i.__current_);
408 }
409
410 _LIBCPP_HIDE_FROM_ABI
411 friend constexpr void iter_swap(const __iterator& __l, const __iterator& __r) noexcept(
412 (noexcept(ranges::iter_swap(declval<const iterator_t<__maybe_const<_Const, _Views>>&>(),
413 declval<const iterator_t<__maybe_const<_Const, _Views>>&>())) &&
414 ...))
415 requires(indirectly_swappable<iterator_t<__maybe_const<_Const, _Views>>> && ...) {
416 ranges::__tuple_zip_for_each(ranges::iter_swap, __l.__current_, __r.__current_);
417 }
418 };
419
420 template <input_range... _Views>
421 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
422 template <bool _Const>
423 class zip_view<_Views...>::__sentinel {
424
425 __tuple_or_pair<sentinel_t<__maybe_const<_Const, _Views>>...> __end_;
426
427 _LIBCPP_HIDE_FROM_ABI
428 constexpr explicit __sentinel(__tuple_or_pair<sentinel_t<__maybe_const<_Const, _Views>>...> __end) : __end_(__end) {}
429
430 friend class zip_view<_Views...>;
431
432 // hidden friend cannot access private member of iterator because they are friends of friends
433 template <bool _OtherConst>
434 _LIBCPP_HIDE_FROM_ABI static constexpr decltype(auto)
435 __iter_current(zip_view<_Views...>::__iterator<_OtherConst> const& __it) {
436 return (__it.__current_);
437 }
438
439 public:
440 _LIBCPP_HIDE_FROM_ABI
441 __sentinel() = default;
442
443 _LIBCPP_HIDE_FROM_ABI
444 constexpr __sentinel(__sentinel<!_Const> __i)
445 requires _Const && (convertible_to<sentinel_t<_Views>, sentinel_t<__maybe_const<_Const, _Views>>> && ...)
446 : __end_(std::move(__i.__end_)) {}
447
448 template <bool _OtherConst>
449 requires(sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
450 ...)
451 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
452 return ranges::__tuple_any_equals(__iter_current(__x), __y.__end_);
453 }
454
455 template <bool _OtherConst>
456 requires(
457 sized_sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
458 ...)
459 _LIBCPP_HIDE_FROM_ABI friend constexpr common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>
460 operator-(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
461 const auto __diffs = ranges::__tuple_zip_transform(minus<>(), __iter_current(__x), __y.__end_);
462 return std::apply(
463 [](auto... __ds) {
464 using _Diff = common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>;
465 return ranges::min({_Diff(__ds)...},
466 [](auto __a, auto __b) { return ranges::__abs(__a) < ranges::__abs(__b); });
467 },
468 __diffs);
469 }
470
471 template <bool _OtherConst>
472 requires(
473 sized_sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
474 ...)
475 _LIBCPP_HIDE_FROM_ABI friend constexpr common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>
476 operator-(const __sentinel& __y, const __iterator<_OtherConst>& __x) {
477 return -(__x - __y);
478 }
479 };
480
481 template <class... _Views>
482 inline constexpr bool enable_borrowed_range<zip_view<_Views...>> = (enable_borrowed_range<_Views> && ...);
483
484 namespace views {
485 namespace __zip {
486
487 struct __fn {
488 _LIBCPP_HIDE_FROM_ABI constexpr auto operator()() const noexcept { return empty_view<tuple<>>{}; }
489
490 template <class... _Ranges>
491 _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Ranges&&... __rs) const
492 noexcept(noexcept(zip_view<all_t<_Ranges&&>...>(std::forward<_Ranges>(__rs)...)))
493 -> decltype(zip_view<all_t<_Ranges&&>...>(std::forward<_Ranges>(__rs)...)) {
494 return zip_view<all_t<_Ranges>...>(std::forward<_Ranges>(__rs)...);
495 }
496 };
497
498 } // namespace __zip
499 inline namespace __cpo {
500 inline constexpr auto zip = __zip::__fn{};
501 } // namespace __cpo
502 } // namespace views
503 } // namespace ranges
504
505 #endif // _LIBCPP_STD_VER > 20 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
506
507 _LIBCPP_END_NAMESPACE_STD
508
509 _LIBCPP_POP_MACROS
510
511 #endif // _LIBCPP___RANGES_ZIP_VIEW_H
512