1 //===----------------------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 // <algorithm>
11
12 // template<BidirectionalIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
13 // requires ShuffleIterator<Iter>
14 // && CopyConstructible<Compare>
15 // void
16 // inplace_merge(Iter first, Iter middle, Iter last, Compare comp);
17
18 #include <algorithm>
19 #include <functional>
20 #include <cassert>
21
22 #include "test_macros.h"
23
24 #if TEST_STD_VER >= 11
25 #include <memory>
26
27 struct indirect_less
28 {
29 template <class P>
operator ()indirect_less30 bool operator()(const P& x, const P& y)
31 {return *x < *y;}
32 };
33
34 struct S {
SS35 S() : i_(0) {}
SS36 S(int i) : i_(i) {}
37
SS38 S(const S& rhs) : i_(rhs.i_) {}
SS39 S( S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
40
operator =S41 S& operator =(const S& rhs) { i_ = rhs.i_; return *this; }
operator =S42 S& operator =( S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; assert(this != &rhs); return *this; }
operator =S43 S& operator =(int i) { i_ = i; return *this; }
44
operator <S45 bool operator <(const S& rhs) const { return i_ < rhs.i_; }
operator >S46 bool operator >(const S& rhs) const { return i_ > rhs.i_; }
operator ==S47 bool operator ==(const S& rhs) const { return i_ == rhs.i_; }
operator ==S48 bool operator ==(int i) const { return i_ == i; }
49
setS50 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.hpp"
60
61 template <class Iter>
62 void
test_one(unsigned N,unsigned M)63 test_one(unsigned N, unsigned M)
64 {
65 assert(M <= N);
66 typedef typename std::iterator_traits<Iter>::value_type value_type;
67 value_type* ia = new value_type[N];
68 for (unsigned i = 0; i < N; ++i)
69 ia[i] = i;
70 std::random_shuffle(ia, ia+N);
71 std::sort(ia, ia+M, std::greater<value_type>());
72 std::sort(ia+M, ia+N, std::greater<value_type>());
73 binary_counting_predicate<std::greater<value_type>, value_type, value_type> pred((std::greater<value_type>()));
74 std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::ref(pred));
75 if(N > 0)
76 {
77 assert(ia[0] == N-1);
78 assert(ia[N-1] == 0);
79 assert(std::is_sorted(ia, ia+N, std::greater<value_type>()));
80 assert(pred.count() <= (N-1));
81 }
82 delete [] ia;
83 }
84
85 template <class Iter>
86 void
test(unsigned N)87 test(unsigned N)
88 {
89 test_one<Iter>(N, 0);
90 test_one<Iter>(N, N/4);
91 test_one<Iter>(N, N/2);
92 test_one<Iter>(N, 3*N/4);
93 test_one<Iter>(N, N);
94 }
95
96 template <class Iter>
97 void
test()98 test()
99 {
100 test_one<Iter>(0, 0);
101 test_one<Iter>(1, 0);
102 test_one<Iter>(1, 1);
103 test_one<Iter>(2, 0);
104 test_one<Iter>(2, 1);
105 test_one<Iter>(2, 2);
106 test_one<Iter>(3, 0);
107 test_one<Iter>(3, 1);
108 test_one<Iter>(3, 2);
109 test_one<Iter>(3, 3);
110 test<Iter>(4);
111 test<Iter>(20);
112 test<Iter>(100);
113 test<Iter>(1000);
114 }
115
main()116 int main()
117 {
118 test<bidirectional_iterator<int*> >();
119 test<random_access_iterator<int*> >();
120 test<int*>();
121
122 #if TEST_STD_VER >= 11
123 test<bidirectional_iterator<S*> >();
124 test<random_access_iterator<S*> >();
125 test<S*>();
126
127 {
128 unsigned N = 100;
129 unsigned M = 50;
130 std::unique_ptr<int>* ia = new std::unique_ptr<int>[N];
131 for (unsigned i = 0; i < N; ++i)
132 ia[i].reset(new int(i));
133 std::random_shuffle(ia, ia+N);
134 std::sort(ia, ia+M, indirect_less());
135 std::sort(ia+M, ia+N, indirect_less());
136 std::inplace_merge(ia, ia+M, ia+N, indirect_less());
137 if(N > 0)
138 {
139 assert(*ia[0] == 0);
140 assert(*ia[N-1] == N-1);
141 assert(std::is_sorted(ia, ia+N, indirect_less()));
142 }
143 delete [] ia;
144 }
145 #endif // TEST_STD_VER >= 11
146 }
147