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

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