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