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 39 It base() const {return it_;} 40 41 output_iterator () {} 42 explicit output_iterator(It it) : it_(it) {} 43 template <class 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 71 TEST_CONSTEXPR_CXX14 It base() const {return it_;} 72 73 TEST_CONSTEXPR_CXX14 input_iterator() : it_() {} 74 explicit TEST_CONSTEXPR_CXX14 input_iterator(It it) : it_(it) {} 75 template <class U, class T> 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 123 TEST_CONSTEXPR_CXX14 It base() const {return it_;} 124 125 TEST_CONSTEXPR_CXX14 forward_iterator() : it_() {} 126 explicit TEST_CONSTEXPR_CXX14 forward_iterator(It it) : it_(it) {} 127 template <class 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 175 TEST_CONSTEXPR_CXX14 It base() const {return it_;} 176 177 TEST_CONSTEXPR_CXX14 bidirectional_iterator() : it_() {} 178 explicit TEST_CONSTEXPR_CXX14 bidirectional_iterator(It it) : it_(it) {} 179 template <class 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 226 TEST_CONSTEXPR_CXX14 It base() const {return it_;} 227 228 TEST_CONSTEXPR_CXX14 random_access_iterator() : it_() {} 229 explicit TEST_CONSTEXPR_CXX14 random_access_iterator(It it) : it_(it) {} 230 template <class 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> 316 inline TEST_CONSTEXPR_CXX14 Iter base(output_iterator<Iter> i) { return i.base(); } 317 318 template <class Iter> 319 inline TEST_CONSTEXPR_CXX14 Iter base(input_iterator<Iter> i) { return i.base(); } 320 321 template <class Iter> 322 inline TEST_CONSTEXPR_CXX14 Iter base(forward_iterator<Iter> i) { return i.base(); } 323 324 template <class Iter> 325 inline TEST_CONSTEXPR_CXX14 Iter base(bidirectional_iterator<Iter> i) { return i.base(); } 326 327 template <class Iter> 328 inline TEST_CONSTEXPR_CXX14 Iter base(random_access_iterator<Iter> i) { return i.base(); } 329 330 template <class Iter> // everything else 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 344 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) 347 : begin_(first), end_(last), current_(first), action_(action), index_(index) {} 348 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 481 NonThrowingIterator () 482 : begin_(nullptr), end_(nullptr), current_(nullptr) {} 483 NonThrowingIterator (const T *first, const T* last) 484 : begin_(first), end_(last), current_(first) {} 485 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