* [PATCH] libstdc++: Implement ranges::fold_* from P2322R6
@ 2023-04-14 4:00 Patrick Palka
2023-04-14 9:49 ` Jonathan Wakely
0 siblings, 1 reply; 2+ messages in thread
From: Patrick Palka @ 2023-04-14 4:00 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, Patrick Palka
Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h: Include <optional> for C++23.
(__cpp_lib_fold): Define for C++23.
(in_value_result): Likewise.
(__detail::__flipped): Likewise.
(__detail::__indirectly_binary_left_foldable_impl): Likewise.
(__detail::__indirectly_binary_left_foldable): Likewise.
(___detail:__indirectly_binary_right_foldable): Likewise.
(fold_left_with_iter_result): Likewise.
(__fold_left_with_iter_fn, fold_left_with_iter): Likewise.
(__fold_left_fn, fold_left): Likewise.
(__fold_left_first_with_iter_fn, fold_left_first_with_iter):
Likewise.
(__fold_left_first_fn, fold_left_first): Likewise.
(__fold_right_fn, fold_right): Likewise.
(__fold_right_last_fn, fold_right_last): Likewise.
* include/std/version (__cpp_lib_fold): Likewise.
* libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc: New test.
* libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc: New test.
---
libstdc++-v3/include/bits/ranges_algo.h | 251 ++++++++++++++++++
libstdc++-v3/include/std/version | 1 +
.../testsuite/25_algorithms/fold_left/1.cc | 73 +++++
.../testsuite/25_algorithms/fold_right/1.cc | 45 ++++
4 files changed, 370 insertions(+)
create mode 100644 libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc
create mode 100644 libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 5d039bd1cd4..f041ff16b0e 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -32,6 +32,9 @@
#if __cplusplus > 201703L
+#if __cplusplus > 202002L
+#include <optional>
+#endif
#include <bits/ranges_algobase.h>
#include <bits/ranges_util.h>
#include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator
@@ -3691,6 +3694,254 @@ namespace ranges
};
inline constexpr __find_last_if_not_fn find_last_if_not{};
+
+#define __cpp_lib_fold 202207L
+
+ template<typename _Iter, typename _Tp>
+ struct in_value_result
+ {
+ [[no_unique_address]] _Iter in;
+ [[no_unique_address]] _Tp value;
+
+ template<typename _Iter2, typename _Tp2>
+ requires convertible_to<const _Iter&, _Iter2>
+ && convertible_to<const _Tp&, _Tp2>
+ constexpr
+ operator in_value_result<_Iter2, _Tp2>() const &
+ { return {in, value}; }
+
+ template<typename _Iter2, typename _Tp2>
+ requires convertible_to<_Iter, _Iter2>
+ && convertible_to<_Tp, _Tp2>
+ constexpr
+ operator in_value_result<_Iter2, _Tp2>() &&
+ { return {std::move(in), std::move(value)}; }
+ };
+
+ namespace __detail
+ {
+ template<typename _Fp>
+ class __flipped
+ {
+ _Fp _M_f;
+
+ public:
+ template<typename _Tp, typename _Up>
+ requires invocable<_Fp&, _Up, _Tp>
+ invoke_result_t<_Fp&, _Up, _Tp>
+ operator()(_Tp&&, _Up&&); // not defined
+ };
+
+ template<typename _Fp, typename _Tp, typename _Iter, typename _Up>
+ concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
+ && convertible_to<_Tp, _Up>
+ && invocable<_Fp&, _Up, iter_reference_t<_Iter>>
+ && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
+
+ template<typename _Fp, typename _Tp, typename _Iter>
+ concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
+ && indirectly_readable<_Iter>
+ && invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
+ && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
+ decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>
+ && __indirectly_binary_left_foldable_impl
+ <_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>;
+
+ template <typename _Fp, typename _Tp, typename _Iter>
+ concept __indirectly_binary_right_foldable
+ = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
+ } // namespace __detail
+
+ template<typename _Iter, typename _Tp>
+ using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
+
+ struct __fold_left_with_iter_fn
+ {
+ template<typename _Ret_iter,
+ typename _Iter, typename _Sent, typename _Tp, typename _Fp>
+ static constexpr auto
+ _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
+ {
+ using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
+ using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
+
+ if (__first == __last)
+ return _Ret{std::move(__first), _Up(std::move(__init))};
+
+ _Up __accum = std::__invoke(__f, std::move(__init), *__first);
+ for (++__first; __first != __last; ++__first)
+ __accum = std::__invoke(__f, std::move(__accum), *__first);
+ return _Ret{std::move(__first), std::move(__accum)};
+ }
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
+ __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
+ constexpr auto
+ operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
+ {
+ using _Ret_iter = _Iter;
+ return _S_impl<_Ret_iter>(std::move(__first), __last,
+ std::move(__init), std::move(__f));
+ }
+
+ template<input_range _Range, typename _Tp,
+ __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
+ constexpr auto
+ operator()(_Range&& __r, _Tp __init, _Fp __f) const
+ {
+ using _Ret_iter = borrowed_iterator_t<_Range>;
+ return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
+ std::move(__init), std::move(__f));
+ }
+ };
+
+ inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
+
+ struct __fold_left_fn
+ {
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
+ __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
+ constexpr auto
+ operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
+ {
+ return ranges::fold_left_with_iter(std::move(__first), __last,
+ std::move(__init), std::move(__f)).value;
+ }
+
+ template<input_range _Range, typename _Tp,
+ __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
+ constexpr auto
+ operator()(_Range&& __r, _Tp __init, _Fp __f) const
+ { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
+ };
+
+ inline constexpr __fold_left_fn fold_left{};
+
+ template<typename _Iter, typename _Tp>
+ using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
+
+ struct __fold_left_first_with_iter_fn
+ {
+ template<typename _Ret_iter, typename _Iter, typename _Sent, typename _Fp>
+ static constexpr auto
+ _S_impl(_Iter __first, _Sent __last, _Fp __f)
+ {
+ using _Up = decltype(ranges::fold_left(std::move(__first), __last,
+ iter_value_t<_Iter>(*__first), __f));
+ using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
+
+ if (__first == __last)
+ return _Ret{std::move(__first), optional<_Up>()};
+
+ optional<_Up> __init(in_place, *__first);
+ for (++__first; __first != __last; ++__first)
+ *__init = std::__invoke(__f, std::move(*__init), *__first);
+ return _Ret{std::move(__first), std::move(__init)};
+ }
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
+ requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
+ constexpr auto
+ operator()(_Iter __first, _Sent __last, _Fp __f) const
+ {
+ using _Ret_iter = _Iter;
+ return _S_impl<_Ret_iter>(std::move(__first), __last, std::move(__f));
+ }
+
+ template<input_range _Range,
+ __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
+ requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
+ constexpr auto
+ operator()(_Range&& __r, _Fp __f) const
+ {
+ using _Ret_iter = borrowed_iterator_t<_Range>;
+ return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), std::move(__f));
+ }
+ };
+
+ inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
+
+ struct __fold_left_first_fn
+ {
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
+ requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
+ constexpr auto
+ operator()(_Iter __first, _Sent __last, _Fp __f) const
+ {
+ return ranges::fold_left_first_with_iter(std::move(__first), __last,
+ std::move(__f)).value;
+ }
+
+ template<input_range _Range,
+ __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
+ requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
+ constexpr auto
+ operator()(_Range&& __r, _Fp __f) const
+ { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
+ };
+
+ inline constexpr __fold_left_first_fn fold_left_first{};
+
+ struct __fold_right_fn
+ {
+ template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
+ __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
+ constexpr auto
+ operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
+ {
+ using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
+
+ if (__first == __last)
+ return _Up(std::move(__init));
+
+ _Iter __tail = ranges::next(__first, __last);
+ _Up __accum = std::__invoke(__f, *--__tail, std::move(__init));
+ while (__first != __tail)
+ __accum = std::__invoke(__f, *--__tail, std::move(__accum));
+ return __accum;
+ }
+
+ template<bidirectional_range _Range, typename _Tp,
+ __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
+ constexpr auto
+ operator()(_Range&& __r, _Tp __init, _Fp __f) const
+ { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
+ };
+
+ inline constexpr __fold_right_fn fold_right{};
+
+ struct __fold_right_last_fn
+ {
+ template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
+ __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
+ requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
+ constexpr auto
+ operator()(_Iter __first, _Sent __last, _Fp __f) const
+ {
+ using _Up = decltype(ranges::fold_right(__first, __last,
+ iter_value_t<_Iter>(*__first), __f));
+
+ if (__first == __last)
+ return optional<_Up>();
+
+ _Iter __tail = ranges::prev(ranges::next(__first, std::move(__last)));
+ return optional<_Up>(in_place,
+ ranges::fold_right(std::move(__first), __tail,
+ iter_value_t<_Iter>(*__tail),
+ std::move(__f)));
+ }
+
+ template<bidirectional_range _Range,
+ __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
+ requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
+ constexpr auto
+ operator()(_Range&& __r, _Fp __f) const
+ { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
+ };
+
+ inline constexpr __fold_right_last_fn fold_right_last{};
#endif // C++23
} // namespace ranges
diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version
index b35435c2669..d233b037d1a 100644
--- a/libstdc++-v3/include/std/version
+++ b/libstdc++-v3/include/std/version
@@ -340,6 +340,7 @@
#define __cpp_lib_ranges_cartesian_product 202207L
#define __cpp_lib_ranges_as_rvalue 202207L
#define __cpp_lib_ranges_enumerate 202302L
+#define __cpp_lib_fold 202207L
#if __cpp_constexpr_dynamic_alloc
# if _GLIBCXX_HOSTED
# define __cpp_lib_constexpr_bitset 202202L
diff --git a/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc b/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc
new file mode 100644
index 00000000000..5cc91b67d27
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc
@@ -0,0 +1,73 @@
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <algorithm>
+#include <ranges>
+#include <testsuite_iterators.h>
+
+#if __cpp_lib_fold != 202207L
+# error "Feature-test macro __cpp_lib_fold has wrong value in <algorithm>"
+#endif
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+constexpr bool
+test01()
+{
+ int x[] = {1, 2, 3, 4, 5};
+ auto f = [](int&& acc, int& x) {
+ return 2 * acc + x;
+ };
+ VERIFY( ranges::fold_left(x, 0, f) == 57 );
+ VERIFY( ranges::fold_left(x, 1, f) == 89 );
+ VERIFY( ranges::fold_left(x+0, x+0, 1, f) == 1 );
+
+ VERIFY( ranges::fold_left_first(x, f).value() == 57 );
+ VERIFY( !ranges::fold_left_first(x+0, x+0, f).has_value() );
+
+ return true;
+}
+
+void
+test02()
+{
+ int x[] = {1, 2, 3, 4, 5};
+ auto f = [](int&& acc, int& x) {
+ return 2 * acc + x;
+ };
+
+ __gnu_test::test_input_range<int> rx(x);
+ ranges::in_value_result ivr = ranges::fold_left_with_iter(rx, 0, f);
+ VERIFY( ivr.in == rx.end() );
+ VERIFY( ivr.value == 57 );
+
+ rx.bounds.first = x;
+ ranges::in_value_result ivr2 = ranges::fold_left_first_with_iter(rx, f);
+ VERIFY( ivr2.in == rx.end() );
+ VERIFY( ivr2.value.value() == 57 );
+
+ rx.bounds.first = x;
+ auto v = rx | views::take(0);
+ ranges::in_value_result ivr3 = ranges::fold_left_first_with_iter(v, f);
+ VERIFY( ivr3.in == v.end() );
+ VERIFY( !ivr3.value.has_value() );
+}
+
+constexpr bool
+test03()
+{
+ double x[] = {0.5, 0.25, 0.125, 0.125};
+ VERIFY( ranges::fold_left(x, 0, std::plus{}) == 1.0 );
+ VERIFY( ranges::fold_left_with_iter(x, 0, std::plus{}).value == 1.0 );
+
+ return true;
+}
+
+int
+main()
+{
+ static_assert(test01());
+ test02();
+ static_assert(test03());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc b/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc
new file mode 100644
index 00000000000..b08b57c6364
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc
@@ -0,0 +1,45 @@
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <algorithm>
+#include <ranges>
+#include <testsuite_iterators.h>
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+constexpr bool
+test01()
+{
+ int x[] = {1, 2, 3, 4, 5};
+ auto v = x | views::filter([](int) { return true; });
+ static_assert( ranges::bidirectional_range<decltype(v)>
+ && !ranges::random_access_range<decltype(v)> );
+ auto f = [](int& x, int&& acc) {
+ return 2 * acc + x;
+ };
+ VERIFY( ranges::fold_right(v, 0, f) == 129 );
+ VERIFY( ranges::fold_right(v, 1, f) == 161 );
+ VERIFY( ranges::fold_right(v.begin(), v.begin(), 1, f) == 1 );
+
+ VERIFY( ranges::fold_right_last(v, f).value() == 129 );
+ VERIFY( !ranges::fold_right_last(v.begin(), v.begin(), f).has_value() );
+
+ return true;
+}
+
+constexpr bool
+test02()
+{
+ double x[] = {0.5, 0.25, 0.125, 0.125};
+ VERIFY( ranges::fold_right(x, 0, std::plus{}) == 1.0 );
+
+ return true;
+}
+
+int
+main()
+{
+ static_assert(test01());
+ static_assert(test02());
+}
--
2.40.0.335.g9857273be0
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] libstdc++: Implement ranges::fold_* from P2322R6
2023-04-14 4:00 [PATCH] libstdc++: Implement ranges::fold_* from P2322R6 Patrick Palka
@ 2023-04-14 9:49 ` Jonathan Wakely
0 siblings, 0 replies; 2+ messages in thread
From: Jonathan Wakely @ 2023-04-14 9:49 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
On Fri, 14 Apr 2023 at 05:01, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
OK, looks good, thanks.
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/ranges_algo.h: Include <optional> for C++23.
> (__cpp_lib_fold): Define for C++23.
> (in_value_result): Likewise.
> (__detail::__flipped): Likewise.
> (__detail::__indirectly_binary_left_foldable_impl): Likewise.
> (__detail::__indirectly_binary_left_foldable): Likewise.
> (___detail:__indirectly_binary_right_foldable): Likewise.
> (fold_left_with_iter_result): Likewise.
> (__fold_left_with_iter_fn, fold_left_with_iter): Likewise.
> (__fold_left_fn, fold_left): Likewise.
> (__fold_left_first_with_iter_fn, fold_left_first_with_iter):
> Likewise.
> (__fold_left_first_fn, fold_left_first): Likewise.
> (__fold_right_fn, fold_right): Likewise.
> (__fold_right_last_fn, fold_right_last): Likewise.
> * include/std/version (__cpp_lib_fold): Likewise.
> * libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc: New test.
> * libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc: New test.
> ---
> libstdc++-v3/include/bits/ranges_algo.h | 251 ++++++++++++++++++
> libstdc++-v3/include/std/version | 1 +
> .../testsuite/25_algorithms/fold_left/1.cc | 73 +++++
> .../testsuite/25_algorithms/fold_right/1.cc | 45 ++++
> 4 files changed, 370 insertions(+)
> create mode 100644 libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc
> create mode 100644 libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> index 5d039bd1cd4..f041ff16b0e 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -32,6 +32,9 @@
>
> #if __cplusplus > 201703L
>
> +#if __cplusplus > 202002L
> +#include <optional>
> +#endif
> #include <bits/ranges_algobase.h>
> #include <bits/ranges_util.h>
> #include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator
> @@ -3691,6 +3694,254 @@ namespace ranges
> };
>
> inline constexpr __find_last_if_not_fn find_last_if_not{};
> +
> +#define __cpp_lib_fold 202207L
> +
> + template<typename _Iter, typename _Tp>
> + struct in_value_result
> + {
> + [[no_unique_address]] _Iter in;
> + [[no_unique_address]] _Tp value;
> +
> + template<typename _Iter2, typename _Tp2>
> + requires convertible_to<const _Iter&, _Iter2>
> + && convertible_to<const _Tp&, _Tp2>
> + constexpr
> + operator in_value_result<_Iter2, _Tp2>() const &
> + { return {in, value}; }
> +
> + template<typename _Iter2, typename _Tp2>
> + requires convertible_to<_Iter, _Iter2>
> + && convertible_to<_Tp, _Tp2>
> + constexpr
> + operator in_value_result<_Iter2, _Tp2>() &&
> + { return {std::move(in), std::move(value)}; }
> + };
> +
> + namespace __detail
> + {
> + template<typename _Fp>
> + class __flipped
> + {
> + _Fp _M_f;
> +
> + public:
> + template<typename _Tp, typename _Up>
> + requires invocable<_Fp&, _Up, _Tp>
> + invoke_result_t<_Fp&, _Up, _Tp>
> + operator()(_Tp&&, _Up&&); // not defined
> + };
> +
> + template<typename _Fp, typename _Tp, typename _Iter, typename _Up>
> + concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
> + && convertible_to<_Tp, _Up>
> + && invocable<_Fp&, _Up, iter_reference_t<_Iter>>
> + && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
> +
> + template<typename _Fp, typename _Tp, typename _Iter>
> + concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
> + && indirectly_readable<_Iter>
> + && invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
> + && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
> + decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>
> + && __indirectly_binary_left_foldable_impl
> + <_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>;
> +
> + template <typename _Fp, typename _Tp, typename _Iter>
> + concept __indirectly_binary_right_foldable
> + = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
> + } // namespace __detail
> +
> + template<typename _Iter, typename _Tp>
> + using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
> +
> + struct __fold_left_with_iter_fn
> + {
> + template<typename _Ret_iter,
> + typename _Iter, typename _Sent, typename _Tp, typename _Fp>
> + static constexpr auto
> + _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
> + {
> + using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
> + using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
> +
> + if (__first == __last)
> + return _Ret{std::move(__first), _Up(std::move(__init))};
> +
> + _Up __accum = std::__invoke(__f, std::move(__init), *__first);
> + for (++__first; __first != __last; ++__first)
> + __accum = std::__invoke(__f, std::move(__accum), *__first);
> + return _Ret{std::move(__first), std::move(__accum)};
> + }
> +
> + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
> + __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
> + constexpr auto
> + operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
> + {
> + using _Ret_iter = _Iter;
> + return _S_impl<_Ret_iter>(std::move(__first), __last,
> + std::move(__init), std::move(__f));
> + }
> +
> + template<input_range _Range, typename _Tp,
> + __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
> + constexpr auto
> + operator()(_Range&& __r, _Tp __init, _Fp __f) const
> + {
> + using _Ret_iter = borrowed_iterator_t<_Range>;
> + return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
> + std::move(__init), std::move(__f));
> + }
> + };
> +
> + inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
> +
> + struct __fold_left_fn
> + {
> + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
> + __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
> + constexpr auto
> + operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
> + {
> + return ranges::fold_left_with_iter(std::move(__first), __last,
> + std::move(__init), std::move(__f)).value;
> + }
> +
> + template<input_range _Range, typename _Tp,
> + __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
> + constexpr auto
> + operator()(_Range&& __r, _Tp __init, _Fp __f) const
> + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
> + };
> +
> + inline constexpr __fold_left_fn fold_left{};
> +
> + template<typename _Iter, typename _Tp>
> + using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
> +
> + struct __fold_left_first_with_iter_fn
> + {
> + template<typename _Ret_iter, typename _Iter, typename _Sent, typename _Fp>
> + static constexpr auto
> + _S_impl(_Iter __first, _Sent __last, _Fp __f)
> + {
> + using _Up = decltype(ranges::fold_left(std::move(__first), __last,
> + iter_value_t<_Iter>(*__first), __f));
> + using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
> +
> + if (__first == __last)
> + return _Ret{std::move(__first), optional<_Up>()};
> +
> + optional<_Up> __init(in_place, *__first);
> + for (++__first; __first != __last; ++__first)
> + *__init = std::__invoke(__f, std::move(*__init), *__first);
> + return _Ret{std::move(__first), std::move(__init)};
> + }
> +
> + template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
> + __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
> + requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
> + constexpr auto
> + operator()(_Iter __first, _Sent __last, _Fp __f) const
> + {
> + using _Ret_iter = _Iter;
> + return _S_impl<_Ret_iter>(std::move(__first), __last, std::move(__f));
> + }
> +
> + template<input_range _Range,
> + __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
> + requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
> + constexpr auto
> + operator()(_Range&& __r, _Fp __f) const
> + {
> + using _Ret_iter = borrowed_iterator_t<_Range>;
> + return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), std::move(__f));
> + }
> + };
> +
> + inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
> +
> + struct __fold_left_first_fn
> + {
> + template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
> + __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
> + requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
> + constexpr auto
> + operator()(_Iter __first, _Sent __last, _Fp __f) const
> + {
> + return ranges::fold_left_first_with_iter(std::move(__first), __last,
> + std::move(__f)).value;
> + }
> +
> + template<input_range _Range,
> + __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
> + requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
> + constexpr auto
> + operator()(_Range&& __r, _Fp __f) const
> + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
> + };
> +
> + inline constexpr __fold_left_first_fn fold_left_first{};
> +
> + struct __fold_right_fn
> + {
> + template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
> + __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
> + constexpr auto
> + operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
> + {
> + using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
> +
> + if (__first == __last)
> + return _Up(std::move(__init));
> +
> + _Iter __tail = ranges::next(__first, __last);
> + _Up __accum = std::__invoke(__f, *--__tail, std::move(__init));
> + while (__first != __tail)
> + __accum = std::__invoke(__f, *--__tail, std::move(__accum));
> + return __accum;
> + }
> +
> + template<bidirectional_range _Range, typename _Tp,
> + __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
> + constexpr auto
> + operator()(_Range&& __r, _Tp __init, _Fp __f) const
> + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
> + };
> +
> + inline constexpr __fold_right_fn fold_right{};
> +
> + struct __fold_right_last_fn
> + {
> + template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
> + __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
> + requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
> + constexpr auto
> + operator()(_Iter __first, _Sent __last, _Fp __f) const
> + {
> + using _Up = decltype(ranges::fold_right(__first, __last,
> + iter_value_t<_Iter>(*__first), __f));
> +
> + if (__first == __last)
> + return optional<_Up>();
> +
> + _Iter __tail = ranges::prev(ranges::next(__first, std::move(__last)));
> + return optional<_Up>(in_place,
> + ranges::fold_right(std::move(__first), __tail,
> + iter_value_t<_Iter>(*__tail),
> + std::move(__f)));
> + }
> +
> + template<bidirectional_range _Range,
> + __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
> + requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
> + constexpr auto
> + operator()(_Range&& __r, _Fp __f) const
> + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
> + };
> +
> + inline constexpr __fold_right_last_fn fold_right_last{};
> #endif // C++23
> } // namespace ranges
>
> diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version
> index b35435c2669..d233b037d1a 100644
> --- a/libstdc++-v3/include/std/version
> +++ b/libstdc++-v3/include/std/version
> @@ -340,6 +340,7 @@
> #define __cpp_lib_ranges_cartesian_product 202207L
> #define __cpp_lib_ranges_as_rvalue 202207L
> #define __cpp_lib_ranges_enumerate 202302L
> +#define __cpp_lib_fold 202207L
> #if __cpp_constexpr_dynamic_alloc
> # if _GLIBCXX_HOSTED
> # define __cpp_lib_constexpr_bitset 202202L
> diff --git a/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc b/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc
> new file mode 100644
> index 00000000000..5cc91b67d27
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc
> @@ -0,0 +1,73 @@
> +// { dg-options "-std=gnu++23" }
> +// { dg-do run { target c++23 } }
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <testsuite_iterators.h>
> +
> +#if __cpp_lib_fold != 202207L
> +# error "Feature-test macro __cpp_lib_fold has wrong value in <algorithm>"
> +#endif
> +
> +namespace ranges = std::ranges;
> +namespace views = std::views;
> +
> +constexpr bool
> +test01()
> +{
> + int x[] = {1, 2, 3, 4, 5};
> + auto f = [](int&& acc, int& x) {
> + return 2 * acc + x;
> + };
> + VERIFY( ranges::fold_left(x, 0, f) == 57 );
> + VERIFY( ranges::fold_left(x, 1, f) == 89 );
> + VERIFY( ranges::fold_left(x+0, x+0, 1, f) == 1 );
> +
> + VERIFY( ranges::fold_left_first(x, f).value() == 57 );
> + VERIFY( !ranges::fold_left_first(x+0, x+0, f).has_value() );
> +
> + return true;
> +}
> +
> +void
> +test02()
> +{
> + int x[] = {1, 2, 3, 4, 5};
> + auto f = [](int&& acc, int& x) {
> + return 2 * acc + x;
> + };
> +
> + __gnu_test::test_input_range<int> rx(x);
> + ranges::in_value_result ivr = ranges::fold_left_with_iter(rx, 0, f);
> + VERIFY( ivr.in == rx.end() );
> + VERIFY( ivr.value == 57 );
> +
> + rx.bounds.first = x;
> + ranges::in_value_result ivr2 = ranges::fold_left_first_with_iter(rx, f);
> + VERIFY( ivr2.in == rx.end() );
> + VERIFY( ivr2.value.value() == 57 );
> +
> + rx.bounds.first = x;
> + auto v = rx | views::take(0);
> + ranges::in_value_result ivr3 = ranges::fold_left_first_with_iter(v, f);
> + VERIFY( ivr3.in == v.end() );
> + VERIFY( !ivr3.value.has_value() );
> +}
> +
> +constexpr bool
> +test03()
> +{
> + double x[] = {0.5, 0.25, 0.125, 0.125};
> + VERIFY( ranges::fold_left(x, 0, std::plus{}) == 1.0 );
> + VERIFY( ranges::fold_left_with_iter(x, 0, std::plus{}).value == 1.0 );
> +
> + return true;
> +}
> +
> +int
> +main()
> +{
> + static_assert(test01());
> + test02();
> + static_assert(test03());
> +}
> diff --git a/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc b/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc
> new file mode 100644
> index 00000000000..b08b57c6364
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc
> @@ -0,0 +1,45 @@
> +// { dg-options "-std=gnu++23" }
> +// { dg-do run { target c++23 } }
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <testsuite_iterators.h>
> +
> +namespace ranges = std::ranges;
> +namespace views = std::views;
> +
> +constexpr bool
> +test01()
> +{
> + int x[] = {1, 2, 3, 4, 5};
> + auto v = x | views::filter([](int) { return true; });
> + static_assert( ranges::bidirectional_range<decltype(v)>
> + && !ranges::random_access_range<decltype(v)> );
> + auto f = [](int& x, int&& acc) {
> + return 2 * acc + x;
> + };
> + VERIFY( ranges::fold_right(v, 0, f) == 129 );
> + VERIFY( ranges::fold_right(v, 1, f) == 161 );
> + VERIFY( ranges::fold_right(v.begin(), v.begin(), 1, f) == 1 );
> +
> + VERIFY( ranges::fold_right_last(v, f).value() == 129 );
> + VERIFY( !ranges::fold_right_last(v.begin(), v.begin(), f).has_value() );
> +
> + return true;
> +}
> +
> +constexpr bool
> +test02()
> +{
> + double x[] = {0.5, 0.25, 0.125, 0.125};
> + VERIFY( ranges::fold_right(x, 0, std::plus{}) == 1.0 );
> +
> + return true;
> +}
> +
> +int
> +main()
> +{
> + static_assert(test01());
> + static_assert(test02());
> +}
> --
> 2.40.0.335.g9857273be0
>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-04-14 9:49 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-04-14 4:00 [PATCH] libstdc++: Implement ranges::fold_* from P2322R6 Patrick Palka
2023-04-14 9:49 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).