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