New SetOperations and unittesting for all SetOperations

[tejohnson]

Summary

New set operations split out of D140908 as suggested, and I have added
unit testing for all set operations.

This adds a set_intersection, which returns the intersection instead of
updating the first set like set_intersect (using a different name
analogous to set_difference vs set_subtract).

Also adds a variant of set_subtract that updates two additional set
arguments to note which members of the subtrahend were removed from
the minuend and which were not.

[snehasish]

lgtm

llvm/include/llvm/ADT/SetOperations.h

91

extra empty comment line?

llvm/unittests/ADT/SetOperationsTest.cpp

88

For cases where the expected result is empty, if you use EXPECT_THAT(Result, IsEmpty()); you will get an appropriate error message on failure, wont have to call clear on ExpectedResult variables and the expectation is easily spelled out for the reader.

[tejohnson]

Address comments

llvm/include/llvm/ADT/SetOperations.h

 void set_intersect(S1Ty &S1, const S2Ty &S2) {
    for (typename S1Ty::iterator I = S1.begin(); I != S1.end();) {
      const auto &E = *I;
      ++I;
      if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
    }
 }
 
+template <class S1Ty, class S2Ty>
+S1Ty set_intersection_impl(const S1Ty &S1, const S2Ty &S2) {
+   S1Ty Result;
+   for (typename S1Ty::const_iterator SI = S1.begin(), SE = S1.end(); SI != SE;
+        ++SI)
+     if (S2.count(*SI))
+      Result.insert(*SI);
+   return Result;
+}
+
+/// set_intersection(A, B) - Return A ^ B
+template <class S1Ty, class S2Ty>
+S1Ty set_intersection(const S1Ty &S1, const S2Ty &S2) {
+   if (S1.size() < S2.size())
+     return set_intersection_impl(S1, S2);
+   else
+     return set_intersection_impl(S2, S1);
+}
+
 /// set_difference(A, B) - Return A - B
 ///
 template <class S1Ty, class S2Ty>
 S1Ty set_difference(const S1Ty &S1, const S2Ty &S2) {
   S1Ty Result;
   for (typename S1Ty::const_iterator SI = S1.begin(), SE = S1.end();
        SI != SE; ++SI)
     if (!S2.count(*SI))       // if the element is not in set2
       Result.insert(*SI);
   return Result;
 }
 
 /// set_subtract(A, B) - Compute A := A - B
 ///
 template <class S1Ty, class S2Ty>
 void set_subtract(S1Ty &S1, const S2Ty &S2) {
   for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end();
        SI != SE; ++SI)
     S1.erase(*SI);
 }
 
+/// set_subtract(A, B, C, D) - Compute A := A - B, set C to the elements of B
+/// removed from A (A ^ B), and D to the elements of B not found in and removed
+/// from A (B - A).
+///
+template <class S1Ty, class S2Ty>
+void set_subtract(S1Ty &S1, const S2Ty &S2, S1Ty &Removed, S1Ty &Remaining) {
+  for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end(); SI != SE;
+       ++SI)
+    if (S1.erase(*SI))
+      Removed.insert(*SI);
+    else
+      Remaining.insert(*SI);
+}
+
 /// set_is_subset(A, B) - Return true iff A in B
 ///
 template <class S1Ty, class S2Ty>
 bool set_is_subset(const S1Ty &S1, const S2Ty &S2) {
   if (S1.size() > S2.size())
     return false;
   for (const auto It : S1)
     if (!S2.count(It))
       return false;
   return true;
 }
 
 } // End llvm namespace
 
 #endif

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   PostOrderIteratorTest.cpp
   PriorityWorklistTest.cpp
   RangeAdapterTest.cpp
   SCCIteratorTest.cpp
   STLExtrasTest.cpp
   STLForwardCompatTest.cpp
   ScopeExitTest.cpp
   SequenceTest.cpp
+  SetOperationsTest.cpp
   SetVectorTest.cpp
   SimpleIListTest.cpp
   SmallPtrSetTest.cpp
   SmallSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
   SparseMultiSetTest.cpp

llvm/unittests/ADT/SetOperationsTest.cpp

+//===- SetOperations.cpp - Unit tests for set operations ------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SetOperations.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include <set>
+
+using namespace llvm;
+
+namespace {
+
+TEST(SetOperationsTest, SetUnion) {
+  std::set<int> Set1 = {1, 2, 3, 4};
+  std::set<int> Set2 = {5, 6, 7, 8};
+  // Set1 should be the union of input sets Set1 and Set2.
+  std::set<int> ExpectedSet1 = {1, 2, 3, 4, 5, 6, 7, 8};
+  // Set2 should not be touched.
+  std::set<int> ExpectedSet2 = Set2;
+
+  set_union(Set1, Set2);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+
+  Set1.clear();
+  Set2 = {1, 2};
+  // Set1 should be the union of input sets Set1 and Set2, which in this case
+  // will be Set2.
+  ExpectedSet1 = Set2;
+  // Set2 should not be touched.
+  ExpectedSet2 = Set2;
+
+  set_union(Set1, Set2);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+}
+
+TEST(SetOperationsTest, SetIntersect) {
+  std::set<int> Set1 = {1, 2, 3, 4};
+  std::set<int> Set2 = {3, 4, 5, 6};
+  // Set1 should be the intersection of sets Set1 and Set2.
+  std::set<int> ExpectedSet1 = {3, 4};
+  // Set2 should not be touched.
+  std::set<int> ExpectedSet2 = Set2;
+
+  set_intersect(Set1, Set2);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {5, 6};
+  // Set1 should be the intersection of sets Set1 and Set2, which
+  // is empty as they are non-overlapping.
+  ExpectedSet1.clear();
+  // Set2 should not be touched.
+  ExpectedSet2 = Set2;
+
+  set_intersect(Set1, Set2);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+}
+
+TEST(SetOperationsTest, SetIntersection) {
+  std::set<int> Set1 = {1, 2, 3, 4};
+  std::set<int> Set2 = {3, 4, 5, 6};
+  std::set<int> Result;
+  // Result should be the intersection of sets Set1 and Set2.
+  std::set<int> ExpectedResult = {3, 4};
+  // Set1 and Set2 should not be touched.
+  std::set<int> ExpectedSet1 = Set1;
+  std::set<int> ExpectedSet2 = Set2;
+
+  Result = set_intersection(Set1, Set2);
+  EXPECT_EQ(ExpectedResult, Result);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {5, 6};
+  // Result should be the intersection of sets Set1 and Set2, which
+  // is empty as they are non-overlapping.
+  ExpectedResult.clear();
+  // Set1 and Set2 should not be touched.
+  ExpectedSet1 = Set1;
+  ExpectedSet2 = Set2;
+
+  Result = set_intersection(Set1, Set2);
+  EXPECT_EQ(ExpectedResult, Result);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+
+  Set1 = {5, 6};
+  Set2 = {1, 2, 3, 4};
+  // Result should be the intersection of sets Set1 and Set2, which
+  // is empty as they are non-overlapping. Test this again with the input sets
+  // reversed, since the code takes a different path depending on which input
+  // set is smaller.
+  ExpectedResult.clear();
+  // Set1 and Set2 should not be touched.
+  ExpectedSet1 = Set1;
+  ExpectedSet2 = Set2;
+
+  Result = set_intersection(Set1, Set2);
+  EXPECT_EQ(ExpectedResult, Result);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+}
+
+TEST(SetOperationsTest, SetDifference) {
+  std::set<int> Set1 = {1, 2, 3, 4};
+  std::set<int> Set2 = {3, 4, 5, 6};
+  std::set<int> Result;
+  // Result should be Set1 - Set2, leaving only {1, 2}.
+  std::set<int> ExpectedResult = {1, 2};
+  // Set1 and Set2 should not be touched.
+  std::set<int> ExpectedSet1 = Set1;
+  std::set<int> ExpectedSet2 = Set2;
+
+  Result = set_difference(Set1, Set2);
+  EXPECT_EQ(ExpectedResult, Result);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {1, 2, 3, 4};
+  // Result should be Set1 - Set2, which should be empty.
+  ExpectedResult.clear();
+  // Set1 and Set2 should not be touched.
+  ExpectedSet1 = Set1;
+  ExpectedSet2 = Set2;
+
+  Result = set_difference(Set1, Set2);
+  EXPECT_EQ(ExpectedResult, Result);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {5, 6};
+  // Result should be Set1 - Set2, which should be Set1 as they are
+  // non-overlapping.
+  ExpectedResult = Set1;
+  // Set1 and Set2 should not be touched.
+  ExpectedSet1 = Set1;
+  ExpectedSet2 = Set2;
+
+  Result = set_difference(Set1, Set2);
+  EXPECT_EQ(ExpectedResult, Result);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+}
+
+TEST(SetOperationsTest, SetSubtract) {
+  std::set<int> Set1 = {1, 2, 3, 4};
+  std::set<int> Set2 = {3, 4, 5, 6};
+  // Set1 should get Set1 - Set2, leaving only {1, 2}.
+  std::set<int> ExpectedSet1 = {1, 2};
+  // Set2 should not be touched.
+  std::set<int> ExpectedSet2 = Set2;
+
+  set_subtract(Set1, Set2);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {1, 2, 3, 4};
+  // Set1 should get Set1 - Set2, which should be empty.
+  ExpectedSet1.clear();
+  // Set2 should not be touched.
+  ExpectedSet2 = Set2;
+
+  set_subtract(Set1, Set2);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {5, 6};
+  // Set1 should get Set1 - Set2, which should be Set1 as they are
+  // non-overlapping.
+  ExpectedSet1 = Set1;
+  // Set2 should not be touched.
+  ExpectedSet2 = Set2;
+
+  set_subtract(Set1, Set2);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+}
+
+TEST(SetOperationsTest, SetSubtractRemovedRemaining) {
+  std::set<int> Removed, Remaining;
+
+  std::set<int> Set1 = {1, 2, 3, 4};
+  std::set<int> Set2 = {3, 4, 5, 6};
+  // Set1 should get Set1 - Set2, leaving only {1, 2}.
+  std::set<int> ExpectedSet1 = {1, 2};
+  // Set2 should not be touched.
+  std::set<int> ExpectedSet2 = Set2;
+  // We should get back that {3, 4} from Set2 were removed from Set1, and {5, 6}
+  // were not removed from Set1.
+  std::set<int> ExpectedRemoved = {3, 4};
+  std::set<int> ExpectedRemaining = {5, 6};
+
+  set_subtract(Set1, Set2, Removed, Remaining);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+  EXPECT_EQ(ExpectedRemoved, Removed);
+  EXPECT_EQ(ExpectedRemaining, Remaining);
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {1, 2, 3, 4};
+  Removed.clear();
+  Remaining.clear();
+  // Set1 should get Set1 - Set2, which should be empty.
+  ExpectedSet1.clear();
+  // Set2 should not be touched.
+  ExpectedSet2 = Set2;
+  // Set should get back that all of Set2 was removed from Set1, and nothing
+  // left in Set2 was not removed from Set1.
+  ExpectedRemoved = Set2;
+  ExpectedRemaining.clear();
+
+  set_subtract(Set1, Set2, Removed, Remaining);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+  EXPECT_EQ(ExpectedRemoved, Removed);
+  EXPECT_EQ(ExpectedRemaining, Remaining);
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {5, 6};
+  Removed.clear();
+  Remaining.clear();
+  // Set1 should get Set1 - Set2, which should be Set1 as they are
+  // non-overlapping.
+  ExpectedSet1 = {1, 2, 3, 4};
+  // Set2 should not be touched.
+  ExpectedSet2 = Set2;
+  // Set should get back that none of Set2 was removed from Set1, and all
+  // of Set2 was not removed from Set1.
+  ExpectedRemoved.clear();
+  ExpectedRemaining = Set2;
+
+  set_subtract(Set1, Set2, Removed, Remaining);
+  EXPECT_EQ(ExpectedSet1, Set1);
+  EXPECT_EQ(ExpectedSet2, Set2);
+  EXPECT_EQ(ExpectedRemoved, Removed);
+  EXPECT_EQ(ExpectedRemaining, Remaining);
+}
+
+TEST(SetOperationsTest, SetIsSubset) {
+  std::set<int> Set1 = {1, 2, 3, 4};
+  std::set<int> Set2 = {3, 4};
+  EXPECT_FALSE(set_is_subset(Set1, Set2));
+
+  Set1 = {1, 2, 3, 4};
+  Set2 = {1, 2, 3, 4};
+  EXPECT_TRUE(set_is_subset(Set1, Set2));
+
+  Set1 = {1, 2};
+  Set2 = {1, 2, 3, 4};
+  EXPECT_TRUE(set_is_subset(Set1, Set2));
+
+  Set1 = {1, 2};
+  Set2 = {3, 4};
+  EXPECT_FALSE(set_is_subset(Set1, Set2));
+}
+
+} // namespace