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