1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 // <algorithm>
10
11 // template<InputIterator InIter, RandomAccessIterator RAIter>
12 // requires ShuffleIterator<RAIter>
13 // && OutputIterator<RAIter, InIter::reference>
14 // && HasLess<InIter::value_type, RAIter::value_type>
15 // && LessThanComparable<RAIter::value_type>
16 // RAIter
17 // partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last);
18
19 #include <algorithm>
20 #include <random>
21 #include <cassert>
22
23 #include "test_macros.h"
24 #include "test_iterators.h"
25
26 std::mt19937 randomness;
27
28 template <class Iter>
29 void
test_larger_sorts(int N,int M)30 test_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
47 template <class Iter>
48 void
test_larger_sorts(int N)49 test_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
64 template <class Iter>
65 void
test()66 test()
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
main(int,char **)79 int main(int, char**)
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 return 0;
91 }
92