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 | namespace llvm { |
19 | |
20 | /// set_union(A, B) - Compute A := A u B, return whether A changed. |
21 | /// |
22 | template <class S1Ty, class S2Ty> |
23 | bool set_union(S1Ty &S1, const S2Ty &S2) { |
24 | bool Changed = false; |
25 | |
26 | for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end(); |
27 | SI != SE; ++SI) |
28 | if (S1.insert(*SI).second) |
29 | Changed = true; |
30 | |
31 | return Changed; |
32 | } |
33 | |
34 | /// set_intersect(A, B) - Compute A := A ^ B |
35 | /// Identical to set_intersection, except that it works on set<>'s and |
36 | /// is nicer to use. Functionally, this iterates through S1, removing |
37 | /// elements that are not contained in S2. |
38 | /// |
39 | template <class S1Ty, class S2Ty> |
40 | void set_intersect(S1Ty &S1, const S2Ty &S2) { |
41 | for (typename S1Ty::iterator I = S1.begin(); I != S1.end();) { |
42 | const auto &E = *I; |
43 | ++I; |
44 | if (!S2.count(E)) S1.erase(E); // Erase element if not in S2 |
45 | } |
46 | } |
47 | |
48 | template <class S1Ty, class S2Ty> |
49 | S1Ty set_intersection_impl(const S1Ty &S1, const S2Ty &S2) { |
50 | S1Ty Result; |
51 | for (typename S1Ty::const_iterator SI = S1.begin(), SE = S1.end(); SI != SE; |
52 | ++SI) |
53 | if (S2.count(*SI)) |
54 | Result.insert(*SI); |
55 | return Result; |
56 | } |
57 | |
58 | /// set_intersection(A, B) - Return A ^ B |
59 | template <class S1Ty, class S2Ty> |
60 | S1Ty set_intersection(const S1Ty &S1, const S2Ty &S2) { |
61 | if (S1.size() < S2.size()) |
62 | return set_intersection_impl(S1, S2); |
63 | else |
64 | return set_intersection_impl(S2, S1); |
65 | } |
66 | |
67 | /// set_difference(A, B) - Return A - B |
68 | /// |
69 | template <class S1Ty, class S2Ty> |
70 | S1Ty set_difference(const S1Ty &S1, const S2Ty &S2) { |
71 | S1Ty Result; |
72 | for (typename S1Ty::const_iterator SI = S1.begin(), SE = S1.end(); |
73 | SI != SE; ++SI) |
74 | if (!S2.count(*SI)) // if the element is not in set2 |
75 | Result.insert(*SI); |
76 | return Result; |
77 | } |
78 | |
79 | /// set_subtract(A, B) - Compute A := A - B |
80 | /// |
81 | template <class S1Ty, class S2Ty> |
82 | void set_subtract(S1Ty &S1, const S2Ty &S2) { |
83 | for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end(); |
84 | SI != SE; ++SI) |
85 | S1.erase(*SI); |
86 | } |
87 | |
88 | /// set_subtract(A, B, C, D) - Compute A := A - B, set C to the elements of B |
89 | /// removed from A (A ^ B), and D to the elements of B not found in and removed |
90 | /// from A (B - A). |
91 | template <class S1Ty, class S2Ty> |
92 | void set_subtract(S1Ty &S1, const S2Ty &S2, S1Ty &Removed, S1Ty &Remaining) { |
93 | for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end(); SI != SE; |
94 | ++SI) |
95 | if (S1.erase(*SI)) |
96 | Removed.insert(*SI); |
97 | else |
98 | Remaining.insert(*SI); |
99 | } |
100 | |
101 | /// set_is_subset(A, B) - Return true iff A in B |
102 | /// |
103 | template <class S1Ty, class S2Ty> |
104 | bool set_is_subset(const S1Ty &S1, const S2Ty &S2) { |
105 | if (S1.size() > S2.size()) |
106 | return false; |
107 | for (const auto It : S1) |
108 | if (!S2.count(It)) |
109 | return false; |
110 | return true; |
111 | } |
112 | |
113 | } // End llvm namespace |
114 | |
115 | #endif |
116 | |