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
21using namespace TestUtils;
22
23struct check_minelement
24{
25 template <typename Policy, typename Iterator>
26 void
27 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
38struct check_maxelement
39{
40 template <typename Policy, typename Iterator>
41 void
42 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
53struct check_minmaxelement
54{
55 template <typename Policy, typename Iterator>
56 void
57 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
69template <typename T>
70struct 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
79 sequence_wrapper(std::size_t n) : seq(n), min_value(-(1 << bits)), max_value(1 << bits) {}
80
81 void
82 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
89 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, bits: 5))
97 seq[i] = value;
98 }
99};
100
101template <typename T>
102void
103test_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(x: 1);
112 targets.insert(x: 2.718282 * n / 3);
113 targets.insert(x: n / 2);
114 targets.insert(x: n / 7.389056);
115 targets.insert(x: 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
151struct OnlyLessCompare
152{
153 int32_t val;
154 OnlyLessCompare() : val(0) {}
155 OnlyLessCompare(int32_t val_) : val(val_) {}
156 bool
157 operator<(const OnlyLessCompare& other) const
158 {
159 return val < other.val;
160 }
161};
162
163template <typename T>
164struct test_non_const
165{
166 template <typename Policy, typename Iterator>
167 void
168 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
176int
177main()
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>(f: run_for_rnd_fw<test_non_const<int32_t>>());
189
190 std::cout << TestUtils::done() << std::endl;
191 return 0;
192}
193

source code of pstl/test/std/algorithms/alg.sorting/alg.min.max/minmax_element.pass.cpp