lemon/maps.h
changeset 302 1871777f62b7
parent 280 e7f8647ce760
child 313 64f8f7cc6168
equal deleted inserted replaced
24:9541e07287f8 25:3ce5c7194a17
    71     Value operator[](const Key&) const { return Value(); }
    71     Value operator[](const Key&) const { return Value(); }
    72     /// Absorbs the value.
    72     /// Absorbs the value.
    73     void set(const Key&, const Value&) {}
    73     void set(const Key&, const Value&) {}
    74   };
    74   };
    75 
    75 
    76   /// Returns a \ref NullMap class
    76   /// Returns a \c NullMap class
    77 
    77 
    78   /// This function just returns a \ref NullMap class.
    78   /// This function just returns a \c NullMap class.
    79   /// \relates NullMap
    79   /// \relates NullMap
    80   template <typename K, typename V>
    80   template <typename K, typename V>
    81   NullMap<K, V> nullMap() {
    81   NullMap<K, V> nullMap() {
    82     return NullMap<K, V>();
    82     return NullMap<K, V>();
    83   }
    83   }
    86   /// Constant map.
    86   /// Constant map.
    87 
    87 
    88   /// This \ref concepts::ReadMap "readable map" assigns a specified
    88   /// This \ref concepts::ReadMap "readable map" assigns a specified
    89   /// value to each key.
    89   /// value to each key.
    90   ///
    90   ///
    91   /// In other aspects it is equivalent to \ref NullMap.
    91   /// In other aspects it is equivalent to \c NullMap.
    92   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
    92   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
    93   /// concept, but it absorbs the data written to it.
    93   /// concept, but it absorbs the data written to it.
    94   ///
    94   ///
    95   /// The simplest way of using this map is through the constMap()
    95   /// The simplest way of using this map is through the constMap()
    96   /// function.
    96   /// function.
   131 
   131 
   132     template<typename V1>
   132     template<typename V1>
   133     ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
   133     ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
   134   };
   134   };
   135 
   135 
   136   /// Returns a \ref ConstMap class
   136   /// Returns a \c ConstMap class
   137 
   137 
   138   /// This function just returns a \ref ConstMap class.
   138   /// This function just returns a \c ConstMap class.
   139   /// \relates ConstMap
   139   /// \relates ConstMap
   140   template<typename K, typename V>
   140   template<typename K, typename V>
   141   inline ConstMap<K, V> constMap(const V &v) {
   141   inline ConstMap<K, V> constMap(const V &v) {
   142     return ConstMap<K, V>(v);
   142     return ConstMap<K, V>(v);
   143   }
   143   }
   154   /// Constant map with inlined constant value.
   154   /// Constant map with inlined constant value.
   155 
   155 
   156   /// This \ref concepts::ReadMap "readable map" assigns a specified
   156   /// This \ref concepts::ReadMap "readable map" assigns a specified
   157   /// value to each key.
   157   /// value to each key.
   158   ///
   158   ///
   159   /// In other aspects it is equivalent to \ref NullMap.
   159   /// In other aspects it is equivalent to \c NullMap.
   160   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
   160   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
   161   /// concept, but it absorbs the data written to it.
   161   /// concept, but it absorbs the data written to it.
   162   ///
   162   ///
   163   /// The simplest way of using this map is through the constMap()
   163   /// The simplest way of using this map is through the constMap()
   164   /// function.
   164   /// function.
   180 
   180 
   181     /// Absorbs the value.
   181     /// Absorbs the value.
   182     void set(const Key&, const Value&) {}
   182     void set(const Key&, const Value&) {}
   183   };
   183   };
   184 
   184 
   185   /// Returns a \ref ConstMap class with inlined constant value
   185   /// Returns a \c ConstMap class with inlined constant value
   186 
   186 
   187   /// This function just returns a \ref ConstMap class with inlined
   187   /// This function just returns a \c ConstMap class with inlined
   188   /// constant value.
   188   /// constant value.
   189   /// \relates ConstMap
   189   /// \relates ConstMap
   190   template<typename K, typename V, V v>
   190   template<typename K, typename V, V v>
   191   inline ConstMap<K, Const<V, v> > constMap() {
   191   inline ConstMap<K, Const<V, v> > constMap() {
   192     return ConstMap<K, Const<V, v> >();
   192     return ConstMap<K, Const<V, v> >();
   210     Value operator[](const Key &k) const {
   210     Value operator[](const Key &k) const {
   211       return k;
   211       return k;
   212     }
   212     }
   213   };
   213   };
   214 
   214 
   215   /// Returns an \ref IdentityMap class
   215   /// Returns an \c IdentityMap class
   216 
   216 
   217   /// This function just returns an \ref IdentityMap class.
   217   /// This function just returns an \c IdentityMap class.
   218   /// \relates IdentityMap
   218   /// \relates IdentityMap
   219   template<typename T>
   219   template<typename T>
   220   inline IdentityMap<T> identityMap() {
   220   inline IdentityMap<T> identityMap() {
   221     return IdentityMap<T>();
   221     return IdentityMap<T>();
   222   }
   222   }
   226   /// <tt>[0..size-1]</tt>.
   226   /// <tt>[0..size-1]</tt>.
   227   ///
   227   ///
   228   /// This map is essentially a wrapper for \c std::vector. It assigns
   228   /// This map is essentially a wrapper for \c std::vector. It assigns
   229   /// values to integer keys from the range <tt>[0..size-1]</tt>.
   229   /// values to integer keys from the range <tt>[0..size-1]</tt>.
   230   /// It can be used with some data structures, for example
   230   /// It can be used with some data structures, for example
   231   /// \ref UnionFind, \ref BinHeap, when the used items are small
   231   /// \c UnionFind, \c BinHeap, when the used items are small
   232   /// integers. This map conforms the \ref concepts::ReferenceMap
   232   /// integers. This map conforms the \ref concepts::ReferenceMap
   233   /// "ReferenceMap" concept.
   233   /// "ReferenceMap" concept.
   234   ///
   234   ///
   235   /// The simplest way of using this map is through the rangeMap()
   235   /// The simplest way of using this map is through the rangeMap()
   236   /// function.
   236   /// function.
   266     /// Constructs the map from an appropriate \c std::vector.
   266     /// Constructs the map from an appropriate \c std::vector.
   267     template <typename V1>
   267     template <typename V1>
   268     RangeMap(const std::vector<V1>& vector)
   268     RangeMap(const std::vector<V1>& vector)
   269       : _vector(vector.begin(), vector.end()) {}
   269       : _vector(vector.begin(), vector.end()) {}
   270 
   270 
   271     /// Constructs the map from another \ref RangeMap.
   271     /// Constructs the map from another \c RangeMap.
   272     template <typename V1>
   272     template <typename V1>
   273     RangeMap(const RangeMap<V1> &c)
   273     RangeMap(const RangeMap<V1> &c)
   274       : _vector(c._vector.begin(), c._vector.end()) {}
   274       : _vector(c._vector.begin(), c._vector.end()) {}
   275 
   275 
   276     /// Returns the size of the map.
   276     /// Returns the size of the map.
   309     void set(const Key &k, const Value &v) {
   309     void set(const Key &k, const Value &v) {
   310       _vector[k] = v;
   310       _vector[k] = v;
   311     }
   311     }
   312   };
   312   };
   313 
   313 
   314   /// Returns a \ref RangeMap class
   314   /// Returns a \c RangeMap class
   315 
   315 
   316   /// This function just returns a \ref RangeMap class.
   316   /// This function just returns a \c RangeMap class.
   317   /// \relates RangeMap
   317   /// \relates RangeMap
   318   template<typename V>
   318   template<typename V>
   319   inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
   319   inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
   320     return RangeMap<V>(size, value);
   320     return RangeMap<V>(size, value);
   321   }
   321   }
   322 
   322 
   323   /// \brief Returns a \ref RangeMap class created from an appropriate
   323   /// \brief Returns a \c RangeMap class created from an appropriate
   324   /// \c std::vector
   324   /// \c std::vector
   325 
   325 
   326   /// This function just returns a \ref RangeMap class created from an
   326   /// This function just returns a \c RangeMap class created from an
   327   /// appropriate \c std::vector.
   327   /// appropriate \c std::vector.
   328   /// \relates RangeMap
   328   /// \relates RangeMap
   329   template<typename V>
   329   template<typename V>
   330   inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
   330   inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
   331     return RangeMap<V>(vector);
   331     return RangeMap<V>(vector);
   386     template <typename V1, typename Comp1>
   386     template <typename V1, typename Comp1>
   387     SparseMap(const std::map<Key, V1, Comp1> &map,
   387     SparseMap(const std::map<Key, V1, Comp1> &map,
   388               const Value &value = Value())
   388               const Value &value = Value())
   389       : _map(map.begin(), map.end()), _value(value) {}
   389       : _map(map.begin(), map.end()), _value(value) {}
   390 
   390 
   391     /// \brief Constructs the map from another \ref SparseMap.
   391     /// \brief Constructs the map from another \c SparseMap.
   392     template<typename V1, typename Comp1>
   392     template<typename V1, typename Comp1>
   393     SparseMap(const SparseMap<Key, V1, Comp1> &c)
   393     SparseMap(const SparseMap<Key, V1, Comp1> &c)
   394       : _map(c._map.begin(), c._map.end()), _value(c._value) {}
   394       : _map(c._map.begin(), c._map.end()), _value(c._value) {}
   395 
   395 
   396   private:
   396   private:
   431       _value = v;
   431       _value = v;
   432       _map.clear();
   432       _map.clear();
   433     }
   433     }
   434   };
   434   };
   435 
   435 
   436   /// Returns a \ref SparseMap class
   436   /// Returns a \c SparseMap class
   437 
   437 
   438   /// This function just returns a \ref SparseMap class with specified
   438   /// This function just returns a \c SparseMap class with specified
   439   /// default value.
   439   /// default value.
   440   /// \relates SparseMap
   440   /// \relates SparseMap
   441   template<typename K, typename V, typename Compare>
   441   template<typename K, typename V, typename Compare>
   442   inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
   442   inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
   443     return SparseMap<K, V, Compare>(value);
   443     return SparseMap<K, V, Compare>(value);
   446   template<typename K, typename V>
   446   template<typename K, typename V>
   447   inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
   447   inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
   448     return SparseMap<K, V, std::less<K> >(value);
   448     return SparseMap<K, V, std::less<K> >(value);
   449   }
   449   }
   450 
   450 
   451   /// \brief Returns a \ref SparseMap class created from an appropriate
   451   /// \brief Returns a \c SparseMap class created from an appropriate
   452   /// \c std::map
   452   /// \c std::map
   453 
   453 
   454   /// This function just returns a \ref SparseMap class created from an
   454   /// This function just returns a \c SparseMap class created from an
   455   /// appropriate \c std::map.
   455   /// appropriate \c std::map.
   456   /// \relates SparseMap
   456   /// \relates SparseMap
   457   template<typename K, typename V, typename Compare>
   457   template<typename K, typename V, typename Compare>
   458   inline SparseMap<K, V, Compare>
   458   inline SparseMap<K, V, Compare>
   459     sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
   459     sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
   499     /// \e
   499     /// \e
   500     typename MapTraits<M1>::ConstReturnValue
   500     typename MapTraits<M1>::ConstReturnValue
   501     operator[](const Key &k) const { return _m1[_m2[k]]; }
   501     operator[](const Key &k) const { return _m1[_m2[k]]; }
   502   };
   502   };
   503 
   503 
   504   /// Returns a \ref ComposeMap class
   504   /// Returns a \c ComposeMap class
   505 
   505 
   506   /// This function just returns a \ref ComposeMap class.
   506   /// This function just returns a \c ComposeMap class.
   507   ///
   507   ///
   508   /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
   508   /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
   509   /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
   509   /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
   510   /// will be equal to <tt>m1[m2[x]]</tt>.
   510   /// will be equal to <tt>m1[m2[x]]</tt>.
   511   ///
   511   ///
   554       : _m1(m1), _m2(m2), _f(f) {}
   554       : _m1(m1), _m2(m2), _f(f) {}
   555     /// \e
   555     /// \e
   556     Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
   556     Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
   557   };
   557   };
   558 
   558 
   559   /// Returns a \ref CombineMap class
   559   /// Returns a \c CombineMap class
   560 
   560 
   561   /// This function just returns a \ref CombineMap class.
   561   /// This function just returns a \c CombineMap class.
   562   ///
   562   ///
   563   /// For example, if \c m1 and \c m2 are both maps with \c double
   563   /// For example, if \c m1 and \c m2 are both maps with \c double
   564   /// values, then
   564   /// values, then
   565   /// \code
   565   /// \code
   566   ///   combineMap(m1,m2,std::plus<double>())
   566   ///   combineMap(m1,m2,std::plus<double>())
   623     FunctorToMap(const F &f = F()) : _f(f) {}
   623     FunctorToMap(const F &f = F()) : _f(f) {}
   624     /// \e
   624     /// \e
   625     Value operator[](const Key &k) const { return _f(k); }
   625     Value operator[](const Key &k) const { return _f(k); }
   626   };
   626   };
   627 
   627 
   628   /// Returns a \ref FunctorToMap class
   628   /// Returns a \c FunctorToMap class
   629 
   629 
   630   /// This function just returns a \ref FunctorToMap class.
   630   /// This function just returns a \c FunctorToMap class.
   631   ///
   631   ///
   632   /// This function is specialized for adaptable binary function
   632   /// This function is specialized for adaptable binary function
   633   /// classes and C++ functions.
   633   /// classes and C++ functions.
   634   ///
   634   ///
   635   /// \relates FunctorToMap
   635   /// \relates FunctorToMap
   682     Value operator()(const Key &k) const { return _m[k]; }
   682     Value operator()(const Key &k) const { return _m[k]; }
   683     /// \e
   683     /// \e
   684     Value operator[](const Key &k) const { return _m[k]; }
   684     Value operator[](const Key &k) const { return _m[k]; }
   685   };
   685   };
   686 
   686 
   687   /// Returns a \ref MapToFunctor class
   687   /// Returns a \c MapToFunctor class
   688 
   688 
   689   /// This function just returns a \ref MapToFunctor class.
   689   /// This function just returns a \c MapToFunctor class.
   690   /// \relates MapToFunctor
   690   /// \relates MapToFunctor
   691   template<typename M>
   691   template<typename M>
   692   inline MapToFunctor<M> mapToFunctor(const M &m) {
   692   inline MapToFunctor<M> mapToFunctor(const M &m) {
   693     return MapToFunctor<M>(m);
   693     return MapToFunctor<M>(m);
   694   }
   694   }
   721 
   721 
   722     /// \e
   722     /// \e
   723     Value operator[](const Key &k) const { return _m[k]; }
   723     Value operator[](const Key &k) const { return _m[k]; }
   724   };
   724   };
   725 
   725 
   726   /// Returns a \ref ConvertMap class
   726   /// Returns a \c ConvertMap class
   727 
   727 
   728   /// This function just returns a \ref ConvertMap class.
   728   /// This function just returns a \c ConvertMap class.
   729   /// \relates ConvertMap
   729   /// \relates ConvertMap
   730   template<typename V, typename M>
   730   template<typename V, typename M>
   731   inline ConvertMap<M, V> convertMap(const M &map) {
   731   inline ConvertMap<M, V> convertMap(const M &map) {
   732     return ConvertMap<M, V>(map);
   732     return ConvertMap<M, V>(map);
   733   }
   733   }
   761     Value operator[](const Key &k) const { return _m1[k]; }
   761     Value operator[](const Key &k) const { return _m1[k]; }
   762     /// Sets the value associated with the given key in both maps.
   762     /// Sets the value associated with the given key in both maps.
   763     void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
   763     void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
   764   };
   764   };
   765 
   765 
   766   /// Returns a \ref ForkMap class
   766   /// Returns a \c ForkMap class
   767 
   767 
   768   /// This function just returns a \ref ForkMap class.
   768   /// This function just returns a \c ForkMap class.
   769   /// \relates ForkMap
   769   /// \relates ForkMap
   770   template <typename M1, typename M2>
   770   template <typename M1, typename M2>
   771   inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
   771   inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
   772     return ForkMap<M1,M2>(m1,m2);
   772     return ForkMap<M1,M2>(m1,m2);
   773   }
   773   }
   805     AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   805     AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   806     /// \e
   806     /// \e
   807     Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
   807     Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
   808   };
   808   };
   809 
   809 
   810   /// Returns an \ref AddMap class
   810   /// Returns an \c AddMap class
   811 
   811 
   812   /// This function just returns an \ref AddMap class.
   812   /// This function just returns an \c AddMap class.
   813   ///
   813   ///
   814   /// For example, if \c m1 and \c m2 are both maps with \c double
   814   /// For example, if \c m1 and \c m2 are both maps with \c double
   815   /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
   815   /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
   816   /// <tt>m1[x]+m2[x]</tt>.
   816   /// <tt>m1[x]+m2[x]</tt>.
   817   ///
   817   ///
   853     SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   853     SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
   854     /// \e
   854     /// \e
   855     Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
   855     Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
   856   };
   856   };
   857 
   857 
   858   /// Returns a \ref SubMap class
   858   /// Returns a \c SubMap class
   859 
   859 
   860   /// This function just returns a \ref SubMap class.
   860   /// This function just returns a \c SubMap class.
   861   ///
   861   ///
   862   /// For example, if \c m1 and \c m2 are both maps with \c double
   862   /// For example, if \c m1 and \c m2 are both maps with \c double
   863   /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
   863   /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
   864   /// <tt>m1[x]-m2[x]</tt>.
   864   /// <tt>m1[x]-m2[x]</tt>.
   865   ///
   865   ///
   902     MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   902     MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   903     /// \e
   903     /// \e
   904     Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
   904     Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
   905   };
   905   };
   906 
   906 
   907   /// Returns a \ref MulMap class
   907   /// Returns a \c MulMap class
   908 
   908 
   909   /// This function just returns a \ref MulMap class.
   909   /// This function just returns a \c MulMap class.
   910   ///
   910   ///
   911   /// For example, if \c m1 and \c m2 are both maps with \c double
   911   /// For example, if \c m1 and \c m2 are both maps with \c double
   912   /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
   912   /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
   913   /// <tt>m1[x]*m2[x]</tt>.
   913   /// <tt>m1[x]*m2[x]</tt>.
   914   ///
   914   ///
   950     DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   950     DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
   951     /// \e
   951     /// \e
   952     Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
   952     Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
   953   };
   953   };
   954 
   954 
   955   /// Returns a \ref DivMap class
   955   /// Returns a \c DivMap class
   956 
   956 
   957   /// This function just returns a \ref DivMap class.
   957   /// This function just returns a \c DivMap class.
   958   ///
   958   ///
   959   /// For example, if \c m1 and \c m2 are both maps with \c double
   959   /// For example, if \c m1 and \c m2 are both maps with \c double
   960   /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
   960   /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
   961   /// <tt>m1[x]/m2[x]</tt>.
   961   /// <tt>m1[x]/m2[x]</tt>.
   962   ///
   962   ///
  1036     Value operator[](const Key &k) const { return _m[k]+_v; }
  1036     Value operator[](const Key &k) const { return _m[k]+_v; }
  1037     /// \e
  1037     /// \e
  1038     void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
  1038     void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
  1039   };
  1039   };
  1040 
  1040 
  1041   /// Returns a \ref ShiftMap class
  1041   /// Returns a \c ShiftMap class
  1042 
  1042 
  1043   /// This function just returns a \ref ShiftMap class.
  1043   /// This function just returns a \c ShiftMap class.
  1044   ///
  1044   ///
  1045   /// For example, if \c m is a map with \c double values and \c v is
  1045   /// For example, if \c m is a map with \c double values and \c v is
  1046   /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
  1046   /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
  1047   /// <tt>m[x]+v</tt>.
  1047   /// <tt>m[x]+v</tt>.
  1048   ///
  1048   ///
  1050   template<typename M, typename C>
  1050   template<typename M, typename C>
  1051   inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
  1051   inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
  1052     return ShiftMap<M, C>(m,v);
  1052     return ShiftMap<M, C>(m,v);
  1053   }
  1053   }
  1054 
  1054 
  1055   /// Returns a \ref ShiftWriteMap class
  1055   /// Returns a \c ShiftWriteMap class
  1056 
  1056 
  1057   /// This function just returns a \ref ShiftWriteMap class.
  1057   /// This function just returns a \c ShiftWriteMap class.
  1058   ///
  1058   ///
  1059   /// For example, if \c m is a map with \c double values and \c v is
  1059   /// For example, if \c m is a map with \c double values and \c v is
  1060   /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
  1060   /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
  1061   /// <tt>m[x]+v</tt>.
  1061   /// <tt>m[x]+v</tt>.
  1062   /// Moreover it makes also possible to write the map.
  1062   /// Moreover it makes also possible to write the map.
  1138     Value operator[](const Key &k) const { return _v*_m[k]; }
  1138     Value operator[](const Key &k) const { return _v*_m[k]; }
  1139     /// \e
  1139     /// \e
  1140     void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
  1140     void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
  1141   };
  1141   };
  1142 
  1142 
  1143   /// Returns a \ref ScaleMap class
  1143   /// Returns a \c ScaleMap class
  1144 
  1144 
  1145   /// This function just returns a \ref ScaleMap class.
  1145   /// This function just returns a \c ScaleMap class.
  1146   ///
  1146   ///
  1147   /// For example, if \c m is a map with \c double values and \c v is
  1147   /// For example, if \c m is a map with \c double values and \c v is
  1148   /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
  1148   /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
  1149   /// <tt>v*m[x]</tt>.
  1149   /// <tt>v*m[x]</tt>.
  1150   ///
  1150   ///
  1152   template<typename M, typename C>
  1152   template<typename M, typename C>
  1153   inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
  1153   inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
  1154     return ScaleMap<M, C>(m,v);
  1154     return ScaleMap<M, C>(m,v);
  1155   }
  1155   }
  1156 
  1156 
  1157   /// Returns a \ref ScaleWriteMap class
  1157   /// Returns a \c ScaleWriteMap class
  1158 
  1158 
  1159   /// This function just returns a \ref ScaleWriteMap class.
  1159   /// This function just returns a \c ScaleWriteMap class.
  1160   ///
  1160   ///
  1161   /// For example, if \c m is a map with \c double values and \c v is
  1161   /// For example, if \c m is a map with \c double values and \c v is
  1162   /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
  1162   /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
  1163   /// <tt>v*m[x]</tt>.
  1163   /// <tt>v*m[x]</tt>.
  1164   /// Moreover it makes also possible to write the map.
  1164   /// Moreover it makes also possible to write the map.
  1238     Value operator[](const Key &k) const { return -_m[k]; }
  1238     Value operator[](const Key &k) const { return -_m[k]; }
  1239     /// \e
  1239     /// \e
  1240     void set(const Key &k, const Value &v) { _m.set(k, -v); }
  1240     void set(const Key &k, const Value &v) { _m.set(k, -v); }
  1241   };
  1241   };
  1242 
  1242 
  1243   /// Returns a \ref NegMap class
  1243   /// Returns a \c NegMap class
  1244 
  1244 
  1245   /// This function just returns a \ref NegMap class.
  1245   /// This function just returns a \c NegMap class.
  1246   ///
  1246   ///
  1247   /// For example, if \c m is a map with \c double values, then
  1247   /// For example, if \c m is a map with \c double values, then
  1248   /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
  1248   /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
  1249   ///
  1249   ///
  1250   /// \relates NegMap
  1250   /// \relates NegMap
  1251   template <typename M>
  1251   template <typename M>
  1252   inline NegMap<M> negMap(const M &m) {
  1252   inline NegMap<M> negMap(const M &m) {
  1253     return NegMap<M>(m);
  1253     return NegMap<M>(m);
  1254   }
  1254   }
  1255 
  1255 
  1256   /// Returns a \ref NegWriteMap class
  1256   /// Returns a \c NegWriteMap class
  1257 
  1257 
  1258   /// This function just returns a \ref NegWriteMap class.
  1258   /// This function just returns a \c NegWriteMap class.
  1259   ///
  1259   ///
  1260   /// For example, if \c m is a map with \c double values, then
  1260   /// For example, if \c m is a map with \c double values, then
  1261   /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
  1261   /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
  1262   /// Moreover it makes also possible to write the map.
  1262   /// Moreover it makes also possible to write the map.
  1263   ///
  1263   ///
  1294       return tmp >= 0 ? tmp : -tmp;
  1294       return tmp >= 0 ? tmp : -tmp;
  1295     }
  1295     }
  1296 
  1296 
  1297   };
  1297   };
  1298 
  1298 
  1299   /// Returns an \ref AbsMap class
  1299   /// Returns an \c AbsMap class
  1300 
  1300 
  1301   /// This function just returns an \ref AbsMap class.
  1301   /// This function just returns an \c AbsMap class.
  1302   ///
  1302   ///
  1303   /// For example, if \c m is a map with \c double values, then
  1303   /// For example, if \c m is a map with \c double values, then
  1304   /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
  1304   /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
  1305   /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
  1305   /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
  1306   /// negative.
  1306   /// negative.
  1343 
  1343 
  1344     /// Gives back \c true.
  1344     /// Gives back \c true.
  1345     Value operator[](const Key&) const { return true; }
  1345     Value operator[](const Key&) const { return true; }
  1346   };
  1346   };
  1347 
  1347 
  1348   /// Returns a \ref TrueMap class
  1348   /// Returns a \c TrueMap class
  1349 
  1349 
  1350   /// This function just returns a \ref TrueMap class.
  1350   /// This function just returns a \c TrueMap class.
  1351   /// \relates TrueMap
  1351   /// \relates TrueMap
  1352   template<typename K>
  1352   template<typename K>
  1353   inline TrueMap<K> trueMap() {
  1353   inline TrueMap<K> trueMap() {
  1354     return TrueMap<K>();
  1354     return TrueMap<K>();
  1355   }
  1355   }
  1380 
  1380 
  1381     /// Gives back \c false.
  1381     /// Gives back \c false.
  1382     Value operator[](const Key&) const { return false; }
  1382     Value operator[](const Key&) const { return false; }
  1383   };
  1383   };
  1384 
  1384 
  1385   /// Returns a \ref FalseMap class
  1385   /// Returns a \c FalseMap class
  1386 
  1386 
  1387   /// This function just returns a \ref FalseMap class.
  1387   /// This function just returns a \c FalseMap class.
  1388   /// \relates FalseMap
  1388   /// \relates FalseMap
  1389   template<typename K>
  1389   template<typename K>
  1390   inline FalseMap<K> falseMap() {
  1390   inline FalseMap<K> falseMap() {
  1391     return FalseMap<K>();
  1391     return FalseMap<K>();
  1392   }
  1392   }
  1427     AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1427     AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1428     /// \e
  1428     /// \e
  1429     Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
  1429     Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
  1430   };
  1430   };
  1431 
  1431 
  1432   /// Returns an \ref AndMap class
  1432   /// Returns an \c AndMap class
  1433 
  1433 
  1434   /// This function just returns an \ref AndMap class.
  1434   /// This function just returns an \c AndMap class.
  1435   ///
  1435   ///
  1436   /// For example, if \c m1 and \c m2 are both maps with \c bool values,
  1436   /// For example, if \c m1 and \c m2 are both maps with \c bool values,
  1437   /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
  1437   /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
  1438   /// <tt>m1[x]&&m2[x]</tt>.
  1438   /// <tt>m1[x]&&m2[x]</tt>.
  1439   ///
  1439   ///
  1475     OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1475     OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1476     /// \e
  1476     /// \e
  1477     Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
  1477     Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
  1478   };
  1478   };
  1479 
  1479 
  1480   /// Returns an \ref OrMap class
  1480   /// Returns an \c OrMap class
  1481 
  1481 
  1482   /// This function just returns an \ref OrMap class.
  1482   /// This function just returns an \c OrMap class.
  1483   ///
  1483   ///
  1484   /// For example, if \c m1 and \c m2 are both maps with \c bool values,
  1484   /// For example, if \c m1 and \c m2 are both maps with \c bool values,
  1485   /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
  1485   /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
  1486   /// <tt>m1[x]||m2[x]</tt>.
  1486   /// <tt>m1[x]||m2[x]</tt>.
  1487   ///
  1487   ///
  1542     Value operator[](const Key &k) const { return !_m[k]; }
  1542     Value operator[](const Key &k) const { return !_m[k]; }
  1543     /// \e
  1543     /// \e
  1544     void set(const Key &k, bool v) { _m.set(k, !v); }
  1544     void set(const Key &k, bool v) { _m.set(k, !v); }
  1545   };
  1545   };
  1546 
  1546 
  1547   /// Returns a \ref NotMap class
  1547   /// Returns a \c NotMap class
  1548 
  1548 
  1549   /// This function just returns a \ref NotMap class.
  1549   /// This function just returns a \c NotMap class.
  1550   ///
  1550   ///
  1551   /// For example, if \c m is a map with \c bool values, then
  1551   /// For example, if \c m is a map with \c bool values, then
  1552   /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
  1552   /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
  1553   ///
  1553   ///
  1554   /// \relates NotMap
  1554   /// \relates NotMap
  1555   template <typename M>
  1555   template <typename M>
  1556   inline NotMap<M> notMap(const M &m) {
  1556   inline NotMap<M> notMap(const M &m) {
  1557     return NotMap<M>(m);
  1557     return NotMap<M>(m);
  1558   }
  1558   }
  1559 
  1559 
  1560   /// Returns a \ref NotWriteMap class
  1560   /// Returns a \c NotWriteMap class
  1561 
  1561 
  1562   /// This function just returns a \ref NotWriteMap class.
  1562   /// This function just returns a \c NotWriteMap class.
  1563   ///
  1563   ///
  1564   /// For example, if \c m is a map with \c bool values, then
  1564   /// For example, if \c m is a map with \c bool values, then
  1565   /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
  1565   /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
  1566   /// Moreover it makes also possible to write the map.
  1566   /// Moreover it makes also possible to write the map.
  1567   ///
  1567   ///
  1603     EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1603     EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1604     /// \e
  1604     /// \e
  1605     Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
  1605     Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
  1606   };
  1606   };
  1607 
  1607 
  1608   /// Returns an \ref EqualMap class
  1608   /// Returns an \c EqualMap class
  1609 
  1609 
  1610   /// This function just returns an \ref EqualMap class.
  1610   /// This function just returns an \c EqualMap class.
  1611   ///
  1611   ///
  1612   /// For example, if \c m1 and \c m2 are maps with keys and values of
  1612   /// For example, if \c m1 and \c m2 are maps with keys and values of
  1613   /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
  1613   /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
  1614   /// <tt>m1[x]==m2[x]</tt>.
  1614   /// <tt>m1[x]==m2[x]</tt>.
  1615   ///
  1615   ///
  1651     LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1651     LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  1652     /// \e
  1652     /// \e
  1653     Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
  1653     Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
  1654   };
  1654   };
  1655 
  1655 
  1656   /// Returns an \ref LessMap class
  1656   /// Returns an \c LessMap class
  1657 
  1657 
  1658   /// This function just returns an \ref LessMap class.
  1658   /// This function just returns an \c LessMap class.
  1659   ///
  1659   ///
  1660   /// For example, if \c m1 and \c m2 are maps with keys and values of
  1660   /// For example, if \c m1 and \c m2 are maps with keys and values of
  1661   /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
  1661   /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
  1662   /// <tt>m1[x]<m2[x]</tt>.
  1662   /// <tt>m1[x]<m2[x]</tt>.
  1663   ///
  1663   ///
  1743   private:
  1743   private:
  1744     Iterator _begin;
  1744     Iterator _begin;
  1745     Iterator _end;
  1745     Iterator _end;
  1746   };
  1746   };
  1747 
  1747 
  1748   /// Returns a \ref LoggerBoolMap class
  1748   /// Returns a \c LoggerBoolMap class
  1749 
  1749 
  1750   /// This function just returns a \ref LoggerBoolMap class.
  1750   /// This function just returns a \c LoggerBoolMap class.
  1751   ///
  1751   ///
  1752   /// The most important usage of it is storing certain nodes or arcs
  1752   /// The most important usage of it is storing certain nodes or arcs
  1753   /// that were marked \c true by an algorithm.
  1753   /// that were marked \c true by an algorithm.
  1754   /// For example it makes easier to store the nodes in the processing
  1754   /// For example it makes easier to store the nodes in the processing
  1755   /// order of Dfs algorithm, as the following examples show.
  1755   /// order of Dfs algorithm, as the following examples show.
  1765   /// \note The container of the iterator must contain enough space
  1765   /// \note The container of the iterator must contain enough space
  1766   /// for the elements or the iterator should be an inserter iterator.
  1766   /// for the elements or the iterator should be an inserter iterator.
  1767   ///
  1767   ///
  1768   /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
  1768   /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
  1769   /// it cannot be used when a readable map is needed, for example as
  1769   /// it cannot be used when a readable map is needed, for example as
  1770   /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
  1770   /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
  1771   ///
  1771   ///
  1772   /// \relates LoggerBoolMap
  1772   /// \relates LoggerBoolMap
  1773   template<typename Iterator>
  1773   template<typename Iterator>
  1774   inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
  1774   inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
  1775     return LoggerBoolMap<Iterator>(it);
  1775     return LoggerBoolMap<Iterator>(it);
  2280 
  2280 
  2281   private:
  2281   private:
  2282     const Digraph& _digraph;
  2282     const Digraph& _digraph;
  2283   };
  2283   };
  2284 
  2284 
  2285   /// \brief Returns a \ref SourceMap class.
  2285   /// \brief Returns a \c SourceMap class.
  2286   ///
  2286   ///
  2287   /// This function just returns an \ref SourceMap class.
  2287   /// This function just returns an \c SourceMap class.
  2288   /// \relates SourceMap
  2288   /// \relates SourceMap
  2289   template <typename Digraph>
  2289   template <typename Digraph>
  2290   inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
  2290   inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
  2291     return SourceMap<Digraph>(digraph);
  2291     return SourceMap<Digraph>(digraph);
  2292   }
  2292   }
  2319 
  2319 
  2320   private:
  2320   private:
  2321     const Digraph& _digraph;
  2321     const Digraph& _digraph;
  2322   };
  2322   };
  2323 
  2323 
  2324   /// \brief Returns a \ref TargetMap class.
  2324   /// \brief Returns a \c TargetMap class.
  2325   ///
  2325   ///
  2326   /// This function just returns a \ref TargetMap class.
  2326   /// This function just returns a \c TargetMap class.
  2327   /// \relates TargetMap
  2327   /// \relates TargetMap
  2328   template <typename Digraph>
  2328   template <typename Digraph>
  2329   inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
  2329   inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
  2330     return TargetMap<Digraph>(digraph);
  2330     return TargetMap<Digraph>(digraph);
  2331   }
  2331   }
  2358 
  2358 
  2359   private:
  2359   private:
  2360     const Graph& _graph;
  2360     const Graph& _graph;
  2361   };
  2361   };
  2362 
  2362 
  2363   /// \brief Returns a \ref ForwardMap class.
  2363   /// \brief Returns a \c ForwardMap class.
  2364   ///
  2364   ///
  2365   /// This function just returns an \ref ForwardMap class.
  2365   /// This function just returns an \c ForwardMap class.
  2366   /// \relates ForwardMap
  2366   /// \relates ForwardMap
  2367   template <typename Graph>
  2367   template <typename Graph>
  2368   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
  2368   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
  2369     return ForwardMap<Graph>(graph);
  2369     return ForwardMap<Graph>(graph);
  2370   }
  2370   }
  2397 
  2397 
  2398   private:
  2398   private:
  2399     const Graph& _graph;
  2399     const Graph& _graph;
  2400   };
  2400   };
  2401 
  2401 
  2402   /// \brief Returns a \ref BackwardMap class
  2402   /// \brief Returns a \c BackwardMap class
  2403 
  2403 
  2404   /// This function just returns a \ref BackwardMap class.
  2404   /// This function just returns a \c BackwardMap class.
  2405   /// \relates BackwardMap
  2405   /// \relates BackwardMap
  2406   template <typename Graph>
  2406   template <typename Graph>
  2407   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
  2407   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
  2408     return BackwardMap<Graph>(graph);
  2408     return BackwardMap<Graph>(graph);
  2409   }
  2409   }