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