[PATCH 1/2] libstdc++: P1243R4 Rangify new algorithms

[Patrick Palka <ppalka at redhat dot com>]

This adds rangified overloads for for_each_n, sample and clamp as per P1243R4.

libstdc++-v3/ChangeLog:

	P1243R4
	* include/bits/ranges_algo.h (for_each_n_result, __for_each_n_fn,
	for_each_n, __sample_fn, sample, __clamp_fn, clamp): New.
	* testsuite/25_algorithms/clamp/constrained.cc: New test.
	* testsuite/25_algorithms/for_each/constrained.cc: Augment test.
	* testsuite/25_algorithms/sample/constrained.cc: New test.
---
 libstdc++-v3/include/bits/ranges_algo.h       | 115 ++++++++++++++++++
 .../25_algorithms/clamp/constrained.cc        |  58 +++++++++
 .../25_algorithms/for_each/constrained.cc     |  44 +++++++
 .../25_algorithms/sample/constrained.cc       |  68 +++++++++++
 4 files changed, 285 insertions(+)
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/clamp/constrained.cc
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 83f295722e9..c50b369c6c0 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -195,6 +195,39 @@ namespace ranges
 
   inline constexpr __for_each_fn for_each{};
 
+  template<typename _Iter, typename _Fp>
+    using for_each_n_result = for_each_result<_Iter, _Fp>;
+
+  struct __for_each_n_fn
+  {
+    template<input_iterator _Iter, typename _Proj = identity,
+	     indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
+      constexpr for_each_n_result<_Iter, _Fun>
+      operator()(_Iter __first, iter_difference_t<_Iter> __n,
+		 _Fun __f, _Proj __proj = {}) const
+      {
+	if constexpr (random_access_iterator<_Iter>)
+	  {
+	    if (__n <= 0)
+	      return {std::move(__first), std::move(__f)};
+	    auto __last = __first + __n;
+	    return ranges::for_each(std::move(__first), std::move(__last),
+				    std::move(__f), std::move(__proj));
+	  }
+	else
+	  {
+	    while (__n-- > 0)
+	      {
+		std::__invoke(__f, std::__invoke(__proj, *__first));
+		++__first;
+	      }
+	    return {std::move(__first), std::move(__f)};
+	  }
+      }
+  };
+
+  inline constexpr __for_each_n_fn for_each_n{};
+
   struct __find_fn
   {
     template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
@@ -1694,6 +1727,64 @@ namespace ranges
 
   inline constexpr __rotate_copy_fn rotate_copy{};
 
+  struct __sample_fn
+  {
+    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+	     weakly_incrementable _Out, typename _Gen>
+      requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
+	&& indirectly_copyable<_Iter, _Out>
+	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
+      _Out
+      operator()(_Iter __first, _Sent __last, _Out __out,
+		 iter_difference_t<_Iter> __n, _Gen&& __g) const
+      {
+	if constexpr (forward_iterator<_Iter>)
+	  {
+	    // FIXME: Forwarding to std::sample here requires computing __lasti
+	    // which may take linear time.
+	    auto __lasti = ranges::next(__first, __last);
+	    return std::sample(std::move(__first), std::move(__lasti),
+			       std::move(__out), __n, std::forward<_Gen>(__g));
+	  }
+	else
+	  {
+	    using __distrib_type
+	      = uniform_int_distribution<iter_difference_t<_Iter>>;
+	    using __param_type = typename __distrib_type::param_type;
+	    __distrib_type __d{};
+	    iter_difference_t<_Iter> __sample_sz = 0;
+	    while (__first != __last && __sample_sz != __n)
+	      {
+		__out[__sample_sz++] = *__first;
+		++__first;
+	      }
+	    for (auto __pop_sz = __sample_sz; __first != __last;
+		++__first, (void) ++__pop_sz)
+	      {
+		const auto __k = __d(__g, __param_type{0, __pop_sz});
+		if (__k < __n)
+		  __out[__k] = *__first;
+	      }
+	    return __out + __sample_sz;
+	  }
+      }
+
+    template<input_range _Range, weakly_incrementable _Out, typename _Gen>
+      requires (forward_range<_Range> || random_access_iterator<_Out>)
+	&& indirectly_copyable<iterator_t<_Range>, _Out>
+	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
+      _Out
+      operator()(_Range&& __r, _Out __out,
+		 range_difference_t<_Range> __n, _Gen&& __g) const
+      {
+	return (*this)(ranges::begin(__r), ranges::end(__r),
+		       std::move(__out), __n,
+		       std::forward<_Gen>(__g));
+      }
+  };
+
+  inline constexpr __sample_fn sample{};
+
 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
   struct __shuffle_fn
   {
@@ -3102,6 +3193,30 @@ namespace ranges
 
   inline constexpr __max_fn max{};
 
+  struct __clamp_fn
+  {
+    template<typename _Tp, typename _Proj = identity,
+	     indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
+	       = ranges::less>
+      constexpr const _Tp&
+      operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi,
+		 _Comp __comp = {}, _Proj __proj = {}) const
+      {
+	__glibcxx_assert(!(std::__invoke(__comp,
+					 std::__invoke(__proj, __hi),
+					 std::__invoke(__proj, __lo))));
+	auto&& __proj_val = std::__invoke(__proj, __val);
+	if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
+	  return __lo;
+	else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val))
+	  return __hi;
+	else
+	  return __val;
+      }
+  };
+
+  inline constexpr __clamp_fn clamp{};
+
   template<typename _Tp>
     struct minmax_result
     {
diff --git a/libstdc++-v3/testsuite/25_algorithms/clamp/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/clamp/constrained.cc
new file mode 100644
index 00000000000..1964bb60354
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/clamp/constrained.cc
@@ -0,0 +1,58 @@
+// 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 } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::test_range;
+using __gnu_test::input_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+struct X
+{
+  int i, j;
+};
+
+void
+test01()
+{
+  VERIFY( ranges::clamp(1, 2, 4) == 2 );
+  VERIFY( ranges::clamp(3, 2, 4) == 3 );
+  VERIFY( ranges::clamp(5, 2, 4) == 4 );
+
+  VERIFY( ranges::clamp(1, 4, 2, ranges::greater{}) == 2 );
+  VERIFY( ranges::clamp(3, 4, 2, ranges::greater{}) == 3 );
+  VERIFY( ranges::clamp(5, 4, 2, ranges::greater{}) == 4 );
+
+  VERIFY( ranges::clamp(1, 2, 4, ranges::greater{}, std::negate<>{}) == 2 );
+  VERIFY( ranges::clamp(3, 2, 4, ranges::greater{}, std::negate<>{}) == 3 );
+  VERIFY( ranges::clamp(5, 2, 4, ranges::greater{}, std::negate<>{}) == 4 );
+
+  static_assert(ranges::clamp(X{1,2}, X{1,3}, X{1,4}, {}, &X::i).j == 2);
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/for_each/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/for_each/constrained.cc
index 142ad2e57da..31ca0a7046a 100644
--- a/libstdc++-v3/testsuite/25_algorithms/for_each/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/for_each/constrained.cc
@@ -26,6 +26,7 @@ using __gnu_test::test_container;
 using __gnu_test::test_range;
 using __gnu_test::input_iterator_wrapper;
 using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
 
 namespace ranges = std::ranges;
 
@@ -75,9 +76,52 @@ test02()
   static_assert(f() == 6);
 }
 
+template<template<typename> typename wrapper>
+void
+test03()
+{
+  int x[] = {1,2,3,4,5};
+  test_range<int, wrapper> rx(x);
+  int s = 0;
+  auto func = [&s](int i){ s += i; };
+  auto [i,f] = ranges::for_each_n(rx.begin(), 3, func);
+  VERIFY( i.ptr = x+3 );
+  VERIFY( s == 1+2+3 );
+  f(1);
+  VERIFY( s == 1+2+3+1 );
+
+  s = 0;
+  rx.bounds.first = x;
+  auto [j,g] = ranges::for_each_n(rx.begin(), -1, func);
+  VERIFY( j.ptr == x );
+  VERIFY( s == 0 );
+  g(1);
+  VERIFY( s == 1 );
+
+  s = 0;
+  rx.bounds.first = x;
+  auto [k,h] = ranges::for_each_n(rx.begin(), 5, func, std::negate<>{});
+  VERIFY( k.ptr == x+5 );
+  VERIFY( s == -(1+2+3+4+5) );
+  h(-6);
+  VERIFY( s == -(1+2+3+4+5+6) );
+}
+
+constexpr bool
+test04()
+{
+  int x[] = {1,2,3,4,5};
+  int p = 1;
+  ranges::for_each_n(x+1, 4, [&p](int i){ p*=i; }, [](int i){ return i+1; });
+  return p == 3*4*5*6;
+}
+
 int
 main()
 {
   test01();
   test02();
+  test03<input_iterator_wrapper>();
+  test03<random_access_iterator_wrapper>();
+  static_assert(test04());
 }
diff --git a/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc
new file mode 100644
index 00000000000..7ed57e8aefc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc
@@ -0,0 +1,68 @@
+// 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_range;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+std::mt19937 rng;
+
+template<template<typename> typename in_wrapper,
+	 template<typename> typename out_wrapper>
+void
+test01()
+{
+  const int x[] = {1,2,3,4,5,6,7,8,9,10};
+  test_range<const int, in_wrapper> rx(x);
+  int y[10];
+  test_range<int, out_wrapper> ry(y);
+  auto out = ranges::sample(rx.begin(), rx.end(), ry.begin(), 20, rng);
+  VERIFY( out.ptr == y+10 );
+  VERIFY( ranges::equal(x, y) );
+
+  for (int i = 0; i < 100; i++)
+    {
+      int z[5] = {0};
+      test_range<int, out_wrapper> rz(z);
+      rx.bounds.first = x;
+      auto out = ranges::sample(rx, rz.begin(), 5, rng);
+      VERIFY( out.ptr == z+5 );
+      ranges::sort(z);
+      VERIFY( ranges::adjacent_find(z) == out.ptr );
+      VERIFY( ranges::includes(x, z) );
+    }
+}
+
+int
+main()
+{
+  test01<forward_iterator_wrapper, output_iterator_wrapper>();
+  test01<input_iterator_wrapper, random_access_iterator_wrapper>();
+}
-- 
2.25.1.291.ge68e29171c