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
00061
00062
00063
00064
00065 #ifndef __GLIBCPP_INTERNAL_ITERATOR_H
00066 #define __GLIBCPP_INTERNAL_ITERATOR_H
00067
00068 namespace std
00069 {
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089 template<typename _Iterator>
00090 class reverse_iterator
00091 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
00092 typename iterator_traits<_Iterator>::value_type,
00093 typename iterator_traits<_Iterator>::difference_type,
00094 typename iterator_traits<_Iterator>::pointer,
00095 typename iterator_traits<_Iterator>::reference>
00096 {
00097 protected:
00098 _Iterator current;
00099
00100 public:
00101 typedef _Iterator iterator_type;
00102 typedef typename iterator_traits<_Iterator>::difference_type
00103 difference_type;
00104 typedef typename iterator_traits<_Iterator>::reference reference;
00105 typedef typename iterator_traits<_Iterator>::pointer pointer;
00106
00107 public:
00108
00109
00110
00111
00112
00113
00114 reverse_iterator() : current() { }
00115
00116
00117
00118
00119 explicit
00120 reverse_iterator(iterator_type __x) : current(__x) { }
00121
00122
00123
00124
00125 reverse_iterator(const reverse_iterator& __x)
00126 : current(__x.current) { }
00127
00128
00129
00130
00131
00132 template<typename _Iter>
00133 reverse_iterator(const reverse_iterator<_Iter>& __x)
00134 : current(__x.base()) { }
00135
00136
00137
00138
00139 iterator_type
00140 base() const { return current; }
00141
00142
00143
00144
00145
00146
00147 reference
00148 operator*() const
00149 {
00150 _Iterator __tmp = current;
00151 return *--__tmp;
00152 }
00153
00154
00155
00156
00157
00158
00159 pointer
00160 operator->() const { return &(operator*()); }
00161
00162
00163
00164
00165
00166
00167 reverse_iterator&
00168 operator++()
00169 {
00170 --current;
00171 return *this;
00172 }
00173
00174
00175
00176
00177
00178
00179 reverse_iterator
00180 operator++(int)
00181 {
00182 reverse_iterator __tmp = *this;
00183 --current;
00184 return __tmp;
00185 }
00186
00187
00188
00189
00190
00191
00192 reverse_iterator&
00193 operator--()
00194 {
00195 ++current;
00196 return *this;
00197 }
00198
00199
00200
00201
00202
00203
00204 reverse_iterator operator--(int)
00205 {
00206 reverse_iterator __tmp = *this;
00207 ++current;
00208 return __tmp;
00209 }
00210
00211
00212
00213
00214
00215
00216 reverse_iterator
00217 operator+(difference_type __n) const
00218 { return reverse_iterator(current - __n); }
00219
00220
00221
00222
00223
00224
00225 reverse_iterator&
00226 operator+=(difference_type __n)
00227 {
00228 current -= __n;
00229 return *this;
00230 }
00231
00232
00233
00234
00235
00236
00237 reverse_iterator
00238 operator-(difference_type __n) const
00239 { return reverse_iterator(current + __n); }
00240
00241
00242
00243
00244
00245
00246 reverse_iterator&
00247 operator-=(difference_type __n)
00248 {
00249 current += __n;
00250 return *this;
00251 }
00252
00253
00254
00255
00256
00257
00258 reference
00259 operator[](difference_type __n) const { return *(*this + __n); }
00260 };
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272 template<typename _Iterator>
00273 inline bool
00274 operator==(const reverse_iterator<_Iterator>& __x,
00275 const reverse_iterator<_Iterator>& __y)
00276 { return __x.base() == __y.base(); }
00277
00278 template<typename _Iterator>
00279 inline bool
00280 operator<(const reverse_iterator<_Iterator>& __x,
00281 const reverse_iterator<_Iterator>& __y)
00282 { return __y.base() < __x.base(); }
00283
00284 template<typename _Iterator>
00285 inline bool
00286 operator!=(const reverse_iterator<_Iterator>& __x,
00287 const reverse_iterator<_Iterator>& __y)
00288 { return !(__x == __y); }
00289
00290 template<typename _Iterator>
00291 inline bool
00292 operator>(const reverse_iterator<_Iterator>& __x,
00293 const reverse_iterator<_Iterator>& __y)
00294 { return __y < __x; }
00295
00296 template<typename _Iterator>
00297 inline bool
00298 operator<=(const reverse_iterator<_Iterator>& __x,
00299 const reverse_iterator<_Iterator>& __y)
00300 { return !(__y < __x); }
00301
00302 template<typename _Iterator>
00303 inline bool
00304 operator>=(const reverse_iterator<_Iterator>& __x,
00305 const reverse_iterator<_Iterator>& __y)
00306 { return !(__x < __y); }
00307
00308 template<typename _Iterator>
00309 inline typename reverse_iterator<_Iterator>::difference_type
00310 operator-(const reverse_iterator<_Iterator>& __x,
00311 const reverse_iterator<_Iterator>& __y)
00312 { return __y.base() - __x.base(); }
00313
00314 template<typename _Iterator>
00315 inline reverse_iterator<_Iterator>
00316 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
00317 const reverse_iterator<_Iterator>& __x)
00318 { return reverse_iterator<_Iterator>(__x.base() - __n); }
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332 template<typename _Container>
00333 class back_insert_iterator
00334 : public iterator<output_iterator_tag, void, void, void, void>
00335 {
00336 protected:
00337 _Container* container;
00338
00339 public:
00340
00341 typedef _Container container_type;
00342
00343
00344 explicit
00345 back_insert_iterator(_Container& __x) : container(&__x) { }
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358 back_insert_iterator&
00359 operator=(typename _Container::const_reference __value)
00360 {
00361 container->push_back(__value);
00362 return *this;
00363 }
00364
00365
00366 back_insert_iterator&
00367 operator*() { return *this; }
00368
00369
00370 back_insert_iterator&
00371 operator++() { return *this; }
00372
00373
00374 back_insert_iterator
00375 operator++(int) { return *this; }
00376 };
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389 template<typename _Container>
00390 inline back_insert_iterator<_Container>
00391 back_inserter(_Container& __x)
00392 { return back_insert_iterator<_Container>(__x); }
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404 template<typename _Container>
00405 class front_insert_iterator
00406 : public iterator<output_iterator_tag, void, void, void, void>
00407 {
00408 protected:
00409 _Container* container;
00410
00411 public:
00412
00413 typedef _Container container_type;
00414
00415
00416 explicit front_insert_iterator(_Container& __x) : container(&__x) { }
00417
00418
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428
00429 front_insert_iterator&
00430 operator=(typename _Container::const_reference __value)
00431 {
00432 container->push_front(__value);
00433 return *this;
00434 }
00435
00436
00437 front_insert_iterator&
00438 operator*() { return *this; }
00439
00440
00441 front_insert_iterator&
00442 operator++() { return *this; }
00443
00444
00445 front_insert_iterator
00446 operator++(int) { return *this; }
00447 };
00448
00449
00450
00451
00452
00453
00454
00455
00456
00457
00458
00459
00460 template<typename _Container>
00461 inline front_insert_iterator<_Container>
00462 front_inserter(_Container& __x)
00463 { return front_insert_iterator<_Container>(__x); }
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479 template<typename _Container>
00480 class insert_iterator
00481 : public iterator<output_iterator_tag, void, void, void, void>
00482 {
00483 protected:
00484 _Container* container;
00485 typename _Container::iterator iter;
00486
00487 public:
00488
00489 typedef _Container container_type;
00490
00491
00492
00493
00494
00495 insert_iterator(_Container& __x, typename _Container::iterator __i)
00496 : container(&__x), iter(__i) {}
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521 insert_iterator&
00522 operator=(const typename _Container::const_reference __value)
00523 {
00524 iter = container->insert(iter, __value);
00525 ++iter;
00526 return *this;
00527 }
00528
00529
00530 insert_iterator&
00531 operator*() { return *this; }
00532
00533
00534 insert_iterator&
00535 operator++() { return *this; }
00536
00537
00538 insert_iterator&
00539 operator++(int) { return *this; }
00540 };
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553 template<typename _Container, typename _Iterator>
00554 inline insert_iterator<_Container>
00555 inserter(_Container& __x, _Iterator __i)
00556 {
00557 return insert_iterator<_Container>(__x,
00558 typename _Container::iterator(__i));
00559 }
00560 }
00561
00562 namespace __gnu_cxx
00563 {
00564
00565
00566
00567
00568
00569
00570
00571 using std::iterator_traits;
00572 using std::iterator;
00573 template<typename _Iterator, typename _Container>
00574 class __normal_iterator
00575 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
00576 typename iterator_traits<_Iterator>::value_type,
00577 typename iterator_traits<_Iterator>::difference_type,
00578 typename iterator_traits<_Iterator>::pointer,
00579 typename iterator_traits<_Iterator>::reference>
00580 {
00581 protected:
00582 _Iterator _M_current;
00583
00584 public:
00585 typedef typename iterator_traits<_Iterator>::difference_type
00586 difference_type;
00587 typedef typename iterator_traits<_Iterator>::reference reference;
00588 typedef typename iterator_traits<_Iterator>::pointer pointer;
00589
00590 __normal_iterator() : _M_current(_Iterator()) { }
00591
00592 explicit
00593 __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
00594
00595
00596 template<typename _Iter>
00597 inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
00598 : _M_current(__i.base()) { }
00599
00600
00601 reference
00602 operator*() const { return *_M_current; }
00603
00604 pointer
00605 operator->() const { return _M_current; }
00606
00607 __normal_iterator&
00608 operator++() { ++_M_current; return *this; }
00609
00610 __normal_iterator
00611 operator++(int) { return __normal_iterator(_M_current++); }
00612
00613
00614 __normal_iterator&
00615 operator--() { --_M_current; return *this; }
00616
00617 __normal_iterator
00618 operator--(int) { return __normal_iterator(_M_current--); }
00619
00620
00621 reference
00622 operator[](const difference_type& __n) const
00623 { return _M_current[__n]; }
00624
00625 __normal_iterator&
00626 operator+=(const difference_type& __n)
00627 { _M_current += __n; return *this; }
00628
00629 __normal_iterator
00630 operator+(const difference_type& __n) const
00631 { return __normal_iterator(_M_current + __n); }
00632
00633 __normal_iterator&
00634 operator-=(const difference_type& __n)
00635 { _M_current -= __n; return *this; }
00636
00637 __normal_iterator
00638 operator-(const difference_type& __n) const
00639 { return __normal_iterator(_M_current - __n); }
00640
00641 const _Iterator&
00642 base() const { return _M_current; }
00643 };
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654 template<typename _IteratorL, typename _IteratorR, typename _Container>
00655 inline bool
00656 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00657 const __normal_iterator<_IteratorR, _Container>& __rhs)
00658 { return __lhs.base() == __rhs.base(); }
00659
00660 template<typename _Iterator, typename _Container>
00661 inline bool
00662 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
00663 const __normal_iterator<_Iterator, _Container>& __rhs)
00664 { return __lhs.base() == __rhs.base(); }
00665
00666 template<typename _IteratorL, typename _IteratorR, typename _Container>
00667 inline bool
00668 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00669 const __normal_iterator<_IteratorR, _Container>& __rhs)
00670 { return __lhs.base() != __rhs.base(); }
00671
00672 template<typename _Iterator, typename _Container>
00673 inline bool
00674 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
00675 const __normal_iterator<_Iterator, _Container>& __rhs)
00676 { return __lhs.base() != __rhs.base(); }
00677
00678
00679 template<typename _IteratorL, typename _IteratorR, typename _Container>
00680 inline bool
00681 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00682 const __normal_iterator<_IteratorR, _Container>& __rhs)
00683 { return __lhs.base() < __rhs.base(); }
00684
00685 template<typename _Iterator, typename _Container>
00686 inline bool
00687 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
00688 const __normal_iterator<_Iterator, _Container>& __rhs)
00689 { return __lhs.base() < __rhs.base(); }
00690
00691 template<typename _IteratorL, typename _IteratorR, typename _Container>
00692 inline bool
00693 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00694 const __normal_iterator<_IteratorR, _Container>& __rhs)
00695 { return __lhs.base() > __rhs.base(); }
00696
00697 template<typename _Iterator, typename _Container>
00698 inline bool
00699 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
00700 const __normal_iterator<_Iterator, _Container>& __rhs)
00701 { return __lhs.base() > __rhs.base(); }
00702
00703 template<typename _IteratorL, typename _IteratorR, typename _Container>
00704 inline bool
00705 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00706 const __normal_iterator<_IteratorR, _Container>& __rhs)
00707 { return __lhs.base() <= __rhs.base(); }
00708
00709 template<typename _Iterator, typename _Container>
00710 inline bool
00711 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
00712 const __normal_iterator<_Iterator, _Container>& __rhs)
00713 { return __lhs.base() <= __rhs.base(); }
00714
00715 template<typename _IteratorL, typename _IteratorR, typename _Container>
00716 inline bool
00717 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00718 const __normal_iterator<_IteratorR, _Container>& __rhs)
00719 { return __lhs.base() >= __rhs.base(); }
00720
00721 template<typename _Iterator, typename _Container>
00722 inline bool
00723 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
00724 const __normal_iterator<_Iterator, _Container>& __rhs)
00725 { return __lhs.base() >= __rhs.base(); }
00726
00727
00728
00729
00730
00731 template<typename _IteratorL, typename _IteratorR, typename _Container>
00732 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
00733 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00734 const __normal_iterator<_IteratorR, _Container>& __rhs)
00735 { return __lhs.base() - __rhs.base(); }
00736
00737 template<typename _Iterator, typename _Container>
00738 inline __normal_iterator<_Iterator, _Container>
00739 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type __n,
00740 const __normal_iterator<_Iterator, _Container>& __i)
00741 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00742 }
00743
00744 #endif
00745
00746
00747
00748