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<RandomAccessIterator Iter>
12 // requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
13 // constexpr void // constexpr in C++20
14 // nth_element(Iter first, Iter nth, Iter last);
15
16 #include <algorithm>
17 #include <cassert>
18
19 #include "test_macros.h"
20 #include "test_iterators.h"
21 #include "MoveOnly.h"
22
23 template<class T, class Iter>
test()24 TEST_CONSTEXPR_CXX20 bool test()
25 {
26 int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
27 T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
28 for (int n = 0; n < 15; ++n) {
29 for (int m = 0; m < n; ++m) {
30 std::nth_element(Iter(work), Iter(work+m), Iter(work+n));
31 assert(std::is_permutation(work, work+n, orig));
32 // No element to m's left is greater than m.
33 for (int i = 0; i < m; ++i) {
34 assert(!(work[i] > work[m]));
35 }
36 // No element to m's right is less than m.
37 for (int i = m; i < n; ++i) {
38 assert(!(work[i] < work[m]));
39 }
40 std::copy(orig, orig+15, work);
41 }
42 }
43
44 {
45 T input[] = {3,1,4,1,5,9,2};
46 std::nth_element(Iter(input), Iter(input+4), Iter(input+7));
47 assert(input[4] == 4);
48 assert(input[5] + input[6] == 5 + 9);
49 }
50
51 {
52 T input[] = {0, 1, 2, 3, 4, 5, 7, 6};
53 std::nth_element(Iter(input), Iter(input + 6), Iter(input + 8));
54 assert(input[6] == 6);
55 assert(input[7] == 7);
56 }
57
58 {
59 T input[] = {1, 0, 2, 3, 4, 5, 6, 7};
60 std::nth_element(Iter(input), Iter(input + 1), Iter(input + 8));
61 assert(input[0] == 0);
62 assert(input[1] == 1);
63 }
64
65 return true;
66 }
67
main(int,char **)68 int main(int, char**)
69 {
70 test<int, random_access_iterator<int*> >();
71 test<int, int*>();
72
73 #if TEST_STD_VER >= 11
74 test<MoveOnly, random_access_iterator<MoveOnly*>>();
75 test<MoveOnly, MoveOnly*>();
76 #endif
77
78 #if TEST_STD_VER >= 20
79 static_assert(test<int, random_access_iterator<int*>>());
80 static_assert(test<int, int*>());
81 static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
82 static_assert(test<MoveOnly, MoveOnly*>());
83 #endif
84
85 return 0;
86 }
87