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
25 template <class Iter>
26 void
test_larger_sorts(unsigned N,unsigned M)27 test_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
44 template <class Iter>
45 void
test_larger_sorts(unsigned N)46 test_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
61 template <class Iter>
62 void
test()63 test()
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
main()76 int 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