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 23193323Sed#include "llvm/ADT/SmallSet.h" 24193323Sed#include <algorithm> 25193323Sed#include <cassert> 26193323Sed#include <vector> 27193323Sed 28193323Sednamespace llvm { 29193323Sed 30243830Sdim/// \brief A vector that has set insertion semantics. 31243830Sdim/// 32193323Sed/// This adapter class provides a way to keep a set of things that also has the 33193323Sed/// property of a deterministic iteration order. The order of iteration is the 34193323Sed/// order of insertion. 35193323Sedtemplate <typename T, typename Vector = std::vector<T>, 36193323Sed typename Set = SmallSet<T, 16> > 37193323Sedclass SetVector { 38193323Sedpublic: 39193323Sed typedef T value_type; 40193323Sed typedef T key_type; 41193323Sed typedef T& reference; 42193323Sed typedef const T& const_reference; 43193323Sed typedef Set set_type; 44193323Sed typedef Vector vector_type; 45193323Sed typedef typename vector_type::const_iterator iterator; 46193323Sed typedef typename vector_type::const_iterator const_iterator; 47193323Sed typedef typename vector_type::size_type size_type; 48193323Sed 49243830Sdim /// \brief Construct an empty SetVector 50193323Sed SetVector() {} 51193323Sed 52243830Sdim /// \brief Initialize a SetVector with a range of elements 53193323Sed template<typename It> 54193323Sed SetVector(It Start, It End) { 55193323Sed insert(Start, End); 56193323Sed } 57193323Sed 58243830Sdim /// \brief Determine if the SetVector is empty or not. 59193323Sed bool empty() const { 60193323Sed return vector_.empty(); 61193323Sed } 62193323Sed 63243830Sdim /// \brief Determine the number of elements in the SetVector. 64193323Sed size_type size() const { 65193323Sed return vector_.size(); 66193323Sed } 67193323Sed 68243830Sdim /// \brief Get an iterator to the beginning of the SetVector. 69193323Sed iterator begin() { 70193323Sed return vector_.begin(); 71193323Sed } 72193323Sed 73243830Sdim /// \brief Get a const_iterator to the beginning of the SetVector. 74193323Sed const_iterator begin() const { 75193323Sed return vector_.begin(); 76193323Sed } 77193323Sed 78243830Sdim /// \brief Get an iterator to the end of the SetVector. 79193323Sed iterator end() { 80193323Sed return vector_.end(); 81193323Sed } 82193323Sed 83243830Sdim /// \brief Get a const_iterator to the end of the SetVector. 84193323Sed const_iterator end() const { 85193323Sed return vector_.end(); 86193323Sed } 87193323Sed 88243830Sdim /// \brief Return the last element of the SetVector. 89193323Sed const T &back() const { 90193323Sed assert(!empty() && "Cannot call back() on empty SetVector!"); 91193323Sed return vector_.back(); 92193323Sed } 93193323Sed 94243830Sdim /// \brief Index into the SetVector. 95193323Sed const_reference operator[](size_type n) const { 96193323Sed assert(n < vector_.size() && "SetVector access out of range!"); 97193323Sed return vector_[n]; 98193323Sed } 99193323Sed 100243830Sdim /// \brief Insert a new element into the SetVector. 101243830Sdim /// \returns true iff the element was inserted into the SetVector. 102193323Sed bool insert(const value_type &X) { 103193323Sed bool result = set_.insert(X); 104193323Sed if (result) 105193323Sed vector_.push_back(X); 106193323Sed return result; 107193323Sed } 108193323Sed 109243830Sdim /// \brief Insert a range of elements into the SetVector. 110193323Sed template<typename It> 111193323Sed void insert(It Start, It End) { 112193323Sed for (; Start != End; ++Start) 113193323Sed if (set_.insert(*Start)) 114193323Sed vector_.push_back(*Start); 115193323Sed } 116193323Sed 117243830Sdim /// \brief Remove an item from the set vector. 118218893Sdim bool remove(const value_type& X) { 119193323Sed if (set_.erase(X)) { 120193323Sed typename vector_type::iterator I = 121193323Sed std::find(vector_.begin(), vector_.end(), X); 122193323Sed assert(I != vector_.end() && "Corrupted SetVector instances!"); 123193323Sed vector_.erase(I); 124218893Sdim return true; 125193323Sed } 126218893Sdim return false; 127193323Sed } 128193323Sed 129243830Sdim /// \brief Remove items from the set vector based on a predicate function. 130243830Sdim /// 131243830Sdim /// This is intended to be equivalent to the following code, if we could 132243830Sdim /// write it: 133243830Sdim /// 134243830Sdim /// \code 135243830Sdim /// V.erase(std::remove_if(V.begin(), V.end(), P), V.end()); 136243830Sdim /// \endcode 137243830Sdim /// 138243830Sdim /// However, SetVector doesn't expose non-const iterators, making any 139243830Sdim /// algorithm like remove_if impossible to use. 140243830Sdim /// 141243830Sdim /// \returns true if any element is removed. 142243830Sdim template <typename UnaryPredicate> 143243830Sdim bool remove_if(UnaryPredicate P) { 144243830Sdim typename vector_type::iterator I 145243830Sdim = std::remove_if(vector_.begin(), vector_.end(), 146243830Sdim TestAndEraseFromSet<UnaryPredicate>(P, set_)); 147243830Sdim if (I == vector_.end()) 148243830Sdim return false; 149243830Sdim vector_.erase(I, vector_.end()); 150243830Sdim return true; 151243830Sdim } 152193323Sed 153243830Sdim 154243830Sdim /// \brief Count the number of elements of a given key in the SetVector. 155243830Sdim /// \returns 0 if the element is not in the SetVector, 1 if it is. 156193323Sed size_type count(const key_type &key) const { 157193323Sed return set_.count(key); 158193323Sed } 159193323Sed 160243830Sdim /// \brief Completely clear the SetVector 161193323Sed void clear() { 162193323Sed set_.clear(); 163193323Sed vector_.clear(); 164193323Sed } 165193323Sed 166243830Sdim /// \brief Remove the last element of the SetVector. 167193323Sed void pop_back() { 168193323Sed assert(!empty() && "Cannot remove an element from an empty SetVector!"); 169193323Sed set_.erase(back()); 170193323Sed vector_.pop_back(); 171193323Sed } 172234353Sdim 173234353Sdim T pop_back_val() { 174234353Sdim T Ret = back(); 175234353Sdim pop_back(); 176234353Sdim return Ret; 177234353Sdim } 178193323Sed 179210299Sed bool operator==(const SetVector &that) const { 180210299Sed return vector_ == that.vector_; 181210299Sed } 182210299Sed 183210299Sed bool operator!=(const SetVector &that) const { 184210299Sed return vector_ != that.vector_; 185210299Sed } 186210299Sed 187193323Sedprivate: 188243830Sdim /// \brief A wrapper predicate designed for use with std::remove_if. 189243830Sdim /// 190243830Sdim /// This predicate wraps a predicate suitable for use with std::remove_if to 191243830Sdim /// call set_.erase(x) on each element which is slated for removal. 192243830Sdim template <typename UnaryPredicate> 193243830Sdim class TestAndEraseFromSet { 194243830Sdim UnaryPredicate P; 195243830Sdim set_type &set_; 196243830Sdim 197243830Sdim public: 198243830Sdim typedef typename UnaryPredicate::argument_type argument_type; 199243830Sdim 200243830Sdim TestAndEraseFromSet(UnaryPredicate P, set_type &set_) : P(P), set_(set_) {} 201243830Sdim 202243830Sdim bool operator()(argument_type Arg) { 203243830Sdim if (P(Arg)) { 204243830Sdim set_.erase(Arg); 205243830Sdim return true; 206243830Sdim } 207243830Sdim return false; 208243830Sdim } 209243830Sdim }; 210243830Sdim 211193323Sed set_type set_; ///< The set. 212193323Sed vector_type vector_; ///< The vector. 213193323Sed}; 214193323Sed 215243830Sdim/// \brief A SetVector that performs no allocations if smaller than 216193323Sed/// a certain size. 217193323Sedtemplate <typename T, unsigned N> 218193323Sedclass SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > { 219193323Sedpublic: 220193323Sed SmallSetVector() {} 221193323Sed 222243830Sdim /// \brief Initialize a SmallSetVector with a range of elements 223193323Sed template<typename It> 224193323Sed SmallSetVector(It Start, It End) { 225193323Sed this->insert(Start, End); 226193323Sed } 227193323Sed}; 228193323Sed 229193323Sed} // End llvm namespace 230193323Sed 231193323Sed// vim: sw=2 ai 232193323Sed#endif 233