libcxx/include/__ranges/zip_view.h

   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
  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 <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
  69 template <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
  78 template <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
  89 template <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
  98 template <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
 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(
 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
 115 template <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.
 123 template <class _Tp>
 124 _LIBCPP_HIDE_FROM_ABI constexpr _Tp __abs(_Tp __t) {
 125   return __t < 0 ? -__t : __t;
 126 }
 127
 128 template <input_range... _Views>
 129   requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
 130 class 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
 139 public:
 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
 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   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
 254 public:
 255   using iterator_concept = decltype(__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
 388 template <input_range... _Views>
 389   requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
 390 template <bool _Const>
 391 class 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
 406 public:
 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
 447 template <class... _Views>
 448 inline constexpr bool enable_borrowed_range<zip_view<_Views...>> = (enable_borrowed_range<_Views> && ...);
 449
 450 namespace views {
 451 namespace __zip {
 452
 453 struct __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
 465 inline namespace __cpo {
 466 inline 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