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<InputIterator InIter, RandomAccessIterator RAIter, class Compare>
13//   requires ShuffleIterator<RAIter>
14//         && OutputIterator<RAIter, InIter::reference>
15//         && Predicate<Compare, InIter::value_type, RAIter::value_type>
16//         && StrictWeakOrder<Compare, RAIter::value_type>}
17//         && CopyConstructible<Compare>
18//   RAIter
19//   partial_sort_copy(InIter first, InIter last,
20//                     RAIter result_first, RAIter result_last, Compare comp);
21
22#include <algorithm>
23#include <functional>
24#include <random>
25#include <cassert>
26
27#include "test_iterators.h"
28
29std::mt19937 randomness;
30
31template <class Iter>
32void
33test_larger_sorts(int N, int M)
34{
35    int* input = new int[N];
36    int* output = new int[M];
37    for (int i = 0; i < N; ++i)
38        input[i] = i;
39    std::shuffle(input, input+N, randomness);
40    int* r = std::partial_sort_copy(Iter(input), Iter(input+N), output, output+M,
41                                    std::greater<int>());
42    int* e = output + std::min(N, M);
43    assert(r == e);
44    int i = 0;
45    for (int* x = output; x < e; ++x, ++i)
46        assert(*x == N-i-1);
47    delete [] output;
48    delete [] input;
49}
50
51template <class Iter>
52void
53test_larger_sorts(int N)
54{
55    test_larger_sorts<Iter>(N, 0);
56    test_larger_sorts<Iter>(N, 1);
57    test_larger_sorts<Iter>(N, 2);
58    test_larger_sorts<Iter>(N, 3);
59    test_larger_sorts<Iter>(N, N/2-1);
60    test_larger_sorts<Iter>(N, N/2);
61    test_larger_sorts<Iter>(N, N/2+1);
62    test_larger_sorts<Iter>(N, N-2);
63    test_larger_sorts<Iter>(N, N-1);
64    test_larger_sorts<Iter>(N, N);
65    test_larger_sorts<Iter>(N, N+1000);
66}
67
68template <class Iter>
69void
70test()
71{
72    test_larger_sorts<Iter>(0, 100);
73    test_larger_sorts<Iter>(10);
74    test_larger_sorts<Iter>(256);
75    test_larger_sorts<Iter>(257);
76    test_larger_sorts<Iter>(499);
77    test_larger_sorts<Iter>(500);
78    test_larger_sorts<Iter>(997);
79    test_larger_sorts<Iter>(1000);
80    test_larger_sorts<Iter>(1009);
81}
82
83int main()
84{
85    int i = 0;
86    std::partial_sort_copy(&i, &i, &i, &i+5);
87    assert(i == 0);
88    test<input_iterator<const int*> >();
89    test<forward_iterator<const int*> >();
90    test<bidirectional_iterator<const int*> >();
91    test<random_access_iterator<const int*> >();
92    test<const int*>();
93}
94