test/support/test_iterators.h

   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 #ifndef _LIBCPP_HAS_NO_DELETED_FUNCTIONS
  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     It base() const {return it_;}
  72
  73     input_iterator() : it_() {}
  74     explicit input_iterator(It it) : it_(it) {}
  75     template <class U, class T>
  76         input_iterator(const input_iterator<U, T>& u) :it_(u.it_) {}
  77
  78     reference operator*() const {return *it_;}
  79     pointer operator->() const {return it_;}
  80
  81     input_iterator& operator++() {++it_; return *this;}
  82     input_iterator operator++(int)
  83         {input_iterator tmp(*this); ++(*this); return tmp;}
  84
  85     friend bool operator==(const input_iterator& x, const input_iterator& y)
  86         {return x.it_ == y.it_;}
  87     friend 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     It base() const {return it_;}
 124
 125     forward_iterator() : it_() {}
 126     explicit forward_iterator(It it) : it_(it) {}
 127     template <class U>
 128         forward_iterator(const forward_iterator<U>& u) :it_(u.it_) {}
 129
 130     reference operator*() const {return *it_;}
 131     pointer operator->() const {return it_;}
 132
 133     forward_iterator& operator++() {++it_; return *this;}
 134     forward_iterator operator++(int)
 135         {forward_iterator tmp(*this); ++(*this); return tmp;}
 136
 137     friend bool operator==(const forward_iterator& x, const forward_iterator& y)
 138         {return x.it_ == y.it_;}
 139     friend 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
 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
 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     It base() const {return it_;}
 176
 177     bidirectional_iterator() : it_() {}
 178     explicit bidirectional_iterator(It it) : it_(it) {}
 179     template <class U>
 180         bidirectional_iterator(const bidirectional_iterator<U>& u) :it_(u.it_) {}
 181
 182     reference operator*() const {return *it_;}
 183     pointer operator->() const {return it_;}
 184
 185     bidirectional_iterator& operator++() {++it_; return *this;}
 186     bidirectional_iterator operator++(int)
 187         {bidirectional_iterator tmp(*this); ++(*this); return tmp;}
 188
 189     bidirectional_iterator& operator--() {--it_; return *this;}
 190     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
 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
 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     It base() const {return it_;}
 227
 228     random_access_iterator() : it_() {}
 229     explicit random_access_iterator(It it) : it_(it) {}
 230    template <class U>
 231         random_access_iterator(const random_access_iterator<U>& u) :it_(u.it_) {}
 232
 233     reference operator*() const {return *it_;}
 234     pointer operator->() const {return it_;}
 235
 236     random_access_iterator& operator++() {++it_; return *this;}
 237     random_access_iterator operator++(int)
 238         {random_access_iterator tmp(*this); ++(*this); return tmp;}
 239
 240     random_access_iterator& operator--() {--it_; return *this;}
 241     random_access_iterator operator--(int)
 242         {random_access_iterator tmp(*this); --(*this); return tmp;}
 243
 244     random_access_iterator& operator+=(difference_type n) {it_ += n; return *this;}
 245     random_access_iterator operator+(difference_type n) const
 246         {random_access_iterator tmp(*this); tmp += n; return tmp;}
 247     friend random_access_iterator operator+(difference_type n, random_access_iterator x)
 248         {x += n; return x;}
 249     random_access_iterator& operator-=(difference_type n) {return *this += -n;}
 250     random_access_iterator operator-(difference_type n) const
 251         {random_access_iterator tmp(*this); tmp -= n; return tmp;}
 252
 253     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
 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
 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
 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
 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
 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
 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
 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 Iter base(output_iterator<Iter> i) { return i.base(); }
 317
 318 template <class Iter>
 319 inline Iter base(input_iterator<Iter> i) { return i.base(); }
 320
 321 template <class Iter>
 322 inline Iter base(forward_iterator<Iter> i) { return i.base(); }
 323
 324 template <class Iter>
 325 inline Iter base(bidirectional_iterator<Iter> i) { return i.base(); }
 326
 327 template <class Iter>
 328 inline Iter base(random_access_iterator<Iter> i) { return i.base(); }
 329
 330 template <class Iter>    // everything else
 331 inline 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