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
28 template <class Iter>
29 void
test_larger_sorts(unsigned N,unsigned M)30 test_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
48 template <class Iter>
49 void
test_larger_sorts(unsigned N)50 test_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
65 template <class Iter>
66 void
test()67 test()
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
main()80 int 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