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
24struct indirect_less
25{
26    template <class P>
27    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
35template <class Iter>
36void
37test_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
56template <class Iter>
57void
58test(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
67template <class Iter>
68void
69test()
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
86int 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