| // -*- C++ -*- |
| //===-- minmax_element.pass.cpp -------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // UNSUPPORTED: c++03, c++11, c++14 |
| |
| #include "support/pstl_test_config.h" |
| |
| #include <execution> |
| #include <algorithm> |
| #include <set> |
| #include <cmath> |
| |
| #include "support/utils.h" |
| |
| using namespace TestUtils; |
| |
| struct check_minelement |
| { |
| template <typename Policy, typename Iterator> |
| void |
| operator()(Policy&& exec, Iterator begin, Iterator end) |
| { |
| typedef typename std::iterator_traits<Iterator>::value_type T; |
| const Iterator expect = std::min_element(begin, end); |
| const Iterator result = std::min_element(exec, begin, end); |
| const Iterator result_pred = std::min_element(exec, begin, end, std::less<T>()); |
| EXPECT_TRUE(expect == result, "wrong return result from min_element"); |
| EXPECT_TRUE(expect == result_pred, "wrong return result from min_element"); |
| } |
| }; |
| |
| struct check_maxelement |
| { |
| template <typename Policy, typename Iterator> |
| void |
| operator()(Policy&& exec, Iterator begin, Iterator end) |
| { |
| typedef typename std::iterator_traits<Iterator>::value_type T; |
| const Iterator expect = std::max_element(begin, end); |
| const Iterator result = std::max_element(exec, begin, end); |
| const Iterator result_pred = std::max_element(exec, begin, end, std::less<T>()); |
| EXPECT_TRUE(expect == result, "wrong return result from max_element"); |
| EXPECT_TRUE(expect == result_pred, "wrong return result from max_element"); |
| } |
| }; |
| |
| struct check_minmaxelement |
| { |
| template <typename Policy, typename Iterator> |
| void |
| operator()(Policy&& exec, Iterator begin, Iterator end) |
| { |
| typedef typename std::iterator_traits<Iterator>::value_type T; |
| const std::pair<Iterator, Iterator> expect = std::minmax_element(begin, end); |
| const std::pair<Iterator, Iterator> got = std::minmax_element(exec, begin, end); |
| const std::pair<Iterator, Iterator> got_pred = std::minmax_element(exec, begin, end, std::less<T>()); |
| EXPECT_TRUE(expect.first == got.first, "wrong return result from minmax_element (min part)"); |
| EXPECT_TRUE(expect.second == got.second, "wrong return result from minmax_element (max part)"); |
| EXPECT_TRUE(expect == got_pred, "wrong return result from minmax_element"); |
| } |
| }; |
| |
| template <typename T> |
| struct sequence_wrapper |
| { |
| TestUtils::Sequence<T> seq; |
| const T min_value; |
| const T max_value; |
| static const std::size_t bits = 30; // We assume that T can handle signed 2^bits+1 value |
| |
| // TestUtils::HashBits returns value between 0 and (1<<bits)-1, |
| // therefore we could threat 1<<bits as maximum and -(1<<bits) as a minimum |
| sequence_wrapper(std::size_t n) : seq(n), min_value(-(1 << bits)), max_value(1 << bits) {} |
| |
| void |
| pattern_fill() |
| { |
| seq.fill([](std::size_t i) -> T { return T(TestUtils::HashBits(i, bits)); }); |
| } |
| |
| // sets first one at position `at` and bunch of them farther |
| void |
| set_desired_value(std::size_t at, T value) |
| { |
| if (seq.size() == 0) |
| return; |
| seq[at] = value; |
| |
| //Producing serveral red herrings |
| for (std::size_t i = at + 1; i < seq.size(); i += 1 + TestUtils::HashBits(i, 5)) |
| seq[i] = value; |
| } |
| }; |
| |
| template <typename T> |
| void |
| test_by_type(std::size_t n) |
| { |
| sequence_wrapper<T> wseq(n); |
| |
| // to avoid overtesing we use std::set to leave only unique indexes |
| std::set<std::size_t> targets{0}; |
| if (n > 1) |
| { |
| targets.insert(1); |
| targets.insert(2.718282 * n / 3); |
| targets.insert(n / 2); |
| targets.insert(n / 7.389056); |
| targets.insert(n - 1); // last |
| } |
| |
| for (std::set<std::size_t>::iterator it = targets.begin(); it != targets.end(); ++it) |
| { |
| wseq.pattern_fill(); |
| wseq.set_desired_value(*it, wseq.min_value); |
| TestUtils::invoke_on_all_policies(check_minelement(), wseq.seq.cbegin(), wseq.seq.cend()); |
| TestUtils::invoke_on_all_policies(check_minelement(), wseq.seq.begin(), wseq.seq.end()); |
| |
| wseq.set_desired_value(*it, wseq.max_value); |
| TestUtils::invoke_on_all_policies(check_maxelement(), wseq.seq.cbegin(), wseq.seq.cend()); |
| TestUtils::invoke_on_all_policies(check_maxelement(), wseq.seq.begin(), wseq.seq.end()); |
| |
| if (targets.size() > 1) |
| { |
| for (std::set<std::size_t>::reverse_iterator rit = targets.rbegin(); rit != targets.rend(); ++rit) |
| { |
| if (*rit == *it) // we requires at least 2 unique indexes in targets |
| break; |
| wseq.pattern_fill(); |
| wseq.set_desired_value(*it, wseq.min_value); // setting minimum element |
| wseq.set_desired_value(*rit, wseq.max_value); // setting maximum element |
| TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.cbegin(), wseq.seq.cend()); |
| TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.begin(), wseq.seq.end()); |
| } |
| } |
| else |
| { // we must check this corner case; it can not be tested in loop above |
| TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.cbegin(), wseq.seq.cend()); |
| TestUtils::invoke_on_all_policies(check_minmaxelement(), wseq.seq.begin(), wseq.seq.end()); |
| } |
| } |
| } |
| |
| // should provide minimal requirements only |
| struct OnlyLessCompare |
| { |
| int32_t val; |
| OnlyLessCompare() : val(0) {} |
| OnlyLessCompare(int32_t val_) : val(val_) {} |
| bool |
| operator<(const OnlyLessCompare& other) const |
| { |
| return val < other.val; |
| } |
| }; |
| |
| template <typename T> |
| struct test_non_const |
| { |
| template <typename Policy, typename Iterator> |
| void |
| operator()(Policy&& exec, Iterator iter) |
| { |
| max_element(exec, iter, iter, non_const(std::less<T>())); |
| min_element(exec, iter, iter, non_const(std::less<T>())); |
| minmax_element(exec, iter, iter, non_const(std::less<T>())); |
| } |
| }; |
| |
| int |
| main() |
| { |
| using TestUtils::float64_t; |
| const std::size_t N = 100000; |
| |
| for (std::size_t n = 0; n < N; n = n < 16 ? n + 1 : size_t(3.14159 * n)) |
| { |
| test_by_type<float64_t>(n); |
| test_by_type<OnlyLessCompare>(n); |
| } |
| |
| test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>()); |
| |
| std::cout << TestUtils::done() << std::endl; |
| return 0; |
| } |