diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -60,11 +60,11 @@ Write,unique_copy,Not assigned,n/a,Not started Write,partition_copy,Not assigned,n/a,Not started Write,partial_sort_copy,Not assigned,n/a,Not started -Merge,merge,Not assigned,n/a,Not started -Merge,set_difference,Not assigned,n/a,Not started -Merge,set_intersection,Not assigned,n/a,Not started -Merge,set_symmetric_difference,Not assigned,n/a,Not started -Merge,set_union,Not assigned,n/a,Not started +Merge,merge,Hui Xie,n/a,✅ +Merge,set_difference,Hui Xie,n/a,Not started +Merge,set_intersection,Hui Xie,n/a,Not started +Merge,set_symmetric_difference,Hui Xie,n/a,Not started +Merge,set_union,Not assigned,Hui Xie,Not started Permutation,remove,Not assigned,n/a,Not started Permutation,remove_if,Not assigned,n/a,Not started Permutation,reverse,Nikolas Klauser,`D125752 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -94,6 +94,7 @@ __algorithm/ranges_lower_bound.h __algorithm/ranges_max.h __algorithm/ranges_max_element.h + __algorithm/ranges_merge.h __algorithm/ranges_min.h __algorithm/ranges_min_element.h __algorithm/ranges_minmax.h diff --git a/libcxx/include/__algorithm/ranges_merge.h b/libcxx/include/__algorithm/ranges_merge.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_merge.h @@ -0,0 +1,142 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MERGE_H +#define _LIBCPP___ALGORITHM_RANGES_MERGE_H + +#include "__algorithm/in_in_out_result.h" +#include "__algorithm/ranges_copy.h" +#include "__iterator/concepts.h" +#include "__iterator/mergeable.h" +#include "__functional/identity.h" +#include "__functional/invoke.h" +#include "__functional/ranges_operations.h" +#include "__utility/move.h" +#include "__ranges/access.h" +#include "__ranges/concepts.h" +#include "__ranges/dangling.h" +#include "__type_traits/decay.h" +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template +using merge_result = in_in_out_result<_InIter1, _InIter2, _OutIter>; + +template < + class _InIter1, + class _Sent1, + class _InIter2, + class _Sent2, + class _OutIter, + class _Comp, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI constexpr ranges::merge_result, decay_t<_InIter2>, decay_t<_OutIter>> +__merge_impl( + _InIter1&& __first1, + _Sent1&& __last1, + _InIter2&& __first2, + _Sent2&& __last2, + _OutIter&& __result, + _Comp&& __comp, + _Proj1&& __proj1, + _Proj2&& __proj2) { + for (; __first1 != __last1 && __first2 != __last2; ++__result) { + if (std::invoke(__comp, std::invoke(__proj2, *__first2), std::invoke(__proj1, *__first1))) { + *__result = *__first2; + ++__first2; + } else { + *__result = *__first1; + ++__first1; + } + } + auto __ret1 = ranges::copy(std::move(__first1), std::move(__last1), std::move(__result)); + auto __ret2 = ranges::copy(std::move(__first2), std::move(__last2), std::move(__ret1.out)); + return {std::move(__ret1.in), std::move(__ret2.in), std::move(__ret2.out)}; +} + +namespace __merge { + + struct __fn { + template < + input_iterator _InIter1, + sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, + sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + class _Comp = ranges::less, + class _Proj1 = identity, + class _Proj2 = identity > + requires std::mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr ranges::merge_result<_InIter1, _InIter2, _OutIter> operator()( + _InIter1 __first1, + _Sent1 __last1, + _InIter2 __first2, + _Sent2 __last2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return ranges::__merge_impl(__first1, __last1, __first2, __last2, __result, __comp, __proj1, __proj2); + } + + template < + ranges::input_range _Range1, + ranges::input_range _Range2, + std::weakly_incrementable _OutIter, + class _Comp = ranges::less, + class _Proj1 = identity, + class _Proj2 = identity > + requires std::mergeable< + ranges::iterator_t<_Range1>, + ranges::iterator_t<_Range2>, + _OutIter, + _Comp, + _Proj1, + _Proj2> _LIBCPP_HIDE_FROM_ABI constexpr ranges:: + merge_result, ranges::borrowed_iterator_t<_Range2>, _OutIter> + operator()( + _Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return ranges::__merge_impl( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + std::move(__result), + std::move(__comp), + std::move(__proj1), + std::move(__proj2)); + } + }; + +} // namespace __merge + +inline namespace __cpo { + inline constexpr auto merge = __merge::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MERGE_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -470,6 +470,23 @@ constexpr ranges::move_result, O> ranges::move(R&& r, O result); // since C++20 + template + using merge_result = in_in_out_result; // since C++20 + + template S1, input_iterator I2, sentinel_for S2, + weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, + class Proj2 = identity> + requires mergeable + constexpr merge_result + merge(I1 first1, S1 last1, I2 first2, S2 last2, O result, + Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + + template + requires mergeable, iterator_t, O, Comp, Proj1, Proj2> + constexpr merge_result, borrowed_iterator_t, O> + merge(R1&& r1, R2&& r2, O result, + Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 } @@ -1216,6 +1233,7 @@ #include <__algorithm/ranges_minmax.h> #include <__algorithm/ranges_minmax_element.h> #include <__algorithm/ranges_mismatch.h> +#include <__algorithm/ranges_merge.h> #include <__algorithm/ranges_move.h> #include <__algorithm/ranges_move_backward.h> #include <__algorithm/ranges_none_of.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -338,6 +338,7 @@ module ranges_minmax { private header "__algorithm/ranges_minmax.h" } module ranges_minmax_element { private header "__algorithm/ranges_minmax_element.h" } module ranges_mismatch { private header "__algorithm/ranges_mismatch.h" } + module ranges_merge { private header "__algorithm/ranges_merge.h" } module ranges_move { private header "__algorithm/ranges_move.h" } module ranges_move_backward { private header "__algorithm/ranges_move_backward.h" } module ranges_none_of { private header "__algorithm/ranges_none_of.h" } diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -79,7 +79,7 @@ { void *a[10] = {}; void *b[10] = {}; - //void *half[5] = {}; + void *half[5] = {}; void **first = a; void **mid = a+5; void **last = a+10; @@ -151,8 +151,8 @@ (void)std::ranges::max(a, Less(&copies)); assert(copies == 0); (void)std::ranges::max_element(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::max_element(a, Less(&copies)); assert(copies == 0); - //(void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); - //(void)std::ranges::merge(half, half, b, Less(&copies)); assert(copies == 0); + (void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); + (void)std::ranges::merge(half, half, b, Less(&copies)); assert(copies == 0); (void)std::ranges::min(value, value, Less(&copies)); assert(copies == 0); (void)std::ranges::min({ value, value }, Less(&copies)); assert(copies == 0); (void)std::ranges::min(a, Less(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -61,7 +61,7 @@ { T a[10] = {}; T b[10] = {}; - //T half[5] = {}; + T half[5] = {}; T *first = a; T *mid = a+5; T *last = a+10; @@ -134,8 +134,8 @@ (void)std::ranges::max(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::max_element(first, last, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::max_element(a, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::merge(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::merge(half, half, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::merge(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::merge(half, half, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::min(T(), T(), Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::min({ T(), T() }, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::min(a, Less(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -131,6 +131,7 @@ #include <__algorithm/ranges_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.h'}} #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}} #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}} +#include <__algorithm/ranges_merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_merge.h'}} #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}} #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}} #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp @@ -0,0 +1,599 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S1, input_­iterator I2, sentinel_­for S2, +// weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, +// class Proj2 = identity> +// requires mergeable +// constexpr merge_result +// merge(I1 first1, S1 last1, I2 first2, S2 last2, O result, +// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 +// +// template +// requires mergeable, iterator_t, O, Comp, Proj1, Proj2> +// constexpr merge_result, borrowed_iterator_t, O> +// merge(R1&& r1, R2&& r2, O result, +// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + +#include +#include + +#include "almost_satisfies_types.h" +#include "MoveOnly.h" +#include "test_iterators.h" + +template +concept HasMerge = requires(Args&&... args) { std::ranges::merge(std::forward(args)...); }; + +// clang-format off + +using NotInputIter = InputIteratorNotDerivedFrom; +using NotSentinel = SentinelForNotSemiregular; + +template +using Sent = sentinel_wrapper; + +// Test iterator overload's constraints: +// ===================================== + +// | InIter1 | Sent1 | InIter2 | Sent2 | OutIter | +// |-----------------|-------------------|----------------|-----------------|-----------------| +static_assert( HasMerge< + int*, int*, int*, int*, int* >); +// |-----------------|-------------------|----------------|-----------------|-----------------| +// !std::input_iterator +static_assert(!HasMerge< + NotInputIter, Sent, int*, int*, int* >); +// |-----------------|-------------------|----------------|-----------------|-----------------| +// !std::sentinel_for +static_assert(!HasMerge< + int*, NotSentinel, int*, int*, int* >); +// |-----------------|-------------------|----------------|-----------------|-----------------| +// !std::input_iterator +static_assert(!HasMerge< + int*, int*, NotInputIter, Sent, int* >); +// |-----------------|-------------------|----------------|-----------------|-----------------| +// !std::sentinel_for +static_assert(!HasMerge< + int*, int*, int*, NotSentinel, int* >); +// |-----------------|-------------------|----------------|-----------------|-----------------| +// !std::weakly_incrementable +static_assert(!HasMerge< + int*, int*, int*, int*, WeaklyIncrementableNotMovable>); +// |-----------------|-------------------|----------------|-----------------|-----------------| +// !std::mergeable +static_assert(!HasMerge< + MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly* >); +// |-----------------|-------------------|----------------|-----------------|-----------------| + +// Test range overload's constraints: +// ===================================== + +template > +using Range = UncheckedRange; + + +// | R1 | R2 | OutIter | +// |------------------------|--------------------------|--------------------------| +static_assert(HasMerge< + Range, Range, int* >); +// |------------------------|--------------------------|--------------------------| +// !std::input_range +static_assert(!HasMerge< + Range, Range, int* >); +// |------------------------|--------------------------|--------------------------| +// !std::input_range +static_assert(!HasMerge< + Range, Range, int* >); +// |------------------------|--------------------------|--------------------------| +// !std::weakly_incrementable +static_assert(!HasMerge< + Range, Range, WeaklyIncrementableNotMovable >); +// |------------------------|--------------------------|--------------------------| +// !mergeable, iterator_t, O, Comp, Proj1, Proj2> +static_assert(!HasMerge< + Range, Range, MoveOnly* >); +// |------------------------|--------------------------|--------------------------| + +// clang-format on + +// test the range is correctly merged for different kinds of input ranges and output iterator +template +struct type_list {}; + +template +constexpr auto cartesian_product_impl( + std::tuple, std::tuple, std::tuple, std::index_sequence) + -> type_list< type_list< + std::tuple_element_t>, + std::tuple_element_t>, + std::tuple_element_t> >... >; + +template +constexpr auto +cartesian_product(type_list, type_list, type_list) -> decltype(cartesian_product_impl( + std::declval>(), + std::declval>(), + std::declval>(), + std::make_index_sequence())) { + return {}; +} + +using In1Iters = type_list< + cpp20_input_iterator, + forward_iterator, + bidirectional_iterator, + random_access_iterator, + contiguous_iterator >; + +using In2Iters = In1Iters; + +using OutIters = type_list< + cpp17_output_iterator, + cpp20_output_iterator, + cpp17_input_iterator, + cpp20_input_iterator, + forward_iterator, + bidirectional_iterator, + random_access_iterator, + contiguous_iterator>; + +template +constexpr void runAllPermutations(Test test, type_list) { + (test(Sigs{}), ...); +} + +constexpr void runAllPermutations(auto test) { + runAllPermutations(test, cartesian_product(In1Iters{}, In2Iters{}, OutIters{})); +} + +template +constexpr void testMergeImpl(std::array& in1, std::array& in2, const auto& expected) { + // TODO: std::ranges::merge calls std::ranges::copy + // std::ranges::copy(contiguous_iterator, sentinel_wrapper>, contiguous_iterator) doesn't seem to work. + // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator into int*, and then it failed because there is no == between int* and sentinel_wrapper> + using Sent1 = std::conditional_t, In1, sentinel_wrapper>; + using Sent2 = std::conditional_t, In2, sentinel_wrapper>; + + // iterator overload + { + std::array out; + std::same_as> decltype(auto) result = std::ranges::merge( + In1{in1.data()}, + Sent1{In1{in1.data() + in1.size()}}, + In2{in2.data()}, + Sent2{In2{in2.data() + in2.size()}}, + Out{out.data()}); + assert(std::ranges::equal(out, expected)); + + assert(base(result.in1) == in1.data() + in1.size()); + assert(base(result.in2) == in2.data() + in2.size()); + assert(base(result.out) == out.data() + out.size()); + } + + // range overload + { + std::array out; + std::ranges::subrange r1{In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}}; + std::ranges::subrange r2{In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}}; + std::same_as> decltype(auto) result = + std::ranges::merge(r1, r2, Out{out.data()}); + assert(std::ranges::equal(out, expected)); + + assert(base(result.in1) == in1.data() + in1.size()); + assert(base(result.in2) == in2.data() + in2.size()); + assert(base(result.out) == out.data() + out.size()); + } +} + +constexpr bool test() { + // Test merge produces correct result for different kinds of iterators + { + constexpr auto testMerge = [](type_list) { + { + std::array in1{0, 1, 5, 6, 9, 10}; + std::array in2{3, 6, 7, 9, 13, 15, 100}; + std::array expected{0, 1, 3, 5, 6, 6, 7, 9, 9, 10, 13, 15, 100}; + testMergeImpl(in1, in2, expected); + } + + { + std::array in1{0, 1, 2}; + std::array in2{0, 1, 2}; + std::array expected{0, 0, 1, 1, 2, 2}; + testMergeImpl(in1, in2, expected); + } + + { + std::array in1{0}; + std::array in2{0, 0, 0, 1}; + std::array expected{0, 0, 0, 0, 1}; + testMergeImpl(in1, in2, expected); + } + }; + runAllPermutations(testMerge); + } + + // check that ranges::dangling is returned for non-borrowed_range and iterator_t is returned for borrowed_range + { + constexpr auto testDangling = [](type_list) { + struct NonBorrowRange { + int* data_; + size_t size_; + + // TODO: std::ranges::merge calls std::ranges::copy + // std::ranges::copy(contiguous_iterator, sentinel_wrapper>, contiguous_iterator) doesn't seem to work. + // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator into int*, and then it failed because there is no == between int* and sentinel_wrapper> + using Sent = std::conditional_t, In2, sentinel_wrapper>; + + constexpr NonBorrowRange(int* d, size_t s) : data_{d}, size_{s} {} + + constexpr In2 begin() const { return In2{data_}; }; + constexpr Sent end() const { return Sent{In2{data_ + size_}}; }; + }; + + std::array r1{3, 6, 7, 9}; + std::array r2{2, 3, 4}; + std::array out; + std::same_as::iterator, std::ranges::dangling, int*>> decltype(auto) + result = std::ranges::merge(r1, NonBorrowRange{r2.data(), r2.size()}, out.data()); + assert(base(result.in1) == r1.end()); + assert(base(result.out) == out.data() + out.size()); + assert(std::ranges::equal(out, std::array{2, 3, 3, 4, 6, 7, 9})); + }; + runAllPermutations(testDangling); + } + + // check that every element is copied exactly once + struct TracedCopy { + int copy_assign = 0; + int data = 0; + + constexpr TracedCopy() = default; + constexpr TracedCopy(int i) : data(i) {} + constexpr TracedCopy(const TracedCopy& other) : copy_assign(other.copy_assign), data(other.data) {} + + constexpr TracedCopy(TracedCopy&& other) = delete; + constexpr TracedCopy& operator=(TracedCopy&& other) = delete; + + constexpr TracedCopy& operator=(const TracedCopy& other) { + copy_assign = other.copy_assign + 1; + data = other.data; + return *this; + } + + constexpr bool operator==(const TracedCopy& o) const { return data == o.data; } + constexpr auto operator<=>(const TracedCopy& o) const { return data <=> o.data; } + }; + { + std::array r1{3, 5, 8}; + std::array r2{1, 3, 8}; + using Iter = std::array::iterator; + + // iterator overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data()); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + assert(std::ranges::equal(out, std::array{1, 3, 3, 5, 8, 8})); + + std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; }); + } + + // range overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1, r2, out.data()); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + assert(std::ranges::equal(out, std::array{1, 3, 3, 5, 8, 8})); + + std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; }); + } + } + + struct IntAndID { + int data; + int id; + + constexpr auto operator==(const IntAndID& o) const { return data == o.data; } + constexpr auto operator<=>(const IntAndID& o) const { return data <=> o.data; } + }; + + // Algorithm is stable: equal elements should merged in the original order + { + std::array r1{{{0, 0}, {0, 1}, {0, 2}}}; + std::array r2{{{1, 0}, {1, 1}, {1, 2}}}; + + // iterator overload + { + std::array out; + std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data()); + + assert(std::ranges::equal(out, std::array{0, 0, 0, 1, 1, 1}, std::ranges::equal_to{}, &IntAndID::data)); + // ID should be in their original order + assert(std::ranges::equal(out, std::array{0, 1, 2, 0, 1, 2}, std::ranges::equal_to{}, &IntAndID::id)); + } + + // range overload + { + std::array out; + std::ranges::merge(r1, r2, out.data()); + + assert(std::ranges::equal(out, std::array{0, 0, 0, 1, 1, 1}, std::ranges::equal_to{}, &IntAndID::data)); + // ID should be in their original order + assert(std::ranges::equal(out, std::array{0, 1, 2, 0, 1, 2}, std::ranges::equal_to{}, &IntAndID::id)); + } + } + + // Equal elements in R1 should be merged before equal elements in R2 + { + std::array r1{{{0, 1}, {1, 1}, {2, 1}}}; + std::array r2{{{0, 2}, {1, 2}, {2, 2}}}; + + // iterator overload + { + std::array out; + std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data()); + + assert(std::ranges::equal(out, std::array{0, 0, 1, 1, 2, 2}, std::ranges::equal_to{}, &IntAndID::data)); + // ID 1 (from R1) should be in front of ID 2 (from R2) + assert(std::ranges::equal(out, std::array{1, 2, 1, 2, 1, 2}, std::ranges::equal_to{}, &IntAndID::id)); + } + + // range overload + { + std::array out; + std::ranges::merge(r1, r2, out.data()); + + assert(std::ranges::equal(out, std::array{0, 0, 1, 1, 2, 2}, std::ranges::equal_to{}, &IntAndID::data)); + // ID 1 (from R1) should be in front of ID 2 (from R2) + assert(std::ranges::equal(out, std::array{1, 2, 1, 2, 1, 2}, std::ranges::equal_to{}, &IntAndID::id)); + } + } + + struct Data { + int data; + + constexpr bool smallerThan(const Data& o) const { return data < o.data; } + }; + // Test custom comparator + { + std::array r1{Data{4}, Data{8}, Data{12}}; + std::array r2{Data{5}, Data{9}}; + using Iter1 = std::array::iterator; + using Iter2 = std::array::iterator; + + // iterator overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), [](const Data& x, const Data& y) { + return x.data < y.data; + }); + + assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data)); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + } + + // range overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1, r2, out.data(), [](const Data& x, const Data& y) { return x.data < y.data; }); + + assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data)); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + } + } + + // Test Projection + { + std::array r1{Data{4}, Data{8}, Data{12}}; + std::array r2{Data{5}, Data{9}}; + using Iter1 = std::array::iterator; + using Iter2 = std::array::iterator; + + const auto proj = [](const Data& d) { return d.data; }; + + // iterator overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), std::ranges::less{}, proj, proj); + + assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data)); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + } + + // range overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1, r2, out.data(), std::ranges::less{}, proj, proj); + + assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data)); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + } + + // member pointer Comparator + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1, r2, out.data(), &Data::smallerThan); + + assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data)); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + } + + // member pointer Projection + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data); + + assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data)); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + } + } + + // Complexity: at most N - 1 comparisons and applications of each projection. + { + Data r1[] = {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}}; + Data r2[] = {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}}; + std::array out; + std::size_t numberOfComp = 0; + std::size_t numberOfProj1 = 0; + std::size_t numberOfProj2 = 0; + + const auto comp = [&numberOfComp](int x, int y) { + ++numberOfComp; + return x < y; + }; + + const auto proj1 = [&numberOfProj1](const Data& d) { + ++numberOfProj1; + return d.data; + }; + + const auto proj2 = [&numberOfProj2](const Data& d) { + ++numberOfProj2; + return d.data; + }; + + std::ranges::merge(r1, r2, out.data(), comp, proj1, proj2); + assert(std::ranges::equal( + out, + std::array{0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9}, + std::ranges::equal_to{}, + &Data::data)); + assert(numberOfComp < out.size()); + assert(numberOfProj1 < out.size()); + assert(numberOfProj2 < out.size()); + } + + // Comparator convertible to bool + { + struct ConvertibleToBool { + bool b; + constexpr operator bool() const { return b; } + }; + Data r1[] = {{2}, {4}}; + Data r2[] = {{3}, {4}, {5}}; + std::array out; + + const auto comp = [](const Data& x, const Data& y) { return ConvertibleToBool{x.data < y.data}; }; + + std::ranges::merge(r1, r2, out.data(), comp); + assert(std::ranges::equal(out, std::array{2, 3, 4, 4, 5}, std::ranges::equal_to{}, &Data::data)); + } + + // One range is empty + { + auto r1 = std::views::empty; + std::array r2 = {{{3}, {4}, {5}}}; + + // iterator overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.begin() + r2.size(), out.data(), &Data::smallerThan); + + assert(std::ranges::equal(out, std::array{3, 4, 5}, std::ranges::equal_to{}, &Data::data)); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + } + + // range overload + { + std::array out; + std::same_as::iterator, Data*>> decltype(auto) result = + std::ranges::merge(r1, r2, out.data(), &Data::smallerThan); + + assert(std::ranges::equal(out, std::array{3, 4, 5}, std::ranges::equal_to{}, &Data::data)); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.end()); + } + } + + // Both ranges are empty + { + auto r1 = std::views::empty; + auto r2 = std::views::empty; + + // iterator overload + { + std::array out{}; + std::same_as> decltype(auto) result = + std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data()); + + assert(out[0].copy_assign == 0); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.begin()); + } + + // range overload + { + std::array out{}; + std::same_as> decltype(auto) result = + std::ranges::merge(r1, r2, out.data()); + + assert(out[0].copy_assign == 0); + + assert(result.in1 == r1.end()); + assert(result.in2 == r2.end()); + assert(result.out == out.begin()); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -98,7 +98,7 @@ //static_assert(test(std::ranges::make_heap, a)); static_assert(test(std::ranges::max, a)); static_assert(test(std::ranges::max_element, a)); -//static_assert(test(std::ranges::merge, a, a, a)); +static_assert(test(std::ranges::merge, a, a, a)); static_assert(test(std::ranges::min, a)); static_assert(test(std::ranges::min_element, a)); static_assert(test(std::ranges::minmax, a));