1 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a set that has insertion order iteration
11 // characteristics. This is useful for keeping a set of things that need to be
12 // visited later but in a deterministic order (insertion order). The interface
13 // is purposefully minimal.
14 //
15 // This file defines SetVector and SmallSetVector, which performs no allocations
16 // if the SetVector has less than a certain number of elements.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_ADT_SETVECTOR_H
21 #define LLVM_ADT_SETVECTOR_H
22 
23 #include "llvm/ADT/SmallSet.h"
24 #include <algorithm>
25 #include <cassert>
26 #include <vector>
27 
28 namespace llvm {
29 
30 /// This adapter class provides a way to keep a set of things that also has the
31 /// property of a deterministic iteration order. The order of iteration is the
32 /// order of insertion.
33 /// @brief A vector that has set insertion semantics.
34 template <typename T, typename Vector = std::vector<T>,
35                       typename Set = SmallSet<T, 16> >
36 class SetVector {
37 public:
38   typedef T value_type;
39   typedef T key_type;
40   typedef T& reference;
41   typedef const T& const_reference;
42   typedef Set set_type;
43   typedef Vector vector_type;
44   typedef typename vector_type::const_iterator iterator;
45   typedef typename vector_type::const_iterator const_iterator;
46   typedef typename vector_type::size_type size_type;
47 
48   /// @brief Construct an empty SetVector
SetVector()49   SetVector() {}
50 
51   /// @brief Initialize a SetVector with a range of elements
52   template<typename It>
SetVector(It Start,It End)53   SetVector(It Start, It End) {
54     insert(Start, End);
55   }
56 
57   /// @brief Determine if the SetVector is empty or not.
empty()58   bool empty() const {
59     return vector_.empty();
60   }
61 
62   /// @brief Determine the number of elements in the SetVector.
size()63   size_type size() const {
64     return vector_.size();
65   }
66 
67   /// @brief Get an iterator to the beginning of the SetVector.
begin()68   iterator begin() {
69     return vector_.begin();
70   }
71 
72   /// @brief Get a const_iterator to the beginning of the SetVector.
begin()73   const_iterator begin() const {
74     return vector_.begin();
75   }
76 
77   /// @brief Get an iterator to the end of the SetVector.
end()78   iterator end() {
79     return vector_.end();
80   }
81 
82   /// @brief Get a const_iterator to the end of the SetVector.
end()83   const_iterator end() const {
84     return vector_.end();
85   }
86 
87   /// @brief Return the last element of the SetVector.
back()88   const T &back() const {
89     assert(!empty() && "Cannot call back() on empty SetVector!");
90     return vector_.back();
91   }
92 
93   /// @brief Index into the SetVector.
94   const_reference operator[](size_type n) const {
95     assert(n < vector_.size() && "SetVector access out of range!");
96     return vector_[n];
97   }
98 
99   /// @returns true iff the element was inserted into the SetVector.
100   /// @brief Insert a new element into the SetVector.
insert(const value_type & X)101   bool insert(const value_type &X) {
102     bool result = set_.insert(X);
103     if (result)
104       vector_.push_back(X);
105     return result;
106   }
107 
108   /// @brief Insert a range of elements into the SetVector.
109   template<typename It>
insert(It Start,It End)110   void insert(It Start, It End) {
111     for (; Start != End; ++Start)
112       if (set_.insert(*Start))
113         vector_.push_back(*Start);
114   }
115 
116   /// @brief Remove an item from the set vector.
remove(const value_type & X)117   bool remove(const value_type& X) {
118     if (set_.erase(X)) {
119       typename vector_type::iterator I =
120         std::find(vector_.begin(), vector_.end(), X);
121       assert(I != vector_.end() && "Corrupted SetVector instances!");
122       vector_.erase(I);
123       return true;
124     }
125     return false;
126   }
127 
128 
129   /// @returns 0 if the element is not in the SetVector, 1 if it is.
130   /// @brief Count the number of elements of a given key in the SetVector.
count(const key_type & key)131   size_type count(const key_type &key) const {
132     return set_.count(key);
133   }
134 
135   /// @brief Completely clear the SetVector
clear()136   void clear() {
137     set_.clear();
138     vector_.clear();
139   }
140 
141   /// @brief Remove the last element of the SetVector.
pop_back()142   void pop_back() {
143     assert(!empty() && "Cannot remove an element from an empty SetVector!");
144     set_.erase(back());
145     vector_.pop_back();
146   }
147 
148   bool operator==(const SetVector &that) const {
149     return vector_ == that.vector_;
150   }
151 
152   bool operator!=(const SetVector &that) const {
153     return vector_ != that.vector_;
154   }
155 
156 private:
157   set_type set_;         ///< The set.
158   vector_type vector_;   ///< The vector.
159 };
160 
161 /// SmallSetVector - A SetVector that performs no allocations if smaller than
162 /// a certain size.
163 template <typename T, unsigned N>
164 class SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > {
165 public:
SmallSetVector()166   SmallSetVector() {}
167 
168   /// @brief Initialize a SmallSetVector with a range of elements
169   template<typename It>
SmallSetVector(It Start,It End)170   SmallSetVector(It Start, It End) {
171     this->insert(Start, End);
172   }
173 };
174 
175 } // End llvm namespace
176 
177 // vim: sw=2 ai
178 #endif
179