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