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