SetVector.h revision 314564
1193323Sed//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements a set that has insertion order iteration 11193323Sed// characteristics. This is useful for keeping a set of things that need to be 12193323Sed// visited later but in a deterministic order (insertion order). The interface 13193323Sed// is purposefully minimal. 14193323Sed// 15193323Sed// This file defines SetVector and SmallSetVector, which performs no allocations 16193323Sed// if the SetVector has less than a certain number of elements. 17193323Sed// 18193323Sed//===----------------------------------------------------------------------===// 19193323Sed 20193323Sed#ifndef LLVM_ADT_SETVECTOR_H 21193323Sed#define LLVM_ADT_SETVECTOR_H 22193323Sed 23314564Sdim#include "llvm/ADT/ArrayRef.h" 24296417Sdim#include "llvm/ADT/DenseSet.h" 25314564Sdim#include "llvm/ADT/STLExtras.h" 26314564Sdim#include "llvm/Support/Compiler.h" 27193323Sed#include <algorithm> 28193323Sed#include <cassert> 29314564Sdim#include <iterator> 30193323Sed#include <vector> 31193323Sed 32193323Sednamespace llvm { 33193323Sed 34243830Sdim/// \brief A vector that has set insertion semantics. 35243830Sdim/// 36193323Sed/// This adapter class provides a way to keep a set of things that also has the 37193323Sed/// property of a deterministic iteration order. The order of iteration is the 38193323Sed/// order of insertion. 39193323Sedtemplate <typename T, typename Vector = std::vector<T>, 40296417Sdim typename Set = DenseSet<T>> 41193323Sedclass SetVector { 42193323Sedpublic: 43193323Sed typedef T value_type; 44193323Sed typedef T key_type; 45193323Sed typedef T& reference; 46193323Sed typedef const T& const_reference; 47193323Sed typedef Set set_type; 48193323Sed typedef Vector vector_type; 49193323Sed typedef typename vector_type::const_iterator iterator; 50193323Sed typedef typename vector_type::const_iterator const_iterator; 51296417Sdim typedef typename vector_type::const_reverse_iterator reverse_iterator; 52296417Sdim typedef typename vector_type::const_reverse_iterator const_reverse_iterator; 53193323Sed typedef typename vector_type::size_type size_type; 54193323Sed 55243830Sdim /// \brief Construct an empty SetVector 56314564Sdim SetVector() = default; 57193323Sed 58243830Sdim /// \brief Initialize a SetVector with a range of elements 59193323Sed template<typename It> 60193323Sed SetVector(It Start, It End) { 61193323Sed insert(Start, End); 62193323Sed } 63193323Sed 64296417Sdim ArrayRef<T> getArrayRef() const { return vector_; } 65296417Sdim 66314564Sdim /// Clear the SetVector and return the underlying vector. 67314564Sdim Vector takeVector() { 68314564Sdim set_.clear(); 69314564Sdim return std::move(vector_); 70314564Sdim } 71314564Sdim 72243830Sdim /// \brief Determine if the SetVector is empty or not. 73193323Sed bool empty() const { 74193323Sed return vector_.empty(); 75193323Sed } 76193323Sed 77243830Sdim /// \brief Determine the number of elements in the SetVector. 78193323Sed size_type size() const { 79193323Sed return vector_.size(); 80193323Sed } 81193323Sed 82243830Sdim /// \brief Get an iterator to the beginning of the SetVector. 83193323Sed iterator begin() { 84193323Sed return vector_.begin(); 85193323Sed } 86193323Sed 87243830Sdim /// \brief Get a const_iterator to the beginning of the SetVector. 88193323Sed const_iterator begin() const { 89193323Sed return vector_.begin(); 90193323Sed } 91193323Sed 92243830Sdim /// \brief Get an iterator to the end of the SetVector. 93193323Sed iterator end() { 94193323Sed return vector_.end(); 95193323Sed } 96193323Sed 97243830Sdim /// \brief Get a const_iterator to the end of the SetVector. 98193323Sed const_iterator end() const { 99193323Sed return vector_.end(); 100193323Sed } 101193323Sed 102296417Sdim /// \brief Get an reverse_iterator to the end of the SetVector. 103296417Sdim reverse_iterator rbegin() { 104296417Sdim return vector_.rbegin(); 105296417Sdim } 106296417Sdim 107296417Sdim /// \brief Get a const_reverse_iterator to the end of the SetVector. 108296417Sdim const_reverse_iterator rbegin() const { 109296417Sdim return vector_.rbegin(); 110296417Sdim } 111296417Sdim 112296417Sdim /// \brief Get a reverse_iterator to the beginning of the SetVector. 113296417Sdim reverse_iterator rend() { 114296417Sdim return vector_.rend(); 115296417Sdim } 116296417Sdim 117296417Sdim /// \brief Get a const_reverse_iterator to the beginning of the SetVector. 118296417Sdim const_reverse_iterator rend() const { 119296417Sdim return vector_.rend(); 120296417Sdim } 121296417Sdim 122243830Sdim /// \brief Return the last element of the SetVector. 123193323Sed const T &back() const { 124193323Sed assert(!empty() && "Cannot call back() on empty SetVector!"); 125193323Sed return vector_.back(); 126193323Sed } 127193323Sed 128243830Sdim /// \brief Index into the SetVector. 129193323Sed const_reference operator[](size_type n) const { 130193323Sed assert(n < vector_.size() && "SetVector access out of range!"); 131193323Sed return vector_[n]; 132193323Sed } 133193323Sed 134243830Sdim /// \brief Insert a new element into the SetVector. 135309124Sdim /// \returns true if the element was inserted into the SetVector. 136193323Sed bool insert(const value_type &X) { 137280031Sdim bool result = set_.insert(X).second; 138193323Sed if (result) 139193323Sed vector_.push_back(X); 140193323Sed return result; 141193323Sed } 142193323Sed 143243830Sdim /// \brief Insert a range of elements into the SetVector. 144193323Sed template<typename It> 145193323Sed void insert(It Start, It End) { 146193323Sed for (; Start != End; ++Start) 147280031Sdim if (set_.insert(*Start).second) 148193323Sed vector_.push_back(*Start); 149193323Sed } 150193323Sed 151243830Sdim /// \brief Remove an item from the set vector. 152218893Sdim bool remove(const value_type& X) { 153193323Sed if (set_.erase(X)) { 154314564Sdim typename vector_type::iterator I = find(vector_, X); 155193323Sed assert(I != vector_.end() && "Corrupted SetVector instances!"); 156193323Sed vector_.erase(I); 157218893Sdim return true; 158193323Sed } 159218893Sdim return false; 160193323Sed } 161193323Sed 162309124Sdim /// Erase a single element from the set vector. 163309124Sdim /// \returns an iterator pointing to the next element that followed the 164309124Sdim /// element erased. This is the end of the SetVector if the last element is 165309124Sdim /// erased. 166309124Sdim iterator erase(iterator I) { 167309124Sdim const key_type &V = *I; 168309124Sdim assert(set_.count(V) && "Corrupted SetVector instances!"); 169309124Sdim set_.erase(V); 170309124Sdim 171309124Sdim // FIXME: No need to use the non-const iterator when built with 172309124Sdim // std:vector.erase(const_iterator) as defined in C++11. This is for 173309124Sdim // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9). 174309124Sdim auto NI = vector_.begin(); 175309124Sdim std::advance(NI, std::distance<iterator>(NI, I)); 176309124Sdim 177309124Sdim return vector_.erase(NI); 178309124Sdim } 179309124Sdim 180243830Sdim /// \brief Remove items from the set vector based on a predicate function. 181243830Sdim /// 182243830Sdim /// This is intended to be equivalent to the following code, if we could 183243830Sdim /// write it: 184243830Sdim /// 185243830Sdim /// \code 186314564Sdim /// V.erase(remove_if(V, P), V.end()); 187243830Sdim /// \endcode 188243830Sdim /// 189243830Sdim /// However, SetVector doesn't expose non-const iterators, making any 190243830Sdim /// algorithm like remove_if impossible to use. 191243830Sdim /// 192243830Sdim /// \returns true if any element is removed. 193243830Sdim template <typename UnaryPredicate> 194243830Sdim bool remove_if(UnaryPredicate P) { 195314564Sdim typename vector_type::iterator I = 196314564Sdim llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_)); 197243830Sdim if (I == vector_.end()) 198243830Sdim return false; 199243830Sdim vector_.erase(I, vector_.end()); 200243830Sdim return true; 201243830Sdim } 202193323Sed 203243830Sdim /// \brief Count the number of elements of a given key in the SetVector. 204243830Sdim /// \returns 0 if the element is not in the SetVector, 1 if it is. 205193323Sed size_type count(const key_type &key) const { 206193323Sed return set_.count(key); 207193323Sed } 208193323Sed 209243830Sdim /// \brief Completely clear the SetVector 210193323Sed void clear() { 211193323Sed set_.clear(); 212193323Sed vector_.clear(); 213193323Sed } 214193323Sed 215243830Sdim /// \brief Remove the last element of the SetVector. 216193323Sed void pop_back() { 217193323Sed assert(!empty() && "Cannot remove an element from an empty SetVector!"); 218193323Sed set_.erase(back()); 219193323Sed vector_.pop_back(); 220193323Sed } 221296417Sdim 222314564Sdim LLVM_NODISCARD T pop_back_val() { 223234353Sdim T Ret = back(); 224234353Sdim pop_back(); 225234353Sdim return Ret; 226234353Sdim } 227193323Sed 228210299Sed bool operator==(const SetVector &that) const { 229210299Sed return vector_ == that.vector_; 230210299Sed } 231210299Sed 232210299Sed bool operator!=(const SetVector &that) const { 233210299Sed return vector_ != that.vector_; 234210299Sed } 235309124Sdim 236309124Sdim /// \brief Compute This := This u S, return whether 'This' changed. 237309124Sdim /// TODO: We should be able to use set_union from SetOperations.h, but 238309124Sdim /// SetVector interface is inconsistent with DenseSet. 239309124Sdim template <class STy> 240309124Sdim bool set_union(const STy &S) { 241309124Sdim bool Changed = false; 242210299Sed 243309124Sdim for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 244309124Sdim ++SI) 245309124Sdim if (insert(*SI)) 246309124Sdim Changed = true; 247309124Sdim 248309124Sdim return Changed; 249309124Sdim } 250309124Sdim 251309124Sdim /// \brief Compute This := This - B 252309124Sdim /// TODO: We should be able to use set_subtract from SetOperations.h, but 253309124Sdim /// SetVector interface is inconsistent with DenseSet. 254309124Sdim template <class STy> 255309124Sdim void set_subtract(const STy &S) { 256309124Sdim for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 257309124Sdim ++SI) 258309124Sdim remove(*SI); 259309124Sdim } 260309124Sdim 261193323Sedprivate: 262243830Sdim /// \brief A wrapper predicate designed for use with std::remove_if. 263243830Sdim /// 264243830Sdim /// This predicate wraps a predicate suitable for use with std::remove_if to 265243830Sdim /// call set_.erase(x) on each element which is slated for removal. 266243830Sdim template <typename UnaryPredicate> 267243830Sdim class TestAndEraseFromSet { 268243830Sdim UnaryPredicate P; 269243830Sdim set_type &set_; 270243830Sdim 271243830Sdim public: 272309124Sdim TestAndEraseFromSet(UnaryPredicate P, set_type &set_) 273309124Sdim : P(std::move(P)), set_(set_) {} 274243830Sdim 275276479Sdim template <typename ArgumentT> 276276479Sdim bool operator()(const ArgumentT &Arg) { 277243830Sdim if (P(Arg)) { 278243830Sdim set_.erase(Arg); 279243830Sdim return true; 280243830Sdim } 281243830Sdim return false; 282243830Sdim } 283243830Sdim }; 284243830Sdim 285193323Sed set_type set_; ///< The set. 286193323Sed vector_type vector_; ///< The vector. 287193323Sed}; 288193323Sed 289243830Sdim/// \brief A SetVector that performs no allocations if smaller than 290193323Sed/// a certain size. 291193323Sedtemplate <typename T, unsigned N> 292314564Sdimclass SmallSetVector 293314564Sdim : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> { 294193323Sedpublic: 295314564Sdim SmallSetVector() = default; 296193323Sed 297243830Sdim /// \brief Initialize a SmallSetVector with a range of elements 298193323Sed template<typename It> 299193323Sed SmallSetVector(It Start, It End) { 300193323Sed this->insert(Start, End); 301193323Sed } 302193323Sed}; 303193323Sed 304314564Sdim} // end namespace llvm 305193323Sed 306314564Sdim#endif // LLVM_ADT_SETVECTOR_H 307