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