1// -*- C++ -*-
2//===-- partial_sort.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 <cmath>
15#include <execution>
16#include <algorithm>
17
18#include "support/utils.h"
19
20using namespace TestUtils;
21
22static std::atomic<int32_t> count_val;
23static std::atomic<int32_t> count_comp;
24
25template <typename T>
26struct Num
27{
28 T val;
29
30 Num() { ++count_val; }
31 Num(T v) : val(v) { ++count_val; }
32 Num(const Num<T>& v) : val(v.val) { ++count_val; }
33 Num(Num<T>&& v) : val(v.val) { ++count_val; }
34 ~Num() { --count_val; }
35 Num<T>&
36 operator=(const Num<T>& v)
37 {
38 val = v.val;
39 return *this;
40 }
41 operator T() const { return val; }
42 bool
43 operator<(const Num<T>& v) const
44 {
45 ++count_comp;
46 return val < v.val;
47 }
48};
49
50struct test_brick_partial_sort
51{
52 template <typename Policy, typename InputIterator, typename Compare>
53 typename std::enable_if<is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
54 void>::type
55 operator()(Policy&& exec, InputIterator first, InputIterator last, InputIterator exp_first, InputIterator exp_last,
56 Compare compare)
57 {
58
59 typedef typename std::iterator_traits<InputIterator>::value_type T;
60
61 // The rand()%(2*n+1) encourages generation of some duplicates.
62 std::srand(seed: 42);
63 const std::size_t n = last - first;
64 for (std::size_t k = 0; k < n; ++k)
65 {
66 first[k] = T(rand() % (2 * n + 1));
67 }
68 std::copy(first, last, exp_first);
69
70 for (std::size_t p = 0; p < n; p = p <= 16 ? p + 1 : std::size_t(31.415 * p))
71 {
72 auto m1 = first + p;
73 auto m2 = exp_first + p;
74
75 std::partial_sort(exp_first, m2, exp_last, compare);
76 count_comp = 0;
77 std::partial_sort(exec, first, m1, last, compare);
78 EXPECT_EQ_N(exp_first, first, p, "wrong effect from partial_sort");
79
80 //checking upper bound number of comparisons; O(p*(last-first)log(middle-first)); where p - number of threads;
81 if (m1 - first > 1)
82 {
83#ifdef _DEBUG
84# if defined(_PSTL_PAR_BACKEND_TBB)
85 auto p = tbb::this_task_arena::max_concurrency();
86# else
87 auto p = 1;
88# endif
89 auto complex = std::ceil(x: n * std::log(x: float32_t(m1 - first)));
90 if (count_comp > complex * p)
91 {
92 std::cout << "complexity exceeded" << std::endl;
93 }
94#endif // _DEBUG
95 }
96 }
97 }
98
99 template <typename Policy, typename InputIterator, typename Compare>
100 typename std::enable_if<!is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
101 void>::type
102 operator()(Policy&&, InputIterator, InputIterator, InputIterator, InputIterator, Compare)
103 {
104 }
105};
106
107template <typename T, typename Compare>
108void
109test_partial_sort(Compare compare)
110{
111
112 const std::size_t n_max = 100000;
113 Sequence<T> in(n_max);
114 Sequence<T> exp(n_max);
115 for (std::size_t n = 0; n < n_max; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
116 {
117 invoke_on_all_policies(test_brick_partial_sort(), in.begin(), in.begin() + n, exp.begin(), exp.begin() + n,
118 compare);
119 }
120}
121
122template <typename T>
123struct test_non_const
124{
125 template <typename Policy, typename Iterator>
126 void
127 operator()(Policy&& exec, Iterator iter)
128 {
129 partial_sort(exec, iter, iter, iter, non_const(std::less<T>()));
130 }
131};
132
133int
134main()
135{
136 count_val = 0;
137
138 test_partial_sort<Num<float32_t>>(compare: [](Num<float32_t> x, Num<float32_t> y) { return x < y; });
139
140 EXPECT_TRUE(count_val == 0, "cleanup error");
141
142 test_partial_sort<int32_t>(
143 compare: [](int32_t x, int32_t y) { return x > y; }); // Reversed so accidental use of < will be detected.
144
145 test_algo_basic_single<int32_t>(f: run_for_rnd<test_non_const<int32_t>>());
146
147 std::cout << done() << std::endl;
148 return 0;
149}
150

source code of pstl/test/std/algorithms/alg.sorting/partial_sort.pass.cpp