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