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