lemon/maps.h
changeset 53 afb5325d6211
parent 44 7bbd94715db5
parent 47 3750b8ebc91e
child 54 ff9bac2351bf
equal deleted inserted replaced
9:93c2f4eb086d 13:48af8b9069f9
    79   }
    79   }
    80 
    80 
    81 
    81 
    82   /// Constant map.
    82   /// Constant map.
    83 
    83 
    84   /// This is a readable map which assigns a specified value to each key.
    84   /// This is a \ref concepts::ReadMap "readable" map which assigns a 
    85   /// In other aspects it is equivalent to the \c NullMap.
    85   /// specified value to each key.
       
    86   /// In other aspects it is equivalent to \c NullMap.
    86   template<typename K, typename T>
    87   template<typename K, typename T>
    87   class ConstMap : public MapBase<K, T> {
    88   class ConstMap : public MapBase<K, T> {
    88   private:
    89   private:
    89     T v;
    90     T v;
    90   public:
    91   public:
   131   template<typename T, T v>
   132   template<typename T, T v>
   132   struct Const { };
   133   struct Const { };
   133 
   134 
   134   /// Constant map with inlined constant value.
   135   /// Constant map with inlined constant value.
   135 
   136 
   136   /// This is a readable map which assigns a specified value to each key.
   137   /// This is a \ref concepts::ReadMap "readable" map which assigns a 
   137   /// In other aspects it is equivalent to the \c NullMap.
   138   /// specified value to each key.
       
   139   /// In other aspects it is equivalent to \c NullMap.
   138   template<typename K, typename V, V v>
   140   template<typename K, typename V, V v>
   139   class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
   141   class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
   140   public:
   142   public:
   141     typedef MapBase<K, V> Parent;
   143     typedef MapBase<K, V> Parent;
   142     typedef typename Parent::Key Key;
   144     typedef typename Parent::Key Key;
   147     V operator[](const K&) const { return v; }
   149     V operator[](const K&) const { return v; }
   148     ///\e
   150     ///\e
   149     void set(const K&, const V&) { }
   151     void set(const K&, const V&) { }
   150   };
   152   };
   151 
   153 
   152   ///Returns a \c ConstMap class
   154   ///Returns a \c ConstMap class with inlined value
   153 
   155 
   154   ///This function just returns a \c ConstMap class with inlined value.
   156   ///This function just returns a \c ConstMap class with inlined value.
   155   ///\relates ConstMap
   157   ///\relates ConstMap
   156   template<typename K, typename V, V v> 
   158   template<typename K, typename V, V v> 
   157   inline ConstMap<K, Const<V, v> > constMap() {
   159   inline ConstMap<K, Const<V, v> > constMap() {
   158     return ConstMap<K, Const<V, v> >();
   160     return ConstMap<K, Const<V, v> >();
   159   }
   161   }
   160 
   162 
   161   ///Map based on std::map
   163   ///Map based on \c std::map
   162 
   164 
   163   ///This is essentially a wrapper for \c std::map with addition that
   165   ///This is essentially a wrapper for \c std::map with addition that
   164   ///you can specify a default value different from \c Value().
   166   ///you can specify a default value different from \c Value().
       
   167   ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
   165   template <typename K, typename T, typename Compare = std::less<K> >
   168   template <typename K, typename T, typename Compare = std::less<K> >
   166   class StdMap {
   169   class StdMap : public MapBase<K, T> {
   167     template <typename K1, typename T1, typename C1>
   170     template <typename K1, typename T1, typename C1>
   168     friend class StdMap;
   171     friend class StdMap;
   169   public:
   172   public:
   170 
   173 
   171     typedef True ReferenceMapTag;
   174     typedef MapBase<K, T> Parent;
   172     ///Key type
   175     ///Key type
   173     typedef K Key;
   176     typedef typename Parent::Key Key;
   174     ///Value type
   177     ///Value type
   175     typedef T Value;
   178     typedef typename Parent::Value Value;
   176     ///Reference Type
   179     ///Reference Type
   177     typedef T& Reference;
   180     typedef T& Reference;
   178     ///Const reference type
   181     ///Const reference type
   179     typedef const T& ConstReference;
   182     typedef const T& ConstReference;
       
   183 
       
   184     typedef True ReferenceMapTag;
   180 
   185 
   181   private:
   186   private:
   182     
   187     
   183     typedef std::map<K, T, Compare> Map;
   188     typedef std::map<K, T, Compare> Map;
   184     Value _value;
   189     Value _value;
   186 
   191 
   187   public:
   192   public:
   188 
   193 
   189     /// Constructor with specified default value
   194     /// Constructor with specified default value
   190     StdMap(const T& value = T()) : _value(value) {}
   195     StdMap(const T& value = T()) : _value(value) {}
   191     /// \brief Constructs the map from an appropriate std::map, and explicitly
   196     /// \brief Constructs the map from an appropriate \c std::map, and 
   192     /// specifies a default value.
   197     /// explicitly specifies a default value.
   193     template <typename T1, typename Comp1>
   198     template <typename T1, typename Comp1>
   194     StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 
   199     StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 
   195       : _map(map.begin(), map.end()), _value(value) {}
   200       : _map(map.begin(), map.end()), _value(value) {}
   196     
   201     
   197     /// \brief Constructs a map from an other StdMap.
   202     /// \brief Constructs a map from an other \ref StdMap.
   198     template<typename T1, typename Comp1>
   203     template<typename T1, typename Comp1>
   199     StdMap(const StdMap<Key, T1, Comp1> &c) 
   204     StdMap(const StdMap<Key, T1, Comp1> &c) 
   200       : _map(c._map.begin(), c._map.end()), _value(c._value) {}
   205       : _map(c._map.begin(), c._map.end()), _value(c._value) {}
   201 
   206 
   202   private:
   207   private:
   237       _value = t;
   242       _value = t;
   238       _map.clear();
   243       _map.clear();
   239     }    
   244     }    
   240 
   245 
   241   };
   246   };
       
   247   
       
   248   ///Returns a \c StdMap class
       
   249 
       
   250   ///This function just returns a \c StdMap class with specified 
       
   251   ///default value.
       
   252   ///\relates StdMap
       
   253   template<typename K, typename V, typename Compare = std::less<K> > 
       
   254   inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
       
   255     return StdMap<K, V, Compare>(value);
       
   256   }
       
   257 
       
   258   ///Returns a \c StdMap class created from an appropriate std::map
       
   259 
       
   260   ///This function just returns a \c StdMap class created from an 
       
   261   ///appropriate std::map.
       
   262   ///\relates StdMap
       
   263   template<typename K, typename V, typename Compare = std::less<K> > 
       
   264   inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map, 
       
   265                                        const V& value = V() ) {
       
   266     return StdMap<K, V, Compare>(map, value);
       
   267   }
   242 
   268 
   243   /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
   269   /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
   244   ///
   270   ///
   245   /// The current map has the <tt>[0..size-1]</tt> keyset and the values
   271   /// This map has the <tt>[0..size-1]</tt> keyset and the values
   246   /// are stored in a \c std::vector<T>  container. It can be used with
   272   /// are stored in a \c std::vector<T>  container. It can be used with
   247   /// some data structures, for example \c UnionFind, \c BinHeap, when 
   273   /// some data structures, for example \c UnionFind, \c BinHeap, when 
   248   /// the used items are small integer numbers. 
   274   /// the used items are small integer numbers.
       
   275   /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
   249   ///
   276   ///
   250   /// \todo Revise its name
   277   /// \todo Revise its name
   251   template <typename T>
   278   template <typename T>
   252   class IntegerMap {
   279   class IntegerMap : public MapBase<int, T> {
   253 
   280 
   254     template <typename T1>
   281     template <typename T1>
   255     friend class IntegerMap;
   282     friend class IntegerMap;
   256 
   283 
   257   public:
   284   public:
   258 
   285 
       
   286     typedef MapBase<int, T> Parent;
       
   287     ///\e
       
   288     typedef typename Parent::Key Key;
       
   289     ///\e
       
   290     typedef typename Parent::Value Value;
       
   291     ///\e
       
   292     typedef T& Reference;
       
   293     ///\e
       
   294     typedef const T& ConstReference;
       
   295 
   259     typedef True ReferenceMapTag;
   296     typedef True ReferenceMapTag;
   260     ///\e
       
   261     typedef int Key;
       
   262     ///\e
       
   263     typedef T Value;
       
   264     ///\e
       
   265     typedef T& Reference;
       
   266     ///\e
       
   267     typedef const T& ConstReference;
       
   268 
   297 
   269   private:
   298   private:
   270     
   299     
   271     typedef std::vector<T> Vector;
   300     typedef std::vector<T> Vector;
   272     Vector _vector;
   301     Vector _vector;
   274   public:
   303   public:
   275 
   304 
   276     /// Constructor with specified default value
   305     /// Constructor with specified default value
   277     IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
   306     IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
   278 
   307 
   279     /// \brief Constructs the map from an appropriate std::vector.
   308     /// \brief Constructs the map from an appropriate \c std::vector.
   280     template <typename T1>
   309     template <typename T1>
   281     IntegerMap(const std::vector<T1>& vector) 
   310     IntegerMap(const std::vector<T1>& vector) 
   282       : _vector(vector.begin(), vector.end()) {}
   311       : _vector(vector.begin(), vector.end()) {}
   283     
   312     
   284     /// \brief Constructs a map from an other IntegerMap.
   313     /// \brief Constructs a map from an other \ref IntegerMap.
   285     template <typename T1>
   314     template <typename T1>
   286     IntegerMap(const IntegerMap<T1> &c) 
   315     IntegerMap(const IntegerMap<T1> &c) 
   287       : _vector(c._vector.begin(), c._vector.end()) {}
   316       : _vector(c._vector.begin(), c._vector.end()) {}
   288 
   317 
   289     /// \brief Resize the container
   318     /// \brief Resize the container
   311     void set(const Key &k, const T& t) {
   340     void set(const Key &k, const T& t) {
   312       _vector[k] = t;
   341       _vector[k] = t;
   313     }
   342     }
   314 
   343 
   315   };
   344   };
       
   345   
       
   346   ///Returns an \c IntegerMap class
       
   347 
       
   348   ///This function just returns an \c IntegerMap class.
       
   349   ///\relates IntegerMap
       
   350   template<typename T>
       
   351   inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
       
   352     return IntegerMap<T>(size, value);
       
   353   }
   316 
   354 
   317   /// @}
   355   /// @}
   318 
   356 
   319   /// \addtogroup map_adaptors
   357   /// \addtogroup map_adaptors
   320   /// @{
   358   /// @{
   347   
   385   
   348 
   386 
   349   ///\brief Convert the \c Value of a map to another type using
   387   ///\brief Convert the \c Value of a map to another type using
   350   ///the default conversion.
   388   ///the default conversion.
   351   ///
   389   ///
   352   ///This \c concepts::ReadMap "read only map"
   390   ///This \ref concepts::ReadMap "read only map"
   353   ///converts the \c Value of a map to type \c T.
   391   ///converts the \c Value of a map to type \c T.
   354   ///Its \c Key is inherited from \c M.
   392   ///Its \c Key is inherited from \c M.
   355   template <typename M, typename T> 
   393   template <typename M, typename T> 
   356   class ConvertMap : public MapBase<typename M::Key, T> {
   394   class ConvertMap : public MapBase<typename M::Key, T> {
   357     const M& m;
   395     const M& m;
   364 
   402 
   365     ///Constructor.
   403     ///Constructor.
   366     ///\param _m is the underlying map.
   404     ///\param _m is the underlying map.
   367     ConvertMap(const M &_m) : m(_m) {};
   405     ConvertMap(const M &_m) : m(_m) {};
   368 
   406 
   369     /// \brief The subscript operator.
   407     ///\e
   370     ///
       
   371     /// The subscript operator.
       
   372     Value operator[](const Key& k) const {return m[k];}
   408     Value operator[](const Key& k) const {return m[k];}
   373   };
   409   };
   374   
   410   
   375   ///Returns a \c ConvertMap class
   411   ///Returns a \c ConvertMap class
   376 
   412 
   403     ///Constructor
   439     ///Constructor
   404     SimpleMap(const M &_m) : m(_m) {};
   440     SimpleMap(const M &_m) : m(_m) {};
   405     ///\e
   441     ///\e
   406     Value operator[](Key k) const {return m[k];}
   442     Value operator[](Key k) const {return m[k];}
   407   };
   443   };
       
   444   
       
   445   ///Returns a \c SimpleMap class
       
   446 
       
   447   ///This function just returns a \c SimpleMap class.
       
   448   ///\relates SimpleMap
       
   449   template<typename M>
       
   450   inline SimpleMap<M> simpleMap(const M &m) {
       
   451     return SimpleMap<M>(m);
       
   452   }
   408 
   453 
   409   ///Simple writable wrapping of a map
   454   ///Simple writable wrapping of a map
   410 
   455 
   411   ///This \ref concepts::WriteMap "write map" returns the simple
   456   ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
   412   ///wrapping of the given map. Sometimes the reference maps cannot be
   457   ///wrapping of the given map. Sometimes the reference maps cannot be
   413   ///combined with simple read-write maps. This map adaptor wraps the
   458   ///combined with simple read-write maps. This map adaptor wraps the
   414   ///given map to simple read-write map.
   459   ///given map to simple read-write map.
   415   ///
   460   ///
   416   ///\sa SimpleMap
   461   ///\sa SimpleMap
   431     Value operator[](Key k) const {return m[k];}
   476     Value operator[](Key k) const {return m[k];}
   432     ///\e
   477     ///\e
   433     void set(Key k, const Value& c) { m.set(k, c); }
   478     void set(Key k, const Value& c) { m.set(k, c); }
   434   };
   479   };
   435 
   480 
       
   481   ///Returns a \c SimpleWriteMap class
       
   482 
       
   483   ///This function just returns a \c SimpleWriteMap class.
       
   484   ///\relates SimpleWriteMap
       
   485   template<typename M>
       
   486   inline SimpleWriteMap<M> simpleWriteMap(M &m) {
       
   487     return SimpleWriteMap<M>(m);
       
   488   }
       
   489 
   436   ///Sum of two maps
   490   ///Sum of two maps
   437 
   491 
   438   ///This \c concepts::ReadMap "read only map" returns the sum of the two
   492   ///This \ref concepts::ReadMap "read only map" returns the sum of the two
   439   ///given maps.
   493   ///given maps.
   440   ///Its \c Key and \c Value are inherited from \c M1.
   494   ///Its \c Key and \c Value are inherited from \c M1.
   441   ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
   495   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   442   template<typename M1, typename M2> 
   496   template<typename M1, typename M2> 
   443   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   497   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   444     const M1& m1;
   498     const M1& m1;
   445     const M2& m2;
   499     const M2& m2;
   446 
   500 
   456   };
   510   };
   457   
   511   
   458   ///Returns an \c AddMap class
   512   ///Returns an \c AddMap class
   459 
   513 
   460   ///This function just returns an \c AddMap class.
   514   ///This function just returns an \c AddMap class.
   461   ///\todo How to call these type of functions?
   515   ///\todo Extend the documentation: how to call these type of functions?
   462   ///
   516   ///
   463   ///\relates AddMap
   517   ///\relates AddMap
   464   template<typename M1, typename M2> 
   518   template<typename M1, typename M2> 
   465   inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
   519   inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
   466     return AddMap<M1, M2>(m1,m2);
   520     return AddMap<M1, M2>(m1,m2);
   467   }
   521   }
   468 
   522 
   469   ///Shift a map with a constant.
   523   ///Shift a map with a constant.
   470 
   524 
   471   ///This \c concepts::ReadMap "read only map" returns the sum of the
   525   ///This \ref concepts::ReadMap "read only map" returns the sum of the
   472   ///given map and a constant value.
   526   ///given map and a constant value.
   473   ///Its \c Key and \c Value are inherited from \c M.
   527   ///Its \c Key and \c Value are inherited from \c M.
   474   ///
   528   ///
   475   ///Actually,
   529   ///Actually,
   476   ///\code
   530   ///\code
   502     Value operator[](Key k) const {return m[k] + v;}
   556     Value operator[](Key k) const {return m[k] + v;}
   503   };
   557   };
   504 
   558 
   505   ///Shift a map with a constant (ReadWrite version).
   559   ///Shift a map with a constant (ReadWrite version).
   506 
   560 
   507   ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
   561   ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
   508   ///given map and a constant value. It makes also possible to write the map.
   562   ///given map and a constant value. It makes also possible to write the map.
   509   ///Its \c Key and \c Value are inherited from \c M.
   563   ///Its \c Key and \c Value are inherited from \c M.
   510   ///
   564   ///
   511   ///\sa ShiftMap
   565   ///\sa ShiftMap
   512   template<typename M, typename C = typename M::Value> 
   566   template<typename M, typename C = typename M::Value> 
   548     return ShiftWriteMap<M, C>(m,v);
   602     return ShiftWriteMap<M, C>(m,v);
   549   }
   603   }
   550 
   604 
   551   ///Difference of two maps
   605   ///Difference of two maps
   552 
   606 
   553   ///This \c concepts::ReadMap "read only map" returns the difference
   607   ///This \ref concepts::ReadMap "read only map" returns the difference
   554   ///of the values of the two given maps.
   608   ///of the values of the two given maps.
   555   ///Its \c Key and \c Value are inherited from \c M1.
   609   ///Its \c Key and \c Value are inherited from \c M1.
   556   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   610   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   557   ///
   611   ///
   558   /// \todo Revise the misleading name
   612   /// \todo Revise the misleading name
   581     return SubMap<M1, M2>(m1, m2);
   635     return SubMap<M1, M2>(m1, m2);
   582   }
   636   }
   583 
   637 
   584   ///Product of two maps
   638   ///Product of two maps
   585 
   639 
   586   ///This \c concepts::ReadMap "read only map" returns the product of the
   640   ///This \ref concepts::ReadMap "read only map" returns the product of the
   587   ///values of the two given maps.
   641   ///values of the two given maps.
   588   ///Its \c Key and \c Value are inherited from \c M1.
   642   ///Its \c Key and \c Value are inherited from \c M1.
   589   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   643   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   590   template<typename M1, typename M2> 
   644   template<typename M1, typename M2> 
   591   class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
   645   class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
   611     return MulMap<M1, M2>(m1,m2);
   665     return MulMap<M1, M2>(m1,m2);
   612   }
   666   }
   613  
   667  
   614   ///Scales a map with a constant.
   668   ///Scales a map with a constant.
   615 
   669 
   616   ///This \c concepts::ReadMap "read only map" returns the value of the
   670   ///This \ref concepts::ReadMap "read only map" returns the value of the
   617   ///given map multiplied from the left side with a constant value.
   671   ///given map multiplied from the left side with a constant value.
   618   ///Its \c Key and \c Value are inherited from \c M.
   672   ///Its \c Key and \c Value are inherited from \c M.
   619   ///
   673   ///
   620   ///Actually,
   674   ///Actually,
   621   ///\code
   675   ///\code
   647     Value operator[](Key k) const {return v * m[k];}
   701     Value operator[](Key k) const {return v * m[k];}
   648   };
   702   };
   649 
   703 
   650   ///Scales a map with a constant (ReadWrite version).
   704   ///Scales a map with a constant (ReadWrite version).
   651 
   705 
   652   ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
   706   ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
   653   ///given map multiplied from the left side with a constant value. It can
   707   ///given map multiplied from the left side with a constant value. It can
   654   ///also be used as write map if the \c / operator is defined between
   708   ///also be used as write map if the \c / operator is defined between
   655   ///\c Value and \c C and the given multiplier is not zero.
   709   ///\c Value and \c C and the given multiplier is not zero.
   656   ///Its \c Key and \c Value are inherited from \c M.
   710   ///Its \c Key and \c Value are inherited from \c M.
   657   ///
   711   ///
   695     return ScaleWriteMap<M, C>(m,v);
   749     return ScaleWriteMap<M, C>(m,v);
   696   }
   750   }
   697 
   751 
   698   ///Quotient of two maps
   752   ///Quotient of two maps
   699 
   753 
   700   ///This \c concepts::ReadMap "read only map" returns the quotient of the
   754   ///This \ref concepts::ReadMap "read only map" returns the quotient of the
   701   ///values of the two given maps.
   755   ///values of the two given maps.
   702   ///Its \c Key and \c Value are inherited from \c M1.
   756   ///Its \c Key and \c Value are inherited from \c M1.
   703   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   757   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   704   template<typename M1, typename M2> 
   758   template<typename M1, typename M2> 
   705   class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
   759   class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
   725     return DivMap<M1, M2>(m1,m2);
   779     return DivMap<M1, M2>(m1,m2);
   726   }
   780   }
   727   
   781   
   728   ///Composition of two maps
   782   ///Composition of two maps
   729 
   783 
   730   ///This \c concepts::ReadMap "read only map" returns the composition of
   784   ///This \ref concepts::ReadMap "read only map" returns the composition of
   731   ///two given maps.
   785   ///two given maps.
   732   ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
   786   ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
   733   ///then for
   787   ///then for
   734   ///\code
   788   ///\code
   735   ///  ComposeMap<M1, M2> cm(m1,m2);
   789   ///  ComposeMap<M1, M2> cm(m1,m2);
   776   
   830   
   777   ///Combine of two maps using an STL (binary) functor.
   831   ///Combine of two maps using an STL (binary) functor.
   778 
   832 
   779   ///Combine of two maps using an STL (binary) functor.
   833   ///Combine of two maps using an STL (binary) functor.
   780   ///
   834   ///
   781   ///This \c concepts::ReadMap "read only map" takes two maps and a
   835   ///This \ref concepts::ReadMap "read only map" takes two maps and a
   782   ///binary functor and returns the composition of the two
   836   ///binary functor and returns the composition of the two
   783   ///given maps unsing the functor. 
   837   ///given maps unsing the functor. 
   784   ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
   838   ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
   785   ///and \c f is of \c F, then for
   839   ///and \c f is of \c F, then for
   786   ///\code
   840   ///\code
   849     return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
   903     return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
   850   }
   904   }
   851 
   905 
   852   ///Negative value of a map
   906   ///Negative value of a map
   853 
   907 
   854   ///This \c concepts::ReadMap "read only map" returns the negative
   908   ///This \ref concepts::ReadMap "read only map" returns the negative
   855   ///value of the value returned by the given map.
   909   ///value of the value returned by the given map.
   856   ///Its \c Key and \c Value are inherited from \c M.
   910   ///Its \c Key and \c Value are inherited from \c M.
   857   ///The unary \c - operator must be defined for \c Value, of course.
   911   ///The unary \c - operator must be defined for \c Value, of course.
   858   ///
   912   ///
   859   ///\sa NegWriteMap
   913   ///\sa NegWriteMap
   871     Value operator[](Key k) const {return -m[k];}
   925     Value operator[](Key k) const {return -m[k];}
   872   };
   926   };
   873   
   927   
   874   ///Negative value of a map (ReadWrite version)
   928   ///Negative value of a map (ReadWrite version)
   875 
   929 
   876   ///This \c concepts::ReadWriteMap "read-write map" returns the negative
   930   ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
   877   ///value of the value returned by the given map.
   931   ///value of the value returned by the given map.
   878   ///Its \c Key and \c Value are inherited from \c M.
   932   ///Its \c Key and \c Value are inherited from \c M.
   879   ///The unary \c - operator must be defined for \c Value, of course.
   933   ///The unary \c - operator must be defined for \c Value, of course.
   880   ///
   934   ///
   881   /// \sa NegMap
   935   /// \sa NegMap
   913     return NegWriteMap<M>(m);
   967     return NegWriteMap<M>(m);
   914   }
   968   }
   915 
   969 
   916   ///Absolute value of a map
   970   ///Absolute value of a map
   917 
   971 
   918   ///This \c concepts::ReadMap "read only map" returns the absolute value
   972   ///This \ref concepts::ReadMap "read only map" returns the absolute value
   919   ///of the value returned by the given map.
   973   ///of the value returned by the given map.
   920   ///Its \c Key and \c Value are inherited from \c M. 
   974   ///Its \c Key and \c Value are inherited from \c M. 
   921   ///\c Value must be comparable to \c 0 and the unary \c -
   975   ///\c Value must be comparable to \c 0 and the unary \c -
   922   ///operator must be defined for it, of course.
   976   ///operator must be defined for it, of course.
   923   template<typename M> 
   977   template<typename M> 
   947     return AbsMap<M>(m);
  1001     return AbsMap<M>(m);
   948   }
  1002   }
   949 
  1003 
   950   ///Converts an STL style functor to a map
  1004   ///Converts an STL style functor to a map
   951 
  1005 
   952   ///This \c concepts::ReadMap "read only map" returns the value
  1006   ///This \ref concepts::ReadMap "read only map" returns the value
   953   ///of a given functor.
  1007   ///of a given functor.
   954   ///
  1008   ///
   955   ///Template parameters \c K and \c V will become its
  1009   ///Template parameters \c K and \c V will become its
   956   ///\c Key and \c Value. 
  1010   ///\c Key and \c Value. 
   957   ///In most cases they have to be given explicitly because a 
  1011   ///In most cases they have to be given explicitly because a 
   958   ///functor typically does not provide such typedefs.
  1012   ///functor typically does not provide \c argument_type and 
       
  1013   ///\c result_type typedefs.
   959   ///
  1014   ///
   960   ///Parameter \c F is the type of the used functor.
  1015   ///Parameter \c F is the type of the used functor.
   961   ///
  1016   ///
   962   ///\sa MapFunctor
  1017   ///\sa MapFunctor
   963   template<typename F, 
  1018   template<typename F, 
   978   
  1033   
   979   ///Returns a \c FunctorMap class
  1034   ///Returns a \c FunctorMap class
   980 
  1035 
   981   ///This function just returns a \c FunctorMap class.
  1036   ///This function just returns a \c FunctorMap class.
   982   ///
  1037   ///
   983   ///It is specialized for adaptable function classes and
  1038   ///This function is specialized for adaptable binary function
   984   ///C++ functions.
  1039   ///classes and C++ functions.
       
  1040   ///
   985   ///\relates FunctorMap
  1041   ///\relates FunctorMap
   986   template<typename K, typename V, typename F> inline 
  1042   template<typename K, typename V, typename F> inline 
   987   FunctorMap<F, K, V> functorMap(const F &f) {
  1043   FunctorMap<F, K, V> functorMap(const F &f) {
   988     return FunctorMap<F, K, V>(f);
  1044     return FunctorMap<F, K, V>(f);
   989   }
  1045   }
  1002 
  1058 
  1003 
  1059 
  1004   ///Converts a map to an STL style (unary) functor
  1060   ///Converts a map to an STL style (unary) functor
  1005 
  1061 
  1006   ///This class Converts a map to an STL style (unary) functor.
  1062   ///This class Converts a map to an STL style (unary) functor.
  1007   ///that is it provides an <tt>operator()</tt> to read its values.
  1063   ///That is it provides an <tt>operator()</tt> to read its values.
  1008   ///
  1064   ///
  1009   ///For the sake of convenience it also works as
  1065   ///For the sake of convenience it also works as
  1010   ///a ususal \c concepts::ReadMap "readable map",
  1066   ///a ususal \ref concepts::ReadMap "readable map",
  1011   ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
  1067   ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
  1012   ///
  1068   ///
  1013   ///\sa FunctorMap
  1069   ///\sa FunctorMap
  1014   template <typename M> 
  1070   template <typename M> 
  1015   class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
  1071   class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
  1037   template<typename M> 
  1093   template<typename M> 
  1038   inline MapFunctor<M> mapFunctor(const M &m) {
  1094   inline MapFunctor<M> mapFunctor(const M &m) {
  1039     return MapFunctor<M>(m);
  1095     return MapFunctor<M>(m);
  1040   }
  1096   }
  1041 
  1097 
  1042   ///Applies all map setting operations to two maps
  1098   ///Just readable version of \ref ForkWriteMap
  1043 
  1099 
  1044   ///This map has two \c concepts::ReadMap "readable map"
  1100   ///This map has two \ref concepts::ReadMap "readable map"
  1045   ///parameters and each read request will be passed just to the
  1101   ///parameters and each read request will be passed just to the
  1046   ///first map. This class is the just readable map type of the ForkWriteMap.
  1102   ///first map. This class is the just readable map type of \c ForkWriteMap.
  1047   ///
  1103   ///
  1048   ///The \c Key and \c Value are inherited from \c M1.
  1104   ///The \c Key and \c Value are inherited from \c M1.
  1049   ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
  1105   ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
  1050   ///
  1106   ///
  1051   ///\sa ForkWriteMap
  1107   ///\sa ForkWriteMap
  1052   ///
  1108   ///
  1053   /// \todo Why is it needed?
  1109   /// \todo Why is it needed?
  1054   template<typename  M1, typename M2> 
  1110   template<typename  M1, typename M2> 
  1067   };
  1123   };
  1068 
  1124 
  1069 
  1125 
  1070   ///Applies all map setting operations to two maps
  1126   ///Applies all map setting operations to two maps
  1071 
  1127 
  1072   ///This map has two \c concepts::WriteMap "writable map"
  1128   ///This map has two \ref concepts::WriteMap "writable map"
  1073   ///parameters and each write request will be passed to both of them.
  1129   ///parameters and each write request will be passed to both of them.
  1074   ///If \c M1 is also \c concepts::ReadMap "readable",
  1130   ///If \c M1 is also \ref concepts::ReadMap "readable",
  1075   ///then the read operations will return the
  1131   ///then the read operations will return the
  1076   ///corresponding values of \c M1.
  1132   ///corresponding values of \c M1.
  1077   ///
  1133   ///
  1078   ///The \c Key and \c Value are inherited from \c M1.
  1134   ///The \c Key and \c Value are inherited from \c M1.
  1079   ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
  1135   ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
  1080   ///
  1136   ///
  1081   ///\sa ForkMap
  1137   ///\sa ForkMap
  1082   template<typename  M1, typename M2> 
  1138   template<typename  M1, typename M2> 
  1083   class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
  1139   class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
  1084     M1& m1;
  1140     M1& m1;
  1118   
  1174   
  1119   /* ************* BOOL MAPS ******************* */
  1175   /* ************* BOOL MAPS ******************* */
  1120   
  1176   
  1121   ///Logical 'not' of a map
  1177   ///Logical 'not' of a map
  1122   
  1178   
  1123   ///This bool \c concepts::ReadMap "read only map" returns the 
  1179   ///This bool \ref concepts::ReadMap "read only map" returns the 
  1124   ///logical negation of the value returned by the given map.
  1180   ///logical negation of the value returned by the given map.
  1125   ///Its \c Key is inherited from \c M, its Value is \c bool.
  1181   ///Its \c Key is inherited from \c M, its \c Value is \c bool.
  1126   ///
  1182   ///
  1127   ///\sa NotWriteMap
  1183   ///\sa NotWriteMap
  1128   template <typename M> 
  1184   template <typename M> 
  1129   class NotMap : public MapBase<typename M::Key, bool> {
  1185   class NotMap : public MapBase<typename M::Key, bool> {
  1130     const M& m;
  1186     const M& m;
  1139     Value operator[](Key k) const {return !m[k];}
  1195     Value operator[](Key k) const {return !m[k];}
  1140   };
  1196   };
  1141 
  1197 
  1142   ///Logical 'not' of a map (ReadWrie version)
  1198   ///Logical 'not' of a map (ReadWrie version)
  1143   
  1199   
  1144   ///This bool \c concepts::ReadWriteMap "read-write map" returns the 
  1200   ///This bool \ref concepts::ReadWriteMap "read-write map" returns the 
  1145   ///logical negation of the value returned by the given map. When it is set,
  1201   ///logical negation of the value returned by the given map. When it is set,
  1146   ///the opposite value is set to the original map.
  1202   ///the opposite value is set to the original map.
  1147   ///Its \c Key is inherited from \c M, its Value is \c bool.
  1203   ///Its \c Key is inherited from \c M, its \c Value is \c bool.
  1148   ///
  1204   ///
  1149   ///\sa NotMap
  1205   ///\sa NotMap
  1150   template <typename M> 
  1206   template <typename M> 
  1151   class NotWriteMap : public MapBase<typename M::Key, bool> {
  1207   class NotWriteMap : public MapBase<typename M::Key, bool> {
  1152     M& m;
  1208     M& m;
  1207   }
  1263   }
  1208   
  1264   
  1209 
  1265 
  1210   /// \brief Writable bool map for logging each \c true assigned element
  1266   /// \brief Writable bool map for logging each \c true assigned element
  1211   ///
  1267   ///
  1212   /// Writable bool map for logging each \c true assigned element, i.e it
  1268   /// A \ref concepts::ReadWriteMap "read-write" bool map for logging 
  1213   /// copies all the keys set to \c true to the given iterator.
  1269   /// each \c true assigned element, i.e it copies all the keys set 
       
  1270   /// to \c true to the given iterator.
  1214   ///
  1271   ///
  1215   /// \note The container of the iterator should contain space 
  1272   /// \note The container of the iterator should contain space 
  1216   /// for each element.
  1273   /// for each element.
  1217   ///
  1274   ///
  1218   /// The following example shows how you can write the edges found by the Prim
  1275   /// The following example shows how you can write the edges found by 
  1219   /// algorithm directly
  1276   /// the \ref Prim algorithm directly to the standard output.
  1220   /// to the standard output.
       
  1221   ///\code
  1277   ///\code
  1222   /// typedef IdMap<Graph, Edge> EdgeIdMap;
  1278   /// typedef IdMap<Graph, Edge> EdgeIdMap;
  1223   /// EdgeIdMap edgeId(graph);
  1279   /// EdgeIdMap edgeId(graph);
  1224   ///
  1280   ///
  1225   /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
  1281   /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;