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// <algorithm>
10
11// template<class BidirectionalIterator, class Compare>
12// constexpr void // constexpr since C++26
13// inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
14
15#include <algorithm>
16#include <cassert>
17#include <functional>
18#include <vector>
19
20#include "constexpr_random.h"
21#include "test_macros.h"
22
23#if TEST_STD_VER >= 11
24#include <memory>
25
26struct indirect_less {
27 template <class P>
28 TEST_CONSTEXPR_CXX26 bool operator()(const P& x, const P& y) const {
29 return *x < *y;
30 }
31};
32
33struct S {
34 TEST_CONSTEXPR_CXX26 S() : i_(0) {}
35 TEST_CONSTEXPR_CXX26 S(int i) : i_(i) {}
36
37 TEST_CONSTEXPR_CXX26 S(const S& rhs) : i_(rhs.i_) {}
38 TEST_CONSTEXPR_CXX26 S(S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
39
40 TEST_CONSTEXPR_CXX26 S& operator=(const S& rhs) {
41 i_ = rhs.i_;
42 return *this;
43 }
44 TEST_CONSTEXPR_CXX26 S& operator=(S&& rhs) {
45 i_ = rhs.i_;
46 rhs.i_ = -2;
47 assert(this != &rhs);
48 return *this;
49 }
50 TEST_CONSTEXPR_CXX26 S& operator=(int i) {
51 i_ = i;
52 return *this;
53 }
54
55 TEST_CONSTEXPR_CXX26 bool operator<(const S& rhs) const { return i_ < rhs.i_; }
56 TEST_CONSTEXPR_CXX26 bool operator>(const S& rhs) const { return i_ > rhs.i_; }
57 TEST_CONSTEXPR_CXX26 bool operator==(const S& rhs) const { return i_ == rhs.i_; }
58 TEST_CONSTEXPR_CXX26 bool operator==(int i) const { return i_ == i; }
59
60 TEST_CONSTEXPR_CXX26 void set(int i) { i_ = i; }
61
62 int i_;
63};
64
65#endif // TEST_STD_VER >= 11
66
67#include "test_iterators.h"
68#include "counting_predicates.h"
69
70template <class Iter, class RandSrc>
71TEST_CONSTEXPR_CXX26 void test_one(unsigned N, unsigned M, RandSrc& randomness) {
72 assert(M <= N);
73 typedef typename std::iterator_traits<Iter>::value_type value_type;
74 value_type* ia = new value_type[N];
75 for (unsigned i = 0; i < N; ++i)
76 ia[i] = i;
77 support::shuffle(ia, ia + N, randomness);
78 std::sort(ia, ia + M, std::greater<value_type>());
79 std::sort(ia + M, ia + N, std::greater<value_type>());
80 binary_counting_predicate<std::greater<value_type>, value_type, value_type> pred((std::greater<value_type>()));
81 std::inplace_merge(Iter(ia), Iter(ia + M), Iter(ia + N), std::ref(t&: pred));
82 if (N > 0) {
83 assert(ia[0] == static_cast<int>(N) - 1);
84 assert(ia[N - 1] == 0);
85 assert(std::is_sorted(ia, ia + N, std::greater<value_type>()));
86#if defined(_LIBCPP_HARDENING_MODE) && _LIBCPP_HARDENING_MODE != _LIBCPP_HARDENING_MODE_DEBUG
87 assert(pred.count() <= (N - 1));
88#endif
89 }
90 delete[] ia;
91}
92
93template <class Iter, class RandSrc>
94TEST_CONSTEXPR_CXX26 void test(unsigned N, RandSrc& randomness) {
95 test_one<Iter>(N, 0, randomness);
96 test_one<Iter>(N, N / 4, randomness);
97 test_one<Iter>(N, N / 2, randomness);
98 test_one<Iter>(N, 3 * N / 4, randomness);
99 test_one<Iter>(N, N, randomness);
100}
101
102template <class Iter, class RandSrc>
103TEST_CONSTEXPR_CXX26 void test(RandSrc& randomness) {
104 test_one<Iter>(0, 0, randomness);
105 test_one<Iter>(1, 0, randomness);
106 test_one<Iter>(1, 1, randomness);
107 test_one<Iter>(2, 0, randomness);
108 test_one<Iter>(2, 1, randomness);
109 test_one<Iter>(2, 2, randomness);
110 test_one<Iter>(3, 0, randomness);
111 test_one<Iter>(3, 1, randomness);
112 test_one<Iter>(3, 2, randomness);
113 test_one<Iter>(3, 3, randomness);
114 test<Iter>(4, randomness);
115 test<Iter>(20, randomness);
116 test<Iter>(50, randomness);
117 if (!TEST_IS_CONSTANT_EVALUATED) { // avoid exceeding the constant evaluation step limit
118 test<Iter>(100, randomness);
119 test<Iter>(1000, randomness);
120 }
121}
122
123struct less_by_first {
124 template <typename Pair>
125 TEST_CONSTEXPR_CXX26 bool operator()(const Pair& lhs, const Pair& rhs) const {
126 return std::less<typename Pair::first_type>()(lhs.first, rhs.first);
127 }
128};
129
130TEST_CONSTEXPR_CXX26 void test_PR31166() {
131 typedef std::pair<int, int> P;
132 typedef std::vector<P> V;
133 P vec[5] = {P(1, 0), P(2, 0), P(2, 1), P(2, 2), P(2, 3)};
134 for (int i = 0; i < 5; ++i) {
135 V res(vec, vec + 5);
136 std::inplace_merge(first: res.begin(), middle: res.begin() + i, last: res.end(), comp: less_by_first());
137 assert(res.size() == 5);
138 assert(std::equal(res.begin(), res.end(), vec));
139 }
140}
141
142TEST_CONSTEXPR_CXX26 bool test() {
143 support::simple_random_generator randomness;
144
145 test<bidirectional_iterator<int*> >(randomness);
146 test<random_access_iterator<int*> >(randomness);
147 test<int*>(randomness);
148
149#if TEST_STD_VER >= 11
150 test<bidirectional_iterator<S*> >(randomness);
151 test<random_access_iterator<S*> >(randomness);
152 test<S*>(randomness);
153
154 {
155 constexpr int N = 100;
156 constexpr int M = 50;
157 std::unique_ptr<int>* ia = new std::unique_ptr<int>[N];
158 for (int i = 0; i < N; ++i)
159 ia[i].reset(new int(i));
160 support::shuffle(ia, ia + N, randomness);
161 std::sort(ia, ia + M, indirect_less());
162 std::sort(ia + M, ia + N, indirect_less());
163 std::inplace_merge(ia, ia + M, ia + N, indirect_less());
164 assert(*ia[0] == 0);
165 assert(*ia[N - 1] == N - 1);
166 assert(std::is_sorted(ia, ia + N, indirect_less()));
167 delete[] ia;
168 }
169#endif // TEST_STD_VER >= 11
170
171 test_PR31166();
172
173 return true;
174}
175
176int main(int, char**) {
177 test();
178#if TEST_STD_VER >= 26
179 static_assert(test());
180#endif // TEST_STD_VER >= 26
181
182 return 0;
183}
184

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