lemon/maps.h
author Balazs Dezso <deba@inf.elte.hu>
Thu, 03 Jul 2008 12:40:04 +0200
changeset 188 70694e6bdcac
parent 159 c7d30f7810e5
child 209 765619b7cbb2
permissions -rw-r--r--
New skip*() functions in (Dig|G)raphReader
     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. It provides the necessary type definitions
    43   /// required by the map %concepts.
    44   template<typename K, typename V>
    45   class MapBase {
    46   public:
    47     /// \biref The key type of the map.
    48     typedef K Key;
    49     /// \brief The value type of the map.
    50     /// (The type of objects associated with the keys).
    51     typedef V Value;
    52   };
    53 
    54 
    55   /// Null map. (a.k.a. DoNothingMap)
    56 
    57   /// This map can be used if you have to provide a map only for
    58   /// its type definitions, or if you have to provide a writable map,
    59   /// but data written to it is not required (i.e. it will be sent to
    60   /// <tt>/dev/null</tt>).
    61   /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    62   ///
    63   /// \sa ConstMap
    64   template<typename K, typename V>
    65   class NullMap : public MapBase<K, V> {
    66   public:
    67     typedef MapBase<K, V> Parent;
    68     typedef typename Parent::Key Key;
    69     typedef typename Parent::Value Value;
    70 
    71     /// Gives back a default constructed element.
    72     Value operator[](const Key&) const { return Value(); }
    73     /// Absorbs the value.
    74     void set(const Key&, const Value&) {}
    75   };
    76 
    77   /// Returns a \ref NullMap class
    78 
    79   /// This function just returns a \ref NullMap class.
    80   /// \relates NullMap
    81   template <typename K, typename V>
    82   NullMap<K, V> nullMap() {
    83     return NullMap<K, V>();
    84   }
    85 
    86 
    87   /// Constant map.
    88 
    89   /// This \ref concepts::ReadMap "readable map" assigns a specified
    90   /// value to each key.
    91   ///
    92   /// In other aspects it is equivalent to \ref NullMap.
    93   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
    94   /// concept, but it absorbs the data written to it.
    95   ///
    96   /// The simplest way of using this map is through the constMap()
    97   /// function.
    98   ///
    99   /// \sa NullMap
   100   /// \sa IdentityMap
   101   template<typename K, typename V>
   102   class ConstMap : public MapBase<K, V> {
   103   private:
   104     V _value;
   105   public:
   106     typedef MapBase<K, V> Parent;
   107     typedef typename Parent::Key Key;
   108     typedef typename Parent::Value Value;
   109 
   110     /// Default constructor
   111 
   112     /// Default constructor.
   113     /// The value of the map will be default constructed.
   114     ConstMap() {}
   115 
   116     /// Constructor with specified initial value
   117 
   118     /// Constructor with specified initial value.
   119     /// \param v The initial value of the map.
   120     ConstMap(const Value &v) : _value(v) {}
   121 
   122     /// Gives back the specified value.
   123     Value operator[](const Key&) const { return _value; }
   124 
   125     /// Absorbs the value.
   126     void set(const Key&, const Value&) {}
   127 
   128     /// Sets the value that is assigned to each key.
   129     void setAll(const Value &v) {
   130       _value = v;
   131     }
   132 
   133     template<typename V1>
   134     ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
   135   };
   136 
   137   /// Returns a \ref ConstMap class
   138 
   139   /// This function just returns a \ref ConstMap class.
   140   /// \relates ConstMap
   141   template<typename K, typename V>
   142   inline ConstMap<K, V> constMap(const V &v) {
   143     return ConstMap<K, V>(v);
   144   }
   145 
   146   template<typename K, typename V>
   147   inline ConstMap<K, V> constMap() {
   148     return ConstMap<K, V>();
   149   }
   150 
   151 
   152   template<typename T, T v>
   153   struct Const {};
   154 
   155   /// Constant map with inlined constant value.
   156 
   157   /// This \ref concepts::ReadMap "readable map" assigns a specified
   158   /// value to each key.
   159   ///
   160   /// In other aspects it is equivalent to \ref NullMap.
   161   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
   162   /// concept, but it absorbs the data written to it.
   163   ///
   164   /// The simplest way of using this map is through the constMap()
   165   /// function.
   166   ///
   167   /// \sa NullMap
   168   /// \sa IdentityMap
   169   template<typename K, typename V, V v>
   170   class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
   171   public:
   172     typedef MapBase<K, V> Parent;
   173     typedef typename Parent::Key Key;
   174     typedef typename Parent::Value Value;
   175 
   176     /// Constructor.
   177     ConstMap() {}
   178 
   179     /// Gives back the specified value.
   180     Value operator[](const Key&) const { return v; }
   181 
   182     /// Absorbs the value.
   183     void set(const Key&, const Value&) {}
   184   };
   185 
   186   /// Returns a \ref ConstMap class with inlined constant value
   187 
   188   /// This function just returns a \ref ConstMap class with inlined
   189   /// constant value.
   190   /// \relates ConstMap
   191   template<typename K, typename V, V v>
   192   inline ConstMap<K, Const<V, v> > constMap() {
   193     return ConstMap<K, Const<V, v> >();
   194   }
   195 
   196 
   197   /// Identity map.
   198 
   199   /// This \ref concepts::ReadMap "read-only map" gives back the given
   200   /// key as value without any modification.
   201   ///
   202   /// \sa ConstMap
   203   template <typename T>
   204   class IdentityMap : public MapBase<T, T> {
   205   public:
   206     typedef MapBase<T, T> Parent;
   207     typedef typename Parent::Key Key;
   208     typedef typename Parent::Value Value;
   209 
   210     /// Gives back the given value without any modification.
   211     Value operator[](const Key &k) const {
   212       return k;
   213     }
   214   };
   215 
   216   /// Returns an \ref IdentityMap class
   217 
   218   /// This function just returns an \ref IdentityMap class.
   219   /// \relates IdentityMap
   220   template<typename T>
   221   inline IdentityMap<T> identityMap() {
   222     return IdentityMap<T>();
   223   }
   224 
   225 
   226   /// \brief Map for storing values for integer keys from the range
   227   /// <tt>[0..size-1]</tt>.
   228   ///
   229   /// This map is essentially a wrapper for \c std::vector. It assigns
   230   /// values to integer keys from the range <tt>[0..size-1]</tt>.
   231   /// It can be used with some data structures, for example
   232   /// \ref UnionFind, \ref BinHeap, when the used items are small
   233   /// integers. This map conforms the \ref concepts::ReferenceMap
   234   /// "ReferenceMap" concept.
   235   ///
   236   /// The simplest way of using this map is through the rangeMap()
   237   /// function.
   238   template <typename V>
   239   class RangeMap : public MapBase<int, V> {
   240     template <typename V1>
   241     friend class RangeMap;
   242   private:
   243 
   244     typedef std::vector<V> Vector;
   245     Vector _vector;
   246 
   247   public:
   248 
   249     typedef MapBase<int, V> Parent;
   250     /// Key type
   251     typedef typename Parent::Key Key;
   252     /// Value type
   253     typedef typename Parent::Value Value;
   254     /// Reference type
   255     typedef typename Vector::reference Reference;
   256     /// Const reference type
   257     typedef typename Vector::const_reference ConstReference;
   258 
   259     typedef True ReferenceMapTag;
   260 
   261   public:
   262 
   263     /// Constructor with specified default value.
   264     RangeMap(int size = 0, const Value &value = Value())
   265       : _vector(size, value) {}
   266 
   267     /// Constructs the map from an appropriate \c std::vector.
   268     template <typename V1>
   269     RangeMap(const std::vector<V1>& vector)
   270       : _vector(vector.begin(), vector.end()) {}
   271 
   272     /// Constructs the map from another \ref RangeMap.
   273     template <typename V1>
   274     RangeMap(const RangeMap<V1> &c)
   275       : _vector(c._vector.begin(), c._vector.end()) {}
   276 
   277     /// Returns the size of the map.
   278     int size() {
   279       return _vector.size();
   280     }
   281 
   282     /// Resizes the map.
   283 
   284     /// Resizes the underlying \c std::vector container, so changes the
   285     /// keyset of the map.
   286     /// \param size The new size of the map. The new keyset will be the
   287     /// range <tt>[0..size-1]</tt>.
   288     /// \param value The default value to assign to the new keys.
   289     void resize(int size, const Value &value = Value()) {
   290       _vector.resize(size, value);
   291     }
   292 
   293   private:
   294 
   295     RangeMap& operator=(const RangeMap&);
   296 
   297   public:
   298 
   299     ///\e
   300     Reference operator[](const Key &k) {
   301       return _vector[k];
   302     }
   303 
   304     ///\e
   305     ConstReference operator[](const Key &k) const {
   306       return _vector[k];
   307     }
   308 
   309     ///\e
   310     void set(const Key &k, const Value &v) {
   311       _vector[k] = v;
   312     }
   313   };
   314 
   315   /// Returns a \ref RangeMap class
   316 
   317   /// This function just returns a \ref RangeMap class.
   318   /// \relates RangeMap
   319   template<typename V>
   320   inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
   321     return RangeMap<V>(size, value);
   322   }
   323 
   324   /// \brief Returns a \ref RangeMap class created from an appropriate
   325   /// \c std::vector
   326 
   327   /// This function just returns a \ref RangeMap class created from an
   328   /// appropriate \c std::vector.
   329   /// \relates RangeMap
   330   template<typename V>
   331   inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
   332     return RangeMap<V>(vector);
   333   }
   334 
   335 
   336   /// Map type based on \c std::map
   337 
   338   /// This map is essentially a wrapper for \c std::map with addition
   339   /// that you can specify a default value for the keys that are not
   340   /// stored actually. This value can be different from the default
   341   /// contructed value (i.e. \c %Value()).
   342   /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
   343   /// concept.
   344   ///
   345   /// This map is useful if a default value should be assigned to most of
   346   /// the keys and different values should be assigned only to a few
   347   /// keys (i.e. the map is "sparse").
   348   /// The name of this type also refers to this important usage.
   349   ///
   350   /// Apart form that this map can be used in many other cases since it
   351   /// is based on \c std::map, which is a general associative container.
   352   /// However keep in mind that it is usually not as efficient as other
   353   /// maps.
   354   ///
   355   /// The simplest way of using this map is through the sparseMap()
   356   /// function.
   357   template <typename K, typename V, typename Compare = std::less<K> >
   358   class SparseMap : public MapBase<K, V> {
   359     template <typename K1, typename V1, typename C1>
   360     friend class SparseMap;
   361   public:
   362 
   363     typedef MapBase<K, V> Parent;
   364     /// Key type
   365     typedef typename Parent::Key Key;
   366     /// Value type
   367     typedef typename Parent::Value Value;
   368     /// Reference type
   369     typedef Value& Reference;
   370     /// Const reference type
   371     typedef const Value& ConstReference;
   372 
   373     typedef True ReferenceMapTag;
   374 
   375   private:
   376 
   377     typedef std::map<K, V, Compare> Map;
   378     Map _map;
   379     Value _value;
   380 
   381   public:
   382 
   383     /// \brief Constructor with specified default value.
   384     SparseMap(const Value &value = Value()) : _value(value) {}
   385     /// \brief Constructs the map from an appropriate \c std::map, and
   386     /// explicitly specifies a default value.
   387     template <typename V1, typename Comp1>
   388     SparseMap(const std::map<Key, V1, Comp1> &map,
   389               const Value &value = Value())
   390       : _map(map.begin(), map.end()), _value(value) {}
   391 
   392     /// \brief Constructs the map from another \ref SparseMap.
   393     template<typename V1, typename Comp1>
   394     SparseMap(const SparseMap<Key, V1, Comp1> &c)
   395       : _map(c._map.begin(), c._map.end()), _value(c._value) {}
   396 
   397   private:
   398 
   399     SparseMap& operator=(const SparseMap&);
   400 
   401   public:
   402 
   403     ///\e
   404     Reference operator[](const Key &k) {
   405       typename Map::iterator it = _map.lower_bound(k);
   406       if (it != _map.end() && !_map.key_comp()(k, it->first))
   407 	return it->second;
   408       else
   409 	return _map.insert(it, std::make_pair(k, _value))->second;
   410     }
   411 
   412     ///\e
   413     ConstReference operator[](const Key &k) const {
   414       typename Map::const_iterator it = _map.find(k);
   415       if (it != _map.end())
   416 	return it->second;
   417       else
   418 	return _value;
   419     }
   420 
   421     ///\e
   422     void set(const Key &k, const Value &v) {
   423       typename Map::iterator it = _map.lower_bound(k);
   424       if (it != _map.end() && !_map.key_comp()(k, it->first))
   425 	it->second = v;
   426       else
   427 	_map.insert(it, std::make_pair(k, v));
   428     }
   429 
   430     ///\e
   431     void setAll(const Value &v) {
   432       _value = v;
   433       _map.clear();
   434     }
   435   };
   436 
   437   /// Returns a \ref SparseMap class
   438 
   439   /// This function just returns a \ref SparseMap class with specified
   440   /// default value.
   441   /// \relates SparseMap
   442   template<typename K, typename V, typename Compare>
   443   inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
   444     return SparseMap<K, V, Compare>(value);
   445   }
   446 
   447   template<typename K, typename V>
   448   inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
   449     return SparseMap<K, V, std::less<K> >(value);
   450   }
   451 
   452   /// \brief Returns a \ref SparseMap class created from an appropriate
   453   /// \c std::map
   454 
   455   /// This function just returns a \ref SparseMap class created from an
   456   /// appropriate \c std::map.
   457   /// \relates SparseMap
   458   template<typename K, typename V, typename Compare>
   459   inline SparseMap<K, V, Compare>
   460     sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
   461   {
   462     return SparseMap<K, V, Compare>(map, value);
   463   }
   464 
   465   /// @}
   466 
   467   /// \addtogroup map_adaptors
   468   /// @{
   469 
   470   /// Composition of two maps
   471 
   472   /// This \ref concepts::ReadMap "read-only map" returns the
   473   /// composition of two given maps. That is to say, if \c m1 is of
   474   /// type \c M1 and \c m2 is of \c M2, then for
   475   /// \code
   476   ///   ComposeMap<M1, M2> cm(m1,m2);
   477   /// \endcode
   478   /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
   479   ///
   480   /// The \c Key type of the map is inherited from \c M2 and the
   481   /// \c Value type is from \c M1.
   482   /// \c M2::Value must be convertible to \c M1::Key.
   483   ///
   484   /// The simplest way of using this map is through the composeMap()
   485   /// function.
   486   ///
   487   /// \sa CombineMap
   488   ///
   489   /// \todo Check the requirements.
   490   template <typename M1, typename M2>
   491   class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
   492     const M1 &_m1;
   493     const M2 &_m2;
   494   public:
   495     typedef MapBase<typename M2::Key, typename M1::Value> Parent;
   496     typedef typename Parent::Key Key;
   497     typedef typename Parent::Value Value;
   498 
   499     /// Constructor
   500     ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   501 
   502     /// \e
   503     typename MapTraits<M1>::ConstReturnValue
   504     operator[](const Key &k) const { return _m1[_m2[k]]; }
   505   };
   506 
   507   /// Returns a \ref ComposeMap class
   508 
   509   /// This function just returns a \ref ComposeMap class.
   510   ///
   511   /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
   512   /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
   513   /// will be equal to <tt>m1[m2[x]]</tt>.
   514   ///
   515   /// \relates ComposeMap
   516   template <typename M1, typename M2>
   517   inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
   518     return ComposeMap<M1, M2>(m1, m2);
   519   }
   520 
   521 
   522   /// Combination of two maps using an STL (binary) functor.
   523 
   524   /// This \ref concepts::ReadMap "read-only map" takes two maps and a
   525   /// binary functor and returns the combination of the two given maps
   526   /// using the functor.
   527   /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
   528   /// and \c f is of \c F, then for
   529   /// \code
   530   ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
   531   /// \endcode
   532   /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
   533   ///
   534   /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
   535   /// must be convertible to \c M2::Key) and the \c Value type is \c V.
   536   /// \c M2::Value and \c M1::Value must be convertible to the
   537   /// corresponding input parameter of \c F and the return type of \c F
   538   /// must be convertible to \c V.
   539   ///
   540   /// The simplest way of using this map is through the combineMap()
   541   /// function.
   542   ///
   543   /// \sa ComposeMap
   544   ///
   545   /// \todo Check the requirements.
   546   template<typename M1, typename M2, typename F,
   547 	   typename V = typename F::result_type>
   548   class CombineMap : public MapBase<typename M1::Key, V> {
   549     const M1 &_m1;
   550     const M2 &_m2;
   551     F _f;
   552   public:
   553     typedef MapBase<typename M1::Key, V> Parent;
   554     typedef typename Parent::Key Key;
   555     typedef typename Parent::Value Value;
   556 
   557     /// Constructor
   558     CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
   559       : _m1(m1), _m2(m2), _f(f) {}
   560     /// \e
   561     Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
   562   };
   563 
   564   /// Returns a \ref CombineMap class
   565 
   566   /// This function just returns a \ref CombineMap class.
   567   ///
   568   /// For example, if \c m1 and \c m2 are both maps with \c double
   569   /// values, then
   570   /// \code
   571   ///   combineMap(m1,m2,std::plus<double>())
   572   /// \endcode
   573   /// is equivalent to
   574   /// \code
   575   ///   addMap(m1,m2)
   576   /// \endcode
   577   ///
   578   /// This function is specialized for adaptable binary function
   579   /// classes and C++ functions.
   580   ///
   581   /// \relates CombineMap
   582   template<typename M1, typename M2, typename F, typename V>
   583   inline CombineMap<M1, M2, F, V>
   584   combineMap(const M1 &m1, const M2 &m2, const F &f) {
   585     return CombineMap<M1, M2, F, V>(m1,m2,f);
   586   }
   587 
   588   template<typename M1, typename M2, typename F>
   589   inline CombineMap<M1, M2, F, typename F::result_type>
   590   combineMap(const M1 &m1, const M2 &m2, const F &f) {
   591     return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
   592   }
   593 
   594   template<typename M1, typename M2, typename K1, typename K2, typename V>
   595   inline CombineMap<M1, M2, V (*)(K1, K2), V>
   596   combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
   597     return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
   598   }
   599 
   600 
   601   /// Converts an STL style (unary) functor to a map
   602 
   603   /// This \ref concepts::ReadMap "read-only map" returns the value
   604   /// of a given functor. Actually, it just wraps the functor and
   605   /// provides the \c Key and \c Value typedefs.
   606   ///
   607   /// Template parameters \c K and \c V will become its \c Key and
   608   /// \c Value. In most cases they have to be given explicitly because
   609   /// a functor typically does not provide \c argument_type and
   610   /// \c result_type typedefs.
   611   /// Parameter \c F is the type of the used functor.
   612   ///
   613   /// The simplest way of using this map is through the functorToMap()
   614   /// function.
   615   ///
   616   /// \sa MapToFunctor
   617   template<typename F,
   618 	   typename K = typename F::argument_type,
   619 	   typename V = typename F::result_type>
   620   class FunctorToMap : public MapBase<K, V> {
   621     F _f;
   622   public:
   623     typedef MapBase<K, V> Parent;
   624     typedef typename Parent::Key Key;
   625     typedef typename Parent::Value Value;
   626 
   627     /// Constructor
   628     FunctorToMap(const F &f = F()) : _f(f) {}
   629     /// \e
   630     Value operator[](const Key &k) const { return _f(k); }
   631   };
   632 
   633   /// Returns a \ref FunctorToMap class
   634 
   635   /// This function just returns a \ref FunctorToMap class.
   636   ///
   637   /// This function is specialized for adaptable binary function
   638   /// classes and C++ functions.
   639   ///
   640   /// \relates FunctorToMap
   641   template<typename K, typename V, typename F>
   642   inline FunctorToMap<F, K, V> functorToMap(const F &f) {
   643     return FunctorToMap<F, K, V>(f);
   644   }
   645 
   646   template <typename F>
   647   inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
   648     functorToMap(const F &f)
   649   {
   650     return FunctorToMap<F, typename F::argument_type,
   651       typename F::result_type>(f);
   652   }
   653 
   654   template <typename K, typename V>
   655   inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
   656     return FunctorToMap<V (*)(K), K, V>(f);
   657   }
   658 
   659 
   660   /// Converts a map to an STL style (unary) functor
   661 
   662   /// This class converts a map to an STL style (unary) functor.
   663   /// That is it provides an <tt>operator()</tt> to read its values.
   664   ///
   665   /// For the sake of convenience it also works as a usual
   666   /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
   667   /// and the \c Key and \c Value typedefs also exist.
   668   ///
   669   /// The simplest way of using this map is through the mapToFunctor()
   670   /// function.
   671   ///
   672   ///\sa FunctorToMap
   673   template <typename M>
   674   class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
   675     const M &_m;
   676   public:
   677     typedef MapBase<typename M::Key, typename M::Value> Parent;
   678     typedef typename Parent::Key Key;
   679     typedef typename Parent::Value Value;
   680 
   681     typedef typename Parent::Key argument_type;
   682     typedef typename Parent::Value result_type;
   683 
   684     /// Constructor
   685     MapToFunctor(const M &m) : _m(m) {}
   686     /// \e
   687     Value operator()(const Key &k) const { return _m[k]; }
   688     /// \e
   689     Value operator[](const Key &k) const { return _m[k]; }
   690   };
   691 
   692   /// Returns a \ref MapToFunctor class
   693 
   694   /// This function just returns a \ref MapToFunctor class.
   695   /// \relates MapToFunctor
   696   template<typename M>
   697   inline MapToFunctor<M> mapToFunctor(const M &m) {
   698     return MapToFunctor<M>(m);
   699   }
   700 
   701 
   702   /// \brief Map adaptor to convert the \c Value type of a map to
   703   /// another type using the default conversion.
   704 
   705   /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
   706   /// "readable map" to another type using the default conversion.
   707   /// The \c Key type of it is inherited from \c M and the \c Value
   708   /// type is \c V.
   709   /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
   710   ///
   711   /// The simplest way of using this map is through the convertMap()
   712   /// function.
   713   template <typename M, typename V>
   714   class ConvertMap : public MapBase<typename M::Key, V> {
   715     const M &_m;
   716   public:
   717     typedef MapBase<typename M::Key, V> Parent;
   718     typedef typename Parent::Key Key;
   719     typedef typename Parent::Value Value;
   720 
   721     /// Constructor
   722 
   723     /// Constructor.
   724     /// \param m The underlying map.
   725     ConvertMap(const M &m) : _m(m) {}
   726 
   727     /// \e
   728     Value operator[](const Key &k) const { return _m[k]; }
   729   };
   730 
   731   /// Returns a \ref ConvertMap class
   732 
   733   /// This function just returns a \ref ConvertMap class.
   734   /// \relates ConvertMap
   735   template<typename V, typename M>
   736   inline ConvertMap<M, V> convertMap(const M &map) {
   737     return ConvertMap<M, V>(map);
   738   }
   739 
   740 
   741   /// Applies all map setting operations to two maps
   742 
   743   /// This map has two \ref concepts::WriteMap "writable map" parameters
   744   /// and each write request will be passed to both of them.
   745   /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
   746   /// operations will return the corresponding values of \c M1.
   747   ///
   748   /// The \c Key and \c Value types are inherited from \c M1.
   749   /// The \c Key and \c Value of \c M2 must be convertible from those
   750   /// of \c M1.
   751   ///
   752   /// The simplest way of using this map is through the forkMap()
   753   /// function.
   754   template<typename  M1, typename M2>
   755   class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
   756     M1 &_m1;
   757     M2 &_m2;
   758   public:
   759     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   760     typedef typename Parent::Key Key;
   761     typedef typename Parent::Value Value;
   762 
   763     /// Constructor
   764     ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
   765     /// Returns the value associated with the given key in the first map.
   766     Value operator[](const Key &k) const { return _m1[k]; }
   767     /// Sets the value associated with the given key in both maps.
   768     void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
   769   };
   770 
   771   /// Returns a \ref ForkMap class
   772 
   773   /// This function just returns a \ref ForkMap class.
   774   /// \relates ForkMap
   775   template <typename M1, typename M2>
   776   inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
   777     return ForkMap<M1,M2>(m1,m2);
   778   }
   779 
   780 
   781   /// Sum of two maps
   782 
   783   /// This \ref concepts::ReadMap "read-only map" returns the sum
   784   /// of the values of the two given maps.
   785   /// Its \c Key and \c Value types are inherited from \c M1.
   786   /// The \c Key and \c Value of \c M2 must be convertible to those of
   787   /// \c M1.
   788   ///
   789   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
   790   /// \code
   791   ///   AddMap<M1,M2> am(m1,m2);
   792   /// \endcode
   793   /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
   794   ///
   795   /// The simplest way of using this map is through the addMap()
   796   /// function.
   797   ///
   798   /// \sa SubMap, MulMap, DivMap
   799   /// \sa ShiftMap, ShiftWriteMap
   800   template<typename M1, typename M2>
   801   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   802     const M1 &_m1;
   803     const M2 &_m2;
   804   public:
   805     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   806     typedef typename Parent::Key Key;
   807     typedef typename Parent::Value Value;
   808 
   809     /// Constructor
   810     AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   811     /// \e
   812     Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
   813   };
   814 
   815   /// Returns an \ref AddMap class
   816 
   817   /// This function just returns an \ref AddMap class.
   818   ///
   819   /// For example, if \c m1 and \c m2 are both maps with \c double
   820   /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
   821   /// <tt>m1[x]+m2[x]</tt>.
   822   ///
   823   /// \relates AddMap
   824   template<typename M1, typename M2>
   825   inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
   826     return AddMap<M1, M2>(m1,m2);
   827   }
   828 
   829 
   830   /// Difference of two maps
   831 
   832   /// This \ref concepts::ReadMap "read-only map" returns the difference
   833   /// of the values of the two given maps.
   834   /// Its \c Key and \c Value types are inherited from \c M1.
   835   /// The \c Key and \c Value of \c M2 must be convertible to those of
   836   /// \c M1.
   837   ///
   838   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
   839   /// \code
   840   ///   SubMap<M1,M2> sm(m1,m2);
   841   /// \endcode
   842   /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
   843   ///
   844   /// The simplest way of using this map is through the subMap()
   845   /// function.
   846   ///
   847   /// \sa AddMap, MulMap, DivMap
   848   template<typename M1, typename M2>
   849   class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
   850     const M1 &_m1;
   851     const M2 &_m2;
   852   public:
   853     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   854     typedef typename Parent::Key Key;
   855     typedef typename Parent::Value Value;
   856 
   857     /// Constructor
   858     SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   859     /// \e
   860     Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
   861   };
   862 
   863   /// Returns a \ref SubMap class
   864 
   865   /// This function just returns a \ref SubMap class.
   866   ///
   867   /// For example, if \c m1 and \c m2 are both maps with \c double
   868   /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
   869   /// <tt>m1[x]-m2[x]</tt>.
   870   ///
   871   /// \relates SubMap
   872   template<typename M1, typename M2>
   873   inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
   874     return SubMap<M1, M2>(m1,m2);
   875   }
   876 
   877 
   878   /// Product of two maps
   879 
   880   /// This \ref concepts::ReadMap "read-only map" returns the product
   881   /// of the values of the two given maps.
   882   /// Its \c Key and \c Value types are inherited from \c M1.
   883   /// The \c Key and \c Value of \c M2 must be convertible to those of
   884   /// \c M1.
   885   ///
   886   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
   887   /// \code
   888   ///   MulMap<M1,M2> mm(m1,m2);
   889   /// \endcode
   890   /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
   891   ///
   892   /// The simplest way of using this map is through the mulMap()
   893   /// function.
   894   ///
   895   /// \sa AddMap, SubMap, DivMap
   896   /// \sa ScaleMap, ScaleWriteMap
   897   template<typename M1, typename M2>
   898   class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
   899     const M1 &_m1;
   900     const M2 &_m2;
   901   public:
   902     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   903     typedef typename Parent::Key Key;
   904     typedef typename Parent::Value Value;
   905 
   906     /// Constructor
   907     MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   908     /// \e
   909     Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
   910   };
   911 
   912   /// Returns a \ref MulMap class
   913 
   914   /// This function just returns a \ref MulMap class.
   915   ///
   916   /// For example, if \c m1 and \c m2 are both maps with \c double
   917   /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
   918   /// <tt>m1[x]*m2[x]</tt>.
   919   ///
   920   /// \relates MulMap
   921   template<typename M1, typename M2>
   922   inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
   923     return MulMap<M1, M2>(m1,m2);
   924   }
   925 
   926 
   927   /// Quotient of two maps
   928 
   929   /// This \ref concepts::ReadMap "read-only map" returns the quotient
   930   /// of the values of the two given maps.
   931   /// Its \c Key and \c Value types are inherited from \c M1.
   932   /// The \c Key and \c Value of \c M2 must be convertible to those of
   933   /// \c M1.
   934   ///
   935   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
   936   /// \code
   937   ///   DivMap<M1,M2> dm(m1,m2);
   938   /// \endcode
   939   /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
   940   ///
   941   /// The simplest way of using this map is through the divMap()
   942   /// function.
   943   ///
   944   /// \sa AddMap, SubMap, MulMap
   945   template<typename M1, typename M2>
   946   class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
   947     const M1 &_m1;
   948     const M2 &_m2;
   949   public:
   950     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
   951     typedef typename Parent::Key Key;
   952     typedef typename Parent::Value Value;
   953 
   954     /// Constructor
   955     DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   956     /// \e
   957     Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
   958   };
   959 
   960   /// Returns a \ref DivMap class
   961 
   962   /// This function just returns a \ref DivMap class.
   963   ///
   964   /// For example, if \c m1 and \c m2 are both maps with \c double
   965   /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
   966   /// <tt>m1[x]/m2[x]</tt>.
   967   ///
   968   /// \relates DivMap
   969   template<typename M1, typename M2>
   970   inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
   971     return DivMap<M1, M2>(m1,m2);
   972   }
   973 
   974 
   975   /// Shifts a map with a constant.
   976 
   977   /// This \ref concepts::ReadMap "read-only map" returns the sum of
   978   /// the given map and a constant value (i.e. it shifts the map with
   979   /// the constant). Its \c Key and \c Value are inherited from \c M.
   980   ///
   981   /// Actually,
   982   /// \code
   983   ///   ShiftMap<M> sh(m,v);
   984   /// \endcode
   985   /// is equivalent to
   986   /// \code
   987   ///   ConstMap<M::Key, M::Value> cm(v);
   988   ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
   989   /// \endcode
   990   ///
   991   /// The simplest way of using this map is through the shiftMap()
   992   /// function.
   993   ///
   994   /// \sa ShiftWriteMap
   995   template<typename M, typename C = typename M::Value>
   996   class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
   997     const M &_m;
   998     C _v;
   999   public:
  1000     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1001     typedef typename Parent::Key Key;
  1002     typedef typename Parent::Value Value;
  1003 
  1004     /// Constructor
  1005 
  1006     /// Constructor.
  1007     /// \param m The undelying map.
  1008     /// \param v The constant value.
  1009     ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
  1010     /// \e
  1011     Value operator[](const Key &k) const { return _m[k]+_v; }
  1012   };
  1013 
  1014   /// Shifts a map with a constant (read-write version).
  1015 
  1016   /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
  1017   /// of the given map and a constant value (i.e. it shifts the map with
  1018   /// the constant). Its \c Key and \c Value are inherited from \c M.
  1019   /// It makes also possible to write the map.
  1020   ///
  1021   /// The simplest way of using this map is through the shiftWriteMap()
  1022   /// function.
  1023   ///
  1024   /// \sa ShiftMap
  1025   template<typename M, typename C = typename M::Value>
  1026   class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1027     M &_m;
  1028     C _v;
  1029   public:
  1030     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1031     typedef typename Parent::Key Key;
  1032     typedef typename Parent::Value Value;
  1033 
  1034     /// Constructor
  1035 
  1036     /// Constructor.
  1037     /// \param m The undelying map.
  1038     /// \param v The constant value.
  1039     ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  1040     /// \e
  1041     Value operator[](const Key &k) const { return _m[k]+_v; }
  1042     /// \e
  1043     void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
  1044   };
  1045 
  1046   /// Returns a \ref ShiftMap class
  1047 
  1048   /// This function just returns a \ref ShiftMap class.
  1049   ///
  1050   /// For example, if \c m is a map with \c double values and \c v is
  1051   /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
  1052   /// <tt>m[x]+v</tt>.
  1053   ///
  1054   /// \relates ShiftMap
  1055   template<typename M, typename C>
  1056   inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
  1057     return ShiftMap<M, C>(m,v);
  1058   }
  1059 
  1060   /// Returns a \ref ShiftWriteMap class
  1061 
  1062   /// This function just returns a \ref ShiftWriteMap class.
  1063   ///
  1064   /// For example, if \c m is a map with \c double values and \c v is
  1065   /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
  1066   /// <tt>m[x]+v</tt>.
  1067   /// Moreover it makes also possible to write the map.
  1068   ///
  1069   /// \relates ShiftWriteMap
  1070   template<typename M, typename C>
  1071   inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
  1072     return ShiftWriteMap<M, C>(m,v);
  1073   }
  1074 
  1075 
  1076   /// Scales a map with a constant.
  1077 
  1078   /// This \ref concepts::ReadMap "read-only map" returns the value of
  1079   /// the given map multiplied from the left side with a constant value.
  1080   /// Its \c Key and \c Value are inherited from \c M.
  1081   ///
  1082   /// Actually,
  1083   /// \code
  1084   ///   ScaleMap<M> sc(m,v);
  1085   /// \endcode
  1086   /// is equivalent to
  1087   /// \code
  1088   ///   ConstMap<M::Key, M::Value> cm(v);
  1089   ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
  1090   /// \endcode
  1091   ///
  1092   /// The simplest way of using this map is through the scaleMap()
  1093   /// function.
  1094   ///
  1095   /// \sa ScaleWriteMap
  1096   template<typename M, typename C = typename M::Value>
  1097   class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
  1098     const M &_m;
  1099     C _v;
  1100   public:
  1101     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1102     typedef typename Parent::Key Key;
  1103     typedef typename Parent::Value Value;
  1104 
  1105     /// Constructor
  1106 
  1107     /// Constructor.
  1108     /// \param m The undelying map.
  1109     /// \param v The constant value.
  1110     ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
  1111     /// \e
  1112     Value operator[](const Key &k) const { return _v*_m[k]; }
  1113   };
  1114 
  1115   /// Scales a map with a constant (read-write version).
  1116 
  1117   /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
  1118   /// the given map multiplied from the left side with a constant value.
  1119   /// Its \c Key and \c Value are inherited from \c M.
  1120   /// It can also be used as write map if the \c / operator is defined
  1121   /// between \c Value and \c C and the given multiplier is not zero.
  1122   ///
  1123   /// The simplest way of using this map is through the scaleWriteMap()
  1124   /// function.
  1125   ///
  1126   /// \sa ScaleMap
  1127   template<typename M, typename C = typename M::Value>
  1128   class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1129     M &_m;
  1130     C _v;
  1131   public:
  1132     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1133     typedef typename Parent::Key Key;
  1134     typedef typename Parent::Value Value;
  1135 
  1136     /// Constructor
  1137 
  1138     /// Constructor.
  1139     /// \param m The undelying map.
  1140     /// \param v The constant value.
  1141     ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  1142     /// \e
  1143     Value operator[](const Key &k) const { return _v*_m[k]; }
  1144     /// \e
  1145     void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
  1146   };
  1147 
  1148   /// Returns a \ref ScaleMap class
  1149 
  1150   /// This function just returns a \ref ScaleMap class.
  1151   ///
  1152   /// For example, if \c m is a map with \c double values and \c v is
  1153   /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
  1154   /// <tt>v*m[x]</tt>.
  1155   ///
  1156   /// \relates ScaleMap
  1157   template<typename M, typename C>
  1158   inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
  1159     return ScaleMap<M, C>(m,v);
  1160   }
  1161 
  1162   /// Returns a \ref ScaleWriteMap class
  1163 
  1164   /// This function just returns a \ref ScaleWriteMap class.
  1165   ///
  1166   /// For example, if \c m is a map with \c double values and \c v is
  1167   /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
  1168   /// <tt>v*m[x]</tt>.
  1169   /// Moreover it makes also possible to write the map.
  1170   ///
  1171   /// \relates ScaleWriteMap
  1172   template<typename M, typename C>
  1173   inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
  1174     return ScaleWriteMap<M, C>(m,v);
  1175   }
  1176 
  1177 
  1178   /// Negative of a map
  1179 
  1180   /// This \ref concepts::ReadMap "read-only map" returns the negative
  1181   /// of the values of the given map (using the unary \c - operator).
  1182   /// Its \c Key and \c Value are inherited from \c M.
  1183   ///
  1184   /// If M::Value is \c int, \c double etc., then
  1185   /// \code
  1186   ///   NegMap<M> neg(m);
  1187   /// \endcode
  1188   /// is equivalent to
  1189   /// \code
  1190   ///   ScaleMap<M> neg(m,-1);
  1191   /// \endcode
  1192   ///
  1193   /// The simplest way of using this map is through the negMap()
  1194   /// function.
  1195   ///
  1196   /// \sa NegWriteMap
  1197   template<typename M>
  1198   class NegMap : public MapBase<typename M::Key, typename M::Value> {
  1199     const M& _m;
  1200   public:
  1201     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1202     typedef typename Parent::Key Key;
  1203     typedef typename Parent::Value Value;
  1204 
  1205     /// Constructor
  1206     NegMap(const M &m) : _m(m) {}
  1207     /// \e
  1208     Value operator[](const Key &k) const { return -_m[k]; }
  1209   };
  1210 
  1211   /// Negative of a map (read-write version)
  1212 
  1213   /// This \ref concepts::ReadWriteMap "read-write map" returns the
  1214   /// negative of the values of the given map (using the unary \c -
  1215   /// operator).
  1216   /// Its \c Key and \c Value are inherited from \c M.
  1217   /// It makes also possible to write the map.
  1218   ///
  1219   /// If M::Value is \c int, \c double etc., then
  1220   /// \code
  1221   ///   NegWriteMap<M> neg(m);
  1222   /// \endcode
  1223   /// is equivalent to
  1224   /// \code
  1225   ///   ScaleWriteMap<M> neg(m,-1);
  1226   /// \endcode
  1227   ///
  1228   /// The simplest way of using this map is through the negWriteMap()
  1229   /// function.
  1230   ///
  1231   /// \sa NegMap
  1232   template<typename M>
  1233   class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
  1234     M &_m;
  1235   public:
  1236     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1237     typedef typename Parent::Key Key;
  1238     typedef typename Parent::Value Value;
  1239 
  1240     /// Constructor
  1241     NegWriteMap(M &m) : _m(m) {}
  1242     /// \e
  1243     Value operator[](const Key &k) const { return -_m[k]; }
  1244     /// \e
  1245     void set(const Key &k, const Value &v) { _m.set(k, -v); }
  1246   };
  1247 
  1248   /// Returns a \ref NegMap class
  1249 
  1250   /// This function just returns a \ref NegMap class.
  1251   ///
  1252   /// For example, if \c m is a map with \c double values, then
  1253   /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
  1254   ///
  1255   /// \relates NegMap
  1256   template <typename M>
  1257   inline NegMap<M> negMap(const M &m) {
  1258     return NegMap<M>(m);
  1259   }
  1260 
  1261   /// Returns a \ref NegWriteMap class
  1262 
  1263   /// This function just returns a \ref NegWriteMap class.
  1264   ///
  1265   /// For example, if \c m is a map with \c double values, then
  1266   /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
  1267   /// Moreover it makes also possible to write the map.
  1268   ///
  1269   /// \relates NegWriteMap
  1270   template <typename M>
  1271   inline NegWriteMap<M> negWriteMap(M &m) {
  1272     return NegWriteMap<M>(m);
  1273   }
  1274 
  1275 
  1276   /// Absolute value of a map
  1277 
  1278   /// This \ref concepts::ReadMap "read-only map" returns the absolute
  1279   /// value of the values of the given map.
  1280   /// Its \c Key and \c Value are inherited from \c M.
  1281   /// \c Value must be comparable to \c 0 and the unary \c -
  1282   /// operator must be defined for it, of course.
  1283   ///
  1284   /// The simplest way of using this map is through the absMap()
  1285   /// function.
  1286   template<typename M>
  1287   class AbsMap : public MapBase<typename M::Key, typename M::Value> {
  1288     const M &_m;
  1289   public:
  1290     typedef MapBase<typename M::Key, typename M::Value> Parent;
  1291     typedef typename Parent::Key Key;
  1292     typedef typename Parent::Value Value;
  1293 
  1294     /// Constructor
  1295     AbsMap(const M &m) : _m(m) {}
  1296     /// \e
  1297     Value operator[](const Key &k) const {
  1298       Value tmp = _m[k];
  1299       return tmp >= 0 ? tmp : -tmp;
  1300     }
  1301 
  1302   };
  1303 
  1304   /// Returns an \ref AbsMap class
  1305 
  1306   /// This function just returns an \ref AbsMap class.
  1307   ///
  1308   /// For example, if \c m is a map with \c double values, then
  1309   /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
  1310   /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
  1311   /// negative.
  1312   ///
  1313   /// \relates AbsMap
  1314   template<typename M>
  1315   inline AbsMap<M> absMap(const M &m) {
  1316     return AbsMap<M>(m);
  1317   }
  1318 
  1319   /// @}
  1320   
  1321   // Logical maps and map adaptors:
  1322 
  1323   /// \addtogroup maps
  1324   /// @{
  1325 
  1326   /// Constant \c true map.
  1327 
  1328   /// This \ref concepts::ReadMap "read-only map" assigns \c true to
  1329   /// each key.
  1330   ///
  1331   /// Note that
  1332   /// \code
  1333   ///   TrueMap<K> tm;
  1334   /// \endcode
  1335   /// is equivalent to
  1336   /// \code
  1337   ///   ConstMap<K,bool> tm(true);
  1338   /// \endcode
  1339   ///
  1340   /// \sa FalseMap
  1341   /// \sa ConstMap
  1342   template <typename K>
  1343   class TrueMap : public MapBase<K, bool> {
  1344   public:
  1345     typedef MapBase<K, bool> Parent;
  1346     typedef typename Parent::Key Key;
  1347     typedef typename Parent::Value Value;
  1348 
  1349     /// Gives back \c true.
  1350     Value operator[](const Key&) const { return true; }
  1351   };
  1352 
  1353   /// Returns a \ref TrueMap class
  1354 
  1355   /// This function just returns a \ref TrueMap class.
  1356   /// \relates TrueMap
  1357   template<typename K>
  1358   inline TrueMap<K> trueMap() {
  1359     return TrueMap<K>();
  1360   }
  1361 
  1362 
  1363   /// Constant \c false map.
  1364 
  1365   /// This \ref concepts::ReadMap "read-only map" assigns \c false to
  1366   /// each key.
  1367   ///
  1368   /// Note that
  1369   /// \code
  1370   ///   FalseMap<K> fm;
  1371   /// \endcode
  1372   /// is equivalent to
  1373   /// \code
  1374   ///   ConstMap<K,bool> fm(false);
  1375   /// \endcode
  1376   ///
  1377   /// \sa TrueMap
  1378   /// \sa ConstMap
  1379   template <typename K>
  1380   class FalseMap : public MapBase<K, bool> {
  1381   public:
  1382     typedef MapBase<K, bool> Parent;
  1383     typedef typename Parent::Key Key;
  1384     typedef typename Parent::Value Value;
  1385 
  1386     /// Gives back \c false.
  1387     Value operator[](const Key&) const { return false; }
  1388   };
  1389 
  1390   /// Returns a \ref FalseMap class
  1391 
  1392   /// This function just returns a \ref FalseMap class.
  1393   /// \relates FalseMap
  1394   template<typename K>
  1395   inline FalseMap<K> falseMap() {
  1396     return FalseMap<K>();
  1397   }
  1398 
  1399   /// @}
  1400 
  1401   /// \addtogroup map_adaptors
  1402   /// @{
  1403 
  1404   /// Logical 'and' of two maps
  1405 
  1406   /// This \ref concepts::ReadMap "read-only map" returns the logical
  1407   /// 'and' of the values of the two given maps.
  1408   /// Its \c Key type is inherited from \c M1 and its \c Value type is
  1409   /// \c bool. \c M2::Key must be convertible to \c M1::Key.
  1410   ///
  1411   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
  1412   /// \code
  1413   ///   AndMap<M1,M2> am(m1,m2);
  1414   /// \endcode
  1415   /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
  1416   ///
  1417   /// The simplest way of using this map is through the andMap()
  1418   /// function.
  1419   ///
  1420   /// \sa OrMap
  1421   /// \sa NotMap, NotWriteMap
  1422   template<typename M1, typename M2>
  1423   class AndMap : public MapBase<typename M1::Key, bool> {
  1424     const M1 &_m1;
  1425     const M2 &_m2;
  1426   public:
  1427     typedef MapBase<typename M1::Key, bool> Parent;
  1428     typedef typename Parent::Key Key;
  1429     typedef typename Parent::Value Value;
  1430 
  1431     /// Constructor
  1432     AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1433     /// \e
  1434     Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
  1435   };
  1436 
  1437   /// Returns an \ref AndMap class
  1438 
  1439   /// This function just returns an \ref AndMap class.
  1440   ///
  1441   /// For example, if \c m1 and \c m2 are both maps with \c bool values,
  1442   /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
  1443   /// <tt>m1[x]&&m2[x]</tt>.
  1444   ///
  1445   /// \relates AndMap
  1446   template<typename M1, typename M2>
  1447   inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
  1448     return AndMap<M1, M2>(m1,m2);
  1449   }
  1450 
  1451 
  1452   /// Logical 'or' of two maps
  1453 
  1454   /// This \ref concepts::ReadMap "read-only map" returns the logical
  1455   /// 'or' of the values of the two given maps.
  1456   /// Its \c Key type is inherited from \c M1 and its \c Value type is
  1457   /// \c bool. \c M2::Key must be convertible to \c M1::Key.
  1458   ///
  1459   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
  1460   /// \code
  1461   ///   OrMap<M1,M2> om(m1,m2);
  1462   /// \endcode
  1463   /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
  1464   ///
  1465   /// The simplest way of using this map is through the orMap()
  1466   /// function.
  1467   ///
  1468   /// \sa AndMap
  1469   /// \sa NotMap, NotWriteMap
  1470   template<typename M1, typename M2>
  1471   class OrMap : public MapBase<typename M1::Key, bool> {
  1472     const M1 &_m1;
  1473     const M2 &_m2;
  1474   public:
  1475     typedef MapBase<typename M1::Key, bool> Parent;
  1476     typedef typename Parent::Key Key;
  1477     typedef typename Parent::Value Value;
  1478 
  1479     /// Constructor
  1480     OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1481     /// \e
  1482     Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
  1483   };
  1484 
  1485   /// Returns an \ref OrMap class
  1486 
  1487   /// This function just returns an \ref OrMap class.
  1488   ///
  1489   /// For example, if \c m1 and \c m2 are both maps with \c bool values,
  1490   /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
  1491   /// <tt>m1[x]||m2[x]</tt>.
  1492   ///
  1493   /// \relates OrMap
  1494   template<typename M1, typename M2>
  1495   inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
  1496     return OrMap<M1, M2>(m1,m2);
  1497   }
  1498 
  1499 
  1500   /// Logical 'not' of a map
  1501 
  1502   /// This \ref concepts::ReadMap "read-only map" returns the logical
  1503   /// negation of the values of the given map.
  1504   /// Its \c Key is inherited from \c M and its \c Value is \c bool.
  1505   ///
  1506   /// The simplest way of using this map is through the notMap()
  1507   /// function.
  1508   ///
  1509   /// \sa NotWriteMap
  1510   template <typename M>
  1511   class NotMap : public MapBase<typename M::Key, bool> {
  1512     const M &_m;
  1513   public:
  1514     typedef MapBase<typename M::Key, bool> Parent;
  1515     typedef typename Parent::Key Key;
  1516     typedef typename Parent::Value Value;
  1517 
  1518     /// Constructor
  1519     NotMap(const M &m) : _m(m) {}
  1520     /// \e
  1521     Value operator[](const Key &k) const { return !_m[k]; }
  1522   };
  1523 
  1524   /// Logical 'not' of a map (read-write version)
  1525 
  1526   /// This \ref concepts::ReadWriteMap "read-write map" returns the
  1527   /// logical negation of the values of the given map.
  1528   /// Its \c Key is inherited from \c M and its \c Value is \c bool.
  1529   /// It makes also possible to write the map. When a value is set,
  1530   /// the opposite value is set to the original map.
  1531   ///
  1532   /// The simplest way of using this map is through the notWriteMap()
  1533   /// function.
  1534   ///
  1535   /// \sa NotMap
  1536   template <typename M>
  1537   class NotWriteMap : public MapBase<typename M::Key, bool> {
  1538     M &_m;
  1539   public:
  1540     typedef MapBase<typename M::Key, bool> Parent;
  1541     typedef typename Parent::Key Key;
  1542     typedef typename Parent::Value Value;
  1543 
  1544     /// Constructor
  1545     NotWriteMap(M &m) : _m(m) {}
  1546     /// \e
  1547     Value operator[](const Key &k) const { return !_m[k]; }
  1548     /// \e
  1549     void set(const Key &k, bool v) { _m.set(k, !v); }
  1550   };
  1551 
  1552   /// Returns a \ref NotMap class
  1553 
  1554   /// This function just returns a \ref NotMap class.
  1555   ///
  1556   /// For example, if \c m is a map with \c bool values, then
  1557   /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
  1558   ///
  1559   /// \relates NotMap
  1560   template <typename M>
  1561   inline NotMap<M> notMap(const M &m) {
  1562     return NotMap<M>(m);
  1563   }
  1564 
  1565   /// Returns a \ref NotWriteMap class
  1566 
  1567   /// This function just returns a \ref NotWriteMap class.
  1568   ///
  1569   /// For example, if \c m is a map with \c bool values, then
  1570   /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
  1571   /// Moreover it makes also possible to write the map.
  1572   ///
  1573   /// \relates NotWriteMap
  1574   template <typename M>
  1575   inline NotWriteMap<M> notWriteMap(M &m) {
  1576     return NotWriteMap<M>(m);
  1577   }
  1578 
  1579 
  1580   /// Combination of two maps using the \c == operator
  1581 
  1582   /// This \ref concepts::ReadMap "read-only map" assigns \c true to
  1583   /// the keys for which the corresponding values of the two maps are
  1584   /// equal.
  1585   /// Its \c Key type is inherited from \c M1 and its \c Value type is
  1586   /// \c bool. \c M2::Key must be convertible to \c M1::Key.
  1587   ///
  1588   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
  1589   /// \code
  1590   ///   EqualMap<M1,M2> em(m1,m2);
  1591   /// \endcode
  1592   /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
  1593   ///
  1594   /// The simplest way of using this map is through the equalMap()
  1595   /// function.
  1596   ///
  1597   /// \sa LessMap
  1598   template<typename M1, typename M2>
  1599   class EqualMap : public MapBase<typename M1::Key, bool> {
  1600     const M1 &_m1;
  1601     const M2 &_m2;
  1602   public:
  1603     typedef MapBase<typename M1::Key, bool> Parent;
  1604     typedef typename Parent::Key Key;
  1605     typedef typename Parent::Value Value;
  1606 
  1607     /// Constructor
  1608     EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1609     /// \e
  1610     Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
  1611   };
  1612 
  1613   /// Returns an \ref EqualMap class
  1614 
  1615   /// This function just returns an \ref EqualMap class.
  1616   ///
  1617   /// For example, if \c m1 and \c m2 are maps with keys and values of
  1618   /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
  1619   /// <tt>m1[x]==m2[x]</tt>.
  1620   ///
  1621   /// \relates EqualMap
  1622   template<typename M1, typename M2>
  1623   inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
  1624     return EqualMap<M1, M2>(m1,m2);
  1625   }
  1626 
  1627 
  1628   /// Combination of two maps using the \c < operator
  1629 
  1630   /// This \ref concepts::ReadMap "read-only map" assigns \c true to
  1631   /// the keys for which the corresponding value of the first map is
  1632   /// less then the value of the second map.
  1633   /// Its \c Key type is inherited from \c M1 and its \c Value type is
  1634   /// \c bool. \c M2::Key must be convertible to \c M1::Key.
  1635   ///
  1636   /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
  1637   /// \code
  1638   ///   LessMap<M1,M2> lm(m1,m2);
  1639   /// \endcode
  1640   /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
  1641   ///
  1642   /// The simplest way of using this map is through the lessMap()
  1643   /// function.
  1644   ///
  1645   /// \sa EqualMap
  1646   template<typename M1, typename M2>
  1647   class LessMap : public MapBase<typename M1::Key, bool> {
  1648     const M1 &_m1;
  1649     const M2 &_m2;
  1650   public:
  1651     typedef MapBase<typename M1::Key, bool> Parent;
  1652     typedef typename Parent::Key Key;
  1653     typedef typename Parent::Value Value;
  1654 
  1655     /// Constructor
  1656     LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1657     /// \e
  1658     Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
  1659   };
  1660 
  1661   /// Returns an \ref LessMap class
  1662 
  1663   /// This function just returns an \ref LessMap class.
  1664   ///
  1665   /// For example, if \c m1 and \c m2 are maps with keys and values of
  1666   /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
  1667   /// <tt>m1[x]<m2[x]</tt>.
  1668   ///
  1669   /// \relates LessMap
  1670   template<typename M1, typename M2>
  1671   inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
  1672     return LessMap<M1, M2>(m1,m2);
  1673   }
  1674 
  1675   namespace _maps_bits {
  1676 
  1677     template <typename _Iterator, typename Enable = void>
  1678     struct IteratorTraits {
  1679       typedef typename std::iterator_traits<_Iterator>::value_type Value;
  1680     };
  1681 
  1682     template <typename _Iterator>
  1683     struct IteratorTraits<_Iterator,
  1684       typename exists<typename _Iterator::container_type>::type>
  1685     {
  1686       typedef typename _Iterator::container_type::value_type Value;
  1687     };
  1688 
  1689   }
  1690 
  1691   /// \brief Writable bool map for logging each \c true assigned element
  1692   ///
  1693   /// A \ref concepts::WriteMap "writable" bool map for logging
  1694   /// each \c true assigned element, i.e it copies subsequently each
  1695   /// keys set to \c true to the given iterator.
  1696   /// The most important usage of it is storing certain nodes or arcs
  1697   /// that were marked \c true by an algorithm.
  1698   ///
  1699   /// There are several algorithms that provide solutions through bool
  1700   /// maps and most of them assign \c true at most once for each key.
  1701   /// In these cases it is a natural request to store each \c true
  1702   /// assigned elements (in order of the assignment), which can be
  1703   /// easily done with LoggerBoolMap.
  1704   ///
  1705   /// The simplest way of using this map is through the loggerBoolMap()
  1706   /// function.
  1707   ///
  1708   /// \tparam It The type of the iterator.
  1709   /// \tparam Ke The key type of the map. The default value set
  1710   /// according to the iterator type should work in most cases.
  1711   ///
  1712   /// \note The container of the iterator must contain enough space
  1713   /// for the elements or the iterator should be an inserter iterator.
  1714 #ifdef DOXYGEN
  1715   template <typename It, typename Ke>
  1716 #else
  1717   template <typename It,
  1718 	    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  1719 #endif
  1720   class LoggerBoolMap {
  1721   public:
  1722     typedef It Iterator;
  1723 
  1724     typedef Ke Key;
  1725     typedef bool Value;
  1726 
  1727     /// Constructor
  1728     LoggerBoolMap(Iterator it)
  1729       : _begin(it), _end(it) {}
  1730 
  1731     /// Gives back the given iterator set for the first key
  1732     Iterator begin() const {
  1733       return _begin;
  1734     }
  1735 
  1736     /// Gives back the the 'after the last' iterator
  1737     Iterator end() const {
  1738       return _end;
  1739     }
  1740 
  1741     /// The set function of the map
  1742     void set(const Key& key, Value value) {
  1743       if (value) {
  1744 	*_end++ = key;
  1745       }
  1746     }
  1747 
  1748   private:
  1749     Iterator _begin;
  1750     Iterator _end;
  1751   };
  1752   
  1753   /// Returns a \ref LoggerBoolMap class
  1754 
  1755   /// This function just returns a \ref LoggerBoolMap class.
  1756   ///
  1757   /// The most important usage of it is storing certain nodes or arcs
  1758   /// that were marked \c true by an algorithm.
  1759   /// For example it makes easier to store the nodes in the processing
  1760   /// order of Dfs algorithm, as the following examples show.
  1761   /// \code
  1762   ///   std::vector<Node> v;
  1763   ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
  1764   /// \endcode
  1765   /// \code
  1766   ///   std::vector<Node> v(countNodes(g));
  1767   ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
  1768   /// \endcode
  1769   ///
  1770   /// \note The container of the iterator must contain enough space
  1771   /// for the elements or the iterator should be an inserter iterator.
  1772   ///
  1773   /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
  1774   /// it cannot be used when a readable map is needed, for example as
  1775   /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
  1776   ///
  1777   /// \relates LoggerBoolMap
  1778   template<typename Iterator>
  1779   inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
  1780     return LoggerBoolMap<Iterator>(it);
  1781   }
  1782 
  1783   /// @}
  1784 }
  1785 
  1786 #endif // LEMON_MAPS_H