COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/maps.h @ 1192:aa4483befa56

Last change on this file since 1192:aa4483befa56 was 1178:3c176c65d33b, checked in by Alpar Juttner, 19 years ago
File size: 16.7 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 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  ///Convert the \c Value of a maps to another type.
190
191  ///This \ref concept::ReadMap "read only map"
192  ///converts the \c Value of a maps to type \c T.
193  ///Its \c Value is inherited from \c M.
194  ///
195  ///Actually,
196  ///\code
197  ///  ConvertMap<X> sh(x,v);
198  ///\endcode
199  ///it is equivalent with
200  ///\code
201  ///  ConstMap<X::Key, X::Value> c_tmp(v);
202  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
203  ///\endcode
204  ///\bug wrong documentation
205  template<class M, class T>
206  class ConvertMap
207  {
208    const M &m;
209  public:
210    typedef typename M::Key Key;
211    typedef T Value;
212
213    ///Constructor
214
215    ///Constructor
216    ///\param _m is the undelying map
217    ///\param _v is the convert value
218    ConvertMap(const M &_m) : m(_m) {};
219    Value operator[](Key k) const {return m[k];}
220  };
221 
222  ///Returns an \ref ConvertMap class
223
224  ///This function just returns an \ref ConvertMap class.
225  ///\relates ConvertMap
226  ///\todo The order of the template parameters are changed.
227  template<class T, class M>
228  inline ConvertMap<M,T> convertMap(const M &m)
229  {
230    return ConvertMap<M,T>(m);
231  }
232
233  ///Sum of two maps
234
235  ///This \ref concept::ReadMap "read only map" returns the sum of the two
236  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
237  ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
238
239  template<class M1,class M2>
240  class AddMap
241  {
242    const M1 &m1;
243    const M2 &m2;
244  public:
245    typedef typename M1::Key Key;
246    typedef typename M1::Value Value;
247
248    ///Constructor
249
250    ///\e
251    ///
252    AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
253    Value operator[](Key k) const {return m1[k]+m2[k];}
254  };
255 
256  ///Returns an \ref AddMap class
257
258  ///This function just returns an \ref AddMap class.
259  ///\todo How to call these type of functions?
260  ///
261  ///\relates AddMap
262  ///\todo Wrong scope in Doxygen when \c \\relates is used
263  template<class M1,class M2>
264  inline AddMap<M1,M2> addMap(const M1 &m1,const M2 &m2)
265  {
266    return AddMap<M1,M2>(m1,m2);
267  }
268
269  ///Shift a maps with a constant.
270
271  ///This \ref concept::ReadMap "read only map" returns the sum of the
272  ///given map and a constant value.
273  ///Its \c Key and \c Value is inherited from \c M.
274  ///
275  ///Actually,
276  ///\code
277  ///  ShiftMap<X> sh(x,v);
278  ///\endcode
279  ///it is equivalent with
280  ///\code
281  ///  ConstMap<X::Key, X::Value> c_tmp(v);
282  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
283  ///\endcode
284  template<class M>
285  class ShiftMap
286  {
287    const M &m;
288    typename M::Value v;
289  public:
290    typedef typename M::Key Key;
291    typedef typename M::Value Value;
292
293    ///Constructor
294
295    ///Constructor
296    ///\param _m is the undelying map
297    ///\param _v is the shift value
298    ShiftMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
299    Value operator[](Key k) const {return m[k]+v;}
300  };
301 
302  ///Returns an \ref ShiftMap class
303
304  ///This function just returns an \ref ShiftMap class.
305  ///\relates ShiftMap
306  ///\todo A better name is required.
307  template<class M>
308  inline ShiftMap<M> shiftMap(const M &m,const typename M::Value &v)
309  {
310    return ShiftMap<M>(m,v);
311  }
312
313  ///Difference of two maps
314
315  ///This \ref concept::ReadMap "read only map" returns the difference
316  ///of the values returned by the two
317  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
318  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
319
320  template<class M1,class M2>
321  class SubMap
322  {
323    const M1 &m1;
324    const M2 &m2;
325  public:
326    typedef typename M1::Key Key;
327    typedef typename M1::Value Value;
328
329    ///Constructor
330
331    ///\e
332    ///
333    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
334    Value operator[](Key k) const {return m1[k]-m2[k];}
335  };
336 
337  ///Returns a \ref SubMap class
338
339  ///This function just returns a \ref SubMap class.
340  ///
341  ///\relates SubMap
342  template<class M1,class M2>
343  inline SubMap<M1,M2> subMap(const M1 &m1,const M2 &m2)
344  {
345    return SubMap<M1,M2>(m1,m2);
346  }
347
348  ///Product of two maps
349
350  ///This \ref concept::ReadMap "read only map" returns the product of the
351  ///values returned by the two
352  ///given
353  ///maps. Its \c Key and \c Value will be inherited from \c M1.
354  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
355
356  template<class M1,class M2>
357  class MulMap
358  {
359    const M1 &m1;
360    const M2 &m2;
361  public:
362    typedef typename M1::Key Key;
363    typedef typename M1::Value Value;
364
365    ///Constructor
366
367    ///\e
368    ///
369    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
370    Value operator[](Key k) const {return m1[k]*m2[k];}
371  };
372 
373  ///Returns a \ref MulMap class
374
375  ///This function just returns a \ref MulMap class.
376  ///\relates MulMap
377  template<class M1,class M2>
378  inline MulMap<M1,M2> mulMap(const M1 &m1,const M2 &m2)
379  {
380    return MulMap<M1,M2>(m1,m2);
381  }
382 
383  ///Scale a maps with a constant.
384
385  ///This \ref concept::ReadMap "read only map" returns the value of the
386  ///given map multipied with a constant value.
387  ///Its \c Key and \c Value is inherited from \c M.
388  ///
389  ///Actually,
390  ///\code
391  ///  ScaleMap<X> sc(x,v);
392  ///\endcode
393  ///it is equivalent with
394  ///\code
395  ///  ConstMap<X::Key, X::Value> c_tmp(v);
396  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
397  ///\endcode
398  template<class M>
399  class ScaleMap
400  {
401    const M &m;
402    typename M::Value v;
403  public:
404    typedef typename M::Key Key;
405    typedef typename M::Value Value;
406
407    ///Constructor
408
409    ///Constructor
410    ///\param _m is the undelying map
411    ///\param _v is the scaling value
412    ScaleMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
413    Value operator[](Key k) const {return m[k]*v;}
414  };
415 
416  ///Returns an \ref ScaleMap class
417
418  ///This function just returns an \ref ScaleMap class.
419  ///\relates ScaleMap
420  ///\todo A better name is required.
421  template<class M>
422  inline ScaleMap<M> scaleMap(const M &m,const typename M::Value &v)
423  {
424    return ScaleMap<M>(m,v);
425  }
426
427  ///Quotient of two maps
428
429  ///This \ref concept::ReadMap "read only map" returns the quotient of the
430  ///values returned by the two
431  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
432  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
433
434  template<class M1,class M2>
435  class DivMap
436  {
437    const M1 &m1;
438    const M2 &m2;
439  public:
440    typedef typename M1::Key Key;
441    typedef typename M1::Value Value;
442
443    ///Constructor
444
445    ///\e
446    ///
447    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
448    Value operator[](Key k) const {return m1[k]/m2[k];}
449  };
450 
451  ///Returns a \ref DivMap class
452
453  ///This function just returns a \ref DivMap class.
454  ///\relates DivMap
455  template<class M1,class M2>
456  inline DivMap<M1,M2> divMap(const M1 &m1,const M2 &m2)
457  {
458    return DivMap<M1,M2>(m1,m2);
459  }
460 
461  ///Composition of two maps
462
463  ///This \ref concept::ReadMap "read only map" returns the composition of
464  ///two
465  ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
466  ///of \c M2,
467  ///then for
468  ///\code
469  ///  ComposeMap<M1,M2> cm(m1,m2);
470  ///\endcode
471  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
472  ///
473  ///Its \c Key is inherited from \c M2 and its \c Value is from
474  ///\c M1.
475  ///The \c M2::Value must be convertible to \c M1::Key.
476  ///\todo Check the requirements.
477
478  template<class M1,class M2>
479  class ComposeMap
480  {
481    const M1 &m1;
482    const M2 &m2;
483  public:
484    typedef typename M2::Key Key;
485    typedef typename M1::Value Value;
486
487    ///Constructor
488
489    ///\e
490    ///
491    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
492    Value operator[](Key k) const {return m1[m2[k]];}
493  };
494 
495  ///Returns a \ref ComposeMap class
496
497  ///This function just returns a \ref ComposeMap class.
498  ///\relates ComposeMap
499  template<class M1,class M2>
500  inline ComposeMap<M1,M2> composeMap(const M1 &m1,const M2 &m2)
501  {
502    return ComposeMap<M1,M2>(m1,m2);
503  }
504
505  ///Negative value of a map
506
507  ///This \ref concept::ReadMap "read only map" returns the negative
508  ///value of the
509  ///value returned by the
510  ///given map. Its \c Key and \c Value will be inherited from \c M.
511  ///The unary \c - operator must be defined for \c Value, of course.
512
513  template<class M>
514  class NegMap
515  {
516    const M &m;
517  public:
518    typedef typename M::Key Key;
519    typedef typename M::Value Value;
520
521    ///Constructor
522
523    ///\e
524    ///
525    NegMap(const M &_m) : m(_m) {};
526    Value operator[](Key k) const {return -m[k];}
527  };
528 
529  ///Returns a \ref NegMap class
530
531  ///This function just returns a \ref NegMap class.
532  ///\relates NegMap
533  template<class M>
534  inline NegMap<M> negMap(const M &m)
535  {
536    return NegMap<M>(m);
537  }
538
539
540  ///Absolute value of a map
541
542  ///This \ref concept::ReadMap "read only map" returns the absolute value
543  ///of the
544  ///value returned by the
545  ///given map. Its \c Key and \c Value will be inherited
546  ///from <tt>M</tt>. <tt>Value</tt>
547  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
548  ///operator must be defined for it, of course.
549  ///
550  ///\bug We need a unified way to handle the situation below:
551  ///\code
552  ///  struct _UnConvertible {};
553  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
554  ///  template<> inline int t_abs<>(int n) {return abs(n);}
555  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
556  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
557  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
558  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
559  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
560  ///\endcode
561 
562
563  template<class M>
564  class AbsMap
565  {
566    const M &m;
567  public:
568    typedef typename M::Key Key;
569    typedef typename M::Value Value;
570
571    ///Constructor
572
573    ///\e
574    ///
575    AbsMap(const M &_m) : m(_m) {};
576    Value operator[](Key k) const {Value tmp=m[k]; return tmp>=0?tmp:-tmp;}
577  };
578 
579  ///Returns a \ref AbsMap class
580
581  ///This function just returns a \ref AbsMap class.
582  ///\relates AbsMap
583  template<class M>
584  inline AbsMap<M> absMap(const M &m)
585  {
586    return AbsMap<M>(m);
587  }
588
589  ///Converts an STL style functor to a a map
590
591  ///This \ref concept::ReadMap "read only map" returns the value
592  ///of a
593  ///given map.
594  ///
595  ///Template parameters \c K and \c V will become its
596  ///\c Key and \c Value. They must be given explicitely
597  ///because a functor does not provide such typedefs.
598  ///
599  ///Parameter \c F is the type of the used functor.
600 
601
602  template<class K,class V,class F>
603  class FunctorMap
604  {
605    const F &f;
606  public:
607    typedef K Key;
608    typedef V Value;
609
610    ///Constructor
611
612    ///\e
613    ///
614    FunctorMap(const F &_f) : f(_f) {};
615    Value operator[](Key k) const {return f(k);}
616  };
617 
618  ///Returns a \ref FunctorMap class
619
620  ///This function just returns a \ref FunctorMap class.
621  ///
622  ///The third template parameter isn't necessary to be given.
623  ///\relates FunctorMap
624  template<class K,class V, class F>
625  inline FunctorMap<K,V,F> functorMap(const F &f)
626  {
627    return FunctorMap<K,V,F>(f);
628  }
629
630  ///Converts a map to an STL style functor
631
632  ///This class Converts a map to an STL style functor.
633  ///that is it provides an <tt>operator()</tt> to read its values.
634  ///
635  ///For the sake of convenience it also works as a ususal map, i.e
636  ///<tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
637
638  template<class M>
639  class MapFunctor
640  {
641    const M &m;
642  public:
643    typedef typename M::Key Key;
644    typedef typename M::Value Value;
645
646    ///Constructor
647
648    ///\e
649    ///
650    MapFunctor(const M &_m) : m(_m) {};
651    ///Returns a value of the map
652   
653    ///\e
654    ///
655    Value operator()(Key k) const {return m[k];}
656    ///\e
657    ///
658    Value operator[](Key k) const {return m[k];}
659  };
660 
661  ///Returns a \ref MapFunctor class
662
663  ///This function just returns a \ref MapFunctor class.
664  ///\relates MapFunctor
665  template<class M>
666  inline MapFunctor<M> mapFunctor(const M &m)
667  {
668    return MapFunctor<M>(m);
669  }
670
671
672  /// @}
673 
674}
675
676
677#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.