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