lemon/iterable_maps.h
author alpar
Mon, 30 Oct 2006 16:19:18 +0000
changeset 2274 432d0469a87e
parent 2112 f27dfd29c5c0
child 2386 81b47fc5c444
permissions -rw-r--r--
Turn off 32 bit only tests, cont'd.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_ITERABLE_MAPS_H
    20 #define LEMON_ITERABLE_MAPS_H
    21 
    22 #include <lemon/bits/traits.h>
    23 #include <lemon/bits/invalid.h>
    24 
    25 #include <lemon/bits/default_map.h>
    26 #include <lemon/bits/map_extender.h>
    27 
    28 #include <vector>
    29 #include <map>
    30 
    31 #include <iterator>
    32 #include <limits>
    33 
    34 ///\ingroup maps
    35 ///\file
    36 ///\brief Maps that makes it possible to iterate through the keys having
    37 ///a certain value
    38 ///
    39 ///
    40 
    41 
    42 namespace lemon {
    43 
    44   ///\ingroup graph_maps
    45   ///
    46   /// \brief Dynamic iterable bool map.
    47   ///
    48   /// This class provides a special graph map type which can store
    49   /// for each graph item(node, edge, etc.) a bool value. For both 
    50   /// the true and the false it is possible to iterate on the keys which
    51   /// mapped to the given value.
    52   /// 
    53   /// \param _Graph The graph type.
    54   /// \param _Item One of the graph's item type, the key of the map.
    55   template <typename _Graph, typename _Item>
    56   class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> {
    57   private:
    58     typedef _Graph Graph;
    59     
    60     typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
    61     typedef DefaultMap<_Graph, _Item, int> Parent;
    62     
    63     std::vector<_Item> array;
    64     int sep;
    65 
    66     const Graph& graph;
    67 
    68   public:
    69 
    70     /// Indicates that the map if reference map.
    71     typedef True ReferenceMapTag;
    72 
    73     /// The key type
    74     typedef _Item Key;
    75     /// The value type
    76     typedef bool Value;
    77     /// The const reference type.    
    78     typedef const Value& ConstReference;
    79 
    80   private:
    81 
    82     int position(const Key& key) const {
    83       return Parent::operator[](key);
    84     }
    85 
    86   public:
    87 
    88     /// \brief Refernce to the value of the map.
    89     ///
    90     /// This class is near to similar to the bool type. It can
    91     /// be converted to bool and it has the same operators.
    92     class Reference {
    93       friend class IterableBoolMap;
    94     private:
    95       Reference(IterableBoolMap& map, const Key& key) 
    96 	: _key(key), _map(map) {} 
    97     public:
    98 
    99       Reference& operator=(const Reference& value) {
   100 	_map.set(_key, (bool)value);
   101  	return *this;
   102       }
   103 
   104       operator bool() const { 
   105 	return static_cast<const IterableBoolMap&>(_map)[_key]; 
   106       }
   107 
   108       Reference& operator=(bool value) { 
   109 	_map.set(_key, value); 
   110 	return *this; 
   111       }
   112       Reference& operator&=(bool value) {
   113 	_map.set(_key, _map[_key] & value); 
   114 	return *this; 	
   115       }
   116       Reference& operator|=(bool value) {
   117 	_map.set(_key, _map[_key] | value); 
   118 	return *this; 	
   119       }
   120       Reference& operator^=(bool value) {
   121 	_map.set(_key, _map[_key] ^ value); 
   122 	return *this; 	
   123       }
   124     private:
   125       Key _key;
   126       IterableBoolMap& _map; 
   127     };
   128     
   129     /// \brief Constructor of the Map with a default value.
   130     ///
   131     /// Constructor of the Map with a default value.
   132     explicit IterableBoolMap(const Graph& _graph, bool def = false) 
   133       : Parent(_graph), graph(_graph) {
   134       for (KeyIt it(graph); it != INVALID; ++it) {
   135         Parent::set(it, array.size());
   136         array.push_back(it);
   137       }
   138       sep = (def ? array.size() : 0);
   139     }
   140 
   141     /// \brief Const subscript operator of the map.
   142     ///
   143     /// Const subscript operator of the map.
   144     bool operator[](const Key& key) const {
   145       return position(key) < sep;
   146     }
   147 
   148     /// \brief Subscript operator of the map.
   149     ///
   150     /// Subscript operator of the map.
   151     Reference operator[](const Key& key) {
   152       return Reference(*this, key);
   153     }
   154 
   155     /// \brief Set operation of the map.
   156     ///
   157     /// Set operation of the map.
   158     void set(const Key& key, bool value) {
   159       int pos = position(key);
   160       if (value) {
   161         if (pos < sep) return;
   162         Key tmp = array[sep];
   163         array[sep] = key;
   164         Parent::set(key, sep);
   165         array[pos] = tmp;
   166         Parent::set(tmp, pos); 
   167         ++sep;
   168       } else {
   169         if (pos >= sep) return;
   170         --sep;
   171         Key tmp = array[sep];
   172         array[sep] = key;
   173         Parent::set(key, sep);
   174         array[pos] = tmp;
   175         Parent::set(tmp, pos);
   176       }
   177     }
   178 
   179     /// \brief Returns the number of the keys mapped to true.
   180     ///
   181     /// Returns the number of the keys mapped to true.
   182     int trueNum() const {
   183       return sep;
   184     } 
   185     
   186     /// \brief Returns the number of the keys mapped to false.
   187     ///
   188     /// Returns the number of the keys mapped to false.
   189     int falseNum() const {
   190       return array.size() - sep;
   191     }
   192 
   193     /// \brief Iterator for the keys mapped to true.
   194     ///
   195     /// Iterator for the keys mapped to true. It works
   196     /// like a graph item iterator in the map, it can be converted
   197     /// the key type of the map, incremented with \c ++ operator, and
   198     /// if the iterator leave the last valid key it will be equal to 
   199     /// \c INVALID.
   200     class TrueIt : public Key {
   201     public:
   202       typedef Key Parent;
   203       
   204       /// \brief Creates an iterator.
   205       ///
   206       /// Creates an iterator. It iterates on the 
   207       /// keys which mapped to true.
   208       /// \param _map The IterableIntMap
   209       explicit TrueIt(const IterableBoolMap& _map) 
   210         : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID), 
   211           map(&_map) {}
   212 
   213       /// \brief Invalid constructor \& conversion.
   214       ///
   215       /// This constructor initializes the key to be invalid.
   216       /// \sa Invalid for more details.
   217       TrueIt(Invalid) : Parent(INVALID), map(0) {}
   218 
   219       /// \brief Increment operator.
   220       ///
   221       /// Increment Operator.
   222       TrueIt& operator++() {
   223         int pos = map->position(*this);
   224         Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
   225         return *this;
   226       }
   227 
   228       
   229     private:
   230       const IterableBoolMap* map;
   231     };
   232 
   233     /// \brief Iterator for the keys mapped to false.
   234     ///
   235     /// Iterator for the keys mapped to false. It works
   236     /// like a graph item iterator in the map, it can be converted
   237     /// the key type of the map, incremented with \c ++ operator, and
   238     /// if the iterator leave the last valid key it will be equal to 
   239     /// \c INVALID.
   240     class FalseIt : public Key {
   241     public:
   242       typedef Key Parent;
   243       
   244       /// \brief Creates an iterator.
   245       ///
   246       /// Creates an iterator. It iterates on the 
   247       /// keys which mapped to false.
   248       /// \param _map The IterableIntMap
   249       explicit FalseIt(const IterableBoolMap& _map) 
   250         : Parent(_map.sep < (int)_map.array.size() ? 
   251                  _map.array.back() : INVALID), map(&_map) {}
   252 
   253       /// \brief Invalid constructor \& conversion.
   254       ///
   255       /// This constructor initializes the key to be invalid.
   256       /// \sa Invalid for more details.
   257       FalseIt(Invalid) : Parent(INVALID), map(0) {}
   258 
   259       /// \brief Increment operator.
   260       ///
   261       /// Increment Operator.
   262       FalseIt& operator++() {
   263         int pos = map->position(*this);
   264         Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
   265         return *this;
   266       }
   267 
   268     private:
   269       const IterableBoolMap* map;
   270     };
   271 
   272     /// \brief Iterator for the keys mapped to a given value.
   273     ///
   274     /// Iterator for the keys mapped to a given value. It works
   275     /// like a graph item iterator in the map, it can be converted
   276     /// the key type of the map, incremented with \c ++ operator, and
   277     /// if the iterator leave the last valid key it will be equal to 
   278     /// \c INVALID.
   279     class ItemIt : public Key {
   280     public:
   281       typedef Key Parent;
   282       
   283       /// \brief Creates an iterator.
   284       ///
   285       /// Creates an iterator. It iterates on the 
   286       /// keys which mapped to false.
   287       /// \param _map The IterableIntMap
   288       /// \param value Which elements should be iterated.
   289       ItemIt(const IterableBoolMap& _map, bool value) 
   290         : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
   291                  (_map.sep < (int)_map.array.size() ? 
   292                   _map.array.back() : INVALID)), map(&_map) {}
   293 
   294       /// \brief Invalid constructor \& conversion.
   295       ///
   296       /// This constructor initializes the key to be invalid.
   297       /// \sa Invalid for more details.
   298       ItemIt(Invalid) : Parent(INVALID), map(0) {}
   299 
   300       /// \brief Increment operator.
   301       ///
   302       /// Increment Operator.
   303       ItemIt& operator++() {
   304         int pos = map->position(*this);
   305         int sep = pos >= map->sep ? map->sep : 0;
   306         Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
   307         return *this;
   308       }
   309 
   310     private:
   311       const IterableBoolMap* map;
   312     };
   313 
   314   protected:
   315     
   316     virtual void add(const Key& key) {
   317       Parent::add(key);
   318       Parent::set(key, array.size());
   319       array.push_back(key);
   320     }
   321 
   322     virtual void add(const std::vector<Key>& keys) {
   323       Parent::add(keys);
   324       for (int i = 0; i < (int)keys.size(); ++i) {
   325         Parent::set(keys[i], array.size());
   326         array.push_back(keys[i]);
   327       }
   328     }
   329 
   330     virtual void erase(const Key& key) {
   331       int pos = position(key); 
   332       if (pos < sep) {
   333         --sep;
   334         Parent::set(array[sep], pos);
   335         array[pos] = array[sep];
   336         Parent::set(array.back(), sep);
   337         array[sep] = array.back();
   338         array.pop_back();
   339       } else {
   340         Parent::set(array.back(), pos);
   341         array[pos] = array.back();
   342         array.pop_back();
   343       }
   344       Parent::erase(key);
   345     }
   346 
   347     virtual void erase(const std::vector<Key>& keys) {
   348       for (int i = 0; i < (int)keys.size(); ++i) {
   349         int pos = position(keys[i]); 
   350         if (pos < sep) {
   351           --sep;
   352           Parent::set(array[sep], pos);
   353           array[pos] = array[sep];
   354           Parent::set(array.back(), sep);
   355           array[sep] = array.back();
   356           array.pop_back();
   357         } else {
   358           Parent::set(array.back(), pos);
   359           array[pos] = array.back();
   360           array.pop_back();
   361         }
   362       }
   363       Parent::erase(keys);
   364     }    
   365 
   366     virtual void build() {
   367       Parent::build();
   368       for (KeyIt it(graph); it != INVALID; ++it) {
   369         Parent::set(it, array.size());
   370         array.push_back(it);
   371       }
   372       sep = 0;      
   373     }
   374 
   375     virtual void clear() {
   376       array.clear();
   377       sep = 0;
   378       Parent::clear();
   379     }
   380     
   381   };
   382   
   383 
   384   namespace _iterable_maps_bits {
   385     template <typename Item>
   386     struct IterableIntMapNode {
   387       IterableIntMapNode() : value(-1) {}
   388       IterableIntMapNode(int _value) : value(_value) {}
   389       Item prev, next;
   390       int value;
   391     };
   392   }
   393 
   394   ///\ingroup graph_maps
   395   ///
   396   /// \brief Dynamic iterable integer map.
   397   ///
   398   /// This class provides a special graph map type which can store
   399   /// for each graph item(node, edge, etc.) an integer value. For each
   400   /// non negative value it is possible to iterate on the keys which
   401   /// mapped to the given value.
   402   /// 
   403   /// \param _Graph The graph type.
   404   /// \param _Item One of the graph's item type, the key of the map.
   405   template <typename _Graph, typename _Item>
   406   class IterableIntMap 
   407     : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
   408                                        IterableIntMapNode<_Item> > >{
   409   public:
   410     typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
   411                                    IterableIntMapNode<_Item> > > Parent;
   412 
   413     /// The key type
   414     typedef _Item Key;
   415     /// The value type
   416     typedef int Value;
   417     /// The graph type
   418     typedef _Graph Graph;
   419 
   420     /// \brief Constructor of the Map.
   421     ///
   422     /// Constructor of the Map. It set all values -1.
   423     explicit IterableIntMap(const Graph& graph) 
   424       : Parent(graph) {}
   425 
   426     /// \brief Constructor of the Map with a given value.
   427     ///
   428     /// Constructor of the Map with a given value.
   429     explicit IterableIntMap(const Graph& graph, int value) 
   430       : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
   431       if (value >= 0) {
   432 	for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
   433 	  lace(it);
   434 	}
   435       }
   436     }
   437 
   438   private:
   439     
   440     void unlace(const Key& key) {
   441       typename Parent::Value& node = Parent::operator[](key);
   442       if (node.value < 0) return;
   443       if (node.prev != INVALID) {
   444 	Parent::operator[](node.prev).next = node.next;	
   445       } else {
   446 	first[node.value] = node.next;
   447       }
   448       if (node.next != INVALID) {
   449 	Parent::operator[](node.next).prev = node.prev;
   450       }
   451       while (!first.empty() && first.back() == INVALID) {
   452 	first.pop_back();
   453       }
   454     }
   455 
   456     void lace(const Key& key) {
   457       typename Parent::Value& node = Parent::operator[](key);
   458       if (node.value < 0) return;
   459       if (node.value >= (int)first.size()) {
   460 	first.resize(node.value + 1, INVALID);
   461       } 
   462       node.prev = INVALID;
   463       node.next = first[node.value];
   464       if (node.next != INVALID) {
   465 	Parent::operator[](node.next).prev = key;	
   466       }
   467       first[node.value] = key;
   468     }
   469 
   470   public:
   471 
   472     /// Indicates that the map if reference map.
   473     typedef True ReferenceMapTag;
   474 
   475     /// \brief Refernce to the value of the map.
   476     ///
   477     /// This class is near to similar to the int type. It can
   478     /// be converted to int and it has the same operators.
   479     class Reference {
   480       friend class IterableIntMap;
   481     private:
   482       Reference(IterableIntMap& map, const Key& key) 
   483 	: _key(key), _map(map) {} 
   484     public:
   485 
   486       Reference& operator=(const Reference& value) {
   487 	_map.set(_key, (const int&)value);
   488  	return *this;
   489       }
   490 
   491       operator const int&() const { 
   492 	return static_cast<const IterableIntMap&>(_map)[_key]; 
   493       }
   494 
   495       Reference& operator=(int value) { 
   496 	_map.set(_key, value); 
   497 	return *this; 
   498       }
   499       Reference& operator++() {
   500 	_map.set(_key, _map[_key] + 1); 
   501 	return *this; 	
   502       }
   503       int operator++(int) {
   504 	int value = _map[_key];
   505 	_map.set(_key, value + 1); 
   506 	return value; 	
   507       }
   508       Reference& operator--() {
   509 	_map.set(_key, _map[_key] - 1); 
   510 	return *this; 	
   511       }
   512       int operator--(int) {
   513 	int value = _map[_key];
   514 	_map.set(_key, value - 1); 
   515 	return value; 	
   516       }
   517       Reference& operator+=(int value) { 
   518 	_map.set(_key, _map[_key] + value); 
   519 	return *this;
   520       }
   521       Reference& operator-=(int value) { 
   522 	_map.set(_key, _map[_key] - value); 
   523 	return *this;
   524       }
   525       Reference& operator*=(int value) { 
   526 	_map.set(_key, _map[_key] * value); 
   527 	return *this;
   528       }
   529       Reference& operator/=(int value) { 
   530 	_map.set(_key, _map[_key] / value); 
   531 	return *this;
   532       }
   533       Reference& operator%=(int value) { 
   534 	_map.set(_key, _map[_key] % value); 
   535 	return *this;
   536       }
   537       Reference& operator&=(int value) { 
   538 	_map.set(_key, _map[_key] & value); 
   539 	return *this;
   540       }
   541       Reference& operator|=(int value) { 
   542 	_map.set(_key, _map[_key] | value); 
   543 	return *this;
   544       }
   545       Reference& operator^=(int value) { 
   546 	_map.set(_key, _map[_key] ^ value); 
   547 	return *this;
   548       }
   549       Reference& operator<<=(int value) { 
   550 	_map.set(_key, _map[_key] << value); 
   551 	return *this;
   552       }
   553       Reference& operator>>=(int value) { 
   554 	_map.set(_key, _map[_key] >> value); 
   555 	return *this;
   556       }
   557 
   558     private:
   559       Key _key;
   560       IterableIntMap& _map; 
   561     };
   562 
   563     /// The const reference type.    
   564     typedef const Value& ConstReference;
   565 
   566     /// \brief Gives back the maximal value plus one.
   567     ///
   568     /// Gives back the maximal value plus one.
   569     unsigned int size() const {
   570       return first.size();
   571     }
   572     
   573     /// \brief Set operation of the map.
   574     ///
   575     /// Set operation of the map.
   576     void set(const Key& key, const Value& value) {
   577       unlace(key);
   578       Parent::operator[](key).value = value;
   579       lace(key);
   580     }
   581 
   582     /// \brief Const subscript operator of the map.
   583     ///
   584     /// Const subscript operator of the map.
   585     const Value& operator[](const Key& key) const {
   586       return Parent::operator[](key).value;
   587     }
   588 
   589     /// \brief Subscript operator of the map.
   590     ///
   591     /// Subscript operator of the map.
   592     Reference operator[](const Key& key) {
   593       return Reference(*this, key);
   594     }
   595 
   596     /// \brief Iterator for the keys with the same value.
   597     ///
   598     /// Iterator for the keys with the same value. It works
   599     /// like a graph item iterator in the map, it can be converted
   600     /// the item type of the map, incremented with \c ++ operator, and
   601     /// if the iterator leave the last valid item it will be equal to 
   602     /// \c INVALID.
   603     class ItemIt : public _Item {
   604     public:
   605       typedef _Item Parent;
   606 
   607       /// \brief Invalid constructor \& conversion.
   608       ///
   609       /// This constructor initializes the item to be invalid.
   610       /// \sa Invalid for more details.
   611       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
   612 
   613       /// \brief Creates an iterator with a value.
   614       ///
   615       /// Creates an iterator with a value. It iterates on the 
   616       /// keys which have the given value.
   617       /// \param map The IterableIntMap
   618       /// \param value The value
   619       ItemIt(const IterableIntMap& map, int value) : _map(&map) {
   620 	if (value < 0 || value >= (int)_map->first.size()) {	  
   621 	  Parent::operator=(INVALID);
   622 	} else {
   623 	  Parent::operator=(_map->first[value]);
   624 	}
   625       } 
   626 
   627       /// \brief Increment operator.
   628       ///
   629       /// Increment Operator.
   630       ItemIt& operator++() {
   631 	Parent::operator=(_map->IterableIntMap::Parent::
   632 			  operator[](static_cast<Parent&>(*this)).next);
   633 	return *this;
   634       }
   635 
   636 
   637     private:
   638       const IterableIntMap* _map;
   639     };
   640 
   641   protected:
   642     
   643     virtual void erase(const Key& key) {
   644       unlace(key);
   645       Parent::erase(key);
   646     }
   647 
   648     virtual void erase(const std::vector<Key>& keys) {
   649       for (int i = 0; i < (int)keys.size(); ++i) {
   650         unlace(keys[i]);
   651       }
   652       Parent::erase(keys);
   653     }
   654 
   655     virtual void clear() {
   656       first.clear();
   657       Parent::clear();
   658     }
   659 
   660   private:
   661     std::vector<_Item> first;
   662   };
   663 
   664   namespace _iterable_maps_bits {
   665     template <typename Item, typename Value>
   666     struct IterableValueMapNode {
   667       IterableValueMapNode(Value _value = Value()) : value(_value) {}
   668       Item prev, next;
   669       Value value;
   670     };
   671   }
   672 
   673   ///\ingroup graph_maps
   674   ///
   675   /// \brief Dynamic iterable map for comparable values.
   676   ///
   677   /// This class provides a special graph map type which can store
   678   /// for each graph item(node, edge, etc.) a value. For each
   679   /// value it is possible to iterate on the keys which mapped to the 
   680   /// given value. The type stores for each value a linked list with
   681   /// the items which mapped to the value, and the values are stored
   682   /// in balanced binary tree. The values of the map can be accessed
   683   /// with stl compatible forward iterator.
   684   ///
   685   /// This type is not reference map so it cannot be modified with
   686   /// the subscription operator.
   687   ///
   688   /// \see InvertableMap
   689   /// 
   690   /// \param _Graph The graph type.
   691   /// \param _Item One of the graph's item type, the key of the map.
   692   /// \param _Value Any comparable value type.
   693   template <typename _Graph, typename _Item, typename _Value>
   694   class IterableValueMap 
   695     : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
   696                                        IterableValueMapNode<_Item, _Value> > >{
   697   public:
   698     typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
   699                                    IterableValueMapNode<_Item, _Value> > >
   700     Parent;
   701 
   702     /// The key type
   703     typedef _Item Key;
   704     /// The value type
   705     typedef _Value Value;
   706     /// The graph type
   707     typedef _Graph Graph;
   708 
   709   public:
   710 
   711     /// \brief Constructor of the Map with a given value.
   712     ///
   713     /// Constructor of the Map with a given value.
   714     explicit IterableValueMap(const Graph& graph, 
   715                               const Value& value = Value()) 
   716       : Parent(graph, _iterable_maps_bits::
   717                IterableValueMapNode<_Item, _Value>(value)) {
   718       for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
   719         lace(it);
   720       }
   721     }
   722 
   723   protected:
   724     
   725     void unlace(const Key& key) {
   726       typename Parent::Value& node = Parent::operator[](key);
   727       if (node.prev != INVALID) {
   728 	Parent::operator[](node.prev).next = node.next;	
   729       } else {
   730         if (node.next != INVALID) {
   731           first[node.value] = node.next;
   732         } else {
   733           first.erase(node.value);
   734         }
   735       }
   736       if (node.next != INVALID) {
   737 	Parent::operator[](node.next).prev = node.prev;
   738       }
   739     }
   740 
   741     void lace(const Key& key) {
   742       typename Parent::Value& node = Parent::operator[](key);
   743       typename std::map<Value, Key>::iterator it = first.find(node.value);
   744       if (it == first.end()) {
   745         node.prev = node.next = INVALID;
   746         if (node.next != INVALID) {
   747           Parent::operator[](node.next).prev = key;	
   748         }
   749         first.insert(make_pair(node.value, key));
   750       } else {
   751         node.prev = INVALID;
   752         node.next = it->second;
   753         if (node.next != INVALID) {
   754           Parent::operator[](node.next).prev = key;	
   755         }
   756         it->second = key;
   757       }
   758     }
   759 
   760   public:
   761 
   762     /// \brief Forward iterator for values.
   763     ///
   764     /// This iterator is an stl compatible forward
   765     /// iterator on the values of the map. The values can
   766     /// be accessed in the [beginValue, endValue) range.
   767     ///
   768     class ValueIterator 
   769       : public std::iterator<std::forward_iterator_tag, Value> {
   770       friend class IterableValueMap;
   771     private:
   772       ValueIterator(typename std::map<Value, Key>::const_iterator _it) 
   773         : it(_it) {}
   774     public:
   775       
   776       ValueIterator() {}
   777 
   778       ValueIterator& operator++() { ++it; return *this; }
   779       ValueIterator operator++(int) { 
   780         ValueIterator tmp(*this); 
   781         operator++();
   782         return tmp; 
   783       }
   784 
   785       const Value& operator*() const { return it->first; }
   786       const Value* operator->() const { return &(it->first); }
   787 
   788       bool operator==(ValueIterator jt) const { return it == jt.it; }
   789       bool operator!=(ValueIterator jt) const { return it != jt.it; }
   790       
   791     private:
   792       typename std::map<Value, Key>::const_iterator it;
   793     };
   794 
   795     /// \brief Returns an iterator to the first value.
   796     ///
   797     /// Returns an stl compatible iterator to the 
   798     /// first value of the map. The values of the
   799     /// map can be accessed in the [beginValue, endValue)
   800     /// range.
   801     ValueIterator beginValue() const {
   802       return ValueIterator(first.begin());
   803     }
   804 
   805     /// \brief Returns an iterator after the last value.
   806     ///
   807     /// Returns an stl compatible iterator after the 
   808     /// last value of the map. The values of the
   809     /// map can be accessed in the [beginValue, endValue)
   810     /// range.
   811     ValueIterator endValue() const {
   812       return ValueIterator(first.end());
   813     }
   814 
   815     /// \brief Set operation of the map.
   816     ///
   817     /// Set operation of the map.
   818     void set(const Key& key, const Value& value) {
   819       unlace(key);
   820       Parent::operator[](key).value = value;
   821       lace(key);
   822     }
   823 
   824     /// \brief Const subscript operator of the map.
   825     ///
   826     /// Const subscript operator of the map.
   827     const Value& operator[](const Key& key) const {
   828       return Parent::operator[](key).value;
   829     }
   830 
   831     /// \brief Iterator for the keys with the same value.
   832     ///
   833     /// Iterator for the keys with the same value. It works
   834     /// like a graph item iterator in the map, it can be converted
   835     /// the item type of the map, incremented with \c ++ operator, and
   836     /// if the iterator leave the last valid item it will be equal to 
   837     /// \c INVALID.
   838     class ItemIt : public _Item {
   839     public:
   840       typedef _Item Parent;
   841 
   842       /// \brief Invalid constructor \& conversion.
   843       ///
   844       /// This constructor initializes the item to be invalid.
   845       /// \sa Invalid for more details.
   846       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
   847 
   848       /// \brief Creates an iterator with a value.
   849       ///
   850       /// Creates an iterator with a value. It iterates on the 
   851       /// keys which have the given value.
   852       /// \param map The IterableValueMap
   853       /// \param value The value
   854       ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
   855         typename std::map<Value, Key>::const_iterator it = 
   856           map.first.find(value); 
   857 	if (it == map.first.end()) {	  
   858 	  Parent::operator=(INVALID);
   859 	} else {
   860 	  Parent::operator=(it->second);
   861 	}
   862       } 
   863 
   864       /// \brief Increment operator.
   865       ///
   866       /// Increment Operator.
   867       ItemIt& operator++() {
   868 	Parent::operator=(_map->IterableValueMap::Parent::
   869 			  operator[](static_cast<Parent&>(*this)).next);
   870 	return *this;
   871       }
   872 
   873 
   874     private:
   875       const IterableValueMap* _map;
   876     };
   877 
   878   protected:
   879     
   880     virtual void add(const Key& key) {
   881       Parent::add(key);
   882       unlace(key);
   883     }
   884 
   885     virtual void add(const std::vector<Key>& keys) {
   886       Parent::add(keys);
   887       for (int i = 0; i < (int)keys.size(); ++i) {
   888         lace(keys[i]);
   889       }
   890     }
   891 
   892     virtual void erase(const Key& key) {
   893       unlace(key);
   894       Parent::erase(key);
   895     }
   896 
   897     virtual void erase(const std::vector<Key>& keys) {
   898       for (int i = 0; i < (int)keys.size(); ++i) {
   899         unlace(keys[i]);
   900       }
   901       Parent::erase(keys);
   902     }
   903 
   904     virtual void build() {
   905       Parent::build();
   906       for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
   907         lace(it);
   908       }
   909     }
   910 
   911     virtual void clear() {
   912       first.clear();
   913       Parent::clear();
   914     }
   915 
   916   private:
   917     std::map<Value, Key> first;
   918   };
   919 
   920   /// @}
   921 }
   922 
   923 #endif