[3/3] libstdc++: Implement ranges::find_last{, _if, _if_not} from P1223R5

Message ID 20221114045047.362745-3-ppalka@redhat.com
State Accepted
Headers
Series [1/3] libstdc++: Implement ranges::contains/contains_subrange from P2302R4 |

Checks

Context Check Description
snail/gcc-patch-check success Github commit url

Commit Message

Patrick Palka Nov. 14, 2022, 4:50 a.m. UTC
  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
  

Comments

Jonathan Wakely Nov. 14, 2022, 3:12 p.m. UTC | #1
On Mon, 14 Nov 2022 at 04:51, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> 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);

std::move(__proj) here too, for consistency.

> +           if (__found == __last)
> +             return {__found, __found};
> +           for (;;)
> +             {
> +               __first = ranges::find(ranges::next(__first), __last, __value, __proj);

And here.

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

And here, and std::move(__pred) too, I think.

OK for trunk with those changes here (and the later cases).
  

Patch

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