COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/maps.h @ 1075:789bad021e2d

Last change on this file since 1075:789bad021e2d was 1070:6aa1520a0f2f, checked in by Alpar Juttner, 15 years ago

ShiftMap? and ScaleMap? added

File size: 13.6 KB
Line 
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 */
16
17#ifndef LEMON_MAPS_H
18#define LEMON_MAPS_H
19
20#include<math.h>
21
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...
28
29#include <map>
30
31namespace lemon {
32
33  /// \addtogroup maps
34  /// @{
35
36  /// Base class of maps.
37
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  };
49
50  /// Null map. (a.k.a. DoNothingMap)
51
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:
59
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  };
65
66
67  /// Constant map.
68
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:
77
78    /// Default constructor
79
80    /// The value of the map will be uninitialized.
81    /// (More exactly it will be default constructed.)
82    ConstMap() {}
83    ///\e
84
85    /// \param _v The initial value of the map.
86    ///
87    ConstMap(const T &_v) : v(_v) {}
88
89    T operator[](const K&) const { return v; }
90    void set(const K&, const T&) {}
91
92    template<typename T1>
93    struct rebind {
94      typedef ConstMap<K,T1> other;
95    };
96
97    template<typename T1>
98    ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}
99  };
100
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  };
113
114  /// \c std::map wrapper
115
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;
125
126  public:
127    typedef K Key;
128    typedef T Value;
129    typedef T& Reference;
130    typedef const T& ConstReference;
131
132
133    StdMap() : v() {}
134    /// Constructor with specified default value
135    StdMap(const T& _v) : v(_v) {}
136
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) {}
146   
147    template<typename T1, typename Comp1>
148    StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {
149      //FIXME;
150    }
151
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    }
164
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; }
171
172    template<typename T1>
173    struct rebind {
174      typedef StdMap<Key,T1,Compare> other;
175    };
176  };
177
178
179  ///Sum of two maps
180
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.
184
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;
193
194    ///Constructor
195
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  };
201 
202  ///Returns an \ref AddMap class
203
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  }
214
215  ///Shift a maps with a constant.
216
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;
238
239    ///Constructor
240
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  };
247 
248  ///Returns an \ref ShiftMap class
249
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  }
258
259  ///Difference of two maps
260
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.
265
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;
274
275    ///Constructor
276
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  };
282 
283  ///Returns a \ref SubMap class
284
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  }
293
294  ///Product of two maps
295
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.
301
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;
310
311    ///Constructor
312
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  };
318 
319  ///Returns a \ref MulMap class
320
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  }
328 
329  ///Scale a maps with a constant.
330
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;
352
353    ///Constructor
354
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  };
361 
362  ///Returns an \ref ScaleMap class
363
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  }
372
373  ///Quotient of two maps
374
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.
379
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;
388
389    ///Constructor
390
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  };
396 
397  ///Returns a \ref DivMap class
398
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  }
406 
407  ///Composition of two maps
408
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.
423
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;
432
433    ///Constructor
434
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  };
440 
441  ///Returns a \ref ComposeMap class
442
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  }
450
451  ///Negative value of a map
452
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.
458
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;
466
467    ///Constructor
468
469    ///\e
470    ///
471    NegMap(const M &_m) : m(_m) {};
472    Value operator[](Key k) const {return -m[k];}
473  };
474 
475  ///Returns a \ref NegMap class
476
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  }
484
485
486  ///Absolute value of a map
487
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
507 
508
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;
516
517    ///Constructor
518
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  };
524 
525  ///Returns a \ref AbsMap class
526
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  }
534
535  /// @}
536 
537}
538
539
540#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.