1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements a set that has insertion order iteration 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// characteristics. This is useful for keeping a set of things that need to be 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// visited later but in a deterministic order (insertion order). The interface 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// is purposefully minimal. 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file defines SetVector and SmallSetVector, which performs no allocations 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// if the SetVector has less than a certain number of elements. 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ADT_SETVECTOR_H 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ADT_SETVECTOR_H 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallSet.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <algorithm> 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cassert> 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <vector> 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This adapter class provides a way to keep a set of things that also has the 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// property of a deterministic iteration order. The order of iteration is the 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// order of insertion. 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// @brief A vector that has set insertion semantics. 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <typename T, typename Vector = std::vector<T>, 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename Set = SmallSet<T, 16> > 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass SetVector { 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef T value_type; 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef T key_type; 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef T& reference; 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef const T& const_reference; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef Set set_type; 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef Vector vector_type; 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename vector_type::const_iterator iterator; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename vector_type::const_iterator const_iterator; 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename vector_type::size_type size_type; 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Construct an empty SetVector 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SetVector() {} 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Initialize a SetVector with a range of elements 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename It> 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SetVector(It Start, It End) { 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman insert(Start, End); 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Determine if the SetVector is empty or not. 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool empty() const { 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_.empty(); 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Determine the number of elements in the SetVector. 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman size_type size() const { 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_.size(); 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get an iterator to the beginning of the SetVector. 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator begin() { 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_.begin(); 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get a const_iterator to the beginning of the SetVector. 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator begin() const { 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_.begin(); 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get an iterator to the end of the SetVector. 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator end() { 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_.end(); 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Get a const_iterator to the end of the SetVector. 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator end() const { 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_.end(); 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Return the last element of the SetVector. 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const T &back() const { 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!empty() && "Cannot call back() on empty SetVector!"); 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_.back(); 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Index into the SetVector. 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_reference operator[](size_type n) const { 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(n < vector_.size() && "SetVector access out of range!"); 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_[n]; 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @returns true iff the element was inserted into the SetVector. 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Insert a new element into the SetVector. 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool insert(const value_type &X) { 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool result = set_.insert(X); 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (result) 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman vector_.push_back(X); 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return result; 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Insert a range of elements into the SetVector. 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename It> 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void insert(It Start, It End) { 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (; Start != End; ++Start) 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (set_.insert(*Start)) 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman vector_.push_back(*Start); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Remove an item from the set vector. 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool remove(const value_type& X) { 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (set_.erase(X)) { 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename vector_type::iterator I = 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::find(vector_.begin(), vector_.end(), X); 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I != vector_.end() && "Corrupted SetVector instances!"); 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman vector_.erase(I); 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @returns 0 if the element is not in the SetVector, 1 if it is. 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Count the number of elements of a given key in the SetVector. 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman size_type count(const key_type &key) const { 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return set_.count(key); 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Completely clear the SetVector 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void clear() { 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman set_.clear(); 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman vector_.clear(); 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Remove the last element of the SetVector. 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void pop_back() { 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!empty() && "Cannot remove an element from an empty SetVector!"); 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman set_.erase(back()); 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman vector_.pop_back(); 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator==(const SetVector &that) const { 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_ == that.vector_; 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator!=(const SetVector &that) const { 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return vector_ != that.vector_; 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman set_type set_; ///< The set. 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman vector_type vector_; ///< The vector. 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// SmallSetVector - A SetVector that performs no allocations if smaller than 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// a certain size. 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <typename T, unsigned N> 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > { 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSetVector() {} 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Initialize a SmallSetVector with a range of elements 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename It> 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSetVector(It Start, It End) { 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman this->insert(Start, End); 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End llvm namespace 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// vim: sw=2 ai 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 179