Home | History | Annotate | Download | only in ADT
      1 //===-- llvm/ADT/SetOperations.h - Generic Set Operations -------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     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 typename S1Ty::key_type &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 } // End llvm namespace
     70 
     71 #endif
     72