lemon/maps.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 22 Jan 2008 16:03:41 +0000
changeset 86 eba5222bb6f5
parent 51 90201bb15a8d
child 80 15968e25ca08
permissions -rw-r--r--
Minor doc improvements
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     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_MAPS_H
    20 #define LEMON_MAPS_H
    21 
    22 #include <iterator>
    23 #include <functional>
    24 #include <vector>
    25 
    26 #include <lemon/bits/utility.h>
    27 // #include <lemon/bits/traits.h>
    28 
    29 ///\file
    30 ///\ingroup maps
    31 ///\brief Miscellaneous property maps
    32 ///
    33 #include <map>
    34 
    35 namespace lemon {
    36 
    37   /// \addtogroup maps
    38   /// @{
    39 
    40   /// Base class of maps.
    41 
    42   /// Base class of maps.
    43   /// It provides the necessary <tt>typedef</tt>s required by the map concept.
    44   template<typename K, typename T>
    45   class MapBase {
    46   public:
    47     /// The key type of the map.
    48     typedef K Key;
    49     /// The value type of the map. (The type of objects associated with the keys).
    50     typedef T Value;
    51   };
    52 
    53   /// Null map. (a.k.a. DoNothingMap)
    54 
    55   /// This map can be used if you have to provide a map only for
    56   /// its type definitions, or if you have to provide a writable map, 
    57   /// but data written to it is not required (i.e. it will be sent to 
    58   /// <tt>/dev/null</tt>).
    59   template<typename K, typename T>
    60   class NullMap : public MapBase<K, T> {
    61   public:
    62     typedef MapBase<K, T> Parent;
    63     typedef typename Parent::Key Key;
    64     typedef typename Parent::Value Value;
    65     
    66     /// Gives back a default constructed element.
    67     T operator[](const K&) const { return T(); }
    68     /// Absorbs the value.
    69     void set(const K&, const T&) {}
    70   };
    71 
    72   ///Returns a \c NullMap class
    73 
    74   ///This function just returns a \c NullMap class.
    75   ///\relates NullMap
    76   template <typename K, typename V> 
    77   NullMap<K, V> nullMap() {
    78     return NullMap<K, V>();
    79   }
    80 
    81 
    82   /// Constant map.
    83 
    84   /// This is a \ref concepts::ReadMap "readable" map which assigns a 
    85   /// specified value to each key.
    86   /// In other aspects it is equivalent to \c NullMap.
    87   template<typename K, typename T>
    88   class ConstMap : public MapBase<K, T> {
    89   private:
    90     T v;
    91   public:
    92 
    93     typedef MapBase<K, T> Parent;
    94     typedef typename Parent::Key Key;
    95     typedef typename Parent::Value Value;
    96 
    97     /// Default constructor
    98 
    99     /// Default constructor.
   100     /// The value of the map will be uninitialized. 
   101     /// (More exactly it will be default constructed.)
   102     ConstMap() {}
   103     
   104     /// Constructor with specified initial value
   105 
   106     /// Constructor with specified initial value.
   107     /// \param _v is the initial value of the map.
   108     ConstMap(const T &_v) : v(_v) {}
   109     
   110     ///\e
   111     T operator[](const K&) const { return v; }
   112 
   113     ///\e
   114     void setAll(const T &t) {
   115       v = t;
   116     }    
   117 
   118     template<typename T1>
   119     ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
   120   };
   121 
   122   ///Returns a \c ConstMap class
   123 
   124   ///This function just returns a \c ConstMap class.
   125   ///\relates ConstMap
   126   template<typename K, typename V> 
   127   inline ConstMap<K, V> constMap(const V &v) {
   128     return ConstMap<K, V>(v);
   129   }
   130 
   131 
   132   template<typename T, T v>
   133   struct Const { };
   134 
   135   /// Constant map with inlined constant value.
   136 
   137   /// This is a \ref concepts::ReadMap "readable" map which assigns a 
   138   /// specified value to each key.
   139   /// In other aspects it is equivalent to \c NullMap.
   140   template<typename K, typename V, V v>
   141   class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
   142   public:
   143     typedef MapBase<K, V> Parent;
   144     typedef typename Parent::Key Key;
   145     typedef typename Parent::Value Value;
   146 
   147     ConstMap() { }
   148     ///\e
   149     V operator[](const K&) const { return v; }
   150     ///\e
   151     void set(const K&, const V&) { }
   152   };
   153 
   154   ///Returns a \c ConstMap class with inlined value
   155 
   156   ///This function just returns a \c ConstMap class with inlined value.
   157   ///\relates ConstMap
   158   template<typename K, typename V, V v> 
   159   inline ConstMap<K, Const<V, v> > constMap() {
   160     return ConstMap<K, Const<V, v> >();
   161   }
   162 
   163   ///Map based on \c std::map
   164 
   165   ///This is essentially a wrapper for \c std::map with addition that
   166   ///you can specify a default value different from \c Value().
   167   ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
   168   template <typename K, typename T, typename Compare = std::less<K> >
   169   class StdMap : public MapBase<K, T> {
   170     template <typename K1, typename T1, typename C1>
   171     friend class StdMap;
   172   public:
   173 
   174     typedef MapBase<K, T> Parent;
   175     ///Key type
   176     typedef typename Parent::Key Key;
   177     ///Value type
   178     typedef typename Parent::Value Value;
   179     ///Reference Type
   180     typedef T& Reference;
   181     ///Const reference type
   182     typedef const T& ConstReference;
   183 
   184     typedef True ReferenceMapTag;
   185 
   186   private:
   187     
   188     typedef std::map<K, T, Compare> Map;
   189     Value _value;
   190     Map _map;
   191 
   192   public:
   193 
   194     /// Constructor with specified default value
   195     StdMap(const T& value = T()) : _value(value) {}
   196     /// \brief Constructs the map from an appropriate \c std::map, and 
   197     /// explicitly specifies a default value.
   198     template <typename T1, typename Comp1>
   199     StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 
   200       : _map(map.begin(), map.end()), _value(value) {}
   201     
   202     /// \brief Constructs a map from an other \ref StdMap.
   203     template<typename T1, typename Comp1>
   204     StdMap(const StdMap<Key, T1, Comp1> &c) 
   205       : _map(c._map.begin(), c._map.end()), _value(c._value) {}
   206 
   207   private:
   208 
   209     StdMap& operator=(const StdMap&);
   210 
   211   public:
   212 
   213     ///\e
   214     Reference operator[](const Key &k) {
   215       typename Map::iterator it = _map.lower_bound(k);
   216       if (it != _map.end() && !_map.key_comp()(k, it->first))
   217 	return it->second;
   218       else
   219 	return _map.insert(it, std::make_pair(k, _value))->second;
   220     }
   221 
   222     /// \e 
   223     ConstReference operator[](const Key &k) const {
   224       typename Map::const_iterator it = _map.find(k);
   225       if (it != _map.end())
   226 	return it->second;
   227       else
   228 	return _value;
   229     }
   230 
   231     /// \e 
   232     void set(const Key &k, const T &t) {
   233       typename Map::iterator it = _map.lower_bound(k);
   234       if (it != _map.end() && !_map.key_comp()(k, it->first))
   235 	it->second = t;
   236       else
   237 	_map.insert(it, std::make_pair(k, t));
   238     }
   239 
   240     /// \e
   241     void setAll(const T &t) {
   242       _value = t;
   243       _map.clear();
   244     }    
   245 
   246   };
   247   
   248   ///Returns a \c StdMap class
   249 
   250   ///This function just returns a \c StdMap class with specified 
   251   ///default value.
   252   ///\relates StdMap
   253   template<typename K, typename V, typename Compare> 
   254   inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
   255     return StdMap<K, V, Compare>(value);
   256   }
   257   
   258   ///Returns a \c StdMap class
   259 
   260   ///This function just returns a \c StdMap class with specified 
   261   ///default value.
   262   ///\relates StdMap
   263   template<typename K, typename V> 
   264   inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {
   265     return StdMap<K, V, std::less<K> >(value);
   266   }
   267   
   268   ///Returns a \c StdMap class created from an appropriate std::map
   269 
   270   ///This function just returns a \c StdMap class created from an 
   271   ///appropriate std::map.
   272   ///\relates StdMap
   273   template<typename K, typename V, typename Compare> 
   274   inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map, 
   275                                        const V& value = V() ) {
   276     return StdMap<K, V, Compare>(map, value);
   277   }
   278 
   279   ///Returns a \c StdMap class created from an appropriate std::map
   280 
   281   ///This function just returns a \c StdMap class created from an 
   282   ///appropriate std::map.
   283   ///\relates StdMap
   284   template<typename K, typename V> 
   285   inline StdMap<K, V, std::less<K> > stdMap( const std::map<K, V, std::less<K> > &map, 
   286                                              const V& value = V() ) {
   287     return StdMap<K, V, std::less<K> >(map, value);
   288   }
   289 
   290   /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
   291   ///
   292   /// This map has the <tt>[0..size-1]</tt> keyset and the values
   293   /// are stored in a \c std::vector<T>  container. It can be used with
   294   /// some data structures, for example \c UnionFind, \c BinHeap, when 
   295   /// the used items are small integer numbers.
   296   /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
   297   ///
   298   /// \todo Revise its name
   299   template <typename T>
   300   class IntegerMap : public MapBase<int, T> {
   301 
   302     template <typename T1>
   303     friend class IntegerMap;
   304 
   305   public:
   306 
   307     typedef MapBase<int, T> Parent;
   308     ///\e
   309     typedef typename Parent::Key Key;
   310     ///\e
   311     typedef typename Parent::Value Value;
   312     ///\e
   313     typedef T& Reference;
   314     ///\e
   315     typedef const T& ConstReference;
   316 
   317     typedef True ReferenceMapTag;
   318 
   319   private:
   320     
   321     typedef std::vector<T> Vector;
   322     Vector _vector;
   323 
   324   public:
   325 
   326     /// Constructor with specified default value
   327     IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
   328 
   329     /// \brief Constructs the map from an appropriate \c std::vector.
   330     template <typename T1>
   331     IntegerMap(const std::vector<T1>& vector) 
   332       : _vector(vector.begin(), vector.end()) {}
   333     
   334     /// \brief Constructs a map from an other \ref IntegerMap.
   335     template <typename T1>
   336     IntegerMap(const IntegerMap<T1> &c) 
   337       : _vector(c._vector.begin(), c._vector.end()) {}
   338 
   339     /// \brief Resize the container
   340     void resize(int size, const T& value = T()) {
   341       _vector.resize(size, value);
   342     }
   343 
   344   private:
   345 
   346     IntegerMap& operator=(const IntegerMap&);
   347 
   348   public:
   349 
   350     ///\e
   351     Reference operator[](Key k) {
   352       return _vector[k];
   353     }
   354 
   355     /// \e 
   356     ConstReference operator[](Key k) const {
   357       return _vector[k];
   358     }
   359 
   360     /// \e 
   361     void set(const Key &k, const T& t) {
   362       _vector[k] = t;
   363     }
   364 
   365   };
   366   
   367   ///Returns an \c IntegerMap class
   368 
   369   ///This function just returns an \c IntegerMap class.
   370   ///\relates IntegerMap
   371   template<typename T>
   372   inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
   373     return IntegerMap<T>(size, value);
   374   }
   375 
   376   /// @}
   377 
   378   /// \addtogroup map_adaptors
   379   /// @{
   380 
   381   /// \brief Identity map.
   382   ///
   383   /// This map gives back the given key as value without any
   384   /// modification. 
   385   template <typename T>
   386   class IdentityMap : public MapBase<T, T> {
   387   public:
   388     typedef MapBase<T, T> Parent;
   389     typedef typename Parent::Key Key;
   390     typedef typename Parent::Value Value;
   391 
   392     /// \e
   393     const T& operator[](const T& t) const {
   394       return t;
   395     }
   396   };
   397 
   398   ///Returns an \c IdentityMap class
   399 
   400   ///This function just returns an \c IdentityMap class.
   401   ///\relates IdentityMap
   402   template<typename T>
   403   inline IdentityMap<T> identityMap() {
   404     return IdentityMap<T>();
   405   }
   406   
   407 
   408   ///\brief Convert the \c Value of a map to another type using
   409   ///the default conversion.
   410   ///
   411   ///This \ref concepts::ReadMap "read only map"
   412   ///converts the \c Value of a map to type \c T.
   413   ///Its \c Key is inherited from \c M.
   414   template <typename M, typename T> 
   415   class ConvertMap : public MapBase<typename M::Key, T> {
   416     const M& m;
   417   public:
   418     typedef MapBase<typename M::Key, T> Parent;
   419     typedef typename Parent::Key Key;
   420     typedef typename Parent::Value Value;
   421 
   422     ///Constructor
   423 
   424     ///Constructor.
   425     ///\param _m is the underlying map.
   426     ConvertMap(const M &_m) : m(_m) {};
   427 
   428     ///\e
   429     Value operator[](const Key& k) const {return m[k];}
   430   };
   431   
   432   ///Returns a \c ConvertMap class
   433 
   434   ///This function just returns a \c ConvertMap class.
   435   ///\relates ConvertMap
   436   template<typename T, typename M>
   437   inline ConvertMap<M, T> convertMap(const M &m) {
   438     return ConvertMap<M, T>(m);
   439   }
   440 
   441   ///Simple wrapping of a map
   442 
   443   ///This \ref concepts::ReadMap "read only map" returns the simple
   444   ///wrapping of the given map. Sometimes the reference maps cannot be
   445   ///combined with simple read maps. This map adaptor wraps the given
   446   ///map to simple read map.
   447   ///
   448   ///\sa SimpleWriteMap
   449   ///
   450   /// \todo Revise the misleading name 
   451   template<typename M> 
   452   class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
   453     const M& m;
   454 
   455   public:
   456     typedef MapBase<typename M::Key, typename M::Value> Parent;
   457     typedef typename Parent::Key Key;
   458     typedef typename Parent::Value Value;
   459 
   460     ///Constructor
   461     SimpleMap(const M &_m) : m(_m) {};
   462     ///\e
   463     Value operator[](Key k) const {return m[k];}
   464   };
   465   
   466   ///Returns a \c SimpleMap class
   467 
   468   ///This function just returns a \c SimpleMap class.
   469   ///\relates SimpleMap
   470   template<typename M>
   471   inline SimpleMap<M> simpleMap(const M &m) {
   472     return SimpleMap<M>(m);
   473   }
   474 
   475   ///Simple writable wrapping of a map
   476 
   477   ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
   478   ///wrapping of the given map. Sometimes the reference maps cannot be
   479   ///combined with simple read-write maps. This map adaptor wraps the
   480   ///given map to simple read-write map.
   481   ///
   482   ///\sa SimpleMap
   483   ///
   484   /// \todo Revise the misleading name
   485   template<typename M> 
   486   class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
   487     M& m;
   488 
   489   public:
   490     typedef MapBase<typename M::Key, typename M::Value> Parent;
   491     typedef typename Parent::Key Key;
   492     typedef typename Parent::Value Value;
   493 
   494     ///Constructor
   495     SimpleWriteMap(M &_m) : m(_m) {};
   496     ///\e
   497     Value operator[](Key k) const {return m[k];}
   498     ///\e
   499     void set(Key k, const Value& c) { m.set(k, c); }
   500   };
   501 
   502   ///Returns a \c SimpleWriteMap class
   503 
   504   ///This function just returns a \c SimpleWriteMap class.
   505   ///\relates SimpleWriteMap
   506   template<typename M>
   507   inline SimpleWriteMap<M> simpleWriteMap(M &m) {
   508     return SimpleWriteMap<M>(m);
   509   }
   510 
   511   ///Sum of two maps
   512 
   513   ///This \ref concepts::ReadMap "read only map" returns the sum of the two
   514   ///given maps.
   515   ///Its \c Key and \c Value are inherited from \c M1.
   516   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   517   template<typename M1, typename M2> 
   518   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   519     const M1& m1;
   520     const M2& m2;
   521 
   522   public:
   523     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   524     typedef typename Parent::Key Key;
   525     typedef typename Parent::Value Value;
   526 
   527     ///Constructor
   528     AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
   529     ///\e
   530     Value operator[](Key k) const {return m1[k]+m2[k];}
   531   };
   532   
   533   ///Returns an \c AddMap class
   534 
   535   ///This function just returns an \c AddMap class.
   536   ///\todo Extend the documentation: how to call these type of functions?
   537   ///
   538   ///\relates AddMap
   539   template<typename M1, typename M2> 
   540   inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
   541     return AddMap<M1, M2>(m1,m2);
   542   }
   543 
   544   ///Shift a map with a constant.
   545 
   546   ///This \ref concepts::ReadMap "read only map" returns the sum of the
   547   ///given map and a constant value.
   548   ///Its \c Key and \c Value are inherited from \c M.
   549   ///
   550   ///Actually,
   551   ///\code
   552   ///  ShiftMap<X> sh(x,v);
   553   ///\endcode
   554   ///is equivalent to
   555   ///\code
   556   ///  ConstMap<X::Key, X::Value> c_tmp(v);
   557   ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
   558   ///\endcode
   559   ///
   560   ///\sa ShiftWriteMap
   561   template<typename M, typename C = typename M::Value> 
   562   class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
   563     const M& m;
   564     C v;
   565   public:
   566     typedef MapBase<typename M::Key, typename M::Value> Parent;
   567     typedef typename Parent::Key Key;
   568     typedef typename Parent::Value Value;
   569 
   570     ///Constructor
   571 
   572     ///Constructor.
   573     ///\param _m is the undelying map.
   574     ///\param _v is the shift value.
   575     ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
   576     ///\e
   577     Value operator[](Key k) const {return m[k] + v;}
   578   };
   579 
   580   ///Shift a map with a constant (ReadWrite version).
   581 
   582   ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
   583   ///given map and a constant value. It makes also possible to write the map.
   584   ///Its \c Key and \c Value are inherited from \c M.
   585   ///
   586   ///\sa ShiftMap
   587   template<typename M, typename C = typename M::Value> 
   588   class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
   589     M& m;
   590     C v;
   591   public:
   592     typedef MapBase<typename M::Key, typename M::Value> Parent;
   593     typedef typename Parent::Key Key;
   594     typedef typename Parent::Value Value;
   595 
   596     ///Constructor
   597 
   598     ///Constructor.
   599     ///\param _m is the undelying map.
   600     ///\param _v is the shift value.
   601     ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
   602     /// \e
   603     Value operator[](Key k) const {return m[k] + v;}
   604     /// \e
   605     void set(Key k, const Value& c) { m.set(k, c - v); }
   606   };
   607   
   608   ///Returns a \c ShiftMap class
   609 
   610   ///This function just returns a \c ShiftMap class.
   611   ///\relates ShiftMap
   612   template<typename M, typename C> 
   613   inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
   614     return ShiftMap<M, C>(m,v);
   615   }
   616 
   617   ///Returns a \c ShiftWriteMap class
   618 
   619   ///This function just returns a \c ShiftWriteMap class.
   620   ///\relates ShiftWriteMap
   621   template<typename M, typename C> 
   622   inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
   623     return ShiftWriteMap<M, C>(m,v);
   624   }
   625 
   626   ///Difference of two maps
   627 
   628   ///This \ref concepts::ReadMap "read only map" returns the difference
   629   ///of the values of the two given maps.
   630   ///Its \c Key and \c Value are inherited from \c M1.
   631   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   632   ///
   633   /// \todo Revise the misleading name
   634   template<typename M1, typename M2> 
   635   class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
   636     const M1& m1;
   637     const M2& m2;
   638   public:
   639     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   640     typedef typename Parent::Key Key;
   641     typedef typename Parent::Value Value;
   642 
   643     ///Constructor
   644     SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
   645     /// \e
   646     Value operator[](Key k) const {return m1[k]-m2[k];}
   647   };
   648   
   649   ///Returns a \c SubMap class
   650 
   651   ///This function just returns a \c SubMap class.
   652   ///
   653   ///\relates SubMap
   654   template<typename M1, typename M2> 
   655   inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
   656     return SubMap<M1, M2>(m1, m2);
   657   }
   658 
   659   ///Product of two maps
   660 
   661   ///This \ref concepts::ReadMap "read only map" returns the product of the
   662   ///values of the two given maps.
   663   ///Its \c Key and \c Value are inherited from \c M1.
   664   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   665   template<typename M1, typename M2> 
   666   class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
   667     const M1& m1;
   668     const M2& m2;
   669   public:
   670     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   671     typedef typename Parent::Key Key;
   672     typedef typename Parent::Value Value;
   673 
   674     ///Constructor
   675     MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
   676     /// \e
   677     Value operator[](Key k) const {return m1[k]*m2[k];}
   678   };
   679   
   680   ///Returns a \c MulMap class
   681 
   682   ///This function just returns a \c MulMap class.
   683   ///\relates MulMap
   684   template<typename M1, typename M2> 
   685   inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
   686     return MulMap<M1, M2>(m1,m2);
   687   }
   688  
   689   ///Scales a map with a constant.
   690 
   691   ///This \ref concepts::ReadMap "read only map" returns the value of the
   692   ///given map multiplied from the left side with a constant value.
   693   ///Its \c Key and \c Value are inherited from \c M.
   694   ///
   695   ///Actually,
   696   ///\code
   697   ///  ScaleMap<X> sc(x,v);
   698   ///\endcode
   699   ///is equivalent to
   700   ///\code
   701   ///  ConstMap<X::Key, X::Value> c_tmp(v);
   702   ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
   703   ///\endcode
   704   ///
   705   ///\sa ScaleWriteMap
   706   template<typename M, typename C = typename M::Value> 
   707   class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
   708     const M& m;
   709     C v;
   710   public:
   711     typedef MapBase<typename M::Key, typename M::Value> Parent;
   712     typedef typename Parent::Key Key;
   713     typedef typename Parent::Value Value;
   714 
   715     ///Constructor
   716 
   717     ///Constructor.
   718     ///\param _m is the undelying map.
   719     ///\param _v is the scaling value.
   720     ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
   721     /// \e
   722     Value operator[](Key k) const {return v * m[k];}
   723   };
   724 
   725   ///Scales a map with a constant (ReadWrite version).
   726 
   727   ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
   728   ///given map multiplied from the left side with a constant value. It can
   729   ///also be used as write map if the \c / operator is defined between
   730   ///\c Value and \c C and the given multiplier is not zero.
   731   ///Its \c Key and \c Value are inherited from \c M.
   732   ///
   733   ///\sa ScaleMap
   734   template<typename M, typename C = typename M::Value> 
   735   class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
   736     M& m;
   737     C v;
   738   public:
   739     typedef MapBase<typename M::Key, typename M::Value> Parent;
   740     typedef typename Parent::Key Key;
   741     typedef typename Parent::Value Value;
   742 
   743     ///Constructor
   744 
   745     ///Constructor.
   746     ///\param _m is the undelying map.
   747     ///\param _v is the scaling value.
   748     ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
   749     /// \e
   750     Value operator[](Key k) const {return v * m[k];}
   751     /// \e
   752     void set(Key k, const Value& c) { m.set(k, c / v);}
   753   };
   754   
   755   ///Returns a \c ScaleMap class
   756 
   757   ///This function just returns a \c ScaleMap class.
   758   ///\relates ScaleMap
   759   template<typename M, typename C> 
   760   inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
   761     return ScaleMap<M, C>(m,v);
   762   }
   763 
   764   ///Returns a \c ScaleWriteMap class
   765 
   766   ///This function just returns a \c ScaleWriteMap class.
   767   ///\relates ScaleWriteMap
   768   template<typename M, typename C> 
   769   inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
   770     return ScaleWriteMap<M, C>(m,v);
   771   }
   772 
   773   ///Quotient of two maps
   774 
   775   ///This \ref concepts::ReadMap "read only map" returns the quotient of the
   776   ///values of the two given maps.
   777   ///Its \c Key and \c Value are inherited from \c M1.
   778   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   779   template<typename M1, typename M2> 
   780   class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
   781     const M1& m1;
   782     const M2& m2;
   783   public:
   784     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   785     typedef typename Parent::Key Key;
   786     typedef typename Parent::Value Value;
   787 
   788     ///Constructor
   789     DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
   790     /// \e
   791     Value operator[](Key k) const {return m1[k]/m2[k];}
   792   };
   793   
   794   ///Returns a \c DivMap class
   795 
   796   ///This function just returns a \c DivMap class.
   797   ///\relates DivMap
   798   template<typename M1, typename M2> 
   799   inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
   800     return DivMap<M1, M2>(m1,m2);
   801   }
   802   
   803   ///Composition of two maps
   804 
   805   ///This \ref concepts::ReadMap "read only map" returns the composition of
   806   ///two given maps.
   807   ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
   808   ///then for
   809   ///\code
   810   ///  ComposeMap<M1, M2> cm(m1,m2);
   811   ///\endcode
   812   /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
   813   ///
   814   ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
   815   ///\c M2::Value must be convertible to \c M1::Key.
   816   ///
   817   ///\sa CombineMap
   818   ///
   819   ///\todo Check the requirements.
   820   template <typename M1, typename M2> 
   821   class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
   822     const M1& m1;
   823     const M2& m2;
   824   public:
   825     typedef MapBase<typename M2::Key, typename M1::Value> Parent;
   826     typedef typename Parent::Key Key;
   827     typedef typename Parent::Value Value;
   828 
   829     ///Constructor
   830     ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
   831     
   832     /// \e
   833 
   834 
   835     /// \todo Use the  MapTraits once it is ported.
   836     ///
   837 
   838     //typename MapTraits<M1>::ConstReturnValue
   839     typename M1::Value
   840     operator[](Key k) const {return m1[m2[k]];}
   841   };
   842 
   843   ///Returns a \c ComposeMap class
   844 
   845   ///This function just returns a \c ComposeMap class.
   846   ///\relates ComposeMap
   847   template <typename M1, typename M2> 
   848   inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
   849     return ComposeMap<M1, M2>(m1,m2);
   850   }
   851   
   852   ///Combine of two maps using an STL (binary) functor.
   853 
   854   ///Combine of two maps using an STL (binary) functor.
   855   ///
   856   ///This \ref concepts::ReadMap "read only map" takes two maps and a
   857   ///binary functor and returns the composition of the two
   858   ///given maps unsing the functor. 
   859   ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
   860   ///and \c f is of \c F, then for
   861   ///\code
   862   ///  CombineMap<M1,M2,F,V> cm(m1,m2,f);
   863   ///\endcode
   864   /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
   865   ///
   866   ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
   867   ///\c M2::Value and \c M1::Value must be convertible to the corresponding
   868   ///input parameter of \c F and the return type of \c F must be convertible
   869   ///to \c V.
   870   ///
   871   ///\sa ComposeMap
   872   ///
   873   ///\todo Check the requirements.
   874   template<typename M1, typename M2, typename F,
   875 	   typename V = typename F::result_type> 
   876   class CombineMap : public MapBase<typename M1::Key, V> {
   877     const M1& m1;
   878     const M2& m2;
   879     F f;
   880   public:
   881     typedef MapBase<typename M1::Key, V> Parent;
   882     typedef typename Parent::Key Key;
   883     typedef typename Parent::Value Value;
   884 
   885     ///Constructor
   886     CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
   887       : m1(_m1), m2(_m2), f(_f) {};
   888     /// \e
   889     Value operator[](Key k) const {return f(m1[k],m2[k]);}
   890   };
   891   
   892   ///Returns a \c CombineMap class
   893 
   894   ///This function just returns a \c CombineMap class.
   895   ///
   896   ///For example if \c m1 and \c m2 are both \c double valued maps, then 
   897   ///\code
   898   ///combineMap(m1,m2,std::plus<double>())
   899   ///\endcode
   900   ///is equivalent to
   901   ///\code
   902   ///addMap(m1,m2)
   903   ///\endcode
   904   ///
   905   ///This function is specialized for adaptable binary function
   906   ///classes and C++ functions.
   907   ///
   908   ///\relates CombineMap
   909   template<typename M1, typename M2, typename F, typename V> 
   910   inline CombineMap<M1, M2, F, V> 
   911   combineMap(const M1& m1,const M2& m2, const F& f) {
   912     return CombineMap<M1, M2, F, V>(m1,m2,f);
   913   }
   914 
   915   template<typename M1, typename M2, typename F> 
   916   inline CombineMap<M1, M2, F, typename F::result_type> 
   917   combineMap(const M1& m1, const M2& m2, const F& f) {
   918     return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
   919   }
   920 
   921   template<typename M1, typename M2, typename K1, typename K2, typename V> 
   922   inline CombineMap<M1, M2, V (*)(K1, K2), V> 
   923   combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
   924     return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
   925   }
   926 
   927   ///Negative value of a map
   928 
   929   ///This \ref concepts::ReadMap "read only map" returns the negative
   930   ///value of the value returned by the given map.
   931   ///Its \c Key and \c Value are inherited from \c M.
   932   ///The unary \c - operator must be defined for \c Value, of course.
   933   ///
   934   ///\sa NegWriteMap
   935   template<typename M> 
   936   class NegMap : public MapBase<typename M::Key, typename M::Value> {
   937     const M& m;
   938   public:
   939     typedef MapBase<typename M::Key, typename M::Value> Parent;
   940     typedef typename Parent::Key Key;
   941     typedef typename Parent::Value Value;
   942 
   943     ///Constructor
   944     NegMap(const M &_m) : m(_m) {};
   945     /// \e
   946     Value operator[](Key k) const {return -m[k];}
   947   };
   948   
   949   ///Negative value of a map (ReadWrite version)
   950 
   951   ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
   952   ///value of the value returned by the given map.
   953   ///Its \c Key and \c Value are inherited from \c M.
   954   ///The unary \c - operator must be defined for \c Value, of course.
   955   ///
   956   /// \sa NegMap
   957   template<typename M> 
   958   class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
   959     M& m;
   960   public:
   961     typedef MapBase<typename M::Key, typename M::Value> Parent;
   962     typedef typename Parent::Key Key;
   963     typedef typename Parent::Value Value;
   964 
   965     ///Constructor
   966     NegWriteMap(M &_m) : m(_m) {};
   967     /// \e
   968     Value operator[](Key k) const {return -m[k];}
   969     /// \e
   970     void set(Key k, const Value& v) { m.set(k, -v); }
   971   };
   972 
   973   ///Returns a \c NegMap class
   974 
   975   ///This function just returns a \c NegMap class.
   976   ///\relates NegMap
   977   template <typename M> 
   978   inline NegMap<M> negMap(const M &m) {
   979     return NegMap<M>(m);
   980   }
   981 
   982   ///Returns a \c NegWriteMap class
   983 
   984   ///This function just returns a \c NegWriteMap class.
   985   ///\relates NegWriteMap
   986   template <typename M> 
   987   inline NegWriteMap<M> negMap(M &m) {
   988     return NegWriteMap<M>(m);
   989   }
   990 
   991   ///Absolute value of a map
   992 
   993   ///This \ref concepts::ReadMap "read only map" returns the absolute value
   994   ///of the value returned by the given map.
   995   ///Its \c Key and \c Value are inherited from \c M. 
   996   ///\c Value must be comparable to \c 0 and the unary \c -
   997   ///operator must be defined for it, of course.
   998   template<typename M> 
   999   class AbsMap : public MapBase<typename M::Key, typename M::Value> {
  1000     const M& m;
  1001   public:
  1002     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1003     typedef typename Parent::Key Key;
  1004     typedef typename Parent::Value Value;
  1005 
  1006     ///Constructor
  1007     AbsMap(const M &_m) : m(_m) {};
  1008     /// \e
  1009     Value operator[](Key k) const {
  1010       Value tmp = m[k]; 
  1011       return tmp >= 0 ? tmp : -tmp;
  1012     }
  1013 
  1014   };
  1015   
  1016   ///Returns an \c AbsMap class
  1017 
  1018   ///This function just returns an \c AbsMap class.
  1019   ///\relates AbsMap
  1020   template<typename M> 
  1021   inline AbsMap<M> absMap(const M &m) {
  1022     return AbsMap<M>(m);
  1023   }
  1024 
  1025   ///Converts an STL style functor to a map
  1026 
  1027   ///This \ref concepts::ReadMap "read only map" returns the value
  1028   ///of a given functor.
  1029   ///
  1030   ///Template parameters \c K and \c V will become its
  1031   ///\c Key and \c Value. 
  1032   ///In most cases they have to be given explicitly because a 
  1033   ///functor typically does not provide \c argument_type and 
  1034   ///\c result_type typedefs.
  1035   ///
  1036   ///Parameter \c F is the type of the used functor.
  1037   ///
  1038   ///\sa MapFunctor
  1039   template<typename F, 
  1040 	   typename K = typename F::argument_type, 
  1041 	   typename V = typename F::result_type> 
  1042   class FunctorMap : public MapBase<K, V> {
  1043     F f;
  1044   public:
  1045     typedef MapBase<K, V> Parent;
  1046     typedef typename Parent::Key Key;
  1047     typedef typename Parent::Value Value;
  1048 
  1049     ///Constructor
  1050     FunctorMap(const F &_f = F()) : f(_f) {}
  1051     /// \e
  1052     Value operator[](Key k) const { return f(k);}
  1053   };
  1054   
  1055   ///Returns a \c FunctorMap class
  1056 
  1057   ///This function just returns a \c FunctorMap class.
  1058   ///
  1059   ///This function is specialized for adaptable binary function
  1060   ///classes and C++ functions.
  1061   ///
  1062   ///\relates FunctorMap
  1063   template<typename K, typename V, typename F> inline 
  1064   FunctorMap<F, K, V> functorMap(const F &f) {
  1065     return FunctorMap<F, K, V>(f);
  1066   }
  1067 
  1068   template <typename F> inline 
  1069   FunctorMap<F, typename F::argument_type, typename F::result_type> 
  1070   functorMap(const F &f) {
  1071     return FunctorMap<F, typename F::argument_type, 
  1072       typename F::result_type>(f);
  1073   }
  1074 
  1075   template <typename K, typename V> inline 
  1076   FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
  1077     return FunctorMap<V (*)(K), K, V>(f);
  1078   }
  1079 
  1080 
  1081   ///Converts a map to an STL style (unary) functor
  1082 
  1083   ///This class Converts a map to an STL style (unary) functor.
  1084   ///That is it provides an <tt>operator()</tt> to read its values.
  1085   ///
  1086   ///For the sake of convenience it also works as
  1087   ///a ususal \ref concepts::ReadMap "readable map",
  1088   ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
  1089   ///
  1090   ///\sa FunctorMap
  1091   template <typename M> 
  1092   class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
  1093     const M& m;
  1094   public:
  1095     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1096     typedef typename Parent::Key Key;
  1097     typedef typename Parent::Value Value;
  1098 
  1099     typedef typename M::Key argument_type;
  1100     typedef typename M::Value result_type;
  1101 
  1102     ///Constructor
  1103     MapFunctor(const M &_m) : m(_m) {};
  1104     ///\e
  1105     Value operator()(Key k) const {return m[k];}
  1106     ///\e
  1107     Value operator[](Key k) const {return m[k];}
  1108   };
  1109   
  1110   ///Returns a \c MapFunctor class
  1111 
  1112   ///This function just returns a \c MapFunctor class.
  1113   ///\relates MapFunctor
  1114   template<typename M> 
  1115   inline MapFunctor<M> mapFunctor(const M &m) {
  1116     return MapFunctor<M>(m);
  1117   }
  1118 
  1119   ///Just readable version of \ref ForkWriteMap
  1120 
  1121   ///This map has two \ref concepts::ReadMap "readable map"
  1122   ///parameters and each read request will be passed just to the
  1123   ///first map. This class is the just readable map type of \c ForkWriteMap.
  1124   ///
  1125   ///The \c Key and \c Value are inherited from \c M1.
  1126   ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
  1127   ///
  1128   ///\sa ForkWriteMap
  1129   ///
  1130   /// \todo Why is it needed?
  1131   template<typename  M1, typename M2> 
  1132   class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
  1133     const M1& m1;
  1134     const M2& m2;
  1135   public:
  1136     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
  1137     typedef typename Parent::Key Key;
  1138     typedef typename Parent::Value Value;
  1139 
  1140     ///Constructor
  1141     ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
  1142     /// \e
  1143     Value operator[](Key k) const {return m1[k];}
  1144   };
  1145 
  1146 
  1147   ///Applies all map setting operations to two maps
  1148 
  1149   ///This map has two \ref concepts::WriteMap "writable map"
  1150   ///parameters and each write request will be passed to both of them.
  1151   ///If \c M1 is also \ref concepts::ReadMap "readable",
  1152   ///then the read operations will return the
  1153   ///corresponding values of \c M1.
  1154   ///
  1155   ///The \c Key and \c Value are inherited from \c M1.
  1156   ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
  1157   ///
  1158   ///\sa ForkMap
  1159   template<typename  M1, typename M2> 
  1160   class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
  1161     M1& m1;
  1162     M2& m2;
  1163   public:
  1164     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
  1165     typedef typename Parent::Key Key;
  1166     typedef typename Parent::Value Value;
  1167 
  1168     ///Constructor
  1169     ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
  1170     ///\e
  1171     Value operator[](Key k) const {return m1[k];}
  1172     ///\e
  1173     void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
  1174   };
  1175   
  1176   ///Returns a \c ForkMap class
  1177 
  1178   ///This function just returns a \c ForkMap class.
  1179   ///\relates ForkMap
  1180   template <typename M1, typename M2> 
  1181   inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
  1182     return ForkMap<M1, M2>(m1,m2);
  1183   }
  1184 
  1185   ///Returns a \c ForkWriteMap class
  1186 
  1187   ///This function just returns a \c ForkWriteMap class.
  1188   ///\relates ForkWriteMap
  1189   template <typename M1, typename M2> 
  1190   inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
  1191     return ForkWriteMap<M1, M2>(m1,m2);
  1192   }
  1193 
  1194 
  1195   
  1196   /* ************* BOOL MAPS ******************* */
  1197   
  1198   ///Logical 'not' of a map
  1199   
  1200   ///This bool \ref concepts::ReadMap "read only map" returns the 
  1201   ///logical negation of the value returned by the given map.
  1202   ///Its \c Key is inherited from \c M, its \c Value is \c bool.
  1203   ///
  1204   ///\sa NotWriteMap
  1205   template <typename M> 
  1206   class NotMap : public MapBase<typename M::Key, bool> {
  1207     const M& m;
  1208   public:
  1209     typedef MapBase<typename M::Key, bool> Parent;
  1210     typedef typename Parent::Key Key;
  1211     typedef typename Parent::Value Value;
  1212 
  1213     /// Constructor
  1214     NotMap(const M &_m) : m(_m) {};
  1215     ///\e
  1216     Value operator[](Key k) const {return !m[k];}
  1217   };
  1218 
  1219   ///Logical 'not' of a map (ReadWrie version)
  1220   
  1221   ///This bool \ref concepts::ReadWriteMap "read-write map" returns the 
  1222   ///logical negation of the value returned by the given map. When it is set,
  1223   ///the opposite value is set to the original map.
  1224   ///Its \c Key is inherited from \c M, its \c Value is \c bool.
  1225   ///
  1226   ///\sa NotMap
  1227   template <typename M> 
  1228   class NotWriteMap : public MapBase<typename M::Key, bool> {
  1229     M& m;
  1230   public:
  1231     typedef MapBase<typename M::Key, bool> Parent;
  1232     typedef typename Parent::Key Key;
  1233     typedef typename Parent::Value Value;
  1234 
  1235     /// Constructor
  1236     NotWriteMap(M &_m) : m(_m) {};
  1237     ///\e
  1238     Value operator[](Key k) const {return !m[k];}
  1239     ///\e
  1240     void set(Key k, bool v) { m.set(k, !v); }
  1241   };
  1242   
  1243   ///Returns a \c NotMap class
  1244   
  1245   ///This function just returns a \c NotMap class.
  1246   ///\relates NotMap
  1247   template <typename M> 
  1248   inline NotMap<M> notMap(const M &m) {
  1249     return NotMap<M>(m);
  1250   }
  1251   
  1252   ///Returns a \c NotWriteMap class
  1253   
  1254   ///This function just returns a \c NotWriteMap class.
  1255   ///\relates NotWriteMap
  1256   template <typename M> 
  1257   inline NotWriteMap<M> notMap(M &m) {
  1258     return NotWriteMap<M>(m);
  1259   }
  1260 
  1261   namespace _maps_bits {
  1262 
  1263     template <typename Value>
  1264     struct Identity {
  1265       typedef Value argument_type;
  1266       typedef Value result_type;
  1267       Value operator()(const Value& val) const {
  1268 	return val;
  1269       }
  1270     };
  1271 
  1272     template <typename _Iterator, typename Enable = void>
  1273     struct IteratorTraits {
  1274       typedef typename std::iterator_traits<_Iterator>::value_type Value;
  1275     };
  1276 
  1277     template <typename _Iterator>
  1278     struct IteratorTraits<_Iterator,
  1279       typename exists<typename _Iterator::container_type>::type> 
  1280     {
  1281       typedef typename _Iterator::container_type::value_type Value;
  1282     };
  1283 
  1284   }
  1285   
  1286 
  1287   /// \brief Writable bool map for logging each \c true assigned element
  1288   ///
  1289   /// A \ref concepts::ReadWriteMap "read-write" bool map for logging 
  1290   /// each \c true assigned element, i.e it copies all the keys set 
  1291   /// to \c true to the given iterator.
  1292   ///
  1293   /// \note The container of the iterator should contain space 
  1294   /// for each element.
  1295   ///
  1296   /// The following example shows how you can write the edges found by 
  1297   /// the \ref Prim algorithm directly to the standard output.
  1298   ///\code
  1299   /// typedef IdMap<Graph, Edge> EdgeIdMap;
  1300   /// EdgeIdMap edgeId(graph);
  1301   ///
  1302   /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
  1303   /// EdgeIdFunctor edgeIdFunctor(edgeId);
  1304   ///
  1305   /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor> 
  1306   ///   writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
  1307   ///
  1308   /// prim(graph, cost, writerMap);
  1309   ///\endcode
  1310   ///
  1311   ///\sa BackInserterBoolMap 
  1312   ///\sa FrontInserterBoolMap 
  1313   ///\sa InserterBoolMap 
  1314   ///
  1315   ///\todo Revise the name of this class and the related ones.
  1316   template <typename _Iterator, 
  1317             typename _Functor =
  1318             _maps_bits::Identity<typename _maps_bits::
  1319                                  IteratorTraits<_Iterator>::Value> >
  1320   class StoreBoolMap {
  1321   public:
  1322     typedef _Iterator Iterator;
  1323 
  1324     typedef typename _Functor::argument_type Key;
  1325     typedef bool Value;
  1326 
  1327     typedef _Functor Functor;
  1328 
  1329     /// Constructor
  1330     StoreBoolMap(Iterator it, const Functor& functor = Functor()) 
  1331       : _begin(it), _end(it), _functor(functor) {}
  1332 
  1333     /// Gives back the given iterator set for the first key
  1334     Iterator begin() const {
  1335       return _begin;
  1336     }
  1337  
  1338     /// Gives back the the 'after the last' iterator
  1339     Iterator end() const {
  1340       return _end;
  1341     }
  1342 
  1343     /// The \c set function of the map
  1344     void set(const Key& key, Value value) const {
  1345       if (value) {
  1346 	*_end++ = _functor(key);
  1347       }
  1348     }
  1349     
  1350   private:
  1351     Iterator _begin;
  1352     mutable Iterator _end;
  1353     Functor _functor;
  1354   };
  1355 
  1356   /// \brief Writable bool map for logging each \c true assigned element in 
  1357   /// a back insertable container.
  1358   ///
  1359   /// Writable bool map for logging each \c true assigned element by pushing
  1360   /// them into a back insertable container.
  1361   /// It can be used to retrieve the items into a standard
  1362   /// container. The next example shows how you can store the
  1363   /// edges found by the Prim algorithm in a vector.
  1364   ///
  1365   ///\code
  1366   /// vector<Edge> span_tree_edges;
  1367   /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
  1368   /// prim(graph, cost, inserter_map);
  1369   ///\endcode
  1370   ///
  1371   ///\sa StoreBoolMap
  1372   ///\sa FrontInserterBoolMap
  1373   ///\sa InserterBoolMap
  1374   template <typename Container,
  1375             typename Functor =
  1376             _maps_bits::Identity<typename Container::value_type> >
  1377   class BackInserterBoolMap {
  1378   public:
  1379     typedef typename Functor::argument_type Key;
  1380     typedef bool Value;
  1381 
  1382     /// Constructor
  1383     BackInserterBoolMap(Container& _container, 
  1384                         const Functor& _functor = Functor()) 
  1385       : container(_container), functor(_functor) {}
  1386 
  1387     /// The \c set function of the map
  1388     void set(const Key& key, Value value) {
  1389       if (value) {
  1390 	container.push_back(functor(key));
  1391       }
  1392     }
  1393     
  1394   private:
  1395     Container& container;
  1396     Functor functor;
  1397   };
  1398 
  1399   /// \brief Writable bool map for logging each \c true assigned element in 
  1400   /// a front insertable container.
  1401   ///
  1402   /// Writable bool map for logging each \c true assigned element by pushing
  1403   /// them into a front insertable container.
  1404   /// It can be used to retrieve the items into a standard
  1405   /// container. For example see \ref BackInserterBoolMap.
  1406   ///
  1407   ///\sa BackInserterBoolMap
  1408   ///\sa InserterBoolMap
  1409   template <typename Container,
  1410             typename Functor =
  1411             _maps_bits::Identity<typename Container::value_type> >
  1412   class FrontInserterBoolMap {
  1413   public:
  1414     typedef typename Functor::argument_type Key;
  1415     typedef bool Value;
  1416 
  1417     /// Constructor
  1418     FrontInserterBoolMap(Container& _container,
  1419                          const Functor& _functor = Functor()) 
  1420       : container(_container), functor(_functor) {}
  1421 
  1422     /// The \c set function of the map
  1423     void set(const Key& key, Value value) {
  1424       if (value) {
  1425 	container.push_front(functor(key));
  1426       }
  1427     }
  1428     
  1429   private:
  1430     Container& container;    
  1431     Functor functor;
  1432   };
  1433 
  1434   /// \brief Writable bool map for storing each \c true assigned element in 
  1435   /// an insertable container.
  1436   ///
  1437   /// Writable bool map for storing each \c true assigned element in an 
  1438   /// insertable container. It will insert all the keys set to \c true into
  1439   /// the container.
  1440   ///
  1441   /// For example, if you want to store the cut arcs of the strongly
  1442   /// connected components in a set you can use the next code:
  1443   ///
  1444   ///\code
  1445   /// set<Arc> cut_arcs;
  1446   /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
  1447   /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
  1448   ///\endcode
  1449   ///
  1450   ///\sa BackInserterBoolMap
  1451   ///\sa FrontInserterBoolMap
  1452   template <typename Container,
  1453             typename Functor =
  1454             _maps_bits::Identity<typename Container::value_type> >
  1455   class InserterBoolMap {
  1456   public:
  1457     typedef typename Container::value_type Key;
  1458     typedef bool Value;
  1459 
  1460     /// Constructor with specified iterator
  1461     
  1462     /// Constructor with specified iterator.
  1463     /// \param _container The container for storing the elements.
  1464     /// \param _it The elements will be inserted before this iterator.
  1465     /// \param _functor The functor that is used when an element is stored.
  1466     InserterBoolMap(Container& _container, typename Container::iterator _it,
  1467                     const Functor& _functor = Functor()) 
  1468       : container(_container), it(_it), functor(_functor) {}
  1469 
  1470     /// Constructor
  1471 
  1472     /// Constructor without specified iterator.
  1473     /// The elements will be inserted before <tt>_container.end()</tt>.
  1474     /// \param _container The container for storing the elements.
  1475     /// \param _functor The functor that is used when an element is stored.
  1476     InserterBoolMap(Container& _container, const Functor& _functor = Functor())
  1477       : container(_container), it(_container.end()), functor(_functor) {}
  1478 
  1479     /// The \c set function of the map
  1480     void set(const Key& key, Value value) {
  1481       if (value) {
  1482 	it = container.insert(it, functor(key));
  1483         ++it;
  1484       }
  1485     }
  1486     
  1487   private:
  1488     Container& container;
  1489     typename Container::iterator it;
  1490     Functor functor;
  1491   };
  1492 
  1493   /// \brief Writable bool map for filling each \c true assigned element with a 
  1494   /// given value.
  1495   ///
  1496   /// Writable bool map for filling each \c true assigned element with a 
  1497   /// given value. The value can set the container.
  1498   ///
  1499   /// The following code finds the connected components of a graph
  1500   /// and stores it in the \c comp map:
  1501   ///\code
  1502   /// typedef Graph::NodeMap<int> ComponentMap;
  1503   /// ComponentMap comp(graph);
  1504   /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
  1505   /// ComponentFillerMap filler(comp, 0);
  1506   ///
  1507   /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
  1508   /// dfs.processedMap(filler);
  1509   /// dfs.init();
  1510   /// for (NodeIt it(graph); it != INVALID; ++it) {
  1511   ///   if (!dfs.reached(it)) {
  1512   ///     dfs.addSource(it);
  1513   ///     dfs.start();
  1514   ///     ++filler.fillValue();
  1515   ///   }
  1516   /// }
  1517   ///\endcode
  1518   template <typename Map>
  1519   class FillBoolMap {
  1520   public:
  1521     typedef typename Map::Key Key;
  1522     typedef bool Value;
  1523 
  1524     /// Constructor
  1525     FillBoolMap(Map& _map, const typename Map::Value& _fill) 
  1526       : map(_map), fill(_fill) {}
  1527 
  1528     /// Constructor
  1529     FillBoolMap(Map& _map) 
  1530       : map(_map), fill() {}
  1531 
  1532     /// Gives back the current fill value
  1533     const typename Map::Value& fillValue() const {
  1534       return fill;
  1535     } 
  1536 
  1537     /// Gives back the current fill value
  1538     typename Map::Value& fillValue() {
  1539       return fill;
  1540     } 
  1541 
  1542     /// Sets the current fill value
  1543     void fillValue(const typename Map::Value& _fill) {
  1544       fill = _fill;
  1545     } 
  1546 
  1547     /// The \c set function of the map
  1548     void set(const Key& key, Value value) {
  1549       if (value) {
  1550 	map.set(key, fill);
  1551       }
  1552     }
  1553     
  1554   private:
  1555     Map& map;
  1556     typename Map::Value fill;
  1557   };
  1558 
  1559 
  1560   /// \brief Writable bool map for storing the sequence number of 
  1561   /// \c true assignments.  
  1562   /// 
  1563   /// Writable bool map that stores for each \c true assigned elements  
  1564   /// the sequence number of this setting.
  1565   /// It makes it easy to calculate the leaving
  1566   /// order of the nodes in the \c Dfs algorithm.
  1567   ///
  1568   ///\code
  1569   /// typedef Digraph::NodeMap<int> OrderMap;
  1570   /// OrderMap order(digraph);
  1571   /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
  1572   /// OrderSetterMap setter(order);
  1573   /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
  1574   /// dfs.processedMap(setter);
  1575   /// dfs.init();
  1576   /// for (NodeIt it(digraph); it != INVALID; ++it) {
  1577   ///   if (!dfs.reached(it)) {
  1578   ///     dfs.addSource(it);
  1579   ///     dfs.start();
  1580   ///   }
  1581   /// }
  1582   ///\endcode
  1583   ///
  1584   /// The storing of the discovering order is more difficult because the
  1585   /// ReachedMap should be readable in the dfs algorithm but the setting
  1586   /// order map is not readable. Thus we must use the fork map:
  1587   ///
  1588   ///\code
  1589   /// typedef Digraph::NodeMap<int> OrderMap;
  1590   /// OrderMap order(digraph);
  1591   /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
  1592   /// OrderSetterMap setter(order);
  1593   /// typedef Digraph::NodeMap<bool> StoreMap;
  1594   /// StoreMap store(digraph);
  1595   ///
  1596   /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
  1597   /// ReachedMap reached(store, setter);
  1598   ///
  1599   /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
  1600   /// dfs.reachedMap(reached);
  1601   /// dfs.init();
  1602   /// for (NodeIt it(digraph); it != INVALID; ++it) {
  1603   ///   if (!dfs.reached(it)) {
  1604   ///     dfs.addSource(it);
  1605   ///     dfs.start();
  1606   ///   }
  1607   /// }
  1608   ///\endcode
  1609   template <typename Map>
  1610   class SettingOrderBoolMap {
  1611   public:
  1612     typedef typename Map::Key Key;
  1613     typedef bool Value;
  1614 
  1615     /// Constructor
  1616     SettingOrderBoolMap(Map& _map) 
  1617       : map(_map), counter(0) {}
  1618 
  1619     /// Number of set operations.
  1620     int num() const {
  1621       return counter;
  1622     }
  1623 
  1624     /// The \c set function of the map
  1625     void set(const Key& key, Value value) {
  1626       if (value) {
  1627 	map.set(key, counter++);
  1628       }
  1629     }
  1630     
  1631   private:
  1632     Map& map;
  1633     int counter;
  1634   };
  1635 
  1636   /// @}
  1637 }
  1638 
  1639 #endif // LEMON_MAPS_H