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/ArrayRef.h"
24#include "llvm/ADT/DenseSet.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/Support/Compiler.h"
27#include <algorithm>
28#include <cassert>
29#include <iterator>
30#include <vector>
31
32namespace llvm {
33
34/// \brief A vector that has set insertion semantics.
35///
36/// This adapter class provides a way to keep a set of things that also has the
37/// property of a deterministic iteration order. The order of iteration is the
38/// order of insertion.
39template <typename T, typename Vector = std::vector<T>,
40          typename Set = DenseSet<T>>
41class SetVector {
42public:
43  using value_type = T;
44  using key_type = T;
45  using reference = T&;
46  using const_reference = const T&;
47  using set_type = Set;
48  using vector_type = Vector;
49  using iterator = typename vector_type::const_iterator;
50  using const_iterator = typename vector_type::const_iterator;
51  using reverse_iterator = typename vector_type::const_reverse_iterator;
52  using const_reverse_iterator = typename vector_type::const_reverse_iterator;
53  using size_type = typename vector_type::size_type;
54
55  /// \brief Construct an empty SetVector
56  SetVector() = default;
57
58  /// \brief Initialize a SetVector with a range of elements
59  template<typename It>
60  SetVector(It Start, It End) {
61    insert(Start, End);
62  }
63
64  ArrayRef<T> getArrayRef() const { return vector_; }
65
66  /// Clear the SetVector and return the underlying vector.
67  Vector takeVector() {
68    set_.clear();
69    return std::move(vector_);
70  }
71
72  /// \brief Determine if the SetVector is empty or not.
73  bool empty() const {
74    return vector_.empty();
75  }
76
77  /// \brief Determine the number of elements in the SetVector.
78  size_type size() const {
79    return vector_.size();
80  }
81
82  /// \brief Get an iterator to the beginning of the SetVector.
83  iterator begin() {
84    return vector_.begin();
85  }
86
87  /// \brief Get a const_iterator to the beginning of the SetVector.
88  const_iterator begin() const {
89    return vector_.begin();
90  }
91
92  /// \brief Get an iterator to the end of the SetVector.
93  iterator end() {
94    return vector_.end();
95  }
96
97  /// \brief Get a const_iterator to the end of the SetVector.
98  const_iterator end() const {
99    return vector_.end();
100  }
101
102  /// \brief Get an reverse_iterator to the end of the SetVector.
103  reverse_iterator rbegin() {
104    return vector_.rbegin();
105  }
106
107  /// \brief Get a const_reverse_iterator to the end of the SetVector.
108  const_reverse_iterator rbegin() const {
109    return vector_.rbegin();
110  }
111
112  /// \brief Get a reverse_iterator to the beginning of the SetVector.
113  reverse_iterator rend() {
114    return vector_.rend();
115  }
116
117  /// \brief Get a const_reverse_iterator to the beginning of the SetVector.
118  const_reverse_iterator rend() const {
119    return vector_.rend();
120  }
121
122  /// \brief Return the first element of the SetVector.
123  const T &front() const {
124    assert(!empty() && "Cannot call front() on empty SetVector!");
125    return vector_.front();
126  }
127
128  /// \brief Return the last element of the SetVector.
129  const T &back() const {
130    assert(!empty() && "Cannot call back() on empty SetVector!");
131    return vector_.back();
132  }
133
134  /// \brief Index into the SetVector.
135  const_reference operator[](size_type n) const {
136    assert(n < vector_.size() && "SetVector access out of range!");
137    return vector_[n];
138  }
139
140  /// \brief Insert a new element into the SetVector.
141  /// \returns true if the element was inserted into the SetVector.
142  bool insert(const value_type &X) {
143    bool result = set_.insert(X).second;
144    if (result)
145      vector_.push_back(X);
146    return result;
147  }
148
149  /// \brief Insert a range of elements into the SetVector.
150  template<typename It>
151  void insert(It Start, It End) {
152    for (; Start != End; ++Start)
153      if (set_.insert(*Start).second)
154        vector_.push_back(*Start);
155  }
156
157  /// \brief Remove an item from the set vector.
158  bool remove(const value_type& X) {
159    if (set_.erase(X)) {
160      typename vector_type::iterator I = find(vector_, X);
161      assert(I != vector_.end() && "Corrupted SetVector instances!");
162      vector_.erase(I);
163      return true;
164    }
165    return false;
166  }
167
168  /// Erase a single element from the set vector.
169  /// \returns an iterator pointing to the next element that followed the
170  /// element erased. This is the end of the SetVector if the last element is
171  /// erased.
172  iterator erase(iterator I) {
173    const key_type &V = *I;
174    assert(set_.count(V) && "Corrupted SetVector instances!");
175    set_.erase(V);
176
177    // FIXME: No need to use the non-const iterator when built with
178    // std:vector.erase(const_iterator) as defined in C++11. This is for
179    // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
180    auto NI = vector_.begin();
181    std::advance(NI, std::distance<iterator>(NI, I));
182
183    return vector_.erase(NI);
184  }
185
186  /// \brief Remove items from the set vector based on a predicate function.
187  ///
188  /// This is intended to be equivalent to the following code, if we could
189  /// write it:
190  ///
191  /// \code
192  ///   V.erase(remove_if(V, P), V.end());
193  /// \endcode
194  ///
195  /// However, SetVector doesn't expose non-const iterators, making any
196  /// algorithm like remove_if impossible to use.
197  ///
198  /// \returns true if any element is removed.
199  template <typename UnaryPredicate>
200  bool remove_if(UnaryPredicate P) {
201    typename vector_type::iterator I =
202        llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
203    if (I == vector_.end())
204      return false;
205    vector_.erase(I, vector_.end());
206    return true;
207  }
208
209  /// \brief Count the number of elements of a given key in the SetVector.
210  /// \returns 0 if the element is not in the SetVector, 1 if it is.
211  size_type count(const key_type &key) const {
212    return set_.count(key);
213  }
214
215  /// \brief Completely clear the SetVector
216  void clear() {
217    set_.clear();
218    vector_.clear();
219  }
220
221  /// \brief Remove the last element of the SetVector.
222  void pop_back() {
223    assert(!empty() && "Cannot remove an element from an empty SetVector!");
224    set_.erase(back());
225    vector_.pop_back();
226  }
227
228  LLVM_NODISCARD T pop_back_val() {
229    T Ret = back();
230    pop_back();
231    return Ret;
232  }
233
234  bool operator==(const SetVector &that) const {
235    return vector_ == that.vector_;
236  }
237
238  bool operator!=(const SetVector &that) const {
239    return vector_ != that.vector_;
240  }
241
242  /// \brief Compute This := This u S, return whether 'This' changed.
243  /// TODO: We should be able to use set_union from SetOperations.h, but
244  ///       SetVector interface is inconsistent with DenseSet.
245  template <class STy>
246  bool set_union(const STy &S) {
247    bool Changed = false;
248
249    for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
250         ++SI)
251      if (insert(*SI))
252        Changed = true;
253
254    return Changed;
255  }
256
257  /// \brief Compute This := This - B
258  /// TODO: We should be able to use set_subtract from SetOperations.h, but
259  ///       SetVector interface is inconsistent with DenseSet.
260  template <class STy>
261  void set_subtract(const STy &S) {
262    for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
263         ++SI)
264      remove(*SI);
265  }
266
267private:
268  /// \brief A wrapper predicate designed for use with std::remove_if.
269  ///
270  /// This predicate wraps a predicate suitable for use with std::remove_if to
271  /// call set_.erase(x) on each element which is slated for removal.
272  template <typename UnaryPredicate>
273  class TestAndEraseFromSet {
274    UnaryPredicate P;
275    set_type &set_;
276
277  public:
278    TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
279        : P(std::move(P)), set_(set_) {}
280
281    template <typename ArgumentT>
282    bool operator()(const ArgumentT &Arg) {
283      if (P(Arg)) {
284        set_.erase(Arg);
285        return true;
286      }
287      return false;
288    }
289  };
290
291  set_type set_;         ///< The set.
292  vector_type vector_;   ///< The vector.
293};
294
295/// \brief A SetVector that performs no allocations if smaller than
296/// a certain size.
297template <typename T, unsigned N>
298class SmallSetVector
299    : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
300public:
301  SmallSetVector() = default;
302
303  /// \brief Initialize a SmallSetVector with a range of elements
304  template<typename It>
305  SmallSetVector(It Start, It End) {
306    this->insert(Start, End);
307  }
308};
309
310} // end namespace llvm
311
312#endif // LLVM_ADT_SETVECTOR_H
313