1 //===----------------------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef ITERATORS_H
11 #define ITERATORS_H
12
13 #include <iterator>
14 #include <stdexcept>
15 #include <cstddef>
16 #include <cassert>
17
18 #include "test_macros.h"
19
20 #if TEST_STD_VER >= 11
21 #define DELETE_FUNCTION = delete
22 #else
23 #define DELETE_FUNCTION
24 #endif
25
26 template <class It>
27 class output_iterator
28 {
29 It it_;
30
31 template <class U> friend class output_iterator;
32 public:
33 typedef std::output_iterator_tag iterator_category;
34 typedef void value_type;
35 typedef typename std::iterator_traits<It>::difference_type difference_type;
36 typedef It pointer;
37 typedef typename std::iterator_traits<It>::reference reference;
38
base()39 It base() const {return it_;}
40
output_iterator()41 output_iterator () {}
output_iterator(It it)42 explicit output_iterator(It it) : it_(it) {}
43 template <class U>
output_iterator(const output_iterator<U> & u)44 output_iterator(const output_iterator<U>& u) :it_(u.it_) {}
45
46 reference operator*() const {return *it_;}
47
48 output_iterator& operator++() {++it_; return *this;}
49 output_iterator operator++(int)
50 {output_iterator tmp(*this); ++(*this); return tmp;}
51
52 template <class T>
53 void operator,(T const &) DELETE_FUNCTION;
54 };
55
56 template <class It,
57 class ItTraits = It>
58 class input_iterator
59 {
60 typedef std::iterator_traits<ItTraits> Traits;
61 It it_;
62
63 template <class U, class T> friend class input_iterator;
64 public:
65 typedef std::input_iterator_tag iterator_category;
66 typedef typename Traits::value_type value_type;
67 typedef typename Traits::difference_type difference_type;
68 typedef It pointer;
69 typedef typename Traits::reference reference;
70
base()71 TEST_CONSTEXPR_CXX14 It base() const {return it_;}
72
input_iterator()73 TEST_CONSTEXPR_CXX14 input_iterator() : it_() {}
input_iterator(It it)74 explicit TEST_CONSTEXPR_CXX14 input_iterator(It it) : it_(it) {}
75 template <class U, class T>
input_iterator(const input_iterator<U,T> & u)76 TEST_CONSTEXPR_CXX14 input_iterator(const input_iterator<U, T>& u) :it_(u.it_) {}
77
78 TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
79 TEST_CONSTEXPR_CXX14 pointer operator->() const {return it_;}
80
81 TEST_CONSTEXPR_CXX14 input_iterator& operator++() {++it_; return *this;}
82 TEST_CONSTEXPR_CXX14 input_iterator operator++(int)
83 {input_iterator tmp(*this); ++(*this); return tmp;}
84
85 friend TEST_CONSTEXPR_CXX14 bool operator==(const input_iterator& x, const input_iterator& y)
86 {return x.it_ == y.it_;}
87 friend TEST_CONSTEXPR_CXX14 bool operator!=(const input_iterator& x, const input_iterator& y)
88 {return !(x == y);}
89
90 template <class T>
91 void operator,(T const &) DELETE_FUNCTION;
92 };
93
94 template <class T, class TV, class U, class UV>
95 inline
96 bool
97 operator==(const input_iterator<T, TV>& x, const input_iterator<U, UV>& y)
98 {
99 return x.base() == y.base();
100 }
101
102 template <class T, class TV, class U, class UV>
103 inline
104 bool
105 operator!=(const input_iterator<T, TV>& x, const input_iterator<U, UV>& y)
106 {
107 return !(x == y);
108 }
109
110 template <class It>
111 class forward_iterator
112 {
113 It it_;
114
115 template <class U> friend class forward_iterator;
116 public:
117 typedef std::forward_iterator_tag iterator_category;
118 typedef typename std::iterator_traits<It>::value_type value_type;
119 typedef typename std::iterator_traits<It>::difference_type difference_type;
120 typedef It pointer;
121 typedef typename std::iterator_traits<It>::reference reference;
122
base()123 TEST_CONSTEXPR_CXX14 It base() const {return it_;}
124
forward_iterator()125 TEST_CONSTEXPR_CXX14 forward_iterator() : it_() {}
forward_iterator(It it)126 explicit TEST_CONSTEXPR_CXX14 forward_iterator(It it) : it_(it) {}
127 template <class U>
forward_iterator(const forward_iterator<U> & u)128 TEST_CONSTEXPR_CXX14 forward_iterator(const forward_iterator<U>& u) :it_(u.it_) {}
129
130 TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
131 TEST_CONSTEXPR_CXX14 pointer operator->() const {return it_;}
132
133 TEST_CONSTEXPR_CXX14 forward_iterator& operator++() {++it_; return *this;}
134 TEST_CONSTEXPR_CXX14 forward_iterator operator++(int)
135 {forward_iterator tmp(*this); ++(*this); return tmp;}
136
137 friend TEST_CONSTEXPR_CXX14 bool operator==(const forward_iterator& x, const forward_iterator& y)
138 {return x.it_ == y.it_;}
139 friend TEST_CONSTEXPR_CXX14 bool operator!=(const forward_iterator& x, const forward_iterator& y)
140 {return !(x == y);}
141
142 template <class T>
143 void operator,(T const &) DELETE_FUNCTION;
144 };
145
146 template <class T, class U>
147 inline
148 bool TEST_CONSTEXPR_CXX14
149 operator==(const forward_iterator<T>& x, const forward_iterator<U>& y)
150 {
151 return x.base() == y.base();
152 }
153
154 template <class T, class U>
155 inline
156 bool TEST_CONSTEXPR_CXX14
157 operator!=(const forward_iterator<T>& x, const forward_iterator<U>& y)
158 {
159 return !(x == y);
160 }
161
162 template <class It>
163 class bidirectional_iterator
164 {
165 It it_;
166
167 template <class U> friend class bidirectional_iterator;
168 public:
169 typedef std::bidirectional_iterator_tag iterator_category;
170 typedef typename std::iterator_traits<It>::value_type value_type;
171 typedef typename std::iterator_traits<It>::difference_type difference_type;
172 typedef It pointer;
173 typedef typename std::iterator_traits<It>::reference reference;
174
base()175 TEST_CONSTEXPR_CXX14 It base() const {return it_;}
176
bidirectional_iterator()177 TEST_CONSTEXPR_CXX14 bidirectional_iterator() : it_() {}
bidirectional_iterator(It it)178 explicit TEST_CONSTEXPR_CXX14 bidirectional_iterator(It it) : it_(it) {}
179 template <class U>
bidirectional_iterator(const bidirectional_iterator<U> & u)180 TEST_CONSTEXPR_CXX14 bidirectional_iterator(const bidirectional_iterator<U>& u) :it_(u.it_) {}
181
182 TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
183 TEST_CONSTEXPR_CXX14 pointer operator->() const {return it_;}
184
185 TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator++() {++it_; return *this;}
186 TEST_CONSTEXPR_CXX14 bidirectional_iterator operator++(int)
187 {bidirectional_iterator tmp(*this); ++(*this); return tmp;}
188
189 TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator--() {--it_; return *this;}
190 TEST_CONSTEXPR_CXX14 bidirectional_iterator operator--(int)
191 {bidirectional_iterator tmp(*this); --(*this); return tmp;}
192
193 template <class T>
194 void operator,(T const &) DELETE_FUNCTION;
195 };
196
197 template <class T, class U>
198 inline
199 bool TEST_CONSTEXPR_CXX14
200 operator==(const bidirectional_iterator<T>& x, const bidirectional_iterator<U>& y)
201 {
202 return x.base() == y.base();
203 }
204
205 template <class T, class U>
206 inline
207 bool TEST_CONSTEXPR_CXX14
208 operator!=(const bidirectional_iterator<T>& x, const bidirectional_iterator<U>& y)
209 {
210 return !(x == y);
211 }
212
213 template <class It>
214 class random_access_iterator
215 {
216 It it_;
217
218 template <class U> friend class random_access_iterator;
219 public:
220 typedef std::random_access_iterator_tag iterator_category;
221 typedef typename std::iterator_traits<It>::value_type value_type;
222 typedef typename std::iterator_traits<It>::difference_type difference_type;
223 typedef It pointer;
224 typedef typename std::iterator_traits<It>::reference reference;
225
base()226 TEST_CONSTEXPR_CXX14 It base() const {return it_;}
227
random_access_iterator()228 TEST_CONSTEXPR_CXX14 random_access_iterator() : it_() {}
random_access_iterator(It it)229 explicit TEST_CONSTEXPR_CXX14 random_access_iterator(It it) : it_(it) {}
230 template <class U>
random_access_iterator(const random_access_iterator<U> & u)231 TEST_CONSTEXPR_CXX14 random_access_iterator(const random_access_iterator<U>& u) :it_(u.it_) {}
232
233 TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
234 TEST_CONSTEXPR_CXX14 pointer operator->() const {return it_;}
235
236 TEST_CONSTEXPR_CXX14 random_access_iterator& operator++() {++it_; return *this;}
237 TEST_CONSTEXPR_CXX14 random_access_iterator operator++(int)
238 {random_access_iterator tmp(*this); ++(*this); return tmp;}
239
240 TEST_CONSTEXPR_CXX14 random_access_iterator& operator--() {--it_; return *this;}
241 TEST_CONSTEXPR_CXX14 random_access_iterator operator--(int)
242 {random_access_iterator tmp(*this); --(*this); return tmp;}
243
244 TEST_CONSTEXPR_CXX14 random_access_iterator& operator+=(difference_type n) {it_ += n; return *this;}
245 TEST_CONSTEXPR_CXX14 random_access_iterator operator+(difference_type n) const
246 {random_access_iterator tmp(*this); tmp += n; return tmp;}
247 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(difference_type n, random_access_iterator x)
248 {x += n; return x;}
249 TEST_CONSTEXPR_CXX14 random_access_iterator& operator-=(difference_type n) {return *this += -n;}
250 TEST_CONSTEXPR_CXX14 random_access_iterator operator-(difference_type n) const
251 {random_access_iterator tmp(*this); tmp -= n; return tmp;}
252
253 TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return it_[n];}
254
255 template <class T>
256 void operator,(T const &) DELETE_FUNCTION;
257 };
258
259 template <class T, class U>
260 inline
261 bool TEST_CONSTEXPR_CXX14
262 operator==(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
263 {
264 return x.base() == y.base();
265 }
266
267 template <class T, class U>
268 inline
269 bool TEST_CONSTEXPR_CXX14
270 operator!=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
271 {
272 return !(x == y);
273 }
274
275 template <class T, class U>
276 inline
277 bool TEST_CONSTEXPR_CXX14
278 operator<(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
279 {
280 return x.base() < y.base();
281 }
282
283 template <class T, class U>
284 inline
285 bool TEST_CONSTEXPR_CXX14
286 operator<=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
287 {
288 return !(y < x);
289 }
290
291 template <class T, class U>
292 inline
293 bool TEST_CONSTEXPR_CXX14
294 operator>(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
295 {
296 return y < x;
297 }
298
299 template <class T, class U>
300 inline
301 bool TEST_CONSTEXPR_CXX14
302 operator>=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
303 {
304 return !(x < y);
305 }
306
307 template <class T, class U>
308 inline TEST_CONSTEXPR_CXX14
309 typename std::iterator_traits<T>::difference_type
310 operator-(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
311 {
312 return x.base() - y.base();
313 }
314
315 template <class Iter>
base(output_iterator<Iter> i)316 inline TEST_CONSTEXPR_CXX14 Iter base(output_iterator<Iter> i) { return i.base(); }
317
318 template <class Iter>
base(input_iterator<Iter> i)319 inline TEST_CONSTEXPR_CXX14 Iter base(input_iterator<Iter> i) { return i.base(); }
320
321 template <class Iter>
base(forward_iterator<Iter> i)322 inline TEST_CONSTEXPR_CXX14 Iter base(forward_iterator<Iter> i) { return i.base(); }
323
324 template <class Iter>
base(bidirectional_iterator<Iter> i)325 inline TEST_CONSTEXPR_CXX14 Iter base(bidirectional_iterator<Iter> i) { return i.base(); }
326
327 template <class Iter>
base(random_access_iterator<Iter> i)328 inline TEST_CONSTEXPR_CXX14 Iter base(random_access_iterator<Iter> i) { return i.base(); }
329
330 template <class Iter> // everything else
base(Iter i)331 inline TEST_CONSTEXPR_CXX14 Iter base(Iter i) { return i; }
332
333 template <typename T>
334 struct ThrowingIterator {
335 typedef std::bidirectional_iterator_tag iterator_category;
336 typedef ptrdiff_t difference_type;
337 typedef const T value_type;
338 typedef const T * pointer;
339 typedef const T & reference;
340
341 enum ThrowingAction { TAIncrement, TADecrement, TADereference, TAAssignment, TAComparison };
342
343 // Constructors
ThrowingIteratorThrowingIterator344 ThrowingIterator ()
345 : begin_(nullptr), end_(nullptr), current_(nullptr), action_(TADereference), index_(0) {}
346 ThrowingIterator (const T *first, const T *last, size_t index = 0, ThrowingAction action = TADereference)
begin_ThrowingIterator347 : begin_(first), end_(last), current_(first), action_(action), index_(index) {}
ThrowingIteratorThrowingIterator348 ThrowingIterator (const ThrowingIterator &rhs)
349 : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_), action_(rhs.action_), index_(rhs.index_) {}
350 ThrowingIterator & operator= (const ThrowingIterator &rhs)
351 {
352 if (action_ == TAAssignment)
353 {
354 if (index_ == 0)
355 #ifndef TEST_HAS_NO_EXCEPTIONS
356 throw std::runtime_error ("throw from iterator assignment");
357 #else
358 assert(false);
359 #endif
360
361 else
362 --index_;
363 }
364 begin_ = rhs.begin_;
365 end_ = rhs.end_;
366 current_ = rhs.current_;
367 action_ = rhs.action_;
368 index_ = rhs.index_;
369 return *this;
370 }
371
372 // iterator operations
373 reference operator*() const
374 {
375 if (action_ == TADereference)
376 {
377 if (index_ == 0)
378 #ifndef TEST_HAS_NO_EXCEPTIONS
379 throw std::runtime_error ("throw from iterator dereference");
380 #else
381 assert(false);
382 #endif
383 else
384 --index_;
385 }
386 return *current_;
387 }
388
389 ThrowingIterator & operator++()
390 {
391 if (action_ == TAIncrement)
392 {
393 if (index_ == 0)
394 #ifndef TEST_HAS_NO_EXCEPTIONS
395 throw std::runtime_error ("throw from iterator increment");
396 #else
397 assert(false);
398 #endif
399 else
400 --index_;
401 }
402 ++current_;
403 return *this;
404 }
405
406 ThrowingIterator operator++(int)
407 {
408 ThrowingIterator temp = *this;
409 ++(*this);
410 return temp;
411 }
412
413 ThrowingIterator & operator--()
414 {
415 if (action_ == TADecrement)
416 {
417 if (index_ == 0)
418 #ifndef TEST_HAS_NO_EXCEPTIONS
419 throw std::runtime_error ("throw from iterator decrement");
420 #else
421 assert(false);
422 #endif
423 else
424 --index_;
425 }
426 --current_;
427 return *this;
428 }
429
430 ThrowingIterator operator--(int) {
431 ThrowingIterator temp = *this;
432 --(*this);
433 return temp;
434 }
435
436 bool operator== (const ThrowingIterator &rhs) const
437 {
438 if (action_ == TAComparison)
439 {
440 if (index_ == 0)
441 #ifndef TEST_HAS_NO_EXCEPTIONS
442 throw std::runtime_error ("throw from iterator comparison");
443 #else
444 assert(false);
445 #endif
446 else
447 --index_;
448 }
449 bool atEndL = current_ == end_;
450 bool atEndR = rhs.current_ == rhs.end_;
451 if (atEndL != atEndR) return false; // one is at the end (or empty), the other is not.
452 if (atEndL) return true; // both are at the end (or empty)
453 return current_ == rhs.current_;
454 }
455
456 private:
457 const T* begin_;
458 const T* end_;
459 const T* current_;
460 ThrowingAction action_;
461 mutable size_t index_;
462 };
463
464 template <typename T>
465 bool operator== (const ThrowingIterator<T>& a, const ThrowingIterator<T>& b)
466 { return a.operator==(b); }
467
468 template <typename T>
469 bool operator!= (const ThrowingIterator<T>& a, const ThrowingIterator<T>& b)
470 { return !a.operator==(b); }
471
472 template <typename T>
473 struct NonThrowingIterator {
474 typedef std::bidirectional_iterator_tag iterator_category;
475 typedef ptrdiff_t difference_type;
476 typedef const T value_type;
477 typedef const T * pointer;
478 typedef const T & reference;
479
480 // Constructors
NonThrowingIteratorNonThrowingIterator481 NonThrowingIterator ()
482 : begin_(nullptr), end_(nullptr), current_(nullptr) {}
NonThrowingIteratorNonThrowingIterator483 NonThrowingIterator (const T *first, const T* last)
484 : begin_(first), end_(last), current_(first) {}
NonThrowingIteratorNonThrowingIterator485 NonThrowingIterator (const NonThrowingIterator &rhs)
486 : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_) {}
487 NonThrowingIterator & operator= (const NonThrowingIterator &rhs) TEST_NOEXCEPT
488 {
489 begin_ = rhs.begin_;
490 end_ = rhs.end_;
491 current_ = rhs.current_;
492 return *this;
493 }
494
495 // iterator operations
496 reference operator*() const TEST_NOEXCEPT
497 {
498 return *current_;
499 }
500
501 NonThrowingIterator & operator++() TEST_NOEXCEPT
502 {
503 ++current_;
504 return *this;
505 }
506
507 NonThrowingIterator operator++(int) TEST_NOEXCEPT
508 {
509 NonThrowingIterator temp = *this;
510 ++(*this);
511 return temp;
512 }
513
514 NonThrowingIterator & operator--() TEST_NOEXCEPT
515 {
516 --current_;
517 return *this;
518 }
519
520 NonThrowingIterator operator--(int) TEST_NOEXCEPT
521 {
522 NonThrowingIterator temp = *this;
523 --(*this);
524 return temp;
525 }
526
527 bool operator== (const NonThrowingIterator &rhs) const TEST_NOEXCEPT
528 {
529 bool atEndL = current_ == end_;
530 bool atEndR = rhs.current_ == rhs.end_;
531 if (atEndL != atEndR) return false; // one is at the end (or empty), the other is not.
532 if (atEndL) return true; // both are at the end (or empty)
533 return current_ == rhs.current_;
534 }
535
536 private:
537 const T* begin_;
538 const T* end_;
539 const T* current_;
540 };
541
542 template <typename T>
543 bool operator== (const NonThrowingIterator<T>& a, const NonThrowingIterator<T>& b) TEST_NOEXCEPT
544 { return a.operator==(b); }
545
546 template <typename T>
547 bool operator!= (const NonThrowingIterator<T>& a, const NonThrowingIterator<T>& b) TEST_NOEXCEPT
548 { return !a.operator==(b); }
549
550 #undef DELETE_FUNCTION
551
552 #endif // ITERATORS_H
553