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