lemon-0.x: lemon/bits/map_iterator.h@874e4bc21435

     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 graphmapfactory

    26 ///\file

    27 ///\brief Iterators on the maps.

    29 namespace lemon {

    31   /// \addtogroup graphmapfactory

    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 _Map::Value MapValue;

   108     typedef typename _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 _Map::Value MapValue;

   198     typedef typename _Map::ConstReference MapReference;

   200   public:

   202     /// The value type of the iterator.

   203     typedef extended_pair<Item, const Item&,

   204       MapValue, const MapValue&> Value;

   206     /// The reference type of the iterator.

   207     typedef extended_pair<const Item&, const Item&,

   208       MapReference, MapReference> Reference;

   210     /// Default constructor.

   211     MapConstIterator() {}

   213     /// Constructor to initalize the iterators returned

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

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

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

   218     /// Dereference operator for the iterator.

   219     Reference operator*() {

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

   221     }

   223     /// The pointer type of the iterator.

   224     class Pointer {

   225       friend class MapConstIterator;

   226     protected:

   227       Reference data;

   228       Pointer(const Item& item, MapReference val)

   229 	: data(item, val) {}

   230     public:

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

   232     };

   234     /// Arrow operator for the iterator.

   235     Pointer operator->() {

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

   237     }

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

   240     MapConstIterator& operator++() {

   241       Parent::increment();

   242       return *this;

   243     }

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

   246     MapConstIterator operator++(int) {

   247       MapConstIterator tmp(*this);

   248       Parent::increment();

   249       return tmp;

   250     }

   252   protected:

   253     const Map* map;

   255   public:

   256     // STL  compatibility typedefs.

   257     typedef std::forward_iterator_tag iterator_category;

   258     typedef int difference_type;

   259     typedef Value value_type;

   260     typedef Reference reference;

   261     typedef Pointer pointer;

   262   };

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

   265    *  with dereferencing operator.

   266    */

   267   template <

   268     typename _Graph,

   269     typename _Item>

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

   272   public:

   274     /// The iterator base class.

   275     typedef MapIteratorBase<_Graph, _Item> Parent;

   277     typedef _Graph Graph;

   278     typedef _Item Item;

   280   protected:

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

   282     typedef typename Parent::ItemIt ItemIt;

   284   public:

   286     typedef Item Value;

   287     typedef const Item& Reference;

   288     typedef const Item* Pointer;

   290     /// Default constructor.

   291     MapConstKeyIterator() {}

   293     /// ItemIt initialized iterator.

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

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

   297     MapConstKeyIterator& operator++() {

   298       Parent::increment();

   299       return *this;

   300     }

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

   303     MapConstKeyIterator operator++(int) {

   304       MapConstKeyIterator tmp(*this);

   305       Parent::increment();

   306       return tmp;

   307     }

   309     /// The dereferencing operator of the iterator.

   310     Item operator*() const {

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

   312     }

   314   public:

   315     // STL  compatibility typedefs.

   316     typedef std::input_iterator_tag iterator_category;

   317     typedef int difference_type;

   318     typedef Value value_type;

   319     typedef Reference reference;

   320     typedef Pointer pointer;

   321   };

   323   template <

   324     typename _Graph,

   325     typename _Item,

   326     typename _Map>

   327   class MapConstValueIterator;

   329   /** MapValueIterator creates an stl compatible iterator

   330    *  for the values.

   331    */

   332   template <

   333     typename _Graph,

   334     typename _Item,

   335     typename _Map>

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

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

   340   public:

   342     /// The iterator base class.

   343     typedef MapIteratorBase<_Graph, _Item> Parent;

   345     typedef _Graph Graph;

   346     typedef _Item Item;

   347     typedef _Map Map;

   349   protected:

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

   352     typedef typename Parent::ItemIt ItemIt;

   354     /// The value type of the iterator.

   355     typedef typename Map::Value MapValue;

   356     /// The reference type of the iterator.

   357     typedef typename Map::Reference MapReference;

   358     /// The pointer type of the iterator.

   359     typedef typename Map::Pointer MapPointer;

   361   public:

   363     typedef MapValue Value;

   364     typedef MapReference Reference;

   365     typedef MapPointer Pointer;

   367     /// Default constructor.

   368     MapValueIterator() {}

   370     /// Map and ItemIt initialized iterator.

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

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

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

   376     MapValueIterator& operator++() {

   377       Parent::increment();

   378       return *this;

   379     }

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

   382     MapValueIterator operator++(int) {

   383       MapValueIterator tmp(*this);

   384       Parent::increment();

   385       return tmp;

   386     }

   388     /// The dereferencing operator of the iterator.

   389     Reference operator*() const {

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

   391     }

   393     /// The arrow operator of the iterator.

   394     Pointer operator->() const {

   395       return &(operator*());

   396     }

   398   protected:

   400     Map* map;

   402   public:

   403     // STL  compatibility typedefs.

   404     typedef std::forward_iterator_tag iterator_category;

   405     typedef int difference_type;

   406     typedef Value value_type;

   407     typedef Reference reference;

   408     typedef Pointer pointer;

   409   };

   411   /** MapValueIterator creates an stl compatible iterator

   412    *  for the values.

   413    */

   414   template <

   415     typename _Graph,

   416     typename _Item,

   417     typename _Map>

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

   420   public:

   422     /// The iterator base class.

   423     typedef MapIteratorBase<_Graph, _Item> Parent;

   425     typedef _Graph Graph;

   426     typedef _Item Item;

   427     typedef _Map Map;

   429   protected:

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

   432     typedef typename Parent::ItemIt ItemIt;

   434     /// The value type of the iterator.

   435     typedef typename Map::Value MapValue;

   436     /// The reference type of the iterator.

   437     typedef typename Map::ConstReference MapReference;

   438     /// The pointer type of the iterator.

   439     typedef typename Map::ConstPointer MapPointer;

   441   public:

   443     typedef MapValue Value;

   444     typedef MapReference Reference;

   445     typedef MapPointer Pointer;

   447     /// Default constructor.

   448     MapConstValueIterator() {}

   450     /// Map and ItemIt initialized iterator.

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

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

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

   456     MapConstValueIterator& operator++() {

   457       Parent::increment();

   458       return *this;

   459     }

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

   462     MapConstValueIterator operator++(int) {

   463       MapConstValueIterator tmp(*this);

   464       Parent::increment();

   465       return tmp;

   466     }

   468     /// The dereferencing operator of the iterator.

   469     Reference operator*() const {

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

   471     }

   473     /// The arrow operator of the iterator.

   474     Pointer operator->() const {

   475       return &(operator*());

   476     }

   478   protected:

   480     const Map* map;

   482   public:

   483     // STL  compatibility typedefs.

   484     typedef std::forward_iterator_tag iterator_category;

   485     typedef int difference_type;

   486     typedef Value value_type;

   487     typedef Reference reference;

   488     typedef Pointer pointer;

   489   };

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

   493    *  which contains all the keys of the map.

   494    */

   495   template <typename _Graph, typename _Item>

   496   class MapConstKeySet {

   498   public:

   500     typedef _Graph Graph;

   501     /// The key type of the iterator.

   502     typedef _Item Item;

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

   505   protected:

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

   509   public:

   511     /// The map initialized const key set.

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

   514     /// The const iterator of the set.

   515     typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;

   517     typedef typename ConstIterator::Value Value;

   518     /// The reference type of the iterator.

   519     typedef typename ConstIterator::Reference ConstReference;

   520     /// The pointer type of the iterator.

   521     typedef typename ConstIterator::Pointer ConstPointer;

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

   524     ConstIterator begin() const {

   525       return ConstIterator(ItemIt(*graph));

   526     }

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

   529     ConstIterator end() const {

   530       return ConstIterator(ItemIt(INVALID));

   531     }

   533   protected:

   535     const Graph* graph;

   537   public:

   538     // STL  compatibility typedefs.

   539     typedef Value value_type;

   540     typedef ConstIterator const_iterator;

   541     typedef ConstReference const_reference;

   542     typedef ConstPointer const_pointer;

   543     typedef int difference_type;

   544   };

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

   547    *  which contains all the values of the map.

   548    *  The values cannot be modified.

   549    */

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

   551   class MapConstValueSet {

   553   public:

   555     typedef _Graph Graph;

   556     typedef _Item Item;

   557     typedef _Map Map;

   559   protected:

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

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

   564   public:

   566     /// The map initialized const value set.

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

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

   570     /// The const iterator of the set.

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

   573     typedef typename ConstIterator::Value Value;

   574     typedef typename ConstIterator::Reference ConstReference;

   575     typedef typename ConstIterator::Pointer ConstPointer;

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

   578     ConstIterator begin() const {

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

   580     }

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

   583     ConstIterator end() const {

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

   585     }

   587   protected:

   589     const Map* map;

   590     const Graph * graph;

   592   public:

   593     // STL  compatibility typedefs.

   594     typedef Value value_type;

   595     typedef ConstIterator const_iterator;

   596     typedef ConstReference const_reference;

   597     typedef ConstPointer const_pointer;

   598     typedef int difference_type;

   599   };

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

   603    *  which contains all the values of the map.

   604    *  The values can be modified.

   605    */

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

   607   class MapValueSet {

   609   public:

   611     typedef _Graph Graph;

   612     typedef _Item Item;

   613     typedef _Map Map;

   615   protected:

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

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

   620   public:

   622     /// The map initialized const value set.

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

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

   626     /// The const iterator of the set.

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

   628     /// The const iterator of the set.

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

   631     typedef typename ConstIterator::Value Value;

   632     typedef typename Iterator::Reference Reference;

   633     typedef typename Iterator::Pointer Pointer;

   634     typedef typename ConstIterator::Reference ConstReference;

   635     typedef typename ConstIterator::Pointer ConstPointer;

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

   638     ConstIterator begin() const {

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

   640     }

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

   643     ConstIterator end() const {

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

   645     }

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

   648     Iterator begin() {

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

   650     }

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

   653     Iterator end() {

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

   655     }

   657   protected:

   659     Map* map;

   660     const Graph * graph;

   662   public:

   663     // STL  compatibility typedefs.

   664     typedef Value value_type;

   665     typedef Iterator iterator;

   666     typedef ConstIterator const_iterator;

   667     typedef Reference reference;

   668     typedef ConstReference const_reference;

   669     typedef Pointer pointer;

   670     typedef ConstPointer const_pointer;

   671     typedef int difference_type;

   673   };

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

   676    *  which contains all the values of the map.

   677    *  The values can be modified.

   678    */

   679   template <

   680     typename _Graph,

   681     typename _Item,

   682     typename _Map

   683     >

   684   class MapSet {

   685   public:

   687     typedef _Graph Graph;

   688     typedef _Item Item;

   689     typedef _Map Map;

   691   protected:

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

   695   public:

   697     /// The map initialized value set.

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

   700     /// The const iterator of the set.

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

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

   704     typedef typename ConstIterator::Value Value;

   705     typedef typename Iterator::Reference Reference;

   706     typedef typename Iterator::Pointer Pointer;

   707     typedef typename ConstIterator::Reference ConstReference;

   708     typedef typename ConstIterator::Pointer ConstPointer;

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

   712     ConstIterator begin() const {

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

   714     }

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

   717     ConstIterator end() const {

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

   719     }

   721     /// The iterator of the set.

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

   724     Iterator begin() {

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

   726     }

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

   729     Iterator end() {

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

   731     }

   733   protected:

   735     const Graph* graph;

   736     Map* map;

   738   public:

   739     // STL  compatibility typedefs.

   740     typedef Value value_type;

   741     typedef Iterator iterator;

   742     typedef ConstIterator const_iterator;

   743     typedef Reference reference;

   744     typedef ConstReference const_reference;

   745     typedef Pointer pointer;

   746     typedef ConstPointer const_pointer;

   747     typedef int difference_type;

   749   };

   751   template <

   752     typename _Graph,

   753     typename _Item,

   754     typename _Map

   755     >

   756   class ConstMapSet {

   758     typedef _Graph Graph;

   759     typedef _Map Map;

   761     const Graph* graph;

   762     const Map* map;

   764   public:

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

   769     /// The map initialized value set.

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

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

   773     /// The const iterator of the set.

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

   776     typedef typename ConstIterator::Value Value;

   777     typedef typename ConstIterator::Reference ConstReference;

   778     typedef typename ConstIterator::Pointer ConstPointer;

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

   782     ConstIterator begin() const {

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

   784     }

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

   787     ConstIterator end() const {

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

   789     }

   791   public:

   792     // STL  compatibility typedefs.

   793     typedef Value value_type;

   794     typedef ConstIterator const_iterator;

   795     typedef ConstReference const_reference;

   796     typedef ConstPointer const_pointer;

   797     typedef int difference_type;

   799   };

   801   template <typename _Map>

   802   class IterableMapExtender : public _Map {

   803   public:

   805     typedef _Map Parent;

   806     typedef Parent Map;

   807     typedef typename Map::Graph Graph;

   808     typedef typename Map::Key Item;

   809     typedef typename Map::Value Value;

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

   813     IterableMapExtender() : Parent() {}

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

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

   818       : Parent(graph, value) {}

   820     MapSet mapSet() {

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

   822     }

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

   826     ConstMapSet mapSet() const {

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

   828     }

   830     typedef MapConstKeySet<Graph, Item> ConstKeySet;

   832     ConstKeySet keySet() const {

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

   834     }

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

   838     ValueSet valueSet() {

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

   840     }

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

   844     ConstValueSet valueSet() const {

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

   846     }

   848   };

   850   /// @}

   852 }

   854 #endif

author	deba
	Fri, 28 Oct 2005 08:40:42 +0000
changeset 1746	874e4bc21435
parent 1587	8f1c317ebeb4
permissions	-rw-r--r--