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

[Patrick Palka]

https://gcc.gnu.org/g:04fdce28164729c067f57a867e37a347e4108286

commit 04fdce28164729c067f57a867e37a347e4108286
Author: Patrick Palka <ppalka@redhat.com>
Date:   Sun Jan 26 01:06:01 2020 -0500

    Reimplement ranges::partial_sort

Diff:
---
 libstdc++-v3/include/bits/ranges_algo.h | 29 +++++++++++++++++------------
 1 file changed, 17 insertions(+), 12 deletions(-)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 89e8214..d71aeb9 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2208,18 +2208,23 @@ namespace ranges
     partial_sort(_Iter __first, _Iter __middle, _Sent __last,
 		 _Comp __comp = {}, _Proj __proj = {})
     {
-      // TODO: is it worth reimplementing std::partial_sort here?
-      auto __lasti = ranges::next(__first, __last);
-      auto __proj_comp = [&] (auto&& __lhs, auto&& __rhs) {
-	using _TL = decltype(__lhs);
-	using _TR = decltype(__rhs);
-	return std::__invoke(__comp,
-			     std::__invoke(__proj, std::forward<_TL>(__lhs)),
-			     std::__invoke(__proj, std::forward<_TR>(__rhs)));
-      };
-      std::partial_sort(std::move(__first), std::move(__middle), __lasti,
-			std::move(__proj_comp));
-      return __lasti;
+      if (__first == __middle)
+	return ranges::next(__first, __last);
+
+      ranges::make_heap(__first, __middle, __comp, __proj);
+      auto __i = __middle;
+      for (; __i != __last; ++__i)
+	if (std::__invoke(__comp,
+			  std::__invoke(__proj, *__i),
+			  std::__invoke(__proj, *__first)))
+	  {
+	    ranges::pop_heap(__first, __middle, __comp, __proj);
+	    ranges::iter_swap(__middle-1, __i);
+	    ranges::push_heap(__first, __middle, __comp, __proj);
+	  }
+      ranges::sort_heap(__first, __middle, __comp, __proj);
+
+      return __i;
     }
 
   template<random_access_range _Range,