lemon-0.x: src/lemon/map_iterator.h@099978eee03f

     1 /* -*- C++ -*-

     2  * src/lemon/map_iterator.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Combinatorial Optimization Research Group, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    17 #ifndef LEMON_MAP_ITERATOR_H

    18 #define LEMON_MAP_ITERATOR_H

    20 #include <iterator>

    22 #include <lemon/extended_pair.h>

    24 ///\ingroup graphmaps

    25 ///\file

    26 ///\brief Iterators on the maps.

    28 namespace lemon {

    30   /// \addtogroup graphmaps

    31   /// @{

    33   /** The base class all of the map iterators.

    34    *  The class defines the typedefs of the iterators,

    35    *  simple step functions and equality operators.

    36    */

    38   template <typename Map>

    39   class MapIteratorBase {

    41   public:

    43     /// The key type of the iterator.

    44     typedef typename Map::Key Key;

    45     /// The iterator to iterate on the keys.

    46     typedef typename Map::KeyIt KeyIt;

    48     /// The value type of the iterator.

    49     typedef typename Map::Value Value;

    50     /// The reference type of the iterator.

    51     typedef typename Map::Reference Reference;

    52     /// The pointer type of the iterator.

    53     typedef typename Map::Pointer Pointer;

    55     /// The const value type of the iterator.

    56     typedef typename Map::ConstValue ConstValue;

    57     /// The const reference type of the iterator.

    58     typedef typename Map::ConstReference ConstReference;

    59     /// The pointer type of the iterator.

    60     typedef typename Map::ConstPointer ConstPointer;

    62   protected:

    64     KeyIt it;

    66     /// Default constructor.

    67     MapIteratorBase() {}

    69     /// KeyIt initialized MapIteratorBase constructor.

    70     MapIteratorBase(const KeyIt pit) : it(pit) {}

    72   public:

    74     /// Stepping forward in the map.

    75     void increment() {

    76       ++it;

    77     }

    79     /// The equality operator of the map.

    80     bool operator==(const MapIteratorBase& pit) const {

    81       return pit.it == it;

    82     }

    84     /// The not-equality operator of the map.

    85     bool operator!=(const MapIteratorBase& pit) const {

    86       return !(*this == pit);

    87     }

    88   };

    90   template <typename Map> class MapConstIterator;

    92   /** Compatible iterator with the stl maps' iterators.

    93    * It iterates on pairs of a key and a value.

    94    */

    95   template <typename Map>

    96   class MapIterator : public MapIteratorBase<Map> {

    98     friend class MapConstIterator<Map>;

   101   public:

   103     /// The iterator base class.

   104     typedef MapIteratorBase<Map> Base;

   106     /// The key type of the iterator.

   107     typedef typename Map::Key Key;

   108     /// The iterator to iterate on the keys.

   109     typedef typename Map::KeyIt KeyIt;

   111     /// The value type of the iterator.

   112     typedef typename Map::Value Value;

   113     /// The reference type of the iterator.

   114     typedef typename Map::Reference Reference;

   115     /// The pointer type of the iterator.

   116     typedef typename Map::Pointer Pointer;

   118     /// The const value type of the iterator.

   119     typedef typename Map::ConstValue ConstValue;

   120     /// The const reference type of the iterator.

   121     typedef typename Map::ConstReference ConstReference;

   122     /// The pointer type of the iterator.

   123     typedef typename Map::ConstPointer ConstPointer;

   125   public:

   127     /// The value type of the iterator.

   128     typedef extended_pair<Key, const Key&,

   129       Value, const Value&> PairValue;

   131     /// The reference type of the iterator.

   132     typedef extended_pair<const Key&, const Key&,

   133       Reference, Reference> PairReference;

   135     /// Default constructor.

   136     MapIterator() {}

   138     /// Constructor to initalize the iterators returned

   139     /// by the begin() and end().

   140     MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {}

   142     /// Dereference operator for the iterator.

   143     PairReference operator*() {

   144       return PairReference(Base::it, (*map)[Base::it]);

   145     }

   147     /// The pointer type of the iterator.

   148     class PairPointer {

   149       friend class MapIterator;

   150     private:

   151       PairReference data;

   152       PairPointer(const Key& key, Reference val)

   153 	: data(key, val) {}

   154     public:

   155       PairReference* operator->() {return &data;}

   156     };

   158     /// Arrow operator for the iterator.

   159     PairPointer operator->() {

   160       return PairPointer(Base::it, ((*map)[Base::it]));

   161     }

   163     /// The pre increment operator of the iterator.

   164     MapIterator& operator++() {

   165       Base::increment();

   166       return *this;

   167     }

   169     /// The post increment operator of the iterator.

   170     MapIterator operator++(int) {

   171       MapIterator tmp(*this);

   172       Base::increment();

   173       return tmp;

   174     }

   176   private:

   177     Map* map;

   179   public:

   180     // STL  compatibility typedefs.

   181     typedef std::forward_iterator_tag iterator_category;

   182     typedef int difference_type;

   183     typedef PairValue value_type;

   184     typedef PairReference reference;

   185     typedef PairPointer pointer;

   186   };

   188   /** Compatible iterator with the stl maps' iterators.

   189    *  It iterates on pairs of a key and a value.

   190    */

   191   template <typename Map>

   192   class MapConstIterator : public MapIteratorBase<Map> {

   194   public:

   196     /// The iterator base class.

   197     typedef MapIteratorBase<Map> Base;

   199     /// The key type of the iterator.

   200     typedef typename Map::Key Key;

   201     /// The iterator to iterate on the keys.

   202     typedef typename Map::KeyIt KeyIt;

   204     /// The value type of the iterator.

   205     typedef typename Map::Value Value;

   206     /// The reference type of the iterator.

   207     typedef typename Map::Reference Reference;

   208     /// The pointer type of the iterator.

   209     typedef typename Map::Pointer Pointer;

   211     /// The const value type of the iterator.

   212     typedef typename Map::ConstValue ConstValue;

   213     /// The const reference type of the iterator.

   214     typedef typename Map::ConstReference ConstReference;

   215     /// The pointer type of the iterator.

   216     typedef typename Map::ConstPointer ConstPointer;

   218   public:

   220     /// Default constructor.

   221     MapConstIterator() {}

   223     /// Constructor to initalize the the iterators returned

   224     ///  by the begin() and end().

   225     MapConstIterator(const Map& pmap, const KeyIt& pit)

   226       : Base(pit), map(&pmap) {}

   228     /// Constructor to create const iterator from a non const.

   229     MapConstIterator(const MapIterator<Map>& pit) {

   230       Base::it = pit.Base::it;

   231       map = pit.map;

   232     }

   234     /// The value type of the iterator.

   235     typedef extended_pair<Key, const Key&,

   236       Value, const Value&> PairValue;

   238     /// The reference type of map.

   239     typedef extended_pair<const Key&, const Key&,

   240       ConstReference, ConstReference> PairReference;

   242     /// Dereference operator for the iterator.

   243     PairReference operator*() {

   244       return PairReference(Base::it, (*map)[Base::it]);

   245     }

   247     /// The pointer type of the iterator.

   248     class PairPointer {

   249       friend class MapConstIterator;

   250     private:

   251       PairReference data;

   252       PairPointer(const Key& key, ConstReference val)

   253 	: data(key, val) {}

   254     public:

   255       PairReference* operator->() {return &data;}

   256     };

   258     /// Arrow operator for the iterator.

   259     PairPointer operator->() {

   260       return PairPointer(Base::it, (*map)[Base::it]);

   261     }

   263     /// The pre increment operator of the iterator.

   264     MapConstIterator& operator++() {

   265       Base::increment();

   266       return *this;

   267     }

   269     /// The post increment operator of the iterator.

   270     MapConstIterator operator++(int) {

   271       MapConstIterator tmp(*this);

   272       Base::increment();

   273       return tmp;

   274     }

   276   private:

   277     const Map* map;

   279   public:

   280     // STL  compatibility typedefs.

   281     typedef std::input_iterator_tag iterator_category;

   282     typedef int difference_type;

   283     typedef PairValue value_type;

   284     typedef PairReference reference;

   285     typedef PairPointer pointer;

   286   };

   288   /** The class makes the KeyIt to an stl compatible iterator

   289    *  with dereferencing operator.

   290    */

   291   template <typename Map>

   292   class MapKeyIterator : public MapIteratorBase<Map> {

   294   public:

   296     /// The iterator base class.

   297     typedef MapIteratorBase<Map> Base;

   299     /// The key type of the iterator.

   300     typedef typename Map::Key Key;

   301     /// The iterator to iterate on the keys.

   302     typedef typename Map::KeyIt KeyIt;

   304   public:

   306     /// Default constructor.

   307     MapKeyIterator() {}

   309     /// KeyIt initialized iterator.

   310     MapKeyIterator(const KeyIt& pit) : Base(pit) {}

   312     /// The pre increment operator of the iterator.

   313     MapKeyIterator& operator++() {

   314       Base::increment();

   315       return *this;

   316     }

   318     /// The post increment operator of the iterator.

   319     MapKeyIterator operator++(int) {

   320       MapKeyIterator tmp(*this);

   321       Base::increment();

   322       return tmp;

   323     }

   325     /// The dereferencing operator of the iterator.

   326     Key operator*() const {

   327       return static_cast<Key>(Base::it);

   328     }

   330   public:

   331     // STL  compatibility typedefs.

   332     typedef std::input_iterator_tag iterator_category;

   333     typedef int difference_type;

   334     typedef Key value_type;

   335     typedef const Key& reference;

   336     typedef const Key* pointer;

   337   };

   339   template <typename Map> class MapConstValueIterator;

   341   /** MapValueIterator creates an stl compatible iterator

   342    *  for the values.

   343    */

   344   template <typename Map>

   345   class MapValueIterator : public MapIteratorBase<Map> {

   347     friend class MapConstValueIterator<Map>;

   349   public:

   351     /// The iterator base class.

   352     typedef MapIteratorBase<Map> Base;

   354     /// The key type of the iterator.

   355     typedef typename Map::Key Key;

   356     /// The iterator to iterate on the keys.

   357     typedef typename Map::KeyIt KeyIt;

   360     /// The value type of the iterator.

   361     typedef typename Map::Value Value;

   362     /// The reference type of the iterator.

   363     typedef typename Map::Reference Reference;

   364     /// The pointer type of the iterator.

   365     typedef typename Map::Pointer Pointer;

   367     /// The const value type of the iterator.

   368     typedef typename Map::ConstValue ConstValue;

   369     /// The const reference type of the iterator.

   370     typedef typename Map::ConstReference ConstReference;

   371     /// The pointer type of the iterator.

   372     typedef typename Map::ConstPointer ConstPointer;

   374   private:

   376     Map* map;

   378   public:

   380     /// Default constructor.

   381     MapValueIterator() {}

   383     /// Map and KeyIt initialized iterator.

   384     MapValueIterator(Map& pmap, const KeyIt& pit)

   385       : Base(pit), map(&pmap) {}

   388     /// The pre increment operator of the iterator.

   389     MapValueIterator& operator++() {

   390       Base::increment();

   391       return *this;

   392     }

   394     /// The post increment operator of the iterator.

   395     MapValueIterator operator++(int) {

   396       MapValueIterator tmp(*this);

   397       Base::increment();

   398       return tmp;

   399     }

   401     /// The dereferencing operator of the iterator.

   402     Reference operator*() const {

   403       return (*map)[Base::it];

   404     }

   406     /// The arrow operator of the iterator.

   407     Pointer operator->() const {

   408       return &(operator*());

   409     }

   411   public:

   412     // STL  compatibility typedefs.

   413     typedef std::forward_iterator_tag iterator_category;

   414     typedef int difference_type;

   415     typedef Value value_type;

   416     typedef Reference reference;

   417     typedef Pointer pointer;

   418   };

   420   /** MapValueIterator creates an stl compatible iterator

   421    *  for the const values.

   422    */

   424   template <typename Map>

   425   class MapConstValueIterator : public MapIteratorBase<Map> {

   427   public:

   429     /// The iterator base class.

   430     typedef MapIteratorBase<Map> Base;

   432     /// The key type of the iterator.

   433     typedef typename Map::Key Key;

   434     /// The iterator to iterate on the keys.

   435     typedef typename Map::KeyIt KeyIt;

   437     /// The value type of the iterator.

   438     typedef typename Map::Value Value;

   439     /// The reference type of the iterator.

   440     typedef typename Map::Reference Reference;

   441     /// The pointer type of the iterator.

   442     typedef typename Map::Pointer Pointer;

   444     /// The const value type of the iterator.

   445     typedef typename Map::ConstValue ConstValue;

   446     /// The const reference type of the iterator.

   447     typedef typename Map::ConstReference ConstReference;

   448     /// The pointer type of the iterator.

   449     typedef typename Map::ConstPointer ConstPointer;

   451   private:

   453     const Map* map;

   455   public:

   457     /// Default constructor.

   458     MapConstValueIterator() {}

   460     /// Constructor to create const iterator from a non const.

   461     MapConstValueIterator(const MapValueIterator<Map>& pit) {

   462       Base::it = pit.Base::it;

   463       map = pit.map;

   464     }

   466     /// Map and KeyIt initialized iterator.

   467     MapConstValueIterator(const Map& pmap, const KeyIt& pit)

   468       : Base(pit), map(&pmap) {}

   470     /// The pre increment operator of the iterator.

   471     MapConstValueIterator& operator++() {

   472       Base::increment();

   473       return *this;

   474     }

   476     /// The post increment operator of the iterator.

   477     MapConstValueIterator operator++(int) {

   478       MapConstValueIterator tmp(*this);

   479       Base::increment();

   480       return tmp;

   481     }

   483     /// The dereferencing operator of the iterator.

   484     ConstReference operator*() const {

   485       return (*map)[Base::it];

   486     }

   488     /// The arrow operator of the iterator.

   489     ConstPointer operator->() const {

   490       return &(operator*());

   491     }

   493   public:

   494     // STL  compatibility typedefs.

   495     typedef std::input_iterator_tag iterator_category;

   496     typedef int difference_type;

   497     typedef Value value_type;

   498     typedef ConstReference reference;

   499     typedef ConstPointer pointer;

   500   };

   503   /** This class makes from a map an iteratable set

   504    *  which contains all the keys of the map.

   505    */

   506   template <typename Map>

   507   class MapConstKeySet {

   509     const Map* map;

   511   public:

   513     /// The key type of the iterator.

   514     typedef typename Map::Key Key;

   515     /// The iterator to iterate on the keys.

   516     typedef typename Map::KeyIt KeyIt;

   519     /// The value type of the iterator.

   520     typedef typename Map::Value Value;

   521     /// The reference type of the iterator.

   522     typedef typename Map::Reference Reference;

   523     /// The pointer type of the iterator.

   524     typedef typename Map::Pointer Pointer;

   526     /// The const value type of the iterator.

   527     typedef typename Map::ConstValue ConstValue;

   528     /// The const reference type of the iterator.

   529     typedef typename Map::ConstReference ConstReference;

   530     /// The pointer type of the iterator.

   531     typedef typename Map::ConstPointer ConstPointer;

   533     /// The map initialized const key set.

   534     MapConstKeySet(const Map& pmap) : map(&pmap) {}

   536     /// The const iterator of the set.

   537     typedef MapKeyIterator<Map> ConstIterator;

   539     /// It gives back the const iterator pointed to the first element.

   540     ConstIterator begin() const {

   541       return ConstIterator(KeyIt(*map->getGraph()));

   542     }

   544     /// It gives back the const iterator pointed to the first ivalid element.

   545     ConstIterator end() const {

   546       return ConstIterator(KeyIt(INVALID));

   547     }

   549   public:

   550     // STL  compatibility typedefs.

   551     typedef Value value_type;

   552     typedef ConstIterator const_iterator;

   553     typedef ConstReference const_reference;

   554     typedef ConstPointer const_pointer;

   555     typedef int difference_type;

   556   };

   558   /** This class makes from a map an iteratable set

   559    *  which contains all the values of the map.

   560    *  The values cannot be modified.

   561    */

   562   template <typename Map>

   563   class MapConstValueSet {

   565     const Map* map;

   567   public:

   569     /// The key type of the iterator.

   570     typedef typename Map::Key Key;

   571     /// The iterator to iterate on the keys.

   572     typedef typename Map::KeyIt KeyIt;

   575     /// The value type of the iterator.

   576     typedef typename Map::Value Value;

   577     /// The reference type of the iterator.

   578     typedef typename Map::Reference Reference;

   579     /// The pointer type of the iterator.

   580     typedef typename Map::Pointer Pointer;

   582     /// The const value type of the iterator.

   583     typedef typename Map::ConstValue ConstValue;

   584     /// The const reference type of the iterator.

   585     typedef typename Map::ConstReference ConstReference;

   586     /// The pointer type of the iterator.

   587     typedef typename Map::ConstPointer ConstPointer;

   589     /// The map initialized const value set.

   590     MapConstValueSet(const Map& pmap) : map(&pmap) {}

   592     /// The const iterator of the set.

   593     typedef MapConstValueIterator<Map> ConstIterator;

   595     /// It gives back the const iterator pointed to the first element.

   596     ConstIterator begin() const {

   597       return ConstIterator(*map, KeyIt(*map->getGraph()));

   598     }

   600     /// It gives back the const iterator pointed to the first invalid element.

   601     ConstIterator end() const {

   602       return ConstIterator(*map, KeyIt(INVALID));

   603     }

   605   public:

   606     // STL  compatibility typedefs.

   607     typedef Value value_type;

   608     typedef ConstIterator const_iterator;

   609     typedef ConstReference const_reference;

   610     typedef ConstPointer const_pointer;

   611     typedef int difference_type;

   612   };

   615   /** This class makes from a map an iteratable set

   616    *  which contains all the values of the map.

   617    *  The values can be modified.

   618    */

   619   template <typename Map>

   620   class MapValueSet {

   622     Map* map;

   624   public:

   626     /// The key type of the iterator.

   627     typedef typename Map::Key Key;

   628     /// The iterator to iterate on the keys.

   629     typedef typename Map::KeyIt KeyIt;

   632     /// The value type of the iterator.

   633     typedef typename Map::Value Value;

   634     /// The reference type of the iterator.

   635     typedef typename Map::Reference Reference;

   636     /// The pointer type of the iterator.

   637     typedef typename Map::Pointer Pointer;

   639     /// The const value type of the iterator.

   640     typedef typename Map::ConstValue ConstValue;

   641     /// The const reference type of the iterator.

   642     typedef typename Map::ConstReference ConstReference;

   643     /// The pointer type of the iterator.

   644     typedef typename Map::ConstPointer ConstPointer;

   646     /// The map initialized value set.

   647     MapValueSet(Map& pmap) : map(&pmap) {}

   649     /// The const iterator of the set.

   650     typedef MapConstValueIterator<Map> ConstIterator;

   652     /// It gives back the const iterator pointed to the first element.

   653     ConstIterator begin() const {

   654       return ConstIterator(*map, KeyIt(*map->getGraph()));

   655     }

   657     /// It gives back the const iterator pointed to the first invalid element.

   658     ConstIterator end() const {

   659       return ConstIterator(*map, KeyIt(INVALID));

   660     }

   662     /// The iterator of the set.

   663     typedef MapValueIterator<Map> Iterator;

   665     /// It gives back the iterator pointed to the first element.

   666     Iterator begin() {

   667       return Iterator(*map, KeyIt(*map->getGraph()));

   668     }

   670     /// It gives back the iterator pointed to the first invalid element.

   671     Iterator end() {

   672       return Iterator(*map, KeyIt(INVALID));

   673     }

   675   public:

   676     // STL  compatibility typedefs.

   677     typedef Value value_type;

   678     typedef Iterator iterator;

   679     typedef ConstIterator const_iterator;

   680     typedef Reference reference;

   681     typedef ConstReference const_reference;

   682     typedef Pointer pointer;

   683     typedef ConstPointer const_pointer;

   684     typedef int difference_type;

   686   };

   688   /// @}

   690 }

   692 #endif

author	athos
	Thu, 24 Feb 2005 10:26:50 +0000
changeset 1173	099978eee03f
parent 987	87f7c54892df
child 1267	a93f94dbe3d3
permissions	-rw-r--r--