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