Line data    Source code

       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    49806635 : bool set_union(S1Ty &S1, const S2Ty &S2) {
      24             :   bool Changed = false;
      25             : 
      26    45361274 :   for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end();
      27    95178122 :        SI != SE; ++SI)
      28    45371487 :     if (S1.insert(*SI).second)
      29             :       Changed = true;
      30             : 
      31    49806635 :   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       12862 : void set_intersect(S1Ty &S1, const S2Ty &S2) {
      41       23369 :    for (typename S1Ty::iterator I = S1.begin(); I != S1.end();) {
      42             :      const auto &E = *I;
      43             :      ++I;
      44       10507 :      if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
      45             :    }
      46       12862 : }
      47             : 
      48             : /// set_difference(A, B) - Return A - B
      49             : ///
      50             : template <class S1Ty, class S2Ty>
      51          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          62 :        SI != SE; ++SI)
      55             :     if (!S2.count(*SI))       // if the element is not in set2
      56             :       Result.insert(*SI);
      57          51 :   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    19806640 :   for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end();
      65    69612694 :        SI != SE; ++SI)
      66             :     S1.erase(*SI);
      67             : }
      68             : 
      69             : } // End llvm namespace
      70             : 
      71             : #endif