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>
12// constexpr void // constexpr since C++26
13// inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
14
15#include <algorithm>
16#include <cassert>
17#include <vector>
18
19#include "count_new.h"
20#include "constexpr_random.h"
21#include "test_iterators.h"
22#include "test_macros.h"
23
24#if TEST_STD_VER >= 11
25struct S {
26 TEST_CONSTEXPR_CXX26 S() : i_(0) {}
27 TEST_CONSTEXPR_CXX26 S(int i) : i_(i) {}
28
29 TEST_CONSTEXPR_CXX26 S(const S& rhs) : i_(rhs.i_) {}
30 TEST_CONSTEXPR_CXX26 S(S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
31
32 TEST_CONSTEXPR_CXX26 S& operator=(const S& rhs) {
33 i_ = rhs.i_;
34 return *this;
35 }
36 TEST_CONSTEXPR_CXX26 S& operator=(S&& rhs) {
37 i_ = rhs.i_;
38 rhs.i_ = -2;
39 assert(this != &rhs);
40 return *this;
41 }
42 TEST_CONSTEXPR_CXX26 S& operator=(int i) {
43 i_ = i;
44 return *this;
45 }
46
47 TEST_CONSTEXPR_CXX26 bool operator<(const S& rhs) const { return i_ < rhs.i_; }
48 TEST_CONSTEXPR_CXX26 bool operator==(const S& rhs) const { return i_ == rhs.i_; }
49 TEST_CONSTEXPR_CXX26 bool operator==(int i) const { return i_ == i; }
50
51 TEST_CONSTEXPR_CXX26 void set(int i) { i_ = i; }
52
53 int i_;
54};
55#endif
56
57template <class Iter, class RandSrc>
58TEST_CONSTEXPR_CXX26 void test_one(unsigned N, unsigned M, RandSrc& randomness) {
59 assert(M <= N);
60
61 typedef typename std::iterator_traits<Iter>::value_type value_type;
62 value_type* ia = new value_type[N];
63 for (unsigned i = 0; i < N; ++i)
64 ia[i] = i;
65 support::shuffle(ia, ia + N, randomness);
66 std::sort(ia, ia + M);
67 std::sort(ia + M, ia + N);
68 std::inplace_merge(Iter(ia), Iter(ia + M), Iter(ia + N));
69 if (N > 0) {
70 assert(ia[0] == 0);
71 assert(ia[N - 1] == static_cast<value_type>(N - 1));
72 assert(std::is_sorted(ia, ia + N));
73 }
74 delete[] ia;
75}
76
77template <class Iter, class RandSrc>
78TEST_CONSTEXPR_CXX26 void test(unsigned N, RandSrc& randomness) {
79 test_one<Iter>(N, 0, randomness);
80 test_one<Iter>(N, N / 4, randomness);
81 test_one<Iter>(N, N / 2, randomness);
82 test_one<Iter>(N, 3 * N / 4, randomness);
83 test_one<Iter>(N, N, randomness);
84}
85
86template <class Iter, class RandSrc>
87TEST_CONSTEXPR_CXX26 void test(RandSrc& randomness) {
88 test_one<Iter>(0, 0, randomness);
89 test_one<Iter>(1, 0, randomness);
90 test_one<Iter>(1, 1, randomness);
91 test_one<Iter>(2, 0, randomness);
92 test_one<Iter>(2, 1, randomness);
93 test_one<Iter>(2, 2, randomness);
94 test_one<Iter>(3, 0, randomness);
95 test_one<Iter>(3, 1, randomness);
96 test_one<Iter>(3, 2, randomness);
97 test_one<Iter>(3, 3, randomness);
98 test<Iter>(4, randomness);
99 test<Iter>(50, randomness);
100 if (!TEST_IS_CONSTANT_EVALUATED) { // avoid exceeding the constant evaluation step limit
101 test<Iter>(100, randomness);
102 test<Iter>(1000, randomness);
103 }
104}
105
106TEST_CONSTEXPR_CXX26 bool test() {
107 support::simple_random_generator randomness;
108
109 test<bidirectional_iterator<int*> >(randomness);
110 test<random_access_iterator<int*> >(randomness);
111 test<int*>(randomness);
112
113#if TEST_STD_VER >= 11
114 test<bidirectional_iterator<S*> >(randomness);
115 test<random_access_iterator<S*> >(randomness);
116 test<S*>(randomness);
117#endif
118
119 return true;
120}
121
122int main(int, char**) {
123 test();
124#if TEST_STD_VER >= 26
125 static_assert(test());
126#endif // TEST_STD_VER >= 26
127
128#if TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)
129 if (!TEST_IS_CONSTANT_EVALUATED) {
130 std::vector<int> vec(150, 3);
131 getGlobalMemCounter()->throw_after = 0;
132 std::inplace_merge(vec.begin(), vec.begin() + 100, vec.end());
133 assert(std::all_of(vec.begin(), vec.end(), [](int i) { return i == 3; }));
134 }
135#endif // TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)
136
137 return 0;
138}
139

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