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
21using namespace TestUtils;
22
23struct WithCmpOp
24{
25 int32_t _first;
26 int32_t _second;
27 WithCmpOp() : _first(0), _second(0){};
28 explicit WithCmpOp(int32_t x) : _first(x), _second(x){};
29 bool
30 operator<(const WithCmpOp& rhs) const
31 {
32 return this->_first < rhs._first;
33 }
34};
35
36struct 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
42 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
47 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
54 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
89 operator()(Policy&&, Iterator, Iterator, Predicate)
90 {
91 }
92};
93
94template <typename T, typename Comp>
95void
96test_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
121template <typename T>
122struct test_non_const
123{
124 template <typename Policy, typename Iterator>
125 void
126 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
135int
136main()
137{
138 test_is_heap_by_type<float32_t>(comp: std::greater<float32_t>());
139 test_is_heap_by_type<WithCmpOp>(comp: std::less<WithCmpOp>());
140 test_is_heap_by_type<uint64_t>(comp: [](uint64_t x, uint64_t y) { return x % 100 < y % 100; });
141
142 test_algo_basic_single<int32_t>(f: run_for_rnd<test_non_const<int32_t>>());
143
144 std::cout << done() << std::endl;
145 return 0;
146}
147

source code of pstl/test/std/algorithms/alg.sorting/alg.heap.operations/is_heap.pass.cpp