lemon-0.x: src/lemon/maps.h@9d503ce002db

     1 /* -*- C++ -*-

     2  * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Combinatorial Optimization Research Group, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    17 #ifndef LEMON_MAPS_H

    18 #define LEMON_MAPS_H

    20 #include<math.h>

    22 ///\file

    23 ///\ingroup maps

    24 ///\brief Miscellaneous property maps

    25 ///

    26 ///\todo This file has the same name as the concept file in concept/,

    27 /// and this is not easily detectable in docs...

    29 #include <map>

    31 namespace lemon {

    33   /// \addtogroup maps

    34   /// @{

    36   /// Base class of maps.

    38   /// Base class of maps.

    39   /// It provides the necessary <tt>typedef</tt>s required by the map concept.

    40   template<typename K, typename T>

    41   class MapBase

    42   {

    43   public:

    44     ///\e

    45     typedef K Key;

    46     ///\e

    47     typedef T Value;

    48   };

    50   /// Null map. (a.k.a. DoNothingMap)

    52   /// If you have to provide a map only for its type definitions,

    53   /// or if you have to provide a writable map, but

    54   /// data written to it will sent to <tt>/dev/null</tt>...

    55   template<typename K, typename T>

    56   class NullMap : public MapBase<K,T>

    57   {

    58   public:

    60     /// Gives back a default constructed element.

    61     T operator[](const K&) const { return T(); }

    62     /// Absorbs the value.

    63     void set(const K&, const T&) {}

    64   };

    67   /// Constant map.

    69   /// This is a readable map which assigns a specified value to each key.

    70   /// In other aspects it is equivalent to the \ref NullMap.

    71   /// \todo set could be used to set the value.

    72   template<typename K, typename T>

    73   class ConstMap : public MapBase<K,T>

    74   {

    75     T v;

    76   public:

    78     /// Default constructor

    80     /// The value of the map will be uninitialized.

    81     /// (More exactly it will be default constructed.)

    82     ConstMap() {}

    83     ///\e

    85     /// \param _v The initial value of the map.

    86     ///

    87     ConstMap(const T &_v) : v(_v) {}

    89     T operator[](const K&) const { return v; }

    90     void set(const K&, const T&) {}

    92     template<typename T1>

    93     struct rebind {

    94       typedef ConstMap<K,T1> other;

    95     };

    97     template<typename T1>

    98     ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}

    99   };

   101   //to document later

   102   template<typename T, T v>

   103   struct Const { };

   104   //to document later

   105   template<typename K, typename V, V v>

   106   class ConstMap<K, Const<V, v> > : public MapBase<K, V>

   107   {

   108   public:

   109     ConstMap() { }

   110     V operator[](const K&) const { return v; }

   111     void set(const K&, const V&) { }

   112   };

   114   /// \c std::map wrapper

   116   /// This is essentially a wrapper for \c std::map. With addition that

   117   /// you can specify a default value different from \c Value() .

   118   ///

   119   /// \todo Provide allocator parameter...

   120   template <typename K, typename T, typename Compare = std::less<K> >

   121   class StdMap : public std::map<K,T,Compare> {

   122     typedef std::map<K,T,Compare> parent;

   123     T v;

   124     typedef typename parent::value_type PairType;

   126   public:

   127     typedef K Key;

   128     typedef T Value;

   129     typedef T& Reference;

   130     typedef const T& ConstReference;

   133     StdMap() : v() {}

   134     /// Constructor with specified default value

   135     StdMap(const T& _v) : v(_v) {}

   137     /// \brief Constructs the map from an appropriate std::map.

   138     ///

   139     /// \warning Inefficient: copies the content of \c m !

   140     StdMap(const parent &m) : parent(m) {}

   141     /// \brief Constructs the map from an appropriate std::map, and explicitly

   142     /// specifies a default value.

   143     ///

   144     /// \warning Inefficient: copies the content of \c m !

   145     StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}

   147     template<typename T1, typename Comp1>

   148     StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {

   149       //FIXME;

   150     }

   152     Reference operator[](const Key &k) {

   153       return insert(PairType(k,v)).first -> second;

   154     }

   155     ConstReference operator[](const Key &k) const {

   156       typename parent::iterator i = lower_bound(k);

   157       if (i == parent::end() || parent::key_comp()(k, (*i).first))

   158 	return v;

   159       return (*i).second;

   160     }

   161     void set(const Key &k, const T &t) {

   162       parent::operator[](k) = t;

   163     }

   165     /// Changes the default value of the map.

   166     /// \return Returns the previous default value.

   167     ///

   168     /// \warning The value of some keys (which has already been queried, but

   169     /// the value has been unchanged from the default) may change!

   170     T setDefault(const T &_v) { T old=v; v=_v; return old; }

   172     template<typename T1>

   173     struct rebind {

   174       typedef StdMap<Key,T1,Compare> other;

   175     };

   176   };

   179   ///Sum of two maps

   181   ///This \ref concept::ReadMap "read only map" returns the sum of the two

   182   ///given maps. Its \c Key and \c Value will be inherited from \c M1.

   183   ///The \c Key and \c Value of M2 must be convertible to those of \c M1.

   185   template<class M1,class M2>

   186   class AddMap

   187   {

   188     const M1 &m1;

   189     const M2 &m2;

   190   public:

   191     typedef typename M1::Key Key;

   192     typedef typename M1::Value Value;

   194     ///Constructor

   196     ///\e

   197     ///

   198     AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};

   199     Value operator[](Key k) {return m1[k]+m2[k];}

   200   };

   202   ///Returns an \ref AddMap class

   204   ///This function just returns an \ref AddMap class.

   205   ///\todo How to call these type of functions?

   206   ///

   207   ///\relates AddMap

   208   ///\todo Wrong scope in Doxygen when \c \\relates is used

   209   template<class M1,class M2>

   210   inline AddMap<M1,M2> addMap(const M1 &m1,const M2 &m2)

   211   {

   212     return AddMap<M1,M2>(m1,m2);

   213   }

   215   ///Difference of two maps

   217   ///This \ref concept::ReadMap "read only map" returns the difference

   218   ///of the values returned by the two

   219   ///given maps. Its \c Key and \c Value will be inherited from \c M1.

   220   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.

   222   template<class M1,class M2>

   223   class SubMap

   224   {

   225     const M1 &m1;

   226     const M2 &m2;

   227   public:

   228     typedef typename M1::Key Key;

   229     typedef typename M1::Value Value;

   231     ///Constructor

   233     ///\e

   234     ///

   235     SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};

   236     Value operator[](Key k) {return m1[k]-m2[k];}

   237   };

   239   ///Returns a \ref SubMap class

   241   ///This function just returns a \ref SubMap class.

   242   ///

   243   ///\relates SubMap

   244   template<class M1,class M2>

   245   inline SubMap<M1,M2> subMap(const M1 &m1,const M2 &m2)

   246   {

   247     return SubMap<M1,M2>(m1,m2);

   248   }

   250   ///Product of two maps

   252   ///This \ref concept::ReadMap "read only map" returns the product of the

   253   ///values returned by the two

   254   ///given

   255   ///maps. Its \c Key and \c Value will be inherited from \c M1.

   256   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.

   258   template<class M1,class M2>

   259   class MulMap

   260   {

   261     const M1 &m1;

   262     const M2 &m2;

   263   public:

   264     typedef typename M1::Key Key;

   265     typedef typename M1::Value Value;

   267     ///Constructor

   269     ///\e

   270     ///

   271     MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};

   272     Value operator[](Key k) {return m1[k]*m2[k];}

   273   };

   275   ///Returns a \ref MulMap class

   277   ///This function just returns a \ref MulMap class.

   278   ///\relates MulMap

   279   template<class M1,class M2>

   280   inline MulMap<M1,M2> mulMap(const M1 &m1,const M2 &m2)

   281   {

   282     return MulMap<M1,M2>(m1,m2);

   283   }

   285   ///Quotient of two maps

   287   ///This \ref concept::ReadMap "read only map" returns the quotient of the

   288   ///values returned by the two

   289   ///given maps. Its \c Key and \c Value will be inherited from \c M1.

   290   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.

   292   template<class M1,class M2>

   293   class DivMap

   294   {

   295     const M1 &m1;

   296     const M2 &m2;

   297   public:

   298     typedef typename M1::Key Key;

   299     typedef typename M1::Value Value;

   301     ///Constructor

   303     ///\e

   304     ///

   305     DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};

   306     Value operator[](Key k) {return m1[k]/m2[k];}

   307   };

   309   ///Returns a \ref DivMap class

   311   ///This function just returns a \ref DivMap class.

   312   ///\relates DivMap

   313   template<class M1,class M2>

   314   inline DivMap<M1,M2> divMap(const M1 &m1,const M2 &m2)

   315   {

   316     return DivMap<M1,M2>(m1,m2);

   317   }

   319   ///Composition of two maps

   321   ///This \ref concept::ReadMap "read only map" returns the composition of

   322   ///two

   323   ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is

   324   ///of \c M2,

   325   ///then for

   326   ///\code

   327   ///  ComposeMap<M1,M2> cm(m1,m2);

   328   ///\endcode

   329   ///<tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>

   330   ///

   331   ///Its \c Key is inherited from \c M2 and its \c Value is from

   332   ///\c M1.

   333   ///The \c M2::Value must be convertible to \c M1::Key.

   334   ///\todo Check the requirements.

   336   template<class M1,class M2>

   337   class ComposeMap

   338   {

   339     const M1 &m1;

   340     const M2 &m2;

   341   public:

   342     typedef typename M2::Key Key;

   343     typedef typename M1::Value Value;

   345     ///Constructor

   347     ///\e

   348     ///

   349     ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};

   350     Value operator[](Key k) {return m1[m2[k]];}

   351   };

   353   ///Returns a \ref ComposeMap class

   355   ///This function just returns a \ref ComposeMap class.

   356   ///\relates ComposeMap

   357   template<class M1,class M2>

   358   inline ComposeMap<M1,M2> composeMap(const M1 &m1,const M2 &m2)

   359   {

   360     return ComposeMap<M1,M2>(m1,m2);

   361   }

   363   ///Negative value of a map

   365   ///This \ref concept::ReadMap "read only map" returns the negative

   366   ///value of the

   367   ///value returned by the

   368   ///given map. Its \c Key and \c Value will be inherited from \c M.

   369   ///The unary \c - operator must be defined for \c Value, of course.

   371   template<class M>

   372   class NegMap

   373   {

   374     const M &m;

   375   public:

   376     typedef typename M::Key Key;

   377     typedef typename M::Value Value;

   379     ///Constructor

   381     ///\e

   382     ///

   383     NegMap(const M &_m) : m(_m) {};

   384     Value operator[](Key k) {return -m[k];}

   385   };

   387   ///Returns a \ref NegMap class

   389   ///This function just returns a \ref NegMap class.

   390   ///\relates NegMap

   391   template<class M>

   392   inline NegMap<M> negMap(const M &m)

   393   {

   394     return NegMap<M>(m);

   395   }

   398   //\todo We need a unified way to handle the situation below!

   399   struct _UnConvertible {};

   400   template<class A> inline A t_abs(A a) {return _UnConvertible();}

   402   template<> inline int t_abs<>(int n) {return abs(n);}

   403   template<> inline long int t_abs<>(long int n) {return labs(n);}

   404   //\bug llabs() is overloaded

   405   template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}

   407   template<> inline float t_abs<>(float n) {return fabsf(n);}

   408   template<> inline double t_abs<>(double n) {return fabs(n);}

   409   template<> inline long double t_abs<>(long double n) {return fabsl(n);}

   411   ///Absolute value of a map

   413   ///This \ref concept::ReadMap "read only map" returns the absolute value

   414   ///of the

   415   ///value returned by the

   416   ///given map. Its \c Key and \c Value will be inherited from \c M.

   417   ///The function <tt>Value abs(Value)<tt> must be defined, of course.

   419   template<class M>

   420   class AbsMap

   421   {

   422     const M &m;

   423   public:

   424     typedef typename M::Key Key;

   425     typedef typename M::Value Value;

   427     ///Constructor

   429     ///\e

   430     ///

   431     AbsMap(const M &_m) : m(_m) {};

   432     Value operator[](Key k) {return t_abs(m[k]);}

   433   };

   435   ///Returns a \ref AbsMap class

   437   ///This function just returns a \ref AbsMap class.

   438   ///\relates AbsMap

   439   template<class M>

   440   inline AbsMap<M> absMap(const M &m)

   441   {

   442     return AbsMap<M>(m);

   443   }

   445   /// @}

   447 }

   450 #endif // LEMON_MAPS_H

author	alpar
	Mon, 03 Jan 2005 16:19:46 +0000
changeset 1041	9d503ce002db
parent 987	87f7c54892df
child 1044	f97380557656
permissions	-rw-r--r--