COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/maps.h @ 1219:ce885274b754

Last change on this file since 1219:ce885274b754 was 1219:ce885274b754, checked in by Alpar Juttner, 15 years ago

ForkMap? and CombineMap? added.

File size: 19.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  ///Returns a \ref ComposeMap class
495
496  ///This function just returns a \ref ComposeMap class.
497  ///
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  ///Combine of two maps using an STL (binary) functor.
506
507  ///Combine of two maps using an STL (binary) functor.
508  ///
509  ///
510  ///This \ref concept::ReadMap "read only map" takes to maps and a
511  ///binary functor and returns the composition of
512  ///two
513  ///given maps unsing the functor.
514  ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
515  ///and \c f is of \c F,
516  ///then for
517  ///\code
518  ///  CombineMap<M1,M2,F,V> cm(m1,m2,f);
519  ///\endcode
520  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
521  ///
522  ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
523  ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
524  ///input parameter of \c F and the return type of \c F must be convertible
525  ///to \c V.
526  ///\todo Check the requirements.
527
528  template<class M1,class M2,class F,class V>
529  class CombineMap
530  {
531    const M1 &m1;
532    const M2 &m2;
533    const F &f;
534  public:
535    typedef typename M1::Key Key;
536    typedef V Value;
537
538    ///Constructor
539
540    ///\e
541    ///
542    CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
543      : m1(_m1), m2(_m2), f(_f) {};
544    Value operator[](Key k) const {return f(m1[k],m2[k]);}
545  };
546 
547  ///Returns a \ref CombineMap class
548
549  ///This function just returns a \ref CombineMap class.
550  ///
551  ///Only the first template parameter (the value type) must be given.
552  ///
553  ///For example if \c m1 and \c m2 are both \c double valued maps, then
554  ///\code
555  ///combineMap<double>(m1,m2,std::plus<double>)
556  ///\endcode
557  ///is equivalent with
558  ///\code
559  ///addMap(m1,m2)
560  ///\endcode
561  ///
562  ///\relates CombineMap
563  template<class V,class M1,class M2,class F>
564  inline CombineMap<M1,M2,F,V> combineMap(const M1 &m1,const M2 &m2,const F &f)
565  {
566    return CombineMap<M1,M2,F,V>(m1,m2,f);
567  }
568
569  ///Negative value of a map
570
571  ///This \ref concept::ReadMap "read only map" returns the negative
572  ///value of the
573  ///value returned by the
574  ///given map. Its \c Key and \c Value will be inherited from \c M.
575  ///The unary \c - operator must be defined for \c Value, of course.
576
577  template<class M>
578  class NegMap
579  {
580    const M &m;
581  public:
582    typedef typename M::Key Key;
583    typedef typename M::Value Value;
584
585    ///Constructor
586
587    ///\e
588    ///
589    NegMap(const M &_m) : m(_m) {};
590    Value operator[](Key k) const {return -m[k];}
591  };
592 
593  ///Returns a \ref NegMap class
594
595  ///This function just returns a \ref NegMap class.
596  ///\relates NegMap
597  template<class M>
598  inline NegMap<M> negMap(const M &m)
599  {
600    return NegMap<M>(m);
601  }
602
603
604  ///Absolute value of a map
605
606  ///This \ref concept::ReadMap "read only map" returns the absolute value
607  ///of the
608  ///value returned by the
609  ///given map. Its \c Key and \c Value will be inherited
610  ///from <tt>M</tt>. <tt>Value</tt>
611  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
612  ///operator must be defined for it, of course.
613  ///
614  ///\bug We need a unified way to handle the situation below:
615  ///\code
616  ///  struct _UnConvertible {};
617  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
618  ///  template<> inline int t_abs<>(int n) {return abs(n);}
619  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
620  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
621  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
622  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
623  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
624  ///\endcode
625 
626
627  template<class M>
628  class AbsMap
629  {
630    const M &m;
631  public:
632    typedef typename M::Key Key;
633    typedef typename M::Value Value;
634
635    ///Constructor
636
637    ///\e
638    ///
639    AbsMap(const M &_m) : m(_m) {};
640    Value operator[](Key k) const {Value tmp=m[k]; return tmp>=0?tmp:-tmp;}
641  };
642 
643  ///Returns a \ref AbsMap class
644
645  ///This function just returns a \ref AbsMap class.
646  ///\relates AbsMap
647  template<class M>
648  inline AbsMap<M> absMap(const M &m)
649  {
650    return AbsMap<M>(m);
651  }
652
653  ///Converts an STL style functor to a a map
654
655  ///This \ref concept::ReadMap "read only map" returns the value
656  ///of a
657  ///given map.
658  ///
659  ///Template parameters \c K and \c V will become its
660  ///\c Key and \c Value. They must be given explicitely
661  ///because a functor does not provide such typedefs.
662  ///
663  ///Parameter \c F is the type of the used functor.
664 
665
666  template<class K,class V,class F>
667  class FunctorMap
668  {
669    const F &f;
670  public:
671    typedef K Key;
672    typedef V Value;
673
674    ///Constructor
675
676    ///\e
677    ///
678    FunctorMap(const F &_f) : f(_f) {};
679    Value operator[](Key k) const {return f(k);}
680  };
681 
682  ///Returns a \ref FunctorMap class
683
684  ///This function just returns a \ref FunctorMap class.
685  ///
686  ///The third template parameter isn't necessary to be given.
687  ///\relates FunctorMap
688  template<class K,class V, class F>
689  inline FunctorMap<K,V,F> functorMap(const F &f)
690  {
691    return FunctorMap<K,V,F>(f);
692  }
693
694  ///Converts a map to an STL style (unary) functor
695
696  ///This class Converts a map to an STL style (unary) functor.
697  ///that is it provides an <tt>operator()</tt> to read its values.
698  ///
699  ///For the sake of convenience it also works as a ususal map, i.e
700  ///<tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
701
702  template<class M>
703  class MapFunctor
704  {
705    const M &m;
706  public:
707    typedef typename M::Key Key;
708    typedef typename M::Value Value;
709
710    ///Constructor
711
712    ///\e
713    ///
714    MapFunctor(const M &_m) : m(_m) {};
715    ///Returns a value of the map
716   
717    ///\e
718    ///
719    Value operator()(Key k) const {return m[k];}
720    ///\e
721    ///
722    Value operator[](Key k) const {return m[k];}
723  };
724 
725  ///Returns a \ref MapFunctor class
726
727  ///This function just returns a \ref MapFunctor class.
728  ///\relates MapFunctor
729  template<class M>
730  inline MapFunctor<M> mapFunctor(const M &m)
731  {
732    return MapFunctor<M>(m);
733  }
734
735
736  ///Apply all map setting operations to two maps
737
738  ///This map has two \ref concept::WriteMap "writable map"
739  ///parameters and each write request will be passed to both of them.
740  ///If \c M1 is also \ref concept::ReadMap "readable",
741  ///then the read operations will return the
742  ///corresponding values \c M1.
743  ///
744  ///The \c Key and \c Value will be inherited from \c M1.
745  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
746
747  template<class M1,class M2>
748  class ForkMap
749  {
750    const M1 &m1;
751    const M2 &m2;
752  public:
753    typedef typename M1::Key Key;
754    typedef typename M1::Value Value;
755
756    ///Constructor
757
758    ///\e
759    ///
760    ForkMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
761    Value operator[](Key k) const {return m1[k];}
762    void set(Key k,const Value &v) {m1.set(k,v); m2.set(k,v);}
763  };
764 
765  ///Returns an \ref ForkMap class
766
767  ///This function just returns an \ref ForkMap class.
768  ///\todo How to call these type of functions?
769  ///
770  ///\relates ForkMap
771  ///\todo Wrong scope in Doxygen when \c \\relates is used
772  template<class M1,class M2>
773  inline ForkMap<M1,M2> forkMap(const M1 &m1,const M2 &m2)
774  {
775    return ForkMap<M1,M2>(m1,m2);
776  }
777
778  /// @}
779 
780}
781
782
783#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.