1//===- SetOperations.cpp - Unit tests for set operations ------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/ADT/SetOperations.h"
10#include "gmock/gmock.h"
11#include "gtest/gtest.h"
12
13#include <set>
14
15using namespace llvm;
16
17using testing::IsEmpty;
18
19namespace {
20
21TEST(SetOperationsTest, SetUnion) {
22 std::set<int> Set1 = {1, 2, 3, 4};
23 std::set<int> Set2 = {5, 6, 7, 8};
24 // Set1 should be the union of input sets Set1 and Set2.
25 std::set<int> ExpectedSet1 = {1, 2, 3, 4, 5, 6, 7, 8};
26 // Set2 should not be touched.
27 std::set<int> ExpectedSet2 = Set2;
28
29 set_union(S1&: Set1, S2: Set2);
30 EXPECT_EQ(ExpectedSet1, Set1);
31 EXPECT_EQ(ExpectedSet2, Set2);
32
33 Set1.clear();
34 Set2 = {1, 2};
35 // Set1 should be the union of input sets Set1 and Set2, which in this case
36 // will be Set2.
37 ExpectedSet1 = Set2;
38 // Set2 should not be touched.
39 ExpectedSet2 = Set2;
40
41 set_union(S1&: Set1, S2: Set2);
42 EXPECT_EQ(ExpectedSet1, Set1);
43 EXPECT_EQ(ExpectedSet2, Set2);
44}
45
46TEST(SetOperationsTest, SetIntersect) {
47 std::set<int> Set1 = {1, 2, 3, 4};
48 std::set<int> Set2 = {3, 4, 5, 6};
49 // Set1 should be the intersection of sets Set1 and Set2.
50 std::set<int> ExpectedSet1 = {3, 4};
51 // Set2 should not be touched.
52 std::set<int> ExpectedSet2 = Set2;
53
54 set_intersect(S1&: Set1, S2: Set2);
55 EXPECT_EQ(ExpectedSet1, Set1);
56 EXPECT_EQ(ExpectedSet2, Set2);
57
58 Set1 = {1, 2, 3, 4};
59 Set2 = {5, 6};
60 // Set2 should not be touched.
61 ExpectedSet2 = Set2;
62
63 set_intersect(S1&: Set1, S2: Set2);
64 // Set1 should be the intersection of sets Set1 and Set2, which
65 // is empty as they are non-overlapping.
66 EXPECT_THAT(Set1, IsEmpty());
67 EXPECT_EQ(ExpectedSet2, Set2);
68}
69
70TEST(SetOperationsTest, SetIntersection) {
71 std::set<int> Set1 = {1, 2, 3, 4};
72 std::set<int> Set2 = {3, 4, 5, 6};
73 std::set<int> Result;
74 // Result should be the intersection of sets Set1 and Set2.
75 std::set<int> ExpectedResult = {3, 4};
76 // Set1 and Set2 should not be touched.
77 std::set<int> ExpectedSet1 = Set1;
78 std::set<int> ExpectedSet2 = Set2;
79
80 Result = set_intersection(S1: Set1, S2: Set2);
81 EXPECT_EQ(ExpectedResult, Result);
82 EXPECT_EQ(ExpectedSet1, Set1);
83 EXPECT_EQ(ExpectedSet2, Set2);
84
85 Set1 = {1, 2, 3, 4};
86 Set2 = {5, 6};
87 // Set1 and Set2 should not be touched.
88 ExpectedSet1 = Set1;
89 ExpectedSet2 = Set2;
90
91 Result = set_intersection(S1: Set1, S2: Set2);
92 // Result should be the intersection of sets Set1 and Set2, which
93 // is empty as they are non-overlapping.
94 EXPECT_THAT(Result, IsEmpty());
95 EXPECT_EQ(ExpectedSet1, Set1);
96 EXPECT_EQ(ExpectedSet2, Set2);
97
98 Set1 = {5, 6};
99 Set2 = {1, 2, 3, 4};
100 // Set1 and Set2 should not be touched.
101 ExpectedSet1 = Set1;
102 ExpectedSet2 = Set2;
103
104 Result = set_intersection(S1: Set1, S2: Set2);
105 // Result should be the intersection of sets Set1 and Set2, which
106 // is empty as they are non-overlapping. Test this again with the input sets
107 // reversed, since the code takes a different path depending on which input
108 // set is smaller.
109 EXPECT_THAT(Result, IsEmpty());
110 EXPECT_EQ(ExpectedSet1, Set1);
111 EXPECT_EQ(ExpectedSet2, Set2);
112}
113
114TEST(SetOperationsTest, SetDifference) {
115 std::set<int> Set1 = {1, 2, 3, 4};
116 std::set<int> Set2 = {3, 4, 5, 6};
117 std::set<int> Result;
118 // Result should be Set1 - Set2, leaving only {1, 2}.
119 std::set<int> ExpectedResult = {1, 2};
120 // Set1 and Set2 should not be touched.
121 std::set<int> ExpectedSet1 = Set1;
122 std::set<int> ExpectedSet2 = Set2;
123
124 Result = set_difference(S1: Set1, S2: Set2);
125 EXPECT_EQ(ExpectedResult, Result);
126 EXPECT_EQ(ExpectedSet1, Set1);
127 EXPECT_EQ(ExpectedSet2, Set2);
128
129 Set1 = {1, 2, 3, 4};
130 Set2 = {1, 2, 3, 4};
131 // Set1 and Set2 should not be touched.
132 ExpectedSet1 = Set1;
133 ExpectedSet2 = Set2;
134
135 Result = set_difference(S1: Set1, S2: Set2);
136 // Result should be Set1 - Set2, which should be empty.
137 EXPECT_THAT(Result, IsEmpty());
138 EXPECT_EQ(ExpectedSet1, Set1);
139 EXPECT_EQ(ExpectedSet2, Set2);
140
141 Set1 = {1, 2, 3, 4};
142 Set2 = {5, 6};
143 // Result should be Set1 - Set2, which should be Set1 as they are
144 // non-overlapping.
145 ExpectedResult = Set1;
146 // Set1 and Set2 should not be touched.
147 ExpectedSet1 = Set1;
148 ExpectedSet2 = Set2;
149
150 Result = set_difference(S1: Set1, S2: Set2);
151 EXPECT_EQ(ExpectedResult, Result);
152 EXPECT_EQ(ExpectedSet1, Set1);
153 EXPECT_EQ(ExpectedSet2, Set2);
154}
155
156TEST(SetOperationsTest, SetSubtract) {
157 std::set<int> Set1 = {1, 2, 3, 4};
158 std::set<int> Set2 = {3, 4, 5, 6};
159 // Set1 should get Set1 - Set2, leaving only {1, 2}.
160 std::set<int> ExpectedSet1 = {1, 2};
161 // Set2 should not be touched.
162 std::set<int> ExpectedSet2 = Set2;
163
164 set_subtract(S1&: Set1, S2: Set2);
165 EXPECT_EQ(ExpectedSet1, Set1);
166 EXPECT_EQ(ExpectedSet2, Set2);
167
168 Set1 = {1, 2, 3, 4};
169 Set2 = {1, 2, 3, 4};
170 // Set2 should not be touched.
171 ExpectedSet2 = Set2;
172
173 set_subtract(S1&: Set1, S2: Set2);
174 // Set1 should get Set1 - Set2, which should be empty.
175 EXPECT_THAT(Set1, IsEmpty());
176 EXPECT_EQ(ExpectedSet2, Set2);
177
178 Set1 = {1, 2, 3, 4};
179 Set2 = {5, 6};
180 // Set1 should get Set1 - Set2, which should be Set1 as they are
181 // non-overlapping.
182 ExpectedSet1 = Set1;
183 // Set2 should not be touched.
184 ExpectedSet2 = Set2;
185
186 set_subtract(S1&: Set1, S2: Set2);
187 EXPECT_EQ(ExpectedSet1, Set1);
188 EXPECT_EQ(ExpectedSet2, Set2);
189}
190
191TEST(SetOperationsTest, SetSubtractRemovedRemaining) {
192 std::set<int> Removed, Remaining;
193
194 std::set<int> Set1 = {1, 2, 3, 4};
195 std::set<int> Set2 = {3, 4, 5, 6};
196 // Set1 should get Set1 - Set2, leaving only {1, 2}.
197 std::set<int> ExpectedSet1 = {1, 2};
198 // Set2 should not be touched.
199 std::set<int> ExpectedSet2 = Set2;
200 // We should get back that {3, 4} from Set2 were removed from Set1, and {5, 6}
201 // were not removed from Set1.
202 std::set<int> ExpectedRemoved = {3, 4};
203 std::set<int> ExpectedRemaining = {5, 6};
204
205 set_subtract(S1&: Set1, S2: Set2, Removed, Remaining);
206 EXPECT_EQ(ExpectedSet1, Set1);
207 EXPECT_EQ(ExpectedSet2, Set2);
208 EXPECT_EQ(ExpectedRemoved, Removed);
209 EXPECT_EQ(ExpectedRemaining, Remaining);
210
211 Set1 = {1, 2, 3, 4};
212 Set2 = {1, 2, 3, 4};
213 Removed.clear();
214 Remaining.clear();
215 // Set2 should not be touched.
216 ExpectedSet2 = Set2;
217 // Set should get back that all of Set2 was removed from Set1, and nothing
218 // left in Set2 was not removed from Set1.
219 ExpectedRemoved = Set2;
220
221 set_subtract(S1&: Set1, S2: Set2, Removed, Remaining);
222 // Set1 should get Set1 - Set2, which should be empty.
223 EXPECT_THAT(Set1, IsEmpty());
224 EXPECT_EQ(ExpectedSet2, Set2);
225 EXPECT_EQ(ExpectedRemoved, Removed);
226 EXPECT_THAT(Remaining, IsEmpty());
227
228 Set1 = {1, 2, 3, 4};
229 Set2 = {5, 6};
230 Removed.clear();
231 Remaining.clear();
232 // Set1 should get Set1 - Set2, which should be Set1 as they are
233 // non-overlapping.
234 ExpectedSet1 = {1, 2, 3, 4};
235 // Set2 should not be touched.
236 ExpectedSet2 = Set2;
237 // Set should get back that none of Set2 was removed from Set1, and all
238 // of Set2 was not removed from Set1.
239 ExpectedRemaining = Set2;
240
241 set_subtract(S1&: Set1, S2: Set2, Removed, Remaining);
242 EXPECT_EQ(ExpectedSet1, Set1);
243 EXPECT_EQ(ExpectedSet2, Set2);
244 EXPECT_THAT(Removed, IsEmpty());
245 EXPECT_EQ(ExpectedRemaining, Remaining);
246}
247
248TEST(SetOperationsTest, SetIsSubset) {
249 std::set<int> Set1 = {1, 2, 3, 4};
250 std::set<int> Set2 = {3, 4};
251 EXPECT_FALSE(set_is_subset(Set1, Set2));
252
253 Set1 = {1, 2, 3, 4};
254 Set2 = {1, 2, 3, 4};
255 EXPECT_TRUE(set_is_subset(Set1, Set2));
256
257 Set1 = {1, 2};
258 Set2 = {1, 2, 3, 4};
259 EXPECT_TRUE(set_is_subset(Set1, Set2));
260
261 Set1 = {1, 2};
262 Set2 = {3, 4};
263 EXPECT_FALSE(set_is_subset(Set1, Set2));
264}
265
266} // namespace
267

source code of llvm/unittests/ADT/SetOperationsTest.cpp