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

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