1 //===-- llvm/ADT/SetOperations.h - Generic Set Operations -------*- C++ -*-===// 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 /// \file 10 /// This file defines generic set operations that may be used on set's of 11 /// different types, and different element types. 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ADT_SETOPERATIONS_H 16 #define LLVM_ADT_SETOPERATIONS_H 17 18 #include "llvm/ADT/STLExtras.h" 19 20 namespace llvm { 21 22 namespace detail { 23 template <typename Set, typename Fn> 24 using check_has_member_remove_if_t = 25 decltype(std::declval<Set>().remove_if(std::declval<Fn>())); 26 27 template <typename Set, typename Fn> 28 static constexpr bool HasMemberRemoveIf = 29 is_detected<check_has_member_remove_if_t, Set, Fn>::value; 30 31 template <typename Set> 32 using check_has_member_erase_iter_t = 33 decltype(std::declval<Set>().erase(std::declval<Set>().begin())); 34 35 template <typename Set> 36 static constexpr bool HasMemberEraseIter = 37 is_detected<check_has_member_erase_iter_t, Set>::value; 38 39 } // namespace detail 40 41 /// set_union(A, B) - Compute A := A u B, return whether A changed. 42 /// 43 template <class S1Ty, class S2Ty> bool set_union(S1Ty &S1, const S2Ty &S2) { 44 bool Changed = false; 45 46 for (const auto &E : S2) 47 if (S1.insert(E).second) 48 Changed = true; 49 50 return Changed; 51 } 52 53 /// set_intersect(A, B) - Compute A := A ^ B 54 /// Identical to set_intersection, except that it works on set<>'s and 55 /// is nicer to use. Functionally, this iterates through S1, removing 56 /// elements that are not contained in S2. 57 /// 58 template <class S1Ty, class S2Ty> void set_intersect(S1Ty &S1, const S2Ty &S2) { 59 auto Pred = [&S2](const auto &E) { return !S2.count(E); }; 60 if constexpr (detail::HasMemberRemoveIf<S1Ty, decltype(Pred)>) { 61 S1.remove_if(Pred); 62 } else { 63 typename S1Ty::iterator Next; 64 for (typename S1Ty::iterator I = S1.begin(); I != S1.end(); I = Next) { 65 Next = std::next(I); 66 if (!S2.count(*I)) 67 S1.erase(I); // Erase element if not in S2 68 } 69 } 70 } 71 72 template <class S1Ty, class S2Ty> 73 S1Ty set_intersection_impl(const S1Ty &S1, const S2Ty &S2) { 74 S1Ty Result; 75 for (const auto &E : S1) 76 if (S2.count(E)) 77 Result.insert(E); 78 return Result; 79 } 80 81 /// set_intersection(A, B) - Return A ^ B 82 template <class S1Ty, class S2Ty> 83 S1Ty set_intersection(const S1Ty &S1, const S2Ty &S2) { 84 if (S1.size() < S2.size()) 85 return set_intersection_impl(S1, S2); 86 else 87 return set_intersection_impl(S2, S1); 88 } 89 90 /// set_difference(A, B) - Return A - B 91 /// 92 template <class S1Ty, class S2Ty> 93 S1Ty set_difference(const S1Ty &S1, const S2Ty &S2) { 94 S1Ty Result; 95 for (const auto &E : S1) 96 if (!S2.count(E)) // if the element is not in set2 97 Result.insert(E); 98 return Result; 99 } 100 101 /// set_subtract(A, B) - Compute A := A - B 102 /// 103 /// Selects the set to iterate based on the relative sizes of A and B for better 104 /// efficiency. 105 /// 106 template <class S1Ty, class S2Ty> void set_subtract(S1Ty &S1, const S2Ty &S2) { 107 // If S1 is smaller than S2, iterate on S1 provided that S2 supports efficient 108 // lookups via contains(). Note that a couple callers pass a vector for S2, 109 // which doesn't support contains(), and wouldn't be efficient if it did. 110 using ElemTy = decltype(*S1.begin()); 111 if constexpr (detail::HasMemberContains<S2Ty, ElemTy>) { 112 auto Pred = [&S2](const auto &E) { return S2.contains(E); }; 113 if constexpr (detail::HasMemberRemoveIf<S1Ty, decltype(Pred)>) { 114 if (S1.size() < S2.size()) { 115 S1.remove_if(Pred); 116 return; 117 } 118 } else if constexpr (detail::HasMemberEraseIter<S1Ty>) { 119 if (S1.size() < S2.size()) { 120 typename S1Ty::iterator Next; 121 for (typename S1Ty::iterator SI = S1.begin(), SE = S1.end(); SI != SE; 122 SI = Next) { 123 Next = std::next(SI); 124 if (S2.contains(*SI)) 125 S1.erase(SI); 126 } 127 return; 128 } 129 } 130 } 131 132 for (const auto &E : S2) 133 S1.erase(E); 134 } 135 136 /// set_subtract(A, B, C, D) - Compute A := A - B, set C to the elements of B 137 /// removed from A (A ^ B), and D to the elements of B not found in and removed 138 /// from A (B - A). 139 template <class S1Ty, class S2Ty> 140 void set_subtract(S1Ty &S1, const S2Ty &S2, S1Ty &Removed, S1Ty &Remaining) { 141 for (const auto &E : S2) 142 if (S1.erase(E)) 143 Removed.insert(E); 144 else 145 Remaining.insert(E); 146 } 147 148 /// set_is_subset(A, B) - Return true iff A in B 149 /// 150 template <class S1Ty, class S2Ty> 151 bool set_is_subset(const S1Ty &S1, const S2Ty &S2) { 152 if (S1.size() > S2.size()) 153 return false; 154 for (const auto It : S1) 155 if (!S2.count(It)) 156 return false; 157 return true; 158 } 159 160 } // namespace llvm 161 162 #endif 163