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