SetVector.h revision 234353
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 30193323Sed/// This adapter class provides a way to keep a set of things that also has the 31193323Sed/// property of a deterministic iteration order. The order of iteration is the 32193323Sed/// order of insertion. 33193323Sed/// @brief A vector that has set insertion semantics. 34193323Sedtemplate <typename T, typename Vector = std::vector<T>, 35193323Sed typename Set = SmallSet<T, 16> > 36193323Sedclass SetVector { 37193323Sedpublic: 38193323Sed typedef T value_type; 39193323Sed typedef T key_type; 40193323Sed typedef T& reference; 41193323Sed typedef const T& const_reference; 42193323Sed typedef Set set_type; 43193323Sed typedef Vector vector_type; 44193323Sed typedef typename vector_type::const_iterator iterator; 45193323Sed typedef typename vector_type::const_iterator const_iterator; 46193323Sed typedef typename vector_type::size_type size_type; 47193323Sed 48193323Sed /// @brief Construct an empty SetVector 49193323Sed SetVector() {} 50193323Sed 51193323Sed /// @brief Initialize a SetVector with a range of elements 52193323Sed template<typename It> 53193323Sed SetVector(It Start, It End) { 54193323Sed insert(Start, End); 55193323Sed } 56193323Sed 57193323Sed /// @brief Determine if the SetVector is empty or not. 58193323Sed bool empty() const { 59193323Sed return vector_.empty(); 60193323Sed } 61193323Sed 62193323Sed /// @brief Determine the number of elements in the SetVector. 63193323Sed size_type size() const { 64193323Sed return vector_.size(); 65193323Sed } 66193323Sed 67193323Sed /// @brief Get an iterator to the beginning of the SetVector. 68193323Sed iterator begin() { 69193323Sed return vector_.begin(); 70193323Sed } 71193323Sed 72193323Sed /// @brief Get a const_iterator to the beginning of the SetVector. 73193323Sed const_iterator begin() const { 74193323Sed return vector_.begin(); 75193323Sed } 76193323Sed 77193323Sed /// @brief Get an iterator to the end of the SetVector. 78193323Sed iterator end() { 79193323Sed return vector_.end(); 80193323Sed } 81193323Sed 82193323Sed /// @brief Get a const_iterator to the end of the SetVector. 83193323Sed const_iterator end() const { 84193323Sed return vector_.end(); 85193323Sed } 86193323Sed 87193323Sed /// @brief Return the last element of the SetVector. 88193323Sed const T &back() const { 89193323Sed assert(!empty() && "Cannot call back() on empty SetVector!"); 90193323Sed return vector_.back(); 91193323Sed } 92193323Sed 93193323Sed /// @brief Index into the SetVector. 94193323Sed const_reference operator[](size_type n) const { 95193323Sed assert(n < vector_.size() && "SetVector access out of range!"); 96193323Sed return vector_[n]; 97193323Sed } 98193323Sed 99193323Sed /// @returns true iff the element was inserted into the SetVector. 100193323Sed /// @brief Insert a new element into the SetVector. 101193323Sed bool insert(const value_type &X) { 102193323Sed bool result = set_.insert(X); 103193323Sed if (result) 104193323Sed vector_.push_back(X); 105193323Sed return result; 106193323Sed } 107193323Sed 108193323Sed /// @brief Insert a range of elements into the SetVector. 109193323Sed template<typename It> 110193323Sed void insert(It Start, It End) { 111193323Sed for (; Start != End; ++Start) 112193323Sed if (set_.insert(*Start)) 113193323Sed vector_.push_back(*Start); 114193323Sed } 115193323Sed 116193323Sed /// @brief Remove an item from the set vector. 117218893Sdim bool remove(const value_type& X) { 118193323Sed if (set_.erase(X)) { 119193323Sed typename vector_type::iterator I = 120193323Sed std::find(vector_.begin(), vector_.end(), X); 121193323Sed assert(I != vector_.end() && "Corrupted SetVector instances!"); 122193323Sed vector_.erase(I); 123218893Sdim return true; 124193323Sed } 125218893Sdim return false; 126193323Sed } 127193323Sed 128193323Sed 129193323Sed /// @returns 0 if the element is not in the SetVector, 1 if it is. 130193323Sed /// @brief Count the number of elements of a given key in the SetVector. 131193323Sed size_type count(const key_type &key) const { 132193323Sed return set_.count(key); 133193323Sed } 134193323Sed 135193323Sed /// @brief Completely clear the SetVector 136193323Sed void clear() { 137193323Sed set_.clear(); 138193323Sed vector_.clear(); 139193323Sed } 140193323Sed 141193323Sed /// @brief Remove the last element of the SetVector. 142193323Sed void pop_back() { 143193323Sed assert(!empty() && "Cannot remove an element from an empty SetVector!"); 144193323Sed set_.erase(back()); 145193323Sed vector_.pop_back(); 146193323Sed } 147234353Sdim 148234353Sdim T pop_back_val() { 149234353Sdim T Ret = back(); 150234353Sdim pop_back(); 151234353Sdim return Ret; 152234353Sdim } 153193323Sed 154210299Sed bool operator==(const SetVector &that) const { 155210299Sed return vector_ == that.vector_; 156210299Sed } 157210299Sed 158210299Sed bool operator!=(const SetVector &that) const { 159210299Sed return vector_ != that.vector_; 160210299Sed } 161210299Sed 162193323Sedprivate: 163193323Sed set_type set_; ///< The set. 164193323Sed vector_type vector_; ///< The vector. 165193323Sed}; 166193323Sed 167193323Sed/// SmallSetVector - A SetVector that performs no allocations if smaller than 168193323Sed/// a certain size. 169193323Sedtemplate <typename T, unsigned N> 170193323Sedclass SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > { 171193323Sedpublic: 172193323Sed SmallSetVector() {} 173193323Sed 174193323Sed /// @brief Initialize a SmallSetVector with a range of elements 175193323Sed template<typename It> 176193323Sed SmallSetVector(It Start, It End) { 177193323Sed this->insert(Start, End); 178193323Sed } 179193323Sed}; 180193323Sed 181193323Sed} // End llvm namespace 182193323Sed 183193323Sed// vim: sw=2 ai 184193323Sed#endif 185