contrib/libstdc++/stl/stl_iterator.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996-1998
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31 #ifndef __SGI_STL_INTERNAL_ITERATOR_H
  32 #define __SGI_STL_INTERNAL_ITERATOR_H
  33
  34 __STL_BEGIN_NAMESPACE
  35
  36 struct input_iterator_tag {};
  37 struct output_iterator_tag {};
  38 struct forward_iterator_tag : public input_iterator_tag {};
  39 struct bidirectional_iterator_tag : public forward_iterator_tag {};
  40 struct random_access_iterator_tag : public bidirectional_iterator_tag {};
  41
  42 // The base classes input_iterator, output_iterator, forward_iterator,
  43 // bidirectional_iterator, and random_access_iterator are not part of
  44 // the C++ standard.  (they have been replaced by struct iterator.)
  45 // They are included for backward compatibility with the HP STL.
  46
  47 template <class _Tp, class _Distance> struct input_iterator {
  48   typedef input_iterator_tag iterator_category;
  49   typedef _Tp                value_type;
  50   typedef _Distance          difference_type;
  51   typedef _Tp*               pointer;
  52   typedef _Tp&               reference;
  53 };
  54
  55 struct output_iterator {
  56   typedef output_iterator_tag iterator_category;
  57   typedef void                value_type;
  58   typedef void                difference_type;
  59   typedef void                pointer;
  60   typedef void                reference;
  61 };
  62
  63 template <class _Tp, class _Distance> struct forward_iterator {
  64   typedef forward_iterator_tag iterator_category;
  65   typedef _Tp                  value_type;
  66   typedef _Distance            difference_type;
  67   typedef _Tp*                 pointer;
  68   typedef _Tp&                 reference;
  69 };
  70
  71
  72 template <class _Tp, class _Distance> struct bidirectional_iterator {
  73   typedef bidirectional_iterator_tag iterator_category;
  74   typedef _Tp                        value_type;
  75   typedef _Distance                  difference_type;
  76   typedef _Tp*                       pointer;
  77   typedef _Tp&                       reference;
  78 };
  79
  80 template <class _Tp, class _Distance> struct random_access_iterator {
  81   typedef random_access_iterator_tag iterator_category;
  82   typedef _Tp                        value_type;
  83   typedef _Distance                  difference_type;
  84   typedef _Tp*                       pointer;
  85   typedef _Tp&                       reference;
  86 };
  87
  88 #ifdef __STL_USE_NAMESPACES
  89 template <class _Category, class _Tp, class _Distance = ptrdiff_t,
  90           class _Pointer = _Tp*, class _Reference = _Tp&>
  91 struct iterator {
  92   typedef _Category  iterator_category;
  93   typedef _Tp        value_type;
  94   typedef _Distance  difference_type;
  95   typedef _Pointer   pointer;
  96   typedef _Reference reference;
  97 };
  98 #endif /* __STL_USE_NAMESPACES */
  99
 100 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 101
 102 template <class _Iterator>
 103 struct iterator_traits {
 104   typedef typename _Iterator::iterator_category iterator_category;
 105   typedef typename _Iterator::value_type        value_type;
 106   typedef typename _Iterator::difference_type   difference_type;
 107   typedef typename _Iterator::pointer           pointer;
 108   typedef typename _Iterator::reference         reference;
 109 };
 110
 111 template <class _Tp>
 112 struct iterator_traits<_Tp*> {
 113   typedef random_access_iterator_tag iterator_category;
 114   typedef _Tp                         value_type;
 115   typedef ptrdiff_t                   difference_type;
 116   typedef _Tp*                        pointer;
 117   typedef _Tp&                        reference;
 118 };
 119
 120 template <class _Tp>
 121 struct iterator_traits<const _Tp*> {
 122   typedef random_access_iterator_tag iterator_category;
 123   typedef _Tp                         value_type;
 124   typedef ptrdiff_t                   difference_type;
 125   typedef const _Tp*                  pointer;
 126   typedef const _Tp&                  reference;
 127 };
 128
 129 // The overloaded functions iterator_category, distance_type, and
 130 // value_type are not part of the C++ standard.  (They have been
 131 // replaced by struct iterator_traits.)  They are included for
 132 // backward compatibility with the HP STL.
 133
 134 // We introduce internal names for these functions.
 135
 136 template <class _Iter>
 137 inline typename iterator_traits<_Iter>::iterator_category
 138 __iterator_category(const _Iter&)
 139 {
 140   typedef typename iterator_traits<_Iter>::iterator_category _Category;
 141   return _Category();
 142 }
 143
 144 template <class _Iter>
 145 inline typename iterator_traits<_Iter>::difference_type*
 146 __distance_type(const _Iter&)
 147 {
 148   return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
 149 }
 150
 151 template <class _Iter>
 152 inline typename iterator_traits<_Iter>::value_type*
 153 __value_type(const _Iter&)
 154 {
 155   return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
 156 }
 157
 158 template <class _Iter>
 159 inline typename iterator_traits<_Iter>::iterator_category
 160 iterator_category(const _Iter& __i) { return __iterator_category(__i); }
 161
 162
 163 template <class _Iter>
 164 inline typename iterator_traits<_Iter>::difference_type*
 165 distance_type(const _Iter& __i) { return __distance_type(__i); }
 166
 167 template <class _Iter>
 168 inline typename iterator_traits<_Iter>::value_type*
 169 value_type(const _Iter& __i) { return __value_type(__i); }
 170
 171 #define __ITERATOR_CATEGORY(__i) __iterator_category(__i)
 172 #define __DISTANCE_TYPE(__i)     __distance_type(__i)
 173 #define __VALUE_TYPE(__i)        __value_type(__i)
 174
 175 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 176
 177 template <class _Tp, class _Distance>
 178 inline input_iterator_tag
 179 iterator_category(const input_iterator<_Tp, _Distance>&)
 180   { return input_iterator_tag(); }
 181
 182 inline output_iterator_tag iterator_category(const output_iterator&)
 183   { return output_iterator_tag(); }
 184
 185 template <class _Tp, class _Distance>
 186 inline forward_iterator_tag
 187 iterator_category(const forward_iterator<_Tp, _Distance>&)
 188   { return forward_iterator_tag(); }
 189
 190 template <class _Tp, class _Distance>
 191 inline bidirectional_iterator_tag
 192 iterator_category(const bidirectional_iterator<_Tp, _Distance>&)
 193   { return bidirectional_iterator_tag(); }
 194
 195 template <class _Tp, class _Distance>
 196 inline random_access_iterator_tag
 197 iterator_category(const random_access_iterator<_Tp, _Distance>&)
 198   { return random_access_iterator_tag(); }
 199
 200 template <class _Tp>
 201 inline random_access_iterator_tag iterator_category(const _Tp*)
 202   { return random_access_iterator_tag(); }
 203
 204 template <class _Tp, class _Distance>
 205 inline _Tp* value_type(const input_iterator<_Tp, _Distance>&)
 206   { return (_Tp*)(0); }
 207
 208 template <class _Tp, class _Distance>
 209 inline _Tp* value_type(const forward_iterator<_Tp, _Distance>&)
 210   { return (_Tp*)(0); }
 211
 212 template <class _Tp, class _Distance>
 213 inline _Tp* value_type(const bidirectional_iterator<_Tp, _Distance>&)
 214   { return (_Tp*)(0); }
 215
 216 template <class _Tp, class _Distance>
 217 inline _Tp* value_type(const random_access_iterator<_Tp, _Distance>&)
 218   { return (_Tp*)(0); }
 219
 220 template <class _Tp>
 221 inline _Tp* value_type(const _Tp*) { return (_Tp*)(0); }
 222
 223 template <class _Tp, class _Distance>
 224 inline _Distance* distance_type(const input_iterator<_Tp, _Distance>&)
 225 {
 226   return (_Distance*)(0);
 227 }
 228
 229 template <class _Tp, class _Distance>
 230 inline _Distance* distance_type(const forward_iterator<_Tp, _Distance>&)
 231 {
 232   return (_Distance*)(0);
 233 }
 234
 235 template <class _Tp, class _Distance>
 236 inline _Distance*
 237 distance_type(const bidirectional_iterator<_Tp, _Distance>&)
 238 {
 239   return (_Distance*)(0);
 240 }
 241
 242 template <class _Tp, class _Distance>
 243 inline _Distance*
 244 distance_type(const random_access_iterator<_Tp, _Distance>&)
 245 {
 246   return (_Distance*)(0);
 247 }
 248
 249 template <class _Tp>
 250 inline ptrdiff_t* distance_type(const _Tp*) { return (ptrdiff_t*)(0); }
 251
 252 // Without partial specialization we can't use iterator_traits, so
 253 // we must keep the old iterator query functions around.
 254
 255 #define __ITERATOR_CATEGORY(__i) iterator_category(__i)
 256 #define __DISTANCE_TYPE(__i)     distance_type(__i)
 257 #define __VALUE_TYPE(__i)        value_type(__i)
 258
 259 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 260
 261 template <class _InputIterator, class _Distance>
 262 inline void __distance(_InputIterator __first, _InputIterator __last,
 263                        _Distance& __n, input_iterator_tag)
 264 {
 265   while (__first != __last) { ++__first; ++__n; }
 266 }
 267
 268 template <class _RandomAccessIterator, class _Distance>
 269 inline void __distance(_RandomAccessIterator __first,
 270                        _RandomAccessIterator __last,
 271                        _Distance& __n, random_access_iterator_tag)
 272 {
 273   __n += __last - __first;
 274 }
 275
 276 template <class _InputIterator, class _Distance>
 277 inline void distance(_InputIterator __first,
 278                      _InputIterator __last, _Distance& __n)
 279 {
 280   __distance(__first, __last, __n, iterator_category(__first));
 281 }
 282
 283 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 284
 285 template <class _InputIterator>
 286 inline typename iterator_traits<_InputIterator>::difference_type
 287 __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
 288 {
 289   typename iterator_traits<_InputIterator>::difference_type __n = 0;
 290   while (__first != __last) {
 291     ++__first; ++__n;
 292   }
 293   return __n;
 294 }
 295
 296 template <class _RandomAccessIterator>
 297 inline typename iterator_traits<_RandomAccessIterator>::difference_type
 298 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
 299            random_access_iterator_tag) {
 300   return __last - __first;
 301 }
 302
 303 template <class _InputIterator>
 304 inline typename iterator_traits<_InputIterator>::difference_type
 305 distance(_InputIterator __first, _InputIterator __last) {
 306   typedef typename iterator_traits<_InputIterator>::iterator_category
 307     _Category;
 308   return __distance(__first, __last, _Category());
 309 }
 310
 311 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 312
 313 template <class _InputIter, class _Distance>
 314 inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
 315   while (__n--) ++__i;
 316 }
 317
 318 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 319 #pragma set woff 1183
 320 #endif
 321
 322 template <class _BidirectionalIterator, class _Distance>
 323 inline void __advance(_BidirectionalIterator& __i, _Distance __n,
 324                       bidirectional_iterator_tag) {
 325   if (__n >= 0)
 326     while (__n--) ++__i;
 327   else
 328     while (__n++) --__i;
 329 }
 330
 331 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 332 #pragma reset woff 1183
 333 #endif
 334
 335 template <class _RandomAccessIterator, class _Distance>
 336 inline void __advance(_RandomAccessIterator& __i, _Distance __n,
 337                       random_access_iterator_tag) {
 338   __i += __n;
 339 }
 340
 341 template <class _InputIterator, class _Distance>
 342 inline void advance(_InputIterator& __i, _Distance __n) {
 343   __advance(__i, __n, iterator_category(__i));
 344 }
 345
 346 template <class _Container>
 347 class back_insert_iterator {
 348 protected:
 349   _Container* container;
 350 public:
 351   typedef _Container          container_type;
 352   typedef output_iterator_tag iterator_category;
 353   typedef void                value_type;
 354   typedef void                difference_type;
 355   typedef void                pointer;
 356   typedef void                reference;
 357
 358   explicit back_insert_iterator(_Container& __x) : container(&__x) {}
 359   back_insert_iterator<_Container>&
 360   operator=(const typename _Container::value_type& __value) {
 361     container->push_back(__value);
 362     return *this;
 363   }
 364   back_insert_iterator<_Container>& operator*() { return *this; }
 365   back_insert_iterator<_Container>& operator++() { return *this; }
 366   back_insert_iterator<_Container>& operator++(int) { return *this; }
 367 };
 368
 369 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 370
 371 template <class _Container>
 372 inline output_iterator_tag
 373 iterator_category(const back_insert_iterator<_Container>&)
 374 {
 375   return output_iterator_tag();
 376 }
 377
 378 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 379
 380 template <class _Container>
 381 inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
 382   return back_insert_iterator<_Container>(__x);
 383 }
 384
 385 template <class _Container>
 386 class front_insert_iterator {
 387 protected:
 388   _Container* container;
 389 public:
 390   typedef _Container          container_type;
 391   typedef output_iterator_tag iterator_category;
 392   typedef void                value_type;
 393   typedef void                difference_type;
 394   typedef void                pointer;
 395   typedef void                reference;
 396
 397   explicit front_insert_iterator(_Container& __x) : container(&__x) {}
 398   front_insert_iterator<_Container>&
 399   operator=(const typename _Container::value_type& __value) {
 400     container->push_front(__value);
 401     return *this;
 402   }
 403   front_insert_iterator<_Container>& operator*() { return *this; }
 404   front_insert_iterator<_Container>& operator++() { return *this; }
 405   front_insert_iterator<_Container>& operator++(int) { return *this; }
 406 };
 407
 408 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 409
 410 template <class _Container>
 411 inline output_iterator_tag
 412 iterator_category(const front_insert_iterator<_Container>&)
 413 {
 414   return output_iterator_tag();
 415 }
 416
 417 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 418
 419 template <class _Container>
 420 inline front_insert_iterator<_Container> front_inserter(_Container& __x) {
 421   return front_insert_iterator<_Container>(__x);
 422 }
 423
 424 template <class _Container>
 425 class insert_iterator {
 426 protected:
 427   _Container* container;
 428   typename _Container::iterator iter;
 429 public:
 430   typedef _Container          container_type;
 431   typedef output_iterator_tag iterator_category;
 432   typedef void                value_type;
 433   typedef void                difference_type;
 434   typedef void                pointer;
 435   typedef void                reference;
 436
 437   insert_iterator(_Container& __x, typename _Container::iterator __i)
 438     : container(&__x), iter(__i) {}
 439   insert_iterator<_Container>&
 440   operator=(const typename _Container::value_type& __value) {
 441     iter = container->insert(iter, __value);
 442     ++iter;
 443     return *this;
 444   }
 445   insert_iterator<_Container>& operator*() { return *this; }
 446   insert_iterator<_Container>& operator++() { return *this; }
 447   insert_iterator<_Container>& operator++(int) { return *this; }
 448 };
 449
 450 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 451
 452 template <class _Container>
 453 inline output_iterator_tag
 454 iterator_category(const insert_iterator<_Container>&)
 455 {
 456   return output_iterator_tag();
 457 }
 458
 459 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 460
 461 template <class _Container, class _Iterator>
 462 inline
 463 insert_iterator<_Container> inserter(_Container& __x, _Iterator __i)
 464 {
 465   typedef typename _Container::iterator __iter;
 466   return insert_iterator<_Container>(__x, __iter(__i));
 467 }
 468
 469 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
 470 template <class _BidirectionalIterator, class _Tp, class _Reference = _Tp&,
 471           class _Distance = ptrdiff_t>
 472 #else
 473 template <class _BidirectionalIterator, class _Tp, class _Reference,
 474           class _Distance>
 475 #endif
 476 class reverse_bidirectional_iterator {
 477   typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
 478                                          _Reference, _Distance>  _Self;
 479 protected:
 480   _BidirectionalIterator current;
 481 public:
 482   typedef bidirectional_iterator_tag iterator_category;
 483   typedef _Tp                        value_type;
 484   typedef _Distance                  difference_type;
 485   typedef _Tp*                       pointer;
 486   typedef _Reference                 reference;
 487
 488   reverse_bidirectional_iterator() {}
 489   explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
 490     : current(__x) {}
 491   _BidirectionalIterator base() const { return current; }
 492   _Reference operator*() const {
 493     _BidirectionalIterator __tmp = current;
 494     return *--__tmp;
 495   }
 496 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 497   pointer operator->() const { return &(operator*()); }
 498 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 499   _Self& operator++() {
 500     --current;
 501     return *this;
 502   }
 503   _Self operator++(int) {
 504     _Self __tmp = *this;
 505     --current;
 506     return __tmp;
 507   }
 508   _Self& operator--() {
 509     ++current;
 510     return *this;
 511   }
 512   _Self operator--(int) {
 513     _Self __tmp = *this;
 514     ++current;
 515     return __tmp;
 516   }
 517 };
 518
 519 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 520
 521 template <class _BidirectionalIterator, class _Tp, class _Reference,
 522           class _Distance>
 523 inline bidirectional_iterator_tag
 524 iterator_category(const reverse_bidirectional_iterator<_BidirectionalIterator,
 525                                                        _Tp, _Reference,
 526                                                        _Distance>&)
 527 {
 528   return bidirectional_iterator_tag();
 529 }
 530
 531 template <class _BidirectionalIterator, class _Tp, class _Reference,
 532           class _Distance>
 533 inline _Tp*
 534 value_type(const reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
 535                                                _Reference, _Distance>&)
 536 {
 537   return (_Tp*) 0;
 538 }
 539
 540 template <class _BidirectionalIterator, class _Tp, class _Reference,
 541           class _Distance>
 542 inline _Distance*
 543 distance_type(const reverse_bidirectional_iterator<_BidirectionalIterator,
 544                                                    _Tp,
 545                                                    _Reference, _Distance>&)
 546 {
 547   return (_Distance*) 0;
 548 }
 549
 550 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 551
 552 template <class _BiIter, class _Tp, class _Ref,
 553           class _Distance>
 554 inline bool operator==(
 555     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
 556     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
 557 {
 558   return __x.base() == __y.base();
 559 }
 560
 561 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 562
 563 // This is the new version of reverse_iterator, as defined in the
 564 //  draft C++ standard.  It relies on the iterator_traits template,
 565 //  which in turn relies on partial specialization.  The class
 566 //  reverse_bidirectional_iterator is no longer part of the draft
 567 //  standard, but it is retained for backward compatibility.
 568
 569 template <class _Iterator>
 570 class reverse_iterator
 571 {
 572 protected:
 573   _Iterator current;
 574 public:
 575   typedef typename iterator_traits<_Iterator>::iterator_category
 576           iterator_category;
 577   typedef typename iterator_traits<_Iterator>::value_type
 578           value_type;
 579   typedef typename iterator_traits<_Iterator>::difference_type
 580           difference_type;
 581   typedef typename iterator_traits<_Iterator>::pointer
 582           pointer;
 583   typedef typename iterator_traits<_Iterator>::reference
 584           reference;
 585
 586   typedef _Iterator iterator_type;
 587   typedef reverse_iterator<_Iterator> _Self;
 588
 589 public:
 590   reverse_iterator() {}
 591   explicit reverse_iterator(iterator_type __x) : current(__x) {}
 592
 593   reverse_iterator(const _Self& __x) : current(__x.current) {}
 594 #ifdef __STL_MEMBER_TEMPLATES
 595   template <class _Iter>
 596   reverse_iterator(const reverse_iterator<_Iter>& __x)
 597     : current(__x.base()) {}
 598 #endif /* __STL_MEMBER_TEMPLATES */
 599
 600   iterator_type base() const { return current; }
 601   reference operator*() const {
 602     _Iterator __tmp = current;
 603     return *--__tmp;
 604   }
 605 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 606   pointer operator->() const { return &(operator*()); }
 607 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 608
 609   _Self& operator++() {
 610     --current;
 611     return *this;
 612   }
 613   _Self operator++(int) {
 614     _Self __tmp = *this;
 615     --current;
 616     return __tmp;
 617   }
 618   _Self& operator--() {
 619     ++current;
 620     return *this;
 621   }
 622   _Self operator--(int) {
 623     _Self __tmp = *this;
 624     ++current;
 625     return __tmp;
 626   }
 627
 628   _Self operator+(difference_type __n) const {
 629     return _Self(current - __n);
 630   }
 631   _Self& operator+=(difference_type __n) {
 632     current -= __n;
 633     return *this;
 634   }
 635   _Self operator-(difference_type __n) const {
 636     return _Self(current + __n);
 637   }
 638   _Self& operator-=(difference_type __n) {
 639     current += __n;
 640     return *this;
 641   }
 642   reference operator[](difference_type __n) const { return *(*this + __n); }
 643 };
 644
 645 template <class _Iterator>
 646 inline bool operator==(const reverse_iterator<_Iterator>& __x,
 647                        const reverse_iterator<_Iterator>& __y) {
 648   return __x.base() == __y.base();
 649 }
 650
 651 template <class _Iterator>
 652 inline bool operator<(const reverse_iterator<_Iterator>& __x,
 653                       const reverse_iterator<_Iterator>& __y) {
 654   return __y.base() < __x.base();
 655 }
 656
 657 template <class _Iterator>
 658 inline typename reverse_iterator<_Iterator>::difference_type
 659 operator-(const reverse_iterator<_Iterator>& __x,
 660           const reverse_iterator<_Iterator>& __y) {
 661   return __y.base() - __x.base();
 662 }
 663
 664 template <class _Iterator>
 665 inline reverse_iterator<_Iterator>
 666 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
 667           const reverse_iterator<_Iterator>& __x) {
 668   return reverse_iterator<_Iterator>(__x.base() - __n);
 669 }
 670
 671 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 672
 673 // This is the old version of reverse_iterator, as found in the original
 674 //  HP STL.  It does not use partial specialization.
 675
 676 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
 677 template <class _RandomAccessIterator, class _Tp, class _Reference = _Tp&,
 678           class _Distance = ptrdiff_t>
 679 #else
 680 template <class _RandomAccessIterator, class _Tp, class _Reference,
 681           class _Distance>
 682 #endif
 683 class reverse_iterator {
 684   typedef reverse_iterator<_RandomAccessIterator, _Tp, _Reference, _Distance>
 685         _Self;
 686 protected:
 687   _RandomAccessIterator current;
 688 public:
 689   typedef random_access_iterator_tag iterator_category;
 690   typedef _Tp                        value_type;
 691   typedef _Distance                  difference_type;
 692   typedef _Tp*                       pointer;
 693   typedef _Reference                 reference;
 694
 695   reverse_iterator() {}
 696   explicit reverse_iterator(_RandomAccessIterator __x) : current(__x) {}
 697   _RandomAccessIterator base() const { return current; }
 698   _Reference operator*() const { return *(current - 1); }
 699 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 700   pointer operator->() const { return &(operator*()); }
 701 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 702   _Self& operator++() {
 703     --current;
 704     return *this;
 705   }
 706   _Self operator++(int) {
 707     _Self __tmp = *this;
 708     --current;
 709     return __tmp;
 710   }
 711   _Self& operator--() {
 712     ++current;
 713     return *this;
 714   }
 715   _Self operator--(int) {
 716     _Self __tmp = *this;
 717     ++current;
 718     return __tmp;
 719   }
 720   _Self operator+(_Distance __n) const {
 721     return _Self(current - __n);
 722   }
 723   _Self& operator+=(_Distance __n) {
 724     current -= __n;
 725     return *this;
 726   }
 727   _Self operator-(_Distance __n) const {
 728     return _Self(current + __n);
 729   }
 730   _Self& operator-=(_Distance __n) {
 731     current += __n;
 732     return *this;
 733   }
 734   _Reference operator[](_Distance __n) const { return *(*this + __n); }
 735 };
 736
 737 template <class _RandomAccessIterator, class _Tp,
 738           class _Reference, class _Distance>
 739 inline random_access_iterator_tag
 740 iterator_category(const reverse_iterator<_RandomAccessIterator, _Tp,
 741                                          _Reference, _Distance>&)
 742 {
 743   return random_access_iterator_tag();
 744 }
 745
 746 template <class _RandomAccessIterator, class _Tp,
 747           class _Reference, class _Distance>
 748 inline _Tp* value_type(const reverse_iterator<_RandomAccessIterator, _Tp,
 749                                               _Reference, _Distance>&)
 750 {
 751   return (_Tp*) 0;
 752 }
 753
 754 template <class _RandomAccessIterator, class _Tp,
 755           class _Reference, class _Distance>
 756 inline _Distance*
 757 distance_type(const reverse_iterator<_RandomAccessIterator,
 758                                      _Tp, _Reference, _Distance>&)
 759 {
 760   return (_Distance*) 0;
 761 }
 762
 763
 764 template <class _RandomAccessIterator, class _Tp,
 765           class _Reference, class _Distance>
 766 inline bool
 767 operator==(const reverse_iterator<_RandomAccessIterator, _Tp,
 768                                   _Reference, _Distance>& __x,
 769            const reverse_iterator<_RandomAccessIterator, _Tp,
 770                                   _Reference, _Distance>& __y)
 771 {
 772   return __x.base() == __y.base();
 773 }
 774
 775 template <class _RandomAccessIterator, class _Tp,
 776           class _Reference, class _Distance>
 777 inline bool
 778 operator<(const reverse_iterator<_RandomAccessIterator, _Tp,
 779                                  _Reference, _Distance>& __x,
 780           const reverse_iterator<_RandomAccessIterator, _Tp,
 781                                  _Reference, _Distance>& __y)
 782 {
 783   return __y.base() < __x.base();
 784 }
 785
 786 template <class _RandomAccessIterator, class _Tp,
 787           class _Reference, class _Distance>
 788 inline _Distance
 789 operator-(const reverse_iterator<_RandomAccessIterator, _Tp,
 790                                  _Reference, _Distance>& __x,
 791           const reverse_iterator<_RandomAccessIterator, _Tp,
 792                                  _Reference, _Distance>& __y)
 793 {
 794   return __y.base() - __x.base();
 795 }
 796
 797 template <class _RandAccIter, class _Tp, class _Ref, class _Dist>
 798 inline reverse_iterator<_RandAccIter, _Tp, _Ref, _Dist>
 799 operator+(_Dist __n,
 800           const reverse_iterator<_RandAccIter, _Tp, _Ref, _Dist>& __x)
 801 {
 802   return reverse_iterator<_RandAccIter, _Tp, _Ref, _Dist>(__x.base() - __n);
 803 }
 804
 805 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 806
 807 // When we have templatized iostreams, istream_iterator and ostream_iterator
 808 // must be rewritten.
 809
 810 template <class _Tp, class _Dist = ptrdiff_t>
 811 class istream_iterator {
 812   friend bool operator== __STL_NULL_TMPL_ARGS (const istream_iterator&,
 813                                                const istream_iterator&);
 814 protected:
 815   istream* _M_stream;
 816   _Tp _M_value;
 817   bool _M_end_marker;
 818   void _M_read() {
 819     _M_end_marker = (*_M_stream) ? true : false;
 820     if (_M_end_marker) *_M_stream >> _M_value;
 821     _M_end_marker = (*_M_stream) ? true : false;
 822   }
 823 public:
 824   typedef input_iterator_tag  iterator_category;
 825   typedef _Tp                 value_type;
 826   typedef _Dist               difference_type;
 827   typedef const _Tp*          pointer;
 828   typedef const _Tp&          reference;
 829
 830   istream_iterator() : _M_stream(&cin), _M_end_marker(false) {}
 831   istream_iterator(istream& __s) : _M_stream(&__s) { _M_read(); }
 832   reference operator*() const { return _M_value; }
 833 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 834   pointer operator->() const { return &(operator*()); }
 835 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 836   istream_iterator<_Tp, _Dist>& operator++() {
 837     _M_read();
 838     return *this;
 839   }
 840   istream_iterator<_Tp, _Dist> operator++(int)  {
 841     istream_iterator<_Tp, _Dist> __tmp = *this;
 842     _M_read();
 843     return __tmp;
 844   }
 845 };
 846
 847 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 848
 849 template <class _Tp, class _Dist>
 850 inline input_iterator_tag
 851 iterator_category(const istream_iterator<_Tp, _Dist>&)
 852 {
 853   return input_iterator_tag();
 854 }
 855
 856 template <class _Tp, class _Dist>
 857 inline _Tp*
 858 value_type(const istream_iterator<_Tp, _Dist>&) { return (_Tp*) 0; }
 859
 860 template <class _Tp, class _Dist>
 861 inline _Dist*
 862 distance_type(const istream_iterator<_Tp, _Dist>&) { return (_Dist*)0; }
 863
 864 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 865
 866 template <class _Tp, class _Distance>
 867 inline bool operator==(const istream_iterator<_Tp, _Distance>& __x,
 868                        const istream_iterator<_Tp, _Distance>& __y) {
 869   return (__x._M_stream == __y._M_stream &&
 870           __x._M_end_marker == __y._M_end_marker) ||
 871          __x._M_end_marker == false && __y._M_end_marker == false;
 872 }
 873
 874 template <class _Tp>
 875 class ostream_iterator {
 876 protected:
 877   ostream* _M_stream;
 878   const char* _M_string;
 879 public:
 880   typedef output_iterator_tag iterator_category;
 881   typedef void                value_type;
 882   typedef void                difference_type;
 883   typedef void                pointer;
 884   typedef void                reference;
 885
 886   ostream_iterator(ostream& __s) : _M_stream(&__s), _M_string(0) {}
 887   ostream_iterator(ostream& __s, const char* __c)
 888     : _M_stream(&__s), _M_string(__c)  {}
 889   ostream_iterator<_Tp>& operator=(const _Tp& __value) {
 890     *_M_stream << __value;
 891     if (_M_string) *_M_stream << _M_string;
 892     return *this;
 893   }
 894   ostream_iterator<_Tp>& operator*() { return *this; }
 895   ostream_iterator<_Tp>& operator++() { return *this; }
 896   ostream_iterator<_Tp>& operator++(int) { return *this; }
 897 };
 898
 899 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 900
 901 template <class _Tp>
 902 inline output_iterator_tag
 903 iterator_category(const ostream_iterator<_Tp>&) {
 904   return output_iterator_tag();
 905 }
 906
 907 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 908
 909 __STL_END_NAMESPACE
 910
 911 #endif /* __SGI_STL_INTERNAL_ITERATOR_H */
 912
 913 // Local Variables:
 914 // mode:C++
 915 // End: