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.

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();
+}