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, StrictWeakOrder<auto, Iter::value_type> Compare>
13 // requires ShuffleIterator<Iter>
14 // && CopyConstructible<Compare>
15 // void
16 // nth_element(Iter first, Iter nth, Iter last, Compare comp);
17
18 #include <algorithm>
19 #include <functional>
20 #include <vector>
21 #include <cassert>
22 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
23 #include <memory>
24
25 struct indirect_less
26 {
27 template <class P>
operator ()indirect_less28 bool operator()(const P& x, const P& y)
29 {return *x < *y;}
30 };
31
32 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
33
34 void
test_one(unsigned N,unsigned M)35 test_one(unsigned N, unsigned M)
36 {
37 assert(N != 0);
38 assert(M < N);
39 int* array = new int[N];
40 for (int i = 0; i < N; ++i)
41 array[i] = i;
42 std::random_shuffle(array, array+N);
43 std::nth_element(array, array+M, array+N, std::greater<int>());
44 assert(array[M] == N-M-1);
45 std::nth_element(array, array+N, array+N, std::greater<int>()); // begin, end, end
46 delete [] array;
47 }
48
49 void
test(unsigned N)50 test(unsigned N)
51 {
52 test_one(N, 0);
53 test_one(N, 1);
54 test_one(N, 2);
55 test_one(N, 3);
56 test_one(N, N/2-1);
57 test_one(N, N/2);
58 test_one(N, N/2+1);
59 test_one(N, N-3);
60 test_one(N, N-2);
61 test_one(N, N-1);
62 }
63
main()64 int main()
65 {
66 int d = 0;
67 std::nth_element(&d, &d, &d);
68 assert(d == 0);
69 test(256);
70 test(257);
71 test(499);
72 test(500);
73 test(997);
74 test(1000);
75 test(1009);
76
77 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
78 {
79 std::vector<std::unique_ptr<int> > v(1000);
80 for (int i = 0; i < v.size(); ++i)
81 v[i].reset(new int(i));
82 std::nth_element(v.begin(), v.begin() + v.size()/2, v.end(), indirect_less());
83 assert(*v[v.size()/2] == v.size()/2);
84 }
85 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
86 }
87