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