[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