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