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<RandomAccessIterator Iter>
13 // requires ShuffleIterator<Iter>
14 // && LessThanComparable<Iter::value_type>
15 // void
16 // nth_element(Iter first, Iter nth, Iter last);
17
18 #include <algorithm>
19 #include <cassert>
20
21 void
test_one(unsigned N,unsigned M)22 test_one(unsigned N, unsigned M)
23 {
24 assert(N != 0);
25 assert(M < N);
26 int* array = new int[N];
27 for (int i = 0; i < N; ++i)
28 array[i] = i;
29 std::random_shuffle(array, array+N);
30 std::nth_element(array, array+M, array+N);
31 assert(array[M] == M);
32 std::nth_element(array, array+N, array+N); // begin, end, end
33 delete [] array;
34 }
35
36 void
test(unsigned N)37 test(unsigned N)
38 {
39 test_one(N, 0);
40 test_one(N, 1);
41 test_one(N, 2);
42 test_one(N, 3);
43 test_one(N, N/2-1);
44 test_one(N, N/2);
45 test_one(N, N/2+1);
46 test_one(N, N-3);
47 test_one(N, N-2);
48 test_one(N, N-1);
49 }
50
main()51 int main()
52 {
53 int d = 0;
54 std::nth_element(&d, &d, &d);
55 assert(d == 0);
56 test(256);
57 test(257);
58 test(499);
59 test(500);
60 test(997);
61 test(1000);
62 test(1009);
63 }
64