1 // Copyright (c) 2016 Google Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef SOURCE_OPT_ITERATOR_H_
16 #define SOURCE_OPT_ITERATOR_H_
17
18 #include <cstddef> // for ptrdiff_t
19 #include <iterator>
20 #include <memory>
21 #include <type_traits>
22 #include <utility>
23 #include <vector>
24
25 namespace spvtools {
26 namespace opt {
27
28 // An ad hoc iterator class for std::vector<std::unique_ptr<|ValueType|>>. The
29 // purpose of this iterator class is to provide transparent access to those
30 // std::unique_ptr managed elements in the vector, behaving like we are using
31 // std::vector<|ValueType|>.
32 template <typename ValueType, bool IsConst = false>
33 class UptrVectorIterator {
34 public:
35 using iterator_category = std::random_access_iterator_tag;
36 using value_type = ValueType;
37
38 using pointer = value_type*;
39 using reference = value_type&;
40 using difference_type = std::ptrdiff_t;
41
42 // Type aliases. We need to apply constness properly if |IsConst| is true.
43 using Uptr = std::unique_ptr<ValueType>;
44 using UptrVector = typename std::conditional<IsConst, const std::vector<Uptr>,
45 std::vector<Uptr>>::type;
46 using UnderlyingIterator =
47 typename std::conditional<IsConst, typename UptrVector::const_iterator,
48 typename UptrVector::iterator>::type;
49
50 // Creates a new iterator from the given |container| and its raw iterator
51 // |it|.
UptrVectorIterator(UptrVector * container,const UnderlyingIterator & it)52 UptrVectorIterator(UptrVector* container, const UnderlyingIterator& it)
53 : container_(container), iterator_(it) {}
54 UptrVectorIterator(const UptrVectorIterator&) = default;
55 UptrVectorIterator& operator=(const UptrVectorIterator&) = default;
56
57 inline UptrVectorIterator& operator++();
58 inline UptrVectorIterator operator++(int);
59 inline UptrVectorIterator& operator--();
60 inline UptrVectorIterator operator--(int);
61
62 reference operator*() const { return **iterator_; }
63 pointer operator->() { return (*iterator_).get(); }
64 reference operator[](ptrdiff_t index) { return **(iterator_ + index); }
65
66 inline bool operator==(const UptrVectorIterator& that) const;
67 inline bool operator!=(const UptrVectorIterator& that) const;
68
69 inline ptrdiff_t operator-(const UptrVectorIterator& that) const;
70 inline bool operator<(const UptrVectorIterator& that) const;
71
72 // Inserts the given |value| to the position pointed to by this iterator
73 // and returns an iterator to the newly iserted |value|.
74 // If the underlying vector changes capacity, all previous iterators will be
75 // invalidated. Otherwise, those previous iterators pointing to after the
76 // insertion point will be invalidated.
77 template <bool IsConstForMethod = IsConst>
78 inline typename std::enable_if<!IsConstForMethod, UptrVectorIterator>::type
79 InsertBefore(Uptr value);
80
81 // Inserts the given |valueVector| to the position pointed to by this iterator
82 // and returns an iterator to the first newly inserted value.
83 // If the underlying vector changes capacity, all previous iterators will be
84 // invalidated. Otherwise, those previous iterators pointing to after the
85 // insertion point will be invalidated.
86 template <bool IsConstForMethod = IsConst>
87 inline typename std::enable_if<!IsConstForMethod, UptrVectorIterator>::type
88 InsertBefore(UptrVector* valueVector);
89
90 // Erases the value at the position pointed to by this iterator
91 // and returns an iterator to the following value.
92 // If the underlying vector changes capacity, all previous iterators will be
93 // invalidated. Otherwise, those previous iterators pointing to after the
94 // erasure point will be invalidated.
95 template <bool IsConstForMethod = IsConst>
96 inline typename std::enable_if<!IsConstForMethod, UptrVectorIterator>::type
97 Erase();
98
99 // Returns the underlying iterator.
Get()100 UnderlyingIterator Get() const { return iterator_; }
101
102 // Returns a valid end iterator for the underlying container.
End()103 UptrVectorIterator End() const {
104 return UptrVectorIterator(container_, container_->end());
105 }
106
107 private:
108 UptrVector* container_; // The container we are manipulating.
109 UnderlyingIterator iterator_; // The raw iterator from the container.
110 };
111
112 // Handy class for a (begin, end) iterator pair.
113 template <typename IteratorType>
114 class IteratorRange {
115 public:
IteratorRange(const IteratorType & b,const IteratorType & e)116 IteratorRange(const IteratorType& b, const IteratorType& e)
117 : begin_(b), end_(e) {}
IteratorRange(IteratorType && b,IteratorType && e)118 IteratorRange(IteratorType&& b, IteratorType&& e)
119 : begin_(std::move(b)), end_(std::move(e)) {}
120
begin()121 IteratorType begin() const { return begin_; }
end()122 IteratorType end() const { return end_; }
123
empty()124 bool empty() const { return begin_ == end_; }
size()125 size_t size() const { return end_ - begin_; }
126
127 private:
128 IteratorType begin_;
129 IteratorType end_;
130 };
131
132 // Returns a (begin, end) iterator pair for the given iterators.
133 // The iterators must belong to the same container.
134 template <typename IteratorType>
make_range(const IteratorType & begin,const IteratorType & end)135 inline IteratorRange<IteratorType> make_range(const IteratorType& begin,
136 const IteratorType& end) {
137 return {begin, end};
138 }
139
140 // Returns a (begin, end) iterator pair for the given iterators.
141 // The iterators must belong to the same container.
142 template <typename IteratorType>
make_range(IteratorType && begin,IteratorType && end)143 inline IteratorRange<IteratorType> make_range(IteratorType&& begin,
144 IteratorType&& end) {
145 return {std::forward<IteratorType>(begin), std::forward<IteratorType>(end)};
146 }
147
148 // Returns a (begin, end) iterator pair for the given container.
149 template <typename ValueType,
150 class IteratorType = UptrVectorIterator<ValueType>>
make_range(std::vector<std::unique_ptr<ValueType>> & container)151 inline IteratorRange<IteratorType> make_range(
152 std::vector<std::unique_ptr<ValueType>>& container) {
153 return {IteratorType(&container, container.begin()),
154 IteratorType(&container, container.end())};
155 }
156
157 // Returns a const (begin, end) iterator pair for the given container.
158 template <typename ValueType,
159 class IteratorType = UptrVectorIterator<ValueType, true>>
make_const_range(const std::vector<std::unique_ptr<ValueType>> & container)160 inline IteratorRange<IteratorType> make_const_range(
161 const std::vector<std::unique_ptr<ValueType>>& container) {
162 return {IteratorType(&container, container.cbegin()),
163 IteratorType(&container, container.cend())};
164 }
165
166 // Wrapping iterator class that only consider elements that satisfy the given
167 // predicate |Predicate|. When moving to the next element of the iterator, the
168 // FilterIterator will iterate over the range until it finds an element that
169 // satisfies |Predicate| or reaches the end of the iterator.
170 //
171 // Currently this iterator is always an input iterator.
172 template <typename SubIterator, typename Predicate>
173 class FilterIterator {
174 public:
175 // Iterator interface.
176 using iterator_category = typename SubIterator::iterator_category;
177 using value_type = typename SubIterator::value_type;
178 using pointer = typename SubIterator::pointer;
179 using reference = typename SubIterator::reference;
180 using difference_type = typename SubIterator::difference_type;
181
182 using Range = IteratorRange<FilterIterator>;
183
FilterIterator(const IteratorRange<SubIterator> & iteration_range,Predicate predicate)184 FilterIterator(const IteratorRange<SubIterator>& iteration_range,
185 Predicate predicate)
186 : cur_(iteration_range.begin()),
187 end_(iteration_range.end()),
188 predicate_(predicate) {
189 if (!IsPredicateSatisfied()) {
190 MoveToNextPosition();
191 }
192 }
193
FilterIterator(const SubIterator & end,Predicate predicate)194 FilterIterator(const SubIterator& end, Predicate predicate)
195 : FilterIterator({end, end}, predicate) {}
196
197 inline FilterIterator& operator++() {
198 MoveToNextPosition();
199 return *this;
200 }
201 inline FilterIterator operator++(int) {
202 FilterIterator old = *this;
203 MoveToNextPosition();
204 return old;
205 }
206
207 reference operator*() const { return *cur_; }
208 pointer operator->() { return &*cur_; }
209
210 inline bool operator==(const FilterIterator& rhs) const {
211 return cur_ == rhs.cur_ && end_ == rhs.end_;
212 }
213 inline bool operator!=(const FilterIterator& rhs) const {
214 return !(*this == rhs);
215 }
216
217 // Returns the underlying iterator.
Get()218 SubIterator Get() const { return cur_; }
219
220 // Returns the sentinel iterator.
GetEnd()221 FilterIterator GetEnd() const { return FilterIterator(end_, predicate_); }
222
223 private:
224 // Returns true if the predicate is satisfied or the current iterator reached
225 // the end.
IsPredicateSatisfied()226 bool IsPredicateSatisfied() { return cur_ == end_ || predicate_(*cur_); }
227
MoveToNextPosition()228 void MoveToNextPosition() {
229 if (cur_ == end_) return;
230
231 do {
232 ++cur_;
233 } while (!IsPredicateSatisfied());
234 }
235
236 SubIterator cur_;
237 SubIterator end_;
238 Predicate predicate_;
239 };
240
241 template <typename SubIterator, typename Predicate>
MakeFilterIterator(const IteratorRange<SubIterator> & sub_iterator_range,Predicate predicate)242 FilterIterator<SubIterator, Predicate> MakeFilterIterator(
243 const IteratorRange<SubIterator>& sub_iterator_range, Predicate predicate) {
244 return FilterIterator<SubIterator, Predicate>(sub_iterator_range, predicate);
245 }
246
247 template <typename SubIterator, typename Predicate>
MakeFilterIterator(const SubIterator & begin,const SubIterator & end,Predicate predicate)248 FilterIterator<SubIterator, Predicate> MakeFilterIterator(
249 const SubIterator& begin, const SubIterator& end, Predicate predicate) {
250 return MakeFilterIterator(make_range(begin, end), predicate);
251 }
252
253 template <typename SubIterator, typename Predicate>
MakeFilterIteratorRange(const SubIterator & begin,const SubIterator & end,Predicate predicate)254 typename FilterIterator<SubIterator, Predicate>::Range MakeFilterIteratorRange(
255 const SubIterator& begin, const SubIterator& end, Predicate predicate) {
256 return typename FilterIterator<SubIterator, Predicate>::Range(
257 MakeFilterIterator(begin, end, predicate),
258 MakeFilterIterator(end, end, predicate));
259 }
260
261 template <typename VT, bool IC>
262 inline UptrVectorIterator<VT, IC>& UptrVectorIterator<VT, IC>::operator++() {
263 ++iterator_;
264 return *this;
265 }
266
267 template <typename VT, bool IC>
268 inline UptrVectorIterator<VT, IC> UptrVectorIterator<VT, IC>::operator++(int) {
269 auto it = *this;
270 ++(*this);
271 return it;
272 }
273
274 template <typename VT, bool IC>
275 inline UptrVectorIterator<VT, IC>& UptrVectorIterator<VT, IC>::operator--() {
276 --iterator_;
277 return *this;
278 }
279
280 template <typename VT, bool IC>
281 inline UptrVectorIterator<VT, IC> UptrVectorIterator<VT, IC>::operator--(int) {
282 auto it = *this;
283 --(*this);
284 return it;
285 }
286
287 template <typename VT, bool IC>
288 inline bool UptrVectorIterator<VT, IC>::operator==(
289 const UptrVectorIterator& that) const {
290 return container_ == that.container_ && iterator_ == that.iterator_;
291 }
292
293 template <typename VT, bool IC>
294 inline bool UptrVectorIterator<VT, IC>::operator!=(
295 const UptrVectorIterator& that) const {
296 return !(*this == that);
297 }
298
299 template <typename VT, bool IC>
300 inline ptrdiff_t UptrVectorIterator<VT, IC>::operator-(
301 const UptrVectorIterator& that) const {
302 assert(container_ == that.container_);
303 return iterator_ - that.iterator_;
304 }
305
306 template <typename VT, bool IC>
307 inline bool UptrVectorIterator<VT, IC>::operator<(
308 const UptrVectorIterator& that) const {
309 assert(container_ == that.container_);
310 return iterator_ < that.iterator_;
311 }
312
313 template <typename VT, bool IC>
314 template <bool IsConstForMethod>
315 inline
316 typename std::enable_if<!IsConstForMethod, UptrVectorIterator<VT, IC>>::type
InsertBefore(Uptr value)317 UptrVectorIterator<VT, IC>::InsertBefore(Uptr value) {
318 auto index = iterator_ - container_->begin();
319 container_->insert(iterator_, std::move(value));
320 return UptrVectorIterator(container_, container_->begin() + index);
321 }
322
323 template <typename VT, bool IC>
324 template <bool IsConstForMethod>
325 inline
326 typename std::enable_if<!IsConstForMethod, UptrVectorIterator<VT, IC>>::type
InsertBefore(UptrVector * values)327 UptrVectorIterator<VT, IC>::InsertBefore(UptrVector* values) {
328 const auto pos = iterator_ - container_->begin();
329 const auto origsz = container_->size();
330 container_->resize(origsz + values->size());
331 std::move_backward(container_->begin() + pos, container_->begin() + origsz,
332 container_->end());
333 std::move(values->begin(), values->end(), container_->begin() + pos);
334 return UptrVectorIterator(container_, container_->begin() + pos);
335 }
336
337 template <typename VT, bool IC>
338 template <bool IsConstForMethod>
339 inline
340 typename std::enable_if<!IsConstForMethod, UptrVectorIterator<VT, IC>>::type
Erase()341 UptrVectorIterator<VT, IC>::Erase() {
342 auto index = iterator_ - container_->begin();
343 (void)container_->erase(iterator_);
344 return UptrVectorIterator(container_, container_->begin() + index);
345 }
346
347 } // namespace opt
348 } // namespace spvtools
349
350 #endif // SOURCE_OPT_ITERATOR_H_
351