From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1888) id 886533858D1E; Thu, 1 Sep 2022 13:56:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 886533858D1E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1662040567; bh=1oWWRQqE2Ob+k/oGaxahE84oDSi2bnvqUlXEowwCSPQ=; h=From:To:Subject:Date:From; b=vWepR+fvu2bnrLnfVTEwomnLIkZ/o2okCSfxRwHZFz5/MZpuhqY57k6pe7x+KjOaZ spcMIeOgu+5Bt6M2Ul0bhghPbOdN/i+crYvZ35Wdf+rnkg4fJ8Cx3ay9dm9X8Mobmu JxJELS1VYJfysP1+0fOBTHzwKZYOlszCBTq4y7HQ= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Patrick Palka To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r13-2343] libstdc++: Implement ranges::adjacent_transform_view from P2321R2 X-Act-Checkin: gcc X-Git-Author: Patrick Palka X-Git-Refname: refs/heads/master X-Git-Oldrev: 47e15513c9e581ef04ad25fb0d561a45d345edd1 X-Git-Newrev: 0cb8d96157a95b7619ef1ccf28051181415fe989 Message-Id: <20220901135607.886533858D1E@sourceware.org> Date: Thu, 1 Sep 2022 13:56:07 +0000 (GMT) List-Id: https://gcc.gnu.org/g:0cb8d96157a95b7619ef1ccf28051181415fe989 commit r13-2343-g0cb8d96157a95b7619ef1ccf28051181415fe989 Author: Patrick Palka Date: Thu Sep 1 09:54:57 2022 -0400 libstdc++: Implement ranges::adjacent_transform_view from P2321R2 libstdc++-v3/ChangeLog: * include/std/ranges (__detail::__unarize): Define. (adjacent_view::_Iterator): Befriend adjacent_transform_view. (adjacent_transform_view): Define. (adjacent_transform_view::_Iterator): Define. (adjacent_transform_view::_Sentinel): Define. (views::__detail::__can_adjacent_transform_view): Define. (views::_AdjacentTransform): Define. (views::adjacent_transform): Define. (views::pairwise_transform): Define. * testsuite/std/ranges/adaptors/adjacent_transform/1.cc: New test. Diff: --- libstdc++-v3/include/std/ranges | 341 +++++++++++++++++++++ .../std/ranges/adaptors/adjacent_transform/1.cc | 106 +++++++ 2 files changed, 447 insertions(+) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 39822b71b94..dad1e4c9f93 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -5156,6 +5156,20 @@ namespace views::__adaptor // Yields tuple<_Tp, ..., _Tp> with _Nm elements. template using __repeated_tuple = decltype(std::tuple_cat(std::declval>())); + + // For a functor F that is callable with N arguments, the expression + // declval<__unarize>(x) is equivalent to declval(x, ..., x). + template + struct __unarize + { + template + static invoke_result_t<_Fp, _Ts...> + __tuple_apply(const tuple<_Ts...>&); // not defined + + template + decltype(__tuple_apply(std::declval<__repeated_tuple<_Tp, _Nm>>())) + operator()(_Tp&&); // not defined + }; } template @@ -5203,6 +5217,13 @@ namespace views::__adaptor friend class adjacent_view; + template + requires view<_Wp> && (_Mm > 0) && is_object_v<_Fp> + && regular_invocable<__detail::__unarize<_Fp&, _Mm>, range_reference_t<_Wp>> + && std::__detail::__can_reference, + range_reference_t<_Wp>>> + friend class adjacent_transform_view; + public: using iterator_category = input_iterator_tag; using iterator_concept = decltype(_S_iter_concept()); @@ -5437,6 +5458,326 @@ namespace views::__adaptor inline constexpr auto pairwise = adjacent<2>; } + + template + requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> + && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> + && std::__detail::__can_reference, + range_reference_t<_Vp>>> + class adjacent_transform_view : public view_interface> + { + [[no_unique_address]] __detail::__box<_Fp> _M_fun; + adjacent_view<_Vp, _Nm> _M_inner; + + using _InnerView = adjacent_view<_Vp, _Nm>; + + template + using _InnerIter = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>; + + template + using _InnerSent = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>; + + template class _Iterator; + template class _Sentinel; + + public: + adjacent_transform_view() = default; + + constexpr explicit + adjacent_transform_view(_Vp __base, _Fp __fun) + : _M_fun(std::move(__fun)), _M_inner(std::move(__base)) + { } + + constexpr auto + begin() + { return _Iterator(*this, _M_inner.begin()); } + + constexpr auto + begin() const + requires range + && regular_invocable<__detail::__unarize, + range_reference_t> + { return _Iterator(*this, _M_inner.begin()); } + + constexpr auto + end() + { + if constexpr (common_range<_InnerView>) + return _Iterator(*this, _M_inner.end()); + else + return _Sentinel(_M_inner.end()); + } + + constexpr auto + end() const + requires range + && regular_invocable<__detail::__unarize, + range_reference_t> + { + if constexpr (common_range) + return _Iterator(*this, _M_inner.end()); + else + return _Sentinel(_M_inner.end()); + } + + constexpr auto + size() requires sized_range<_InnerView> + { return _M_inner.size(); } + + constexpr auto + size() const requires sized_range + { return _M_inner.size(); } + }; + + template + requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> + && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> + && std::__detail::__can_reference, + range_reference_t<_Vp>>> + template + class adjacent_transform_view<_Vp, _Fp, _Nm>::_Iterator + { + using _Parent = __detail::__maybe_const_t<_Const, adjacent_transform_view>; + using _Base = __detail::__maybe_const_t<_Const, _Vp>; + + _Parent* _M_parent = nullptr; + _InnerIter<_Const> _M_inner; + + constexpr + _Iterator(_Parent& __parent, _InnerIter<_Const> __inner) + : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner)) + { } + + static auto + _S_iter_cat() + { + using __detail::__maybe_const_t; + using __detail::__unarize; + using _Res = invoke_result_t<__unarize<__maybe_const_t<_Const, _Fp>&, _Nm>, + range_reference_t<_Base>>; + using _Cat = iterator_traits>::iterator_category; + if constexpr (!is_lvalue_reference_v<_Res>) + return input_iterator_tag{}; + else if constexpr (derived_from<_Cat, random_access_iterator_tag>) + return random_access_iterator_tag{}; + else if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) + return bidirectional_iterator_tag{}; + else if constexpr (derived_from<_Cat, forward_iterator_tag>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + friend class adjacent_transform_view; + + public: + using iterator_category = decltype(_S_iter_cat()); + using iterator_concept = typename _InnerIter<_Const>::iterator_concept; + using value_type + = remove_cvref_t&, _Nm>, + range_reference_t<_Base>>>; + using difference_type = range_difference_t<_Base>; + + _Iterator() = default; + + constexpr + _Iterator(_Iterator __i) + requires _Const && convertible_to<_InnerIter, _InnerIter<_Const>> + : _M_parent(__i._M_parent), _M_inner(std::move(__i._M_inner)) + { } + + constexpr decltype(auto) + operator*() const + { + return std::apply([&](const auto&... __iters) -> decltype(auto) { + return std::__invoke(*_M_parent->_M_fun, *__iters...); + }, _M_inner._M_current); + } + + constexpr _Iterator& + operator++() + { + ++_M_inner; + return *this; + } + + constexpr _Iterator + operator++(int) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Base> + { + --_M_inner; + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Base> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __x) requires random_access_range<_Base> + { + _M_inner += __x; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __x) requires random_access_range<_Base> + { + _M_inner -= __x; + return *this; + } + + constexpr decltype(auto) + operator[](difference_type __n) const requires random_access_range<_Base> + { + return std::apply([&](const auto&... __iters) -> decltype(auto) { + return std::__invoke(*_M_parent->_M_fun, __iters[__n]...); + }, _M_inner._M_current); + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + { return __x._M_inner == __y._M_inner; } + + friend constexpr bool + operator<(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_inner < __y._M_inner; } + + friend constexpr bool + operator>(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_inner > __y._M_inner; } + + friend constexpr bool + operator<=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_inner <= __y._M_inner; } + + friend constexpr bool + operator>=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_inner >= __y._M_inner; } + + friend constexpr auto + operator<=>(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> && + three_way_comparable<_InnerIter<_Const>> + { return __x._M_inner <=> __y._M_inner; } + + friend constexpr _Iterator + operator+(const _Iterator& __i, difference_type __n) + requires random_access_range<_Base> + { return _Iterator(*__i._M_parent, __i._M_inner + __n); } + + friend constexpr _Iterator + operator+(difference_type __n, const _Iterator& __i) + requires random_access_range<_Base> + { return _Iterator(*__i._M_parent, __i._M_inner + __n); } + + friend constexpr _Iterator + operator-(const _Iterator& __i, difference_type __n) + requires random_access_range<_Base> + { return _Iterator(*__i._M_parent, __i._M_inner - __n); } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires sized_sentinel_for<_InnerIter<_Const>, _InnerIter<_Const>> + { return __x._M_inner - __y._M_inner; } + }; + + template + requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> + && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> + && std::__detail::__can_reference, + range_reference_t<_Vp>>> + template + class adjacent_transform_view<_Vp, _Fp, _Nm>::_Sentinel + { + _InnerSent<_Const> _M_inner; + + constexpr explicit + _Sentinel(_InnerSent<_Const> __inner) + : _M_inner(__inner) + { } + + friend class adjacent_transform_view; + + public: + _Sentinel() = default; + + constexpr + _Sentinel(_Sentinel __i) + requires _Const && convertible_to<_InnerSent, _InnerSent<_Const>> + : _M_inner(std::move(__i._M_inner)) + { } + + template + requires sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> + friend constexpr bool + operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) + { return __x._M_inner == __y._M_inner; } + + template + requires sized_sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> + friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>> + operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) + { return __x._M_inner - __y._M_inner; } + + template + requires sized_sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> + friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>> + operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y) + { return __x._M_inner - __y._M_inner; } + }; + + namespace views + { + namespace __detail + { + template + concept __can_adjacent_transform_view + = requires { adjacent_transform_view, decay_t<_Fp>, _Nm> + (std::declval<_Range>(), std::declval<_Fp>()); }; + } + + template + struct _AdjacentTransform : __adaptor::_RangeAdaptor<_AdjacentTransform<_Nm>> + { + template + requires (_Nm == 0) || __detail::__can_adjacent_transform_view<_Nm, _Range, _Fp> + constexpr auto + operator() [[nodiscard]] (_Range&& __r, _Fp&& __f) const + { + if constexpr (_Nm == 0) + return views::empty>; + else + return adjacent_transform_view, decay_t<_Fp>, _Nm> + (std::forward<_Range>(__r), std::forward<_Fp>(__f)); + } + + using __adaptor::_RangeAdaptor<_AdjacentTransform>::operator(); + static constexpr int _S_arity = 2; + static constexpr bool _S_has_simple_extra_args = true; + }; + + template + inline constexpr _AdjacentTransform<_Nm> adjacent_transform; + + inline constexpr auto pairwise_transform = adjacent_transform<2>; + } #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc new file mode 100644 index 00000000000..07f20b702dd --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc @@ -0,0 +1,106 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include +#include +#include +#include +#include + +namespace ranges = std::ranges; +namespace views = std::views; + +constexpr bool +test01() +{ + auto v1 = std::array{1, 2, 3} | views::adjacent_transform<1>(std::identity{}); + VERIFY( ranges::equal(v1, (int[]){1, 2, 3}) ); + const auto i0 = v1.begin(), i1 = v1.begin() + 1; + VERIFY( i0 + 1 - 1 == i0 ); + VERIFY( i0 < i1 ); + VERIFY( i1 < v1.end() ); + VERIFY( i1 - i0 == 1 ); + VERIFY( i0 - i1 == -1 ); + VERIFY( v1.end() - i1 == 2 ); + VERIFY( i1 - v1.end() == -2 ); + ranges::iter_swap(i0, i1); + VERIFY( ranges::equal(std::move(v1), (int[]){2, 1, 3}) ); + + auto v2 = std::array{1, -1, 2, -2} | views::pairwise_transform(std::multiplies{}); + auto i2 = v2.begin(); + i2 += 1; + i2 -= -2; + VERIFY( i2 == v2.end() ); + VERIFY( ranges::size(v2) == 3 ); + VERIFY( ranges::size(std::as_const(v2)) == 3 ); + VERIFY( ranges::equal(v2, (int[]){-1, -2, -4}) ); + + int y[] = {1, 2, 3, 4, 5, 6}; + auto v3 = y | views::adjacent_transform<3>([](auto... xs) { return ranges::max({xs...}); }); + VERIFY( ranges::size(v3) == 4 ); + VERIFY( ranges::equal(v3, (int[]){3, 4, 5, 6}) ); + + const auto v6 = y | views::adjacent_transform<6>([](auto...) { return 0; }); + VERIFY( ranges::equal(v6, (int[]){0}) ); + + const auto v7 = y | views::adjacent_transform<7>([](auto...) { return 0; }); + VERIFY( ranges::empty(v7) ); + + const auto v0 = y | views::adjacent_transform<0>([] { return 0; }); + VERIFY( ranges::empty(v0) ); + + return true; +} + +constexpr bool +test02() +{ + using __gnu_test::test_input_range; + using __gnu_test::test_forward_range; + using __gnu_test::test_random_access_range; + + using ty1 = ranges::adjacent_transform_view>, + std::plus<>, 2>; + static_assert(ranges::forward_range); + static_assert(!ranges::bidirectional_range); + static_assert(!ranges::sized_range); + + using ty2 = ranges::adjacent_transform_view>, + decltype([](int, int, int) { return 0;}), 3>; + static_assert(ranges::random_access_range); + static_assert(ranges::sized_range); + + return true; +} + +constexpr bool +test03() +{ + auto v = views::iota(0, 4) + | views::filter([](auto) { return true; }) + | views::pairwise_transform(std::plus{}); + using ty = decltype(v); + static_assert(ranges::forward_range); + static_assert(ranges::common_range); + static_assert(!ranges::sized_range); + VERIFY( v.begin() == v.begin() ); + VERIFY( v.begin() != v.end() ); + VERIFY( ranges::next(v.begin(), 3) == v.end() ); + auto it = v.begin(); + ++it; + it++; + VERIFY( ranges::next(it) == v.end() ); + it--; + --it; + VERIFY( it == v.begin() ); + + return true; +} + +int +main() +{ + static_assert(test01()); + static_assert(test02()); + static_assert(test03()); +}