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