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