00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060 #ifndef __SGI_STL_INTERNAL_ITERATOR_H
00061 #define __SGI_STL_INTERNAL_ITERATOR_H
00062
00063 namespace std
00064 {
00065
00066 template <class _Container>
00067 class back_insert_iterator {
00068 protected:
00069 _Container* container;
00070 public:
00071 typedef _Container container_type;
00072 typedef output_iterator_tag iterator_category;
00073 typedef void value_type;
00074 typedef void difference_type;
00075 typedef void pointer;
00076 typedef void reference;
00077
00078 explicit back_insert_iterator(_Container& __x) : container(&__x) {}
00079 back_insert_iterator<_Container>&
00080 operator=(const typename _Container::value_type& __value) {
00081 container->push_back(__value);
00082 return *this;
00083 }
00084 back_insert_iterator<_Container>& operator*() { return *this; }
00085 back_insert_iterator<_Container>& operator++() { return *this; }
00086 back_insert_iterator<_Container>& operator++(int) { return *this; }
00087 };
00088
00089 template <class _Container>
00090 inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
00091 return back_insert_iterator<_Container>(__x);
00092 }
00093
00094 template <class _Container>
00095 class front_insert_iterator {
00096 protected:
00097 _Container* container;
00098 public:
00099 typedef _Container container_type;
00100 typedef output_iterator_tag iterator_category;
00101 typedef void value_type;
00102 typedef void difference_type;
00103 typedef void pointer;
00104 typedef void reference;
00105
00106 explicit front_insert_iterator(_Container& __x) : container(&__x) {}
00107 front_insert_iterator<_Container>&
00108 operator=(const typename _Container::value_type& __value) {
00109 container->push_front(__value);
00110 return *this;
00111 }
00112 front_insert_iterator<_Container>& operator*() { return *this; }
00113 front_insert_iterator<_Container>& operator++() { return *this; }
00114 front_insert_iterator<_Container>& operator++(int) { return *this; }
00115 };
00116
00117 template <class _Container>
00118 inline front_insert_iterator<_Container> front_inserter(_Container& __x) {
00119 return front_insert_iterator<_Container>(__x);
00120 }
00121
00122 template <class _Container>
00123 class insert_iterator {
00124 protected:
00125 _Container* container;
00126 typename _Container::iterator iter;
00127 public:
00128 typedef _Container container_type;
00129 typedef output_iterator_tag iterator_category;
00130 typedef void value_type;
00131 typedef void difference_type;
00132 typedef void pointer;
00133 typedef void reference;
00134
00135 insert_iterator(_Container& __x, typename _Container::iterator __i)
00136 : container(&__x), iter(__i) {}
00137 insert_iterator<_Container>&
00138 operator=(const typename _Container::value_type& __value) {
00139 iter = container->insert(iter, __value);
00140 ++iter;
00141 return *this;
00142 }
00143 insert_iterator<_Container>& operator*() { return *this; }
00144 insert_iterator<_Container>& operator++() { return *this; }
00145 insert_iterator<_Container>& operator++(int) { return *this; }
00146 };
00147
00148 template <class _Container, class _Iterator>
00149 inline
00150 insert_iterator<_Container> inserter(_Container& __x, _Iterator __i)
00151 {
00152 typedef typename _Container::iterator __iter;
00153 return insert_iterator<_Container>(__x, __iter(__i));
00154 }
00155
00156 template <class _BidirectionalIterator, class _Tp, class _Reference = _Tp&,
00157 class _Distance = ptrdiff_t>
00158 class reverse_bidirectional_iterator {
00159 typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
00160 _Reference, _Distance> _Self;
00161 protected:
00162 _BidirectionalIterator current;
00163 public:
00164 typedef bidirectional_iterator_tag iterator_category;
00165 typedef _Tp value_type;
00166 typedef _Distance difference_type;
00167 typedef _Tp* pointer;
00168 typedef _Reference reference;
00169
00170 reverse_bidirectional_iterator() {}
00171 explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
00172 : current(__x) {}
00173 _BidirectionalIterator base() const { return current; }
00174 _Reference operator*() const {
00175 _BidirectionalIterator __tmp = current;
00176 return *--__tmp;
00177 }
00178 pointer operator->() const { return &(operator*()); }
00179 _Self& operator++() {
00180 --current;
00181 return *this;
00182 }
00183 _Self operator++(int) {
00184 _Self __tmp = *this;
00185 --current;
00186 return __tmp;
00187 }
00188 _Self& operator--() {
00189 ++current;
00190 return *this;
00191 }
00192 _Self operator--(int) {
00193 _Self __tmp = *this;
00194 ++current;
00195 return __tmp;
00196 }
00197 };
00198
00199 template <class _BiIter, class _Tp, class _Ref, class _Distance>
00200 inline bool operator==(
00201 const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
00202 const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
00203 {
00204 return __x.base() == __y.base();
00205 }
00206
00207 template <class _BiIter, class _Tp, class _Ref, class _Distance>
00208 inline bool operator!=(
00209 const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
00210 const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
00211 {
00212 return !(__x == __y);
00213 }
00214
00215
00216
00217
00218
00219
00220
00221
00222 template <class _Iterator>
00223 class reverse_iterator
00224 {
00225 protected:
00226 _Iterator current;
00227 public:
00228 typedef typename iterator_traits<_Iterator>::iterator_category
00229 iterator_category;
00230 typedef typename iterator_traits<_Iterator>::value_type
00231 value_type;
00232 typedef typename iterator_traits<_Iterator>::difference_type
00233 difference_type;
00234 typedef typename iterator_traits<_Iterator>::pointer
00235 pointer;
00236 typedef typename iterator_traits<_Iterator>::reference
00237 reference;
00238
00239 typedef _Iterator iterator_type;
00240 typedef reverse_iterator<_Iterator> _Self;
00241
00242 public:
00243 reverse_iterator() {}
00244 explicit reverse_iterator(iterator_type __x) : current(__x) {}
00245
00246 reverse_iterator(const _Self& __x) : current(__x.current) {}
00247 template <class _Iter>
00248 reverse_iterator(const reverse_iterator<_Iter>& __x)
00249 : current(__x.base()) {}
00250
00251 iterator_type base() const { return current; }
00252 reference operator*() const {
00253 _Iterator __tmp = current;
00254 return *--__tmp;
00255 }
00256 pointer operator->() const { return &(operator*()); }
00257
00258 _Self& operator++() {
00259 --current;
00260 return *this;
00261 }
00262 _Self operator++(int) {
00263 _Self __tmp = *this;
00264 --current;
00265 return __tmp;
00266 }
00267 _Self& operator--() {
00268 ++current;
00269 return *this;
00270 }
00271 _Self operator--(int) {
00272 _Self __tmp = *this;
00273 ++current;
00274 return __tmp;
00275 }
00276
00277 _Self operator+(difference_type __n) const {
00278 return _Self(current - __n);
00279 }
00280 _Self& operator+=(difference_type __n) {
00281 current -= __n;
00282 return *this;
00283 }
00284 _Self operator-(difference_type __n) const {
00285 return _Self(current + __n);
00286 }
00287 _Self& operator-=(difference_type __n) {
00288 current += __n;
00289 return *this;
00290 }
00291 reference operator[](difference_type __n) const { return *(*this + __n); }
00292 };
00293
00294 template <class _Iterator>
00295 inline bool operator==(const reverse_iterator<_Iterator>& __x,
00296 const reverse_iterator<_Iterator>& __y) {
00297 return __x.base() == __y.base();
00298 }
00299
00300 template <class _Iterator>
00301 inline bool operator<(const reverse_iterator<_Iterator>& __x,
00302 const reverse_iterator<_Iterator>& __y) {
00303 return __y.base() < __x.base();
00304 }
00305
00306 template <class _Iterator>
00307 inline bool operator!=(const reverse_iterator<_Iterator>& __x,
00308 const reverse_iterator<_Iterator>& __y) {
00309 return !(__x == __y);
00310 }
00311
00312 template <class _Iterator>
00313 inline bool operator>(const reverse_iterator<_Iterator>& __x,
00314 const reverse_iterator<_Iterator>& __y) {
00315 return __y < __x;
00316 }
00317
00318 template <class _Iterator>
00319 inline bool operator<=(const reverse_iterator<_Iterator>& __x,
00320 const reverse_iterator<_Iterator>& __y) {
00321 return !(__y < __x);
00322 }
00323
00324 template <class _Iterator>
00325 inline bool operator>=(const reverse_iterator<_Iterator>& __x,
00326 const reverse_iterator<_Iterator>& __y) {
00327 return !(__x < __y);
00328 }
00329
00330 template <class _Iterator>
00331 inline typename reverse_iterator<_Iterator>::difference_type
00332 operator-(const reverse_iterator<_Iterator>& __x,
00333 const reverse_iterator<_Iterator>& __y) {
00334 return __y.base() - __x.base();
00335 }
00336
00337 template <class _Iterator>
00338 inline reverse_iterator<_Iterator>
00339 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
00340 const reverse_iterator<_Iterator>& __x) {
00341 return reverse_iterator<_Iterator>(__x.base() - __n);
00342 }
00343
00344
00345 template <class _Tp,
00346 class _CharT = char, class _Traits = char_traits<_CharT>,
00347 class _Dist = ptrdiff_t>
00348 class istream_iterator {
00349 public:
00350 typedef _CharT char_type;
00351 typedef _Traits traits_type;
00352 typedef basic_istream<_CharT, _Traits> istream_type;
00353
00354 typedef input_iterator_tag iterator_category;
00355 typedef _Tp value_type;
00356 typedef _Dist difference_type;
00357 typedef const _Tp* pointer;
00358 typedef const _Tp& reference;
00359
00360 istream_iterator() : _M_stream(0), _M_ok(false) {}
00361 istream_iterator(istream_type& __s) : _M_stream(&__s) { _M_read(); }
00362
00363 reference operator*() const { return _M_value; }
00364 pointer operator->() const { return &(operator*()); }
00365
00366 istream_iterator& operator++() {
00367 _M_read();
00368 return *this;
00369 }
00370 istream_iterator operator++(int) {
00371 istream_iterator __tmp = *this;
00372 _M_read();
00373 return __tmp;
00374 }
00375
00376 bool _M_equal(const istream_iterator& __x) const
00377 { return (_M_ok == __x._M_ok) && (!_M_ok || _M_stream == __x._M_stream); }
00378
00379 private:
00380 istream_type* _M_stream;
00381 _Tp _M_value;
00382 bool _M_ok;
00383
00384 void _M_read() {
00385 _M_ok = (_M_stream && *_M_stream) ? true : false;
00386 if (_M_ok) {
00387 *_M_stream >> _M_value;
00388 _M_ok = *_M_stream ? true : false;
00389 }
00390 }
00391 };
00392
00393 template <class _Tp, class _CharT, class _Traits, class _Dist>
00394 inline bool
00395 operator==(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
00396 const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
00397 return __x._M_equal(__y);
00398 }
00399
00400 template <class _Tp, class _CharT, class _Traits, class _Dist>
00401 inline bool
00402 operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
00403 const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
00404 return !__x._M_equal(__y);
00405 }
00406
00407
00408 template <class _Tp,
00409 class _CharT = char, class _Traits = char_traits<_CharT> >
00410 class ostream_iterator {
00411 public:
00412 typedef _CharT char_type;
00413 typedef _Traits traits_type;
00414 typedef basic_ostream<_CharT, _Traits> ostream_type;
00415
00416 typedef output_iterator_tag iterator_category;
00417 typedef void value_type;
00418 typedef void difference_type;
00419 typedef void pointer;
00420 typedef void reference;
00421
00422 ostream_iterator(ostream_type& __s) : _M_stream(&__s), _M_string(0) {}
00423 ostream_iterator(ostream_type& __s, const _CharT* __c)
00424 : _M_stream(&__s), _M_string(__c) {}
00425 ostream_iterator<_Tp>& operator=(const _Tp& __value) {
00426 *_M_stream << __value;
00427 if (_M_string) *_M_stream << _M_string;
00428 return *this;
00429 }
00430 ostream_iterator<_Tp>& operator*() { return *this; }
00431 ostream_iterator<_Tp>& operator++() { return *this; }
00432 ostream_iterator<_Tp>& operator++(int) { return *this; }
00433 private:
00434 ostream_type* _M_stream;
00435 const _CharT* _M_string;
00436 };
00437
00438
00439
00440
00441
00442
00443
00444
00445
00446 template<typename _Iterator, typename _Container>
00447 class __normal_iterator
00448 : public iterator<iterator_traits<_Iterator>::iterator_category,
00449 iterator_traits<_Iterator>::value_type,
00450 iterator_traits<_Iterator>::difference_type,
00451 iterator_traits<_Iterator>::pointer,
00452 iterator_traits<_Iterator>::reference>
00453 {
00454
00455 protected:
00456 _Iterator _M_current;
00457
00458 public:
00459 typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
00460 typedef iterator_traits<_Iterator> __traits_type;
00461 typedef typename __traits_type::iterator_category iterator_category;
00462 typedef typename __traits_type::value_type value_type;
00463 typedef typename __traits_type::difference_type difference_type;
00464 typedef typename __traits_type::pointer pointer;
00465 typedef typename __traits_type::reference reference;
00466
00467 __normal_iterator() : _M_current(_Iterator()) { }
00468
00469 explicit __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
00470
00471
00472 template<typename _Iter>
00473 inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
00474 : _M_current(__i.base()) { }
00475
00476
00477 reference
00478 operator*() const { return *_M_current; }
00479
00480 pointer
00481 operator->() const { return _M_current; }
00482
00483 normal_iterator_type&
00484 operator++() { ++_M_current; return *this; }
00485
00486 normal_iterator_type
00487 operator++(int) { return __normal_iterator(_M_current++); }
00488
00489
00490 normal_iterator_type&
00491 operator--() { --_M_current; return *this; }
00492
00493 normal_iterator_type
00494 operator--(int) { return __normal_iterator(_M_current--); }
00495
00496
00497 reference
00498 operator[](const difference_type& __n) const
00499 { return _M_current[__n]; }
00500
00501 normal_iterator_type&
00502 operator+=(const difference_type& __n)
00503 { _M_current += __n; return *this; }
00504
00505 normal_iterator_type
00506 operator+(const difference_type& __n) const
00507 { return __normal_iterator(_M_current + __n); }
00508
00509 normal_iterator_type&
00510 operator-=(const difference_type& __n)
00511 { _M_current -= __n; return *this; }
00512
00513 normal_iterator_type
00514 operator-(const difference_type& __n) const
00515 { return __normal_iterator(_M_current - __n); }
00516
00517 difference_type
00518 operator-(const normal_iterator_type& __i) const
00519 { return _M_current - __i._M_current; }
00520
00521 const _Iterator&
00522 base() const { return _M_current; }
00523 };
00524
00525
00526
00527 template<typename _IteratorL, typename _IteratorR, typename _Container>
00528 inline bool
00529 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00530 const __normal_iterator<_IteratorR, _Container>& __rhs)
00531 { return __lhs.base() == __rhs.base(); }
00532
00533 template<typename _IteratorL, typename _IteratorR, typename _Container>
00534 inline bool
00535 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00536 const __normal_iterator<_IteratorR, _Container>& __rhs)
00537 { return !(__lhs == __rhs); }
00538
00539
00540
00541 template<typename _IteratorL, typename _IteratorR, typename _Container>
00542 inline bool
00543 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00544 const __normal_iterator<_IteratorR, _Container>& __rhs)
00545 { return __lhs.base() < __rhs.base(); }
00546
00547 template<typename _IteratorL, typename _IteratorR, typename _Container>
00548 inline bool
00549 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00550 const __normal_iterator<_IteratorR, _Container>& __rhs)
00551 { return __rhs < __lhs; }
00552
00553 template<typename _IteratorL, typename _IteratorR, typename _Container>
00554 inline bool
00555 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00556 const __normal_iterator<_IteratorR, _Container>& __rhs)
00557 { return !(__rhs < __lhs); }
00558
00559 template<typename _IteratorL, typename _IteratorR, typename _Container>
00560 inline bool
00561 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00562 const __normal_iterator<_IteratorR, _Container>& __rhs)
00563 { return !(__lhs < __rhs); }
00564
00565 template<typename _Iterator, typename _Container>
00566 inline __normal_iterator<_Iterator, _Container>
00567 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type __n,
00568 const __normal_iterator<_Iterator, _Container>& __i)
00569 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00570
00571 }
00572
00573 #endif
00574
00575
00576
00577