libstdc++-v3/include/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   : public iterator<input_iterator_tag, _CharT,
 683                     typename _Traits::off_type, _CharT*, _CharT&>
 684 {
 685 public:
 686   typedef _CharT                           char_type;
 687   typedef _Traits                          traits_type;
 688   typedef typename _Traits::int_type       int_type;
 689   typedef basic_streambuf<_CharT, _Traits> streambuf_type;
 690   typedef basic_istream<_CharT, _Traits>   istream_type;
 691
 692 public:
 693   istreambuf_iterator(streambuf_type* __p = 0) { this->_M_init(__p); }
 694   istreambuf_iterator(istream_type& __is) { this->_M_init(__is.rdbuf()); }
 695
 696   char_type operator*() const
 697     { return _M_is_initialized ? _M_c : _M_dereference_aux(); }
 698
 699   istreambuf_iterator& operator++() { this->_M_nextc(); return *this; }
 700   istreambuf_iterator  operator++(int) {
 701     if (!_M_is_initialized)
 702       _M_postincr_aux();
 703     istreambuf_iterator __tmp = *this;
 704     this->_M_nextc();
 705     return __tmp;
 706   }
 707
 708   bool equal(const istreambuf_iterator& __i) const {
 709     return this->_M_is_initialized && __i._M_is_initialized
 710       ? this->_M_eof == __i._M_eof
 711       : this->_M_equal_aux(__i);
 712   }
 713
 714 private:
 715   void _M_init(streambuf_type* __p) {
 716     _M_buf = __p;
 717     _M_eof = !__p;
 718     _M_is_initialized = _M_eof;
 719   }
 720
 721   char_type _M_dereference_aux() const;
 722   bool _M_equal_aux(const istreambuf_iterator&) const;
 723   void _M_postincr_aux();
 724
 725   void _M_nextc() {
 726     int_type __c = _M_buf->snextc();
 727     _M_c = traits_type::to_char_type(__c);
 728     _M_eof = traits_type::eq_int_type(__c, traits_type::eof());
 729     _M_is_initialized = true;
 730   }
 731
 732   void _M_getc() const {
 733     int_type __c = _M_buf->sgetc();
 734     _M_c = traits_type::to_char_type(__c);
 735     _M_eof = traits_type::eq_int_type(__c, traits_type::eof());
 736     _M_is_initialized = true;
 737   }
 738
 739 private:
 740   streambuf_type* _M_buf;
 741   mutable _CharT _M_c;
 742   mutable bool _M_eof : 1;
 743   mutable bool _M_is_initialized : 1;
 744 };
 745
 746 template<class _CharT, class _Traits>
 747 _CharT istreambuf_iterator<_CharT, _Traits>::_M_dereference_aux() const
 748 {
 749   this->_M_getc();
 750   return _M_c;
 751 }
 752
 753 template<class _CharT, class _Traits>
 754 bool istreambuf_iterator<_CharT, _Traits>
 755   ::_M_equal_aux(const istreambuf_iterator& __i) const
 756 {
 757   if (!this->_M_is_initialized)
 758     this->_M_getc();
 759   if (!__i._M_is_initialized)
 760     __i._M_getc();
 761
 762   return this->_M_eof == __i._M_eof;
 763 }
 764
 765 template<class _CharT, class _Traits>
 766 void istreambuf_iterator<_CharT, _Traits>::_M_postincr_aux()
 767 {
 768   this->_M_getc();
 769 }
 770
 771 template<class _CharT, class _Traits>
 772 inline bool operator==(const istreambuf_iterator<_CharT, _Traits>& __x,
 773                        const istreambuf_iterator<_CharT, _Traits>& __y) {
 774   return __x.equal(__y);
 775 }
 776
 777 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 778
 779 template<class _CharT, class _Traits>
 780 inline bool operator!=(const istreambuf_iterator<_CharT, _Traits>& __x,
 781                        const istreambuf_iterator<_CharT, _Traits>& __y) {
 782   return !__x.equal(__y);
 783 }
 784
 785 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 786
 787 // The default template argument is declared in iosfwd
 788 template<class _CharT, class _Traits>
 789 class ostreambuf_iterator
 790   : public iterator<output_iterator_tag, void, void, void, void>
 791 {
 792 public:
 793   typedef _CharT                           char_type;
 794   typedef _Traits                          traits_type;
 795   typedef typename _Traits::int_type       int_type;
 796   typedef basic_streambuf<_CharT, _Traits> streambuf_type;
 797   typedef basic_ostream<_CharT, _Traits>   ostream_type;
 798
 799 public:
 800   ostreambuf_iterator(streambuf_type* __buf) : _M_buf(__buf), _M_ok(__buf) {}
 801   ostreambuf_iterator(ostream_type& __o)
 802     : _M_buf(__o.rdbuf()), _M_ok(__o.rdbuf() != 0) {}
 803
 804   ostreambuf_iterator& operator=(char_type __c) {
 805     _M_ok = _M_ok && !traits_type::eq_int_type(_M_buf->sputc(__c),
 806                                                traits_type::eof());
 807     return *this;
 808   }
 809
 810   ostreambuf_iterator& operator*()     { return *this; }
 811   ostreambuf_iterator& operator++()    { return *this; }
 812   ostreambuf_iterator& operator++(int) { return *this; }
 813
 814   bool failed() const { return !_M_ok; }
 815
 816 private:
 817   streambuf_type* _M_buf;
 818   bool _M_ok;
 819 };
 820
 821 #else /* __STL_USE_NEW_IOSTREAMS */
 822
 823 template <class _Tp, class _Dist = ptrdiff_t> class istream_iterator;
 824
 825 template <class _Tp, class _Dist>
 826 inline bool operator==(const istream_iterator<_Tp, _Dist>&,
 827                        const istream_iterator<_Tp, _Dist>&);
 828
 829 template <class _Tp, class _Dist>
 830 class istream_iterator {
 831 #ifdef __STL_TEMPLATE_FRIENDS
 832   template <class _T1, class _D1>
 833   friend bool operator==(const istream_iterator<_T1, _D1>&,
 834                          const istream_iterator<_T1, _D1>&);
 835 #else /* __STL_TEMPLATE_FRIENDS */
 836   friend bool __STD_QUALIFIER
 837   operator== __STL_NULL_TMPL_ARGS (const istream_iterator&,
 838                                    const istream_iterator&);
 839 #endif /* __STL_TEMPLATE_FRIENDS */
 840
 841 protected:
 842   istream* _M_stream;
 843   _Tp _M_value;
 844   bool _M_end_marker;
 845   void _M_read() {
 846     _M_end_marker = (*_M_stream) ? true : false;
 847     if (_M_end_marker) *_M_stream >> _M_value;
 848     _M_end_marker = (*_M_stream) ? true : false;
 849   }
 850 public:
 851   typedef input_iterator_tag  iterator_category;
 852   typedef _Tp                 value_type;
 853   typedef _Dist               difference_type;
 854   typedef const _Tp*          pointer;
 855   typedef const _Tp&          reference;
 856
 857   istream_iterator() : _M_stream(&cin), _M_end_marker(false) {}
 858   istream_iterator(istream& __s) : _M_stream(&__s) { _M_read(); }
 859   reference operator*() const { return _M_value; }
 860 #ifndef __SGI_STL_NO_ARROW_OPERATOR
 861   pointer operator->() const { return &(operator*()); }
 862 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
 863   istream_iterator<_Tp, _Dist>& operator++() {
 864     _M_read();
 865     return *this;
 866   }
 867   istream_iterator<_Tp, _Dist> operator++(int)  {
 868     istream_iterator<_Tp, _Dist> __tmp = *this;
 869     _M_read();
 870     return __tmp;
 871   }
 872 };
 873
 874 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 875
 876 template <class _Tp, class _Dist>
 877 inline input_iterator_tag
 878 iterator_category(const istream_iterator<_Tp, _Dist>&)
 879 {
 880   return input_iterator_tag();
 881 }
 882
 883 template <class _Tp, class _Dist>
 884 inline _Tp*
 885 value_type(const istream_iterator<_Tp, _Dist>&) { return (_Tp*) 0; }
 886
 887 template <class _Tp, class _Dist>
 888 inline _Dist*
 889 distance_type(const istream_iterator<_Tp, _Dist>&) { return (_Dist*)0; }
 890
 891 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 892
 893 template <class _Tp, class _Distance>
 894 inline bool operator==(const istream_iterator<_Tp, _Distance>& __x,
 895                        const istream_iterator<_Tp, _Distance>& __y) {
 896   return (__x._M_stream == __y._M_stream &&
 897           __x._M_end_marker == __y._M_end_marker) ||
 898          __x._M_end_marker == false && __y._M_end_marker == false;
 899 }
 900
 901 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 902
 903 template <class _Tp, class _Distance>
 904 inline bool operator!=(const istream_iterator<_Tp, _Distance>& __x,
 905                        const istream_iterator<_Tp, _Distance>& __y) {
 906   return !(__x == __y);
 907 }
 908
 909 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 910
 911 template <class _Tp>
 912 class ostream_iterator {
 913 protected:
 914   ostream* _M_stream;
 915   const char* _M_string;
 916 public:
 917   typedef output_iterator_tag iterator_category;
 918   typedef void                value_type;
 919   typedef void                difference_type;
 920   typedef void                pointer;
 921   typedef void                reference;
 922
 923   ostream_iterator(ostream& __s) : _M_stream(&__s), _M_string(0) {}
 924   ostream_iterator(ostream& __s, const char* __c)
 925     : _M_stream(&__s), _M_string(__c)  {}
 926   ostream_iterator<_Tp>& operator=(const _Tp& __value) {
 927     *_M_stream << __value;
 928     if (_M_string) *_M_stream << _M_string;
 929     return *this;
 930   }
 931   ostream_iterator<_Tp>& operator*() { return *this; }
 932   ostream_iterator<_Tp>& operator++() { return *this; }
 933   ostream_iterator<_Tp>& operator++(int) { return *this; }
 934 };
 935
 936 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
 937
 938 template <class _Tp>
 939 inline output_iterator_tag
 940 iterator_category(const ostream_iterator<_Tp>&) {
 941   return output_iterator_tag();
 942 }
 943
 944 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 945
 946 #endif /* __STL_USE_NEW_IOSTREAMS */
 947
 948 // This iterator adapter is 'normal' in the sense that it does not
 949 // change the semantics of any of the operators of its itererator
 950 // parameter.  Its primary purpose is to convert an iterator that is
 951 // not a class, e.g. a pointer, into an iterator that is a class.
 952 // The _Container parameter exists solely so that different containers
 953 // using this template can instantiate different types, even if the
 954 // _Iterator parameter is the same.
 955 template<typename _Iterator, typename _Container>
 956 class __normal_iterator
 957   : public iterator<iterator_traits<_Iterator>::iterator_category,
 958                     iterator_traits<_Iterator>::value_type,
 959                     iterator_traits<_Iterator>::difference_type,
 960                     iterator_traits<_Iterator>::pointer,
 961                     iterator_traits<_Iterator>::reference>
 962 {
 963
 964 protected:
 965   _Iterator _M_current;
 966
 967 public:
 968   typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
 969   typedef iterator_traits<_Iterator>                    __traits_type;
 970   typedef typename __traits_type::iterator_category     iterator_category;
 971   typedef typename __traits_type::value_type            value_type;
 972   typedef typename __traits_type::difference_type       difference_type;
 973   typedef typename __traits_type::pointer               pointer;
 974   typedef typename __traits_type::reference             reference;
 975
 976   __normal_iterator() : _M_current(_Iterator()) { }
 977
 978   explicit __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
 979
 980   // Allow iterator to const_iterator conversion
 981   template<typename _Iter>
 982   inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
 983     : _M_current(__i.base()) { }
 984
 985   // Forward iterator requirements
 986   reference
 987   operator*() const { return *_M_current; }
 988
 989   pointer
 990   operator->() const { return _M_current; }
 991
 992   normal_iterator_type&
 993   operator++() { ++_M_current; return *this; }
 994
 995   normal_iterator_type
 996   operator++(int) { return __normal_iterator(_M_current++); }
 997
 998   // Bidirectional iterator requirements
 999   normal_iterator_type&
1000   operator--() { --_M_current; return *this; }
1001
1002   normal_iterator_type
1003   operator--(int) { return __normal_iterator(_M_current--); }
1004
1005   // Random access iterator requirements
1006   reference
1007   operator[](const difference_type& __n) const
1008   { return _M_current[__n]; }
1009
1010   normal_iterator_type&
1011   operator+=(const difference_type& __n)
1012   { _M_current += __n; return *this; }
1013
1014   normal_iterator_type
1015   operator+(const difference_type& __n) const
1016   { return __normal_iterator(_M_current + __n); }
1017
1018   normal_iterator_type&
1019   operator-=(const difference_type& __n)
1020   { _M_current -= __n; return *this; }
1021
1022   normal_iterator_type
1023   operator-(const difference_type& __n) const
1024   { return __normal_iterator(_M_current - __n); }
1025
1026   difference_type
1027   operator-(const normal_iterator_type& __i) const
1028   { return _M_current - __i._M_current; }
1029
1030   const _Iterator&
1031   base() const { return _M_current; }
1032 };
1033
1034 // forward iterator requirements
1035
1036 template<typename _IteratorL, typename _IteratorR, typename _Container>
1037 inline bool
1038 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1039            const __normal_iterator<_IteratorR, _Container>& __rhs)
1040 { return __lhs.base() == __rhs.base(); }
1041
1042 template<typename _IteratorL, typename _IteratorR, typename _Container>
1043 inline bool
1044 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1045            const __normal_iterator<_IteratorR, _Container>& __rhs)
1046 { return !(__lhs == __rhs); }
1047
1048 // random access iterator requirements
1049
1050 template<typename _IteratorL, typename _IteratorR, typename _Container>
1051 inline bool
1052 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
1053           const __normal_iterator<_IteratorR, _Container>& __rhs)
1054 { return __lhs.base() < __rhs.base(); }
1055
1056 template<typename _IteratorL, typename _IteratorR, typename _Container>
1057 inline bool
1058 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1059           const __normal_iterator<_IteratorR, _Container>& __rhs)
1060 { return __rhs < __lhs; }
1061
1062 template<typename _IteratorL, typename _IteratorR, typename _Container>
1063 inline bool
1064 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1065            const __normal_iterator<_IteratorR, _Container>& __rhs)
1066 { return !(__rhs < __lhs); }
1067
1068 template<typename _IteratorL, typename _IteratorR, typename _Container>
1069 inline bool
1070 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1071            const __normal_iterator<_IteratorR, _Container>& __rhs)
1072 { return !(__lhs < __rhs); }
1073
1074 template<typename _Iterator, typename _Container>
1075 inline __normal_iterator<_Iterator, _Container>
1076 operator+(__normal_iterator<_Iterator, _Container>::difference_type __n,
1077           const __normal_iterator<_Iterator, _Container>& __i)
1078 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1079
1080 __STL_END_NAMESPACE
1081
1082 #endif /* __SGI_STL_INTERNAL_ITERATOR_H */
1083
1084 // Local Variables:
1085 // mode:C++
1086 // End: