LLVM  mainline
SetVector.h
Go to the documentation of this file.
00001 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a set that has insertion order iteration
00011 // characteristics. This is useful for keeping a set of things that need to be
00012 // visited later but in a deterministic order (insertion order). The interface
00013 // is purposefully minimal.
00014 //
00015 // This file defines SetVector and SmallSetVector, which performs no allocations
00016 // if the SetVector has less than a certain number of elements.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #ifndef LLVM_ADT_SETVECTOR_H
00021 #define LLVM_ADT_SETVECTOR_H
00022 
00023 #include "llvm/ADT/DenseSet.h"
00024 #include "llvm/ADT/SmallSet.h"
00025 #include <algorithm>
00026 #include <cassert>
00027 #include <vector>
00028 
00029 namespace llvm {
00030 
00031 /// \brief A vector that has set insertion semantics.
00032 ///
00033 /// This adapter class provides a way to keep a set of things that also has the
00034 /// property of a deterministic iteration order. The order of iteration is the
00035 /// order of insertion.
00036 template <typename T, typename Vector = std::vector<T>,
00037           typename Set = DenseSet<T>>
00038 class SetVector {
00039 public:
00040   typedef T value_type;
00041   typedef T key_type;
00042   typedef T& reference;
00043   typedef const T& const_reference;
00044   typedef Set set_type;
00045   typedef Vector vector_type;
00046   typedef typename vector_type::const_iterator iterator;
00047   typedef typename vector_type::const_iterator const_iterator;
00048   typedef typename vector_type::const_reverse_iterator reverse_iterator;
00049   typedef typename vector_type::const_reverse_iterator const_reverse_iterator;
00050   typedef typename vector_type::size_type size_type;
00051 
00052   /// \brief Construct an empty SetVector
00053   SetVector() {}
00054 
00055   /// \brief Initialize a SetVector with a range of elements
00056   template<typename It>
00057   SetVector(It Start, It End) {
00058     insert(Start, End);
00059   }
00060 
00061   ArrayRef<T> getArrayRef() const { return vector_; }
00062 
00063   /// \brief Determine if the SetVector is empty or not.
00064   bool empty() const {
00065     return vector_.empty();
00066   }
00067 
00068   /// \brief Determine the number of elements in the SetVector.
00069   size_type size() const {
00070     return vector_.size();
00071   }
00072 
00073   /// \brief Get an iterator to the beginning of the SetVector.
00074   iterator begin() {
00075     return vector_.begin();
00076   }
00077 
00078   /// \brief Get a const_iterator to the beginning of the SetVector.
00079   const_iterator begin() const {
00080     return vector_.begin();
00081   }
00082 
00083   /// \brief Get an iterator to the end of the SetVector.
00084   iterator end() {
00085     return vector_.end();
00086   }
00087 
00088   /// \brief Get a const_iterator to the end of the SetVector.
00089   const_iterator end() const {
00090     return vector_.end();
00091   }
00092 
00093   /// \brief Get an reverse_iterator to the end of the SetVector.
00094   reverse_iterator rbegin() {
00095     return vector_.rbegin();
00096   }
00097 
00098   /// \brief Get a const_reverse_iterator to the end of the SetVector.
00099   const_reverse_iterator rbegin() const {
00100     return vector_.rbegin();
00101   }
00102 
00103   /// \brief Get a reverse_iterator to the beginning of the SetVector.
00104   reverse_iterator rend() {
00105     return vector_.rend();
00106   }
00107 
00108   /// \brief Get a const_reverse_iterator to the beginning of the SetVector.
00109   const_reverse_iterator rend() const {
00110     return vector_.rend();
00111   }
00112 
00113   /// \brief Return the last element of the SetVector.
00114   const T &back() const {
00115     assert(!empty() && "Cannot call back() on empty SetVector!");
00116     return vector_.back();
00117   }
00118 
00119   /// \brief Index into the SetVector.
00120   const_reference operator[](size_type n) const {
00121     assert(n < vector_.size() && "SetVector access out of range!");
00122     return vector_[n];
00123   }
00124 
00125   /// \brief Insert a new element into the SetVector.
00126   /// \returns true iff the element was inserted into the SetVector.
00127   bool insert(const value_type &X) {
00128     bool result = set_.insert(X).second;
00129     if (result)
00130       vector_.push_back(X);
00131     return result;
00132   }
00133 
00134   /// \brief Insert a range of elements into the SetVector.
00135   template<typename It>
00136   void insert(It Start, It End) {
00137     for (; Start != End; ++Start)
00138       if (set_.insert(*Start).second)
00139         vector_.push_back(*Start);
00140   }
00141 
00142   /// \brief Remove an item from the set vector.
00143   bool remove(const value_type& X) {
00144     if (set_.erase(X)) {
00145       typename vector_type::iterator I =
00146         std::find(vector_.begin(), vector_.end(), X);
00147       assert(I != vector_.end() && "Corrupted SetVector instances!");
00148       vector_.erase(I);
00149       return true;
00150     }
00151     return false;
00152   }
00153 
00154   /// \brief Remove items from the set vector based on a predicate function.
00155   ///
00156   /// This is intended to be equivalent to the following code, if we could
00157   /// write it:
00158   ///
00159   /// \code
00160   ///   V.erase(std::remove_if(V.begin(), V.end(), P), V.end());
00161   /// \endcode
00162   ///
00163   /// However, SetVector doesn't expose non-const iterators, making any
00164   /// algorithm like remove_if impossible to use.
00165   ///
00166   /// \returns true if any element is removed.
00167   template <typename UnaryPredicate>
00168   bool remove_if(UnaryPredicate P) {
00169     typename vector_type::iterator I
00170       = std::remove_if(vector_.begin(), vector_.end(),
00171                        TestAndEraseFromSet<UnaryPredicate>(P, set_));
00172     if (I == vector_.end())
00173       return false;
00174     vector_.erase(I, vector_.end());
00175     return true;
00176   }
00177 
00178   /// \brief Count the number of elements of a given key in the SetVector.
00179   /// \returns 0 if the element is not in the SetVector, 1 if it is.
00180   size_type count(const key_type &key) const {
00181     return set_.count(key);
00182   }
00183 
00184   /// \brief Completely clear the SetVector
00185   void clear() {
00186     set_.clear();
00187     vector_.clear();
00188   }
00189 
00190   /// \brief Remove the last element of the SetVector.
00191   void pop_back() {
00192     assert(!empty() && "Cannot remove an element from an empty SetVector!");
00193     set_.erase(back());
00194     vector_.pop_back();
00195   }
00196 
00197   T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
00198     T Ret = back();
00199     pop_back();
00200     return Ret;
00201   }
00202 
00203   bool operator==(const SetVector &that) const {
00204     return vector_ == that.vector_;
00205   }
00206 
00207   bool operator!=(const SetVector &that) const {
00208     return vector_ != that.vector_;
00209   }
00210 
00211 private:
00212   /// \brief A wrapper predicate designed for use with std::remove_if.
00213   ///
00214   /// This predicate wraps a predicate suitable for use with std::remove_if to
00215   /// call set_.erase(x) on each element which is slated for removal.
00216   template <typename UnaryPredicate>
00217   class TestAndEraseFromSet {
00218     UnaryPredicate P;
00219     set_type &set_;
00220 
00221   public:
00222     TestAndEraseFromSet(UnaryPredicate P, set_type &set_) : P(P), set_(set_) {}
00223 
00224     template <typename ArgumentT>
00225     bool operator()(const ArgumentT &Arg) {
00226       if (P(Arg)) {
00227         set_.erase(Arg);
00228         return true;
00229       }
00230       return false;
00231     }
00232   };
00233 
00234   set_type set_;         ///< The set.
00235   vector_type vector_;   ///< The vector.
00236 };
00237 
00238 /// \brief A SetVector that performs no allocations if smaller than
00239 /// a certain size.
00240 template <typename T, unsigned N>
00241 class SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > {
00242 public:
00243   SmallSetVector() {}
00244 
00245   /// \brief Initialize a SmallSetVector with a range of elements
00246   template<typename It>
00247   SmallSetVector(It Start, It End) {
00248     this->insert(Start, End);
00249   }
00250 };
00251 
00252 } // End llvm namespace
00253 
00254 // vim: sw=2 ai
00255 #endif