Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

map_iterator.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
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     // STL  compatibility typedefs.
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     // STL  compatibility typedefs.
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     // STL  compatibility typedefs.
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     // STL  compatibility typedefs.
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     // STL  compatibility typedefs.
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     // STL  compatibility typedefs.
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     // STL  compatibility typedefs.
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     // STL  compatibility typedefs.
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

Generated on Sat Mar 19 10:58:40 2005 for LEMON by  doxygen 1.4.1