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

[Patrick Palka]

https://gcc.gnu.org/g:5cf48f6c1d130f5cf24249128aa26c59218f9677

commit 5cf48f6c1d130f5cf24249128aa26c59218f9677
Author: Patrick Palka <ppalka@redhat.com>
Date:   Sun Jan 26 01:30:07 2020 -0500

    Add ranges::nth_element

Diff:
---
 libstdc++-v3/include/bits/ranges_algo.h            | 32 +++++++++
 .../25_algorithms/nth_element/constrained.cc       | 76 ++++++++++++++++++++++
 2 files changed, 108 insertions(+)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index d71aeb9..7226be9 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2369,6 +2369,38 @@ namespace ranges
 			       std::move(__comp), std::move(__proj));
     }
 
+  template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
+	   typename _Comp = ranges::less, typename _Proj = identity>
+    requires sortable<_Iter, _Comp, _Proj>
+    constexpr _Iter
+    nth_element(_Iter __first, _Iter __nth, _Sent __last,
+		_Comp __comp = {}, _Proj __proj = {})
+    {
+      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::nth_element(std::move(__first), std::move(__nth), __lasti,
+		       __proj_comp);
+      return __lasti;
+    }
+
+  template<random_access_range _Range,
+	   typename _Comp = ranges::less, typename _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+    constexpr safe_iterator_t<_Range>
+    nth_element(_Range&& __r, iterator_t<_Range> __nth,
+		_Comp __comp = {}, _Proj __proj = {})
+    {
+      return ranges::nth_element(ranges::begin(__r), std::move(__nth),
+				 ranges::end(__r),
+				 std::move(__comp), std::move(__proj));
+    }
+
   template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
 	   typename _Tp, typename _Proj = identity,
 	   indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
new file mode 100644
index 0000000..34f3013
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
@@ -0,0 +1,76 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+// { dg-require-cstdint "" }
+
+#include <algorithm>
+#include <random>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::test_range;
+using __gnu_test::random_access_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+  int x[50];
+  std::iota(x, x+50, 0);
+
+  auto pred = std::greater{};
+  auto proj = [] (int a) { return -a; };
+  for (int i = 0; i < 50; i++)
+    {
+      test_range<int, random_access_iterator_wrapper> rx(x);
+      std::ranlux48_base g(i);
+      ranges::shuffle(rx, g);
+
+      auto result = ranges::nth_element(rx, rx.begin()+i, pred, proj);
+      VERIFY( result == rx.end() );
+      VERIFY( x[i] == i );
+      for (int j = 0; j < i; j++)
+	for (int k = i; k < 50; k++)
+	  VERIFY( !pred(proj(x[k]), proj(x[j])) );
+
+      result = ranges::nth_element(rx, rx.begin()+i, pred);
+      VERIFY( result == rx.end() );
+      VERIFY( x[i] == 49-i );
+      for (int j = 0; j < i; j++)
+	for (int k = i; k < 50; k++)
+	  VERIFY( !pred(x[k], x[j]) );
+    }
+}
+
+constexpr bool
+test02()
+{
+  int x[] = {5,2,1,3,4};
+  ranges::nth_element(x, x+3);
+  return x[3] == 4;
+}
+
+int
+main()
+{
+  test01();
+  static_assert(test02());
+}