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