Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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. namespace std
  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. template <class _Container>
  61. inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
  62.   return back_insert_iterator<_Container>(__x);
  63. }
  64.  
  65. template <class _Container>
  66. class front_insert_iterator {
  67. protected:
  68.   _Container* container;
  69. public:
  70.   typedef _Container          container_type;
  71.   typedef output_iterator_tag iterator_category;
  72.   typedef void                value_type;
  73.   typedef void                difference_type;
  74.   typedef void                pointer;
  75.   typedef void                reference;
  76.  
  77.   explicit front_insert_iterator(_Container& __x) : container(&__x) {}
  78.   front_insert_iterator<_Container>&
  79.   operator=(const typename _Container::value_type& __value) {
  80.     container->push_front(__value);
  81.     return *this;
  82.   }
  83.   front_insert_iterator<_Container>& operator*() { return *this; }
  84.   front_insert_iterator<_Container>& operator++() { return *this; }
  85.   front_insert_iterator<_Container>& operator++(int) { return *this; }
  86. };
  87.  
  88. template <class _Container>
  89. inline front_insert_iterator<_Container> front_inserter(_Container& __x) {
  90.   return front_insert_iterator<_Container>(__x);
  91. }
  92.  
  93. template <class _Container>
  94. class insert_iterator {
  95. protected:
  96.   _Container* container;
  97.   typename _Container::iterator iter;
  98. public:
  99.   typedef _Container          container_type;
  100.   typedef output_iterator_tag iterator_category;
  101.   typedef void                value_type;
  102.   typedef void                difference_type;
  103.   typedef void                pointer;
  104.   typedef void                reference;
  105.  
  106.   insert_iterator(_Container& __x, typename _Container::iterator __i)
  107.     : container(&__x), iter(__i) {}
  108.   insert_iterator<_Container>&
  109.   operator=(const typename _Container::value_type& __value) {
  110.     iter = container->insert(iter, __value);
  111.     ++iter;
  112.     return *this;
  113.   }
  114.   insert_iterator<_Container>& operator*() { return *this; }
  115.   insert_iterator<_Container>& operator++() { return *this; }
  116.   insert_iterator<_Container>& operator++(int) { return *this; }
  117. };
  118.  
  119. template <class _Container, class _Iterator>
  120. inline
  121. insert_iterator<_Container> inserter(_Container& __x, _Iterator __i)
  122. {
  123.   typedef typename _Container::iterator __iter;
  124.   return insert_iterator<_Container>(__x, __iter(__i));
  125. }
  126.  
  127. template <class _BidirectionalIterator, class _Tp, class _Reference = _Tp&,
  128.           class _Distance = ptrdiff_t>
  129. class reverse_bidirectional_iterator {
  130.   typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
  131.                                          _Reference, _Distance>  _Self;
  132. protected:
  133.   _BidirectionalIterator current;
  134. public:
  135.   typedef bidirectional_iterator_tag iterator_category;
  136.   typedef _Tp                        value_type;
  137.   typedef _Distance                  difference_type;
  138.   typedef _Tp*                       pointer;
  139.   typedef _Reference                 reference;
  140.  
  141.   reverse_bidirectional_iterator() {}
  142.   explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
  143.     : current(__x) {}
  144.   _BidirectionalIterator base() const { return current; }
  145.   _Reference operator*() const {
  146.     _BidirectionalIterator __tmp = current;
  147.     return *--__tmp;
  148.   }
  149.   pointer operator->() const { return &(operator*()); }
  150.   _Self& operator++() {
  151.     --current;
  152.     return *this;
  153.   }
  154.   _Self operator++(int) {
  155.     _Self __tmp = *this;
  156.     --current;
  157.     return __tmp;
  158.   }
  159.   _Self& operator--() {
  160.     ++current;
  161.     return *this;
  162.   }
  163.   _Self operator--(int) {
  164.     _Self __tmp = *this;
  165.     ++current;
  166.     return __tmp;
  167.   }
  168. };
  169.  
  170. template <class _BiIter, class _Tp, class _Ref, class _Distance>
  171. inline bool operator==(
  172.     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
  173.     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
  174. {
  175.   return __x.base() == __y.base();
  176. }
  177.  
  178. template <class _BiIter, class _Tp, class _Ref, class _Distance>
  179. inline bool operator!=(
  180.     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
  181.     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
  182. {
  183.   return !(__x == __y);
  184. }
  185.  
  186.  
  187. // This is the new version of reverse_iterator, as defined in the
  188. //  draft C++ standard.  It relies on the iterator_traits template,
  189. //  which in turn relies on partial specialization.  The class
  190. //  reverse_bidirectional_iterator is no longer part of the draft
  191. //  standard, but it is retained for backward compatibility.
  192.  
  193. template <class _Iterator>
  194. class reverse_iterator
  195. {
  196. protected:
  197.   _Iterator current;
  198. public:
  199.   typedef typename iterator_traits<_Iterator>::iterator_category
  200.           iterator_category;
  201.   typedef typename iterator_traits<_Iterator>::value_type
  202.           value_type;
  203.   typedef typename iterator_traits<_Iterator>::difference_type
  204.           difference_type;
  205.   typedef typename iterator_traits<_Iterator>::pointer
  206.           pointer;
  207.   typedef typename iterator_traits<_Iterator>::reference
  208.           reference;
  209.  
  210.   typedef _Iterator iterator_type;
  211.   typedef reverse_iterator<_Iterator> _Self;
  212.  
  213. public:
  214.   reverse_iterator() {}
  215.   explicit reverse_iterator(iterator_type __x) : current(__x) {}
  216.  
  217.   reverse_iterator(const _Self& __x) : current(__x.current) {}
  218.   template <class _Iter>
  219.   reverse_iterator(const reverse_iterator<_Iter>& __x)
  220.     : current(__x.base()) {}
  221.    
  222.   iterator_type base() const { return current; }
  223.   reference operator*() const {
  224.     _Iterator __tmp = current;
  225.     return *--__tmp;
  226.   }
  227.   pointer operator->() const { return &(operator*()); }
  228.  
  229.   _Self& operator++() {
  230.     --current;
  231.     return *this;
  232.   }
  233.   _Self operator++(int) {
  234.     _Self __tmp = *this;
  235.     --current;
  236.     return __tmp;
  237.   }
  238.   _Self& operator--() {
  239.     ++current;
  240.     return *this;
  241.   }
  242.   _Self operator--(int) {
  243.     _Self __tmp = *this;
  244.     ++current;
  245.     return __tmp;
  246.   }
  247.  
  248.   _Self operator+(difference_type __n) const {
  249.     return _Self(current - __n);
  250.   }
  251.   _Self& operator+=(difference_type __n) {
  252.     current -= __n;
  253.     return *this;
  254.   }
  255.   _Self operator-(difference_type __n) const {
  256.     return _Self(current + __n);
  257.   }
  258.   _Self& operator-=(difference_type __n) {
  259.     current += __n;
  260.     return *this;
  261.   }
  262.   reference operator[](difference_type __n) const { return *(*this + __n); }  
  263. };
  264.  
  265. template <class _Iterator>
  266. inline bool operator==(const reverse_iterator<_Iterator>& __x,
  267.                        const reverse_iterator<_Iterator>& __y) {
  268.   return __x.base() == __y.base();
  269. }
  270.  
  271. template <class _Iterator>
  272. inline bool operator<(const reverse_iterator<_Iterator>& __x,
  273.                       const reverse_iterator<_Iterator>& __y) {
  274.   return __y.base() < __x.base();
  275. }
  276.  
  277. template <class _Iterator>
  278. inline bool operator!=(const reverse_iterator<_Iterator>& __x,
  279.                        const reverse_iterator<_Iterator>& __y) {
  280.   return !(__x == __y);
  281. }
  282.  
  283. template <class _Iterator>
  284. inline bool operator>(const reverse_iterator<_Iterator>& __x,
  285.                       const reverse_iterator<_Iterator>& __y) {
  286.   return __y < __x;
  287. }
  288.  
  289. template <class _Iterator>
  290. inline bool operator<=(const reverse_iterator<_Iterator>& __x,
  291.                        const reverse_iterator<_Iterator>& __y) {
  292.   return !(__y < __x);
  293. }
  294.  
  295. template <class _Iterator>
  296. inline bool operator>=(const reverse_iterator<_Iterator>& __x,
  297.                       const reverse_iterator<_Iterator>& __y) {
  298.   return !(__x < __y);
  299. }
  300.  
  301. template <class _Iterator>
  302. inline typename reverse_iterator<_Iterator>::difference_type
  303. operator-(const reverse_iterator<_Iterator>& __x,
  304.           const reverse_iterator<_Iterator>& __y) {
  305.   return __y.base() - __x.base();
  306. }
  307.  
  308. template <class _Iterator>
  309. inline reverse_iterator<_Iterator>
  310. operator+(typename reverse_iterator<_Iterator>::difference_type __n,
  311.           const reverse_iterator<_Iterator>& __x) {
  312.   return reverse_iterator<_Iterator>(__x.base() - __n);
  313. }
  314.  
  315.  
  316. template <class _Tp,
  317.           class _CharT = char, class _Traits = char_traits<_CharT>,
  318.           class _Dist = ptrdiff_t>
  319. class istream_iterator {
  320. public:
  321.   typedef _CharT                         char_type;
  322.   typedef _Traits                        traits_type;
  323.   typedef basic_istream<_CharT, _Traits> istream_type;
  324.  
  325.   typedef input_iterator_tag             iterator_category;
  326.   typedef _Tp                            value_type;
  327.   typedef _Dist                          difference_type;
  328.   typedef const _Tp*                     pointer;
  329.   typedef const _Tp&                     reference;
  330.  
  331.   istream_iterator() : _M_stream(0), _M_ok(false) {}
  332.   istream_iterator(istream_type& __s) : _M_stream(&__s) { _M_read(); }
  333.  
  334.   reference operator*() const { return _M_value; }
  335.   pointer operator->() const { return &(operator*()); }
  336.  
  337.   istream_iterator& operator++() {
  338.     _M_read();
  339.     return *this;
  340.   }
  341.   istream_iterator operator++(int)  {
  342.     istream_iterator __tmp = *this;
  343.     _M_read();
  344.     return __tmp;
  345.   }
  346.  
  347.   bool _M_equal(const istream_iterator& __x) const
  348.     { return (_M_ok == __x._M_ok) && (!_M_ok || _M_stream == __x._M_stream); }
  349.  
  350. private:
  351.   istream_type* _M_stream;
  352.   _Tp _M_value;
  353.   bool _M_ok;
  354.  
  355.   void _M_read() {
  356.     _M_ok = (_M_stream && *_M_stream) ? true : false;
  357.     if (_M_ok) {
  358.       *_M_stream >> _M_value;
  359.       _M_ok = *_M_stream ? true : false;
  360.     }
  361.   }
  362. };
  363.  
  364. template <class _Tp, class _CharT, class _Traits, class _Dist>
  365. inline bool
  366. operator==(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
  367.            const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
  368.   return __x._M_equal(__y);
  369. }
  370.  
  371. template <class _Tp, class _CharT, class _Traits, class _Dist>
  372. inline bool
  373. operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
  374.            const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
  375.   return !__x._M_equal(__y);
  376. }
  377.  
  378.  
  379. template <class _Tp,
  380.           class _CharT = char, class _Traits = char_traits<_CharT> >
  381. class ostream_iterator {
  382. public:
  383.   typedef _CharT                         char_type;
  384.   typedef _Traits                        traits_type;
  385.   typedef basic_ostream<_CharT, _Traits> ostream_type;
  386.  
  387.   typedef output_iterator_tag            iterator_category;
  388.   typedef void                           value_type;
  389.   typedef void                           difference_type;
  390.   typedef void                           pointer;
  391.   typedef void                           reference;
  392.  
  393.   ostream_iterator(ostream_type& __s) : _M_stream(&__s), _M_string(0) {}
  394.   ostream_iterator(ostream_type& __s, const _CharT* __c)
  395.     : _M_stream(&__s), _M_string(__c)  {}
  396.   ostream_iterator<_Tp>& operator=(const _Tp& __value) {
  397.     *_M_stream << __value;
  398.     if (_M_string) *_M_stream << _M_string;
  399.     return *this;
  400.   }
  401.   ostream_iterator<_Tp>& operator*() { return *this; }
  402.   ostream_iterator<_Tp>& operator++() { return *this; }
  403.   ostream_iterator<_Tp>& operator++(int) { return *this; }
  404. private:
  405.   ostream_type* _M_stream;
  406.   const _CharT* _M_string;
  407. };
  408.  
  409.  
  410. // This iterator adapter is 'normal' in the sense that it does not
  411. // change the semantics of any of the operators of its itererator
  412. // parameter.  Its primary purpose is to convert an iterator that is
  413. // not a class, e.g. a pointer, into an iterator that is a class.
  414. // The _Container parameter exists solely so that different containers
  415. // using this template can instantiate different types, even if the
  416. // _Iterator parameter is the same.
  417. template<typename _Iterator, typename _Container>
  418. class __normal_iterator
  419.   : public iterator<iterator_traits<_Iterator>::iterator_category,
  420.                     iterator_traits<_Iterator>::value_type,
  421.                     iterator_traits<_Iterator>::difference_type,
  422.                     iterator_traits<_Iterator>::pointer,
  423.                     iterator_traits<_Iterator>::reference>
  424. {
  425.  
  426. protected:
  427.   _Iterator _M_current;
  428.  
  429. public:
  430.   typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
  431.   typedef iterator_traits<_Iterator>                    __traits_type;
  432.   typedef typename __traits_type::iterator_category     iterator_category;
  433.   typedef typename __traits_type::value_type            value_type;
  434.   typedef typename __traits_type::difference_type       difference_type;
  435.   typedef typename __traits_type::pointer               pointer;
  436.   typedef typename __traits_type::reference             reference;
  437.  
  438.   __normal_iterator() : _M_current(_Iterator()) { }
  439.  
  440.   explicit __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
  441.  
  442.   // Allow iterator to const_iterator conversion
  443.   template<typename _Iter>
  444.   inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
  445.     : _M_current(__i.base()) { }
  446.  
  447.   // Forward iterator requirements
  448.   reference
  449.   operator*() const { return *_M_current; }
  450.  
  451.   pointer
  452.   operator->() const { return _M_current; }
  453.  
  454.   normal_iterator_type&
  455.   operator++() { ++_M_current; return *this; }
  456.  
  457.   normal_iterator_type
  458.   operator++(int) { return __normal_iterator(_M_current++); }
  459.  
  460.   // Bidirectional iterator requirements
  461.   normal_iterator_type&
  462.   operator--() { --_M_current; return *this; }
  463.  
  464.   normal_iterator_type
  465.   operator--(int) { return __normal_iterator(_M_current--); }
  466.  
  467.   // Random access iterator requirements
  468.   reference
  469.   operator[](const difference_type& __n) const
  470.   { return _M_current[__n]; }
  471.  
  472.   normal_iterator_type&
  473.   operator+=(const difference_type& __n)
  474.   { _M_current += __n; return *this; }
  475.  
  476.   normal_iterator_type
  477.   operator+(const difference_type& __n) const
  478.   { return __normal_iterator(_M_current + __n); }
  479.  
  480.   normal_iterator_type&
  481.   operator-=(const difference_type& __n)
  482.   { _M_current -= __n; return *this; }
  483.  
  484.   normal_iterator_type
  485.   operator-(const difference_type& __n) const
  486.   { return __normal_iterator(_M_current - __n); }
  487.  
  488.   difference_type
  489.   operator-(const normal_iterator_type& __i) const
  490.   { return _M_current - __i._M_current; }
  491.  
  492.   const _Iterator&
  493.   base() const { return _M_current; }
  494. };
  495.  
  496. // forward iterator requirements
  497.  
  498. template<typename _IteratorL, typename _IteratorR, typename _Container>
  499. inline bool
  500. operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
  501.            const __normal_iterator<_IteratorR, _Container>& __rhs)
  502. { return __lhs.base() == __rhs.base(); }
  503.  
  504. template<typename _IteratorL, typename _IteratorR, typename _Container>
  505. inline bool
  506. operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
  507.            const __normal_iterator<_IteratorR, _Container>& __rhs)
  508. { return !(__lhs == __rhs); }
  509.  
  510. // random access iterator requirements
  511.  
  512. template<typename _IteratorL, typename _IteratorR, typename _Container>
  513. inline bool
  514. operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
  515.           const __normal_iterator<_IteratorR, _Container>& __rhs)
  516. { return __lhs.base() < __rhs.base(); }
  517.  
  518. template<typename _IteratorL, typename _IteratorR, typename _Container>
  519. inline bool
  520. operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
  521.           const __normal_iterator<_IteratorR, _Container>& __rhs)
  522. { return __rhs < __lhs; }
  523.  
  524. template<typename _IteratorL, typename _IteratorR, typename _Container>
  525. inline bool
  526. operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
  527.            const __normal_iterator<_IteratorR, _Container>& __rhs)
  528. { return !(__rhs < __lhs); }
  529.  
  530. template<typename _IteratorL, typename _IteratorR, typename _Container>
  531. inline bool
  532. operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
  533.            const __normal_iterator<_IteratorR, _Container>& __rhs)
  534. { return !(__lhs < __rhs); }
  535.  
  536. template<typename _Iterator, typename _Container>
  537. inline __normal_iterator<_Iterator, _Container>
  538. operator+(__normal_iterator<_Iterator, _Container>::difference_type __n,
  539.           const __normal_iterator<_Iterator, _Container>& __i)
  540. { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
  541.  
  542. } // namespace std
  543.  
  544. #endif /* __SGI_STL_INTERNAL_ITERATOR_H */
  545.  
  546. // Local Variables:
  547. // mode:C++
  548. // End:
  549.