llvm/unittests/ADT/SetOperationsTest.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-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