1 // -*- C++ -*-
2 //===-- partial_sort_copy.pass.cpp ----------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 // UNSUPPORTED: c++98, c++03, c++11, c++14
11
12 // Tests for partial_sort_copy
13 #include "support/pstl_test_config.h"
14
15 #include <cmath>
16 #include <execution>
17 #include <algorithm>
18
19 #include "support/utils.h"
20
21 using namespace TestUtils;
22
23 template <typename T>
24 struct Num
25 {
26 T val;
27
NumNum28 Num() : val(0) {}
NumNum29 Num(T v) : val(v) {}
NumNum30 Num(const Num<T>& v) : val(v.val) {}
NumNum31 Num(Num<T>&& v) : val(v.val) {}
32 Num<T>&
operator =Num33 operator=(const Num<T>& v)
34 {
35 val = v.val;
36 return *this;
37 }
operator TNum38 operator T() const { return val; }
39 bool
operator <Num40 operator<(const Num<T>& v) const
41 {
42 return val < v.val;
43 }
44 };
45
46 template <typename RandomAccessIterator>
47 struct test_one_policy
48 {
49 RandomAccessIterator d_first;
50 RandomAccessIterator d_last;
51 RandomAccessIterator exp_first;
52 RandomAccessIterator exp_last;
53 // This ctor is needed because output shouldn't be transformed to any iterator type (only random access iterators are allowed)
test_one_policytest_one_policy54 test_one_policy(RandomAccessIterator b1, RandomAccessIterator e1, RandomAccessIterator b2, RandomAccessIterator e2)
55 : d_first(b1), d_last(e1), exp_first(b2), exp_last(e2)
56 {
57 }
58 #if _PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \
59 _PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN // dummy specialization by policy type, in case of broken configuration
60 template <typename InputIterator, typename Size, typename T, typename Compare>
61 void
operator ()test_one_policy62 operator()(pstl::execution::unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
63 const T& trash, Compare compare)
64 {
65 }
66
67 template <typename InputIterator, typename Size, typename T, typename Compare>
68 void
operator ()test_one_policy69 operator()(pstl::execution::parallel_unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
70 const T& trash, Compare compare)
71 {
72 }
73
74 template <typename InputIterator, typename Size, typename T>
75 void
operator ()test_one_policy76 operator()(pstl::execution::unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
77 const T& trash)
78 {
79 }
80
81 template <typename InputIterator, typename Size, typename T>
82 void
operator ()test_one_policy83 operator()(pstl::execution::parallel_unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
84 const T& trash)
85 {
86 }
87 #endif
88
89 template <typename Policy, typename InputIterator, typename Size, typename T, typename Compare>
90 void
operator ()test_one_policy91 operator()(Policy&& exec, InputIterator first, InputIterator last, Size n1, Size n2, const T& trash,
92 Compare compare)
93 {
94 prepare_data(first, last, n1, trash);
95 RandomAccessIterator exp = std::partial_sort_copy(first, last, exp_first, exp_last, compare);
96 RandomAccessIterator res = std::partial_sort_copy(exec, first, last, d_first, d_last, compare);
97
98 EXPECT_TRUE((exp - exp_first) == (res - d_first), "wrong result from partial_sort_copy with predicate");
99 EXPECT_EQ_N(exp_first, d_first, n2, "wrong effect from partial_sort_copy with predicate");
100 }
101
102 template <typename Policy, typename InputIterator, typename Size, typename T>
103 void
operator ()test_one_policy104 operator()(Policy&& exec, InputIterator first, InputIterator last, Size n1, Size n2, const T& trash)
105 {
106 prepare_data(first, last, n1, trash);
107 RandomAccessIterator exp = std::partial_sort_copy(first, last, exp_first, exp_last);
108 RandomAccessIterator res = std::partial_sort_copy(exec, first, last, d_first, d_last);
109
110 EXPECT_TRUE((exp - exp_first) == (res - d_first), "wrong result from partial_sort_copy without predicate");
111 EXPECT_EQ_N(exp_first, d_first, n2, "wrong effect from partial_sort_copy without predicate");
112 }
113
114 private:
115 template <typename InputIterator, typename Size, typename T>
116 void
prepare_datatest_one_policy117 prepare_data(InputIterator first, InputIterator last, Size n1, const T& trash)
118 {
119 // The rand()%(2*n+1) encourages generation of some duplicates.
120 std::srand(42);
121 std::generate(first, last, [n1]() { return T(rand() % (2 * n1 + 1)); });
122
123 std::fill(exp_first, exp_last, trash);
124 std::fill(d_first, d_last, trash);
125 }
126 };
127
128 template <typename T, typename Compare>
129 void
test_partial_sort_copy(Compare compare)130 test_partial_sort_copy(Compare compare)
131 {
132
133 typedef typename Sequence<T>::iterator iterator_type;
134 const std::size_t n_max = 100000;
135 Sequence<T> in(n_max);
136 Sequence<T> out(2 * n_max);
137 Sequence<T> exp(2 * n_max);
138 std::size_t n1 = 0;
139 std::size_t n2;
140 T trash = T(-666);
141 for (; n1 < n_max; n1 = n1 <= 16 ? n1 + 1 : size_t(3.1415 * n1))
142 {
143 // If both sequences are equal
144 n2 = n1;
145 invoke_on_all_policies(
146 test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
147 in.begin() + n1, n1, n2, trash, compare);
148
149 // If first sequence is greater than second
150 n2 = n1 / 3;
151 invoke_on_all_policies(
152 test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
153 in.begin() + n1, n1, n2, trash, compare);
154
155 // If first sequence is less than second
156 n2 = 2 * n1;
157 invoke_on_all_policies(
158 test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
159 in.begin() + n1, n1, n2, trash, compare);
160 }
161 // Test partial_sort_copy without predicate
162 n1 = n_max;
163 n2 = 2 * n1;
164 invoke_on_all_policies(test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2),
165 in.begin(), in.begin() + n1, n1, n2, trash);
166 }
167
168 template <typename T>
169 struct test_non_const
170 {
171 template <typename Policy, typename InputIterator, typename OutputInterator>
172 void
operator ()test_non_const173 operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
174 {
175 invoke_if(exec, [&]() {
176 partial_sort_copy(exec, input_iter, input_iter, out_iter, out_iter, non_const(std::less<T>()));
177 });
178 }
179 };
180
181 int
main()182 main()
183 {
184 test_partial_sort_copy<Num<float32_t>>([](Num<float32_t> x, Num<float32_t> y) { return x < y; });
185 test_partial_sort_copy<int32_t>([](int32_t x, int32_t y) { return x > y; });
186
187 test_algo_basic_double<int32_t>(run_for_rnd<test_non_const<int32_t>>());
188
189 test_partial_sort_copy<MemoryChecker>(
190 [](const MemoryChecker& val1, const MemoryChecker& val2){ return val1.value() < val2.value(); });
191 EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from partial_sort_copy: number of ctors calls < num of dtors calls");
192 EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from partial_sort_copy: number of ctors calls > num of dtors calls");
193
194 std::cout << done() << std::endl;
195 return 0;
196 }
197