From f3169941996c76ecbfae9c37709d2b57652be555 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Mon, 17 Feb 2020 11:50:29 -0500 Subject: [PATCH] libstdc++: P1243R4 Rangify new algorithms This adds rangified overloads for for_each_n, sample and clamp as per P1243R4. libstdc++-v3/ChangeLog: P1243R4 Rangify new algorithms * include/bits/ranges_algo.h (for_each_n_result, __for_each_n_fn, for_each_n, __sample_fn, sample, __clamp_fn, clamp): New. * testsuite/25_algorithms/clamp/constrained.cc: New test. * testsuite/25_algorithms/for_each/constrained.cc: Augment test. * testsuite/25_algorithms/sample/constrained.cc: New test. --- libstdc++-v3/ChangeLog | 9 ++ libstdc++-v3/include/bits/ranges_algo.h | 115 ++++++++++++++++++ .../25_algorithms/clamp/constrained.cc | 58 +++++++++ .../25_algorithms/for_each/constrained.cc | 44 +++++++ .../25_algorithms/sample/constrained.cc | 68 +++++++++++ 5 files changed, 294 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/clamp/constrained.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 7e48bee2b18..c230b2bae69 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,12 @@ +2020-02-17 Patrick Palka + + P1243R4 Rangify new algorithms + * include/bits/ranges_algo.h (for_each_n_result, __for_each_n_fn, + for_each_n, __sample_fn, sample, __clamp_fn, clamp): New. + * testsuite/25_algorithms/clamp/constrained.cc: New test. + * testsuite/25_algorithms/for_each/constrained.cc: Augment test. + * testsuite/25_algorithms/sample/constrained.cc: New test. + 2020-02-17 Jonathan Wakely P1964R2 Wording for boolean-testable diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 83f295722e9..c50b369c6c0 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -195,6 +195,39 @@ namespace ranges inline constexpr __for_each_fn for_each{}; + template + using for_each_n_result = for_each_result<_Iter, _Fp>; + + struct __for_each_n_fn + { + template> _Fun> + constexpr for_each_n_result<_Iter, _Fun> + operator()(_Iter __first, iter_difference_t<_Iter> __n, + _Fun __f, _Proj __proj = {}) const + { + if constexpr (random_access_iterator<_Iter>) + { + if (__n <= 0) + return {std::move(__first), std::move(__f)}; + auto __last = __first + __n; + return ranges::for_each(std::move(__first), std::move(__last), + std::move(__f), std::move(__proj)); + } + else + { + while (__n-- > 0) + { + std::__invoke(__f, std::__invoke(__proj, *__first)); + ++__first; + } + return {std::move(__first), std::move(__f)}; + } + } + }; + + inline constexpr __for_each_n_fn for_each_n{}; + struct __find_fn { template _Sent, typename _Tp, @@ -1694,6 +1727,64 @@ namespace ranges inline constexpr __rotate_copy_fn rotate_copy{}; + struct __sample_fn + { + template _Sent, + weakly_incrementable _Out, typename _Gen> + requires (forward_iterator<_Iter> || random_access_iterator<_Out>) + && indirectly_copyable<_Iter, _Out> + && uniform_random_bit_generator> + _Out + operator()(_Iter __first, _Sent __last, _Out __out, + iter_difference_t<_Iter> __n, _Gen&& __g) const + { + if constexpr (forward_iterator<_Iter>) + { + // FIXME: Forwarding to std::sample here requires computing __lasti + // which may take linear time. + auto __lasti = ranges::next(__first, __last); + return std::sample(std::move(__first), std::move(__lasti), + std::move(__out), __n, std::forward<_Gen>(__g)); + } + else + { + using __distrib_type + = uniform_int_distribution>; + using __param_type = typename __distrib_type::param_type; + __distrib_type __d{}; + iter_difference_t<_Iter> __sample_sz = 0; + while (__first != __last && __sample_sz != __n) + { + __out[__sample_sz++] = *__first; + ++__first; + } + for (auto __pop_sz = __sample_sz; __first != __last; + ++__first, (void) ++__pop_sz) + { + const auto __k = __d(__g, __param_type{0, __pop_sz}); + if (__k < __n) + __out[__k] = *__first; + } + return __out + __sample_sz; + } + } + + template + requires (forward_range<_Range> || random_access_iterator<_Out>) + && indirectly_copyable, _Out> + && uniform_random_bit_generator> + _Out + operator()(_Range&& __r, _Out __out, + range_difference_t<_Range> __n, _Gen&& __g) const + { + return (*this)(ranges::begin(__r), ranges::end(__r), + std::move(__out), __n, + std::forward<_Gen>(__g)); + } + }; + + inline constexpr __sample_fn sample{}; + #ifdef _GLIBCXX_USE_C99_STDINT_TR1 struct __shuffle_fn { @@ -3102,6 +3193,30 @@ namespace ranges inline constexpr __max_fn max{}; + struct __clamp_fn + { + template> _Comp + = ranges::less> + constexpr const _Tp& + operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, + _Comp __comp = {}, _Proj __proj = {}) const + { + __glibcxx_assert(!(std::__invoke(__comp, + std::__invoke(__proj, __hi), + std::__invoke(__proj, __lo)))); + auto&& __proj_val = std::__invoke(__proj, __val); + if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo))) + return __lo; + else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val)) + return __hi; + else + return __val; + } + }; + + inline constexpr __clamp_fn clamp{}; + template struct minmax_result { diff --git a/libstdc++-v3/testsuite/25_algorithms/clamp/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/clamp/constrained.cc new file mode 100644 index 00000000000..1964bb60354 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/clamp/constrained.cc @@ -0,0 +1,58 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include +#include + +using __gnu_test::test_container; +using __gnu_test::test_range; +using __gnu_test::input_iterator_wrapper; + +namespace ranges = std::ranges; + +struct X +{ + int i, j; +}; + +void +test01() +{ + VERIFY( ranges::clamp(1, 2, 4) == 2 ); + VERIFY( ranges::clamp(3, 2, 4) == 3 ); + VERIFY( ranges::clamp(5, 2, 4) == 4 ); + + VERIFY( ranges::clamp(1, 4, 2, ranges::greater{}) == 2 ); + VERIFY( ranges::clamp(3, 4, 2, ranges::greater{}) == 3 ); + VERIFY( ranges::clamp(5, 4, 2, ranges::greater{}) == 4 ); + + VERIFY( ranges::clamp(1, 2, 4, ranges::greater{}, std::negate<>{}) == 2 ); + VERIFY( ranges::clamp(3, 2, 4, ranges::greater{}, std::negate<>{}) == 3 ); + VERIFY( ranges::clamp(5, 2, 4, ranges::greater{}, std::negate<>{}) == 4 ); + + static_assert(ranges::clamp(X{1,2}, X{1,3}, X{1,4}, {}, &X::i).j == 2); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/for_each/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/for_each/constrained.cc index 142ad2e57da..31ca0a7046a 100644 --- a/libstdc++-v3/testsuite/25_algorithms/for_each/constrained.cc +++ b/libstdc++-v3/testsuite/25_algorithms/for_each/constrained.cc @@ -26,6 +26,7 @@ using __gnu_test::test_container; using __gnu_test::test_range; using __gnu_test::input_iterator_wrapper; using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; namespace ranges = std::ranges; @@ -75,9 +76,52 @@ test02() static_assert(f() == 6); } +template typename wrapper> +void +test03() +{ + int x[] = {1,2,3,4,5}; + test_range rx(x); + int s = 0; + auto func = [&s](int i){ s += i; }; + auto [i,f] = ranges::for_each_n(rx.begin(), 3, func); + VERIFY( i.ptr = x+3 ); + VERIFY( s == 1+2+3 ); + f(1); + VERIFY( s == 1+2+3+1 ); + + s = 0; + rx.bounds.first = x; + auto [j,g] = ranges::for_each_n(rx.begin(), -1, func); + VERIFY( j.ptr == x ); + VERIFY( s == 0 ); + g(1); + VERIFY( s == 1 ); + + s = 0; + rx.bounds.first = x; + auto [k,h] = ranges::for_each_n(rx.begin(), 5, func, std::negate<>{}); + VERIFY( k.ptr == x+5 ); + VERIFY( s == -(1+2+3+4+5) ); + h(-6); + VERIFY( s == -(1+2+3+4+5+6) ); +} + +constexpr bool +test04() +{ + int x[] = {1,2,3,4,5}; + int p = 1; + ranges::for_each_n(x+1, 4, [&p](int i){ p*=i; }, [](int i){ return i+1; }); + return p == 3*4*5*6; +} + int main() { test01(); test02(); + test03(); + test03(); + static_assert(test04()); } diff --git a/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc new file mode 100644 index 00000000000..7ed57e8aefc --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc @@ -0,0 +1,68 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } +// { dg-require-cstdint "" } + +#include +#include +#include +#include + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::input_iterator_wrapper; +using __gnu_test::output_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; + +namespace ranges = std::ranges; + +std::mt19937 rng; + +template typename in_wrapper, + template typename out_wrapper> +void +test01() +{ + const int x[] = {1,2,3,4,5,6,7,8,9,10}; + test_range rx(x); + int y[10]; + test_range ry(y); + auto out = ranges::sample(rx.begin(), rx.end(), ry.begin(), 20, rng); + VERIFY( out.ptr == y+10 ); + VERIFY( ranges::equal(x, y) ); + + for (int i = 0; i < 100; i++) + { + int z[5] = {0}; + test_range rz(z); + rx.bounds.first = x; + auto out = ranges::sample(rx, rz.begin(), 5, rng); + VERIFY( out.ptr == z+5 ); + ranges::sort(z); + VERIFY( ranges::adjacent_find(z) == out.ptr ); + VERIFY( ranges::includes(x, z) ); + } +} + +int +main() +{ + test01(); + test01(); +} -- 2.30.2