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 "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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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(Set1, 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