COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/maps.h @ 1096:1cfb25ef14d2

Last change on this file since 1096:1cfb25ef14d2 was 1076:67a115cdade4, checked in by Alpar Juttner, 19 years ago

functor->map and map->functor converters added.

File size: 15.7 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  ///Returns a \ref ConstMap class
102
103  ///This function just returns a \ref ConstMap class.
104  ///\relates ConstMap
105  template<class V,class K>
106  inline ConstMap<V,K> constMap(const K &k)
107  {
108    return ConstMap<V,K>(k);
109  }
110
111
112  //to document later
113  template<typename T, T v>
114  struct Const { };
115  //to document later
116  template<typename K, typename V, V v>
117  class ConstMap<K, Const<V, v> > : public MapBase<K, V>
118  {
119  public:
120    ConstMap() { }
121    V operator[](const K&) const { return v; }
122    void set(const K&, const V&) { }
123  };
124
125  /// \c std::map wrapper
126
127  /// This is essentially a wrapper for \c std::map. With addition that
128  /// you can specify a default value different from \c Value() .
129  ///
130  /// \todo Provide allocator parameter...
131  template <typename K, typename T, typename Compare = std::less<K> >
132  class StdMap : public std::map<K,T,Compare> {
133    typedef std::map<K,T,Compare> parent;
134    T v;
135    typedef typename parent::value_type PairType;
136
137  public:
138    typedef K Key;
139    typedef T Value;
140    typedef T& Reference;
141    typedef const T& ConstReference;
142
143
144    StdMap() : v() {}
145    /// Constructor with specified default value
146    StdMap(const T& _v) : v(_v) {}
147
148    /// \brief Constructs the map from an appropriate std::map.
149    ///
150    /// \warning Inefficient: copies the content of \c m !
151    StdMap(const parent &m) : parent(m) {}
152    /// \brief Constructs the map from an appropriate std::map, and explicitly
153    /// specifies a default value.
154    ///
155    /// \warning Inefficient: copies the content of \c m !
156    StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
157   
158    template<typename T1, typename Comp1>
159    StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {
160      //FIXME;
161    }
162
163    Reference operator[](const Key &k) {
164      return insert(PairType(k,v)).first -> second;
165    }
166    ConstReference operator[](const Key &k) const {
167      typename parent::iterator i = lower_bound(k);
168      if (i == parent::end() || parent::key_comp()(k, (*i).first))
169        return v;
170      return (*i).second;
171    }
172    void set(const Key &k, const T &t) {
173      parent::operator[](k) = t;
174    }
175
176    /// Changes the default value of the map.
177    /// \return Returns the previous default value.
178    ///
179    /// \warning The value of some keys (which has already been queried, but
180    /// the value has been unchanged from the default) may change!
181    T setDefault(const T &_v) { T old=v; v=_v; return old; }
182
183    template<typename T1>
184    struct rebind {
185      typedef StdMap<Key,T1,Compare> other;
186    };
187  };
188
189
190  ///Sum of two maps
191
192  ///This \ref concept::ReadMap "read only map" returns the sum of the two
193  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
194  ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
195
196  template<class M1,class M2>
197  class AddMap
198  {
199    const M1 &m1;
200    const M2 &m2;
201  public:
202    typedef typename M1::Key Key;
203    typedef typename M1::Value Value;
204
205    ///Constructor
206
207    ///\e
208    ///
209    AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
210    Value operator[](Key k) const {return m1[k]+m2[k];}
211  };
212 
213  ///Returns an \ref AddMap class
214
215  ///This function just returns an \ref AddMap class.
216  ///\todo How to call these type of functions?
217  ///
218  ///\relates AddMap
219  ///\todo Wrong scope in Doxygen when \c \\relates is used
220  template<class M1,class M2>
221  inline AddMap<M1,M2> addMap(const M1 &m1,const M2 &m2)
222  {
223    return AddMap<M1,M2>(m1,m2);
224  }
225
226  ///Shift a maps with a constant.
227
228  ///This \ref concept::ReadMap "read only map" returns the sum of the
229  ///given map and a constant value.
230  ///Its \c Key and \c Value is inherited from \c M.
231  ///
232  ///Actually,
233  ///\code
234  ///  ShiftMap<X> sh(x,v);
235  ///\endcode
236  ///it is equivalent with
237  ///\code
238  ///  ConstMap<X::Key, X::Value> c_tmp(v);
239  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
240  ///\endcode
241  template<class M>
242  class ShiftMap
243  {
244    const M &m;
245    typename M::Value v;
246  public:
247    typedef typename M::Key Key;
248    typedef typename M::Value Value;
249
250    ///Constructor
251
252    ///Constructor
253    ///\param _m is the undelying map
254    ///\param _v is the shift value
255    ShiftMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
256    Value operator[](Key k) const {return m[k]+v;}
257  };
258 
259  ///Returns an \ref ShiftMap class
260
261  ///This function just returns an \ref ShiftMap class.
262  ///\relates ShiftMap
263  ///\todo A better name is required.
264  template<class M>
265  inline ShiftMap<M> shiftMap(const M &m,const typename M::Value &v)
266  {
267    return ShiftMap<M>(m,v);
268  }
269
270  ///Difference of two maps
271
272  ///This \ref concept::ReadMap "read only map" returns the difference
273  ///of the values returned by the two
274  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
275  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
276
277  template<class M1,class M2>
278  class SubMap
279  {
280    const M1 &m1;
281    const M2 &m2;
282  public:
283    typedef typename M1::Key Key;
284    typedef typename M1::Value Value;
285
286    ///Constructor
287
288    ///\e
289    ///
290    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
291    Value operator[](Key k) const {return m1[k]-m2[k];}
292  };
293 
294  ///Returns a \ref SubMap class
295
296  ///This function just returns a \ref SubMap class.
297  ///
298  ///\relates SubMap
299  template<class M1,class M2>
300  inline SubMap<M1,M2> subMap(const M1 &m1,const M2 &m2)
301  {
302    return SubMap<M1,M2>(m1,m2);
303  }
304
305  ///Product of two maps
306
307  ///This \ref concept::ReadMap "read only map" returns the product of the
308  ///values returned by the two
309  ///given
310  ///maps. Its \c Key and \c Value will be inherited from \c M1.
311  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
312
313  template<class M1,class M2>
314  class MulMap
315  {
316    const M1 &m1;
317    const M2 &m2;
318  public:
319    typedef typename M1::Key Key;
320    typedef typename M1::Value Value;
321
322    ///Constructor
323
324    ///\e
325    ///
326    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
327    Value operator[](Key k) const {return m1[k]*m2[k];}
328  };
329 
330  ///Returns a \ref MulMap class
331
332  ///This function just returns a \ref MulMap class.
333  ///\relates MulMap
334  template<class M1,class M2>
335  inline MulMap<M1,M2> mulMap(const M1 &m1,const M2 &m2)
336  {
337    return MulMap<M1,M2>(m1,m2);
338  }
339 
340  ///Scale a maps with a constant.
341
342  ///This \ref concept::ReadMap "read only map" returns the value of the
343  ///given map multipied with a constant value.
344  ///Its \c Key and \c Value is inherited from \c M.
345  ///
346  ///Actually,
347  ///\code
348  ///  ScaleMap<X> sc(x,v);
349  ///\endcode
350  ///it is equivalent with
351  ///\code
352  ///  ConstMap<X::Key, X::Value> c_tmp(v);
353  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
354  ///\endcode
355  template<class M>
356  class ScaleMap
357  {
358    const M &m;
359    typename M::Value v;
360  public:
361    typedef typename M::Key Key;
362    typedef typename M::Value Value;
363
364    ///Constructor
365
366    ///Constructor
367    ///\param _m is the undelying map
368    ///\param _v is the scaling value
369    ScaleMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
370    Value operator[](Key k) const {return m[k]*v;}
371  };
372 
373  ///Returns an \ref ScaleMap class
374
375  ///This function just returns an \ref ScaleMap class.
376  ///\relates ScaleMap
377  ///\todo A better name is required.
378  template<class M>
379  inline ScaleMap<M> scaleMap(const M &m,const typename M::Value &v)
380  {
381    return ScaleMap<M>(m,v);
382  }
383
384  ///Quotient of two maps
385
386  ///This \ref concept::ReadMap "read only map" returns the quotient of the
387  ///values returned by the two
388  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
389  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
390
391  template<class M1,class M2>
392  class DivMap
393  {
394    const M1 &m1;
395    const M2 &m2;
396  public:
397    typedef typename M1::Key Key;
398    typedef typename M1::Value Value;
399
400    ///Constructor
401
402    ///\e
403    ///
404    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
405    Value operator[](Key k) const {return m1[k]/m2[k];}
406  };
407 
408  ///Returns a \ref DivMap class
409
410  ///This function just returns a \ref DivMap class.
411  ///\relates DivMap
412  template<class M1,class M2>
413  inline DivMap<M1,M2> divMap(const M1 &m1,const M2 &m2)
414  {
415    return DivMap<M1,M2>(m1,m2);
416  }
417 
418  ///Composition of two maps
419
420  ///This \ref concept::ReadMap "read only map" returns the composition of
421  ///two
422  ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
423  ///of \c M2,
424  ///then for
425  ///\code
426  ///  ComposeMap<M1,M2> cm(m1,m2);
427  ///\endcode
428  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
429  ///
430  ///Its \c Key is inherited from \c M2 and its \c Value is from
431  ///\c M1.
432  ///The \c M2::Value must be convertible to \c M1::Key.
433  ///\todo Check the requirements.
434
435  template<class M1,class M2>
436  class ComposeMap
437  {
438    const M1 &m1;
439    const M2 &m2;
440  public:
441    typedef typename M2::Key Key;
442    typedef typename M1::Value Value;
443
444    ///Constructor
445
446    ///\e
447    ///
448    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
449    Value operator[](Key k) const {return m1[m2[k]];}
450  };
451 
452  ///Returns a \ref ComposeMap class
453
454  ///This function just returns a \ref ComposeMap class.
455  ///\relates ComposeMap
456  template<class M1,class M2>
457  inline ComposeMap<M1,M2> composeMap(const M1 &m1,const M2 &m2)
458  {
459    return ComposeMap<M1,M2>(m1,m2);
460  }
461
462  ///Negative value of a map
463
464  ///This \ref concept::ReadMap "read only map" returns the negative
465  ///value of the
466  ///value returned by the
467  ///given map. Its \c Key and \c Value will be inherited from \c M.
468  ///The unary \c - operator must be defined for \c Value, of course.
469
470  template<class M>
471  class NegMap
472  {
473    const M &m;
474  public:
475    typedef typename M::Key Key;
476    typedef typename M::Value Value;
477
478    ///Constructor
479
480    ///\e
481    ///
482    NegMap(const M &_m) : m(_m) {};
483    Value operator[](Key k) const {return -m[k];}
484  };
485 
486  ///Returns a \ref NegMap class
487
488  ///This function just returns a \ref NegMap class.
489  ///\relates NegMap
490  template<class M>
491  inline NegMap<M> negMap(const M &m)
492  {
493    return NegMap<M>(m);
494  }
495
496
497  ///Absolute value of a map
498
499  ///This \ref concept::ReadMap "read only map" returns the absolute value
500  ///of the
501  ///value returned by the
502  ///given map. Its \c Key and \c Value will be inherited
503  ///from <tt>M</tt>. <tt>Value</tt>
504  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
505  ///operator must be defined for it, of course.
506  ///
507  ///\bug We need a unified way to handle the situation below:
508  ///\code
509  ///  struct _UnConvertible {};
510  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
511  ///  template<> inline int t_abs<>(int n) {return abs(n);}
512  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
513  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
514  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
515  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
516  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
517  ///\endcode
518 
519
520  template<class M>
521  class AbsMap
522  {
523    const M &m;
524  public:
525    typedef typename M::Key Key;
526    typedef typename M::Value Value;
527
528    ///Constructor
529
530    ///\e
531    ///
532    AbsMap(const M &_m) : m(_m) {};
533    Value operator[](Key k) const {Value tmp=m[k]; return tmp>=0?tmp:-tmp;}
534  };
535 
536  ///Returns a \ref AbsMap class
537
538  ///This function just returns a \ref AbsMap class.
539  ///\relates AbsMap
540  template<class M>
541  inline AbsMap<M> absMap(const M &m)
542  {
543    return AbsMap<M>(m);
544  }
545
546  ///Converts an STL style functor to a a map
547
548  ///This \ref concept::ReadMap "read only map" returns the value
549  ///of a
550  ///given map.
551  ///
552  ///Template parameters \c K and \c V will become its
553  ///\c Key and \c Value. They must be given explicitely
554  ///because a functor does not provide such typedefs.
555  ///
556  ///Parameter \c F is the type of the used functor.
557 
558
559  template<class K,class V,class F>
560  class FunctorMap
561  {
562    const F &f;
563  public:
564    typedef K Key;
565    typedef V Value;
566
567    ///Constructor
568
569    ///\e
570    ///
571    FunctorMap(const F &_f) : f(_f) {};
572    Value operator[](Key k) const {return f(k);}
573  };
574 
575  ///Returns a \ref FunctorMap class
576
577  ///This function just returns a \ref FunctorMap class.
578  ///
579  ///The third template parameter isn't necessary to be given.
580  ///\relates FunctorMap
581  template<class K,class V, class F>
582  inline FunctorMap<K,V,F> functorMap(const F &f)
583  {
584    return FunctorMap<K,V,F>(f);
585  }
586
587  ///Converts a map to an STL style functor
588
589  ///This class Converts a map to an STL style functor.
590  ///that is it provides an <tt>operator()</tt> to read its values.
591  ///
592  ///For the sake of convenience it also works as a ususal map, i.e
593  ///<tt>operator[]</tt> and the \c Key and \c Valu typedefs also exist.
594
595  template<class M>
596  class MapFunctor
597  {
598    const M &m;
599  public:
600    typedef typename M::Key Key;
601    typedef typename M::Value Value;
602
603    ///Constructor
604
605    ///\e
606    ///
607    MapFunctor(const M &_m) : m(_m) {};
608    ///Returns a value of the map
609   
610    ///\e
611    ///
612    Value operator()(Key k) const {return m[k];}
613    ///\e
614    ///
615    Value operator[](Key k) const {return m[k];}
616  };
617 
618  ///Returns a \ref MapFunctor class
619
620  ///This function just returns a \ref MapFunctor class.
621  ///\relates MapFunctor
622  template<class M>
623  inline MapFunctor<M> mapFunctor(const M &m)
624  {
625    return MapFunctor<M>(m);
626  }
627
628
629  /// @}
630 
631}
632
633
634#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.