[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add ranges [alg.merge]

Patrick Palka ppalka@gcc.gnu.org
Fri Jan 24 21:00:00 GMT 2020


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

commit cb7a12b36529e6c0ea097e1bcee023b04f1cb5bc
Author: Patrick Palka <ppalka@redhat.com>
Date:   Fri Jan 24 15:58:52 2020 -0500

    Add ranges [alg.merge]

Diff:
---
 libstdc++-v3/include/bits/ranges_algo.h            | 89 +++++++++++++++++++++-
 .../25_algorithms/inplace_merge/constrained.cc     | 69 +++++++++++++++++
 .../testsuite/25_algorithms/merge/constrained.cc   | 75 ++++++++++++++++++
 3 files changed, 232 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index f1de85f..1746484 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2508,10 +2508,97 @@ namespace ranges
 				     std::move(__pred), std::move(__proj));
     }
 
+  template<typename _Iter1, typename _Iter2, typename _Out>
+  using merge_result = binary_transform_result<_Iter1, _Iter2, _Out>;
+
+  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+	   input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+	   weakly_incrementable _Out, typename _Comp = ranges::less,
+	   typename _Proj1 = identity, typename _Proj2 = identity>
+    requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
+    constexpr merge_result<_Iter1, _Iter2, _Out>
+    merge(_Iter1 __first1, _Sent1 __last1,
+	  _Iter2 __first2, _Sent2 __last2, _Out __result,
+	  _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+    {
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (std::__invoke(__comp,
+			    std::__invoke(__proj2, *__first2),
+			    std::__invoke(__proj1, *__first1)))
+	    {
+	      *__result = *__first2;
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = *__first1;
+	      ++__first1;
+	    }
+	  ++__result;
+	}
+      auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
+				  std::move(__result));
+      auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
+				  std::move(__copy1.out));
+      return { std::move(__copy1.in), std::move(__copy2.in),
+	       std::move(__copy2.out) };
+    }
+
+  template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
+	   typename _Comp = ranges::less,
+	   typename _Proj1 = identity, typename _Proj2 = identity>
+    requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
+		       _Comp, _Proj1, _Proj2>
+    constexpr merge_result<safe_iterator_t<_Range1>,
+			   safe_iterator_t<_Range2>,
+			   _Out>
+    merge(_Range1&& __r1, _Range2&& __r2, _Out __result,
+	  _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+    {
+      return ranges::merge(ranges::begin(__r1), ranges::end(__r1),
+			   ranges::begin(__r2), ranges::end(__r2),
+			   std::move(__result), std::move(__comp),
+			   std::move(__proj1), std::move(__proj2));
+    }
+
+  template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
+	   typename _Comp = ranges::less,
+	   typename _Proj = identity>
+    requires sortable<_Iter, _Comp, _Proj>
+    _Iter
+    inplace_merge(_Iter __first, _Iter __middle, _Sent __last,
+		  _Comp __comp = {}, _Proj __proj = {})
+    {
+      // TODO: is it worth reimplementing std::inplace_merge 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::inplace_merge(std::move(__first), std::move(__middle), __lasti,
+			 std::move(__proj_comp));
+      return __lasti;
+    }
+
+  template<bidirectional_range _Range,
+	   typename _Comp = ranges::less, typename _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+    safe_iterator_t<_Range>
+    inplace_merge(_Range&& __r, iterator_t<_Range> __middle,
+		  _Comp __comp = {}, _Proj __proj = {})
+    {
+      return ranges::inplace_merge(ranges::begin(__r), std::move(__middle),
+				   ranges::end(__r),
+				   std::move(__comp), std::move(__proj));
+    }
+
 } // namespace ranges
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 #endif // concepts
 #endif // C++20
 #endif // _RANGES_ALGO_H
-
diff --git a/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constrained.cc
new file mode 100644
index 0000000..8560568
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constrained.cc
@@ -0,0 +1,69 @@
+// 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 <vector>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::test_range;
+using __gnu_test::bidirectional_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+  int x[] = {1,2,3,4,5};
+  for (int i = 0; i <= 5; i++)
+    for (int j = 0; j <= 5; j++)
+      {
+	std::vector<int> v(x, x+i);
+	v.insert(v.end(), x, x+j);
+	ranges::sort(v);
+
+	test_range<int, bidirectional_iterator_wrapper> rz(&v[0], &v[0]+i+j);
+	auto result = ranges::inplace_merge(rz, next(ranges::begin(rz), i));
+	VERIFY( result == rz.end() );
+
+	VERIFY( ranges::is_sorted(rz) );
+      }
+}
+
+void
+test02()
+{
+  struct X { int i, j; };
+  X x[] = { {1, 1}, {3, 4}, {5, 5}, {2, 2}, {2, 3} };
+  auto comp = ranges::greater{};
+  auto proj = [] (X a) { return -a.i; };
+  ranges::inplace_merge(x, x+3, x+5, comp, proj);
+  VERIFY( ranges::is_sorted(x, {}, &X::i) );
+  VERIFY( ranges::is_sorted(x, {}, &X::j) );
+}
+
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/merge/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/merge/constrained.cc
new file mode 100644
index 0000000..3f3a0f7
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/merge/constrained.cc
@@ -0,0 +1,75 @@
+// 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 <vector>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::test_range;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+  int x[] = {1,2,3,4,5};
+  for (int i = 0; i <= 5; i++)
+    for (int j = 0; j <= 5; j++)
+      {
+	int z[10];
+	test_range<int, input_iterator_wrapper> rx(x, x+i), ry(x, x+j);
+	test_range<int, output_iterator_wrapper> rz(z, z+i+j);
+	auto [in1,in2,out] = ranges::merge(rx, ry, rz.begin());
+	VERIFY( in1 == rx.end() );
+	VERIFY( in2 == ry.end() );
+	VERIFY( out == rz.end() );
+
+	std::vector<int> v(x, x+i);
+	v.insert(v.end(), x, x+j);
+	ranges::sort(v);
+
+	VERIFY( ranges::equal(v.begin(), v.end(), z, z+i+j) );
+      }
+}
+
+constexpr bool
+test02()
+{
+  int x[] = {-1,-3,-5};
+  int y[] = {2,4,6};
+  int z[6];
+  ranges::merge(x, x+3, y, y+3, z,
+		ranges::greater{}, {}, [] (int a) { return -a; });
+
+  const int w[6] = {-1, 2, -3, 4, -5, 6};
+  return ranges::equal(w, z);
+}
+
+
+int
+main()
+{
+  test01();
+  static_assert(test02());
+}



More information about the Libstdc++-cvs mailing list