COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/maps.h @ 1402:655d8e78454d

Last change on this file since 1402:655d8e78454d was 1402:655d8e78454d, checked in by Alpar Juttner, 15 years ago

Special maps' placement in the headers and in the doxigen modules
reorganized

File size: 20.0 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 Research Group on Combinatorial Optimization, 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
21///\file
22///\ingroup maps
23///\brief Miscellaneous property maps
24///
25///\todo This file has the same name as the concept file in concept/,
26/// and this is not easily detectable in docs...
27
28#include <map>
29
30namespace lemon {
31
32  /// \addtogroup maps
33  /// @{
34
35  /// Base class of maps.
36
37  /// Base class of maps.
38  /// It provides the necessary <tt>typedef</tt>s required by the map concept.
39  template<typename K, typename T>
40  class MapBase
41  {
42  public:
43    ///\e
44    typedef K Key;
45    ///\e
46    typedef T Value;
47  };
48
49  /// Null map. (a.k.a. DoNothingMap)
50
51  /// If you have to provide a map only for its type definitions,
52  /// or if you have to provide a writable map, but
53  /// data written to it will sent to <tt>/dev/null</tt>...
54  template<typename K, typename T>
55  class NullMap : public MapBase<K,T>
56  {
57  public:
58
59    /// Gives back a default constructed element.
60    T operator[](const K&) const { return T(); }
61    /// Absorbs the value.
62    void set(const K&, const T&) {}
63  };
64
65
66  /// Constant map.
67
68  /// This is a readable map which assigns a specified value to each key.
69  /// In other aspects it is equivalent to the \ref NullMap.
70  /// \todo set could be used to set the value.
71  template<typename K, typename T>
72  class ConstMap : public MapBase<K,T>
73  {
74    T v;
75  public:
76
77    /// Default constructor
78
79    /// The value of the map will be uninitialized.
80    /// (More exactly it will be default constructed.)
81    ConstMap() {}
82    ///\e
83
84    /// \param _v The initial value of the map.
85    ///
86    ConstMap(const T &_v) : v(_v) {}
87
88    T operator[](const K&) const { return v; }
89    void set(const K&, const T&) {}
90
91    template<typename T1>
92    struct rebind {
93      typedef ConstMap<K,T1> other;
94    };
95
96    template<typename T1>
97    ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}
98  };
99
100  ///Returns a \ref ConstMap class
101
102  ///This function just returns a \ref ConstMap class.
103  ///\relates ConstMap
104  template<class V,class K>
105  inline ConstMap<V,K> constMap(const K &k)
106  {
107    return ConstMap<V,K>(k);
108  }
109
110
111  //to document later
112  template<typename T, T v>
113  struct Const { };
114  //to document later
115  template<typename K, typename V, V v>
116  class ConstMap<K, Const<V, v> > : public MapBase<K, V>
117  {
118  public:
119    ConstMap() { }
120    V operator[](const K&) const { return v; }
121    void set(const K&, const V&) { }
122  };
123
124  /// \c std::map wrapper
125
126  /// This is essentially a wrapper for \c std::map. With addition that
127  /// you can specify a default value different from \c Value() .
128  ///
129  /// \todo Provide allocator parameter...
130  template <typename K, typename T, typename Compare = std::less<K> >
131  class StdMap : public std::map<K,T,Compare> {
132    typedef std::map<K,T,Compare> parent;
133    T v;
134    typedef typename parent::value_type PairType;
135
136  public:
137    typedef K Key;
138    typedef T Value;
139    typedef T& Reference;
140    typedef const T& ConstReference;
141
142
143    StdMap() : v() {}
144    /// Constructor with specified default value
145    StdMap(const T& _v) : v(_v) {}
146
147    /// \brief Constructs the map from an appropriate std::map.
148    ///
149    /// \warning Inefficient: copies the content of \c m !
150    StdMap(const parent &m) : parent(m) {}
151    /// \brief Constructs the map from an appropriate std::map, and explicitly
152    /// specifies a default value.
153    ///
154    /// \warning Inefficient: copies the content of \c m !
155    StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
156   
157    template<typename T1, typename Comp1>
158    StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {
159      //FIXME;
160    }
161
162    Reference operator[](const Key &k) {
163      return insert(PairType(k,v)).first -> second;
164    }
165    ConstReference operator[](const Key &k) const {
166      typename parent::iterator i = lower_bound(k);
167      if (i == parent::end() || parent::key_comp()(k, (*i).first))
168        return v;
169      return (*i).second;
170    }
171    void set(const Key &k, const T &t) {
172      parent::operator[](k) = t;
173    }
174
175    /// Changes the default value of the map.
176    /// \return Returns the previous default value.
177    ///
178    /// \warning The value of some keys (which has already been queried, but
179    /// the value has been unchanged from the default) may change!
180    T setDefault(const T &_v) { T old=v; v=_v; return old; }
181
182    template<typename T1>
183    struct rebind {
184      typedef StdMap<Key,T1,Compare> other;
185    };
186  };
187
188  /// @}
189
190  /// \addtogroup map_adaptors
191  /// @{
192
193
194  ///Convert the \c Value of a maps to another type.
195
196  ///This \ref concept::ReadMap "read only map"
197  ///converts the \c Value of a maps to type \c T.
198  ///Its \c Value is inherited from \c M.
199  ///
200  ///Actually,
201  ///\code
202  ///  ConvertMap<X> sh(x,v);
203  ///\endcode
204  ///it is equivalent with
205  ///\code
206  ///  ConstMap<X::Key, X::Value> c_tmp(v);
207  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
208  ///\endcode
209  ///\bug wrong documentation
210  template<class M, class T>
211  class ConvertMap
212  {
213    const M &m;
214  public:
215    typedef typename M::Key Key;
216    typedef T Value;
217
218    ///Constructor
219
220    ///Constructor
221    ///\param _m is the undelying map
222    ///\param _v is the convert value
223    ConvertMap(const M &_m) : m(_m) {};
224
225    /// \brief The subscript operator.
226    ///
227    /// The subscript operator.
228    /// \param edge The edge
229    /// \return The target of the edge
230    Value operator[](Key k) const {return m[k];}
231  };
232 
233  ///Returns an \ref ConvertMap class
234
235  ///This function just returns an \ref ConvertMap class.
236  ///\relates ConvertMap
237  ///\todo The order of the template parameters are changed.
238  template<class T, class M>
239  inline ConvertMap<M,T> convertMap(const M &m)
240  {
241    return ConvertMap<M,T>(m);
242  }
243
244  ///Sum of two maps
245
246  ///This \ref concept::ReadMap "read only map" returns the sum of the two
247  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
248  ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
249
250  template<class M1,class M2>
251  class AddMap
252  {
253    const M1 &m1;
254    const M2 &m2;
255  public:
256    typedef typename M1::Key Key;
257    typedef typename M1::Value Value;
258
259    ///Constructor
260
261    ///\e
262    ///
263    AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
264    Value operator[](Key k) const {return m1[k]+m2[k];}
265  };
266 
267  ///Returns an \ref AddMap class
268
269  ///This function just returns an \ref AddMap class.
270  ///\todo How to call these type of functions?
271  ///
272  ///\relates AddMap
273  ///\todo Wrong scope in Doxygen when \c \\relates is used
274  template<class M1,class M2>
275  inline AddMap<M1,M2> addMap(const M1 &m1,const M2 &m2)
276  {
277    return AddMap<M1,M2>(m1,m2);
278  }
279
280  ///Shift a maps with a constant.
281
282  ///This \ref concept::ReadMap "read only map" returns the sum of the
283  ///given map and a constant value.
284  ///Its \c Key and \c Value is inherited from \c M.
285  ///
286  ///Actually,
287  ///\code
288  ///  ShiftMap<X> sh(x,v);
289  ///\endcode
290  ///it is equivalent with
291  ///\code
292  ///  ConstMap<X::Key, X::Value> c_tmp(v);
293  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
294  ///\endcode
295  template<class M>
296  class ShiftMap
297  {
298    const M &m;
299    typename M::Value v;
300  public:
301    typedef typename M::Key Key;
302    typedef typename M::Value Value;
303
304    ///Constructor
305
306    ///Constructor
307    ///\param _m is the undelying map
308    ///\param _v is the shift value
309    ShiftMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
310    Value operator[](Key k) const {return m[k]+v;}
311  };
312 
313  ///Returns an \ref ShiftMap class
314
315  ///This function just returns an \ref ShiftMap class.
316  ///\relates ShiftMap
317  ///\todo A better name is required.
318  template<class M>
319  inline ShiftMap<M> shiftMap(const M &m,const typename M::Value &v)
320  {
321    return ShiftMap<M>(m,v);
322  }
323
324  ///Difference of two maps
325
326  ///This \ref concept::ReadMap "read only map" returns the difference
327  ///of the values returned by the two
328  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
329  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
330
331  template<class M1,class M2>
332  class SubMap
333  {
334    const M1 &m1;
335    const M2 &m2;
336  public:
337    typedef typename M1::Key Key;
338    typedef typename M1::Value Value;
339
340    ///Constructor
341
342    ///\e
343    ///
344    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
345    Value operator[](Key k) const {return m1[k]-m2[k];}
346  };
347 
348  ///Returns a \ref SubMap class
349
350  ///This function just returns a \ref SubMap class.
351  ///
352  ///\relates SubMap
353  template<class M1,class M2>
354  inline SubMap<M1,M2> subMap(const M1 &m1,const M2 &m2)
355  {
356    return SubMap<M1,M2>(m1,m2);
357  }
358
359  ///Product of two maps
360
361  ///This \ref concept::ReadMap "read only map" returns the product of the
362  ///values returned by the two
363  ///given
364  ///maps. Its \c Key and \c Value will be inherited from \c M1.
365  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
366
367  template<class M1,class M2>
368  class MulMap
369  {
370    const M1 &m1;
371    const M2 &m2;
372  public:
373    typedef typename M1::Key Key;
374    typedef typename M1::Value Value;
375
376    ///Constructor
377
378    ///\e
379    ///
380    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
381    Value operator[](Key k) const {return m1[k]*m2[k];}
382  };
383 
384  ///Returns a \ref MulMap class
385
386  ///This function just returns a \ref MulMap class.
387  ///\relates MulMap
388  template<class M1,class M2>
389  inline MulMap<M1,M2> mulMap(const M1 &m1,const M2 &m2)
390  {
391    return MulMap<M1,M2>(m1,m2);
392  }
393 
394  ///Scale a maps with a constant.
395
396  ///This \ref concept::ReadMap "read only map" returns the value of the
397  ///given map multipied with a constant value.
398  ///Its \c Key and \c Value is inherited from \c M.
399  ///
400  ///Actually,
401  ///\code
402  ///  ScaleMap<X> sc(x,v);
403  ///\endcode
404  ///it is equivalent with
405  ///\code
406  ///  ConstMap<X::Key, X::Value> c_tmp(v);
407  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
408  ///\endcode
409  template<class M>
410  class ScaleMap
411  {
412    const M &m;
413    typename M::Value v;
414  public:
415    typedef typename M::Key Key;
416    typedef typename M::Value Value;
417
418    ///Constructor
419
420    ///Constructor
421    ///\param _m is the undelying map
422    ///\param _v is the scaling value
423    ScaleMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
424    Value operator[](Key k) const {return m[k]*v;}
425  };
426 
427  ///Returns an \ref ScaleMap class
428
429  ///This function just returns an \ref ScaleMap class.
430  ///\relates ScaleMap
431  ///\todo A better name is required.
432  template<class M>
433  inline ScaleMap<M> scaleMap(const M &m,const typename M::Value &v)
434  {
435    return ScaleMap<M>(m,v);
436  }
437
438  ///Quotient of two maps
439
440  ///This \ref concept::ReadMap "read only map" returns the quotient of the
441  ///values returned by the two
442  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
443  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
444
445  template<class M1,class M2>
446  class DivMap
447  {
448    const M1 &m1;
449    const M2 &m2;
450  public:
451    typedef typename M1::Key Key;
452    typedef typename M1::Value Value;
453
454    ///Constructor
455
456    ///\e
457    ///
458    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
459    Value operator[](Key k) const {return m1[k]/m2[k];}
460  };
461 
462  ///Returns a \ref DivMap class
463
464  ///This function just returns a \ref DivMap class.
465  ///\relates DivMap
466  template<class M1,class M2>
467  inline DivMap<M1,M2> divMap(const M1 &m1,const M2 &m2)
468  {
469    return DivMap<M1,M2>(m1,m2);
470  }
471 
472  ///Composition of two maps
473
474  ///This \ref concept::ReadMap "read only map" returns the composition of
475  ///two
476  ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
477  ///of \c M2,
478  ///then for
479  ///\code
480  ///  ComposeMap<M1,M2> cm(m1,m2);
481  ///\endcode
482  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
483  ///
484  ///Its \c Key is inherited from \c M2 and its \c Value is from
485  ///\c M1.
486  ///The \c M2::Value must be convertible to \c M1::Key.
487  ///\todo Check the requirements.
488
489  template<class M1,class M2>
490  class ComposeMap
491  {
492    const M1 &m1;
493    const M2 &m2;
494  public:
495    typedef typename M2::Key Key;
496    typedef typename M1::Value Value;
497
498    ///Constructor
499
500    ///\e
501    ///
502    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
503    Value operator[](Key k) const {return m1[m2[k]];}
504  };
505  ///Returns a \ref ComposeMap class
506
507  ///This function just returns a \ref ComposeMap class.
508  ///
509  ///\relates ComposeMap
510  template<class M1,class M2>
511  inline ComposeMap<M1,M2> composeMap(const M1 &m1,const M2 &m2)
512  {
513    return ComposeMap<M1,M2>(m1,m2);
514  }
515 
516  ///Combine of two maps using an STL (binary) functor.
517
518  ///Combine of two maps using an STL (binary) functor.
519  ///
520  ///
521  ///This \ref concept::ReadMap "read only map" takes to maps and a
522  ///binary functor and returns the composition of
523  ///two
524  ///given maps unsing the functor.
525  ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
526  ///and \c f is of \c F,
527  ///then for
528  ///\code
529  ///  CombineMap<M1,M2,F,V> cm(m1,m2,f);
530  ///\endcode
531  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
532  ///
533  ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
534  ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
535  ///input parameter of \c F and the return type of \c F must be convertible
536  ///to \c V.
537  ///\todo Check the requirements.
538
539  template<class M1,class M2,class F,class V>
540  class CombineMap
541  {
542    const M1 &m1;
543    const M2 &m2;
544    const F &f;
545  public:
546    typedef typename M1::Key Key;
547    typedef V Value;
548
549    ///Constructor
550
551    ///\e
552    ///
553    CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
554      : m1(_m1), m2(_m2), f(_f) {};
555    Value operator[](Key k) const {return f(m1[k],m2[k]);}
556  };
557 
558  ///Returns a \ref CombineMap class
559
560  ///This function just returns a \ref CombineMap class.
561  ///
562  ///Only the first template parameter (the value type) must be given.
563  ///
564  ///For example if \c m1 and \c m2 are both \c double valued maps, then
565  ///\code
566  ///combineMap<double>(m1,m2,std::plus<double>)
567  ///\endcode
568  ///is equivalent with
569  ///\code
570  ///addMap(m1,m2)
571  ///\endcode
572  ///
573  ///\relates CombineMap
574  template<class V,class M1,class M2,class F>
575  inline CombineMap<M1,M2,F,V> combineMap(const M1 &m1,const M2 &m2,const F &f)
576  {
577    return CombineMap<M1,M2,F,V>(m1,m2,f);
578  }
579
580  ///Negative value of a map
581
582  ///This \ref concept::ReadMap "read only map" returns the negative
583  ///value of the
584  ///value returned by the
585  ///given map. Its \c Key and \c Value will be inherited from \c M.
586  ///The unary \c - operator must be defined for \c Value, of course.
587
588  template<class M>
589  class NegMap
590  {
591    const M &m;
592  public:
593    typedef typename M::Key Key;
594    typedef typename M::Value Value;
595
596    ///Constructor
597
598    ///\e
599    ///
600    NegMap(const M &_m) : m(_m) {};
601    Value operator[](Key k) const {return -m[k];}
602  };
603 
604  ///Returns a \ref NegMap class
605
606  ///This function just returns a \ref NegMap class.
607  ///\relates NegMap
608  template<class M>
609  inline NegMap<M> negMap(const M &m)
610  {
611    return NegMap<M>(m);
612  }
613
614
615  ///Absolute value of a map
616
617  ///This \ref concept::ReadMap "read only map" returns the absolute value
618  ///of the
619  ///value returned by the
620  ///given map. Its \c Key and \c Value will be inherited
621  ///from <tt>M</tt>. <tt>Value</tt>
622  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
623  ///operator must be defined for it, of course.
624  ///
625  ///\bug We need a unified way to handle the situation below:
626  ///\code
627  ///  struct _UnConvertible {};
628  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
629  ///  template<> inline int t_abs<>(int n) {return abs(n);}
630  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
631  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
632  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
633  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
634  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
635  ///\endcode
636 
637
638  template<class M>
639  class AbsMap
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    AbsMap(const M &_m) : m(_m) {};
651    Value operator[](Key k) const {Value tmp=m[k]; return tmp>=0?tmp:-tmp;}
652  };
653 
654  ///Returns a \ref AbsMap class
655
656  ///This function just returns a \ref AbsMap class.
657  ///\relates AbsMap
658  template<class M>
659  inline AbsMap<M> absMap(const M &m)
660  {
661    return AbsMap<M>(m);
662  }
663
664  ///Converts an STL style functor to a map
665
666  ///This \ref concept::ReadMap "read only map" returns the value
667  ///of a
668  ///given map.
669  ///
670  ///Template parameters \c K and \c V will become its
671  ///\c Key and \c Value. They must be given explicitely
672  ///because a functor does not provide such typedefs.
673  ///
674  ///Parameter \c F is the type of the used functor.
675 
676
677  template<class K,class V,class F>
678  class FunctorMap
679  {
680    const F &f;
681  public:
682    typedef K Key;
683    typedef V Value;
684
685    ///Constructor
686
687    ///\e
688    ///
689    FunctorMap(const F &_f) : f(_f) {};
690    Value operator[](Key k) const {return f(k);}
691  };
692 
693  ///Returns a \ref FunctorMap class
694
695  ///This function just returns a \ref FunctorMap class.
696  ///
697  ///The third template parameter isn't necessary to be given.
698  ///\relates FunctorMap
699  template<class K,class V, class F>
700  inline FunctorMap<K,V,F> functorMap(const F &f)
701  {
702    return FunctorMap<K,V,F>(f);
703  }
704
705  ///Converts a map to an STL style (unary) functor
706
707  ///This class Converts a map to an STL style (unary) functor.
708  ///that is it provides an <tt>operator()</tt> to read its values.
709  ///
710  ///For the sake of convenience it also works as
711  ///a ususal \ref concept::ReadMap "readable map", i.e
712  ///<tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
713
714  template<class M>
715  class MapFunctor
716  {
717    const M &m;
718  public:
719    typedef typename M::Key argument_type;
720    typedef typename M::Value result_type;
721    typedef typename M::Key Key;
722    typedef typename M::Value Value;
723
724    ///Constructor
725
726    ///\e
727    ///
728    MapFunctor(const M &_m) : m(_m) {};
729    ///Returns a value of the map
730   
731    ///\e
732    ///
733    Value operator()(Key k) const {return m[k];}
734    ///\e
735    ///
736    Value operator[](Key k) const {return m[k];}
737  };
738 
739  ///Returns a \ref MapFunctor class
740
741  ///This function just returns a \ref MapFunctor class.
742  ///\relates MapFunctor
743  template<class M>
744  inline MapFunctor<M> mapFunctor(const M &m)
745  {
746    return MapFunctor<M>(m);
747  }
748
749
750  ///Apply all map setting operations to two maps
751
752  ///This map has two \ref concept::WriteMap "writable map"
753  ///parameters and each write request will be passed to both of them.
754  ///If \c M1 is also \ref concept::ReadMap "readable",
755  ///then the read operations will return the
756  ///corresponding values of \c M1.
757  ///
758  ///The \c Key and \c Value will be inherited from \c M1.
759  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
760
761  template<class M1,class M2>
762  class ForkMap
763  {
764    const M1 &m1;
765    const M2 &m2;
766  public:
767    typedef typename M1::Key Key;
768    typedef typename M1::Value Value;
769
770    ///Constructor
771
772    ///\e
773    ///
774    ForkMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
775    Value operator[](Key k) const {return m1[k];}
776    void set(Key k,const Value &v) {m1.set(k,v); m2.set(k,v);}
777  };
778 
779  ///Returns an \ref ForkMap class
780
781  ///This function just returns an \ref ForkMap class.
782  ///\todo How to call these type of functions?
783  ///
784  ///\relates ForkMap
785  ///\todo Wrong scope in Doxygen when \c \\relates is used
786  template<class M1,class M2>
787  inline ForkMap<M1,M2> forkMap(const M1 &m1,const M2 &m2)
788  {
789    return ForkMap<M1,M2>(m1,m2);
790  }
791
792  /// @}
793 
794}
795
796
797#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.