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___CXX03___RANGES_ZIP_VIEW_H
11 #define _LIBCPP___CXX03___RANGES_ZIP_VIEW_H
13 #include <__cxx03/__config>
15 #include <__cxx03/__algorithm/ranges_min.h>
16 #include <__cxx03/__compare/three_way_comparable.h>
17 #include <__cxx03/__concepts/convertible_to.h>
18 #include <__cxx03/__concepts/equality_comparable.h>
19 #include <__cxx03/__functional/invoke.h>
20 #include <__cxx03/__functional/operations.h>
21 #include <__cxx03/__iterator/concepts.h>
22 #include <__cxx03/__iterator/incrementable_traits.h>
23 #include <__cxx03/__iterator/iter_move.h>
24 #include <__cxx03/__iterator/iter_swap.h>
25 #include <__cxx03/__iterator/iterator_traits.h>
26 #include <__cxx03/__ranges/access.h>
27 #include <__cxx03/__ranges/all.h>
28 #include <__cxx03/__ranges/concepts.h>
29 #include <__cxx03/__ranges/empty_view.h>
30 #include <__cxx03/__ranges/enable_borrowed_range.h>
31 #include <__cxx03/__ranges/size.h>
32 #include <__cxx03/__ranges/view_interface.h>
33 #include <__cxx03/__type_traits/is_nothrow_constructible.h>
34 #include <__cxx03/__type_traits/make_unsigned.h>
35 #include <__cxx03/__utility/declval.h>
36 #include <__cxx03/__utility/forward.h>
37 #include <__cxx03/__utility/integer_sequence.h>
38 #include <__cxx03/__utility/move.h>
39 #include <__cxx03/__utility/pair.h>
40 #include <__cxx03/tuple>
42 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
43 # pragma GCC system_header
47 #include <__cxx03/__undef_macros>
49 _LIBCPP_BEGIN_NAMESPACE_STD
51 #if _LIBCPP_STD_VER >= 23
55 template <class... _Ranges
>
56 concept __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
> && ...));
61 template <typename _Tp
, typename _Up
>
62 auto __tuple_or_pair_test() -> pair
<_Tp
, _Up
>;
64 template <typename
... _Types
>
65 requires(sizeof...(_Types
) != 2)
66 auto __tuple_or_pair_test() -> tuple
<_Types
...>;
68 template <class... _Types
>
69 using __tuple_or_pair
= decltype(__tuple_or_pair_test
<_Types
...>());
71 template <class _Fun
, class _Tuple
>
72 _LIBCPP_HIDE_FROM_ABI
constexpr auto __tuple_transform(_Fun
&& __f
, _Tuple
&& __tuple
) {
74 [&]<class... _Types
>(_Types
&&... __elements
) {
75 return __tuple_or_pair
<invoke_result_t
<_Fun
&, _Types
>...>(
76 std::invoke(__f
, std::forward
<_Types
>(__elements
))...);
78 std::forward
<_Tuple
>(__tuple
));
81 template <class _Fun
, class _Tuple
>
82 _LIBCPP_HIDE_FROM_ABI
constexpr void __tuple_for_each(_Fun
&& __f
, _Tuple
&& __tuple
) {
84 [&]<class... _Types
>(_Types
&&... __elements
) {
85 (static_cast<void>(std::invoke(__f
, std::forward
<_Types
>(__elements
))), ...);
87 std::forward
<_Tuple
>(__tuple
));
90 template <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
)))...};
101 template <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(
105 std::forward
<_Tuple1
>(__tuple1
),
106 std::forward
<_Tuple2
>(__tuple2
),
107 std::make_index_sequence
<tuple_size
<remove_cvref_t
<_Tuple1
>>::value
>());
110 template <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
...>) {
114 __f
, std::get
<_Indices
>(std::forward
<_Tuple1
>(__tuple1
)), std::get
<_Indices
>(std::forward
<_Tuple2
>(__tuple2
))),
118 template <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(
122 std::forward
<_Tuple1
>(__tuple1
),
123 std::forward
<_Tuple2
>(__tuple2
),
124 std::make_index_sequence
<tuple_size
<remove_cvref_t
<_Tuple1
>>::value
>());
127 template <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
);
133 // abs in cstdlib is not constexpr
134 // TODO : remove __abs once P0533R9 is implemented.
136 _LIBCPP_HIDE_FROM_ABI
constexpr _Tp
__abs(_Tp __t
) {
137 return __t
< 0 ? -__t
: __t
;
140 template <input_range
... _Views
>
141 requires(view
<_Views
> && ...) && (sizeof...(_Views
) > 0)
142 class zip_view
: public view_interface
<zip_view
<_Views
...>> {
143 _LIBCPP_NO_UNIQUE_ADDRESS tuple
<_Views
...> __views_
;
152 _LIBCPP_HIDE_FROM_ABI
zip_view() = default;
154 _LIBCPP_HIDE_FROM_ABI
constexpr explicit zip_view(_Views
... __views
) : __views_(std::move(__views
)...) {}
156 _LIBCPP_HIDE_FROM_ABI
constexpr auto begin()
157 requires(!(__simple_view
<_Views
> && ...))
159 return __iterator
<false>(ranges::__tuple_transform(ranges::begin
, __views_
));
162 _LIBCPP_HIDE_FROM_ABI
constexpr auto begin() const
163 requires(range
<const _Views
> && ...)
165 return __iterator
<true>(ranges::__tuple_transform(ranges::begin
, __views_
));
168 _LIBCPP_HIDE_FROM_ABI
constexpr auto end()
169 requires(!(__simple_view
<_Views
> && ...))
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());
176 return __iterator
<false>(ranges::__tuple_transform(ranges::end
, __views_
));
180 _LIBCPP_HIDE_FROM_ABI
constexpr auto end() const
181 requires(range
<const _Views
> && ...)
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());
188 return __iterator
<true>(ranges::__tuple_transform(ranges::end
, __views_
));
192 _LIBCPP_HIDE_FROM_ABI
constexpr auto size()
193 requires(sized_range
<_Views
> && ...)
196 [](auto... __sizes
) {
197 using _CT
= make_unsigned_t
<common_type_t
<decltype(__sizes
)...>>;
198 return ranges::min({_CT(__sizes
)...});
200 ranges::__tuple_transform(ranges::size
, __views_
));
203 _LIBCPP_HIDE_FROM_ABI
constexpr auto size() const
204 requires(sized_range
<const _Views
> && ...)
207 [](auto... __sizes
) {
208 using _CT
= make_unsigned_t
<common_type_t
<decltype(__sizes
)...>>;
209 return ranges::min({_CT(__sizes
)...});
211 ranges::__tuple_transform(ranges::size
, __views_
));
215 template <class... _Ranges
>
216 zip_view(_Ranges
&&...) -> zip_view
<views::all_t
<_Ranges
>...>;
218 template <bool _Const
, class... _Views
>
219 concept __zip_all_random_access
= (random_access_range
<__maybe_const
<_Const
, _Views
>> && ...);
221 template <bool _Const
, class... _Views
>
222 concept __zip_all_bidirectional
= (bidirectional_range
<__maybe_const
<_Const
, _Views
>> && ...);
224 template <bool _Const
, class... _Views
>
225 concept __zip_all_forward
= (forward_range
<__maybe_const
<_Const
, _Views
>> && ...);
227 template <bool _Const
, class... _Views
>
228 consteval
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();
236 return input_iterator_tag();
240 template <bool _Const
, class... _Views
>
241 struct __zip_view_iterator_category_base
{};
243 template <bool _Const
, class... _Views
>
244 requires __zip_all_forward
<_Const
, _Views
...>
245 struct __zip_view_iterator_category_base
<_Const
, _Views
...> {
246 using iterator_category
= input_iterator_tag
;
249 template <input_range
... _Views
>
250 requires(view
<_Views
> && ...) && (sizeof...(_Views
) > 0)
251 template <bool _Const
>
252 class zip_view
<_Views
...>::__iterator
: public __zip_view_iterator_category_base
<_Const
, _Views
...> {
253 __tuple_or_pair
<iterator_t
<__maybe_const
<_Const
, _Views
>>...> __current_
;
255 _LIBCPP_HIDE_FROM_ABI
constexpr explicit __iterator(
256 __tuple_or_pair
<iterator_t
<__maybe_const
<_Const
, _Views
>>...> __current
)
257 : __current_(std::move(__current
)) {}
260 friend class zip_view
<_Views
...>::__iterator
;
263 friend class zip_view
<_Views
...>::__sentinel
;
265 friend class zip_view
<_Views
...>;
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
>>...>;
272 _LIBCPP_HIDE_FROM_ABI
__iterator() = default;
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_
)) {}
278 _LIBCPP_HIDE_FROM_ABI
constexpr auto operator*() const {
279 return ranges::__tuple_transform([](auto& __i
) -> decltype(auto) { return *__i
; }, __current_
);
282 _LIBCPP_HIDE_FROM_ABI
constexpr __iterator
& operator++() {
283 ranges::__tuple_for_each([](auto& __i
) { ++__i
; }, __current_
);
287 _LIBCPP_HIDE_FROM_ABI
constexpr void operator++(int) { ++*this; }
289 _LIBCPP_HIDE_FROM_ABI
constexpr __iterator
operator++(int)
290 requires __zip_all_forward
<_Const
, _Views
...>
297 _LIBCPP_HIDE_FROM_ABI
constexpr __iterator
& operator--()
298 requires __zip_all_bidirectional
<_Const
, _Views
...>
300 ranges::__tuple_for_each([](auto& __i
) { --__i
; }, __current_
);
304 _LIBCPP_HIDE_FROM_ABI
constexpr __iterator
operator--(int)
305 requires __zip_all_bidirectional
<_Const
, _Views
...>
312 _LIBCPP_HIDE_FROM_ABI
constexpr __iterator
& operator+=(difference_type __x
)
313 requires __zip_all_random_access
<_Const
, _Views
...>
315 ranges::__tuple_for_each([&]<class _Iter
>(_Iter
& __i
) { __i
+= iter_difference_t
<_Iter
>(__x
); }, __current_
);
319 _LIBCPP_HIDE_FROM_ABI
constexpr __iterator
& operator-=(difference_type __x
)
320 requires __zip_all_random_access
<_Const
, _Views
...>
322 ranges::__tuple_for_each([&]<class _Iter
>(_Iter
& __i
) { __i
-= iter_difference_t
<_Iter
>(__x
); }, __current_
);
326 _LIBCPP_HIDE_FROM_ABI
constexpr auto operator[](difference_type __n
) const
327 requires __zip_all_random_access
<_Const
, _Views
...>
329 return ranges::__tuple_transform(
330 [&]<class _Iter
>(_Iter
& __i
) -> decltype(auto) { return __i
[iter_difference_t
<_Iter
>(__n
)]; }, __current_
);
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
>>> && ...)
336 if constexpr (__zip_all_bidirectional
<_Const
, _Views
...>) {
337 return __x
.__current_
== __y
.__current_
;
339 return ranges::__tuple_any_equals(__x
.__current_
, __y
.__current_
);
343 _LIBCPP_HIDE_FROM_ABI
friend constexpr bool operator<(const __iterator
& __x
, const __iterator
& __y
)
344 requires __zip_all_random_access
<_Const
, _Views
...>
346 return __x
.__current_
< __y
.__current_
;
349 _LIBCPP_HIDE_FROM_ABI
friend constexpr bool operator>(const __iterator
& __x
, const __iterator
& __y
)
350 requires __zip_all_random_access
<_Const
, _Views
...>
355 _LIBCPP_HIDE_FROM_ABI
friend constexpr bool operator<=(const __iterator
& __x
, const __iterator
& __y
)
356 requires __zip_all_random_access
<_Const
, _Views
...>
361 _LIBCPP_HIDE_FROM_ABI
friend constexpr bool operator>=(const __iterator
& __x
, const __iterator
& __y
)
362 requires __zip_all_random_access
<_Const
, _Views
...>
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
>>> && ...)
371 return __x
.__current_
<=> __y
.__current_
;
374 _LIBCPP_HIDE_FROM_ABI
friend constexpr __iterator
operator+(const __iterator
& __i
, difference_type __n
)
375 requires __zip_all_random_access
<_Const
, _Views
...>
382 _LIBCPP_HIDE_FROM_ABI
friend constexpr __iterator
operator+(difference_type __n
, const __iterator
& __i
)
383 requires __zip_all_random_access
<_Const
, _Views
...>
388 _LIBCPP_HIDE_FROM_ABI
friend constexpr __iterator
operator-(const __iterator
& __i
, difference_type __n
)
389 requires __zip_all_random_access
<_Const
, _Views
...>
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
>>> &&
400 const auto __diffs
= ranges::__tuple_zip_transform(minus
<>(), __x
.__current_
, __y
.__current_
);
403 return ranges::min({difference_type(__ds
)...}, [](auto __a
, auto __b
) {
404 return ranges::__abs(__a
) < ranges::__abs(__b
);
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_
);
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
>>&>())) &&
420 requires(indirectly_swappable
<iterator_t
<__maybe_const
<_Const
, _Views
>>> && ...)
422 ranges::__tuple_zip_for_each(ranges::iter_swap
, __l
.__current_
, __r
.__current_
);
426 template <input_range
... _Views
>
427 requires(view
<_Views
> && ...) && (sizeof...(_Views
) > 0)
428 template <bool _Const
>
429 class zip_view
<_Views
...>::__sentinel
{
430 __tuple_or_pair
<sentinel_t
<__maybe_const
<_Const
, _Views
>>...> __end_
;
432 _LIBCPP_HIDE_FROM_ABI
constexpr explicit __sentinel(
433 __tuple_or_pair
<sentinel_t
<__maybe_const
<_Const
, _Views
>>...> __end
)
436 friend class zip_view
<_Views
...>;
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_
);
446 _LIBCPP_HIDE_FROM_ABI
__sentinel() = default;
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_
)) {}
452 template <bool _OtherConst
>
453 requires(sentinel_for
<sentinel_t
<__maybe_const
<_Const
, _Views
>>, iterator_t
<__maybe_const
<_OtherConst
, _Views
>>> &&
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_
);
459 template <bool _OtherConst
>
461 sized_sentinel_for
<sentinel_t
<__maybe_const
<_Const
, _Views
>>, iterator_t
<__maybe_const
<_OtherConst
, _Views
>>> &&
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_
);
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
);
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
static constexpr auto operator()() noexcept
{ return empty_view
<tuple
<>>{}; }
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
)...);
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___CXX03___RANGES_ZIP_VIEW_H