diff options
author | Patrick Palka <ppalka@redhat.com> | 2023-02-03 10:52:18 -0500 |
---|---|---|
committer | Patrick Palka <ppalka@redhat.com> | 2023-02-03 10:52:18 -0500 |
commit | c9aef107ce697f58a34734d82f8d2514405c9be0 (patch) | |
tree | 71dd3092d98aa58dccb12b67ab0932bebf5285f2 | |
parent | 28752bcbbfb2efa1b57db725d7a3e352eabcc336 (diff) | |
download | gcc-c9aef107ce697f58a34734d82f8d2514405c9be0.zip gcc-c9aef107ce697f58a34734d82f8d2514405c9be0.tar.gz gcc-c9aef107ce697f58a34734d82f8d2514405c9be0.tar.bz2 |
libstdc++: Implement ranges::find_last{,_if,_if_not} from P1223R5
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__find_last_fn, find_last):
Define.
(__find_last_if_fn, find_last_if): Define.
(__find_last_if_not_fn, find_last_if_not): Define.
* testsuite/25_algorithms/find_last/1.cc: New test.
* testsuite/25_algorithms/find_last_if/1.cc: New test.
* testsuite/25_algorithms/find_last_if_not/1.cc: New test.
-rw-r--r-- | libstdc++-v3/include/bits/ranges_algo.h | 126 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/find_last/1.cc | 90 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc | 92 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc | 92 |
4 files changed, 400 insertions, 0 deletions
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 8f9e1f8..5577d86 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3565,6 +3565,132 @@ namespace ranges }; inline constexpr __iota_fn iota{}; + + struct __find_last_fn + { + template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename T, typename _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const T*> + constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, const T& __value, _Proj __proj = {}) const + { + if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) + { + _Iter __found = ranges::find(reverse_iterator<_Iter>{__last}, + reverse_iterator<_Iter>{__first}, + __value, std::move(__proj)).base(); + if (__found == __first) + return {__last, __last}; + else + return {ranges::prev(__found), __last}; + } + else + { + _Iter __found = ranges::find(__first, __last, __value, __proj); + if (__found == __last) + return {__found, __found}; + __first = __found; + for (;;) + { + __first = ranges::find(ranges::next(__first), __last, __value, __proj); + if (__first == __last) + return {__found, __first}; + __found = __first; + } + } + } + + template<forward_range _Range, typename T, typename _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const T*> + constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __r, const T& __value, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); } + }; + + inline constexpr __find_last_fn find_last{}; + + struct __find_last_if_fn + { + template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const + { + if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) + { + _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last}, + reverse_iterator<_Iter>{__first}, + std::move(__pred), std::move(__proj)).base(); + if (__found == __first) + return {__last, __last}; + else + return {ranges::prev(__found), __last}; + } + else + { + _Iter __found = ranges::find_if(__first, __last, __pred, __proj); + if (__found == __last) + return {__found, __found}; + __first = __found; + for (;;) + { + __first = ranges::find_if(ranges::next(__first), __last, __pred, __proj); + if (__first == __last) + return {__found, __first}; + __found = __first; + } + } + } + + template<forward_range _Range, typename _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); } + }; + + inline constexpr __find_last_if_fn find_last_if{}; + + struct __find_last_if_not_fn + { + template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const + { + if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>) + { + _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last}, + reverse_iterator<_Iter>{__first}, + std::move(__pred), std::move(__proj)).base(); + if (__found == __first) + return {__last, __last}; + else + return {ranges::prev(__found), __last}; + } + else + { + _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj); + if (__found == __last) + return {__found, __found}; + __first = __found; + for (;;) + { + __first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj); + if (__first == __last) + return {__found, __first}; + __found = __first; + } + } + } + + template<forward_range _Range, typename _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); } + }; + + inline constexpr __find_last_if_not_fn find_last_if_not{}; #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/25_algorithms/find_last/1.cc b/libstdc++-v3/testsuite/25_algorithms/find_last/1.cc new file mode 100644 index 0000000..ef5844c --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/find_last/1.cc @@ -0,0 +1,90 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +constexpr bool +test01() +{ + int x[] = {1, 2, 1, 2, 1, 2, 1, 2}; + + auto sr0 = ranges::find_last(x, 0); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(x) ); + + auto sr1 = ranges::find_last(x, 1); + VERIFY( ranges::equal(sr1, (int[]){1, 2}) ); + VERIFY( sr1.begin() == &x[6] ); + + auto sr2 = ranges::find_last(x, 2); + VERIFY( ranges::equal(sr2, (int[]){2}) ); + VERIFY( sr2.begin() == &x[7] ); + + auto plus3 = [](int n) { return n+3; }; + + auto sr3 = ranges::find_last(x, 3, plus3); + VERIFY( ranges::empty(sr3) ); + VERIFY( sr3.begin() == ranges::end(x) ); + + auto sr4 = ranges::find_last(x, 4, plus3); + VERIFY( ranges::equal(sr4, (int[]){1, 2}) ); + VERIFY( sr4.begin() == &x[6] ); + + auto sr5 = ranges::find_last(x, 5, plus3); + VERIFY( ranges::equal(sr5, (int[]){2}) ); + VERIFY( sr5.begin() == &x[7] ); + + return true; +} + +void +test02() +{ + int x[] = {1, 2, 3, 1, 2, 3, 1, 2, 3}; + __gnu_test::test_forward_range<int> rx(x); + + auto sr0 = ranges::find_last(rx, 0); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(rx) ); + + auto sr1 = ranges::find_last(rx, 1); + VERIFY( ranges::equal(sr1, (int[]){1, 2, 3}) ); + VERIFY( sr1.begin().ptr == &x[6] ); + + auto sr2 = ranges::find_last(rx, 2); + VERIFY( ranges::equal(sr2, (int[]){2, 3}) ); + VERIFY( sr2.begin().ptr == &x[7] ); + + auto sr3 = ranges::find_last(rx, 3); + VERIFY( ranges::equal(sr3, (int[]){3}) ); + VERIFY( sr3.begin().ptr == &x[8] ); + + auto plus4 = [](int n) { return n+4; }; + + auto sr4 = ranges::find_last(rx, 4, plus4); + VERIFY( ranges::empty(sr4) ); + VERIFY( sr4.begin() == ranges::end(rx) ); + + auto sr5 = ranges::find_last(rx, 5, plus4); + VERIFY( ranges::equal(sr5, (int[]){1, 2, 3}) ); + VERIFY( sr5.begin().ptr == &x[6] ); + + auto sr6 = ranges::find_last(rx, 6, plus4); + VERIFY( ranges::equal(sr6, (int[]){2, 3}) ); + VERIFY( sr6.begin().ptr == &x[7] ); + + auto sr7 = ranges::find_last(rx, 7, plus4); + VERIFY( ranges::equal(sr7, (int[]){3}) ); + VERIFY( sr7.begin().ptr == &x[8] ); +} + +int +main() +{ + static_assert(test01()); + test02(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc b/libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc new file mode 100644 index 0000000..0a72347 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc @@ -0,0 +1,92 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +template<int N> constexpr auto eq = [](int m) { return m == N; }; + +constexpr bool +test01() +{ + int x[] = {1, 2, 1, 2, 1, 2, 1, 2}; + + auto sr0 = ranges::find_last_if(x, eq<0>); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(x) ); + + auto sr1 = ranges::find_last_if(x, eq<1>); + VERIFY( ranges::equal(sr1, (int[]){1, 2}) ); + VERIFY( sr1.begin() == &x[6] ); + + auto sr2 = ranges::find_last_if(x, eq<2>); + VERIFY( ranges::equal(sr2, (int[]){2}) ); + VERIFY( sr2.begin() == &x[7] ); + + auto plus3 = [](int n) { return n+3; }; + + auto sr3 = ranges::find_last_if(x, eq<3>, plus3); + VERIFY( ranges::empty(sr3) ); + VERIFY( sr3.begin() == ranges::end(x) ); + + auto sr4 = ranges::find_last_if(x, eq<4>, plus3); + VERIFY( ranges::equal(sr4, (int[]){1, 2}) ); + VERIFY( sr4.begin() == &x[6] ); + + auto sr5 = ranges::find_last_if(x, eq<5>, plus3); + VERIFY( ranges::equal(sr5, (int[]){2}) ); + VERIFY( sr5.begin() == &x[7] ); + + return true; +} + +void +test02() +{ + int x[] = {1, 2, 3, 1, 2, 3, 1, 2, 3}; + __gnu_test::test_forward_range<int> rx(x); + + auto sr0 = ranges::find_last_if(rx, eq<0>); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(rx) ); + + auto sr1 = ranges::find_last_if(rx, eq<1>); + VERIFY( ranges::equal(sr1, (int[]){1, 2, 3}) ); + VERIFY( sr1.begin().ptr == &x[6] ); + + auto sr2 = ranges::find_last_if(rx, eq<2>); + VERIFY( ranges::equal(sr2, (int[]){2, 3}) ); + VERIFY( sr2.begin().ptr == &x[7] ); + + auto sr3 = ranges::find_last_if(rx, eq<3>); + VERIFY( ranges::equal(sr3, (int[]){3}) ); + VERIFY( sr3.begin().ptr == &x[8] ); + + auto plus4 = [](int n) { return n+4; }; + + auto sr4 = ranges::find_last_if(rx, eq<4>, plus4); + VERIFY( ranges::empty(sr4) ); + VERIFY( sr4.begin() == ranges::end(rx) ); + + auto sr5 = ranges::find_last_if(rx, eq<5>, plus4); + VERIFY( ranges::equal(sr5, (int[]){1, 2, 3}) ); + VERIFY( sr5.begin().ptr == &x[6] ); + + auto sr6 = ranges::find_last_if(rx, eq<6>, plus4); + VERIFY( ranges::equal(sr6, (int[]){2, 3}) ); + VERIFY( sr6.begin().ptr == &x[7] ); + + auto sr7 = ranges::find_last_if(rx, eq<7>, plus4); + VERIFY( ranges::equal(sr7, (int[]){3}) ); + VERIFY( sr7.begin().ptr == &x[8] ); +} + +int +main() +{ + static_assert(test01()); + test02(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc b/libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc new file mode 100644 index 0000000..98aa94b --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc @@ -0,0 +1,92 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +template<int N> constexpr auto ne = [](int m) { return m != N; }; + +constexpr bool +test01() +{ + int x[] = {1, 2, 1, 2, 1, 2, 1, 2}; + + auto sr0 = ranges::find_last_if_not(x, ne<0>); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(x) ); + + auto sr1 = ranges::find_last_if_not(x, ne<1>); + VERIFY( ranges::equal(sr1, (int[]){1, 2}) ); + VERIFY( sr1.begin() == &x[6] ); + + auto sr2 = ranges::find_last_if_not(x, ne<2>); + VERIFY( ranges::equal(sr2, (int[]){2}) ); + VERIFY( sr2.begin() == &x[7] ); + + auto plus3 = [](int n) { return n+3; }; + + auto sr3 = ranges::find_last_if_not(x, ne<3>, plus3); + VERIFY( ranges::empty(sr3) ); + VERIFY( sr3.begin() == ranges::end(x) ); + + auto sr4 = ranges::find_last_if_not(x, ne<4>, plus3); + VERIFY( ranges::equal(sr4, (int[]){1, 2}) ); + VERIFY( sr4.begin() == &x[6] ); + + auto sr5 = ranges::find_last_if_not(x, ne<5>, plus3); + VERIFY( ranges::equal(sr5, (int[]){2}) ); + VERIFY( sr5.begin() == &x[7] ); + + return true; +} + +void +test02() +{ + int x[] = {1, 2, 3, 1, 2, 3, 1, 2, 3}; + __gnu_test::test_forward_range<int> rx(x); + + auto sr0 = ranges::find_last_if_not(rx, ne<0>); + VERIFY( ranges::empty(sr0) ); + VERIFY( sr0.begin() == ranges::end(rx) ); + + auto sr1 = ranges::find_last_if_not(rx, ne<1>); + VERIFY( ranges::equal(sr1, (int[]){1, 2, 3}) ); + VERIFY( sr1.begin().ptr == &x[6] ); + + auto sr2 = ranges::find_last_if_not(rx, ne<2>); + VERIFY( ranges::equal(sr2, (int[]){2, 3}) ); + VERIFY( sr2.begin().ptr == &x[7] ); + + auto sr3 = ranges::find_last_if_not(rx, ne<3>); + VERIFY( ranges::equal(sr3, (int[]){3}) ); + VERIFY( sr3.begin().ptr == &x[8] ); + + auto plus4 = [](int n) { return n+4; }; + + auto sr4 = ranges::find_last_if_not(rx, ne<4>, plus4); + VERIFY( ranges::empty(sr4) ); + VERIFY( sr4.begin() == ranges::end(rx) ); + + auto sr5 = ranges::find_last_if_not(rx, ne<5>, plus4); + VERIFY( ranges::equal(sr5, (int[]){1, 2, 3}) ); + VERIFY( sr5.begin().ptr == &x[6] ); + + auto sr6 = ranges::find_last_if_not(rx, ne<6>, plus4); + VERIFY( ranges::equal(sr6, (int[]){2, 3}) ); + VERIFY( sr6.begin().ptr == &x[7] ); + + auto sr7 = ranges::find_last_if_not(rx, ne<7>, plus4); + VERIFY( ranges::equal(sr7, (int[]){3}) ); + VERIFY( sr7.begin().ptr == &x[8] ); +} + +int +main() +{ + static_assert(test01()); + test02(); +} |