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 ///
set_union(S1Ty & S1,const S2Ty & S2)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 ///
set_intersect(S1Ty & S1,const S2Ty & S2)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>
set_intersection_impl(const S1Ty & S1,const S2Ty & S2)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>
set_intersection(const S1Ty & S1,const S2Ty & S2)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>
set_difference(const S1Ty & S1,const S2Ty & S2)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 ///
set_subtract(S1Ty & S1,const S2Ty & S2)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>
set_subtract(S1Ty & S1,const S2Ty & S2,S1Ty & Removed,S1Ty & Remaining)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>
set_is_subset(const S1Ty & S1,const S2Ty & S2)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