[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add better implementation of ranges::find_end for bidirectional iterators

[Patrick Palka]

https://gcc.gnu.org/g:ecb9da237193936fcbbf2a0321377b005d3df0a1

commit ecb9da237193936fcbbf2a0321377b005d3df0a1
Author: Patrick Palka <ppalka@gcc.gnu.org>
Date:   Wed Jan 15 12:20:25 2020 -0500

    Add better implementation of ranges::find_end for bidirectional iterators

Diff:
---
 libstdc++-v3/include/bits/ranges_algo.h | 39 ++++++++++++++++++++++++++++++---
 1 file changed, 36 insertions(+), 3 deletions(-)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 965fe85..b89f19a 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -424,9 +424,9 @@ namespace ranges
 	   class _Proj1 = identity, class _Proj2 = identity>
     requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
     constexpr subrange<_Iter1>
-    find_end(_Iter1 __first1, _Sent1 __last1,
-	     _Iter2 __first2, _Sent2 __last2,
-	     _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+    __find_end(_Iter1 __first1, _Sent1 __last1,
+	       _Iter2 __first2, _Sent2 __last2,
+	       _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
     {
       if (__first2 == __last2)
 	return {__last1, __last1};
@@ -452,6 +452,39 @@ namespace ranges
 	}
     }
 
+  template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+	   forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+	   class _Pred = ranges::equal_to,
+	   class _Proj1 = identity, class _Proj2 = identity>
+    requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
+    constexpr subrange<_Iter1>
+    find_end(_Iter1 __first1, _Sent1 __last1,
+	     _Iter2 __first2, _Sent2 __last2,
+	     _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+    {
+      if constexpr (std::bidirectional_iterator<_Iter1>
+		    && std::bidirectional_iterator<_Iter2>)
+	{
+	  auto __rresult
+	    = ranges::search(reverse_iterator<_Iter1>(__last1),
+			     reverse_iterator<_Iter1>(__first1),
+			     reverse_iterator<_Iter2>(__last2),
+			     reverse_iterator<_Iter2>(__first2),
+			     std::move(__pred),
+			     std::move(__proj1), std::move(__proj2));
+	  auto __result_first = ranges::end(__rresult).base();
+	  auto __result_last = ranges::begin(__rresult).base();
+	  if (__result_last == __first1)
+	    return {__last1, __last1};
+	  else
+	    return {__result_first, __result_last};
+	}
+      else
+	return ranges::__find_end(__first1, __last1, __first2, __last2,
+				  std::move(__pred),
+				  std::move(__proj1), std::move(__proj2));
+    }
+
   template<forward_range _Range1, forward_range _Range2,
 	   class _Pred = ranges::equal_to,
 	   class _Proj1 = identity, class _Proj2 = identity>