508 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___RANGES_ZIP_VIEW_H11#define _LIBCPP___RANGES_ZIP_VIEW_H12 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 <__iterator/product_iterator.h>27#include <__ranges/access.h>28#include <__ranges/all.h>29#include <__ranges/concepts.h>30#include <__ranges/empty_view.h>31#include <__ranges/enable_borrowed_range.h>32#include <__ranges/size.h>33#include <__ranges/view_interface.h>34#include <__type_traits/is_nothrow_constructible.h>35#include <__type_traits/make_unsigned.h>36#include <__utility/declval.h>37#include <__utility/forward.h>38#include <__utility/integer_sequence.h>39#include <__utility/move.h>40#include <tuple>41 42#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)43# pragma GCC system_header44#endif45 46_LIBCPP_PUSH_MACROS47#include <__undef_macros>48 49_LIBCPP_BEGIN_NAMESPACE_STD50 51#if _LIBCPP_STD_VER >= 2352 53namespace ranges {54 55template <class... _Ranges>56concept __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 61template <class _Fun, class _Tuple>62_LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_transform(_Fun&& __f, _Tuple&& __tuple) {63 return std::apply(64 [&]<class... _Types>(_Types&&... __elements) {65 return tuple<invoke_result_t<_Fun&, _Types>...>(std::invoke(__f, std::forward<_Types>(__elements))...);66 },67 std::forward<_Tuple>(__tuple));68}69 70template <class _Fun, class _Tuple>71_LIBCPP_HIDE_FROM_ABI constexpr void __tuple_for_each(_Fun&& __f, _Tuple&& __tuple) {72 std::apply(73 [&]<class... _Types>(_Types&&... __elements) {74 (static_cast<void>(std::invoke(__f, std::forward<_Types>(__elements))), ...);75 },76 std::forward<_Tuple>(__tuple));77}78 79template <class _Fun, class _Tuple1, class _Tuple2, size_t... _Indices>80_LIBCPP_HIDE_FROM_ABI constexpr tuple<81 invoke_result_t<_Fun&,82 typename tuple_element<_Indices, remove_cvref_t<_Tuple1>>::type,83 typename tuple_element<_Indices, remove_cvref_t<_Tuple2>>::type>...>84__tuple_zip_transform(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2, index_sequence<_Indices...>) {85 return {std::invoke(__f,86 std::get<_Indices>(std::forward<_Tuple1>(__tuple1)),87 std::get<_Indices>(std::forward<_Tuple2>(__tuple2)))...};88}89 90template <class _Fun, class _Tuple1, class _Tuple2>91_LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_zip_transform(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2) {92 return ranges::__tuple_zip_transform(93 __f,94 std::forward<_Tuple1>(__tuple1),95 std::forward<_Tuple2>(__tuple2),96 std::make_index_sequence<tuple_size<remove_cvref_t<_Tuple1>>::value>());97}98 99template <class _Fun, class _Tuple1, class _Tuple2, size_t... _Indices>100_LIBCPP_HIDE_FROM_ABI constexpr void101__tuple_zip_for_each(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2, index_sequence<_Indices...>) {102 (std::invoke(103 __f, std::get<_Indices>(std::forward<_Tuple1>(__tuple1)), std::get<_Indices>(std::forward<_Tuple2>(__tuple2))),104 ...);105}106 107template <class _Fun, class _Tuple1, class _Tuple2>108_LIBCPP_HIDE_FROM_ABI constexpr auto __tuple_zip_for_each(_Fun&& __f, _Tuple1&& __tuple1, _Tuple2&& __tuple2) {109 return ranges::__tuple_zip_for_each(110 __f,111 std::forward<_Tuple1>(__tuple1),112 std::forward<_Tuple2>(__tuple2),113 std::make_index_sequence<tuple_size<remove_cvref_t<_Tuple1>>::value>());114}115 116template <class _Tuple1, class _Tuple2>117_LIBCPP_HIDE_FROM_ABI constexpr bool __tuple_any_equals(const _Tuple1& __tuple1, const _Tuple2& __tuple2) {118 const auto __equals = ranges::__tuple_zip_transform(std::equal_to<>(), __tuple1, __tuple2);119 return std::apply([](auto... __bools) { return (__bools || ...); }, __equals);120}121 122// abs in cstdlib is not constexpr123// TODO : remove __abs once P0533R9 is implemented.124template <class _Tp>125_LIBCPP_HIDE_FROM_ABI constexpr _Tp __abs(_Tp __t) {126 return __t < 0 ? -__t : __t;127}128 129template <input_range... _Views>130 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)131class zip_view : public view_interface<zip_view<_Views...>> {132 _LIBCPP_NO_UNIQUE_ADDRESS tuple<_Views...> __views_;133 134 template <bool>135 class __iterator;136 137 template <bool>138 class __sentinel;139 140public:141 _LIBCPP_HIDE_FROM_ABI zip_view() = default;142 143 _LIBCPP_HIDE_FROM_ABI constexpr explicit zip_view(_Views... __views) : __views_(std::move(__views)...) {}144 145 _LIBCPP_HIDE_FROM_ABI constexpr auto begin()146 requires(!(__simple_view<_Views> && ...))147 {148 return __iterator<false>(ranges::__tuple_transform(ranges::begin, __views_));149 }150 151 _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const152 requires(range<const _Views> && ...)153 {154 return __iterator<true>(ranges::__tuple_transform(ranges::begin, __views_));155 }156 157 _LIBCPP_HIDE_FROM_ABI constexpr auto end()158 requires(!(__simple_view<_Views> && ...))159 {160 if constexpr (!__zip_is_common<_Views...>) {161 return __sentinel<false>(ranges::__tuple_transform(ranges::end, __views_));162 } else if constexpr ((random_access_range<_Views> && ...)) {163 return begin() + iter_difference_t<__iterator<false>>(size());164 } else {165 return __iterator<false>(ranges::__tuple_transform(ranges::end, __views_));166 }167 }168 169 _LIBCPP_HIDE_FROM_ABI constexpr auto end() const170 requires(range<const _Views> && ...)171 {172 if constexpr (!__zip_is_common<const _Views...>) {173 return __sentinel<true>(ranges::__tuple_transform(ranges::end, __views_));174 } else if constexpr ((random_access_range<const _Views> && ...)) {175 return begin() + iter_difference_t<__iterator<true>>(size());176 } else {177 return __iterator<true>(ranges::__tuple_transform(ranges::end, __views_));178 }179 }180 181 _LIBCPP_HIDE_FROM_ABI constexpr auto size()182 requires(sized_range<_Views> && ...)183 {184 return std::apply(185 [](auto... __sizes) {186 using _CT = make_unsigned_t<common_type_t<decltype(__sizes)...>>;187 return ranges::min({_CT(__sizes)...});188 },189 ranges::__tuple_transform(ranges::size, __views_));190 }191 192 _LIBCPP_HIDE_FROM_ABI constexpr auto size() const193 requires(sized_range<const _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 204template <class... _Ranges>205zip_view(_Ranges&&...) -> zip_view<views::all_t<_Ranges>...>;206 207template <bool _Const, class... _Views>208concept __zip_all_random_access = (random_access_range<__maybe_const<_Const, _Views>> && ...);209 210template <bool _Const, class... _Views>211concept __zip_all_bidirectional = (bidirectional_range<__maybe_const<_Const, _Views>> && ...);212 213template <bool _Const, class... _Views>214concept __zip_all_forward = (forward_range<__maybe_const<_Const, _Views>> && ...);215 216template <bool _Const, class... _Views>217consteval auto __get_zip_view_iterator_tag() {218 if constexpr (__zip_all_random_access<_Const, _Views...>) {219 return random_access_iterator_tag();220 } else if constexpr (__zip_all_bidirectional<_Const, _Views...>) {221 return bidirectional_iterator_tag();222 } else if constexpr (__zip_all_forward<_Const, _Views...>) {223 return forward_iterator_tag();224 } else {225 return input_iterator_tag();226 }227}228 229template <bool _Const, class... _Views>230struct __zip_view_iterator_category_base {};231 232template <bool _Const, class... _Views>233 requires __zip_all_forward<_Const, _Views...>234struct __zip_view_iterator_category_base<_Const, _Views...> {235 using iterator_category = input_iterator_tag;236};237 238struct __zip_view_iterator_access {239 template <class _Iter>240 _LIBCPP_HIDE_FROM_ABI static constexpr decltype(auto) __get_underlying(_Iter& __iter) noexcept {241 return (__iter.__current_);242 }243};244 245template <input_range... _Views>246 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)247template <bool _Const>248class zip_view<_Views...>::__iterator : public __zip_view_iterator_category_base<_Const, _Views...> {249 tuple<iterator_t<__maybe_const<_Const, _Views>>...> __current_;250 251 _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(tuple<iterator_t<__maybe_const<_Const, _Views>>...> __current)252 : __current_(std::move(__current)) {}253 254 template <bool>255 friend class zip_view<_Views...>::__iterator;256 257 template <bool>258 friend class zip_view<_Views...>::__sentinel;259 260 friend class zip_view<_Views...>;261 262 static constexpr bool __is_zip_view_iterator = true;263 264 friend struct __product_iterator_traits<__iterator>;265 friend __zip_view_iterator_access;266 267public:268 using iterator_concept = decltype(ranges::__get_zip_view_iterator_tag<_Const, _Views...>());269 using value_type = tuple<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) const327 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 auto 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 __iterator operator+(const __iterator& __i, difference_type __n)350 requires __zip_all_random_access<_Const, _Views...>351 {352 auto __r = __i;353 __r += __n;354 return __r;355 }356 357 _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(difference_type __n, const __iterator& __i)358 requires __zip_all_random_access<_Const, _Views...>359 {360 return __i + __n;361 }362 363 _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator-(const __iterator& __i, difference_type __n)364 requires __zip_all_random_access<_Const, _Views...>365 {366 auto __r = __i;367 __r -= __n;368 return __r;369 }370 371 _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type operator-(const __iterator& __x, const __iterator& __y)372 requires(sized_sentinel_for<iterator_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_Const, _Views>>> &&373 ...)374 {375 const auto __diffs = ranges::__tuple_zip_transform(minus<>(), __x.__current_, __y.__current_);376 return std::apply(377 [](auto... __ds) {378 return ranges::min({difference_type(__ds)...}, [](auto __a, auto __b) {379 return ranges::__abs(__a) < ranges::__abs(__b);380 });381 },382 __diffs);383 }384 385 _LIBCPP_HIDE_FROM_ABI friend constexpr auto iter_move(const __iterator& __i) noexcept(386 (noexcept(ranges::iter_move(std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>())) && ...) &&387 (is_nothrow_move_constructible_v<range_rvalue_reference_t<__maybe_const<_Const, _Views>>> && ...)) {388 return ranges::__tuple_transform(ranges::iter_move, __i.__current_);389 }390 391 _LIBCPP_HIDE_FROM_ABI friend constexpr void iter_swap(const __iterator& __l, const __iterator& __r) noexcept(392 (noexcept(ranges::iter_swap(std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>(),393 std::declval<const iterator_t<__maybe_const<_Const, _Views>>&>())) &&394 ...))395 requires(indirectly_swappable<iterator_t<__maybe_const<_Const, _Views>>> && ...)396 {397 ranges::__tuple_zip_for_each(ranges::iter_swap, __l.__current_, __r.__current_);398 }399};400 401template <input_range... _Views>402 requires(view<_Views> && ...) && (sizeof...(_Views) > 0)403template <bool _Const>404class zip_view<_Views...>::__sentinel {405 tuple<sentinel_t<__maybe_const<_Const, _Views>>...> __end_;406 407 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(tuple<sentinel_t<__maybe_const<_Const, _Views>>...> __end)408 : __end_(__end) {}409 410 friend class zip_view<_Views...>;411 412 // hidden friend cannot access private member of iterator because they are friends of friends413 template <bool _OtherConst>414 _LIBCPP_HIDE_FROM_ABI static constexpr decltype(auto)415 __iter_current(zip_view<_Views...>::__iterator<_OtherConst> const& __it) {416 return (__it.__current_);417 }418 419public:420 _LIBCPP_HIDE_FROM_ABI __sentinel() = default;421 422 _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __i)423 requires _Const && (convertible_to<sentinel_t<_Views>, sentinel_t<__maybe_const<_Const, _Views>>> && ...)424 : __end_(std::move(__i.__end_)) {}425 426 template <bool _OtherConst>427 requires(sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&428 ...)429 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {430 return ranges::__tuple_any_equals(__iter_current(__x), __y.__end_);431 }432 433 template <bool _OtherConst>434 requires(435 sized_sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&436 ...)437 _LIBCPP_HIDE_FROM_ABI friend constexpr common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>438 operator-(const __iterator<_OtherConst>& __x, const __sentinel& __y) {439 const auto __diffs = ranges::__tuple_zip_transform(minus<>(), __iter_current(__x), __y.__end_);440 return std::apply(441 [](auto... __ds) {442 using _Diff = common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>;443 return ranges::min({_Diff(__ds)...}, [](auto __a, auto __b) {444 return ranges::__abs(__a) < ranges::__abs(__b);445 });446 },447 __diffs);448 }449 450 template <bool _OtherConst>451 requires(452 sized_sentinel_for<sentinel_t<__maybe_const<_Const, _Views>>, iterator_t<__maybe_const<_OtherConst, _Views>>> &&453 ...)454 _LIBCPP_HIDE_FROM_ABI friend constexpr common_type_t<range_difference_t<__maybe_const<_OtherConst, _Views>>...>455 operator-(const __sentinel& __y, const __iterator<_OtherConst>& __x) {456 return -(__x - __y);457 }458};459 460template <class... _Views>461inline constexpr bool enable_borrowed_range<zip_view<_Views...>> = (enable_borrowed_range<_Views> && ...);462 463namespace views {464namespace __zip {465 466struct __fn {467 _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()() noexcept { return empty_view<tuple<>>{}; }468 469 template <class... _Ranges>470 _LIBCPP_HIDE_FROM_ABI static constexpr auto471 operator()(_Ranges&&... __rs) noexcept(noexcept(zip_view<all_t<_Ranges&&>...>(std::forward<_Ranges>(__rs)...)))472 -> decltype(zip_view<all_t<_Ranges&&>...>(std::forward<_Ranges>(__rs)...)) {473 return zip_view<all_t<_Ranges>...>(std::forward<_Ranges>(__rs)...);474 }475};476 477} // namespace __zip478inline namespace __cpo {479inline constexpr auto zip = __zip::__fn{};480} // namespace __cpo481} // namespace views482} // namespace ranges483 484template <class _Iterator>485 requires _Iterator::__is_zip_view_iterator486struct __product_iterator_traits<_Iterator> {487 static constexpr size_t __size = tuple_size<decltype(std::declval<_Iterator>().__current_)>::value;488 489 template <size_t _Nth, class _Iter>490 requires(_Nth < __size)491 _LIBCPP_HIDE_FROM_ABI static constexpr decltype(auto) __get_iterator_element(_Iter&& __it) {492 return std::get<_Nth>(std::forward<_Iter>(__it).__current_);493 }494 495 template <class... _Iters>496 _LIBCPP_HIDE_FROM_ABI static constexpr _Iterator __make_product_iterator(_Iters&&... __iters) {497 return _Iterator(std::tuple(std::forward<_Iters>(__iters)...));498 }499};500 501#endif // _LIBCPP_STD_VER >= 23502 503_LIBCPP_END_NAMESPACE_STD504 505_LIBCPP_POP_MACROS506 507#endif // _LIBCPP___RANGES_ZIP_VIEW_H508