lemon-0.x: src/hugo/map_iterator.h@89dfa3bece81

     1 // -*- c++ -*-

     2 #ifndef MAP_ITERATOR_H

     3 #define MAP_ITERATOR_H

     5 #include <hugo/extended_pair.h>

     7 ///\ingroup graphmaps

     8 ///\file

     9 ///\brief Iterators on the maps.

    11 namespace hugo {

    13   /// \addtogroup graphmaps

    14   /// @{

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

    17    *  The class defines the typedefs of the iterators,

    18    *  simple step functions and equality operators.

    19    */

    21   template <typename Map>

    22   class MapIteratorBase {

    24   public:

    25     /// The key type of the iterator.

    26     typedef typename Map::KeyType KeyType;

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

    28     typedef typename Map::KeyIt KeyIt;

    30     /// The value type of the iterator.

    31     typedef typename Map::ValueType ValueType;

    32     /// The reference type of the iterator.

    33     typedef typename Map::ReferenceType ReferenceType;

    34     /// The pointer type of the iterator.

    35     typedef typename Map::PointerType PointerType;

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

    38     typedef typename Map::ConstValueType ConstValueType;

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

    40     typedef typename Map::ConstReferenceType ConstReferenceType;

    41     /// The pointer type of the iterator.

    42     typedef typename Map::ConstPointerType ConstPointerType;

    44   protected:

    46     KeyIt it;

    48     /// Default constructor.

    49     MapIteratorBase() {}

    51     /// KeyIt initialized MapIteratorBase constructor.

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

    54   public:

    56     /// Stepping forward in the map.

    57     void increment() {

    58       ++it;

    59     }

    61     /// The equality operator of the map.

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

    63       return pit.it == it;

    64     }

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

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

    68       return !(*this == pit);

    69     }

    70   };

    72   template <typename Map> class MapConstIterator;

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

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

    76    */

    77   template <typename Map>

    78   class MapIterator : public MapIteratorBase<Map> {

    80     friend class MapConstIterator<Map>;

    82   public:

    84     /// The key type of the iterator.

    85     typedef typename Map::KeyType KeyType;

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

    87     typedef typename Map::KeyIt KeyIt;

    89     /// The value type of the iterator.

    90     typedef typename Map::ValueType ValueType;

    91     /// The reference type of the iterator.

    92     typedef typename Map::ReferenceType ReferenceType;

    93     /// The pointer type of the iterator.

    94     typedef typename Map::PointerType PointerType;

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

    97     typedef typename Map::ConstValueType ConstValueType;

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

    99     typedef typename Map::ConstReferenceType ConstReferenceType;

   100     /// The pointer type of the iterator.

   101     typedef typename Map::ConstPointerType ConstPointerType;

   103   public:

   105     /// The reference type of the iterator.

   106     typedef extended_pair<const KeyType&, const KeyType&,

   107       ReferenceType, ReferenceType> PairReferenceType;

   109     /// Default constructor.

   110     MapIterator() {}

   112     /// Constructor to initalize the iterators returned

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

   114     MapIterator(Map& pmap, const KeyIt& pit)

   115       : MapIteratorBase<Map>(pit), map(&pmap) {}

   117     /// Dereference operator for the iterator.

   118     PairReferenceType operator*() {

   119       return PairReferenceType(it, (*map)[it]);

   120     }

   122     /// The pointer type of the iterator.

   123     class PairPointerType {

   124       friend class MapIterator;

   125     private:

   126       PairReferenceType data;

   127       PairPointerType(const KeyType& key, ReferenceType val)

   128 	: data(key, val) {}

   129     public:

   130       PairReferenceType* operator->() {return &data;}

   131     };

   133     /// Arrow operator for the iterator.

   134     PairPointerType operator->() {

   135       return PairPointerType(it, ((*map)[it]));

   136     }

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

   139     MapIterator& operator++() {

   140       increment();

   141       return *this;

   142     }

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

   145     MapIterator operator++(int) {

   146       MapIterator tmp(it);

   147       increment();

   148       return tmp;

   149     }

   151   private:

   152     Map* map;

   153   };

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

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

   157    */

   158   template <typename Map>

   159   class MapConstIterator : public MapIteratorBase<Map> {

   161   public:

   163     /// The key type of the iterator.

   164     typedef typename Map::KeyType KeyType;

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

   166     typedef typename Map::KeyIt KeyIt;

   168     /// The value type of the iterator.

   169     typedef typename Map::ValueType ValueType;

   170     /// The reference type of the iterator.

   171     typedef typename Map::ReferenceType ReferenceType;

   172     /// The pointer type of the iterator.

   173     typedef typename Map::PointerType PointerType;

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

   176     typedef typename Map::ConstValueType ConstValueType;

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

   178     typedef typename Map::ConstReferenceType ConstReferenceType;

   179     /// The pointer type of the iterator.

   180     typedef typename Map::ConstPointerType ConstPointerType;

   182   public:

   184     /// Default constructor.

   185     MapConstIterator() {}

   187     /// Constructor to initalize the the iterators returned

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

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

   190       : MapIteratorBase<Map>(pit), map(&pmap) {}

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

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

   194       it = pit.it;

   195       map = pit.map;

   196     }

   198     /// The reference type of map.

   199     typedef extended_pair<const KeyType&, const KeyType&,

   200       ConstReferenceType, ConstReferenceType> PairReferenceType;

   202     /// Dereference operator for the iterator.

   203     PairReferenceType operator*() {

   204       return PairReferenceType(it, (*map)[it]);

   205     }

   207     /// The pointer type of the iterator.

   208     class PairPointerType {

   209       friend class MapConstIterator;

   210     private:

   211       PairReferenceType data;

   212       PairPointerType(const KeyType& key, ConstReferenceType val)

   213 	: data(key, val) {}

   214     public:

   215       PairReferenceType* operator->() {return &data;}

   216     };

   218     /// Arrow operator for the iterator.

   219     PairPointerType operator->() {

   220       return PairPointerType(it, ((*map)[it]));

   221     }

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

   224     MapConstIterator& operator++() {

   225       increment();

   226       return *this;

   227     }

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

   230     MapConstIterator operator++(int) {

   231       MapConstIterator<Map> tmp(it);

   232       increment();

   233       return tmp;

   234     }

   236   private:

   237     const Map* map;

   238   };

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

   241    *  with dereferencing operator.

   242    */

   243   template <typename Map>

   244   class MapKeyIterator : public MapIteratorBase<Map> {

   246   public:

   248     /// The key type of the iterator.

   249     typedef typename Map::KeyType KeyType;

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

   251     typedef typename Map::KeyIt KeyIt;

   253   public:

   255     /// Default constructor.

   256     MapKeyIterator() {}

   258     /// KeyIt initialized iterator.

   259     MapKeyIterator(const KeyIt& pit) : MapIteratorBase<Map>(pit) {}

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

   262     MapKeyIterator& operator++() {

   263       increment();

   264       return *this;

   265     }

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

   268     MapKeyIterator operator++(int) {

   269       MapKeyIterator tmp(*this);

   270       increment();

   271       return tmp;

   272     }

   274     /// The dereferencing operator of the iterator.

   275     KeyType operator*() const {

   276       return static_cast<KeyType>(it);

   277     }

   278   };

   280   template <typename Map> class MapConstValueIterator;

   282   template <typename Map>

   283   class MapValueIterator : public MapIteratorBase<Map> {

   285     friend class MapConstValueIterator<Map>;

   287   public:

   289     /// The key type of the iterator.

   290     typedef typename Map::KeyType KeyType;

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

   292     typedef typename Map::KeyIt KeyIt;

   295     /// The value type of the iterator.

   296     typedef typename Map::ValueType ValueType;

   297     /// The reference type of the iterator.

   298     typedef typename Map::ReferenceType ReferenceType;

   299     /// The pointer type of the iterator.

   300     typedef typename Map::PointerType PointerType;

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

   303     typedef typename Map::ConstValueType ConstValueType;

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

   305     typedef typename Map::ConstReferenceType ConstReferenceType;

   306     /// The pointer type of the iterator.

   307     typedef typename Map::ConstPointerType ConstPointerType;

   309   private:

   311     Map* map;

   313   public:

   315     /// Default constructor.

   316     MapValueIterator() {}

   318     /// Map and KeyIt initialized iterator.

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

   320       : MapIteratorBase<Map>(pit), map(&pmap) {}

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

   324     MapValueIterator& operator++() {

   325       increment();

   326       return *this;

   327     }

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

   330     MapValueIterator operator++(int) {

   331       MapValueIterator tmp(*this);

   332       increment();

   333       return tmp;

   334     }

   336     /// The dereferencing operator of the iterator.

   337     ReferenceType operator*() const {

   338       return (*map)[it];

   339     }

   341     /// The arrow operator of the iterator.

   342     PointerType operator->() const {

   343       return &(operator*());

   344     }

   346   };

   349   template <typename Map>

   350   class MapConstValueIterator : public MapIteratorBase<Map> {

   352   public:

   354     /// The key type of the iterator.

   355     typedef typename Map::KeyType KeyType;

   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::ValueType ValueType;

   362     /// The reference type of the iterator.

   363     typedef typename Map::ReferenceType ReferenceType;

   364     /// The pointer type of the iterator.

   365     typedef typename Map::PointerType PointerType;

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

   368     typedef typename Map::ConstValueType ConstValueType;

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

   370     typedef typename Map::ConstReferenceType ConstReferenceType;

   371     /// The pointer type of the iterator.

   372     typedef typename Map::ConstPointerType ConstPointerType;

   374   private:

   376     const Map* map;

   378   public:

   380     /// Default constructor.

   381     MapConstValueIterator() {}

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

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

   385       it = pit.it;

   386       map = pit.map;

   387     }

   389     /// Map and KeyIt initialized iterator.

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

   391       : MapIteratorBase<Map>(pit), map(&pmap) {}

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

   394     MapConstValueIterator& operator++() {

   395       increment();

   396       return *this;

   397     }

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

   400     MapConstValueIterator operator++(int) {

   401       MapConstValueIterator tmp(*this);

   402       increment();

   403       return tmp;

   404     }

   406     /// The dereferencing operator of the iterator.

   407     ConstReferenceType operator*() const {

   408       return (*map)[it];

   409     }

   411     /// The arrow operator of the iterator.

   412     ConstPointerType operator->() const {

   413       return &(operator*());

   414     }

   416   };

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

   420    *  which contains all the keys of the map.

   421    */

   422   template <typename Map>

   423   class MapConstKeySet {

   425     const Map* map;

   427   public:

   429     /// The key type of the iterator.

   430     typedef typename Map::KeyType KeyType;

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

   432     typedef typename Map::KeyIt KeyIt;

   434     /// The map initialized const key set.

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

   437     /// The const iterator of the set.

   438     typedef MapKeyIterator<Map> ConstIterator;

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

   441     ConstIterator begin() const {

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

   443     }

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

   446     ConstIterator end() const {

   447       return ConstIterator(KeyIt(INVALID));

   448     }

   449   };

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

   452    *  which contains all the values of the map.

   453    *  The values cannot be modified.

   454    */

   455   template <typename Map>

   456   class MapConstValueSet {

   458     const Map* map;

   460   public:

   462     /// The key type of the iterator.

   463     typedef typename Map::KeyType KeyType;

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

   465     typedef typename Map::KeyIt KeyIt;

   467     /// The map initialized const value set.

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

   470     /// The const iterator of the set.

   471     typedef MapConstValueIterator<Map> ConstIterator;

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

   474     ConstIterator begin() const {

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

   476     }

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

   479     ConstIterator end() const {

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

   481     }

   482   };

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

   486    *  which contains all the values of the map.

   487    *  The values can be modified.

   488    */

   489   template <typename Map>

   490   class MapValueSet {

   492     Map* map;

   494   public:

   496     /// The key type of the iterator.

   497     typedef typename Map::KeyType KeyType;

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

   499     typedef typename Map::KeyIt KeyIt;

   501     /// The map initialized value set.

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

   504     /// The const iterator of the set.

   505     typedef MapConstValueIterator<Map> ConstIterator;

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

   508     ConstIterator begin() const {

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

   510     }

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

   513     ConstIterator end() const {

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

   515     }

   517     /// The iterator of the set.

   518     typedef MapValueIterator<Map> Iterator;

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

   521     Iterator begin() {

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

   523     }

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

   526     Iterator end() {

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

   528     }

   530   };

   532   /// @}

   534 }

   536 #endif

author	deba
	Sun, 12 Sep 2004 19:32:21 +0000
changeset 830	89dfa3bece81
parent 822	88226d9fe821
child 844	9bf990cb066d
permissions	-rw-r--r--