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 | |
15 | using namespace llvm; |
16 | |
17 | using testing::IsEmpty; |
18 | |
19 | namespace { |
20 | |
21 | TEST(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 | |
46 | TEST(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 | |
70 | TEST(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 | |
114 | TEST(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 | |
156 | TEST(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 | |
191 | TEST(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 | |
248 | TEST(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 | |