1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11// <algorithm>
12
13// template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
14// class Proj = identity>
15// requires sortable<I, Comp, Proj>
16// constexpr I // constexpr since C++26
17// inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {}); // Since C++20
18//
19// template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
20// requires sortable<iterator_t<R>, Comp, Proj>
21// constexpr borrowed_iterator_t<R> // constexpr since C++26
22// inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {},
23// Proj proj = {}); // Since C++20
24
25#include <algorithm>
26#include <array>
27#include <concepts>
28#include <functional>
29#include <ranges>
30#include <type_traits>
31
32#include "almost_satisfies_types.h"
33#include "counting_predicates.h"
34#include "counting_projection.h"
35#include "test_iterators.h"
36
37template < class Iter,
38 class Middle = Iter,
39 class Sent = sentinel_wrapper<std::remove_cvref_t<Iter>>,
40 class Comp = std::ranges::less,
41 class Proj = std::identity>
42concept HasInplaceMergeIter =
43 requires(Iter&& iter, Middle&& mid, Sent&& sent, Comp&& comp, Proj&& proj) {
44 std::ranges::inplace_merge(
45 std::forward<Iter>(iter),
46 std::forward<Middle>(mid),
47 std::forward<Sent>(sent),
48 std::forward<Comp>(comp),
49 std::forward<Proj>(proj));
50 };
51
52static_assert(HasInplaceMergeIter<int*, int*, int*>);
53
54// !bidirectional_iterator<I>
55static_assert(!HasInplaceMergeIter<BidirectionalIteratorNotDerivedFrom>);
56static_assert(!HasInplaceMergeIter<cpp20_input_iterator<int*>>);
57
58// !sentinel_for<S, I>
59static_assert(!HasInplaceMergeIter<int*, int*, SentinelForNotSemiregular>);
60static_assert(!HasInplaceMergeIter<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
61
62// !sortable<I, Comp, Proj>
63static_assert(!HasInplaceMergeIter<int*, int*, int*, ComparatorNotCopyable<int*>>);
64static_assert(!HasInplaceMergeIter<const int*, const int*, const int*>);
65
66template < class Range,
67 class Middle = std::ranges::iterator_t<Range>,
68 class Comp = std::ranges::less,
69 class Proj = std::identity>
70concept HasInplaceMergeRange =
71 requires(Range&& r, Middle&& mid, Comp&& comp, Proj&& proj) {
72 std::ranges::inplace_merge(
73 std::forward<Range>(r), std::forward<Middle>(mid), std::forward<Comp>(comp), std::forward<Proj>(proj));
74 };
75
76template <class T>
77using R = UncheckedRange<T>;
78
79static_assert(HasInplaceMergeRange<R<int*>, int*>);
80
81// !bidirectional_range<R>
82static_assert(!HasInplaceMergeRange<R<cpp20_input_iterator<int*>>>);
83static_assert(!HasInplaceMergeRange<R<BidirectionalIteratorNotDecrementable>>);
84
85// !sortable<iterator_t<R>, Comp, Proj>
86static_assert(!HasInplaceMergeRange<R<int*>, int*, ComparatorNotCopyable<int*>>);
87static_assert(!HasInplaceMergeIter<R<const int*>, const int*>);
88
89template <class In, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
90TEST_CONSTEXPR_CXX26 void testInplaceMergeImpl(std::array<int, N1> input, int midIdx, std::array<int, N2> expected) {
91 assert(std::is_sorted(input.begin(), input.begin() + midIdx));
92 assert(std::is_sorted(input.begin() + midIdx, input.end()));
93 assert(std::is_sorted(expected.begin(), expected.end()));
94
95 using Sent = SentWrapper<In>;
96
97 // iterator overload
98 {
99 auto in = input;
100 std::same_as<In> decltype(auto) result =
101 std::ranges::inplace_merge(In{in.data()}, In{in.data() + midIdx}, Sent{In{in.data() + in.size()}});
102 assert(std::ranges::equal(in, expected));
103 assert(base(result) == in.data() + in.size());
104 }
105
106 // range overload
107 {
108 auto in = input;
109 std::ranges::subrange r{In{in.data()}, Sent{In{in.data() + in.size()}}};
110 std::same_as<In> decltype(auto) result = std::ranges::inplace_merge(r, In{in.data() + midIdx});
111 assert(std::ranges::equal(in, expected));
112 assert(base(result) == in.data() + in.size());
113 }
114}
115
116template <class In, template <class> class SentWrapper>
117TEST_CONSTEXPR_CXX26 void testImpl() {
118 // sorted range
119 {
120 std::array in{0, 1, 5, 6, 9, 10};
121 std::array expected = in;
122 testInplaceMergeImpl<In, SentWrapper>(in, 3, expected);
123 }
124
125 // [first, mid) is longer
126 {
127 std::array in{0, 5, 9, 15, 18, 22, 2, 4, 6, 10};
128 std::array expected = {0, 2, 4, 5, 6, 9, 10, 15, 18, 22};
129 testInplaceMergeImpl<In, SentWrapper>(in, 6, expected);
130 }
131
132 // [first, mid) is shorter
133 {
134 std::array in{0, 5, 9, 2, 4, 6, 10};
135 std::array expected = {0, 2, 4, 5, 6, 9, 10};
136 testInplaceMergeImpl<In, SentWrapper>(in, 3, expected);
137 }
138
139 // [first, mid) == [mid, last)
140 {
141 std::array in{0, 5, 9, 0, 5, 9};
142 std::array expected = {0, 0, 5, 5, 9, 9};
143 testInplaceMergeImpl<In, SentWrapper>(in, 3, expected);
144 }
145
146 // duplicates within each range
147 {
148 std::array in{1, 5, 5, 2, 9, 9, 9};
149 std::array expected = {1, 2, 5, 5, 9, 9, 9};
150 testInplaceMergeImpl<In, SentWrapper>(in, 3, expected);
151 }
152
153 // all the same
154 {
155 std::array in{5, 5, 5, 5, 5, 5, 5, 5};
156 std::array expected = in;
157 testInplaceMergeImpl<In, SentWrapper>(in, 5, expected);
158 }
159
160 // [first, mid) is empty (mid == begin)
161 {
162 std::array in{0, 1, 5, 6, 9, 10};
163 std::array expected = in;
164 testInplaceMergeImpl<In, SentWrapper>(in, 0, expected);
165 }
166
167 // [mid, last] is empty (mid == end)
168 {
169 std::array in{0, 1, 5, 6, 9, 10};
170 std::array expected = in;
171 testInplaceMergeImpl<In, SentWrapper>(in, 6, expected);
172 }
173
174 // both empty
175 {
176 std::array<int, 0> in{};
177 std::array expected = in;
178 testInplaceMergeImpl<In, SentWrapper>(in, 0, expected);
179 }
180
181 // mid == first + 1
182 {
183 std::array in{9, 2, 5, 7, 10};
184 std::array expected{2, 5, 7, 9, 10};
185 testInplaceMergeImpl<In, SentWrapper>(in, 1, expected);
186 }
187
188 // mid == last - 1
189 {
190 std::array in{2, 5, 7, 10, 9};
191 std::array expected{2, 5, 7, 9, 10};
192 testInplaceMergeImpl<In, SentWrapper>(in, 4, expected);
193 }
194}
195
196template < template <class> class SentWrapper>
197TEST_CONSTEXPR_CXX26 void withAllPermutationsOfIter() {
198 testImpl<bidirectional_iterator<int*>, SentWrapper>();
199 testImpl<random_access_iterator<int*>, SentWrapper>();
200 testImpl<contiguous_iterator<int*>, SentWrapper>();
201 testImpl<int*, SentWrapper>();
202}
203
204TEST_CONSTEXPR_CXX26 bool test() {
205 withAllPermutationsOfIter<std::type_identity_t>();
206 withAllPermutationsOfIter<sentinel_wrapper>();
207
208 struct Data {
209 int data;
210 };
211
212 const auto equal = [](const Data& x, const Data& y) { return x.data == y.data; };
213 // Test custom comparator
214 {
215 std::array<Data, 4> input{._M_elems: {{.data: 4}, {.data: 8}, {.data: 2}, {.data: 5}}};
216 std::array<Data, 4> expected{._M_elems: {{.data: 2}, {.data: 4}, {.data: 5}, {.data: 8}}};
217 const auto comp = [](const Data& x, const Data& y) { return x.data < y.data; };
218
219 // iterator overload
220 {
221 auto in = input;
222 auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 2, in.end(), comp);
223 assert(std::ranges::equal(in, expected, equal));
224 assert(result == in.end());
225 }
226
227 // range overload
228 {
229 auto in = input;
230 auto result = std::ranges::inplace_merge(in, in.begin() + 2, comp);
231 assert(std::ranges::equal(in, expected, equal));
232 assert(result == in.end());
233 }
234 }
235
236 // Test custom projection
237 {
238 std::array<Data, 4> input{._M_elems: {{.data: 4}, {.data: 8}, {.data: 2}, {.data: 5}}};
239 std::array<Data, 4> expected{._M_elems: {{.data: 2}, {.data: 4}, {.data: 5}, {.data: 8}}};
240
241 const auto proj = &Data::data;
242
243 // iterator overload
244 {
245 auto in = input;
246 auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 2, in.end(), {}, proj);
247 assert(std::ranges::equal(in, expected, equal));
248 assert(result == in.end());
249 }
250
251 // range overload
252 {
253 auto in = input;
254 auto result = std::ranges::inplace_merge(in, in.begin() + 2, {}, proj);
255 assert(std::ranges::equal(in, expected, equal));
256 assert(result == in.end());
257 }
258 }
259
260 // Remarks: Stable.
261 {
262 struct IntAndID {
263 int data;
264 int id;
265 constexpr auto operator<=>(const IntAndID& rhs) const { return data <=> rhs.data; }
266 constexpr auto operator==(const IntAndID& rhs) const { return data == rhs.data; }
267 };
268 std::array<IntAndID, 6> input{._M_elems: {{.data: 0, .id: 0}, {.data: 1, .id: 0}, {.data: 2, .id: 0}, {.data: 0, .id: 1}, {.data: 1, .id: 1}, {.data: 2, .id: 1}}};
269
270 // iterator overload
271 {
272 auto in = input;
273 auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 3, in.end());
274 assert(std::ranges::equal(in, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data));
275 assert(std::ranges::equal(in, std::array{0, 1, 0, 1, 0, 1}, {}, &IntAndID::id));
276 assert(result == in.end());
277 }
278
279 // range overload
280 {
281 auto in = input;
282 auto result = std::ranges::inplace_merge(in, in.begin() + 3);
283 assert(std::ranges::equal(in, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data));
284 assert(std::ranges::equal(in, std::array{0, 1, 0, 1, 0, 1}, {}, &IntAndID::id));
285 assert(result == in.end());
286 }
287 }
288
289 // Complexity: Let N = last - first :
290 // - For the overloads with no ExecutionPolicy, and if enough
291 // additional memory is available, exactly N - 1 comparisons.
292 // - Otherwise, O(NlogN) comparisons.
293 // In either case, twice as many projections as comparisons.
294 {
295 std::array input{1, 2, 3, 3, 3, 7, 7, 2, 2, 5, 5, 6, 6};
296 std::array expected{1, 2, 2, 2, 3, 3, 3, 5, 5, 6, 6, 7, 7};
297 auto mid = 7;
298 // iterator overload
299 {
300 auto in = input;
301 int numberOfComp = 0;
302 int numberOfProj = 0;
303 auto result = std::ranges::inplace_merge(
304 in.begin(),
305 in.begin() + mid,
306 in.end(),
307 counting_predicate{std::ranges::less{}, numberOfComp},
308 counting_projection{numberOfProj});
309 assert(std::ranges::equal(in, expected));
310 assert(result == in.end());
311
312 // the spec specifies exactly N-1 comparison but we actually
313 // do not invoke as many times as specified
314 assert(numberOfComp <= static_cast<int>(in.size() - 1));
315 assert(numberOfProj <= 2 * numberOfComp);
316 }
317 // range overload
318 {
319 auto in = input;
320 int numberOfComp = 0;
321 int numberOfProj = 0;
322 auto result = std::ranges::inplace_merge(
323 in,
324 in.begin() + mid,
325 counting_predicate{std::ranges::less{}, numberOfComp},
326 counting_projection{numberOfProj});
327 assert(std::ranges::equal(in, expected));
328 assert(result == in.end());
329 assert(numberOfComp <= static_cast<int>(in.size() - 1));
330 assert(numberOfProj <= 2 * numberOfComp);
331 }
332 }
333 return true;
334}
335
336int main(int, char**) {
337 test();
338#if TEST_STD_VER >= 26
339 static_assert(test());
340#endif
341
342 return 0;
343}
344

source code of libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp