From: Patrick Palka <ppalka@redhat.com>
To: gcc-patches@gcc.gnu.org
Cc: libstdc++@gcc.gnu.org, Patrick Palka <ppalka@redhat.com>
Subject: [PATCH 3/3] libstdc++: Implement ranges::find_last{,_if,_if_not} from P1223R5
Date: Sun, 13 Nov 2022 23:50:47 -0500 [thread overview]
Message-ID: <20221114045047.362745-3-ppalka@redhat.com> (raw)
In-Reply-To: <20221114045047.362745-1-ppalka@redhat.com>
Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
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.
---
libstdc++-v3/include/bits/ranges_algo.h | 123 ++++++++++++++++++
.../testsuite/25_algorithms/find_last/1.cc | 90 +++++++++++++
.../testsuite/25_algorithms/find_last_if/1.cc | 92 +++++++++++++
.../25_algorithms/find_last_if_not/1.cc | 92 +++++++++++++
4 files changed, 397 insertions(+)
create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last/1.cc
create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc
create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index f003117c569..0e4329382eb 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3565,6 +3565,129 @@ 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, __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};
+ 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},
+ __pred, __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};
+ 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},
+ __pred, __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};
+ 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();
+}
--
2.38.1.420.g319605f8f0
next prev parent reply other threads:[~2022-11-14 4:51 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-14 4:50 [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Patrick Palka
2022-11-14 4:50 ` [PATCH 2/3] libstdc++: Implement ranges::iota from P2440R1 Patrick Palka
2022-11-14 10:08 ` Jonathan Wakely
2022-11-14 10:17 ` Daniel Krügler
2022-11-14 10:20 ` Jonathan Wakely
2022-11-14 15:11 ` Patrick Palka
2022-11-14 15:12 ` Jonathan Wakely
2022-11-14 4:50 ` Patrick Palka [this message]
2022-11-14 15:12 ` [PATCH 3/3] libstdc++: Implement ranges::find_last{, _if, _if_not} from P1223R5 Jonathan Wakely
2022-11-14 9:04 ` [PATCH 1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 Jonathan Wakely
2022-11-14 15:07 ` Patrick Palka
2022-11-14 15:09 ` Jonathan Wakely
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=20221114045047.362745-3-ppalka@redhat.com \
--to=ppalka@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@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: link
Be 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).