lemon/maps.h
changeset 2354 3609c77b77be
parent 2258 741995f3dbc4
child 2391 14a343be7a5a
equal deleted inserted replaced
26:fe91c7bf9ade 27:875a7eb83ec1
    27 
    27 
    28 ///\file
    28 ///\file
    29 ///\ingroup maps
    29 ///\ingroup maps
    30 ///\brief Miscellaneous property maps
    30 ///\brief Miscellaneous property maps
    31 ///
    31 ///
    32 ///\todo This file has the same name as the concept file in concept/,
    32 ///\todo This file has the same name as the concept file in concepts/,
    33 /// and this is not easily detectable in docs...
    33 /// and this is not easily detectable in docs...
    34 
    34 
    35 #include <map>
    35 #include <map>
    36 
    36 
    37 namespace lemon {
    37 namespace lemon {
   250   }
   250   }
   251   
   251   
   252 
   252 
   253   ///Convert the \c Value of a map to another type.
   253   ///Convert the \c Value of a map to another type.
   254 
   254 
   255   ///This \ref concept::ReadMap "read only map"
   255   ///This \ref concepts::ReadMap "read only map"
   256   ///converts the \c Value of a maps to type \c T.
   256   ///converts the \c Value of a maps to type \c T.
   257   ///Its \c Key is inherited from \c M.
   257   ///Its \c Key is inherited from \c M.
   258   template <typename M, typename T> 
   258   template <typename M, typename T> 
   259   class ConvertMap : public MapBase<typename M::Key, T> {
   259   class ConvertMap : public MapBase<typename M::Key, T> {
   260     const M& m;
   260     const M& m;
   287     return ConvertMap<M, T>(m);
   287     return ConvertMap<M, T>(m);
   288   }
   288   }
   289 
   289 
   290   ///Simple wrapping of the map
   290   ///Simple wrapping of the map
   291 
   291 
   292   ///This \ref concept::ReadMap "read only map" returns the simple
   292   ///This \ref concepts::ReadMap "read only map" returns the simple
   293   ///wrapping of the given map. Sometimes the reference maps cannot be
   293   ///wrapping of the given map. Sometimes the reference maps cannot be
   294   ///combined with simple read maps. This map adaptor wraps the given
   294   ///combined with simple read maps. This map adaptor wraps the given
   295   ///map to simple read map.
   295   ///map to simple read map.
   296   template<typename M> 
   296   template<typename M> 
   297   class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
   297   class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
   307     Value operator[](Key k) const {return m[k];}
   307     Value operator[](Key k) const {return m[k];}
   308   };
   308   };
   309 
   309 
   310   ///Simple writeable wrapping of the map
   310   ///Simple writeable wrapping of the map
   311 
   311 
   312   ///This \ref concept::ReadMap "read only map" returns the simple
   312   ///This \ref concepts::ReadMap "read only map" returns the simple
   313   ///wrapping of the given map. Sometimes the reference maps cannot be
   313   ///wrapping of the given map. Sometimes the reference maps cannot be
   314   ///combined with simple read-write maps. This map adaptor wraps the
   314   ///combined with simple read-write maps. This map adaptor wraps the
   315   ///given map to simple read-write map.
   315   ///given map to simple read-write map.
   316   template<typename M> 
   316   template<typename M> 
   317   class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
   317   class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
   328     void set(Key k, const Value& c) { m.set(k, c); }
   328     void set(Key k, const Value& c) { m.set(k, c); }
   329   };
   329   };
   330 
   330 
   331   ///Sum of two maps
   331   ///Sum of two maps
   332 
   332 
   333   ///This \ref concept::ReadMap "read only map" returns the sum of the two
   333   ///This \ref concepts::ReadMap "read only map" returns the sum of the two
   334   ///given maps. Its \c Key and \c Value will be inherited from \c M1.
   334   ///given maps. Its \c Key and \c Value will be inherited from \c M1.
   335   ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
   335   ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
   336 
   336 
   337   template<typename M1, typename M2> 
   337   template<typename M1, typename M2> 
   338   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   338   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
   361     return AddMap<M1, M2>(m1,m2);
   361     return AddMap<M1, M2>(m1,m2);
   362   }
   362   }
   363 
   363 
   364   ///Shift a map with a constant.
   364   ///Shift a map with a constant.
   365 
   365 
   366   ///This \ref concept::ReadMap "read only map" returns the sum of the
   366   ///This \ref concepts::ReadMap "read only map" returns the sum of the
   367   ///given map and a constant value.
   367   ///given map and a constant value.
   368   ///Its \c Key and \c Value is inherited from \c M.
   368   ///Its \c Key and \c Value is inherited from \c M.
   369   ///
   369   ///
   370   ///Actually,
   370   ///Actually,
   371   ///\code
   371   ///\code
   394     Value operator[](Key k) const {return m[k] + v;}
   394     Value operator[](Key k) const {return m[k] + v;}
   395   };
   395   };
   396 
   396 
   397   ///Shift a map with a constant.
   397   ///Shift a map with a constant.
   398 
   398 
   399   ///This \ref concept::ReadWriteMap "read-write map" returns the sum of the
   399   ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
   400   ///given map and a constant value. It makes also possible to write the map.
   400   ///given map and a constant value. It makes also possible to write the map.
   401   ///Its \c Key and \c Value is inherited from \c M.
   401   ///Its \c Key and \c Value is inherited from \c M.
   402   ///
   402   ///
   403   ///Actually,
   403   ///Actually,
   404   ///\code
   404   ///\code
   443     return ShiftWriteMap<M, C>(m,v);
   443     return ShiftWriteMap<M, C>(m,v);
   444   }
   444   }
   445 
   445 
   446   ///Difference of two maps
   446   ///Difference of two maps
   447 
   447 
   448   ///This \ref concept::ReadMap "read only map" returns the difference
   448   ///This \ref concepts::ReadMap "read only map" returns the difference
   449   ///of the values of the two
   449   ///of the values of the two
   450   ///given maps. Its \c Key and \c Value will be inherited from \c M1.
   450   ///given maps. Its \c Key and \c Value will be inherited from \c M1.
   451   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   451   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   452 
   452 
   453   template<typename M1, typename M2> 
   453   template<typename M1, typename M2> 
   474     return SubMap<M1, M2>(m1, m2);
   474     return SubMap<M1, M2>(m1, m2);
   475   }
   475   }
   476 
   476 
   477   ///Product of two maps
   477   ///Product of two maps
   478 
   478 
   479   ///This \ref concept::ReadMap "read only map" returns the product of the
   479   ///This \ref concepts::ReadMap "read only map" returns the product of the
   480   ///values of the two
   480   ///values of the two
   481   ///given
   481   ///given
   482   ///maps. Its \c Key and \c Value will be inherited from \c M1.
   482   ///maps. Its \c Key and \c Value will be inherited from \c M1.
   483   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   483   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   484 
   484 
   505     return MulMap<M1, M2>(m1,m2);
   505     return MulMap<M1, M2>(m1,m2);
   506   }
   506   }
   507  
   507  
   508   ///Scales a maps with a constant.
   508   ///Scales a maps with a constant.
   509 
   509 
   510   ///This \ref concept::ReadMap "read only map" returns the value of the
   510   ///This \ref concepts::ReadMap "read only map" returns the value of the
   511   ///given map multiplied from the left side with a constant value.
   511   ///given map multiplied from the left side with a constant value.
   512   ///Its \c Key and \c Value is inherited from \c M.
   512   ///Its \c Key and \c Value is inherited from \c M.
   513   ///
   513   ///
   514   ///Actually,
   514   ///Actually,
   515   ///\code
   515   ///\code
   538     Value operator[](Key k) const {return v * m[k];}
   538     Value operator[](Key k) const {return v * m[k];}
   539   };
   539   };
   540 
   540 
   541   ///Scales a maps with a constant.
   541   ///Scales a maps with a constant.
   542 
   542 
   543   ///This \ref concept::ReadWriteMap "read-write map" returns the value of the
   543   ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
   544   ///given map multiplied from the left side with a constant value. It can
   544   ///given map multiplied from the left side with a constant value. It can
   545   ///be used as write map also if the given multiplier is not zero.
   545   ///be used as write map also if the given multiplier is not zero.
   546   ///Its \c Key and \c Value is inherited from \c M.
   546   ///Its \c Key and \c Value is inherited from \c M.
   547   template<typename M, typename C = typename M::Value> 
   547   template<typename M, typename C = typename M::Value> 
   548   class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
   548   class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
   578     return ScaleWriteMap<M, C>(m,v);
   578     return ScaleWriteMap<M, C>(m,v);
   579   }
   579   }
   580 
   580 
   581   ///Quotient of two maps
   581   ///Quotient of two maps
   582 
   582 
   583   ///This \ref concept::ReadMap "read only map" returns the quotient of the
   583   ///This \ref concepts::ReadMap "read only map" returns the quotient of the
   584   ///values of the two
   584   ///values of the two
   585   ///given maps. Its \c Key and \c Value will be inherited from \c M1.
   585   ///given maps. Its \c Key and \c Value will be inherited from \c M1.
   586   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   586   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   587 
   587 
   588   template<typename M1, typename M2> 
   588   template<typename M1, typename M2> 
   608     return DivMap<M1, M2>(m1,m2);
   608     return DivMap<M1, M2>(m1,m2);
   609   }
   609   }
   610   
   610   
   611   ///Composition of two maps
   611   ///Composition of two maps
   612 
   612 
   613   ///This \ref concept::ReadMap "read only map" returns the composition of
   613   ///This \ref concepts::ReadMap "read only map" returns the composition of
   614   ///two
   614   ///two
   615   ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
   615   ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
   616   ///of \c M2,
   616   ///of \c M2,
   617   ///then for
   617   ///then for
   618   ///\code
   618   ///\code
   653   ///Combines of two maps using an STL (binary) functor.
   653   ///Combines of two maps using an STL (binary) functor.
   654 
   654 
   655   ///Combines of two maps using an STL (binary) functor.
   655   ///Combines of two maps using an STL (binary) functor.
   656   ///
   656   ///
   657   ///
   657   ///
   658   ///This \ref concept::ReadMap "read only map" takes two maps and a
   658   ///This \ref concepts::ReadMap "read only map" takes two maps and a
   659   ///binary functor and returns the composition of
   659   ///binary functor and returns the composition of
   660   ///the two
   660   ///the two
   661   ///given maps unsing the functor. 
   661   ///given maps unsing the functor. 
   662   ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
   662   ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
   663   ///and \c f is of \c F,
   663   ///and \c f is of \c F,
   725     return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
   725     return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
   726   }
   726   }
   727 
   727 
   728   ///Negative value of a map
   728   ///Negative value of a map
   729 
   729 
   730   ///This \ref concept::ReadMap "read only map" returns the negative
   730   ///This \ref concepts::ReadMap "read only map" returns the negative
   731   ///value of the
   731   ///value of the
   732   ///value returned by the
   732   ///value returned by the
   733   ///given map. Its \c Key and \c Value will be inherited from \c M.
   733   ///given map. Its \c Key and \c Value will be inherited from \c M.
   734   ///The unary \c - operator must be defined for \c Value, of course.
   734   ///The unary \c - operator must be defined for \c Value, of course.
   735 
   735 
   746     Value operator[](Key k) const {return -m[k];}
   746     Value operator[](Key k) const {return -m[k];}
   747   };
   747   };
   748   
   748   
   749   ///Negative value of a map
   749   ///Negative value of a map
   750 
   750 
   751   ///This \ref concept::ReadWriteMap "read-write map" returns the negative
   751   ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
   752   ///value of the value returned by the
   752   ///value of the value returned by the
   753   ///given map. Its \c Key and \c Value will be inherited from \c M.
   753   ///given map. Its \c Key and \c Value will be inherited from \c M.
   754   ///The unary \c - operator must be defined for \c Value, of course.
   754   ///The unary \c - operator must be defined for \c Value, of course.
   755 
   755 
   756   template<typename M> 
   756   template<typename M> 
   781     return NegWriteMap<M>(m);
   781     return NegWriteMap<M>(m);
   782   }
   782   }
   783 
   783 
   784   ///Absolute value of a map
   784   ///Absolute value of a map
   785 
   785 
   786   ///This \ref concept::ReadMap "read only map" returns the absolute value
   786   ///This \ref concepts::ReadMap "read only map" returns the absolute value
   787   ///of the
   787   ///of the
   788   ///value returned by the
   788   ///value returned by the
   789   ///given map. Its \c Key and \c Value will be inherited
   789   ///given map. Its \c Key and \c Value will be inherited
   790   ///from <tt>M</tt>. <tt>Value</tt>
   790   ///from <tt>M</tt>. <tt>Value</tt>
   791   ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
   791   ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
   830     return AbsMap<M>(m);
   830     return AbsMap<M>(m);
   831   }
   831   }
   832 
   832 
   833   ///Converts an STL style functor to a map
   833   ///Converts an STL style functor to a map
   834 
   834 
   835   ///This \ref concept::ReadMap "read only map" returns the value
   835   ///This \ref concepts::ReadMap "read only map" returns the value
   836   ///of a
   836   ///of a
   837   ///given map.
   837   ///given map.
   838   ///
   838   ///
   839   ///Template parameters \c K and \c V will become its
   839   ///Template parameters \c K and \c V will become its
   840   ///\c Key and \c Value. They must be given explicitely
   840   ///\c Key and \c Value. They must be given explicitely
   888 
   888 
   889   ///This class Converts a map to an STL style (unary) functor.
   889   ///This class Converts a map to an STL style (unary) functor.
   890   ///that is it provides an <tt>operator()</tt> to read its values.
   890   ///that is it provides an <tt>operator()</tt> to read its values.
   891   ///
   891   ///
   892   ///For the sake of convenience it also works as
   892   ///For the sake of convenience it also works as
   893   ///a ususal \ref concept::ReadMap "readable map",
   893   ///a ususal \ref concepts::ReadMap "readable map",
   894   ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
   894   ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
   895 
   895 
   896   template <typename M> 
   896   template <typename M> 
   897   class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
   897   class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
   898     const M& m;
   898     const M& m;
   923     return MapFunctor<M>(m);
   923     return MapFunctor<M>(m);
   924   }
   924   }
   925 
   925 
   926   ///Applies all map setting operations to two maps
   926   ///Applies all map setting operations to two maps
   927 
   927 
   928   ///This map has two \ref concept::ReadMap "readable map"
   928   ///This map has two \ref concepts::ReadMap "readable map"
   929   ///parameters and each read request will be passed just to the
   929   ///parameters and each read request will be passed just to the
   930   ///first map. This class is the just readable map type of the ForkWriteMap.
   930   ///first map. This class is the just readable map type of the ForkWriteMap.
   931   ///
   931   ///
   932   ///The \c Key and \c Value will be inherited from \c M1.
   932   ///The \c Key and \c Value will be inherited from \c M1.
   933   ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
   933   ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
   947   };
   947   };
   948 
   948 
   949 
   949 
   950   ///Applies all map setting operations to two maps
   950   ///Applies all map setting operations to two maps
   951 
   951 
   952   ///This map has two \ref concept::WriteMap "writable map"
   952   ///This map has two \ref concepts::WriteMap "writable map"
   953   ///parameters and each write request will be passed to both of them.
   953   ///parameters and each write request will be passed to both of them.
   954   ///If \c M1 is also \ref concept::ReadMap "readable",
   954   ///If \c M1 is also \ref concepts::ReadMap "readable",
   955   ///then the read operations will return the
   955   ///then the read operations will return the
   956   ///corresponding values of \c M1.
   956   ///corresponding values of \c M1.
   957   ///
   957   ///
   958   ///The \c Key and \c Value will be inherited from \c M1.
   958   ///The \c Key and \c Value will be inherited from \c M1.
   959   ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
   959   ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
   994   
   994   
   995   /* ************* BOOL MAPS ******************* */
   995   /* ************* BOOL MAPS ******************* */
   996   
   996   
   997   ///Logical 'not' of a map
   997   ///Logical 'not' of a map
   998   
   998   
   999   ///This bool \ref concept::ReadMap "read only map" returns the 
   999   ///This bool \ref concepts::ReadMap "read only map" returns the 
  1000   ///logical negation of
  1000   ///logical negation of
  1001   ///value returned by the
  1001   ///value returned by the
  1002   ///given map. Its \c Key and will be inherited from \c M,
  1002   ///given map. Its \c Key and will be inherited from \c M,
  1003   ///its Value is <tt>bool</tt>.
  1003   ///its Value is <tt>bool</tt>.
  1004 
  1004 
  1015     Value operator[](Key k) const {return !m[k];}
  1015     Value operator[](Key k) const {return !m[k];}
  1016   };
  1016   };
  1017 
  1017 
  1018   ///Logical 'not' of a map with writing possibility
  1018   ///Logical 'not' of a map with writing possibility
  1019   
  1019   
  1020   ///This bool \ref concept::ReadWriteMap "read-write map" returns the 
  1020   ///This bool \ref concepts::ReadWriteMap "read-write map" returns the 
  1021   ///logical negation of value returned by the given map. When it is set,
  1021   ///logical negation of value returned by the given map. When it is set,
  1022   ///the opposite value is set to the original map.
  1022   ///the opposite value is set to the original map.
  1023   ///Its \c Key and will be inherited from \c M,
  1023   ///Its \c Key and will be inherited from \c M,
  1024   ///its Value is <tt>bool</tt>.
  1024   ///its Value is <tt>bool</tt>.
  1025   template <typename M> 
  1025   template <typename M>