COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/maps.h @ 1044:f97380557656

Last change on this file since 1044:f97380557656 was 1044:f97380557656, checked in by Alpar Juttner, 15 years ago
  • Missing 'const' keywords added
  • Stupid implementation of 'AbsMap?' has been corrected.
File size: 11.4 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  ///Difference of two maps
216
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.
221
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;
230
231    ///Constructor
232
233    ///\e
234    ///
235    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
236    Value operator[](Key k) const {return m1[k]-m2[k];}
237  };
238 
239  ///Returns a \ref SubMap class
240
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  }
249
250  ///Product of two maps
251
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.
257
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;
266
267    ///Constructor
268
269    ///\e
270    ///
271    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
272    Value operator[](Key k) const {return m1[k]*m2[k];}
273  };
274 
275  ///Returns a \ref MulMap class
276
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  }
284 
285  ///Quotient of two maps
286
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.
291
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;
300
301    ///Constructor
302
303    ///\e
304    ///
305    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
306    Value operator[](Key k) const {return m1[k]/m2[k];}
307  };
308 
309  ///Returns a \ref DivMap class
310
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  }
318 
319  ///Composition of two maps
320
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.
335
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;
344
345    ///Constructor
346
347    ///\e
348    ///
349    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
350    Value operator[](Key k) const {return m1[m2[k]];}
351  };
352 
353  ///Returns a \ref ComposeMap class
354
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  }
362
363  ///Negative value of a map
364
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.
370
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;
378
379    ///Constructor
380
381    ///\e
382    ///
383    NegMap(const M &_m) : m(_m) {};
384    Value operator[](Key k) const {return -m[k];}
385  };
386 
387  ///Returns a \ref NegMap class
388
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  }
396
397
398  ///Absolute value of a map
399
400  ///This \ref concept::ReadMap "read only map" returns the absolute value
401  ///of the
402  ///value returned by the
403  ///given map. Its \c Key and \c Value will be inherited
404  ///from <tt>M</tt>. <tt>Value</tt>
405  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
406  ///operator must be defined for it, of course.
407  ///
408  ///\bug We need a unified way to handle the situation below:
409  ///\code
410  ///  struct _UnConvertible {};
411  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
412  ///  template<> inline int t_abs<>(int n) {return abs(n);}
413  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
414  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
415  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
416  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
417  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
418  ///\endcode
419 
420
421  template<class M>
422  class AbsMap
423  {
424    const M &m;
425  public:
426    typedef typename M::Key Key;
427    typedef typename M::Value Value;
428
429    ///Constructor
430
431    ///\e
432    ///
433    AbsMap(const M &_m) : m(_m) {};
434    Value operator[](Key k) const {Value tmp=m[k]; return tmp>=0?tmp:-tmp;}
435  };
436 
437  ///Returns a \ref AbsMap class
438
439  ///This function just returns a \ref AbsMap class.
440  ///\relates AbsMap
441  template<class M>
442  inline AbsMap<M> absMap(const M &m)
443  {
444    return AbsMap<M>(m);
445  }
446
447  /// @}
448 
449}
450
451
452#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.