public inbox for libstdc++-cvs@sourceware.org help / color / mirror / Atom feed
From: Aldy Hernandez <aldyh@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc/devel/ranger] libstdc++: P1243R4 Rangify new algorithms Date: Wed, 17 Jun 2020 18:58:57 +0000 (GMT) [thread overview] Message-ID: <20200617185857.E6AC439960E5@sourceware.org> (raw) https://gcc.gnu.org/g:f3169941996c76ecbfae9c37709d2b57652be555 commit f3169941996c76ecbfae9c37709d2b57652be555 Author: Patrick Palka <ppalka@redhat.com> Date: Mon Feb 17 11:50:29 2020 -0500 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. Diff: --- libstdc++-v3/ChangeLog | 9 ++ libstdc++-v3/include/bits/ranges_algo.h | 115 +++++++++++++++++++++ .../testsuite/25_algorithms/clamp/constrained.cc | 58 +++++++++++ .../25_algorithms/for_each/constrained.cc | 44 ++++++++ .../testsuite/25_algorithms/sample/constrained.cc | 68 ++++++++++++ 5 files changed, 294 insertions(+) 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 <ppalka@redhat.com> + + 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 <jwakely@redhat.com> 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<typename _Iter, typename _Fp> + using for_each_n_result = for_each_result<_Iter, _Fp>; + + struct __for_each_n_fn + { + template<input_iterator _Iter, typename _Proj = identity, + indirectly_unary_invocable<projected<_Iter, _Proj>> _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<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp, @@ -1694,6 +1727,64 @@ namespace ranges inline constexpr __rotate_copy_fn rotate_copy{}; + struct __sample_fn + { + template<input_iterator _Iter, sentinel_for<_Iter> _Sent, + weakly_incrementable _Out, typename _Gen> + requires (forward_iterator<_Iter> || random_access_iterator<_Out>) + && indirectly_copyable<_Iter, _Out> + && uniform_random_bit_generator<remove_reference_t<_Gen>> + _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<iter_difference_t<_Iter>>; + 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<input_range _Range, weakly_incrementable _Out, typename _Gen> + requires (forward_range<_Range> || random_access_iterator<_Out>) + && indirectly_copyable<iterator_t<_Range>, _Out> + && uniform_random_bit_generator<remove_reference_t<_Gen>> + _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<typename _Tp, typename _Proj = identity, + indirect_strict_weak_order<projected<const _Tp*, _Proj>> _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<typename _Tp> 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +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<template<typename> typename wrapper> +void +test03() +{ + int x[] = {1,2,3,4,5}; + test_range<int, wrapper> 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<input_iterator_wrapper>(); + test03<random_access_iterator_wrapper>(); + 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } +// { dg-require-cstdint "" } + +#include <algorithm> +#include <random> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +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<template<typename> typename in_wrapper, + template<typename> typename out_wrapper> +void +test01() +{ + const int x[] = {1,2,3,4,5,6,7,8,9,10}; + test_range<const int, in_wrapper> rx(x); + int y[10]; + test_range<int, out_wrapper> 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<int, out_wrapper> 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<forward_iterator_wrapper, output_iterator_wrapper>(); + test01<input_iterator_wrapper, random_access_iterator_wrapper>(); +}
reply other threads:[~2020-06-17 18:58 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20200617185857.E6AC439960E5@sourceware.org \ --to=aldyh@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ --cc=libstdc++-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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).