Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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 | /// set_difference(A, B) - Return A - B |
||
| 49 | /// |
||
| 50 | template <class S1Ty, class S2Ty> |
||
| 51 | S1Ty set_difference(const S1Ty &S1, const S2Ty &S2) { |
||
| 52 | S1Ty Result; |
||
| 53 | for (typename S1Ty::const_iterator SI = S1.begin(), SE = S1.end(); |
||
| 54 | SI != SE; ++SI) |
||
| 55 | if (!S2.count(*SI)) // if the element is not in set2 |
||
| 56 | Result.insert(*SI); |
||
| 57 | return Result; |
||
| 58 | } |
||
| 59 | |||
| 60 | /// set_subtract(A, B) - Compute A := A - B |
||
| 61 | /// |
||
| 62 | template <class S1Ty, class S2Ty> |
||
| 63 | void set_subtract(S1Ty &S1, const S2Ty &S2) { |
||
| 64 | for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end(); |
||
| 65 | SI != SE; ++SI) |
||
| 66 | S1.erase(*SI); |
||
| 67 | } |
||
| 68 | |||
| 69 | /// set_is_subset(A, B) - Return true iff A in B |
||
| 70 | /// |
||
| 71 | template <class S1Ty, class S2Ty> |
||
| 72 | bool set_is_subset(const S1Ty &S1, const S2Ty &S2) { |
||
| 73 | if (S1.size() > S2.size()) |
||
| 74 | return false; |
||
| 75 | for (const auto It : S1) |
||
| 76 | if (!S2.count(It)) |
||
| 77 | return false; |
||
| 78 | return true; |
||
| 79 | } |
||
| 80 | |||
| 81 | } // End llvm namespace |
||
| 82 | |||
| 83 | #endif |