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