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 | // Test std::partial_sort stability randomization |
12 | |
13 | // UNSUPPORTED: c++03 |
14 | // ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY |
15 | |
16 | #include <algorithm> |
17 | #include <array> |
18 | #include <cassert> |
19 | #include <functional> |
20 | #include <iterator> |
21 | #include <vector> |
22 | |
23 | #include "test_macros.h" |
24 | |
25 | struct MyType { |
26 | int value = 0; |
27 | constexpr bool operator<(const MyType& other) const { return value < other.value; } |
28 | }; |
29 | |
30 | std::vector<MyType> deterministic() { |
31 | static constexpr int kSize = 100; |
32 | std::vector<MyType> v; |
33 | v.resize(new_size: kSize); |
34 | for (int i = 0; i < kSize; ++i) { |
35 | v[i].value = (i % 2 ? 1 : kSize / 2 + i); |
36 | } |
37 | auto comp = std::less<MyType>(); |
38 | std::__partial_sort_impl<std::_ClassicAlgPolicy>(v.begin(), v.begin() + kSize / 2, v.end(), comp); |
39 | return v; |
40 | } |
41 | |
42 | void test_randomization() { |
43 | static constexpr int kSize = 100; |
44 | std::vector<MyType> v; |
45 | v.resize(new_size: kSize); |
46 | for (int i = 0; i < kSize; ++i) { |
47 | v[i].value = (i % 2 ? 1 : kSize / 2 + i); |
48 | } |
49 | auto deterministic_v = deterministic(); |
50 | std::partial_sort(first: v.begin(), middle: v.begin() + kSize / 2, last: v.end()); |
51 | bool all_equal = true; |
52 | for (int i = 0; i < kSize; ++i) { |
53 | if (v[i].value != deterministic_v[i].value) { |
54 | all_equal = false; |
55 | } |
56 | } |
57 | assert(!all_equal); |
58 | } |
59 | |
60 | void test_same() { |
61 | static constexpr int kSize = 100; |
62 | std::vector<MyType> v; |
63 | v.resize(new_size: kSize); |
64 | for (int i = 0; i < kSize; ++i) { |
65 | v[i].value = (i % 2 ? 1 : kSize / 2 + i); |
66 | } |
67 | auto snapshot_v = v; |
68 | auto snapshot_custom_v = v; |
69 | std::partial_sort(first: v.begin(), middle: v.begin() + kSize / 2, last: v.end()); |
70 | std::partial_sort(first: snapshot_v.begin(), middle: snapshot_v.begin() + kSize / 2, last: snapshot_v.end()); |
71 | std::partial_sort(first: snapshot_custom_v.begin(), middle: snapshot_custom_v.begin() + kSize / 2, last: snapshot_custom_v.end(), comp: std::less<MyType>()); |
72 | bool all_equal = true; |
73 | for (int i = 0; i < kSize; ++i) { |
74 | if (v[i].value != snapshot_v[i].value || v[i].value != snapshot_custom_v[i].value) { |
75 | all_equal = false; |
76 | } |
77 | if (i < kSize / 2) { |
78 | assert(v[i].value == 1); |
79 | } |
80 | } |
81 | assert(all_equal); |
82 | } |
83 | |
84 | #if TEST_STD_VER > 17 |
85 | constexpr bool test_constexpr() { |
86 | std::array<MyType, 10> v; |
87 | for (int i = 9; i >= 0; --i) { |
88 | v[9 - i].value = i; |
89 | } |
90 | std::partial_sort(v.begin(), v.begin() + 5, v.end()); |
91 | return std::is_sorted(v.begin(), v.begin() + 5); |
92 | } |
93 | #endif |
94 | |
95 | int main(int, char**) { |
96 | test_randomization(); |
97 | test_same(); |
98 | #if TEST_STD_VER > 17 |
99 | static_assert(test_constexpr(), "" ); |
100 | #endif |
101 | return 0; |
102 | } |
103 | |