[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Finish ranges::search_n

[Patrick Palka]

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

commit f779c0e10ea30e26d8b24db91917c3c54d576aef
Author: Patrick Palka <ppalka@gcc.gnu.org>
Date:   Fri Jan 17 19:57:39 2020 -0500

    Finish ranges::search_n
    
    The non-modifying constrained algorithms are done!

Diff:
---
 libstdc++-v3/include/bits/ranges_algo.h            | 49 +++++++++++++++-------
 .../25_algorithms/search_n/constrained.cc          |  2 +-
 2 files changed, 36 insertions(+), 15 deletions(-)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 79ba19a..c63b2a1 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -445,25 +445,46 @@ namespace ranges
 	    }
 	}
 
-      __first = ranges::find_if(__first, __last, __value_comp, __proj);
-      while (__first != __last)
+      if constexpr (sized_sentinel_for<_Sent, _Iter>)
 	{
-	  auto __n = __count;
-	  auto __i = __first;
-	  ++__i;
-	  while (__i != __last && __n != 1
-		 && std::__invoke(__pred, __value, std::__invoke(__proj, *__i)))
+	  auto __tail_size = __last - __first;
+	  auto __remainder = __count;
+
+	  while (__remainder <= __tail_size)
 	    {
-	      ++__i;
-	      --__n;
+	      __first += __remainder;
+	      __tail_size -= __remainder;
+	      auto __backtrack = __first;
+	      while (__value_comp(std::__invoke(__proj, *--__backtrack)))
+		{
+		  if (--__remainder == 0)
+		    return {__first - __count, __first};
+		}
 	    }
-	  if (__n == 1)
-	    return {__first, __i};
-	  if (__i == __last)
-	    return {__last, __last};
+	  return {__last, __last};
+	}
+      else
+	{
 	  __first = ranges::find_if(__first, __last, __value_comp, __proj);
+	  while (__first != __last)
+	    {
+	      auto __n = __count;
+	      auto __i = __first;
+	      ++__i;
+	      while (__i != __last && __n != 1
+		     && __value_comp(std::__invoke(__proj, *__i)))
+		{
+		  ++__i;
+		  --__n;
+		}
+	      if (__n == 1)
+		return {__first, __i};
+	      if (__i == __last)
+		return {__last, __last};
+	      __first = ranges::find_if(++__i, __last, __value_comp, __proj);
+	    }
+	  return {__last, __last};
 	}
-      return {__last, __last};
     }
 
   template<forward_range _Range, typename _Tp,
diff --git a/libstdc++-v3/testsuite/25_algorithms/search_n/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/search_n/constrained.cc
index b0733a6..de9b171 100644
--- a/libstdc++-v3/testsuite/25_algorithms/search_n/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/search_n/constrained.cc
@@ -49,7 +49,7 @@ test01()
 
   int y[] = { {2}, {2}, {8}, {2}, {2}, {2}, {5} };
   test_range<int, forward_iterator_wrapper> ry(y);
-  auto res3 = ranges::search_n(ry, 2, 3);
+  auto res3 = ranges::search_n(ry, 3, 2);
   VERIFY( *res3.begin() == 2 && *res3.end() == 5 );
 }