1 // -*- C++ -*-
2 //===-- is_heap.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 // Tests for is_heap, is_heap_until
13 #include "support/pstl_test_config.h"
14
15 #include <execution>
16 #include <algorithm>
17
18 #include "support/utils.h"
19 #include <iostream>
20
21 using namespace TestUtils;
22
23 struct WithCmpOp
24 {
25 int32_t _first;
26 int32_t _second;
WithCmpOpWithCmpOp27 WithCmpOp() : _first(0), _second(0){};
WithCmpOpWithCmpOp28 explicit WithCmpOp(int32_t x) : _first(x), _second(x){};
29 bool
operator <WithCmpOp30 operator<(const WithCmpOp& rhs) const
31 {
32 return this->_first < rhs._first;
33 }
34 };
35
36 struct test_is_heap
37 {
38 #if defined(_PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN) || \
39 defined(_PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN) //dummy specialization by policy type, in case of broken configuration
40 template <typename Iterator, typename Predicate>
41 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
operator ()test_is_heap42 operator()(pstl::execution::unsequenced_policy, Iterator first, Iterator last, Predicate pred)
43 {
44 }
45 template <typename Iterator, typename Predicate>
46 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
operator ()test_is_heap47 operator()(pstl::execution::parallel_unsequenced_policy, Iterator first, Iterator last, Predicate pred)
48 {
49 }
50 #endif
51
52 template <typename Policy, typename Iterator, typename Predicate>
53 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
operator ()test_is_heap54 operator()(Policy&& exec, Iterator first, Iterator last, Predicate pred)
55 {
56 using namespace std;
57 // is_heap
58 {
59 bool expected = is_heap(first, last);
60 bool actual = is_heap(exec, first, last);
61 EXPECT_TRUE(expected == actual, "wrong return value from is_heap");
62 }
63 // is_heap with predicate
64 {
65 bool expected = is_heap(first, last, pred);
66 bool actual = is_heap(exec, first, last, pred);
67 EXPECT_TRUE(expected == actual, "wrong return value from is_heap with predicate");
68 }
69 // is_heap_until
70 {
71 Iterator expected = is_heap_until(first, last);
72 Iterator actual = is_heap_until(exec, first, last);
73 EXPECT_TRUE(expected == actual, "wrong return value from is_heap_until");
74 }
75 // is_heap_until with predicate
76 {
77 const Iterator expected = is_heap_until(first, last, pred);
78 const auto y = std::distance(first, expected);
79 const Iterator actual = is_heap_until(exec, first, last, pred);
80 const auto x = std::distance(first, actual);
81 EXPECT_TRUE(expected == actual, "wrong return value from is_heap_until with predicate");
82 EXPECT_EQ(x, y, "both iterators should be the same distance away from 'first'");
83 }
84 }
85
86 // is_heap, is_heap_until works only with random access iterators
87 template <typename Policy, typename Iterator, typename Predicate>
88 typename std::enable_if<!is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
operator ()test_is_heap89 operator()(Policy&&, Iterator, Iterator, Predicate)
90 {
91 }
92 };
93
94 template <typename T, typename Comp>
95 void
test_is_heap_by_type(Comp comp)96 test_is_heap_by_type(Comp comp)
97 {
98 using namespace std;
99
100 const size_t max_size = 100000;
101 for (size_t n = 0; n <= max_size; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
102 {
103 Sequence<T> in(n, [](size_t v) -> T { return T(v); });
104
105 invoke_on_all_policies(test_is_heap(), in.begin(), in.end(), comp);
106
107 std::make_heap(in.begin(), in.begin() + n / 4, comp);
108 invoke_on_all_policies(test_is_heap(), in.cbegin(), in.cend(), comp);
109
110 std::make_heap(in.begin(), in.begin() + n / 3, comp);
111 invoke_on_all_policies(test_is_heap(), in.begin(), in.end(), comp);
112
113 std::make_heap(in.begin(), in.end(), comp);
114 invoke_on_all_policies(test_is_heap(), in.cbegin(), in.cend(), comp);
115 }
116
117 Sequence<T> in(max_size / 10, [](size_t) -> T { return T(1); });
118 invoke_on_all_policies(test_is_heap(), in.begin(), in.end(), comp);
119 }
120
121 template <typename T>
122 struct test_non_const
123 {
124 template <typename Policy, typename Iterator>
125 void
operator ()test_non_const126 operator()(Policy&& exec, Iterator iter)
127 {
128 invoke_if(exec, [&]() {
129 is_heap(exec, iter, iter, non_const(std::less<T>()));
130 is_heap_until(exec, iter, iter, non_const(std::less<T>()));
131 });
132 }
133 };
134
135 int
main()136 main()
137 {
138 test_is_heap_by_type<float32_t>(std::greater<float32_t>());
139 test_is_heap_by_type<WithCmpOp>(std::less<WithCmpOp>());
140 test_is_heap_by_type<uint64_t>([](uint64_t x, uint64_t y) { return x % 100 < y % 100; });
141
142 test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());
143
144 std::cout << done() << std::endl;
145 return 0;
146 }
147