xref: /freebsd/contrib/llvm-project/libcxx/include/__ranges/zip_view.h (revision 700637cbb5e582861067a11aaca4d053546871d2) 
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 
53 namespace ranges {
54 
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> && ...));
60 
61 template <class _Fun, class _Tuple>
__tuple_transform(_Fun && __f,_Tuple && __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 
70 template <class _Fun, class _Tuple>
__tuple_for_each(_Fun && __f,_Tuple && __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 
79 template <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>...>
__tuple_zip_transform(_Fun && __f,_Tuple1 && __tuple1,_Tuple2 && __tuple2,index_sequence<_Indices...>)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 
90 template <class _Fun, class _Tuple1, class _Tuple2>
__tuple_zip_transform(_Fun && __f,_Tuple1 && __tuple1,_Tuple2 && __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 
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,index_sequence<_Indices...>)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 
107 template <class _Fun, class _Tuple1, class _Tuple2>
__tuple_zip_for_each(_Fun && __f,_Tuple1 && __tuple1,_Tuple2 && __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 
116 template <class _Tuple1, class _Tuple2>
__tuple_any_equals(const _Tuple1 & __tuple1,const _Tuple2 & __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.
124 template <class _Tp>
__abs(_Tp __t)125 _LIBCPP_HIDE_FROM_ABI constexpr _Tp __abs(_Tp __t) {
126   return __t < 0 ? -__t : __t;
127 }
128 
129 template <input_range... _Views>
requires(view<_Views> &&...)130   requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
131 class 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 
140 public:
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 
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>
__get_zip_view_iterator_tag()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   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 
259 public:
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 
393 template <input_range... _Views>
394   requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
395 template <bool _Const>
396 class 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 
411 public:
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 
452 template <class... _Views>
453 inline constexpr bool enable_borrowed_range<zip_view<_Views...>> = (enable_borrowed_range<_Views> && ...);
454 
455 namespace views {
456 namespace __zip {
457 
458 struct __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
470 inline namespace __cpo {
471 inline constexpr auto zip = __zip::__fn{};
472 } // namespace __cpo
473 } // namespace views
474 } // namespace ranges
475 
476 template <class _Iterator>
477   requires _Iterator::__is_zip_view_iterator
478 struct __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