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#include "counting_predicates.hpp"
35
36template <class Iter>
37void
38test_one(unsigned N, unsigned M)
39{
40    assert(M <= N);
41    int* ia = new int[N];
42    for (unsigned i = 0; i < N; ++i)
43        ia[i] = i;
44    std::random_shuffle(ia, ia+N);
45    std::sort(ia, ia+M, std::greater<int>());
46    std::sort(ia+M, ia+N, std::greater<int>());
47    binary_counting_predicate<std::greater<int>, int, int> pred((std::greater<int>()));
48    std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::ref(pred));
49    if(N > 0)
50    {
51        assert(ia[0] == N-1);
52        assert(ia[N-1] == 0);
53        assert(std::is_sorted(ia, ia+N, std::greater<int>()));
54        assert(pred.count() <= (N-1));
55    }
56    delete [] ia;
57}
58
59template <class Iter>
60void
61test(unsigned N)
62{
63    test_one<Iter>(N, 0);
64    test_one<Iter>(N, N/4);
65    test_one<Iter>(N, N/2);
66    test_one<Iter>(N, 3*N/4);
67    test_one<Iter>(N, N);
68}
69
70template <class Iter>
71void
72test()
73{
74    test_one<Iter>(0, 0);
75    test_one<Iter>(1, 0);
76    test_one<Iter>(1, 1);
77    test_one<Iter>(2, 0);
78    test_one<Iter>(2, 1);
79    test_one<Iter>(2, 2);
80    test_one<Iter>(3, 0);
81    test_one<Iter>(3, 1);
82    test_one<Iter>(3, 2);
83    test_one<Iter>(3, 3);
84    test<Iter>(4);
85    test<Iter>(20);
86    test<Iter>(100);
87    test<Iter>(1000);
88}
89
90int main()
91{
92    test<bidirectional_iterator<int*> >();
93    test<random_access_iterator<int*> >();
94    test<int*>();
95
96#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
97    {
98    unsigned N = 100;
99    unsigned M = 50;
100    std::unique_ptr<int>* ia = new std::unique_ptr<int>[N];
101    for (unsigned i = 0; i < N; ++i)
102        ia[i].reset(new int(i));
103    std::random_shuffle(ia, ia+N);
104    std::sort(ia, ia+M, indirect_less());
105    std::sort(ia+M, ia+N, indirect_less());
106    std::inplace_merge(ia, ia+M, ia+N, indirect_less());
107    if(N > 0)
108    {
109        assert(*ia[0] == 0);
110        assert(*ia[N-1] == N-1);
111        assert(std::is_sorted(ia, ia+N, indirect_less()));
112    }
113    delete [] ia;
114    }
115#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
116}
117