libstdc++-v3/bits/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
  37 template <class _Container>
  38 class back_insert_iterator {
  39 protected:
  40   _Container* container;
  41 public:
  42   typedef _Container          container_type;
  43   typedef output_iterator_tag iterator_category;
  44   typedef void                value_type;
  45   typedef void                difference_type;
  46   typedef void                pointer;
  47   typedef void                reference;
  48
  49   explicit back_insert_iterator(_Container& __x) : container(&__x) {}
  50   back_insert_iterator<_Container>&
  51   operator=(const typename _Container::value_type& __value) {
  52     container->push_back(__value);
  53     return *this;
  54   }
  55   back_insert_iterator<_Container>& operator*() { return *this; }
  56   back_insert_iterator<_Container>& operator++() { return *this; }
  57   back_insert_iterator<_Container>& operator++(int) { return *this; }
  58 };
  59
  60 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  61
  62 template <class _Container>
  63 inline output_iterator_tag
  64 iterator_category(const back_insert_iterator<_Container>&)
  65 {
  66   return output_iterator_tag();
  67 }
  68
  69 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  70
  71 template <class _Container>
  72 inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
  73   return back_insert_iterator<_Container>(__x);
  74 }
  75
  76 template <class _Container>
  77 class front_insert_iterator {
  78 protected:
  79   _Container* container;
  80 public:
  81   typedef _Container          container_type;
  82   typedef output_iterator_tag iterator_category;
  83   typedef void                value_type;
  84   typedef void                difference_type;
  85   typedef void                pointer;
  86   typedef void                reference;
  87
  88   explicit front_insert_iterator(_Container& __x) : container(&__x) {}
  89   front_insert_iterator<_Container>&
  90   operator=(const typename _Container::value_type& __value) {
  91     container->push_front(__value);
  92     return *this;
  93   }
  94   front_insert_iterator<_Container>& operator*() { return *this; }
  95   front_insert_iterator<_Container>& operator++() { return *this; }
  96   front_insert_iterator<_Container>& operator++(int) { return *this; }
  97 };
  98
  99 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 100
 101 template <class _Container>
 102 inline output_iterator_tag
 103 iterator_category(const front_insert_iterator<_Container>&)
 104 {
 105   return output_iterator_tag();
 106 }
 107
 108 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 109
 110 template <class _Container>
 111 inline front_insert_iterator<_Container> front_inserter(_Container& __x) {
 112   return front_insert_iterator<_Container>(__x);
 113 }
 114
 115 template <class _Container>
 116 class insert_iterator {
 117 protected:
 118   _Container* container;
 119   typename _Container::iterator iter;
 120 public:
 121   typedef _Container          container_type;
 122   typedef output_iterator_tag iterator_category;
 123   typedef void                value_type;
 124   typedef void                difference_type;
 125   typedef void                pointer;
 126   typedef void                reference;
 127
 128   insert_iterator(_Container& __x, typename _Container::iterator __i)
 129     : container(&__x), iter(__i) {}
 130   insert_iterator<_Container>&
 131   operator=(const typename _Container::value_type& __value) {
 132     iter = container->insert(iter, __value);
 133     ++iter;
 134     return *this;
 135   }
 136   insert_iterator<_Container>& operator*() { return *this; }
 137   insert_iterator<_Container>& operator++() { return *this; }
 138   insert_iterator<_Container>& operator++(int) { return *this; }
 139 };
 140
 141 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 142
 143 template <class _Container>
 144 inline output_iterator_tag
 145 iterator_category(const insert_iterator<_Container>&)
 146 {
 147   return output_iterator_tag();
 148 }
 149
 150 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 151
 152 template <class _Container, class _Iterator>
 153 inline
 154 insert_iterator<_Container> inserter(_Container& __x, _Iterator __i)
 155 {
 156   typedef typename _Container::iterator __iter;
 157   return insert_iterator<_Container>(__x, __iter(__i));
 158 }
 159
 160 template <class _BidirectionalIterator, class _Tp, class _Reference = _Tp&,
 161           class _Distance = ptrdiff_t>
 162 class reverse_bidirectional_iterator {
 163   typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
 164                                          _Reference, _Distance>  _Self;
 165 protected:
 166   _BidirectionalIterator current;
 167 public:
 168   typedef bidirectional_iterator_tag iterator_category;
 169   typedef _Tp                        value_type;
 170   typedef _Distance                  difference_type;
 171   typedef _Tp*                       pointer;
 172   typedef _Reference                 reference;
 173
 174   reverse_bidirectional_iterator() {}
 175   explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
 176     : current(__x) {}
 177   _BidirectionalIterator base() const { return current; }
 178   _Reference operator*() const {
 179     _BidirectionalIterator __tmp = current;
 180     return *--__tmp;
 181   }
 182 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 183   pointer operator->() const { return &(operator*()); }
 184 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 185   _Self& operator++() {
 186     --current;
 187     return *this;
 188   }
 189   _Self operator++(int) {
 190     _Self __tmp = *this;
 191     --current;
 192     return __tmp;
 193   }
 194   _Self& operator--() {
 195     ++current;
 196     return *this;
 197   }
 198   _Self operator--(int) {
 199     _Self __tmp = *this;
 200     ++current;
 201     return __tmp;
 202   }
 203 };
 204
 205 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 206
 207 template <class _BidirectionalIterator, class _Tp, class _Reference,
 208           class _Distance>
 209 inline bidirectional_iterator_tag
 210 iterator_category(const reverse_bidirectional_iterator<_BidirectionalIterator,
 211                                                        _Tp, _Reference,
 212                                                        _Distance>&)
 213 {
 214   return bidirectional_iterator_tag();
 215 }
 216
 217 template <class _BidirectionalIterator, class _Tp, class _Reference,
 218           class _Distance>
 219 inline _Tp*
 220 value_type(const reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
 221                                                _Reference, _Distance>&)
 222 {
 223   return (_Tp*) 0;
 224 }
 225
 226 template <class _BidirectionalIterator, class _Tp, class _Reference,
 227           class _Distance>
 228 inline _Distance*
 229 distance_type(const reverse_bidirectional_iterator<_BidirectionalIterator,
 230                                                    _Tp,
 231                                                    _Reference, _Distance>&)
 232 {
 233   return (_Distance*) 0;
 234 }
 235
 236 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 237
 238 template <class _BiIter, class _Tp, class _Ref, class _Distance>
 239 inline bool operator==(
 240     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
 241     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
 242 {
 243   return __x.base() == __y.base();
 244 }
 245
 246 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 247
 248 template <class _BiIter, class _Tp, class _Ref, class _Distance>
 249 inline bool operator!=(
 250     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
 251     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
 252 {
 253   return !(__x == __y);
 254 }
 255
 256 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 257
 258
 259 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 260
 261 // This is the new version of reverse_iterator, as defined in the
 262 //  draft C++ standard.  It relies on the iterator_traits template,
 263 //  which in turn relies on partial specialization.  The class
 264 //  reverse_bidirectional_iterator is no longer part of the draft
 265 //  standard, but it is retained for backward compatibility.
 266
 267 template <class _Iterator>
 268 class reverse_iterator
 269 {
 270 protected:
 271   _Iterator current;
 272 public:
 273   typedef typename iterator_traits<_Iterator>::iterator_category
 274           iterator_category;
 275   typedef typename iterator_traits<_Iterator>::value_type
 276           value_type;
 277   typedef typename iterator_traits<_Iterator>::difference_type
 278           difference_type;
 279   typedef typename iterator_traits<_Iterator>::pointer
 280           pointer;
 281   typedef typename iterator_traits<_Iterator>::reference
 282           reference;
 283
 284   typedef _Iterator iterator_type;
 285   typedef reverse_iterator<_Iterator> _Self;
 286
 287 public:
 288   reverse_iterator() {}
 289   explicit reverse_iterator(iterator_type __x) : current(__x) {}
 290
 291   reverse_iterator(const _Self& __x) : current(__x.current) {}
 292 #ifdef __STL_MEMBER_TEMPLATES
 293   template <class _Iter>
 294   reverse_iterator(const reverse_iterator<_Iter>& __x)
 295     : current(__x.base()) {}
 296 #endif /* __STL_MEMBER_TEMPLATES */
 297
 298   iterator_type base() const { return current; }
 299   reference operator*() const {
 300     _Iterator __tmp = current;
 301     return *--__tmp;
 302   }
 303 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 304   pointer operator->() const { return &(operator*()); }
 305 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 306
 307   _Self& operator++() {
 308     --current;
 309     return *this;
 310   }
 311   _Self operator++(int) {
 312     _Self __tmp = *this;
 313     --current;
 314     return __tmp;
 315   }
 316   _Self& operator--() {
 317     ++current;
 318     return *this;
 319   }
 320   _Self operator--(int) {
 321     _Self __tmp = *this;
 322     ++current;
 323     return __tmp;
 324   }
 325
 326   _Self operator+(difference_type __n) const {
 327     return _Self(current - __n);
 328   }
 329   _Self& operator+=(difference_type __n) {
 330     current -= __n;
 331     return *this;
 332   }
 333   _Self operator-(difference_type __n) const {
 334     return _Self(current + __n);
 335   }
 336   _Self& operator-=(difference_type __n) {
 337     current += __n;
 338     return *this;
 339   }
 340   reference operator[](difference_type __n) const { return *(*this + __n); }
 341 };
 342
 343 template <class _Iterator>
 344 inline bool operator==(const reverse_iterator<_Iterator>& __x,
 345                        const reverse_iterator<_Iterator>& __y) {
 346   return __x.base() == __y.base();
 347 }
 348
 349 template <class _Iterator>
 350 inline bool operator<(const reverse_iterator<_Iterator>& __x,
 351                       const reverse_iterator<_Iterator>& __y) {
 352   return __y.base() < __x.base();
 353 }
 354
 355 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 356
 357 template <class _Iterator>
 358 inline bool operator!=(const reverse_iterator<_Iterator>& __x,
 359                        const reverse_iterator<_Iterator>& __y) {
 360   return !(__x == __y);
 361 }
 362
 363 template <class _Iterator>
 364 inline bool operator>(const reverse_iterator<_Iterator>& __x,
 365                       const reverse_iterator<_Iterator>& __y) {
 366   return __y < __x;
 367 }
 368
 369 template <class _Iterator>
 370 inline bool operator<=(const reverse_iterator<_Iterator>& __x,
 371                        const reverse_iterator<_Iterator>& __y) {
 372   return !(__y < __x);
 373 }
 374
 375 template <class _Iterator>
 376 inline bool operator>=(const reverse_iterator<_Iterator>& __x,
 377                       const reverse_iterator<_Iterator>& __y) {
 378   return !(__x < __y);
 379 }
 380
 381 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 382
 383 template <class _Iterator>
 384 inline typename reverse_iterator<_Iterator>::difference_type
 385 operator-(const reverse_iterator<_Iterator>& __x,
 386           const reverse_iterator<_Iterator>& __y) {
 387   return __y.base() - __x.base();
 388 }
 389
 390 template <class _Iterator>
 391 inline reverse_iterator<_Iterator>
 392 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
 393           const reverse_iterator<_Iterator>& __x) {
 394   return reverse_iterator<_Iterator>(__x.base() - __n);
 395 }
 396
 397 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 398
 399 // This is the old version of reverse_iterator, as found in the original
 400 //  HP STL.  It does not use partial specialization.
 401
 402 template <class _RandomAccessIterator, class _Tp, class _Reference = _Tp&,
 403           class _Distance = ptrdiff_t>
 404 class reverse_iterator {
 405   typedef reverse_iterator<_RandomAccessIterator, _Tp, _Reference, _Distance>
 406         _Self;
 407 protected:
 408   _RandomAccessIterator current;
 409 public:
 410   typedef random_access_iterator_tag iterator_category;
 411   typedef _Tp                        value_type;
 412   typedef _Distance                  difference_type;
 413   typedef _Tp*                       pointer;
 414   typedef _Reference                 reference;
 415
 416   reverse_iterator() {}
 417   explicit reverse_iterator(_RandomAccessIterator __x) : current(__x) {}
 418   _RandomAccessIterator base() const { return current; }
 419   _Reference operator*() const { return *(current - 1); }
 420 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 421   pointer operator->() const { return &(operator*()); }
 422 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 423   _Self& operator++() {
 424     --current;
 425     return *this;
 426   }
 427   _Self operator++(int) {
 428     _Self __tmp = *this;
 429     --current;
 430     return __tmp;
 431   }
 432   _Self& operator--() {
 433     ++current;
 434     return *this;
 435   }
 436   _Self operator--(int) {
 437     _Self __tmp = *this;
 438     ++current;
 439     return __tmp;
 440   }
 441   _Self operator+(_Distance __n) const {
 442     return _Self(current - __n);
 443   }
 444   _Self& operator+=(_Distance __n) {
 445     current -= __n;
 446     return *this;
 447   }
 448   _Self operator-(_Distance __n) const {
 449     return _Self(current + __n);
 450   }
 451   _Self& operator-=(_Distance __n) {
 452     current += __n;
 453     return *this;
 454   }
 455   _Reference operator[](_Distance __n) const { return *(*this + __n); }
 456 };
 457
 458 template <class _RandomAccessIterator, class _Tp,
 459           class _Reference, class _Distance>
 460 inline random_access_iterator_tag
 461 iterator_category(const reverse_iterator<_RandomAccessIterator, _Tp,
 462                                          _Reference, _Distance>&)
 463 {
 464   return random_access_iterator_tag();
 465 }
 466
 467 template <class _RandomAccessIterator, class _Tp,
 468           class _Reference, class _Distance>
 469 inline _Tp* value_type(const reverse_iterator<_RandomAccessIterator, _Tp,
 470                                               _Reference, _Distance>&)
 471 {
 472   return (_Tp*) 0;
 473 }
 474
 475 template <class _RandomAccessIterator, class _Tp,
 476           class _Reference, class _Distance>
 477 inline _Distance*
 478 distance_type(const reverse_iterator<_RandomAccessIterator,
 479                                      _Tp, _Reference, _Distance>&)
 480 {
 481   return (_Distance*) 0;
 482 }
 483
 484
 485 template <class _RandomAccessIterator, class _Tp,
 486           class _Reference, class _Distance>
 487 inline bool
 488 operator==(const reverse_iterator<_RandomAccessIterator, _Tp,
 489                                   _Reference, _Distance>& __x,
 490            const reverse_iterator<_RandomAccessIterator, _Tp,
 491                                   _Reference, _Distance>& __y)
 492 {
 493   return __x.base() == __y.base();
 494 }
 495
 496 template <class _RandomAccessIterator, class _Tp,
 497           class _Reference, class _Distance>
 498 inline bool
 499 operator<(const reverse_iterator<_RandomAccessIterator, _Tp,
 500                                  _Reference, _Distance>& __x,
 501           const reverse_iterator<_RandomAccessIterator, _Tp,
 502                                  _Reference, _Distance>& __y)
 503 {
 504   return __y.base() < __x.base();
 505 }
 506
 507 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 508
 509 template <class _RandomAccessIterator, class _Tp,
 510           class _Reference, class _Distance>
 511 inline bool
 512 operator!=(const reverse_iterator<_RandomAccessIterator, _Tp,
 513                                   _Reference, _Distance>& __x,
 514            const reverse_iterator<_RandomAccessIterator, _Tp,
 515                                   _Reference, _Distance>& __y) {
 516   return !(__x == __y); }
 517 }
 518
 519 template <class _RandomAccessIterator, class _Tp,
 520           class _Reference, class _Distance>
 521 inline bool
 522 operator>(const reverse_iterator<_RandomAccessIterator, _Tp,
 523                                  _Reference, _Distance>& __x,
 524           const reverse_iterator<_RandomAccessIterator, _Tp,
 525                                  _Reference, _Distance>& __y) {
 526   return __y < __x;
 527 }
 528
 529 template <class _RandomAccessIterator, class _Tp,
 530           class _Reference, class _Distance>
 531 inline bool
 532 operator<=(const reverse_iterator<_RandomAccessIterator, _Tp,
 533                                   _Reference, _Distance>& __x,
 534            const reverse_iterator<_RandomAccessIterator, _Tp,
 535                                   _Reference, _Distance>& __y) {
 536   return !(__y < __x);
 537 }
 538
 539 template <class _RandomAccessIterator, class _Tp,
 540           class _Reference, class _Distance>
 541 inline bool
 542 operator>=(const reverse_iterator<_RandomAccessIterator, _Tp,
 543                                   _Reference, _Distance>& __x,
 544            const reverse_iterator<_RandomAccessIterator, _Tp,
 545                                   _Reference, _Distance>& __y) {
 546   return !(__x < __y);
 547 }
 548
 549 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 550
 551 template <class _RandomAccessIterator, class _Tp,
 552           class _Reference, class _Distance>
 553 inline _Distance
 554 operator-(const reverse_iterator<_RandomAccessIterator, _Tp,
 555                                  _Reference, _Distance>& __x,
 556           const reverse_iterator<_RandomAccessIterator, _Tp,
 557                                  _Reference, _Distance>& __y)
 558 {
 559   return __y.base() - __x.base();
 560 }
 561
 562 template <class _RandAccIter, class _Tp, class _Ref, class _Dist>
 563 inline reverse_iterator<_RandAccIter, _Tp, _Ref, _Dist>
 564 operator+(_Dist __n,
 565           const reverse_iterator<_RandAccIter, _Tp, _Ref, _Dist>& __x)
 566 {
 567   return reverse_iterator<_RandAccIter, _Tp, _Ref, _Dist>(__x.base() - __n);
 568 }
 569
 570 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 571
 572 // istream_iterator and ostream_iterator look very different if we're
 573 // using new, templatized iostreams than if we're using the old cfront
 574 // version.
 575
 576 #ifdef __STL_USE_NEW_IOSTREAMS
 577
 578 template <class _Tp,
 579           class _CharT = char, class _Traits = char_traits<_CharT>,
 580           class _Dist = ptrdiff_t>
 581 class istream_iterator {
 582 public:
 583   typedef _CharT                         char_type;
 584   typedef _Traits                        traits_type;
 585   typedef basic_istream<_CharT, _Traits> istream_type;
 586
 587   typedef input_iterator_tag             iterator_category;
 588   typedef _Tp                            value_type;
 589   typedef _Dist                          difference_type;
 590   typedef const _Tp*                     pointer;
 591   typedef const _Tp&                     reference;
 592
 593   istream_iterator() : _M_stream(0), _M_ok(false) {}
 594   istream_iterator(istream_type& __s) : _M_stream(&__s) { _M_read(); }
 595
 596   reference operator*() const { return _M_value; }
 597   pointer operator->() const { return &(operator*()); }
 598
 599   istream_iterator& operator++() {
 600     _M_read();
 601     return *this;
 602   }
 603   istream_iterator operator++(int)  {
 604     istream_iterator __tmp = *this;
 605     _M_read();
 606     return __tmp;
 607   }
 608
 609   bool _M_equal(const istream_iterator& __x) const
 610     { return (_M_ok == __x._M_ok) && (!_M_ok || _M_stream == __x._M_stream); }
 611
 612 private:
 613   istream_type* _M_stream;
 614   _Tp _M_value;
 615   bool _M_ok;
 616
 617   void _M_read() {
 618     _M_ok = (_M_stream && *_M_stream) ? true : false;
 619     if (_M_ok) {
 620       *_M_stream >> _M_value;
 621       _M_ok = *_M_stream ? true : false;
 622     }
 623   }
 624 };
 625
 626 template <class _Tp, class _CharT, class _Traits, class _Dist>
 627 inline bool
 628 operator==(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
 629            const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
 630   return __x._M_equal(__y);
 631 }
 632
 633 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 634
 635 template <class _Tp, class _CharT, class _Traits, class _Dist>
 636 inline bool
 637 operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
 638            const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
 639   return !__x._M_equal(__y);
 640 }
 641
 642 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 643
 644 template <class _Tp,
 645           class _CharT = char, class _Traits = char_traits<_CharT> >
 646 class ostream_iterator {
 647 public:
 648   typedef _CharT                         char_type;
 649   typedef _Traits                        traits_type;
 650   typedef basic_ostream<_CharT, _Traits> ostream_type;
 651
 652   typedef output_iterator_tag            iterator_category;
 653   typedef void                           value_type;
 654   typedef void                           difference_type;
 655   typedef void                           pointer;
 656   typedef void                           reference;
 657
 658   ostream_iterator(ostream_type& __s) : _M_stream(&__s), _M_string(0) {}
 659   ostream_iterator(ostream_type& __s, const _CharT* __c)
 660     : _M_stream(&__s), _M_string(__c)  {}
 661   ostream_iterator<_Tp>& operator=(const _Tp& __value) {
 662     *_M_stream << __value;
 663     if (_M_string) *_M_stream << _M_string;
 664     return *this;
 665   }
 666   ostream_iterator<_Tp>& operator*() { return *this; }
 667   ostream_iterator<_Tp>& operator++() { return *this; }
 668   ostream_iterator<_Tp>& operator++(int) { return *this; }
 669 private:
 670   ostream_type* _M_stream;
 671   const _CharT* _M_string;
 672 };
 673
 674 // The default template argument is declared in iosfwd
 675
 676 // We do not read any characters until operator* is called.  The first
 677 // time operator* is called, it calls getc.  Subsequent calls to getc
 678 // return a cached character, and calls to operator++ use snextc.  Before
 679 // operator* or operator++ has been called, _M_is_initialized is false.
 680 template<class _CharT, class _Traits>
 681 class istreambuf_iterator
 682 {
 683 public:
 684   typedef _CharT                           char_type;
 685   typedef _Traits                          traits_type;
 686   typedef typename _Traits::int_type       int_type;
 687   typedef basic_streambuf<_CharT, _Traits> streambuf_type;
 688   typedef basic_istream<_CharT, _Traits>   istream_type;
 689
 690   typedef input_iterator_tag               iterator_category;
 691   typedef _CharT                           value_type;
 692   typedef typename _Traits::off_type       difference_type;
 693   typedef const _CharT*                    pointer;
 694   typedef const _CharT&                    reference;
 695
 696 public:
 697   istreambuf_iterator(streambuf_type* __p = 0) { this->_M_init(__p); }
 698   istreambuf_iterator(istream_type& __is) { this->_M_init(__is.rdbuf()); }
 699
 700   char_type operator*() const
 701     { return _M_is_initialized ? _M_c : _M_dereference_aux(); }
 702
 703   istreambuf_iterator& operator++() { this->_M_nextc(); return *this; }
 704   istreambuf_iterator  operator++(int) {
 705     if (!_M_is_initialized)
 706       _M_postincr_aux();
 707     istreambuf_iterator __tmp = *this;
 708     this->_M_nextc();
 709     return __tmp;
 710   }
 711
 712   bool equal(const istreambuf_iterator& __i) const {
 713     return this->_M_is_initialized && __i._M_is_initialized
 714       ? this->_M_eof == __i._M_eof
 715       : this->_M_equal_aux(__i);
 716   }
 717
 718 private:
 719   void _M_init(streambuf_type* __p) {
 720     _M_buf = __p;
 721     _M_eof = !__p;
 722     _M_is_initialized = _M_eof;
 723   }
 724
 725   char_type _M_dereference_aux() const;
 726   bool _M_equal_aux(const istreambuf_iterator&) const;
 727   void _M_postincr_aux();
 728
 729   void _M_nextc() {
 730     int_type __c = _M_buf->snextc();
 731     _M_c = traits_type::to_char_type(__c);
 732     _M_eof = traits_type::eq_int_type(__c, traits_type::eof());
 733     _M_is_initialized = true;
 734   }
 735
 736   void _M_getc() const {
 737     int_type __c = _M_buf->sgetc();
 738     _M_c = traits_type::to_char_type(__c);
 739     _M_eof = traits_type::eq_int_type(__c, traits_type::eof());
 740     _M_is_initialized = true;
 741   }
 742
 743 private:
 744   streambuf_type* _M_buf;
 745   mutable _CharT _M_c;
 746   mutable bool _M_eof : 1;
 747   mutable bool _M_is_initialized : 1;
 748 };
 749
 750 template<class _CharT, class _Traits>
 751 _CharT istreambuf_iterator<_CharT, _Traits>::_M_dereference_aux() const
 752 {
 753   this->_M_getc();
 754   return _M_c;
 755 }
 756
 757 template<class _CharT, class _Traits>
 758 bool istreambuf_iterator<_CharT, _Traits>
 759   ::_M_equal_aux(const istreambuf_iterator& __i) const
 760 {
 761   if (!this->_M_is_initialized)
 762     this->_M_getc();
 763   if (!__i._M_is_initialized)
 764     __i._M_getc();
 765
 766   return this->_M_eof == __i._M_eof;
 767 }
 768
 769 template<class _CharT, class _Traits>
 770 void istreambuf_iterator<_CharT, _Traits>::_M_postincr_aux()
 771 {
 772   this->_M_getc();
 773 }
 774
 775 template<class _CharT, class _Traits>
 776 inline bool operator==(const istreambuf_iterator<_CharT, _Traits>& __x,
 777                        const istreambuf_iterator<_CharT, _Traits>& __y) {
 778   return __x.equal(__y);
 779 }
 780
 781 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 782
 783 template<class _CharT, class _Traits>
 784 inline bool operator!=(const istreambuf_iterator<_CharT, _Traits>& __x,
 785                        const istreambuf_iterator<_CharT, _Traits>& __y) {
 786   return !__x.equal(__y);
 787 }
 788
 789 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 790
 791 // The default template argument is declared in iosfwd
 792 template<class _CharT, class _Traits>
 793 class ostreambuf_iterator
 794 {
 795 public:
 796   typedef _CharT                           char_type;
 797   typedef _Traits                          traits_type;
 798   typedef typename _Traits::int_type       int_type;
 799   typedef basic_streambuf<_CharT, _Traits> streambuf_type;
 800   typedef basic_ostream<_CharT, _Traits>   ostream_type;
 801
 802   typedef output_iterator_tag              iterator_category;
 803   typedef void                             value_type;
 804   typedef void                             difference_type;
 805   typedef void                             pointer;
 806   typedef void                             reference;
 807
 808 public:
 809   ostreambuf_iterator(streambuf_type* __buf) : _M_buf(__buf), _M_ok(__buf) {}
 810   ostreambuf_iterator(ostream_type& __o)
 811     : _M_buf(__o.rdbuf()), _M_ok(__o.rdbuf()) {}
 812
 813   ostreambuf_iterator& operator=(char_type __c) {
 814     _M_ok = _M_ok && !traits_type::eq_int_type(_M_buf->sputc(__c),
 815                                                traits_type::eof());
 816     return *this;
 817   }
 818
 819   ostreambuf_iterator& operator*()     { return *this; }
 820   ostreambuf_iterator& operator++()    { return *this; }
 821   ostreambuf_iterator& operator++(int) { return *this; }
 822
 823   bool failed() const { return !_M_ok; }
 824
 825 private:
 826   streambuf_type* _M_buf;
 827   bool _M_ok;
 828 };
 829
 830 #else /* __STL_USE_NEW_IOSTREAMS */
 831
 832 template <class _Tp, class _Dist = ptrdiff_t> class istream_iterator;
 833
 834 template <class _Tp, class _Dist>
 835 inline bool operator==(const istream_iterator<_Tp, _Dist>&,
 836                        const istream_iterator<_Tp, _Dist>&);
 837
 838 template <class _Tp, class _Dist>
 839 class istream_iterator {
 840 #ifdef __STL_MEMBER_TEMPLATES
 841   template <class _T1, class _D1>
 842   friend bool operator==(const istream_iterator<_T1, _D1>&,
 843                          const istream_iterator<_T1, _D1>&);
 844 #else /* __STL_MEMBER_TEMPLATES */
 845   friend bool __STD_QUALIFIER
 846   operator== __STL_NULL_TMPL_ARGS (const istream_iterator&,
 847                                    const istream_iterator&);
 848 #endif /* __STL_MEMBER_TEMPLATES */
 849
 850 protected:
 851   istream* _M_stream;
 852   _Tp _M_value;
 853   bool _M_end_marker;
 854   void _M_read() {
 855     _M_end_marker = (*_M_stream) ? true : false;
 856     if (_M_end_marker) *_M_stream >> _M_value;
 857     _M_end_marker = (*_M_stream) ? true : false;
 858   }
 859 public:
 860   typedef input_iterator_tag  iterator_category;
 861   typedef _Tp                 value_type;
 862   typedef _Dist               difference_type;
 863   typedef const _Tp*          pointer;
 864   typedef const _Tp&          reference;
 865
 866   istream_iterator() : _M_stream(&cin), _M_end_marker(false) {}
 867   istream_iterator(istream& __s) : _M_stream(&__s) { _M_read(); }
 868   reference operator*() const { return _M_value; }
 869 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 870   pointer operator->() const { return &(operator*()); }
 871 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 872   istream_iterator<_Tp, _Dist>& operator++() {
 873     _M_read();
 874     return *this;
 875   }
 876   istream_iterator<_Tp, _Dist> operator++(int)  {
 877     istream_iterator<_Tp, _Dist> __tmp = *this;
 878     _M_read();
 879     return __tmp;
 880   }
 881 };
 882
 883 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 884
 885 template <class _Tp, class _Dist>
 886 inline input_iterator_tag
 887 iterator_category(const istream_iterator<_Tp, _Dist>&)
 888 {
 889   return input_iterator_tag();
 890 }
 891
 892 template <class _Tp, class _Dist>
 893 inline _Tp*
 894 value_type(const istream_iterator<_Tp, _Dist>&) { return (_Tp*) 0; }
 895
 896 template <class _Tp, class _Dist>
 897 inline _Dist*
 898 distance_type(const istream_iterator<_Tp, _Dist>&) { return (_Dist*)0; }
 899
 900 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 901
 902 template <class _Tp, class _Distance>
 903 inline bool operator==(const istream_iterator<_Tp, _Distance>& __x,
 904                        const istream_iterator<_Tp, _Distance>& __y) {
 905   return (__x._M_stream == __y._M_stream &&
 906           __x._M_end_marker == __y._M_end_marker) ||
 907          __x._M_end_marker == false && __y._M_end_marker == false;
 908 }
 909
 910 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 911
 912 template <class _Tp, class _Distance>
 913 inline bool operator!=(const istream_iterator<_Tp, _Distance>& __x,
 914                        const istream_iterator<_Tp, _Distance>& __y) {
 915   return !(__x == __y);
 916 }
 917
 918 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 919
 920 template <class _Tp>
 921 class ostream_iterator {
 922 protected:
 923   ostream* _M_stream;
 924   const char* _M_string;
 925 public:
 926   typedef output_iterator_tag iterator_category;
 927   typedef void                value_type;
 928   typedef void                difference_type;
 929   typedef void                pointer;
 930   typedef void                reference;
 931
 932   ostream_iterator(ostream& __s) : _M_stream(&__s), _M_string(0) {}
 933   ostream_iterator(ostream& __s, const char* __c)
 934     : _M_stream(&__s), _M_string(__c)  {}
 935   ostream_iterator<_Tp>& operator=(const _Tp& __value) {
 936     *_M_stream << __value;
 937     if (_M_string) *_M_stream << _M_string;
 938     return *this;
 939   }
 940   ostream_iterator<_Tp>& operator*() { return *this; }
 941   ostream_iterator<_Tp>& operator++() { return *this; }
 942   ostream_iterator<_Tp>& operator++(int) { return *this; }
 943 };
 944
 945 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 946
 947 template <class _Tp>
 948 inline output_iterator_tag
 949 iterator_category(const ostream_iterator<_Tp>&) {
 950   return output_iterator_tag();
 951 }
 952
 953 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 954
 955 #endif /* __STL_USE_NEW_IOSTREAMS */
 956
 957 // This iterator adapter is 'normal' in the sense that it does not
 958 // change the semantics of any of the operators of its itererator
 959 // parameter.  Its primary purpose is to convert an iterator that is
 960 // not a class, e.g. a pointer, into an iterator that is a class.
 961 // The _Container parameter exists solely so that different containers
 962 // using this template can instantiate different types, even if the
 963 // _Iterator parameter is the same.
 964 template<typename _Iterator, typename _Container>
 965 class __normal_iterator
 966   : public iterator<iterator_traits<_Iterator>::iterator_category,
 967                     iterator_traits<_Iterator>::value_type,
 968                     iterator_traits<_Iterator>::difference_type,
 969                     iterator_traits<_Iterator>::pointer,
 970                     iterator_traits<_Iterator>::reference>
 971 {
 972
 973 protected:
 974   _Iterator _M_current;
 975
 976 public:
 977   typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
 978   typedef iterator_traits<_Iterator>                    __traits_type;
 979   typedef typename __traits_type::iterator_category     iterator_category;
 980   typedef typename __traits_type::value_type            value_type;
 981   typedef typename __traits_type::difference_type       difference_type;
 982   typedef typename __traits_type::pointer               pointer;
 983   typedef typename __traits_type::reference             reference;
 984
 985   __normal_iterator() : _M_current(_Iterator()) { }
 986
 987   explicit __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
 988
 989   // Allow iterator to const_iterator conversion
 990   template<typename _Iter>
 991   inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
 992     : _M_current(__i.base()) { }
 993
 994   // Forward iterator requirements
 995   reference
 996   operator*() const { return *_M_current; }
 997
 998   pointer
 999   operator->() const { return _M_current; }
1000
1001   normal_iterator_type&
1002   operator++() { ++_M_current; return *this; }
1003
1004   normal_iterator_type
1005   operator++(int) { return __normal_iterator(_M_current++); }
1006
1007   // Bidirectional iterator requirements
1008   normal_iterator_type&
1009   operator--() { --_M_current; return *this; }
1010
1011   normal_iterator_type
1012   operator--(int) { return __normal_iterator(_M_current--); }
1013
1014   // Random access iterator requirements
1015   reference
1016   operator[](const difference_type& __n) const
1017   { return _M_current[__n]; }
1018
1019   normal_iterator_type&
1020   operator+=(const difference_type& __n)
1021   { _M_current += __n; return *this; }
1022
1023   normal_iterator_type
1024   operator+(const difference_type& __n) const
1025   { return __normal_iterator(_M_current + __n); }
1026
1027   normal_iterator_type&
1028   operator-=(const difference_type& __n)
1029   { _M_current -= __n; return *this; }
1030
1031   normal_iterator_type
1032   operator-(const difference_type& __n) const
1033   { return __normal_iterator(_M_current - __n); }
1034
1035   difference_type
1036   operator-(const normal_iterator_type& __i) const
1037   { return _M_current - __i._M_current; }
1038
1039   const _Iterator&
1040   base() const { return _M_current; }
1041 };
1042
1043 // forward iterator requirements
1044
1045 template<typename _IteratorL, typename _IteratorR, typename _Container>
1046 bool operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1047                 const __normal_iterator<_IteratorR, _Container>& __rhs)
1048 { return __lhs.base() == __rhs.base(); }
1049
1050 template<typename _IteratorL, typename _IteratorR, typename _Container>
1051 bool operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1052                 const __normal_iterator<_IteratorR, _Container>& __rhs)
1053 { return !(__lhs == __rhs); }
1054
1055 // random access iterator requirements
1056
1057 template<typename _IteratorL, typename _IteratorR, typename _Container>
1058 bool operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
1059                const __normal_iterator<_IteratorR, _Container>& __rhs)
1060 { return __lhs.base() < __rhs.base(); }
1061
1062 template<typename _IteratorL, typename _IteratorR, typename _Container>
1063 bool operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1064                const __normal_iterator<_IteratorR, _Container>& __rhs)
1065 { return __rhs < __lhs; }
1066
1067 template<typename _IteratorL, typename _IteratorR, typename _Container>
1068 bool operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1069                 const __normal_iterator<_IteratorR, _Container>& __rhs)
1070 { return !(__rhs < __lhs); }
1071
1072 template<typename _IteratorL, typename _IteratorR, typename _Container>
1073 bool operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1074                 const __normal_iterator<_IteratorR, _Container>& __rhs)
1075 { return !(__lhs < __rhs); }
1076
1077 template<typename _Iterator, typename _Container>
1078 inline __normal_iterator<_Iterator, _Container>
1079 operator+(__normal_iterator<_Iterator, _Container>::difference_type __n,
1080           const __normal_iterator<_Iterator, _Container>& __i)
1081 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1082
1083 __STL_END_NAMESPACE
1084
1085 #endif /* __SGI_STL_INTERNAL_ITERATOR_H */
1086
1087 // Local Variables:
1088 // mode:C++
1089 // End: