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