v1/__ranges/zip_view.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___RANGES_ZIP_VIEW_H
0011 #define _LIBCPP___RANGES_ZIP_VIEW_H
0012
0013 #include <__config>
0014
0015 #include <__algorithm/ranges_min.h>
0016 #include <__compare/three_way_comparable.h>
0017 #include <__concepts/convertible_to.h>
0018 #include <__concepts/equality_comparable.h>
0019 #include <__functional/invoke.h>
0020 #include <__functional/operations.h>
0021 #include <__iterator/concepts.h>
0022 #include <__iterator/incrementable_traits.h>
0023 #include <__iterator/iter_move.h>
0024 #include <__iterator/iter_swap.h>
0025 #include <__iterator/iterator_traits.h>
0026 #include <__ranges/access.h>
0027 #include <__ranges/all.h>
0028 #include <__ranges/concepts.h>
0029 #include <__ranges/empty_view.h>
0030 #include <__ranges/enable_borrowed_range.h>
0031 #include <__ranges/size.h>
0032 #include <__ranges/view_interface.h>
0033 #include <__type_traits/is_nothrow_constructible.h>
0034 #include <__type_traits/make_unsigned.h>
0035 #include <__utility/declval.h>
0036 #include <__utility/forward.h>
0037 #include <__utility/integer_sequence.h>
0038 #include <__utility/move.h>
0039 #include <tuple>
0040
0041 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0042 #  pragma GCC system_header
0043 #endif
0044
0045 _LIBCPP_PUSH_MACROS
0046 #include <__undef_macros>
0047
0048 _LIBCPP_BEGIN_NAMESPACE_STD
0049
0050 #if _LIBCPP_STD_VER >= 23
0051
0052 namespace ranges {
0053
0054 template <class... _Ranges>
0055 concept __zip_is_common =
0056     (sizeof...(_Ranges) == 1 && (common_range<_Ranges> && ...)) ||
0057     (!(bidirectional_range<_Ranges> && ...) && (common_range<_Ranges> && ...)) ||
0058     ((random_access_range<_Ranges> && ...) && (sized_range<_Ranges> && ...));
0059
0060 template <class _Fun, class _Tuple>
0061 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_transform(_Fun&& __f, _Tuple&& __tuple) {
0062   return std::apply(
0063       [&]<class... _Types>(_Types&&... __elements) {
0064         return tuple<invoke_result_t<_Fun&, _Types>...>(std::invoke(__f, std::forward<_Types>(__elements))...);
0065       },
0066       std::forward<_Tuple>(__tuple));
0067 }
0068
0069 template <class _Fun, class _Tuple>
0070 _LIBCPP_HIDE_FROM_ABI constexpr void __tuple_for_each(_Fun&& __f, _Tuple&& __tuple) {
0071   std::apply(
0072       [&]<class... _Types>(_Types&&... __elements) {
0073         (static_cast<void>(std::invoke(__f, std::forward<_Types>(__elements))), ...);
0074       },
0075       std::forward<_Tuple>(__tuple));
0076 }
0077
0078 template <class _Fun, class _Tuple1, class _Tuple2, size_t... _Indices>
0079 _LIBCPP_HIDE_FROM_ABI constexpr tuple<
0080     invoke_result_t<_Fun&,
0081                     typename tuple_element<_Indices, remove_cvref_t<_Tuple1>>::type,
0082                     typename tuple_element<_Indices, remove_cvref_t<_Tuple2>>::type>...>
0083 __tuple_zip_transform(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2, index_sequence<_Indices...>) {
0084   return {std::invoke(__f,
0085                       std::get<_Indices>(std::forward<_Tuple1>(__tuple1)),
0086                       std::get<_Indices>(std::forward<_Tuple2>(__tuple2)))...};
0087 }
0088
0089 template <class _Fun, class _Tuple1, class _Tuple2>
0090 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_zip_transform(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2) {
0091   return ranges::__tuple_zip_transform(
0092       __f,
0093       std::forward<_Tuple1>(__tuple1),
0094       std::forward<_Tuple2>(__tuple2),
0095       std::make_index_sequence<tuple_size<remove_cvref_t<_Tuple1>>::value>());
0096 }
0097
0098 template <class _Fun, class _Tuple1, class _Tuple2, size_t... _Indices>
0099 _LIBCPP_HIDE_FROM_ABI constexpr void
0100 __tuple_zip_for_each(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2, index_sequence<_Indices...>) {
0101   (std::invoke(
0102        __f, std::get<_Indices>(std::forward<_Tuple1>(__tuple1)), std::get<_Indices>(std::forward<_Tuple2>(__tuple2))),
0103    ...);
0104 }
0105
0106 template <class _Fun, class _Tuple1, class _Tuple2>
0107 _LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_zip_for_each(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2) {
0108   return ranges::__tuple_zip_for_each(
0109       __f,
0110       std::forward<_Tuple1>(__tuple1),
0111       std::forward<_Tuple2>(__tuple2),
0112       std::make_index_sequence<tuple_size<remove_cvref_t<_Tuple1>>::value>());
0113 }
0114
0115 template <class _Tuple1, class _Tuple2>
0116 _LIBCPP_HIDE_FROM_ABI constexpr bool __tuple_any_equals(const _Tuple1& __tuple1, const _Tuple2& __tuple2) {
0117   const auto __equals = ranges::__tuple_zip_transform(std::equal_to<>(), __tuple1, __tuple2);
0118   return std::apply([](auto... __bools) { return (__bools || ...); }, __equals);
0119 }
0120
0121 // abs in cstdlib is not constexpr
0122 // TODO : remove __abs once P0533R9 is implemented.
0123 template <class _Tp>
0124 _LIBCPP_HIDE_FROM_ABI constexpr _Tp __abs(_Tp __t) {
0125   return __t < 0 ? -__t : __t;
0126 }
0127
0128 template <input_range... _Views>
0129   requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
0130 class zip_view : public view_interface<zip_view<_Views...>> {
0131   _LIBCPP_NO_UNIQUE_ADDRESS tuple<_Views...> __views_;
0132
0133   template <bool>
0134   class __iterator;
0135
0136   template <bool>
0137   class __sentinel;
0138
0139 public:
0140   _LIBCPP_HIDE_FROM_ABI zip_view() = default;
0141
0142   _LIBCPP_HIDE_FROM_ABI constexpr explicit zip_view(_Views... __views) : __views_(std::move(__views)...) {}
0143
0144   _LIBCPP_HIDE_FROM_ABI constexpr auto begin()
0145     requires(!(__simple_view<_Views> && ...))
0146   {
0147     return __iterator<false>(ranges::__tuple_transform(ranges::begin, __views_));
0148   }
0149
0150   _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
0151     requires(range<const _Views> && ...)
0152   {
0153     return __iterator<true>(ranges::__tuple_transform(ranges::begin, __views_));
0154   }
0155
0156   _LIBCPP_HIDE_FROM_ABI constexpr auto end()
0157     requires(!(__simple_view<_Views> && ...))
0158   {
0159     if constexpr (!__zip_is_common<_Views...>) {
0160       return __sentinel<false>(ranges::__tuple_transform(ranges::end, __views_));
0161     } else if constexpr ((random_access_range<_Views> && ...)) {
0162       return begin() + iter_difference_t<__iterator<false>>(size());
0163     } else {
0164       return __iterator<false>(ranges::__tuple_transform(ranges::end, __views_));
0165     }
0166   }
0167
0168   _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
0169     requires(range<const _Views> && ...)
0170   {
0171     if constexpr (!__zip_is_common<const _Views...>) {
0172       return __sentinel<true>(ranges::__tuple_transform(ranges::end, __views_));
0173     } else if constexpr ((random_access_range<const _Views> && ...)) {
0174       return begin() + iter_difference_t<__iterator<true>>(size());
0175     } else {
0176       return __iterator<true>(ranges::__tuple_transform(ranges::end, __views_));
0177     }
0178   }
0179
0180   _LIBCPP_HIDE_FROM_ABI constexpr auto size()
0181     requires(sized_range<_Views> && ...)
0182   {
0183     return std::apply(
0184         [](auto... __sizes) {
0185           using _CT = make_unsigned_t<common_type_t<decltype(__sizes)...>>;
0186           return ranges::min({_CT(__sizes)...});
0187         },
0188         ranges::__tuple_transform(ranges::size, __views_));
0189   }
0190
0191   _LIBCPP_HIDE_FROM_ABI constexpr auto size() const
0192     requires(sized_range<const _Views> && ...)
0193   {
0194     return std::apply(
0195         [](auto... __sizes) {
0196           using _CT = make_unsigned_t<common_type_t<decltype(__sizes)...>>;
0197           return ranges::min({_CT(__sizes)...});
0198         },
0199         ranges::__tuple_transform(ranges::size, __views_));
0200   }
0201 };
0202
0203 template <class... _Ranges>
0204 zip_view(_Ranges&&...) -> zip_view<views::all_t<_Ranges>...>;
0205
0206 template <bool _Const, class... _Views>
0207 concept __zip_all_random_access = (random_access_range<__maybe_const<_Const, _Views>> && ...);
0208
0209 template <bool _Const, class... _Views>
0210 concept __zip_all_bidirectional = (bidirectional_range<__maybe_const<_Const, _Views>> && ...);
0211
0212 template <bool _Const, class... _Views>
0213 concept __zip_all_forward = (forward_range<__maybe_const<_Const, _Views>> && ...);
0214
0215 template <bool _Const, class... _Views>
0216 consteval auto __get_zip_view_iterator_tag() {
0217   if constexpr (__zip_all_random_access<_Const, _Views...>) {
0218     return random_access_iterator_tag();
0219   } else if constexpr (__zip_all_bidirectional<_Const, _Views...>) {
0220     return bidirectional_iterator_tag();
0221   } else if constexpr (__zip_all_forward<_Const, _Views...>) {
0222     return forward_iterator_tag();
0223   } else {
0224     return input_iterator_tag();
0225   }
0226 }
0227
0228 template <bool _Const, class... _Views>
0229 struct __zip_view_iterator_category_base {};
0230
0231 template <bool _Const, class... _Views>
0232   requires __zip_all_forward<_Const, _Views...>
0233 struct __zip_view_iterator_category_base<_Const, _Views...> {
0234   using iterator_category = input_iterator_tag;
0235 };
0236
0237 template <input_range... _Views>
0238   requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
0239 template <bool _Const>
0240 class zip_view<_Views...>::__iterator : public __zip_view_iterator_category_base<_Const, _Views...> {
0241   tuple<iterator_t<__maybe_const<_Const, _Views>>...> __current_;
0242
0243   _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(tuple<iterator_t<__maybe_const<_Const, _Views>>...> __current)
0244       : __current_(std::move(__current)) {}
0245
0246   template <bool>
0247   friend class zip_view<_Views...>::__iterator;
0248
0249   template <bool>
0250   friend class zip_view<_Views...>::__sentinel;
0251
0252   friend class zip_view<_Views...>;
0253
0254 public:
0255   using iterator_concept = decltype(__get_zip_view_iterator_tag<_Const, _Views...>());
0256   using value_type       = tuple<range_value_t<__maybe_const<_Const, _Views>>...>;
0257   using difference_type  = common_type_t<range_difference_t<__maybe_const<_Const, _Views>>...>;
0258
0259   _LIBCPP_HIDE_FROM_ABI __iterator() = default;
0260
0261   _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i)
0262     requires _Const && (convertible_to<iterator_t<_Views>, iterator_t<__maybe_const<_Const, _Views>>> && ...)
0263       : __current_(std::move(__i.__current_)) {}
0264
0265   _LIBCPP_HIDE_FROM_ABI constexpr auto operator*() const {
0266     return ranges::__tuple_transform([](auto& __i) -> decltype(auto) { return *__i; }, __current_);
0267   }
0268
0269   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
0270     ranges::__tuple_for_each([](auto& __i) { ++__i; }, __current_);
0271     return *this;
0272   }
0273
0274   _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; }
0275
0276   _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)
0277     requires __zip_all_forward<_Const, _Views...>
0278   {
0279     auto __tmp = *this;
0280     ++*this;
0281     return __tmp;
0282   }
0283
0284   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()
0285     requires __zip_all_bidirectional<_Const, _Views...>
0286   {
0287     ranges::__tuple_for_each([](auto& __i) { --__i; }, __current_);
0288     return *this;
0289   }
0290
0291   _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)
0292     requires __zip_all_bidirectional<_Const, _Views...>
0293   {
0294     auto __tmp = *this;
0295     --*this;
0296     return __tmp;
0297   }
0298
0299   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator+=(difference_type __x)
0300     requires __zip_all_random_access<_Const, _Views...>
0301   {
0302     ranges::__tuple_for_each([&]<class _Iter>(_Iter& __i) { __i += iter_difference_t<_Iter>(__x); }, __current_);
0303     return *this;
0304   }
0305
0306   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator-=(difference_type __x)
0307     requires __zip_all_random_access<_Const, _Views...>
0308   {
0309     ranges::__tuple_for_each([&]<class _Iter>(_Iter& __i) { __i -= iter_difference_t<_Iter>(__x); }, __current_);
0310     return *this;
0311   }
0312
0313   _LIBCPP_HIDE_FROM_ABI constexpr auto operator[](difference_type __n) const
0314     requires __zip_all_random_access<_Const, _Views...>
0315   {
0316     return ranges::__tuple_transform(
0317         [&]<class _Iter>(_Iter& __i) -> decltype(auto) { return __i[iter_difference_t<_Iter>(__n)]; }, __current_);
0318   }
0319
0320   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
0321     requires(equality_comparable<iterator_t<__maybe_const<_Const, _Views>>> && ...)
0322   {
0323     if constexpr (__zip_all_bidirectional<_Const, _Views...>) {
0324       return __x.__current_ == __y.__current_;
0325     } else {
0326       return ranges::__tuple_any_equals(__x.__current_, __y.__current_);
0327     }
0328   }
0329
0330   _LIBCPP_HIDE_FROM_ABI friend constexpr auto operator<=>(const __iterator& __x, const __iterator& __y)
0331     requires __zip_all_random_access<_Const, _Views...>
0332   {
0333     return __x.__current_ <=> __y.__current_;
0334   }
0335
0336   _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(const __iterator& __i, difference_type __n)
0337     requires __zip_all_random_access<_Const, _Views...>
0338   {
0339     auto __r = __i;
0340     __r += __n;
0341     return __r;
0342   }
0343
0344   _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(difference_type __n, const __iterator& __i)
0345     requires __zip_all_random_access<_Const, _Views...>
0346   {
0347     return __i + __n;
0348   }
0349
0350   _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator-(const __iterator& __i, difference_type __n)
0351     requires __zip_all_random_access<_Const, _Views...>
0352   {
0353     auto __r = __i;
0354     __r -= __n;
0355     return __r;
0356   }
0357
0358   _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type operator-(const __iterator& __x, const __iterator& __y)
0359     requires(sized_sentinel_for<iterator_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_Const, _Views>>> &&
0360              ...)
0361   {
0362     const auto __diffs = ranges::__tuple_zip_transform(minus<>(), __x.__current_, __y.__current_);
0363     return std::apply(
0364         [](auto... __ds) {
0365           return ranges::min({difference_type(__ds)...}, [](auto __a, auto __b) {
0366             return ranges::__abs(__a) < ranges::__abs(__b);
0367           });
0368         },
0369         __diffs);
0370   }
0371
0372   _LIBCPP_HIDE_FROM_ABI friend constexpr auto iter_move(const __iterator& __i) noexcept(
0373       (noexcept(ranges::iter_move(std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>())) && ...) &&
0374       (is_nothrow_move_constructible_v<range_rvalue_reference_t<__maybe_const<_Const, _Views>>> && ...)) {
0375     return ranges::__tuple_transform(ranges::iter_move, __i.__current_);
0376   }
0377
0378   _LIBCPP_HIDE_FROM_ABI friend constexpr void iter_swap(const __iterator& __l, const __iterator& __r) noexcept(
0379       (noexcept(ranges::iter_swap(std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>(),
0380                                   std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>())) &&
0381        ...))
0382     requires(indirectly_swappable<iterator_t<__maybe_const<_Const, _Views>>> && ...)
0383   {
0384     ranges::__tuple_zip_for_each(ranges::iter_swap, __l.__current_, __r.__current_);
0385   }
0386 };
0387
0388 template <input_range... _Views>
0389   requires(view<_Views> && ...) && (sizeof...(_Views) > 0)
0390 template <bool _Const>
0391 class zip_view<_Views...>::__sentinel {
0392   tuple<sentinel_t<__maybe_const<_Const, _Views>>...> __end_;
0393
0394   _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(tuple<sentinel_t<__maybe_const<_Const, _Views>>...> __end)
0395       : __end_(__end) {}
0396
0397   friend class zip_view<_Views...>;
0398
0399   // hidden friend cannot access private member of iterator because they are friends of friends
0400   template <bool _OtherConst>
0401   _LIBCPP_HIDE_FROM_ABI static constexpr decltype(auto)
0402   __iter_current(zip_view<_Views...>::__iterator<_OtherConst> const& __it) {
0403     return (__it.__current_);
0404   }
0405
0406 public:
0407   _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
0408
0409   _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __i)
0410     requires _Const && (convertible_to<sentinel_t<_Views>, sentinel_t<__maybe_const<_Const, _Views>>> && ...)
0411       : __end_(std::move(__i.__end_)) {}
0412
0413   template <bool _OtherConst>
0414     requires(sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
0415              ...)
0416   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
0417     return ranges::__tuple_any_equals(__iter_current(__x), __y.__end_);
0418   }
0419
0420   template <bool _OtherConst>
0421     requires(
0422         sized_sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
0423         ...)
0424   _LIBCPP_HIDE_FROM_ABI friend constexpr common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>
0425   operator-(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
0426     const auto __diffs = ranges::__tuple_zip_transform(minus<>(), __iter_current(__x), __y.__end_);
0427     return std::apply(
0428         [](auto... __ds) {
0429           using _Diff = common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>;
0430           return ranges::min({_Diff(__ds)...}, [](auto __a, auto __b) {
0431             return ranges::__abs(__a) < ranges::__abs(__b);
0432           });
0433         },
0434         __diffs);
0435   }
0436
0437   template <bool _OtherConst>
0438     requires(
0439         sized_sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&
0440         ...)
0441   _LIBCPP_HIDE_FROM_ABI friend constexpr common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>
0442   operator-(const __sentinel& __y, const __iterator<_OtherConst>& __x) {
0443     return -(__x - __y);
0444   }
0445 };
0446
0447 template <class... _Views>
0448 inline constexpr bool enable_borrowed_range<zip_view<_Views...>> = (enable_borrowed_range<_Views> && ...);
0449
0450 namespace views {
0451 namespace __zip {
0452
0453 struct __fn {
0454   _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()() noexcept { return empty_view<tuple<>>{}; }
0455
0456   template <class... _Ranges>
0457   _LIBCPP_HIDE_FROM_ABI static constexpr auto
0458   operator()(_Ranges&&... __rs) noexcept(noexcept(zip_view<all_t<_Ranges&&>...>(std::forward<_Ranges>(__rs)...)))
0459       -> decltype(zip_view<all_t<_Ranges&&>...>(std::forward<_Ranges>(__rs)...)) {
0460     return zip_view<all_t<_Ranges>...>(std::forward<_Ranges>(__rs)...);
0461   }
0462 };
0463
0464 } // namespace __zip
0465 inline namespace __cpo {
0466 inline constexpr auto zip = __zip::__fn{};
0467 } // namespace __cpo
0468 } // namespace views
0469 } // namespace ranges
0470
0471 #endif // _LIBCPP_STD_VER >= 23
0472
0473 _LIBCPP_END_NAMESPACE_STD
0474
0475 _LIBCPP_POP_MACROS
0476
0477 #endif // _LIBCPP___RANGES_ZIP_VIEW_H