1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
// -*- C++ -*-
//===-- set.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++98, c++03, c++11, c++14
#include "support/pstl_test_config.h"
#include <algorithm>
#include <chrono>
#include <cmath>
#include <execution>
#include <functional>
#include "support/utils.h"
using namespace TestUtils;
template <typename T>
struct Num
{
T val;
Num() : val{} {}
Num(const T& v) : val(v) {}
//for "includes" checks
template <typename T1>
bool
operator<(const Num<T1>& v1) const
{
return val < v1.val;
}
//The types Type1 and Type2 must be such that an object of type InputIt can be dereferenced and then implicitly converted to both of them
template <typename T1>
operator Num<T1>() const
{
return Num<T1>((T1)val);
}
friend bool
operator==(const Num& v1, const Num& v2)
{
return v1.val == v2.val;
}
};
struct test_one_policy
{
template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type
operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
Compare comp)
{
using T1 = typename std::iterator_traits<InputIterator1>::value_type;
auto n1 = std::distance(first1, last1);
auto n2 = std::distance(first2, last2);
auto n = n1 + n2;
Sequence<T1> expect(n);
Sequence<T1> out(n);
//1. set_union
auto expect_res = std::set_union(first1, last1, first2, last2, expect.begin(), comp);
auto res = std::set_union(exec, first1, last1, first2, last2, out.begin(), comp);
EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_union");
EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_union effect");
//2. set_intersection
expect_res = std::set_intersection(first1, last1, first2, last2, expect.begin(), comp);
res = std::set_intersection(exec, first1, last1, first2, last2, out.begin(), comp);
EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_intersection");
EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_intersection effect");
//3. set_difference
expect_res = std::set_difference(first1, last1, first2, last2, expect.begin(), comp);
res = std::set_difference(exec, first1, last1, first2, last2, out.begin(), comp);
EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_difference");
EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_difference effect");
//4. set_symmetric_difference
expect_res = std::set_symmetric_difference(first1, last1, first2, last2, expect.begin(), comp);
res = std::set_symmetric_difference(exec, first1, last1, first2, last2, out.begin(), comp);
EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_symmetric_difference");
EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res),
"wrong set_symmetric_difference effect");
}
template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type
operator()(Policy&&, InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare)
{
}
};
template <typename T1, typename T2, typename Compare>
void
test_set(Compare compare)
{
const std::size_t n_max = 100000;
// The rand()%(2*n+1) encourages generation of some duplicates.
std::srand(4200);
for (std::size_t n = 0; n < n_max; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
{
for (std::size_t m = 0; m < n_max; m = m <= 16 ? m + 1 : size_t(2.71828 * m))
{
//prepare the input ranges
Sequence<T1> in1(n, [](std::size_t k) { return rand() % (2 * k + 1); });
Sequence<T2> in2(m, [m](std::size_t k) { return (m % 2) * rand() + rand() % (k + 1); });
std::sort(in1.begin(), in1.end(), compare);
std::sort(in2.begin(), in2.end(), compare);
invoke_on_all_policies(test_one_policy(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), compare);
}
}
}
template <typename T>
struct test_non_const
{
template <typename Policy, typename InputIterator, typename OutputInterator>
void
operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
{
set_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
set_intersection(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
set_symmetric_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter,
non_const(std::less<T>()));
set_union(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
}
};
int
main()
{
test_set<float64_t, float64_t>(std::less<>());
test_set<Num<int64_t>, Num<int32_t>>([](const Num<int64_t>& x, const Num<int32_t>& y) { return x < y; });
test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
std::cout << done() << std::endl;
return 0;
}
|