1 // -*- C++ -*-
2 //===-- minmax_element.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++03, c++11, c++14
11
12 #include "support/pstl_test_config.h"
13
14 #include <execution>
15 #include <algorithm>
16 #include <set>
17 #include <cmath>
18
19 #include "support/utils.h"
20
21 using namespace TestUtils;
22
23 struct check_minelement
24 {
25 template <typename Policy, typename Iterator>
26 void
operator ()check_minelement27 operator()(Policy&& exec, Iterator begin, Iterator end)
28 {
29 typedef typename std::iterator_traits<Iterator>::value_type T;
30 const Iterator expect = std::min_element(begin, end);
31 const Iterator result = std::min_element(exec, begin, end);
32 const Iterator result_pred = std::min_element(exec, begin, end, std::less<T>());
33 EXPECT_TRUE(expect == result, "wrong return result from min_element");
34 EXPECT_TRUE(expect == result_pred, "wrong return result from min_element");
35 }
36 };
37
38 struct check_maxelement
39 {
40 template <typename Policy, typename Iterator>
41 void
operator ()check_maxelement42 operator()(Policy&& exec, Iterator begin, Iterator end)
43 {
44 typedef typename std::iterator_traits<Iterator>::value_type T;
45 const Iterator expect = std::max_element(begin, end);
46 const Iterator result = std::max_element(exec, begin, end);
47 const Iterator result_pred = std::max_element(exec, begin, end, std::less<T>());
48 EXPECT_TRUE(expect == result, "wrong return result from max_element");
49 EXPECT_TRUE(expect == result_pred, "wrong return result from max_element");
50 }
51 };
52
53 struct check_minmaxelement
54 {
55 template <typename Policy, typename Iterator>
56 void
operator ()check_minmaxelement57 operator()(Policy&& exec, Iterator begin, Iterator end)
58 {
59 typedef typename std::iterator_traits<Iterator>::value_type T;
60 const std::pair<Iterator, Iterator> expect = std::minmax_element(begin, end);
61 const std::pair<Iterator, Iterator> got = std::minmax_element(exec, begin, end);
62 const std::pair<Iterator, Iterator> got_pred = std::minmax_element(exec, begin, end, std::less<T>());
63 EXPECT_TRUE(expect.first == got.first, "wrong return result from minmax_element (min part)");
64 EXPECT_TRUE(expect.second == got.second, "wrong return result from minmax_element (max part)");
65 EXPECT_TRUE(expect == got_pred, "wrong return result from minmax_element");
66 }
67 };
68
69 template <typename T>
70 struct sequence_wrapper
71 {
72 TestUtils::Sequence<T> seq;
73 const T min_value;
74 const T max_value;
75 static const std::size_t bits = 30; // We assume that T can handle signed 2^bits+1 value
76
77 // TestUtils::HashBits returns value between 0 and (1<<bits)-1,
78 // therefore we could threat 1<<bits as maximum and -(1<<bits) as a minimum
sequence_wrappersequence_wrapper79 sequence_wrapper(std::size_t n) : seq(n), min_value(-(1 << bits)), max_value(1 << bits) {}
80
81 void
pattern_fillsequence_wrapper82 pattern_fill()
83 {
84 seq.fill([](std::size_t i) -> T { return T(TestUtils::HashBits(i, bits)); });
85 }
86
87 // sets first one at position `at` and bunch of them farther
88 void
set_desired_valuesequence_wrapper89 set_desired_value(std::size_t at, T value)
90 {
91 if (seq.size() == 0)
92 return;
93 seq[at] = value;
94
95 //Producing serveral red herrings
96 for (std::size_t i = at + 1; i < seq.size(); i += 1 + TestUtils::HashBits(i, 5))
97 seq[i] = value;
98 }
99 };
100
101 template <typename T>
102 void
test_by_type(std::size_t n)103 test_by_type(std::size_t n)
104 {
105 sequence_wrapper<T> wseq(n);
106
107 // to avoid overtesing we use std::set to leave only unique indexes
108 std::set<std::size_t> targets{0};
109 if (n > 1)
110 {
111 targets.insert(1);
112 targets.insert(2.718282 * n / 3);
113 targets.insert(n / 2);
114 targets.insert(n / 7.389056);
115 targets.insert(n - 1); // last
116 }
117
118 for (std::set<std::size_t>::iterator it = targets.begin(); it != targets.end(); ++it)
119 {
120 wseq.pattern_fill();
121 wseq.set_desired_value(*it, wseq.min_value);
122 TestUtils::invoke_on_all_policies(check_minelement(), wseq.seq.cbegin(), wseq.seq.cend());
123 TestUtils::invoke_on_all_policies(check_minelement(), wseq.seq.begin(), wseq.seq.end());
124
125 wseq.set_desired_value(*it, wseq.max_value);
126 TestUtils::invoke_on_all_policies(check_maxelement(), wseq.seq.cbegin(), wseq.seq.cend());
127 TestUtils::invoke_on_all_policies(check_maxelement(), wseq.seq.begin(), wseq.seq.end());
128
129 if (targets.size() > 1)
130 {
131 for (std::set<std::size_t>::reverse_iterator rit = targets.rbegin(); rit != targets.rend(); ++rit)
132 {
133 if (*rit == *it) // we requires at least 2 unique indexes in targets
134 break;
135 wseq.pattern_fill();
136 wseq.set_desired_value(*it, wseq.min_value); // setting minimum element
137 wseq.set_desired_value(*rit, wseq.max_value); // setting maximum element
138 TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.cbegin(), wseq.seq.cend());
139 TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.begin(), wseq.seq.end());
140 }
141 }
142 else
143 { // we must check this corner case; it can not be tested in loop above
144 TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.cbegin(), wseq.seq.cend());
145 TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.begin(), wseq.seq.end());
146 }
147 }
148 }
149
150 // should provide minimal requirements only
151 struct OnlyLessCompare
152 {
153 int32_t val;
OnlyLessCompareOnlyLessCompare154 OnlyLessCompare() : val(0) {}
OnlyLessCompareOnlyLessCompare155 OnlyLessCompare(int32_t val_) : val(val_) {}
156 bool
operator <OnlyLessCompare157 operator<(const OnlyLessCompare& other) const
158 {
159 return val < other.val;
160 }
161 };
162
163 template <typename T>
164 struct test_non_const
165 {
166 template <typename Policy, typename Iterator>
167 void
operator ()test_non_const168 operator()(Policy&& exec, Iterator iter)
169 {
170 max_element(exec, iter, iter, non_const(std::less<T>()));
171 min_element(exec, iter, iter, non_const(std::less<T>()));
172 minmax_element(exec, iter, iter, non_const(std::less<T>()));
173 }
174 };
175
176 int
main()177 main()
178 {
179 using TestUtils::float64_t;
180 const std::size_t N = 100000;
181
182 for (std::size_t n = 0; n < N; n = n < 16 ? n + 1 : size_t(3.14159 * n))
183 {
184 test_by_type<float64_t>(n);
185 test_by_type<OnlyLessCompare>(n);
186 }
187
188 test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
189
190 std::cout << TestUtils::done() << std::endl;
191 return 0;
192 }
193