Warning: This file is not a C or C++ file. It does not have highlighting.

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
52namespace ranges {
53
54template <class... _Ranges>
55concept __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
60template <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
69template <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
78template <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
89template <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
98template <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
106template <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
115template <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.
123template <class _Tp>
124_LIBCPP_HIDE_FROM_ABI constexpr _Tp __abs(_Tp __t) {
125 return __t < 0 ? -__t : __t;
126}
127
128template <input_range... _Views>
129 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
130class 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
139public:
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
203template <class... _Ranges>
204zip_view(_Ranges&&...) -> zip_view<views::all_t<_Ranges>...>;
205
206template <bool _Const, class... _Views>
207concept __zip_all_random_access = (random_access_range<__maybe_const<_Const, _Views>> && ...);
208
209template <bool _Const, class... _Views>
210concept __zip_all_bidirectional = (bidirectional_range<__maybe_const<_Const, _Views>> && ...);
211
212template <bool _Const, class... _Views>
213concept __zip_all_forward = (forward_range<__maybe_const<_Const, _Views>> && ...);
214
215template <bool _Const, class... _Views>
216consteval 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
228template <bool _Const, class... _Views>
229struct __zip_view_iterator_category_base {};
230
231template <bool _Const, class... _Views>
232 requires __zip_all_forward<_Const, _Views...>
233struct __zip_view_iterator_category_base<_Const, _Views...> {
234 using iterator_category = input_iterator_tag;
235};
236
237template <input_range... _Views>
238 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
239template <bool _Const>
240class 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
254public:
255 using iterator_concept = decltype(ranges::__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
388template <input_range... _Views>
389 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
390template <bool _Const>
391class 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
406public:
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
447template <class... _Views>
448inline constexpr bool enable_borrowed_range<zip_view<_Views...>> = (enable_borrowed_range<_Views> && ...);
449
450namespace views {
451namespace __zip {
452
453struct __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
465inline namespace __cpo {
466inline 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

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__ranges/zip_view.h