lemon-0.x: src/lemon/maps.h@bedab8bd915f

     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) const {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   ///Shift a maps with a constant.

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

   218   ///given map and a constant value.

   219   ///Its \c Key and \c Value is inherited from \c M.

   220   ///

   221   ///Actually,

   222   ///\code

   223   ///  ShiftMap<X> sh(x,v);

   224   ///\endcode

   225   ///it is equivalent with

   226   ///\code

   227   ///  ConstMap<X::Key, X::Value> c_tmp(v);

   228   ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);

   229   ///\endcode

   230   template<class M>

   231   class ShiftMap

   232   {

   233     const M &m;

   234     typename M::Value v;

   235   public:

   236     typedef typename M::Key Key;

   237     typedef typename M::Value Value;

   239     ///Constructor

   241     ///Constructor

   242     ///\param _m is the undelying map

   243     ///\param _v is the shift value

   244     ShiftMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};

   245     Value operator[](Key k) const {return m[k]+v;}

   246   };

   248   ///Returns an \ref ShiftMap class

   250   ///This function just returns an \ref ShiftMap class.

   251   ///\relates ShiftMap

   252   ///\todo A better name is required.

   253   template<class M>

   254   inline ShiftMap<M> shiftMap(const M &m,const typename M::Value &v)

   255   {

   256     return ShiftMap<M>(m,v);

   257   }

   259   ///Difference of two maps

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

   262   ///of the values returned by the two

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

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

   266   template<class M1,class M2>

   267   class SubMap

   268   {

   269     const M1 &m1;

   270     const M2 &m2;

   271   public:

   272     typedef typename M1::Key Key;

   273     typedef typename M1::Value Value;

   275     ///Constructor

   277     ///\e

   278     ///

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

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

   281   };

   283   ///Returns a \ref SubMap class

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

   286   ///

   287   ///\relates SubMap

   288   template<class M1,class M2>

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

   290   {

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

   292   }

   294   ///Product of two maps

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

   297   ///values returned by the two

   298   ///given

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

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

   302   template<class M1,class M2>

   303   class MulMap

   304   {

   305     const M1 &m1;

   306     const M2 &m2;

   307   public:

   308     typedef typename M1::Key Key;

   309     typedef typename M1::Value Value;

   311     ///Constructor

   313     ///\e

   314     ///

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

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

   317   };

   319   ///Returns a \ref MulMap class

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

   322   ///\relates MulMap

   323   template<class M1,class M2>

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

   325   {

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

   327   }

   329   ///Scale a maps with a constant.

   331   ///This \ref concept::ReadMap "read only map" returns the value of the

   332   ///given map multipied with a constant value.

   333   ///Its \c Key and \c Value is inherited from \c M.

   334   ///

   335   ///Actually,

   336   ///\code

   337   ///  ScaleMap<X> sc(x,v);

   338   ///\endcode

   339   ///it is equivalent with

   340   ///\code

   341   ///  ConstMap<X::Key, X::Value> c_tmp(v);

   342   ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);

   343   ///\endcode

   344   template<class M>

   345   class ScaleMap

   346   {

   347     const M &m;

   348     typename M::Value v;

   349   public:

   350     typedef typename M::Key Key;

   351     typedef typename M::Value Value;

   353     ///Constructor

   355     ///Constructor

   356     ///\param _m is the undelying map

   357     ///\param _v is the scaling value

   358     ScaleMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};

   359     Value operator[](Key k) const {return m[k]*v;}

   360   };

   362   ///Returns an \ref ScaleMap class

   364   ///This function just returns an \ref ScaleMap class.

   365   ///\relates ScaleMap

   366   ///\todo A better name is required.

   367   template<class M>

   368   inline ScaleMap<M> scaleMap(const M &m,const typename M::Value &v)

   369   {

   370     return ScaleMap<M>(m,v);

   371   }

   373   ///Quotient of two maps

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

   376   ///values returned by the two

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

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

   380   template<class M1,class M2>

   381   class DivMap

   382   {

   383     const M1 &m1;

   384     const M2 &m2;

   385   public:

   386     typedef typename M1::Key Key;

   387     typedef typename M1::Value Value;

   389     ///Constructor

   391     ///\e

   392     ///

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

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

   395   };

   397   ///Returns a \ref DivMap class

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

   400   ///\relates DivMap

   401   template<class M1,class M2>

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

   403   {

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

   405   }

   407   ///Composition of two maps

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

   410   ///two

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

   412   ///of \c M2,

   413   ///then for

   414   ///\code

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

   416   ///\endcode

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

   418   ///

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

   420   ///\c M1.

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

   422   ///\todo Check the requirements.

   424   template<class M1,class M2>

   425   class ComposeMap

   426   {

   427     const M1 &m1;

   428     const M2 &m2;

   429   public:

   430     typedef typename M2::Key Key;

   431     typedef typename M1::Value Value;

   433     ///Constructor

   435     ///\e

   436     ///

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

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

   439   };

   441   ///Returns a \ref ComposeMap class

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

   444   ///\relates ComposeMap

   445   template<class M1,class M2>

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

   447   {

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

   449   }

   451   ///Negative value of a map

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

   454   ///value of the

   455   ///value returned by the

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

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

   459   template<class M>

   460   class NegMap

   461   {

   462     const M &m;

   463   public:

   464     typedef typename M::Key Key;

   465     typedef typename M::Value Value;

   467     ///Constructor

   469     ///\e

   470     ///

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

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

   473   };

   475   ///Returns a \ref NegMap class

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

   478   ///\relates NegMap

   479   template<class M>

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

   481   {

   482     return NegMap<M>(m);

   483   }

   486   ///Absolute value of a map

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

   489   ///of the

   490   ///value returned by the

   491   ///given map. Its \c Key and \c Value will be inherited

   492   ///from <tt>M</tt>. <tt>Value</tt>

   493   ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>

   494   ///operator must be defined for it, of course.

   495   ///

   496   ///\bug We need a unified way to handle the situation below:

   497   ///\code

   498   ///  struct _UnConvertible {};

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

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

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

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

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

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

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

   506   ///\endcode

   509   template<class M>

   510   class AbsMap

   511   {

   512     const M &m;

   513   public:

   514     typedef typename M::Key Key;

   515     typedef typename M::Value Value;

   517     ///Constructor

   519     ///\e

   520     ///

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

   522     Value operator[](Key k) const {Value tmp=m[k]; return tmp>=0?tmp:-tmp;}

   523   };

   525   ///Returns a \ref AbsMap class

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

   528   ///\relates AbsMap

   529   template<class M>

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

   531   {

   532     return AbsMap<M>(m);

   533   }

   535   /// @}

   537 }

   540 #endif // LEMON_MAPS_H

author	alpar
	Tue, 11 Jan 2005 09:15:25 +0000
changeset 1073	bedab8bd915f
parent 1044	f97380557656
child 1076	67a115cdade4
permissions	-rw-r--r--