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