public inbox for libstdc++-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r13-5689] libstdc++: Implement ranges::find_last{, _if, _if_not} from P1223R5
@ 2023-02-03 15:54 Patrick Palka
0 siblings, 0 replies; only message in thread
From: Patrick Palka @ 2023-02-03 15:54 UTC (permalink / raw)
To: gcc-cvs, libstdc++-cvs
https://gcc.gnu.org/g:c9aef107ce697f58a34734d82f8d2514405c9be0
commit r13-5689-gc9aef107ce697f58a34734d82f8d2514405c9be0
Author: Patrick Palka <ppalka@redhat.com>
Date: Fri Feb 3 10:52:18 2023 -0500
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.
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 126 +++++++++++++++++++++
.../testsuite/25_algorithms/find_last/1.cc | 90 +++++++++++++++
.../testsuite/25_algorithms/find_last_if/1.cc | 92 +++++++++++++++
.../testsuite/25_algorithms/find_last_if_not/1.cc | 92 +++++++++++++++
4 files changed, 400 insertions(+)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 8f9e1f8bcc3..5577d862cb5 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 00000000000..ef5844c8afd
--- /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 00000000000..0a723475dec
--- /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 00000000000..98aa94b7f2c
--- /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();
+}
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2023-02-03 15:54 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-02-03 15:54 [gcc r13-5689] libstdc++: Implement ranges::find_last{, _if, _if_not} from P1223R5 Patrick Palka
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).