2 * lemon/maps.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
20 #include <lemon/graph_utils.h>
21 #include <lemon/utility.h>
26 ///\brief Miscellaneous property maps
28 ///\todo This file has the same name as the concept file in concept/,
29 /// and this is not easily detectable in docs...
38 /// Base class of maps.
40 /// Base class of maps.
41 /// It provides the necessary <tt>typedef</tt>s required by the map concept.
42 template<typename K, typename T>
52 /// Null map. (a.k.a. DoNothingMap)
54 /// If you have to provide a map only for its type definitions,
55 /// or if you have to provide a writable map, but
56 /// data written to it will sent to <tt>/dev/null</tt>...
57 template<typename K, typename T>
58 class NullMap : public MapBase<K,T>
62 typedef True NeedCopy;
64 /// Gives back a default constructed element.
65 T operator[](const K&) const { return T(); }
66 /// Absorbs the value.
67 void set(const K&, const T&) {}
70 template <typename K, typename V>
71 NullMap<K, V> nullMap() {
72 return NullMap<K, V>();
78 /// This is a readable map which assigns a specified value to each key.
79 /// In other aspects it is equivalent to the \ref NullMap.
80 /// \todo set could be used to set the value.
81 template<typename K, typename T>
82 class ConstMap : public MapBase<K,T>
87 typedef True NeedCopy;
89 /// Default constructor
91 /// The value of the map will be uninitialized.
92 /// (More exactly it will be default constructed.)
96 /// \param _v The initial value of the map.
98 ConstMap(const T &_v) : v(_v) {}
100 T operator[](const K&) const { return v; }
101 void set(const K&, const T&) {}
103 template<typename T1>
105 typedef ConstMap<K,T1> other;
108 template<typename T1>
109 ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}
112 ///Returns a \ref ConstMap class
114 ///This function just returns a \ref ConstMap class.
116 template<class V,class K>
117 inline ConstMap<V,K> constMap(const K &k)
119 return ConstMap<V,K>(k);
124 template<typename T, T v>
127 template<typename K, typename V, V v>
128 class ConstMap<K, Const<V, v> > : public MapBase<K, V>
132 V operator[](const K&) const { return v; }
133 void set(const K&, const V&) { }
136 /// \c std::map wrapper
138 /// This is essentially a wrapper for \c std::map. With addition that
139 /// you can specify a default value different from \c Value() .
141 /// \todo Provide allocator parameter...
142 template <typename K, typename T, typename Compare = std::less<K> >
143 class StdMap : public std::map<K,T,Compare> {
144 typedef std::map<K,T,Compare> parent;
146 typedef typename parent::value_type PairType;
154 typedef T& Reference;
156 typedef const T& ConstReference;
160 /// Constructor with specified default value
161 StdMap(const T& _v) : v(_v) {}
163 /// \brief Constructs the map from an appropriate std::map.
165 /// \warning Inefficient: copies the content of \c m !
166 StdMap(const parent &m) : parent(m) {}
167 /// \brief Constructs the map from an appropriate std::map, and explicitly
168 /// specifies a default value.
170 /// \warning Inefficient: copies the content of \c m !
171 StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
173 template<typename T1, typename Comp1>
174 StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {
178 Reference operator[](const Key &k) {
179 return insert(PairType(k,v)).first -> second;
181 ConstReference operator[](const Key &k) const {
182 typename parent::iterator i = lower_bound(k);
183 if (i == parent::end() || parent::key_comp()(k, (*i).first))
187 void set(const Key &k, const T &t) {
188 parent::operator[](k) = t;
191 /// Changes the default value of the map.
192 /// \return Returns the previous default value.
194 /// \warning The value of some keys (which has already been queried, but
195 /// the value has been unchanged from the default) may change!
196 T setDefault(const T &_v) { T old=v; v=_v; return old; }
198 template<typename T1>
200 typedef StdMap<Key,T1,Compare> other;
206 /// \addtogroup map_adaptors
209 /// \brief Identity mapping.
211 /// This mapping gives back the given key as value without any
213 template <typename T>
219 const Value& operator[](const Key& t) const {
224 ///Convert the \c Value of a maps to another type.
226 ///This \ref concept::ReadMap "read only map"
227 ///converts the \c Value of a maps to type \c T.
228 ///Its \c Value is inherited from \c M.
230 ///\bug wrong documentation
231 template<class M, class T>
233 typename SmartConstReference<M>::Type m;
236 typedef True NeedCopy;
239 typedef typename M::Key Key;
246 ///\param _m is the underlying map
247 ConvertMap(const M &_m) : m(_m) {};
249 /// \brief The subscript operator.
251 /// The subscript operator.
253 /// \return The target of the edge
254 Value operator[](Key k) const {return m[k];}
257 ///Returns an \ref ConvertMap class
259 ///This function just returns an \ref ConvertMap class.
260 ///\relates ConvertMap
261 ///\todo The order of the template parameters are changed.
262 template<class T, class M>
263 inline ConvertMap<M,T> convertMap(const M &m)
265 return ConvertMap<M,T>(m);
270 ///This \ref concept::ReadMap "read only map" returns the sum of the two
271 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
272 ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
274 template<class M1,class M2>
277 typename SmartConstReference<M1>::Type m1;
278 typename SmartConstReference<M2>::Type m2;
282 typedef True NeedCopy;
285 typedef typename M1::Key Key;
287 typedef typename M1::Value Value;
290 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
291 Value operator[](Key k) const {return m1[k]+m2[k];}
294 ///Returns an \ref AddMap class
296 ///This function just returns an \ref AddMap class.
297 ///\todo How to call these type of functions?
300 ///\todo Wrong scope in Doxygen when \c \\relates is used
301 template<class M1,class M2>
302 inline AddMap<M1,M2> addMap(const M1 &m1,const M2 &m2)
304 return AddMap<M1,M2>(m1,m2);
307 ///Shift a maps with a constant.
309 ///This \ref concept::ReadMap "read only map" returns the sum of the
310 ///given map and a constant value.
311 ///Its \c Key and \c Value is inherited from \c M.
315 /// ShiftMap<X> sh(x,v);
317 ///it is equivalent with
319 /// ConstMap<X::Key, X::Value> c_tmp(v);
320 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
325 typename SmartConstReference<M>::Type m;
329 typedef True NeedCopy;
331 typedef typename M::Key Key;
333 typedef typename M::Value Value;
338 ///\param _m is the undelying map
339 ///\param _v is the shift value
340 ShiftMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
341 Value operator[](Key k) const {return m[k]+v;}
344 ///Returns an \ref ShiftMap class
346 ///This function just returns an \ref ShiftMap class.
348 ///\todo A better name is required.
350 inline ShiftMap<M> shiftMap(const M &m,const typename M::Value &v)
352 return ShiftMap<M>(m,v);
355 ///Difference of two maps
357 ///This \ref concept::ReadMap "read only map" returns the difference
358 ///of the values returned by the two
359 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
360 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
362 template<class M1,class M2>
365 typename SmartConstReference<M1>::Type m1;
366 typename SmartConstReference<M2>::Type m2;
369 typedef True NeedCopy;
371 typedef typename M1::Key Key;
373 typedef typename M1::Value Value;
376 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
377 Value operator[](Key k) const {return m1[k]-m2[k];}
380 ///Returns a \ref SubMap class
382 ///This function just returns a \ref SubMap class.
385 template<class M1,class M2>
386 inline SubMap<M1,M2> subMap(const M1 &m1,const M2 &m2)
388 return SubMap<M1,M2>(m1,m2);
391 ///Product of two maps
393 ///This \ref concept::ReadMap "read only map" returns the product of the
394 ///values returned by the two
396 ///maps. Its \c Key and \c Value will be inherited from \c M1.
397 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
399 template<class M1,class M2>
402 typename SmartConstReference<M1>::Type m1;
403 typename SmartConstReference<M2>::Type m2;
406 typedef True NeedCopy;
408 typedef typename M1::Key Key;
410 typedef typename M1::Value Value;
413 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
414 Value operator[](Key k) const {return m1[k]*m2[k];}
417 ///Returns a \ref MulMap class
419 ///This function just returns a \ref MulMap class.
421 template<class M1,class M2>
422 inline MulMap<M1,M2> mulMap(const M1 &m1,const M2 &m2)
424 return MulMap<M1,M2>(m1,m2);
427 ///Scale a maps with a constant.
429 ///This \ref concept::ReadMap "read only map" returns the value of the
430 ///given map multipied with a constant value.
431 ///Its \c Key and \c Value is inherited from \c M.
435 /// ScaleMap<X> sc(x,v);
437 ///it is equivalent with
439 /// ConstMap<X::Key, X::Value> c_tmp(v);
440 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
445 typename SmartConstReference<M>::Type m;
449 typedef True NeedCopy;
451 typedef typename M::Key Key;
453 typedef typename M::Value Value;
458 ///\param _m is the undelying map
459 ///\param _v is the scaling value
460 ScaleMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
461 Value operator[](Key k) const {return m[k]*v;}
464 ///Returns an \ref ScaleMap class
466 ///This function just returns an \ref ScaleMap class.
468 ///\todo A better name is required.
470 inline ScaleMap<M> scaleMap(const M &m,const typename M::Value &v)
472 return ScaleMap<M>(m,v);
475 ///Quotient of two maps
477 ///This \ref concept::ReadMap "read only map" returns the quotient of the
478 ///values returned by the two
479 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
480 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
482 template<class M1,class M2>
485 typename SmartConstReference<M1>::Type m1;
486 typename SmartConstReference<M2>::Type m2;
489 typedef True NeedCopy;
491 typedef typename M1::Key Key;
493 typedef typename M1::Value Value;
496 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
497 Value operator[](Key k) const {return m1[k]/m2[k];}
500 ///Returns a \ref DivMap class
502 ///This function just returns a \ref DivMap class.
504 template<class M1,class M2>
505 inline DivMap<M1,M2> divMap(const M1 &m1,const M2 &m2)
507 return DivMap<M1,M2>(m1,m2);
510 ///Composition of two maps
512 ///This \ref concept::ReadMap "read only map" returns the composition of
514 ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
518 /// ComposeMap<M1,M2> cm(m1,m2);
520 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
522 ///Its \c Key is inherited from \c M2 and its \c Value is from
524 ///The \c M2::Value must be convertible to \c M1::Key.
525 ///\todo Check the requirements.
527 template<class M1,class M2>
530 typename SmartConstReference<M1>::Type m1;
531 typename SmartConstReference<M2>::Type m2;
534 typedef True NeedCopy;
536 typedef typename M2::Key Key;
538 typedef typename M1::Value Value;
541 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
542 Value operator[](Key k) const {return m1[m2[k]];}
544 ///Returns a \ref ComposeMap class
546 ///This function just returns a \ref ComposeMap class.
548 ///\relates ComposeMap
549 template<class M1,class M2>
550 inline ComposeMap<M1,M2> composeMap(const M1 &m1,const M2 &m2)
552 return ComposeMap<M1,M2>(m1,m2);
555 ///Combine of two maps using an STL (binary) functor.
557 ///Combine of two maps using an STL (binary) functor.
560 ///This \ref concept::ReadMap "read only map" takes to maps and a
561 ///binary functor and returns the composition of
563 ///given maps unsing the functor.
564 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
565 ///and \c f is of \c F,
568 /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
570 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
572 ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
573 ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
574 ///input parameter of \c F and the return type of \c F must be convertible
576 ///\todo Check the requirements.
578 template<class M1,class M2,class F,class V = typename F::result_type>
581 typename SmartConstReference<M1>::Type m1;
582 typename SmartConstReference<M2>::Type m2;
586 typedef True NeedCopy;
588 typedef typename M1::Key Key;
593 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
594 : m1(_m1), m2(_m2), f(_f) {};
595 Value operator[](Key k) const {return f(m1[k],m2[k]);}
598 ///Returns a \ref CombineMap class
600 ///This function just returns a \ref CombineMap class.
602 ///Only the first template parameter (the value type) must be given.
604 ///For example if \c m1 and \c m2 are both \c double valued maps, then
606 ///combineMap<double>(m1,m2,std::plus<double>)
608 ///is equivalent with
613 ///\relates CombineMap
614 template<class M1,class M2,class F>
615 inline CombineMap<M1,M2,F> combineMap(const M1 &m1,const M2 &m2,const F &f)
617 return CombineMap<M1,M2,F>(m1,m2,f);
620 ///Negative value of a map
622 ///This \ref concept::ReadMap "read only map" returns the negative
624 ///value returned by the
625 ///given map. Its \c Key and \c Value will be inherited from \c M.
626 ///The unary \c - operator must be defined for \c Value, of course.
631 typename SmartConstReference<M>::Type m;
634 typedef True NeedCopy;
636 typedef typename M::Key Key;
638 typedef typename M::Value Value;
641 NegMap(const M &_m) : m(_m) {};
642 Value operator[](Key k) const {return -m[k];}
645 ///Returns a \ref NegMap class
647 ///This function just returns a \ref NegMap class.
650 inline NegMap<M> negMap(const M &m)
656 ///Absolute value of a map
658 ///This \ref concept::ReadMap "read only map" returns the absolute value
660 ///value returned by the
661 ///given map. Its \c Key and \c Value will be inherited
662 ///from <tt>M</tt>. <tt>Value</tt>
663 ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
664 ///operator must be defined for it, of course.
666 ///\bug We need a unified way to handle the situation below:
668 /// struct _UnConvertible {};
669 /// template<class A> inline A t_abs(A a) {return _UnConvertible();}
670 /// template<> inline int t_abs<>(int n) {return abs(n);}
671 /// template<> inline long int t_abs<>(long int n) {return labs(n);}
672 /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
673 /// template<> inline float t_abs<>(float n) {return fabsf(n);}
674 /// template<> inline double t_abs<>(double n) {return fabs(n);}
675 /// template<> inline long double t_abs<>(long double n) {return fabsl(n);}
682 typename SmartConstReference<M>::Type m;
685 typedef True NeedCopy;
687 typedef typename M::Key Key;
689 typedef typename M::Value Value;
692 AbsMap(const M &_m) : m(_m) {};
693 Value operator[](Key k) const {Value tmp=m[k]; return tmp>=0?tmp:-tmp;}
696 ///Returns a \ref AbsMap class
698 ///This function just returns a \ref AbsMap class.
701 inline AbsMap<M> absMap(const M &m)
706 ///Converts an STL style functor to a map
708 ///This \ref concept::ReadMap "read only map" returns the value
712 ///Template parameters \c K and \c V will become its
713 ///\c Key and \c Value. They must be given explicitely
714 ///because a functor does not provide such typedefs.
716 ///Parameter \c F is the type of the used functor.
719 template<class K,class V,class F>
725 typedef True NeedCopy;
732 FunctorMap(const F &_f) : f(_f) {};
733 Value operator[](Key k) const {return f(k);}
736 ///Returns a \ref FunctorMap class
738 ///This function just returns a \ref FunctorMap class.
740 ///The third template parameter isn't necessary to be given.
741 ///\relates FunctorMap
742 template<class K,class V, class F>
743 inline FunctorMap<K,V,F> functorMap(const F &f)
745 return FunctorMap<K,V,F>(f);
748 ///Converts a map to an STL style (unary) functor
750 ///This class Converts a map to an STL style (unary) functor.
751 ///that is it provides an <tt>operator()</tt> to read its values.
753 ///For the sake of convenience it also works as
754 ///a ususal \ref concept::ReadMap "readable map", i.e
755 ///<tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
760 typename SmartConstReference<M>::Type m;
763 typedef True NeedCopy;
765 typedef typename M::Key argument_type;
767 typedef typename M::Value result_type;
769 typedef typename M::Key Key;
771 typedef typename M::Value Value;
777 MapFunctor(const M &_m) : m(_m) {};
778 ///Returns a value of the map
782 Value operator()(Key k) const {return m[k];}
785 Value operator[](Key k) const {return m[k];}
788 ///Returns a \ref MapFunctor class
790 ///This function just returns a \ref MapFunctor class.
791 ///\relates MapFunctor
793 inline MapFunctor<M> mapFunctor(const M &m)
795 return MapFunctor<M>(m);
799 ///Apply all map setting operations to two maps
801 ///This map has two \ref concept::WriteMap "writable map"
802 ///parameters and each write request will be passed to both of them.
803 ///If \c M1 is also \ref concept::ReadMap "readable",
804 ///then the read operations will return the
805 ///corresponding values of \c M1.
807 ///The \c Key and \c Value will be inherited from \c M1.
808 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
810 template<class M1,class M2>
813 typename SmartConstReference<M1>::Type m1;
814 typename SmartConstReference<M2>::Type m2;
817 typedef True NeedCopy;
819 typedef typename M1::Key Key;
821 typedef typename M1::Value Value;
827 ForkMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
828 Value operator[](Key k) const {return m1[k];}
829 void set(Key k,const Value &v) {m1.set(k,v); m2.set(k,v);}
832 ///Returns an \ref ForkMap class
834 ///This function just returns an \ref ForkMap class.
835 ///\todo How to call these type of functions?
838 ///\todo Wrong scope in Doxygen when \c \\relates is used
839 template<class M1,class M2>
840 inline ForkMap<M1,M2> forkMap(const M1 &m1,const M2 &m2)
842 return ForkMap<M1,M2>(m1,m2);
847 /* ************* BOOL MAPS ******************* */
849 ///Logical 'not' of a map
851 ///This bool \ref concept::ReadMap "read only map" returns the
852 ///logical negation of
853 ///value returned by the
854 ///given map. Its \c Key and will be inherited from \c M,
855 ///its Value is <tt>bool</tt>.
860 typename SmartConstReference<M>::Type m;
863 typedef True NeedCopy;
865 typedef typename M::Key Key;
873 NotMap(const M &_m) : m(_m) {};
874 Value operator[](Key k) const {return !m[k];}
877 ///Returns a \ref NotMap class
879 ///This function just returns a \ref NotMap class.
882 inline NotMap<M> notMap(const M &m)
900 #endif // LEMON_MAPS_H