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
36struct input_iterator_tag {};
37struct output_iterator_tag {};
38struct forward_iterator_tag : public input_iterator_tag {};
39struct bidirectional_iterator_tag : public forward_iterator_tag {};
40struct 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
47template <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
55struct 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
63template <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
72template <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
80template <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
89template <class _Category, class _Tp, class _Distance = ptrdiff_t,
90          class _Pointer = _Tp*, class _Reference = _Tp&>
91struct 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
102template <class _Iterator>
103struct 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
111template <class _Tp>
112struct 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
120template <class _Tp>
121struct 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
136template <class _Iter>
137inline 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
144template <class _Iter>
145inline 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
151template <class _Iter>
152inline 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
158template <class _Iter>
159inline typename iterator_traits<_Iter>::iterator_category
160iterator_category(const _Iter& __i) { return __iterator_category(__i); }
161
162
163template <class _Iter>
164inline typename iterator_traits<_Iter>::difference_type*
165distance_type(const _Iter& __i) { return __distance_type(__i); }
166
167template <class _Iter>
168inline typename iterator_traits<_Iter>::value_type*
169value_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
177template <class _Tp, class _Distance>
178inline input_iterator_tag
179iterator_category(const input_iterator<_Tp, _Distance>&)
180  { return input_iterator_tag(); }
181
182inline output_iterator_tag iterator_category(const output_iterator&)
183  { return output_iterator_tag(); }
184
185template <class _Tp, class _Distance>
186inline forward_iterator_tag
187iterator_category(const forward_iterator<_Tp, _Distance>&)
188  { return forward_iterator_tag(); }
189
190template <class _Tp, class _Distance>
191inline bidirectional_iterator_tag
192iterator_category(const bidirectional_iterator<_Tp, _Distance>&)
193  { return bidirectional_iterator_tag(); }
194
195template <class _Tp, class _Distance>
196inline random_access_iterator_tag
197iterator_category(const random_access_iterator<_Tp, _Distance>&)
198  { return random_access_iterator_tag(); }
199
200template <class _Tp>
201inline random_access_iterator_tag iterator_category(const _Tp*)
202  { return random_access_iterator_tag(); }
203
204template <class _Tp, class _Distance>
205inline _Tp* value_type(const input_iterator<_Tp, _Distance>&)
206  { return (_Tp*)(0); }
207
208template <class _Tp, class _Distance>
209inline _Tp* value_type(const forward_iterator<_Tp, _Distance>&)
210  { return (_Tp*)(0); }
211
212template <class _Tp, class _Distance>
213inline _Tp* value_type(const bidirectional_iterator<_Tp, _Distance>&)
214  { return (_Tp*)(0); }
215
216template <class _Tp, class _Distance>
217inline _Tp* value_type(const random_access_iterator<_Tp, _Distance>&)
218  { return (_Tp*)(0); }
219
220template <class _Tp>
221inline _Tp* value_type(const _Tp*) { return (_Tp*)(0); }
222
223template <class _Tp, class _Distance>
224inline _Distance* distance_type(const input_iterator<_Tp, _Distance>&)
225{
226  return (_Distance*)(0);
227}
228
229template <class _Tp, class _Distance>
230inline _Distance* distance_type(const forward_iterator<_Tp, _Distance>&)
231{
232  return (_Distance*)(0);
233}
234
235template <class _Tp, class _Distance>
236inline _Distance*
237distance_type(const bidirectional_iterator<_Tp, _Distance>&)
238{
239  return (_Distance*)(0);
240}
241
242template <class _Tp, class _Distance>
243inline _Distance*
244distance_type(const random_access_iterator<_Tp, _Distance>&)
245{
246  return (_Distance*)(0);
247}
248
249template <class _Tp>
250inline 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
261template <class _InputIterator, class _Distance>
262inline void __distance(_InputIterator __first, _InputIterator __last,
263                       _Distance& __n, input_iterator_tag)
264{
265  while (__first != __last) { ++__first; ++__n; }
266}
267
268template <class _RandomAccessIterator, class _Distance>
269inline void __distance(_RandomAccessIterator __first,
270                       _RandomAccessIterator __last,
271                       _Distance& __n, random_access_iterator_tag)
272{
273  __n += __last - __first;
274}
275
276template <class _InputIterator, class _Distance>
277inline 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
285template <class _InputIterator>
286inline 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
296template <class _RandomAccessIterator>
297inline typename iterator_traits<_RandomAccessIterator>::difference_type
298__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
299           random_access_iterator_tag) {
300  return __last - __first;
301}
302
303template <class _InputIterator>
304inline typename iterator_traits<_InputIterator>::difference_type
305distance(_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
313template <class _InputIter, class _Distance>
314inline 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
322template <class _BidirectionalIterator, class _Distance>
323inline 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
335template <class _RandomAccessIterator, class _Distance>
336inline void __advance(_RandomAccessIterator& __i, _Distance __n,
337                      random_access_iterator_tag) {
338  __i += __n;
339}
340
341template <class _InputIterator, class _Distance>
342inline void advance(_InputIterator& __i, _Distance __n) {
343  __advance(__i, __n, iterator_category(__i));
344}
345
346template <class _Container>
347class back_insert_iterator {
348protected:
349  _Container* container;
350public:
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
371template <class _Container>
372inline output_iterator_tag
373iterator_category(const back_insert_iterator<_Container>&)
374{
375  return output_iterator_tag();
376}
377
378#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
379
380template <class _Container>
381inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
382  return back_insert_iterator<_Container>(__x);
383}
384
385template <class _Container>
386class front_insert_iterator {
387protected:
388  _Container* container;
389public:
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
410template <class _Container>
411inline output_iterator_tag
412iterator_category(const front_insert_iterator<_Container>&)
413{
414  return output_iterator_tag();
415}
416
417#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
418
419template <class _Container>
420inline front_insert_iterator<_Container> front_inserter(_Container& __x) {
421  return front_insert_iterator<_Container>(__x);
422}
423
424template <class _Container>
425class insert_iterator {
426protected:
427  _Container* container;
428  typename _Container::iterator iter;
429public:
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
452template <class _Container>
453inline output_iterator_tag
454iterator_category(const insert_iterator<_Container>&)
455{
456  return output_iterator_tag();
457}
458
459#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
460
461template <class _Container, class _Iterator>
462inline
463insert_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
470template <class _BidirectionalIterator, class _Tp, class _Reference = _Tp&,
471          class _Distance = ptrdiff_t>
472#else
473template <class _BidirectionalIterator, class _Tp, class _Reference,
474          class _Distance>
475#endif
476class reverse_bidirectional_iterator {
477  typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
478                                         _Reference, _Distance>  _Self;
479protected:
480  _BidirectionalIterator current;
481public:
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
521template <class _BidirectionalIterator, class _Tp, class _Reference,
522          class _Distance>
523inline bidirectional_iterator_tag
524iterator_category(const reverse_bidirectional_iterator<_BidirectionalIterator,
525                                                       _Tp, _Reference,
526                                                       _Distance>&)
527{
528  return bidirectional_iterator_tag();
529}
530
531template <class _BidirectionalIterator, class _Tp, class _Reference,
532          class _Distance>
533inline _Tp*
534value_type(const reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
535                                               _Reference, _Distance>&)
536{
537  return (_Tp*) 0;
538}
539
540template <class _BidirectionalIterator, class _Tp, class _Reference,
541          class _Distance>
542inline _Distance*
543distance_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
552template <class _BiIter, class _Tp, class _Ref,
553          class _Distance>
554inline 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
569template <class _Iterator>
570class reverse_iterator
571{
572protected:
573  _Iterator current;
574public:
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
589public:
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
645template <class _Iterator>
646inline bool operator==(const reverse_iterator<_Iterator>& __x,
647                       const reverse_iterator<_Iterator>& __y) {
648  return __x.base() == __y.base();
649}
650
651template <class _Iterator>
652inline bool operator<(const reverse_iterator<_Iterator>& __x,
653                      const reverse_iterator<_Iterator>& __y) {
654  return __y.base() < __x.base();
655}
656
657template <class _Iterator>
658inline typename reverse_iterator<_Iterator>::difference_type
659operator-(const reverse_iterator<_Iterator>& __x,
660          const reverse_iterator<_Iterator>& __y) {
661  return __y.base() - __x.base();
662}
663
664template <class _Iterator>
665inline reverse_iterator<_Iterator>
666operator+(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
677template <class _RandomAccessIterator, class _Tp, class _Reference = _Tp&,
678          class _Distance = ptrdiff_t>
679#else
680template <class _RandomAccessIterator, class _Tp, class _Reference,
681          class _Distance>
682#endif
683class reverse_iterator {
684  typedef reverse_iterator<_RandomAccessIterator, _Tp, _Reference, _Distance>
685        _Self;
686protected:
687  _RandomAccessIterator current;
688public:
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
737template <class _RandomAccessIterator, class _Tp,
738          class _Reference, class _Distance>
739inline random_access_iterator_tag
740iterator_category(const reverse_iterator<_RandomAccessIterator, _Tp,
741                                         _Reference, _Distance>&)
742{
743  return random_access_iterator_tag();
744}
745
746template <class _RandomAccessIterator, class _Tp,
747          class _Reference, class _Distance>
748inline _Tp* value_type(const reverse_iterator<_RandomAccessIterator, _Tp,
749                                              _Reference, _Distance>&)
750{
751  return (_Tp*) 0;
752}
753
754template <class _RandomAccessIterator, class _Tp,
755          class _Reference, class _Distance>
756inline _Distance*
757distance_type(const reverse_iterator<_RandomAccessIterator,
758                                     _Tp, _Reference, _Distance>&)
759{
760  return (_Distance*) 0;
761}
762
763
764template <class _RandomAccessIterator, class _Tp,
765          class _Reference, class _Distance>
766inline bool
767operator==(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
775template <class _RandomAccessIterator, class _Tp,
776          class _Reference, class _Distance>
777inline bool
778operator<(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
786template <class _RandomAccessIterator, class _Tp,
787          class _Reference, class _Distance>
788inline _Distance
789operator-(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
797template <class _RandAccIter, class _Tp, class _Ref, class _Dist>
798inline reverse_iterator<_RandAccIter, _Tp, _Ref, _Dist>
799operator+(_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
810template <class _Tp, class _Dist = ptrdiff_t>
811class istream_iterator {
812  friend bool operator== __STL_NULL_TMPL_ARGS (const istream_iterator&,
813                                               const istream_iterator&);
814protected:
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  }
823public:
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
849template <class _Tp, class _Dist>
850inline input_iterator_tag
851iterator_category(const istream_iterator<_Tp, _Dist>&)
852{
853  return input_iterator_tag();
854}
855
856template <class _Tp, class _Dist>
857inline _Tp*
858value_type(const istream_iterator<_Tp, _Dist>&) { return (_Tp*) 0; }
859
860template <class _Tp, class _Dist>
861inline _Dist*
862distance_type(const istream_iterator<_Tp, _Dist>&) { return (_Dist*)0; }
863
864#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
865
866template <class _Tp, class _Distance>
867inline 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
874template <class _Tp>
875class ostream_iterator {
876protected:
877  ostream* _M_stream;
878  const char* _M_string;
879public:
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
901template <class _Tp>
902inline output_iterator_tag
903iterator_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:
916