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 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
22 #include <memory>
23
24 struct indirect_less
25 {
26 template <class P>
operator ()indirect_less27 bool operator()(const P& x, const P& y)
28 {return *x < *y;}
29 };
30
31 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
32
33 #include "test_iterators.h"
34
35 template <class Iter>
36 void
test_one(unsigned N,unsigned M)37 test_one(unsigned N, unsigned M)
38 {
39 assert(M <= N);
40 int* ia = new int[N];
41 for (unsigned i = 0; i < N; ++i)
42 ia[i] = i;
43 std::random_shuffle(ia, ia+N);
44 std::sort(ia, ia+M, std::greater<int>());
45 std::sort(ia+M, ia+N, std::greater<int>());
46 std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::greater<int>());
47 if(N > 0)
48 {
49 assert(ia[0] == N-1);
50 assert(ia[N-1] == 0);
51 assert(std::is_sorted(ia, ia+N, std::greater<int>()));
52 }
53 delete [] ia;
54 }
55
56 template <class Iter>
57 void
test(unsigned N)58 test(unsigned N)
59 {
60 test_one<Iter>(N, 0);
61 test_one<Iter>(N, N/4);
62 test_one<Iter>(N, N/2);
63 test_one<Iter>(N, 3*N/4);
64 test_one<Iter>(N, N);
65 }
66
67 template <class Iter>
68 void
test()69 test()
70 {
71 test_one<Iter>(0, 0);
72 test_one<Iter>(1, 0);
73 test_one<Iter>(1, 1);
74 test_one<Iter>(2, 0);
75 test_one<Iter>(2, 1);
76 test_one<Iter>(2, 2);
77 test_one<Iter>(3, 0);
78 test_one<Iter>(3, 1);
79 test_one<Iter>(3, 2);
80 test_one<Iter>(3, 3);
81 test<Iter>(4);
82 test<Iter>(100);
83 test<Iter>(1000);
84 }
85
main()86 int main()
87 {
88 test<bidirectional_iterator<int*> >();
89 test<random_access_iterator<int*> >();
90 test<int*>();
91
92 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
93 {
94 unsigned N = 100;
95 unsigned M = 50;
96 std::unique_ptr<int>* ia = new std::unique_ptr<int>[N];
97 for (unsigned i = 0; i < N; ++i)
98 ia[i].reset(new int(i));
99 std::random_shuffle(ia, ia+N);
100 std::sort(ia, ia+M, indirect_less());
101 std::sort(ia+M, ia+N, indirect_less());
102 std::inplace_merge(ia, ia+M, ia+N, indirect_less());
103 if(N > 0)
104 {
105 assert(*ia[0] == 0);
106 assert(*ia[N-1] == N-1);
107 assert(std::is_sorted(ia, ia+N, indirect_less()));
108 }
109 delete [] ia;
110 }
111 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
112 }
113