lemon-0.x: lemon/bits/map_iterator.h@9f99ede44d59

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

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

     3  *

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

     5  * (Egervary Research Group on Combinatorial Optimization, 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/bits/extended_pair.h>

    23 #include <lemon/graph_utils.h>

    25 ///\ingroup graphmaps

    26 ///\file

    27 ///\brief Iterators on the maps.

    29 namespace lemon {

    31   /// \addtogroup graphmaps

    32   /// @{

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

    35    *  The class defines the typedefs of the iterators,

    36    *  simple step functions and equality operators.

    37    */

    39   template <

    40     typename _Graph,

    41     typename _Item>

    42   class MapIteratorBase {

    44   protected:

    46     /// The key type of the iterator.

    47     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;

    49     ItemIt it;

    51     /// Default constructor.

    52     MapIteratorBase() {}

    54     /// ItemIt initialized MapIteratorBase constructor.

    55     MapIteratorBase(const ItemIt _it) : it(_it) {}

    57   public:

    59     /// Stepping forward in the map.

    60     void increment() {

    61       ++it;

    62     }

    64     /// The equality operator of the map.

    65     bool operator==(const MapIteratorBase& _it) const {

    66       return _it.it == it;

    67     }

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

    70     bool operator!=(const MapIteratorBase& _it) const {

    71       return !(*this == _it);

    72     }

    73   };

    76   template <

    77     typename _Graph,

    78     typename _Item,

    79     typename _Map>

    80   class MapConstIterator;

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

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

    84    */

    85   template <

    86     typename _Graph,

    87     typename _Item,

    88     typename _Map>

    89   class MapIterator : public MapIteratorBase<_Graph, _Item> {

    91     friend class MapConstIterator<_Graph, _Item, _Map>;

    94   public:

    96     /// The iterator base class.

    97     typedef MapIteratorBase<_Graph, _Item> Parent;

    99     typedef _Item Item;

   100     typedef _Map Map;

   101     typedef _Graph Graph;

   103   protected:

   105     typedef typename Parent::ItemIt ItemIt;

   107     typedef typename ReferenceMapTraits<_Map>::Value MapValue;

   108     typedef typename ReferenceMapTraits<_Map>::Reference MapReference;

   110   public:

   112     /// The value type of the iterator.

   113     typedef extended_pair<Item, const Item&,

   114       MapValue, const MapValue&> Value;

   116     /// The reference type of the iterator.

   117     typedef extended_pair<const Item&, const Item&,

   118       MapReference, MapReference> Reference;

   120     /// Default constructor.

   121     MapIterator() {}

   123     /// Constructor to initalize the iterators returned

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

   125     MapIterator(Map& _map, const ItemIt& _it)

   126       : Parent(_it), map(&_map) {}

   128     /// Dereference operator for the iterator.

   129     Reference operator*() {

   130       return Reference(Parent::it, (*map)[Parent::it]);

   131     }

   133     /// The pointer type of the iterator.

   134     class Pointer {

   135       friend class MapIterator;

   136     protected:

   137       Reference data;

   138       Pointer(const Item& item, MapReference val)

   139 	: data(item, val) {}

   140     public:

   141       Reference* operator->() {return &data;}

   142     };

   144     /// Arrow operator for the iterator.

   145     Pointer operator->() {

   146       return Pointer(Parent::it, (*map)[Parent::it]);

   147     }

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

   150     MapIterator& operator++() {

   151       Parent::increment();

   152       return *this;

   153     }

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

   156     MapIterator operator++(int) {

   157       MapIterator tmp(*this);

   158       Parent::increment();

   159       return tmp;

   160     }

   162   protected:

   164     Map* map;

   166   public:

   167     // STL  compatibility typedefs.

   168     typedef std::forward_iterator_tag iterator_category;

   169     typedef int difference_type;

   170     typedef Value value_type;

   171     typedef Reference reference;

   172     typedef Pointer pointer;

   173   };

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

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

   177    */

   178   template <

   179     typename _Graph,

   180     typename _Item,

   181     typename _Map>

   182   class MapConstIterator : public MapIteratorBase<_Graph, _Item> {

   184   public:

   186     /// The iterator base class.

   187     typedef MapIteratorBase<_Graph, _Item> Parent;

   189     typedef _Graph Graph;

   190     typedef _Item Item;

   191     typedef _Map Map;

   193   protected:

   195     typedef typename Parent::ItemIt ItemIt;

   197     typedef typename ReferenceMapTraits<_Map>::Value MapValue;

   198     typedef typename ReferenceMapTraits<_Map>::ConstReference

   199     MapReference;

   201   public:

   203     /// The value type of the iterator.

   204     typedef extended_pair<Item, const Item&,

   205       MapValue, const MapValue&> Value;

   207     /// The reference type of the iterator.

   208     typedef extended_pair<const Item&, const Item&,

   209       MapReference, MapReference> Reference;

   211     /// Default constructor.

   212     MapConstIterator() {}

   214     /// Constructor to initalize the iterators returned

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

   216     MapConstIterator(const Map& _map, const ItemIt& _it)

   217       : Parent(_it), map(&_map) {}

   219     /// Dereference operator for the iterator.

   220     Reference operator*() {

   221       return Reference(Parent::it, (*map)[Parent::it]);

   222     }

   224     /// The pointer type of the iterator.

   225     class Pointer {

   226       friend class MapConstIterator;

   227     protected:

   228       Reference data;

   229       Pointer(const Item& item, MapReference val)

   230 	: data(item, val) {}

   231     public:

   232       Reference* operator->() {return &data;}

   233     };

   235     /// Arrow operator for the iterator.

   236     Pointer operator->() {

   237       return Pointer(Parent::it, ((*map)[Parent::it]));

   238     }

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

   241     MapConstIterator& operator++() {

   242       Parent::increment();

   243       return *this;

   244     }

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

   247     MapConstIterator operator++(int) {

   248       MapConstIterator tmp(*this);

   249       Parent::increment();

   250       return tmp;

   251     }

   253   protected:

   254     const Map* map;

   256   public:

   257     // STL  compatibility typedefs.

   258     typedef std::forward_iterator_tag iterator_category;

   259     typedef int difference_type;

   260     typedef Value value_type;

   261     typedef Reference reference;

   262     typedef Pointer pointer;

   263   };

   265   /** The class makes the ItemIt to an stl compatible iterator

   266    *  with dereferencing operator.

   267    */

   268   template <

   269     typename _Graph,

   270     typename _Item>

   271   class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {

   273   public:

   275     /// The iterator base class.

   276     typedef MapIteratorBase<_Graph, _Item> Parent;

   278     typedef _Graph Graph;

   279     typedef _Item Item;

   281   protected:

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

   283     typedef typename Parent::ItemIt ItemIt;

   285   public:

   287     typedef Item Value;

   288     typedef const Item& Reference;

   289     typedef const Item* Pointer;

   291     /// Default constructor.

   292     MapConstKeyIterator() {}

   294     /// ItemIt initialized iterator.

   295     MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}

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

   298     MapConstKeyIterator& operator++() {

   299       Parent::increment();

   300       return *this;

   301     }

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

   304     MapConstKeyIterator operator++(int) {

   305       MapConstKeyIterator tmp(*this);

   306       Parent::increment();

   307       return tmp;

   308     }

   310     /// The dereferencing operator of the iterator.

   311     Item operator*() const {

   312       return static_cast<Item>(Parent::it);

   313     }

   315   public:

   316     // STL  compatibility typedefs.

   317     typedef std::input_iterator_tag iterator_category;

   318     typedef int difference_type;

   319     typedef Value value_type;

   320     typedef Reference reference;

   321     typedef Pointer pointer;

   322   };

   324   template <

   325     typename _Graph,

   326     typename _Item,

   327     typename _Map>

   328   class MapConstValueIterator;

   330   /** MapValueIterator creates an stl compatible iterator

   331    *  for the values.

   332    */

   333   template <

   334     typename _Graph,

   335     typename _Item,

   336     typename _Map>

   337   class MapValueIterator : public MapIteratorBase<_Graph, _Item> {

   339     friend class MapConstValueIterator<_Graph, _Item, _Map>;

   341   public:

   343     /// The iterator base class.

   344     typedef MapIteratorBase<_Graph, _Item> Parent;

   346     typedef _Graph Graph;

   347     typedef _Item Item;

   348     typedef _Map Map;

   350   protected:

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

   353     typedef typename Parent::ItemIt ItemIt;

   355     /// The value type of the iterator.

   356     typedef typename ReferenceMapTraits<Map>::Value MapValue;

   357     /// The reference type of the iterator.

   358     typedef typename ReferenceMapTraits<Map>::Reference MapReference;

   359     /// The pointer type of the iterator.

   360     typedef typename ReferenceMapTraits<Map>::Pointer MapPointer;

   362   public:

   364     typedef MapValue Value;

   365     typedef MapReference Reference;

   366     typedef MapPointer Pointer;

   368     /// Default constructor.

   369     MapValueIterator() {}

   371     /// Map and ItemIt initialized iterator.

   372     MapValueIterator(Map& _map, const ItemIt& _it)

   373       : Parent(_it), map(&_map) {}

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

   377     MapValueIterator& operator++() {

   378       Parent::increment();

   379       return *this;

   380     }

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

   383     MapValueIterator operator++(int) {

   384       MapValueIterator tmp(*this);

   385       Parent::increment();

   386       return tmp;

   387     }

   389     /// The dereferencing operator of the iterator.

   390     Reference operator*() const {

   391       return (*map)[Parent::it];

   392     }

   394     /// The arrow operator of the iterator.

   395     Pointer operator->() const {

   396       return &(operator*());

   397     }

   399   protected:

   401     Map* map;

   403   public:

   404     // STL  compatibility typedefs.

   405     typedef std::forward_iterator_tag iterator_category;

   406     typedef int difference_type;

   407     typedef Value value_type;

   408     typedef Reference reference;

   409     typedef Pointer pointer;

   410   };

   412   /** MapValueIterator creates an stl compatible iterator

   413    *  for the values.

   414    */

   415   template <

   416     typename _Graph,

   417     typename _Item,

   418     typename _Map>

   419   class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {

   421   public:

   423     /// The iterator base class.

   424     typedef MapIteratorBase<_Graph, _Item> Parent;

   426     typedef _Graph Graph;

   427     typedef _Item Item;

   428     typedef _Map Map;

   430   protected:

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

   433     typedef typename Parent::ItemIt ItemIt;

   435     /// The value type of the iterator.

   436     typedef typename ReferenceMapTraits<Map>::Value MapValue;

   437     /// The reference type of the iterator.

   438     typedef typename ReferenceMapTraits<Map>::ConstReference MapReference;

   439     /// The pointer type of the iterator.

   440     typedef typename ReferenceMapTraits<Map>::ConstPointer MapPointer;

   442   public:

   444     typedef MapValue Value;

   445     typedef MapReference Reference;

   446     typedef MapPointer Pointer;

   448     /// Default constructor.

   449     MapConstValueIterator() {}

   451     /// Map and ItemIt initialized iterator.

   452     MapConstValueIterator(const Map& _map, const ItemIt& _it)

   453       : Parent(_it), map(&_map) {}

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

   457     MapConstValueIterator& operator++() {

   458       Parent::increment();

   459       return *this;

   460     }

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

   463     MapConstValueIterator operator++(int) {

   464       MapConstValueIterator tmp(*this);

   465       Parent::increment();

   466       return tmp;

   467     }

   469     /// The dereferencing operator of the iterator.

   470     Reference operator*() const {

   471       return (*map)[Parent::it];

   472     }

   474     /// The arrow operator of the iterator.

   475     Pointer operator->() const {

   476       return &(operator*());

   477     }

   479   protected:

   481     const Map* map;

   483   public:

   484     // STL  compatibility typedefs.

   485     typedef std::forward_iterator_tag iterator_category;

   486     typedef int difference_type;

   487     typedef Value value_type;

   488     typedef Reference reference;

   489     typedef Pointer pointer;

   490   };

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

   494    *  which contains all the keys of the map.

   495    */

   496   template <typename _Graph, typename _Item>

   497   class MapConstKeySet {

   499   public:

   501     typedef _Graph Graph;

   502     /// The key type of the iterator.

   503     typedef _Item Item;

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

   506   protected:

   508     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;

   510   public:

   512     /// The map initialized const key set.

   513     MapConstKeySet(const Graph& _graph) : graph(&_graph) {}

   515     /// The const iterator of the set.

   516     typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;

   518     typedef typename ConstIterator::Value Value;

   519     /// The reference type of the iterator.

   520     typedef typename ConstIterator::Reference ConstReference;

   521     /// The pointer type of the iterator.

   522     typedef typename ConstIterator::Pointer ConstPointer;

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

   525     ConstIterator begin() const {

   526       return ConstIterator(ItemIt(*graph));

   527     }

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

   530     ConstIterator end() const {

   531       return ConstIterator(ItemIt(INVALID));

   532     }

   534   protected:

   536     const Graph* graph;

   538   public:

   539     // STL  compatibility typedefs.

   540     typedef Value value_type;

   541     typedef ConstIterator const_iterator;

   542     typedef ConstReference const_reference;

   543     typedef ConstPointer const_pointer;

   544     typedef int difference_type;

   545   };

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

   548    *  which contains all the values of the map.

   549    *  The values cannot be modified.

   550    */

   551   template <typename _Graph, typename _Item, typename _Map>

   552   class MapConstValueSet {

   554   public:

   556     typedef _Graph Graph;

   557     typedef _Item Item;

   558     typedef _Map Map;

   560   protected:

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

   563     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;

   565   public:

   567     /// The map initialized const value set.

   568     MapConstValueSet(const Graph& _graph, const Map& _map)

   569       : graph(&_graph), map(&_map) {}

   571     /// The const iterator of the set.

   572     typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;

   574     typedef typename ConstIterator::Value Value;

   575     typedef typename ConstIterator::Reference ConstReference;

   576     typedef typename ConstIterator::Pointer ConstPointer;

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

   579     ConstIterator begin() const {

   580       return ConstIterator(*map, ItemIt(*graph));

   581     }

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

   584     ConstIterator end() const {

   585       return ConstIterator(*map, ItemIt(INVALID));

   586     }

   588   protected:

   590     const Map* map;

   591     const Graph * graph;

   593   public:

   594     // STL  compatibility typedefs.

   595     typedef Value value_type;

   596     typedef ConstIterator const_iterator;

   597     typedef ConstReference const_reference;

   598     typedef ConstPointer const_pointer;

   599     typedef int difference_type;

   600   };

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

   604    *  which contains all the values of the map.

   605    *  The values can be modified.

   606    */

   607   template <typename _Graph, typename _Item, typename _Map>

   608   class MapValueSet {

   610   public:

   612     typedef _Graph Graph;

   613     typedef _Item Item;

   614     typedef _Map Map;

   616   protected:

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

   619     typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;

   621   public:

   623     /// The map initialized const value set.

   624     MapValueSet(const Graph& _graph, Map& _map)

   625       : map(&_map), graph(&_graph) {}

   627     /// The const iterator of the set.

   628     typedef MapValueIterator<_Graph, _Item, _Map> Iterator;

   629     /// The const iterator of the set.

   630     typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;

   632     typedef typename ConstIterator::Value Value;

   633     typedef typename Iterator::Reference Reference;

   634     typedef typename Iterator::Pointer Pointer;

   635     typedef typename ConstIterator::Reference ConstReference;

   636     typedef typename ConstIterator::Pointer ConstPointer;

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

   639     ConstIterator begin() const {

   640       return ConstIterator(*map, ItemIt(*graph));

   641     }

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

   644     ConstIterator end() const {

   645       return ConstIterator(*map, ItemIt(INVALID));

   646     }

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

   649     Iterator begin() {

   650       return Iterator(*map, ItemIt(*graph));

   651     }

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

   654     Iterator end() {

   655       return Iterator(*map, ItemIt(INVALID));

   656     }

   658   protected:

   660     Map* map;

   661     const Graph * graph;

   663   public:

   664     // STL  compatibility typedefs.

   665     typedef Value value_type;

   666     typedef Iterator iterator;

   667     typedef ConstIterator const_iterator;

   668     typedef Reference reference;

   669     typedef ConstReference const_reference;

   670     typedef Pointer pointer;

   671     typedef ConstPointer const_pointer;

   672     typedef int difference_type;

   674   };

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

   677    *  which contains all the values of the map.

   678    *  The values can be modified.

   679    */

   680   template <

   681     typename _Graph,

   682     typename _Item,

   683     typename _Map

   684     >

   685   class MapSet {

   686   public:

   688     typedef _Graph Graph;

   689     typedef _Item Item;

   690     typedef _Map Map;

   692   protected:

   694     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;

   696   public:

   698     /// The map initialized value set.

   699     MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}

   701     /// The const iterator of the set.

   702     typedef MapIterator<_Graph, _Item, _Map> Iterator;

   703     typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;

   705     typedef typename ConstIterator::Value Value;

   706     typedef typename Iterator::Reference Reference;

   707     typedef typename Iterator::Pointer Pointer;

   708     typedef typename ConstIterator::Reference ConstReference;

   709     typedef typename ConstIterator::Pointer ConstPointer;

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

   713     ConstIterator begin() const {

   714       return ConstIterator(*map, ItemIt(*graph));

   715     }

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

   718     ConstIterator end() const {

   719       return ConstIterator(*map, ItemIt(INVALID));

   720     }

   722     /// The iterator of the set.

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

   725     Iterator begin() {

   726       return Iterator(*map, ItemIt(*graph));

   727     }

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

   730     Iterator end() {

   731       return Iterator(*map, ItemIt(INVALID));

   732     }

   734   protected:

   736     const Graph* graph;

   737     Map* map;

   739   public:

   740     // STL  compatibility typedefs.

   741     typedef Value value_type;

   742     typedef Iterator iterator;

   743     typedef ConstIterator const_iterator;

   744     typedef Reference reference;

   745     typedef ConstReference const_reference;

   746     typedef Pointer pointer;

   747     typedef ConstPointer const_pointer;

   748     typedef int difference_type;

   750   };

   752   template <

   753     typename _Graph,

   754     typename _Item,

   755     typename _Map

   756     >

   757   class ConstMapSet {

   759     typedef _Graph Graph;

   760     typedef _Map Map;

   762     const Graph* graph;

   763     const Map* map;

   765   public:

   767     typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;

   770     /// The map initialized value set.

   771     ConstMapSet(const Graph& _graph, const Map& _map)

   772       : graph(&_graph), map(&_map) {}

   774     /// The const iterator of the set.

   775     typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;

   777     typedef typename ConstIterator::Value Value;

   778     typedef typename ConstIterator::Reference ConstReference;

   779     typedef typename ConstIterator::Pointer ConstPointer;

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

   783     ConstIterator begin() const {

   784       return ConstIterator(*map, ItemIt(*graph));

   785     }

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

   788     ConstIterator end() const {

   789       return ConstIterator(*map, ItemIt(INVALID));

   790     }

   792   public:

   793     // STL  compatibility typedefs.

   794     typedef Value value_type;

   795     typedef ConstIterator const_iterator;

   796     typedef ConstReference const_reference;

   797     typedef ConstPointer const_pointer;

   798     typedef int difference_type;

   800   };

   802   template <typename _Map>

   803   class IterableMapExtender : public _Map {

   804   public:

   806     typedef _Map Parent;

   807     typedef Parent Map;

   808     typedef typename Map::Graph Graph;

   809     typedef typename Map::Key Item;

   810     typedef typename Map::Value Value;

   812     typedef MapSet<Graph, Item, Map> MapSet;

   814     IterableMapExtender() : Parent() {}

   816     IterableMapExtender(const Graph& graph) : Parent(graph) {}

   818     IterableMapExtender(const Graph& graph, const Value& value)

   819       : Parent(graph, value) {}

   821     MapSet mapSet() {

   822       return MapSet(*Parent::getGraph(), *this);

   823     }

   825     typedef ConstMapSet<Graph, Item, Map> ConstMapSet;

   827     ConstMapSet mapSet() const {

   828       return ConstMapSet(*Parent::getGraph(), *this);

   829     }

   831     typedef MapConstKeySet<Graph, Item> ConstKeySet;

   833     ConstKeySet keySet() const {

   834       return ConstKeySet(*Parent::getGraph());

   835     }

   837     typedef MapValueSet<Graph, Item, Map> ValueSet;

   839     ValueSet valueSet() {

   840       return ValueSet(*Parent::getGraph(), *this);

   841     }

   843     typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;

   845     ConstValueSet valueSet() const {

   846       return ConstValueSet(*Parent::getGraph(), *this);

   847     }

   849   };

   851   /// @}

   853 }

   855 #endif

author	athos
	Thu, 09 Jun 2005 15:12:01 +0000
changeset 1461	9f99ede44d59
parent 1402	655d8e78454d
child 1587	8f1c317ebeb4
permissions	-rw-r--r--