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