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