include/llvm/ADT/SetOperations.h

   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 // This file defines generic set operations that may be used on set's of
  10 // different types, and different element types.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_SETOPERATIONS_H
  15 #define LLVM_ADT_SETOPERATIONS_H
  16
  17 namespace llvm {
  18
  19 /// set_union(A, B) - Compute A := A u B, return whether A changed.
  20 ///
  21 template <class S1Ty, class S2Ty>
  22 bool set_union(S1Ty &S1, const S2Ty &S2) {
  23   bool Changed = false;
  24
  25   for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end();
  26        SI != SE; ++SI)
  27     if (S1.insert(*SI).second)
  28       Changed = true;
  29
  30   return Changed;
  31 }
  32
  33 /// set_intersect(A, B) - Compute A := A ^ B
  34 /// Identical to set_intersection, except that it works on set<>'s and
  35 /// is nicer to use.  Functionally, this iterates through S1, removing
  36 /// elements that are not contained in S2.
  37 ///
  38 template <class S1Ty, class S2Ty>
  39 void set_intersect(S1Ty &S1, const S2Ty &S2) {
  40    for (typename S1Ty::iterator I = S1.begin(); I != S1.end();) {
  41      const auto &E = *I;
  42      ++I;
  43      if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
  44    }
  45 }
  46
  47 /// set_difference(A, B) - Return A - B
  48 ///
  49 template <class S1Ty, class S2Ty>
  50 S1Ty set_difference(const S1Ty &S1, const S2Ty &S2) {
  51   S1Ty Result;
  52   for (typename S1Ty::const_iterator SI = S1.begin(), SE = S1.end();
  53        SI != SE; ++SI)
  54     if (!S2.count(*SI))       // if the element is not in set2
  55       Result.insert(*SI);
  56   return Result;
  57 }
  58
  59 /// set_subtract(A, B) - Compute A := A - B
  60 ///
  61 template <class S1Ty, class S2Ty>
  62 void set_subtract(S1Ty &S1, const S2Ty &S2) {
  63   for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end();
  64        SI != SE; ++SI)
  65     S1.erase(*SI);
  66 }
  67
  68 } // End llvm namespace
  69
  70 #endif