00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_MAP_ITERATOR_H
00018 #define LEMON_MAP_ITERATOR_H
00019
00020 #include <iterator>
00021
00022 #include <lemon/extended_pair.h>
00023
00027
00028 namespace lemon {
00029
00032
00038 template <typename Map>
00039 class MapIteratorBase {
00040
00041 public:
00042
00044 typedef typename Map::Key Key;
00046 typedef typename Map::KeyIt KeyIt;
00047
00049 typedef typename Map::Value Value;
00051 typedef typename Map::Reference Reference;
00053 typedef typename Map::Pointer Pointer;
00054
00056 typedef typename Map::ConstValue ConstValue;
00058 typedef typename Map::ConstReference ConstReference;
00060 typedef typename Map::ConstPointer ConstPointer;
00061
00062 protected:
00063
00064 KeyIt it;
00065
00067 MapIteratorBase() {}
00068
00070 MapIteratorBase(const KeyIt pit) : it(pit) {}
00071
00072 public:
00073
00075 void increment() {
00076 ++it;
00077 }
00078
00080 bool operator==(const MapIteratorBase& pit) const {
00081 return pit.it == it;
00082 }
00083
00085 bool operator!=(const MapIteratorBase& pit) const {
00086 return !(*this == pit);
00087 }
00088 };
00089
00090 template <typename Map> class MapConstIterator;
00091
00095 template <typename Map>
00096 class MapIterator : public MapIteratorBase<Map> {
00097
00098 friend class MapConstIterator<Map>;
00099
00100
00101 public:
00102
00104 typedef MapIteratorBase<Map> Base;
00105
00107 typedef typename Map::Key Key;
00109 typedef typename Map::KeyIt KeyIt;
00110
00112 typedef typename Map::Value Value;
00114 typedef typename Map::Reference Reference;
00116 typedef typename Map::Pointer Pointer;
00117
00119 typedef typename Map::ConstValue ConstValue;
00121 typedef typename Map::ConstReference ConstReference;
00123 typedef typename Map::ConstPointer ConstPointer;
00124
00125 public:
00126
00128 typedef extended_pair<Key, const Key&,
00129 Value, const Value&> PairValue;
00130
00132 typedef extended_pair<const Key&, const Key&,
00133 Reference, Reference> PairReference;
00134
00136 MapIterator() {}
00137
00140 MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {}
00141
00143 PairReference operator*() {
00144 return PairReference(Base::it, (*map)[Base::it]);
00145 }
00146
00148 class PairPointer {
00149 friend class MapIterator;
00150 private:
00151 PairReference data;
00152 PairPointer(const Key& key, Reference val)
00153 : data(key, val) {}
00154 public:
00155 PairReference* operator->() {return &data;}
00156 };
00157
00159 PairPointer operator->() {
00160 return PairPointer(Base::it, ((*map)[Base::it]));
00161 }
00162
00164 MapIterator& operator++() {
00165 Base::increment();
00166 return *this;
00167 }
00168
00170 MapIterator operator++(int) {
00171 MapIterator tmp(*this);
00172 Base::increment();
00173 return tmp;
00174 }
00175
00176 private:
00177 Map* map;
00178
00179 public:
00180
00181 typedef std::forward_iterator_tag iterator_category;
00182 typedef int difference_type;
00183 typedef PairValue value_type;
00184 typedef PairReference reference;
00185 typedef PairPointer pointer;
00186 };
00187
00191 template <typename Map>
00192 class MapConstIterator : public MapIteratorBase<Map> {
00193
00194 public:
00195
00197 typedef MapIteratorBase<Map> Base;
00198
00200 typedef typename Map::Key Key;
00202 typedef typename Map::KeyIt KeyIt;
00203
00205 typedef typename Map::Value Value;
00207 typedef typename Map::Reference Reference;
00209 typedef typename Map::Pointer Pointer;
00210
00212 typedef typename Map::ConstValue ConstValue;
00214 typedef typename Map::ConstReference ConstReference;
00216 typedef typename Map::ConstPointer ConstPointer;
00217
00218 public:
00219
00221 MapConstIterator() {}
00222
00225 MapConstIterator(const Map& pmap, const KeyIt& pit)
00226 : Base(pit), map(&pmap) {}
00227
00229 MapConstIterator(const MapIterator<Map>& pit) {
00230 Base::it = pit.Base::it;
00231 map = pit.map;
00232 }
00233
00235 typedef extended_pair<Key, const Key&,
00236 Value, const Value&> PairValue;
00237
00239 typedef extended_pair<const Key&, const Key&,
00240 ConstReference, ConstReference> PairReference;
00241
00243 PairReference operator*() {
00244 return PairReference(Base::it, (*map)[Base::it]);
00245 }
00246
00248 class PairPointer {
00249 friend class MapConstIterator;
00250 private:
00251 PairReference data;
00252 PairPointer(const Key& key, ConstReference val)
00253 : data(key, val) {}
00254 public:
00255 PairReference* operator->() {return &data;}
00256 };
00257
00259 PairPointer operator->() {
00260 return PairPointer(Base::it, (*map)[Base::it]);
00261 }
00262
00264 MapConstIterator& operator++() {
00265 Base::increment();
00266 return *this;
00267 }
00268
00270 MapConstIterator operator++(int) {
00271 MapConstIterator tmp(*this);
00272 Base::increment();
00273 return tmp;
00274 }
00275
00276 private:
00277 const Map* map;
00278
00279 public:
00280
00281 typedef std::input_iterator_tag iterator_category;
00282 typedef int difference_type;
00283 typedef PairValue value_type;
00284 typedef PairReference reference;
00285 typedef PairPointer pointer;
00286 };
00287
00291 template <typename Map>
00292 class MapKeyIterator : public MapIteratorBase<Map> {
00293
00294 public:
00295
00297 typedef MapIteratorBase<Map> Base;
00298
00300 typedef typename Map::Key Key;
00302 typedef typename Map::KeyIt KeyIt;
00303
00304 public:
00305
00307 MapKeyIterator() {}
00308
00310 MapKeyIterator(const KeyIt& pit) : Base(pit) {}
00311
00313 MapKeyIterator& operator++() {
00314 Base::increment();
00315 return *this;
00316 }
00317
00319 MapKeyIterator operator++(int) {
00320 MapKeyIterator tmp(*this);
00321 Base::increment();
00322 return tmp;
00323 }
00324
00326 Key operator*() const {
00327 return static_cast<Key>(Base::it);
00328 }
00329
00330 public:
00331
00332 typedef std::input_iterator_tag iterator_category;
00333 typedef int difference_type;
00334 typedef Key value_type;
00335 typedef const Key& reference;
00336 typedef const Key* pointer;
00337 };
00338
00339 template <typename Map> class MapConstValueIterator;
00340
00344 template <typename Map>
00345 class MapValueIterator : public MapIteratorBase<Map> {
00346
00347 friend class MapConstValueIterator<Map>;
00348
00349 public:
00350
00352 typedef MapIteratorBase<Map> Base;
00353
00355 typedef typename Map::Key Key;
00357 typedef typename Map::KeyIt KeyIt;
00358
00359
00361 typedef typename Map::Value Value;
00363 typedef typename Map::Reference Reference;
00365 typedef typename Map::Pointer Pointer;
00366
00368 typedef typename Map::ConstValue ConstValue;
00370 typedef typename Map::ConstReference ConstReference;
00372 typedef typename Map::ConstPointer ConstPointer;
00373
00374 private:
00375
00376 Map* map;
00377
00378 public:
00379
00381 MapValueIterator() {}
00382
00384 MapValueIterator(Map& pmap, const KeyIt& pit)
00385 : Base(pit), map(&pmap) {}
00386
00387
00389 MapValueIterator& operator++() {
00390 Base::increment();
00391 return *this;
00392 }
00393
00395 MapValueIterator operator++(int) {
00396 MapValueIterator tmp(*this);
00397 Base::increment();
00398 return tmp;
00399 }
00400
00402 Reference operator*() const {
00403 return (*map)[Base::it];
00404 }
00405
00407 Pointer operator->() const {
00408 return &(operator*());
00409 }
00410
00411 public:
00412
00413 typedef std::forward_iterator_tag iterator_category;
00414 typedef int difference_type;
00415 typedef Value value_type;
00416 typedef Reference reference;
00417 typedef Pointer pointer;
00418 };
00419
00424 template <typename Map>
00425 class MapConstValueIterator : public MapIteratorBase<Map> {
00426
00427 public:
00428
00430 typedef MapIteratorBase<Map> Base;
00431
00433 typedef typename Map::Key Key;
00435 typedef typename Map::KeyIt KeyIt;
00436
00438 typedef typename Map::Value Value;
00440 typedef typename Map::Reference Reference;
00442 typedef typename Map::Pointer Pointer;
00443
00445 typedef typename Map::ConstValue ConstValue;
00447 typedef typename Map::ConstReference ConstReference;
00449 typedef typename Map::ConstPointer ConstPointer;
00450
00451 private:
00452
00453 const Map* map;
00454
00455 public:
00456
00458 MapConstValueIterator() {}
00459
00461 MapConstValueIterator(const MapValueIterator<Map>& pit) {
00462 Base::it = pit.Base::it;
00463 map = pit.map;
00464 }
00465
00467 MapConstValueIterator(const Map& pmap, const KeyIt& pit)
00468 : Base(pit), map(&pmap) {}
00469
00471 MapConstValueIterator& operator++() {
00472 Base::increment();
00473 return *this;
00474 }
00475
00477 MapConstValueIterator operator++(int) {
00478 MapConstValueIterator tmp(*this);
00479 Base::increment();
00480 return tmp;
00481 }
00482
00484 ConstReference operator*() const {
00485 return (*map)[Base::it];
00486 }
00487
00489 ConstPointer operator->() const {
00490 return &(operator*());
00491 }
00492
00493 public:
00494
00495 typedef std::input_iterator_tag iterator_category;
00496 typedef int difference_type;
00497 typedef Value value_type;
00498 typedef ConstReference reference;
00499 typedef ConstPointer pointer;
00500 };
00501
00502
00506 template <typename Map>
00507 class MapConstKeySet {
00508
00509 const Map* map;
00510
00511 public:
00512
00514 typedef typename Map::Key Key;
00516 typedef typename Map::KeyIt KeyIt;
00517
00518
00520 typedef typename Map::Value Value;
00522 typedef typename Map::Reference Reference;
00524 typedef typename Map::Pointer Pointer;
00525
00527 typedef typename Map::ConstValue ConstValue;
00529 typedef typename Map::ConstReference ConstReference;
00531 typedef typename Map::ConstPointer ConstPointer;
00532
00534 MapConstKeySet(const Map& pmap) : map(&pmap) {}
00535
00537 typedef MapKeyIterator<Map> ConstIterator;
00538
00540 ConstIterator begin() const {
00541 return ConstIterator(KeyIt(*map->getGraph()));
00542 }
00543
00545 ConstIterator end() const {
00546 return ConstIterator(KeyIt(INVALID));
00547 }
00548
00549 public:
00550
00551 typedef Value value_type;
00552 typedef ConstIterator const_iterator;
00553 typedef ConstReference const_reference;
00554 typedef ConstPointer const_pointer;
00555 typedef int difference_type;
00556 };
00557
00562 template <typename Map>
00563 class MapConstValueSet {
00564
00565 const Map* map;
00566
00567 public:
00568
00570 typedef typename Map::Key Key;
00572 typedef typename Map::KeyIt KeyIt;
00573
00574
00576 typedef typename Map::Value Value;
00578 typedef typename Map::Reference Reference;
00580 typedef typename Map::Pointer Pointer;
00581
00583 typedef typename Map::ConstValue ConstValue;
00585 typedef typename Map::ConstReference ConstReference;
00587 typedef typename Map::ConstPointer ConstPointer;
00588
00590 MapConstValueSet(const Map& pmap) : map(&pmap) {}
00591
00593 typedef MapConstValueIterator<Map> ConstIterator;
00594
00596 ConstIterator begin() const {
00597 return ConstIterator(*map, KeyIt(*map->getGraph()));
00598 }
00599
00601 ConstIterator end() const {
00602 return ConstIterator(*map, KeyIt(INVALID));
00603 }
00604
00605 public:
00606
00607 typedef Value value_type;
00608 typedef ConstIterator const_iterator;
00609 typedef ConstReference const_reference;
00610 typedef ConstPointer const_pointer;
00611 typedef int difference_type;
00612 };
00613
00614
00619 template <typename Map>
00620 class MapValueSet {
00621
00622 Map* map;
00623
00624 public:
00625
00627 typedef typename Map::Key Key;
00629 typedef typename Map::KeyIt KeyIt;
00630
00631
00633 typedef typename Map::Value Value;
00635 typedef typename Map::Reference Reference;
00637 typedef typename Map::Pointer Pointer;
00638
00640 typedef typename Map::ConstValue ConstValue;
00642 typedef typename Map::ConstReference ConstReference;
00644 typedef typename Map::ConstPointer ConstPointer;
00645
00647 MapValueSet(Map& pmap) : map(&pmap) {}
00648
00650 typedef MapConstValueIterator<Map> ConstIterator;
00651
00653 ConstIterator begin() const {
00654 return ConstIterator(*map, KeyIt(*map->getGraph()));
00655 }
00656
00658 ConstIterator end() const {
00659 return ConstIterator(*map, KeyIt(INVALID));
00660 }
00661
00663 typedef MapValueIterator<Map> Iterator;
00664
00666 Iterator begin() {
00667 return Iterator(*map, KeyIt(*map->getGraph()));
00668 }
00669
00671 Iterator end() {
00672 return Iterator(*map, KeyIt(INVALID));
00673 }
00674
00675 public:
00676
00677 typedef Value value_type;
00678 typedef Iterator iterator;
00679 typedef ConstIterator const_iterator;
00680 typedef Reference reference;
00681 typedef ConstReference const_reference;
00682 typedef Pointer pointer;
00683 typedef ConstPointer const_pointer;
00684 typedef int difference_type;
00685
00686 };
00687
00689
00690 }
00691
00692 #endif