llvm/ADT/SetOperations.h

0001 //===-- llvm/ADT/SetOperations.h - Generic Set Operations -------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines generic set operations that may be used on set's of
0011 /// different types, and different element types.
0012 ///
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_ADT_SETOPERATIONS_H
0016 #define LLVM_ADT_SETOPERATIONS_H
0017
0018 #include "llvm/ADT/STLExtras.h"
0019
0020 namespace llvm {
0021
0022 namespace detail {
0023 template <typename Set, typename Fn>
0024 using check_has_member_remove_if_t =
0025     decltype(std::declval<Set>().remove_if(std::declval<Fn>()));
0026
0027 template <typename Set, typename Fn>
0028 static constexpr bool HasMemberRemoveIf =
0029     is_detected<check_has_member_remove_if_t, Set, Fn>::value;
0030
0031 template <typename Set>
0032 using check_has_member_erase_iter_t =
0033     decltype(std::declval<Set>().erase(std::declval<Set>().begin()));
0034
0035 template <typename Set>
0036 static constexpr bool HasMemberEraseIter =
0037     is_detected<check_has_member_erase_iter_t, Set>::value;
0038
0039 } // namespace detail
0040
0041 /// set_union(A, B) - Compute A := A u B, return whether A changed.
0042 ///
0043 template <class S1Ty, class S2Ty> bool set_union(S1Ty &S1, const S2Ty &S2) {
0044   bool Changed = false;
0045
0046   for (const auto &E : S2)
0047     if (S1.insert(E).second)
0048       Changed = true;
0049
0050   return Changed;
0051 }
0052
0053 /// set_intersect(A, B) - Compute A := A ^ B
0054 /// Identical to set_intersection, except that it works on set<>'s and
0055 /// is nicer to use.  Functionally, this iterates through S1, removing
0056 /// elements that are not contained in S2.
0057 ///
0058 template <class S1Ty, class S2Ty> void set_intersect(S1Ty &S1, const S2Ty &S2) {
0059   auto Pred = [&S2](const auto &E) { return !S2.count(E); };
0060   if constexpr (detail::HasMemberRemoveIf<S1Ty, decltype(Pred)>) {
0061     S1.remove_if(Pred);
0062   } else {
0063     typename S1Ty::iterator Next;
0064     for (typename S1Ty::iterator I = S1.begin(); I != S1.end(); I = Next) {
0065       Next = std::next(I);
0066       if (!S2.count(*I))
0067         S1.erase(I); // Erase element if not in S2
0068     }
0069   }
0070 }
0071
0072 template <class S1Ty, class S2Ty>
0073 S1Ty set_intersection_impl(const S1Ty &S1, const S2Ty &S2) {
0074   S1Ty Result;
0075   for (const auto &E : S1)
0076     if (S2.count(E))
0077       Result.insert(E);
0078   return Result;
0079 }
0080
0081 /// set_intersection(A, B) - Return A ^ B
0082 template <class S1Ty, class S2Ty>
0083 S1Ty set_intersection(const S1Ty &S1, const S2Ty &S2) {
0084   if (S1.size() < S2.size())
0085     return set_intersection_impl(S1, S2);
0086   else
0087     return set_intersection_impl(S2, S1);
0088 }
0089
0090 /// set_difference(A, B) - Return A - B
0091 ///
0092 template <class S1Ty, class S2Ty>
0093 S1Ty set_difference(const S1Ty &S1, const S2Ty &S2) {
0094   S1Ty Result;
0095   for (const auto &E : S1)
0096     if (!S2.count(E)) // if the element is not in set2
0097       Result.insert(E);
0098   return Result;
0099 }
0100
0101 /// set_subtract(A, B) - Compute A := A - B
0102 ///
0103 /// Selects the set to iterate based on the relative sizes of A and B for better
0104 /// efficiency.
0105 ///
0106 template <class S1Ty, class S2Ty> void set_subtract(S1Ty &S1, const S2Ty &S2) {
0107   // If S1 is smaller than S2, iterate on S1 provided that S2 supports efficient
0108   // lookups via contains().  Note that a couple callers pass a vector for S2,
0109   // which doesn't support contains(), and wouldn't be efficient if it did.
0110   using ElemTy = decltype(*S1.begin());
0111   if constexpr (detail::HasMemberContains<S2Ty, ElemTy>) {
0112     auto Pred = [&S2](const auto &E) { return S2.contains(E); };
0113     if constexpr (detail::HasMemberRemoveIf<S1Ty, decltype(Pred)>) {
0114       if (S1.size() < S2.size()) {
0115         S1.remove_if(Pred);
0116         return;
0117       }
0118     } else if constexpr (detail::HasMemberEraseIter<S1Ty>) {
0119       if (S1.size() < S2.size()) {
0120         typename S1Ty::iterator Next;
0121         for (typename S1Ty::iterator SI = S1.begin(), SE = S1.end(); SI != SE;
0122              SI = Next) {
0123           Next = std::next(SI);
0124           if (S2.contains(*SI))
0125             S1.erase(SI);
0126         }
0127         return;
0128       }
0129     }
0130   }
0131
0132   for (const auto &E : S2)
0133     S1.erase(E);
0134 }
0135
0136 /// set_subtract(A, B, C, D) - Compute A := A - B, set C to the elements of B
0137 /// removed from A (A ^ B), and D to the elements of B not found in and removed
0138 /// from A (B - A).
0139 template <class S1Ty, class S2Ty>
0140 void set_subtract(S1Ty &S1, const S2Ty &S2, S1Ty &Removed, S1Ty &Remaining) {
0141   for (const auto &E : S2)
0142     if (S1.erase(E))
0143       Removed.insert(E);
0144     else
0145       Remaining.insert(E);
0146 }
0147
0148 /// set_is_subset(A, B) - Return true iff A in B
0149 ///
0150 template <class S1Ty, class S2Ty>
0151 bool set_is_subset(const S1Ty &S1, const S2Ty &S2) {
0152   if (S1.size() > S2.size())
0153     return false;
0154   for (const auto It : S1)
0155     if (!S2.count(It))
0156       return false;
0157   return true;
0158 }
0159
0160 } // namespace llvm
0161
0162 #endif