3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
26 #include <lemon/bits/utility.h>
27 // #include <lemon/bits/traits.h>
31 ///\brief Miscellaneous property maps
40 /// Base class of maps.
42 /// Base class of maps.
43 /// It provides the necessary <tt>typedef</tt>s required by the map concept.
44 template<typename K, typename T>
53 /// Null map. (a.k.a. DoNothingMap)
55 /// If you have to provide a map only for its type definitions,
56 /// or if you have to provide a writable map, but
57 /// data written to it will sent to <tt>/dev/null</tt>...
58 template<typename K, typename T>
59 class NullMap : public MapBase<K, T> {
61 typedef MapBase<K, T> Parent;
62 typedef typename Parent::Key Key;
63 typedef typename Parent::Value Value;
65 /// Gives back a default constructed element.
66 T operator[](const K&) const { return T(); }
67 /// Absorbs the value.
68 void set(const K&, const T&) {}
71 template <typename K, typename V>
72 NullMap<K, V> nullMap() {
73 return NullMap<K, V>();
79 /// This is a readable map which assigns a specified value to each key.
80 /// In other aspects it is equivalent to the \c NullMap.
81 template<typename K, typename T>
82 class ConstMap : public MapBase<K, T> {
87 typedef MapBase<K, T> Parent;
88 typedef typename Parent::Key Key;
89 typedef typename Parent::Value Value;
91 /// Default constructor
93 /// The value of the map will be uninitialized.
94 /// (More exactly it will be default constructed.)
98 /// \param _v The initial value of the map.
100 ConstMap(const T &_v) : v(_v) {}
103 T operator[](const K&) const { return v; }
106 void setAll(const T &t) {
110 template<typename T1>
112 typedef ConstMap<K, T1> other;
115 template<typename T1>
116 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
119 ///Returns a \c ConstMap class
121 ///This function just returns a \c ConstMap class.
123 template<typename K, typename V>
124 inline ConstMap<K, V> constMap(const V &v) {
125 return ConstMap<K, V>(v);
129 template<typename T, T v>
132 /// Constant map with inlined constant value.
134 /// This is a readable map which assigns a specified value to each key.
135 /// In other aspects it is equivalent to the \c NullMap.
136 template<typename K, typename V, V v>
137 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
139 typedef MapBase<K, V> Parent;
140 typedef typename Parent::Key Key;
141 typedef typename Parent::Value Value;
145 V operator[](const K&) const { return v; }
147 void set(const K&, const V&) { }
150 ///Returns a \c ConstMap class
152 ///This function just returns a \c ConstMap class with inlined value.
154 template<typename K, typename V, V v>
155 inline ConstMap<K, Const<V, v> > constMap() {
156 return ConstMap<K, Const<V, v> >();
159 ///Map based on std::map
161 ///This is essentially a wrapper for \c std::map. With addition that
162 ///you can specify a default value different from \c Value() .
163 template <typename K, typename T, typename Compare = std::less<K> >
165 template <typename K1, typename T1, typename C1>
169 typedef True ReferenceMapTag;
175 typedef T& Reference;
177 typedef const T& ConstReference;
181 typedef std::map<K, T, Compare> Map;
187 /// Constructor with specified default value
188 StdMap(const T& value = T()) : _value(value) {}
189 /// \brief Constructs the map from an appropriate std::map, and explicitly
190 /// specifies a default value.
191 template <typename T1, typename Comp1>
192 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
193 : _map(map.begin(), map.end()), _value(value) {}
195 /// \brief Constructs a map from an other StdMap.
196 template<typename T1, typename Comp1>
197 StdMap(const StdMap<Key, T1, Comp1> &c)
198 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
202 StdMap& operator=(const StdMap&);
207 Reference operator[](const Key &k) {
208 typename Map::iterator it = _map.lower_bound(k);
209 if (it != _map.end() && !_map.key_comp()(k, it->first))
212 return _map.insert(it, std::make_pair(k, _value))->second;
216 ConstReference operator[](const Key &k) const {
217 typename Map::const_iterator it = _map.find(k);
218 if (it != _map.end())
225 void set(const Key &k, const T &t) {
226 typename Map::iterator it = _map.lower_bound(k);
227 if (it != _map.end() && !_map.key_comp()(k, it->first))
230 _map.insert(it, std::make_pair(k, t));
234 void setAll(const T &t) {
239 template <typename T1, typename C1 = std::less<T1> >
241 typedef StdMap<Key, T1, C1> other;
245 /// \brief Map for storing values for the range \c [0..size-1] range keys
247 /// The current map has the \c [0..size-1] keyset and the values
248 /// are stored in a \c std::vector<T> container. It can be used with
249 /// some data structures, for example \c UnionFind, \c BinHeap, when
250 /// the used items are small integer numbers.
251 template <typename T>
254 template <typename T1>
255 friend class IntegerMap;
259 typedef True ReferenceMapTag;
265 typedef T& Reference;
267 typedef const T& ConstReference;
271 typedef std::vector<T> Vector;
276 /// Constructor with specified default value
277 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
279 /// \brief Constructs the map from an appropriate std::vector.
280 template <typename T1>
281 IntegerMap(const std::vector<T1>& vector)
282 : _vector(vector.begin(), vector.end()) {}
284 /// \brief Constructs a map from an other IntegerMap.
285 template <typename T1>
286 IntegerMap(const IntegerMap<T1> &c)
287 : _vector(c._vector.begin(), c._vector.end()) {}
289 /// \brief Resize the container
290 void resize(int size, const T& value = T()) {
291 _vector.resize(size, value);
296 IntegerMap& operator=(const IntegerMap&);
301 Reference operator[](Key k) {
306 ConstReference operator[](Key k) const {
311 void set(const Key &k, const T& t) {
319 /// \addtogroup map_adaptors
322 /// \brief Identity mapping.
324 /// This mapping gives back the given key as value without any
326 template <typename T>
327 class IdentityMap : public MapBase<T, T> {
329 typedef MapBase<T, T> Parent;
330 typedef typename Parent::Key Key;
331 typedef typename Parent::Value Value;
334 const T& operator[](const T& t) const {
339 ///Returns an \c IdentityMap class
341 ///This function just returns an \c IdentityMap class.
342 ///\relates IdentityMap
344 inline IdentityMap<T> identityMap() {
345 return IdentityMap<T>();
349 ///Convert the \c Value of a map to another type.
351 ///This \c concepts::ReadMap "read only map"
352 ///converts the \c Value of a maps to type \c T.
353 ///Its \c Key is inherited from \c M.
354 template <typename M, typename T>
355 class ConvertMap : public MapBase<typename M::Key, T> {
358 typedef MapBase<typename M::Key, T> Parent;
359 typedef typename Parent::Key Key;
360 typedef typename Parent::Value Value;
365 ///\param _m is the underlying map
366 ConvertMap(const M &_m) : m(_m) {};
368 /// \brief The subscript operator.
370 /// The subscript operator.
372 /// \return The target of the arc
373 Value operator[](const Key& k) const {return m[k];}
376 ///Returns an \c ConvertMap class
378 ///This function just returns an \c ConvertMap class.
379 ///\relates ConvertMap
380 template<typename T, typename M>
381 inline ConvertMap<M, T> convertMap(const M &m) {
382 return ConvertMap<M, T>(m);
385 ///Simple wrapping of the map
387 ///This \c concepts::ReadMap "read only map" returns the simple
388 ///wrapping of the given map. Sometimes the reference maps cannot be
389 ///combined with simple read maps. This map adaptor wraps the given
390 ///map to simple read map.
392 class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
396 typedef MapBase<typename M::Key, typename M::Value> Parent;
397 typedef typename Parent::Key Key;
398 typedef typename Parent::Value Value;
401 SimpleMap(const M &_m) : m(_m) {};
403 Value operator[](Key k) const {return m[k];}
406 ///Simple writeable wrapping of the map
408 ///This \c concepts::ReadMap "read only map" returns the simple
409 ///wrapping of the given map. Sometimes the reference maps cannot be
410 ///combined with simple read-write maps. This map adaptor wraps the
411 ///given map to simple read-write map.
413 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
417 typedef MapBase<typename M::Key, typename M::Value> Parent;
418 typedef typename Parent::Key Key;
419 typedef typename Parent::Value Value;
422 SimpleWriteMap(M &_m) : m(_m) {};
424 Value operator[](Key k) const {return m[k];}
426 void set(Key k, const Value& c) { m.set(k, c); }
431 ///This \c concepts::ReadMap "read only map" returns the sum of the two
432 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
433 ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
435 template<typename M1, typename M2>
436 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
441 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
442 typedef typename Parent::Key Key;
443 typedef typename Parent::Value Value;
446 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
448 Value operator[](Key k) const {return m1[k]+m2[k];}
451 ///Returns an \c AddMap class
453 ///This function just returns an \c AddMap class.
454 ///\todo How to call these type of functions?
457 template<typename M1, typename M2>
458 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
459 return AddMap<M1, M2>(m1,m2);
462 ///Shift a map with a constant.
464 ///This \c concepts::ReadMap "read only map" returns the sum of the
465 ///given map and a constant value.
466 ///Its \c Key and \c Value is inherited from \c M.
470 /// ShiftMap<X> sh(x,v);
472 ///is equivalent with
474 /// ConstMap<X::Key, X::Value> c_tmp(v);
475 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
477 template<typename M, typename C = typename M::Value>
478 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
482 typedef MapBase<typename M::Key, typename M::Value> Parent;
483 typedef typename Parent::Key Key;
484 typedef typename Parent::Value Value;
489 ///\param _m is the undelying map
490 ///\param _v is the shift value
491 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
493 Value operator[](Key k) const {return m[k] + v;}
496 ///Shift a map with a constant.
498 ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
499 ///given map and a constant value. It makes also possible to write the map.
500 ///Its \c Key and \c Value is inherited from \c M.
504 /// ShiftMap<X> sh(x,v);
506 ///is equivalent with
508 /// ConstMap<X::Key, X::Value> c_tmp(v);
509 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
511 template<typename M, typename C = typename M::Value>
512 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
516 typedef MapBase<typename M::Key, typename M::Value> Parent;
517 typedef typename Parent::Key Key;
518 typedef typename Parent::Value Value;
523 ///\param _m is the undelying map
524 ///\param _v is the shift value
525 ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
527 Value operator[](Key k) const {return m[k] + v;}
529 void set(Key k, const Value& c) { m.set(k, c - v); }
532 ///Returns an \c ShiftMap class
534 ///This function just returns an \c ShiftMap class.
536 template<typename M, typename C>
537 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
538 return ShiftMap<M, C>(m,v);
541 template<typename M, typename C>
542 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
543 return ShiftWriteMap<M, C>(m,v);
546 ///Difference of two maps
548 ///This \c concepts::ReadMap "read only map" returns the difference
549 ///of the values of the two
550 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
551 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
553 template<typename M1, typename M2>
554 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
558 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
559 typedef typename Parent::Key Key;
560 typedef typename Parent::Value Value;
563 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
565 Value operator[](Key k) const {return m1[k]-m2[k];}
568 ///Returns a \c SubMap class
570 ///This function just returns a \c SubMap class.
573 template<typename M1, typename M2>
574 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
575 return SubMap<M1, M2>(m1, m2);
578 ///Product of two maps
580 ///This \c concepts::ReadMap "read only map" returns the product of the
583 ///maps. Its \c Key and \c Value will be inherited from \c M1.
584 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
586 template<typename M1, typename M2>
587 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
591 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
592 typedef typename Parent::Key Key;
593 typedef typename Parent::Value Value;
596 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
598 Value operator[](Key k) const {return m1[k]*m2[k];}
601 ///Returns a \c MulMap class
603 ///This function just returns a \c MulMap class.
605 template<typename M1, typename M2>
606 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
607 return MulMap<M1, M2>(m1,m2);
610 ///Scales a maps with a constant.
612 ///This \c concepts::ReadMap "read only map" returns the value of the
613 ///given map multiplied from the left side with a constant value.
614 ///Its \c Key and \c Value is inherited from \c M.
618 /// ScaleMap<X> sc(x,v);
620 ///is equivalent with
622 /// ConstMap<X::Key, X::Value> c_tmp(v);
623 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
625 template<typename M, typename C = typename M::Value>
626 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
630 typedef MapBase<typename M::Key, typename M::Value> Parent;
631 typedef typename Parent::Key Key;
632 typedef typename Parent::Value Value;
637 ///\param _m is the undelying map
638 ///\param _v is the scaling value
639 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
641 Value operator[](Key k) const {return v * m[k];}
644 ///Scales a maps with a constant.
646 ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
647 ///given map multiplied from the left side with a constant value. It can
648 ///be used as write map also if the given multiplier is not zero.
649 ///Its \c Key and \c Value is inherited from \c M.
650 template<typename M, typename C = typename M::Value>
651 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
655 typedef MapBase<typename M::Key, typename M::Value> Parent;
656 typedef typename Parent::Key Key;
657 typedef typename Parent::Value Value;
662 ///\param _m is the undelying map
663 ///\param _v is the scaling value
664 ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
666 Value operator[](Key k) const {return v * m[k];}
668 void set(Key k, const Value& c) { m.set(k, c / v);}
671 ///Returns an \c ScaleMap class
673 ///This function just returns an \c ScaleMap class.
675 template<typename M, typename C>
676 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
677 return ScaleMap<M, C>(m,v);
680 template<typename M, typename C>
681 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
682 return ScaleWriteMap<M, C>(m,v);
685 ///Quotient of two maps
687 ///This \c concepts::ReadMap "read only map" returns the quotient of the
689 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
690 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
692 template<typename M1, typename M2>
693 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
697 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
698 typedef typename Parent::Key Key;
699 typedef typename Parent::Value Value;
702 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
704 Value operator[](Key k) const {return m1[k]/m2[k];}
707 ///Returns a \c DivMap class
709 ///This function just returns a \c DivMap class.
711 template<typename M1, typename M2>
712 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
713 return DivMap<M1, M2>(m1,m2);
716 ///Composition of two maps
718 ///This \c concepts::ReadMap "read only map" returns the composition of
720 ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
724 /// ComposeMap<M1, M2> cm(m1,m2);
726 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
728 ///Its \c Key is inherited from \c M2 and its \c Value is from
730 ///The \c M2::Value must be convertible to \c M1::Key.
731 ///\todo Check the requirements.
732 template <typename M1, typename M2>
733 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
737 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
738 typedef typename Parent::Key Key;
739 typedef typename Parent::Value Value;
742 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
747 /// \todo Use the MapTraits once it is ported.
750 //typename MapTraits<M1>::ConstReturnValue
752 operator[](Key k) const {return m1[m2[k]];}
754 ///Returns a \c ComposeMap class
756 ///This function just returns a \c ComposeMap class.
758 ///\relates ComposeMap
759 template <typename M1, typename M2>
760 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
761 return ComposeMap<M1, M2>(m1,m2);
764 ///Combines of two maps using an STL (binary) functor.
766 ///Combines of two maps using an STL (binary) functor.
769 ///This \c concepts::ReadMap "read only map" takes two maps and a
770 ///binary functor and returns the composition of
772 ///given maps unsing the functor.
773 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
774 ///and \c f is of \c F,
777 /// CombineMap<M1, M2,F,V> cm(m1,m2,f);
779 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
781 ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
782 ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
783 ///input parameter of \c F and the return type of \c F must be convertible
785 ///\todo Check the requirements.
786 template<typename M1, typename M2, typename F,
787 typename V = typename F::result_type>
788 class CombineMap : public MapBase<typename M1::Key, V> {
793 typedef MapBase<typename M1::Key, V> Parent;
794 typedef typename Parent::Key Key;
795 typedef typename Parent::Value Value;
798 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
799 : m1(_m1), m2(_m2), f(_f) {};
801 Value operator[](Key k) const {return f(m1[k],m2[k]);}
804 ///Returns a \c CombineMap class
806 ///This function just returns a \c CombineMap class.
808 ///For example if \c m1 and \c m2 are both \c double valued maps, then
810 ///combineMap<double>(m1,m2,std::plus<double>())
812 ///is equivalent with
817 ///This function is specialized for adaptable binary function
818 ///classes and c++ functions.
820 ///\relates CombineMap
821 template<typename M1, typename M2, typename F, typename V>
822 inline CombineMap<M1, M2, F, V>
823 combineMap(const M1& m1,const M2& m2, const F& f) {
824 return CombineMap<M1, M2, F, V>(m1,m2,f);
827 template<typename M1, typename M2, typename F>
828 inline CombineMap<M1, M2, F, typename F::result_type>
829 combineMap(const M1& m1, const M2& m2, const F& f) {
830 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
833 template<typename M1, typename M2, typename K1, typename K2, typename V>
834 inline CombineMap<M1, M2, V (*)(K1, K2), V>
835 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
836 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
839 ///Negative value of a map
841 ///This \c concepts::ReadMap "read only map" returns the negative
843 ///value returned by the
844 ///given map. Its \c Key and \c Value will be inherited from \c M.
845 ///The unary \c - operator must be defined for \c Value, of course.
848 class NegMap : public MapBase<typename M::Key, typename M::Value> {
851 typedef MapBase<typename M::Key, typename M::Value> Parent;
852 typedef typename Parent::Key Key;
853 typedef typename Parent::Value Value;
856 NegMap(const M &_m) : m(_m) {};
858 Value operator[](Key k) const {return -m[k];}
861 ///Negative value of a map
863 ///This \c concepts::ReadWriteMap "read-write map" returns the negative
864 ///value of the value returned by the
865 ///given map. Its \c Key and \c Value will be inherited from \c M.
866 ///The unary \c - operator must be defined for \c Value, of course.
869 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
872 typedef MapBase<typename M::Key, typename M::Value> Parent;
873 typedef typename Parent::Key Key;
874 typedef typename Parent::Value Value;
877 NegWriteMap(M &_m) : m(_m) {};
879 Value operator[](Key k) const {return -m[k];}
881 void set(Key k, const Value& v) { m.set(k, -v); }
884 ///Returns a \c NegMap class
886 ///This function just returns a \c NegMap class.
888 template <typename M>
889 inline NegMap<M> negMap(const M &m) {
893 template <typename M>
894 inline NegWriteMap<M> negMap(M &m) {
895 return NegWriteMap<M>(m);
898 ///Absolute value of a map
900 ///This \c concepts::ReadMap "read only map" returns the absolute value
902 ///value returned by the
903 ///given map. Its \c Key and \c Value will be inherited
904 ///from <tt>M</tt>. <tt>Value</tt>
905 ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
906 ///operator must be defined for it, of course.
908 ///\bug We need a unified way to handle the situation below:
910 /// struct _UnConvertible {};
911 /// template<class A> inline A t_abs(A a) {return _UnConvertible();}
912 /// template<> inline int t_abs<>(int n) {return abs(n);}
913 /// template<> inline long int t_abs<>(long int n) {return labs(n);}
914 /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
915 /// template<> inline float t_abs<>(float n) {return fabsf(n);}
916 /// template<> inline double t_abs<>(double n) {return fabs(n);}
917 /// template<> inline long double t_abs<>(long double n) {return fabsl(n);}
922 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
925 typedef MapBase<typename M::Key, typename M::Value> Parent;
926 typedef typename Parent::Key Key;
927 typedef typename Parent::Value Value;
930 AbsMap(const M &_m) : m(_m) {};
932 Value operator[](Key k) const {
934 return tmp >= 0 ? tmp : -tmp;
939 ///Returns a \c AbsMap class
941 ///This function just returns a \c AbsMap class.
944 inline AbsMap<M> absMap(const M &m) {
948 ///Converts an STL style functor to a map
950 ///This \c concepts::ReadMap "read only map" returns the value
954 ///Template parameters \c K and \c V will become its
955 ///\c Key and \c Value. They must be given explicitely
956 ///because a functor does not provide such typedefs.
958 ///Parameter \c F is the type of the used functor.
960 typename K = typename F::argument_type,
961 typename V = typename F::result_type>
962 class FunctorMap : public MapBase<K, V> {
965 typedef MapBase<K, V> Parent;
966 typedef typename Parent::Key Key;
967 typedef typename Parent::Value Value;
970 FunctorMap(const F &_f = F()) : f(_f) {}
972 Value operator[](Key k) const { return f(k);}
975 ///Returns a \c FunctorMap class
977 ///This function just returns a \c FunctorMap class.
979 ///It is specialized for adaptable function classes and
981 ///\relates FunctorMap
982 template<typename K, typename V, typename F> inline
983 FunctorMap<F, K, V> functorMap(const F &f) {
984 return FunctorMap<F, K, V>(f);
987 template <typename F> inline
988 FunctorMap<F, typename F::argument_type, typename F::result_type>
989 functorMap(const F &f) {
990 return FunctorMap<F, typename F::argument_type,
991 typename F::result_type>(f);
994 template <typename K, typename V> inline
995 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
996 return FunctorMap<V (*)(K), K, V>(f);
1000 ///Converts a map to an STL style (unary) functor
1002 ///This class Converts a map to an STL style (unary) functor.
1003 ///that is it provides an <tt>operator()</tt> to read its values.
1005 ///For the sake of convenience it also works as
1006 ///a ususal \c concepts::ReadMap "readable map",
1007 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1008 template <typename M>
1009 class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1012 typedef MapBase<typename M::Key, typename M::Value> Parent;
1013 typedef typename Parent::Key Key;
1014 typedef typename Parent::Value Value;
1016 typedef typename M::Key argument_type;
1017 typedef typename M::Value result_type;
1020 MapFunctor(const M &_m) : m(_m) {};
1022 Value operator()(Key k) const {return m[k];}
1024 Value operator[](Key k) const {return m[k];}
1027 ///Returns a \c MapFunctor class
1029 ///This function just returns a \c MapFunctor class.
1030 ///\relates MapFunctor
1031 template<typename M>
1032 inline MapFunctor<M> mapFunctor(const M &m) {
1033 return MapFunctor<M>(m);
1036 ///Applies all map setting operations to two maps
1038 ///This map has two \c concepts::ReadMap "readable map"
1039 ///parameters and each read request will be passed just to the
1040 ///first map. This class is the just readable map type of the ForkWriteMap.
1042 ///The \c Key and \c Value will be inherited from \c M1.
1043 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1044 template<typename M1, typename M2>
1045 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1049 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1050 typedef typename Parent::Key Key;
1051 typedef typename Parent::Value Value;
1054 ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1056 Value operator[](Key k) const {return m1[k];}
1060 ///Applies all map setting operations to two maps
1062 ///This map has two \c concepts::WriteMap "writable map"
1063 ///parameters and each write request will be passed to both of them.
1064 ///If \c M1 is also \c concepts::ReadMap "readable",
1065 ///then the read operations will return the
1066 ///corresponding values of \c M1.
1068 ///The \c Key and \c Value will be inherited from \c M1.
1069 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1070 template<typename M1, typename M2>
1071 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1075 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1076 typedef typename Parent::Key Key;
1077 typedef typename Parent::Value Value;
1080 ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1082 Value operator[](Key k) const {return m1[k];}
1084 void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1087 ///Returns an \c ForkMap class
1089 ///This function just returns an \c ForkMap class.
1092 template <typename M1, typename M2>
1093 inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1094 return ForkMap<M1, M2>(m1,m2);
1097 template <typename M1, typename M2>
1098 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1099 return ForkWriteMap<M1, M2>(m1,m2);
1104 /* ************* BOOL MAPS ******************* */
1106 ///Logical 'not' of a map
1108 ///This bool \c concepts::ReadMap "read only map" returns the
1109 ///logical negation of
1110 ///value returned by the
1111 ///given map. Its \c Key and will be inherited from \c M,
1112 ///its Value is <tt>bool</tt>.
1113 template <typename M>
1114 class NotMap : public MapBase<typename M::Key, bool> {
1117 typedef MapBase<typename M::Key, bool> Parent;
1118 typedef typename Parent::Key Key;
1119 typedef typename Parent::Value Value;
1122 NotMap(const M &_m) : m(_m) {};
1124 Value operator[](Key k) const {return !m[k];}
1127 ///Logical 'not' of a map with writing possibility
1129 ///This bool \c concepts::ReadWriteMap "read-write map" returns the
1130 ///logical negation of value returned by the given map. When it is set,
1131 ///the opposite value is set to the original map.
1132 ///Its \c Key and will be inherited from \c M,
1133 ///its Value is <tt>bool</tt>.
1134 template <typename M>
1135 class NotWriteMap : public MapBase<typename M::Key, bool> {
1138 typedef MapBase<typename M::Key, bool> Parent;
1139 typedef typename Parent::Key Key;
1140 typedef typename Parent::Value Value;
1143 NotWriteMap(M &_m) : m(_m) {};
1145 Value operator[](Key k) const {return !m[k];}
1147 void set(Key k, bool v) { m.set(k, !v); }
1150 ///Returns a \c NotMap class
1152 ///This function just returns a \c NotMap class.
1154 template <typename M>
1155 inline NotMap<M> notMap(const M &m) {
1156 return NotMap<M>(m);
1159 template <typename M>
1160 inline NotWriteMap<M> notMap(M &m) {
1161 return NotWriteMap<M>(m);
1164 namespace _maps_bits {
1166 template <typename Value>
1168 typedef Value argument_type;
1169 typedef Value result_type;
1170 Value operator()(const Value& val) const {
1175 template <typename _Iterator, typename Enable = void>
1176 struct IteratorTraits {
1177 typedef typename std::iterator_traits<_Iterator>::value_type Value;
1180 template <typename _Iterator>
1181 struct IteratorTraits<_Iterator,
1182 typename exists<typename _Iterator::container_type>::type>
1184 typedef typename _Iterator::container_type::value_type Value;
1190 /// \brief Writable bool map for store each true assigned elements.
1192 /// Writable bool map to store each true assigned elements. It will
1193 /// copies all the keys set to true to the given iterator.
1195 /// \note The container of the iterator should contain space
1196 /// for each element.
1198 /// The next example shows how can you write the nodes directly
1199 /// to the standard output.
1201 /// typedef IdMap<Graph, Edge> EdgeIdMap;
1202 /// EdgeIdMap edgeId(graph);
1204 /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
1205 /// EdgeIdFunctor edgeIdFunctor(edgeId);
1207 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
1208 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1210 /// prim(graph, cost, writerMap);
1212 template <typename _Iterator,
1214 _maps_bits::Identity<typename _maps_bits::
1215 IteratorTraits<_Iterator>::Value> >
1216 class StoreBoolMap {
1218 typedef _Iterator Iterator;
1220 typedef typename _Functor::argument_type Key;
1223 typedef _Functor Functor;
1226 StoreBoolMap(Iterator it, const Functor& functor = Functor())
1227 : _begin(it), _end(it), _functor(functor) {}
1229 /// Gives back the given iterator set for the first time.
1230 Iterator begin() const {
1234 /// Gives back the iterator after the last set operation.
1235 Iterator end() const {
1239 /// Setter function of the map
1240 void set(const Key& key, Value value) const {
1242 *_end++ = _functor(key);
1248 mutable Iterator _end;
1252 /// \brief Writable bool map for store each true assigned elements in
1253 /// a back insertable container.
1255 /// Writable bool map for store each true assigned elements in a back
1256 /// insertable container. It will push back all the keys set to true into
1257 /// the container. It can be used to retrieve the items into a standard
1258 /// container. The next example shows how can you store the undirected
1259 /// arcs in a vector with prim algorithm.
1262 /// vector<Edge> span_tree_edges;
1263 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1264 /// prim(graph, cost, inserter_map);
1266 template <typename Container,
1268 _maps_bits::Identity<typename Container::value_type> >
1269 class BackInserterBoolMap {
1271 typedef typename Container::value_type Key;
1275 BackInserterBoolMap(Container& _container,
1276 const Functor& _functor = Functor())
1277 : container(_container), functor(_functor) {}
1279 /// Setter function of the map
1280 void set(const Key& key, Value value) {
1282 container.push_back(functor(key));
1287 Container& container;
1291 /// \brief Writable bool map for store each true assigned elements in
1292 /// a front insertable container.
1294 /// Writable bool map for store each true assigned elements in a front
1295 /// insertable container. It will push front all the keys set to \c true into
1296 /// the container. For example see the BackInserterBoolMap.
1297 template <typename Container,
1299 _maps_bits::Identity<typename Container::value_type> >
1300 class FrontInserterBoolMap {
1302 typedef typename Container::value_type Key;
1306 FrontInserterBoolMap(Container& _container,
1307 const Functor& _functor = Functor())
1308 : container(_container), functor(_functor) {}
1310 /// Setter function of the map
1311 void set(const Key& key, Value value) {
1313 container.push_front(key);
1318 Container& container;
1322 /// \brief Writable bool map for store each true assigned elements in
1323 /// an insertable container.
1325 /// Writable bool map for store each true assigned elements in an
1326 /// insertable container. It will insert all the keys set to \c true into
1327 /// the container. If you want to store the cut arcs of the strongly
1328 /// connected components in a set you can use the next code:
1331 /// set<Arc> cut_arcs;
1332 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1333 /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1335 template <typename Container,
1337 _maps_bits::Identity<typename Container::value_type> >
1338 class InserterBoolMap {
1340 typedef typename Container::value_type Key;
1344 InserterBoolMap(Container& _container, typename Container::iterator _it,
1345 const Functor& _functor = Functor())
1346 : container(_container), it(_it), functor(_functor) {}
1349 InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1350 : container(_container), it(_container.end()), functor(_functor) {}
1352 /// Setter function of the map
1353 void set(const Key& key, Value value) {
1355 it = container.insert(it, key);
1361 Container& container;
1362 typename Container::iterator it;
1366 /// \brief Fill the true set elements with a given value.
1368 /// Writable bool map to fill the elements set to \c true with a given value.
1369 /// The value can set
1372 /// The next code finds the connected components of the undirected digraph
1373 /// and stores it in the \c comp map:
1375 /// typedef Graph::NodeMap<int> ComponentMap;
1376 /// ComponentMap comp(graph);
1377 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1378 /// ComponentFillerMap filler(comp, 0);
1380 /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1381 /// dfs.processedMap(filler);
1383 /// for (NodeIt it(graph); it != INVALID; ++it) {
1384 /// if (!dfs.reached(it)) {
1385 /// dfs.addSource(it);
1387 /// ++filler.fillValue();
1391 template <typename Map>
1394 typedef typename Map::Key Key;
1398 FillBoolMap(Map& _map, const typename Map::Value& _fill)
1399 : map(_map), fill(_fill) {}
1402 FillBoolMap(Map& _map)
1403 : map(_map), fill() {}
1405 /// Gives back the current fill value
1406 const typename Map::Value& fillValue() const {
1410 /// Gives back the current fill value
1411 typename Map::Value& fillValue() {
1415 /// Sets the current fill value
1416 void fillValue(const typename Map::Value& _fill) {
1420 /// Setter function of the map
1421 void set(const Key& key, Value value) {
1429 typename Map::Value fill;
1433 /// \brief Writable bool map which stores for each true assigned elements
1434 /// the setting order number.
1436 /// Writable bool map which stores for each true assigned elements
1437 /// the setting order number. It make easy to calculate the leaving
1438 /// order of the nodes in the \c Dfs algorithm.
1441 /// typedef Digraph::NodeMap<int> OrderMap;
1442 /// OrderMap order(digraph);
1443 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1444 /// OrderSetterMap setter(order);
1445 /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1446 /// dfs.processedMap(setter);
1448 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1449 /// if (!dfs.reached(it)) {
1450 /// dfs.addSource(it);
1456 /// The discovering order can be stored a little harder because the
1457 /// ReachedMap should be readable in the dfs algorithm but the setting
1458 /// order map is not readable. Now we should use the fork map:
1461 /// typedef Digraph::NodeMap<int> OrderMap;
1462 /// OrderMap order(digraph);
1463 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1464 /// OrderSetterMap setter(order);
1465 /// typedef Digraph::NodeMap<bool> StoreMap;
1466 /// StoreMap store(digraph);
1468 /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1469 /// ReachedMap reached(store, setter);
1471 /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1472 /// dfs.reachedMap(reached);
1474 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1475 /// if (!dfs.reached(it)) {
1476 /// dfs.addSource(it);
1481 template <typename Map>
1482 class SettingOrderBoolMap {
1484 typedef typename Map::Key Key;
1488 SettingOrderBoolMap(Map& _map)
1489 : map(_map), counter(0) {}
1491 /// Number of set operations.
1496 /// Setter function of the map
1497 void set(const Key& key, Value value) {
1499 map.set(key, counter++);
1511 #endif // LEMON_MAPS_H