2 //===----------------------------------------------------------------------===//
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
8 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP___RANGES_ZIP_VIEW_H
11 #define _LIBCPP___RANGES_ZIP_VIEW_H
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_move_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>
41 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
42 # pragma GCC system_header
46 #include <__undef_macros>
48 _LIBCPP_BEGIN_NAMESPACE_STD
50 #if _LIBCPP_STD_VER >= 23
54 template <class... _Ranges
>
55 concept __zip_is_common
= (sizeof...(_Ranges
) == 1 && (common_range
<_Ranges
> && ...)) ||
56 (!(bidirectional_range
<_Ranges
> && ...) && (common_range
<_Ranges
> && ...)) ||
57 ((random_access_range
<_Ranges
> && ...) && (sized_range
<_Ranges
> && ...));
59 template <typename _Tp
, typename _Up
>
60 auto __tuple_or_pair_test() -> pair
<_Tp
, _Up
>;
62 template <typename
... _Types
>
63 requires(sizeof...(_Types
) != 2)
64 auto __tuple_or_pair_test() -> tuple
<_Types
...>;
66 template <class... _Types
>
67 using __tuple_or_pair
= decltype(__tuple_or_pair_test
<_Types
...>());
69 template <class _Fun
, class _Tuple
>
70 _LIBCPP_HIDE_FROM_ABI
constexpr auto __tuple_transform(_Fun
&& __f
, _Tuple
&& __tuple
) {
72 [&]<class... _Types
>(_Types
&&... __elements
) {
73 return __tuple_or_pair
<invoke_result_t
<_Fun
&, _Types
>...>(
74 std::invoke(__f
, std::forward
<_Types
>(__elements
))...);
76 std::forward
<_Tuple
>(__tuple
));
79 template <class _Fun
, class _Tuple
>
80 _LIBCPP_HIDE_FROM_ABI
constexpr void __tuple_for_each(_Fun
&& __f
, _Tuple
&& __tuple
) {
82 [&]<class... _Types
>(_Types
&&... __elements
) {
83 (static_cast<void>(std::invoke(__f
, std::forward
<_Types
>(__elements
))), ...);
85 std::forward
<_Tuple
>(__tuple
));
88 template <class _Fun
, class _Tuple1
, class _Tuple2
, size_t... _Indices
>
89 _LIBCPP_HIDE_FROM_ABI
constexpr __tuple_or_pair
<
90 invoke_result_t
<_Fun
&, typename tuple_element
<_Indices
, remove_cvref_t
<_Tuple1
>>::type
,
91 typename tuple_element
<_Indices
, remove_cvref_t
<_Tuple2
>>::type
>...>
92 __tuple_zip_transform(_Fun
&& __f
, _Tuple1
&& __tuple1
, _Tuple2
&& __tuple2
, index_sequence
<_Indices
...>) {
93 return {std::invoke(__f
, std::get
<_Indices
>(std::forward
<_Tuple1
>(__tuple1
)),
94 std::get
<_Indices
>(std::forward
<_Tuple2
>(__tuple2
)))...};
97 template <class _Fun
, class _Tuple1
, class _Tuple2
>
98 _LIBCPP_HIDE_FROM_ABI
constexpr auto __tuple_zip_transform(_Fun
&& __f
, _Tuple1
&& __tuple1
, _Tuple2
&& __tuple2
) {
99 return ranges::__tuple_zip_transform(__f
, std::forward
<_Tuple1
>(__tuple1
), std::forward
<_Tuple2
>(__tuple2
),
100 std::make_index_sequence
<tuple_size
<remove_cvref_t
<_Tuple1
>>::value
>());
103 template <class _Fun
, class _Tuple1
, class _Tuple2
, size_t... _Indices
>
104 _LIBCPP_HIDE_FROM_ABI
constexpr void __tuple_zip_for_each(_Fun
&& __f
, _Tuple1
&& __tuple1
, _Tuple2
&& __tuple2
,
105 index_sequence
<_Indices
...>) {
106 (std::invoke(__f
, std::get
<_Indices
>(std::forward
<_Tuple1
>(__tuple1
)),
107 std::get
<_Indices
>(std::forward
<_Tuple2
>(__tuple2
))),
111 template <class _Fun
, class _Tuple1
, class _Tuple2
>
112 _LIBCPP_HIDE_FROM_ABI
constexpr auto __tuple_zip_for_each(_Fun
&& __f
, _Tuple1
&& __tuple1
, _Tuple2
&& __tuple2
) {
113 return ranges::__tuple_zip_for_each(__f
, std::forward
<_Tuple1
>(__tuple1
), std::forward
<_Tuple2
>(__tuple2
),
114 std::make_index_sequence
<tuple_size
<remove_cvref_t
<_Tuple1
>>::value
>());
117 template <class _Tuple1
, class _Tuple2
>
118 _LIBCPP_HIDE_FROM_ABI
constexpr bool __tuple_any_equals(const _Tuple1
& __tuple1
, const _Tuple2
& __tuple2
) {
119 const auto __equals
= ranges::__tuple_zip_transform(std::equal_to
<>(), __tuple1
, __tuple2
);
120 return std::apply([](auto... __bools
) { return (__bools
|| ...); }, __equals
);
123 // abs in cstdlib is not constexpr
124 // TODO : remove __abs once P0533R9 is implemented.
126 _LIBCPP_HIDE_FROM_ABI
constexpr _Tp
__abs(_Tp __t
) {
127 return __t
< 0 ? -__t
: __t
;
130 template <input_range
... _Views
>
131 requires(view
<_Views
> && ...) && (sizeof...(_Views
) > 0)
132 class zip_view
: public view_interface
<zip_view
<_Views
...>> {
134 _LIBCPP_NO_UNIQUE_ADDRESS tuple
<_Views
...> __views_
;
143 _LIBCPP_HIDE_FROM_ABI
144 zip_view() = default;
146 _LIBCPP_HIDE_FROM_ABI
147 constexpr explicit zip_view(_Views
... __views
) : __views_(std::move(__views
)...) {}
149 _LIBCPP_HIDE_FROM_ABI
150 constexpr auto begin()
151 requires(!(__simple_view
<_Views
> && ...)) {
152 return __iterator
<false>(ranges::__tuple_transform(ranges::begin
, __views_
));
155 _LIBCPP_HIDE_FROM_ABI
156 constexpr auto begin() const
157 requires(range
<const _Views
> && ...) {
158 return __iterator
<true>(ranges::__tuple_transform(ranges::begin
, __views_
));
161 _LIBCPP_HIDE_FROM_ABI
163 requires(!(__simple_view
<_Views
> && ...)) {
164 if constexpr (!__zip_is_common
<_Views
...>) {
165 return __sentinel
<false>(ranges::__tuple_transform(ranges::end
, __views_
));
166 } else if constexpr ((random_access_range
<_Views
> && ...)) {
167 return begin() + iter_difference_t
<__iterator
<false>>(size());
169 return __iterator
<false>(ranges::__tuple_transform(ranges::end
, __views_
));
173 _LIBCPP_HIDE_FROM_ABI
174 constexpr auto end() const
175 requires(range
<const _Views
> && ...) {
176 if constexpr (!__zip_is_common
<const _Views
...>) {
177 return __sentinel
<true>(ranges::__tuple_transform(ranges::end
, __views_
));
178 } else if constexpr ((random_access_range
<const _Views
> && ...)) {
179 return begin() + iter_difference_t
<__iterator
<true>>(size());
181 return __iterator
<true>(ranges::__tuple_transform(ranges::end
, __views_
));
185 _LIBCPP_HIDE_FROM_ABI
186 constexpr auto size()
187 requires(sized_range
<_Views
> && ...) {
189 [](auto... __sizes
) {
190 using _CT
= make_unsigned_t
<common_type_t
<decltype(__sizes
)...>>;
191 return ranges::min({_CT(__sizes
)...});
193 ranges::__tuple_transform(ranges::size
, __views_
));
196 _LIBCPP_HIDE_FROM_ABI
197 constexpr auto size() const
198 requires(sized_range
<const _Views
> && ...) {
200 [](auto... __sizes
) {
201 using _CT
= make_unsigned_t
<common_type_t
<decltype(__sizes
)...>>;
202 return ranges::min({_CT(__sizes
)...});
204 ranges::__tuple_transform(ranges::size
, __views_
));
208 template <class... _Ranges
>
209 zip_view(_Ranges
&&...) -> zip_view
<views::all_t
<_Ranges
>...>;
211 template <bool _Const
, class... _Views
>
212 concept __zip_all_random_access
= (random_access_range
<__maybe_const
<_Const
, _Views
>> && ...);
214 template <bool _Const
, class... _Views
>
215 concept __zip_all_bidirectional
= (bidirectional_range
<__maybe_const
<_Const
, _Views
>> && ...);
217 template <bool _Const
, class... _Views
>
218 concept __zip_all_forward
= (forward_range
<__maybe_const
<_Const
, _Views
>> && ...);
220 template <bool _Const
, class... _Views
>
221 consteval
auto __get_zip_view_iterator_tag() {
222 if constexpr (__zip_all_random_access
<_Const
, _Views
...>) {
223 return random_access_iterator_tag();
224 } else if constexpr (__zip_all_bidirectional
<_Const
, _Views
...>) {
225 return bidirectional_iterator_tag();
226 } else if constexpr (__zip_all_forward
<_Const
, _Views
...>) {
227 return forward_iterator_tag();
229 return input_iterator_tag();
233 template <bool _Const
, class... _Views
>
234 struct __zip_view_iterator_category_base
{};
236 template <bool _Const
, class... _Views
>
237 requires __zip_all_forward
<_Const
, _Views
...>
238 struct __zip_view_iterator_category_base
<_Const
, _Views
...> {
239 using iterator_category
= input_iterator_tag
;
242 template <input_range
... _Views
>
243 requires(view
<_Views
> && ...) && (sizeof...(_Views
) > 0)
244 template <bool _Const
>
245 class zip_view
<_Views
...>::__iterator
: public __zip_view_iterator_category_base
<_Const
, _Views
...> {
247 __tuple_or_pair
<iterator_t
<__maybe_const
<_Const
, _Views
>>...> __current_
;
249 _LIBCPP_HIDE_FROM_ABI
250 constexpr explicit __iterator(__tuple_or_pair
<iterator_t
<__maybe_const
<_Const
, _Views
>>...> __current
)
251 : __current_(std::move(__current
)) {}
254 friend class zip_view
<_Views
...>::__iterator
;
257 friend class zip_view
<_Views
...>::__sentinel
;
259 friend class zip_view
<_Views
...>;
262 using iterator_concept
= decltype(__get_zip_view_iterator_tag
<_Const
, _Views
...>());
263 using value_type
= __tuple_or_pair
<range_value_t
<__maybe_const
<_Const
, _Views
>>...>;
264 using difference_type
= common_type_t
<range_difference_t
<__maybe_const
<_Const
, _Views
>>...>;
266 _LIBCPP_HIDE_FROM_ABI
267 __iterator() = default;
269 _LIBCPP_HIDE_FROM_ABI
270 constexpr __iterator(__iterator
<!_Const
> __i
)
271 requires _Const
&& (convertible_to
<iterator_t
<_Views
>, iterator_t
<__maybe_const
<_Const
, _Views
>>> && ...)
272 : __current_(std::move(__i
.__current_
)) {}
274 _LIBCPP_HIDE_FROM_ABI
275 constexpr auto operator*() const {
276 return ranges::__tuple_transform([](auto& __i
) -> decltype(auto) { return *__i
; }, __current_
);
279 _LIBCPP_HIDE_FROM_ABI
280 constexpr __iterator
& operator++() {
281 ranges::__tuple_for_each([](auto& __i
) { ++__i
; }, __current_
);
285 _LIBCPP_HIDE_FROM_ABI
286 constexpr void operator++(int) { ++*this; }
288 _LIBCPP_HIDE_FROM_ABI
289 constexpr __iterator
operator++(int)
290 requires __zip_all_forward
<_Const
, _Views
...> {
296 _LIBCPP_HIDE_FROM_ABI
297 constexpr __iterator
& operator--()
298 requires __zip_all_bidirectional
<_Const
, _Views
...> {
299 ranges::__tuple_for_each([](auto& __i
) { --__i
; }, __current_
);
303 _LIBCPP_HIDE_FROM_ABI
304 constexpr __iterator
operator--(int)
305 requires __zip_all_bidirectional
<_Const
, _Views
...> {
311 _LIBCPP_HIDE_FROM_ABI
312 constexpr __iterator
& operator+=(difference_type __x
)
313 requires __zip_all_random_access
<_Const
, _Views
...> {
314 ranges::__tuple_for_each([&]<class _Iter
>(_Iter
& __i
) { __i
+= iter_difference_t
<_Iter
>(__x
); }, __current_
);
318 _LIBCPP_HIDE_FROM_ABI
319 constexpr __iterator
& operator-=(difference_type __x
)
320 requires __zip_all_random_access
<_Const
, _Views
...> {
321 ranges::__tuple_for_each([&]<class _Iter
>(_Iter
& __i
) { __i
-= iter_difference_t
<_Iter
>(__x
); }, __current_
);
325 _LIBCPP_HIDE_FROM_ABI
326 constexpr auto operator[](difference_type __n
) const
327 requires __zip_all_random_access
<_Const
, _Views
...> {
328 return ranges::__tuple_transform(
329 [&]<class _Iter
>(_Iter
& __i
) -> decltype(auto) { return __i
[iter_difference_t
<_Iter
>(__n
)]; }, __current_
);
332 _LIBCPP_HIDE_FROM_ABI
333 friend constexpr bool operator==(const __iterator
& __x
, const __iterator
& __y
)
334 requires(equality_comparable
<iterator_t
<__maybe_const
<_Const
, _Views
>>> && ...) {
335 if constexpr (__zip_all_bidirectional
<_Const
, _Views
...>) {
336 return __x
.__current_
== __y
.__current_
;
338 return ranges::__tuple_any_equals(__x
.__current_
, __y
.__current_
);
342 _LIBCPP_HIDE_FROM_ABI
343 friend constexpr bool operator<(const __iterator
& __x
, const __iterator
& __y
)
344 requires __zip_all_random_access
<_Const
, _Views
...> {
345 return __x
.__current_
< __y
.__current_
;
348 _LIBCPP_HIDE_FROM_ABI
349 friend constexpr bool operator>(const __iterator
& __x
, const __iterator
& __y
)
350 requires __zip_all_random_access
<_Const
, _Views
...> {
354 _LIBCPP_HIDE_FROM_ABI
355 friend constexpr bool operator<=(const __iterator
& __x
, const __iterator
& __y
)
356 requires __zip_all_random_access
<_Const
, _Views
...> {
360 _LIBCPP_HIDE_FROM_ABI
361 friend constexpr bool operator>=(const __iterator
& __x
, const __iterator
& __y
)
362 requires __zip_all_random_access
<_Const
, _Views
...> {
366 _LIBCPP_HIDE_FROM_ABI
367 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 return __x
.__current_
<=> __y
.__current_
;
373 _LIBCPP_HIDE_FROM_ABI
374 friend constexpr __iterator
operator+(const __iterator
& __i
, difference_type __n
)
375 requires __zip_all_random_access
<_Const
, _Views
...> {
381 _LIBCPP_HIDE_FROM_ABI
382 friend constexpr __iterator
operator+(difference_type __n
, const __iterator
& __i
)
383 requires __zip_all_random_access
<_Const
, _Views
...> {
387 _LIBCPP_HIDE_FROM_ABI
388 friend constexpr __iterator
operator-(const __iterator
& __i
, difference_type __n
)
389 requires __zip_all_random_access
<_Const
, _Views
...> {
395 _LIBCPP_HIDE_FROM_ABI
396 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
>>> &&
399 const auto __diffs
= ranges::__tuple_zip_transform(minus
<>(), __x
.__current_
, __y
.__current_
);
402 return ranges::min({difference_type(__ds
)...},
403 [](auto __a
, auto __b
) { return ranges::__abs(__a
) < ranges::__abs(__b
); });
408 _LIBCPP_HIDE_FROM_ABI
409 friend constexpr auto iter_move(const __iterator
& __i
) noexcept(
410 (noexcept(ranges::iter_move(std::declval
<const iterator_t
<__maybe_const
<_Const
, _Views
>>&>())) && ...) &&
411 (is_nothrow_move_constructible_v
<range_rvalue_reference_t
<__maybe_const
<_Const
, _Views
>>> && ...)) {
412 return ranges::__tuple_transform(ranges::iter_move
, __i
.__current_
);
415 _LIBCPP_HIDE_FROM_ABI
416 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
>>&>())) &&
420 requires(indirectly_swappable
<iterator_t
<__maybe_const
<_Const
, _Views
>>> && ...) {
421 ranges::__tuple_zip_for_each(ranges::iter_swap
, __l
.__current_
, __r
.__current_
);
425 template <input_range
... _Views
>
426 requires(view
<_Views
> && ...) && (sizeof...(_Views
) > 0)
427 template <bool _Const
>
428 class zip_view
<_Views
...>::__sentinel
{
430 __tuple_or_pair
<sentinel_t
<__maybe_const
<_Const
, _Views
>>...> __end_
;
432 _LIBCPP_HIDE_FROM_ABI
433 constexpr explicit __sentinel(__tuple_or_pair
<sentinel_t
<__maybe_const
<_Const
, _Views
>>...> __end
) : __end_(__end
) {}
435 friend class zip_view
<_Views
...>;
437 // hidden friend cannot access private member of iterator because they are friends of friends
438 template <bool _OtherConst
>
439 _LIBCPP_HIDE_FROM_ABI
static constexpr decltype(auto)
440 __iter_current(zip_view
<_Views
...>::__iterator
<_OtherConst
> const& __it
) {
441 return (__it
.__current_
);
445 _LIBCPP_HIDE_FROM_ABI
446 __sentinel() = default;
448 _LIBCPP_HIDE_FROM_ABI
449 constexpr __sentinel(__sentinel
<!_Const
> __i
)
450 requires _Const
&& (convertible_to
<sentinel_t
<_Views
>, sentinel_t
<__maybe_const
<_Const
, _Views
>>> && ...)
451 : __end_(std::move(__i
.__end_
)) {}
453 template <bool _OtherConst
>
454 requires(sentinel_for
<sentinel_t
<__maybe_const
<_Const
, _Views
>>, iterator_t
<__maybe_const
<_OtherConst
, _Views
>>> &&
456 _LIBCPP_HIDE_FROM_ABI
friend constexpr bool operator==(const __iterator
<_OtherConst
>& __x
, const __sentinel
& __y
) {
457 return ranges::__tuple_any_equals(__iter_current(__x
), __y
.__end_
);
460 template <bool _OtherConst
>
462 sized_sentinel_for
<sentinel_t
<__maybe_const
<_Const
, _Views
>>, iterator_t
<__maybe_const
<_OtherConst
, _Views
>>> &&
464 _LIBCPP_HIDE_FROM_ABI
friend constexpr common_type_t
<range_difference_t
<__maybe_const
<_OtherConst
, _Views
>>...>
465 operator-(const __iterator
<_OtherConst
>& __x
, const __sentinel
& __y
) {
466 const auto __diffs
= ranges::__tuple_zip_transform(minus
<>(), __iter_current(__x
), __y
.__end_
);
469 using _Diff
= common_type_t
<range_difference_t
<__maybe_const
<_OtherConst
, _Views
>>...>;
470 return ranges::min({_Diff(__ds
)...},
471 [](auto __a
, auto __b
) { return ranges::__abs(__a
) < ranges::__abs(__b
); });
476 template <bool _OtherConst
>
478 sized_sentinel_for
<sentinel_t
<__maybe_const
<_Const
, _Views
>>, iterator_t
<__maybe_const
<_OtherConst
, _Views
>>> &&
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
) {
486 template <class... _Views
>
487 inline constexpr bool enable_borrowed_range
<zip_view
<_Views
...>> = (enable_borrowed_range
<_Views
> && ...);
493 _LIBCPP_HIDE_FROM_ABI
constexpr auto operator()() const noexcept
{ return empty_view
<tuple
<>>{}; }
495 template <class... _Ranges
>
496 _LIBCPP_HIDE_FROM_ABI
constexpr auto operator()(_Ranges
&&... __rs
) const
497 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
)...);
504 inline namespace __cpo
{
505 inline constexpr auto zip
= __zip::__fn
{};
508 } // namespace ranges
510 #endif // _LIBCPP_STD_VER >= 23
512 _LIBCPP_END_NAMESPACE_STD
516 #endif // _LIBCPP___RANGES_ZIP_VIEW_H