294 lines · cpp
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-exception6//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 18using namespace llvm;19 20using testing::IsEmpty;21using testing::UnorderedElementsAre;22 23namespace {24 25TEST(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 case40 // 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 46TEST(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, which61 // 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 77TEST(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, which94 // 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, which105 // is empty as they are non-overlapping. Test this again with the input sets106 // reversed, since the code takes a different path depending on which input107 // 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 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 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 are141 // 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 148TEST(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 are172 // 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 178TEST(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 194TEST(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 210TEST(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 nothing237 // 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 are248 // 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 all254 // of Set2 was not removed from Set1.255 EXPECT_THAT(Remaining, UnorderedElementsAre(5, 6));256}257 258TEST(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 276TEST(SetOperationsTest, SetIntersects) {277 std::set<int> Set1 = {1, 2, 3, 4};278 std::set<int> Set2 = {3, 4, 5};279 EXPECT_TRUE(set_intersects(Set1, Set2));280 EXPECT_TRUE(set_intersects(Set2, Set1));281 282 Set2 = {5, 6, 7};283 EXPECT_FALSE(set_intersects(Set1, Set2));284 EXPECT_FALSE(set_intersects(Set2, Set1));285 286 // Check that intersecting with a null set returns false.287 Set1.clear();288 EXPECT_FALSE(set_intersects(Set1, Set2));289 EXPECT_FALSE(set_intersects(Set2, Set1));290 EXPECT_FALSE(set_intersects(Set1, Set1));291}292 293} // namespace294