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

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