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