Several doc improvements and fixes in maps.h and concepts/maps.h.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
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>
47 /// The key type of the map.
49 /// The value type of the map. (The type of objects associated with the keys).
53 /// Null map. (a.k.a. DoNothingMap)
55 /// This map can be used if you have to provide a map only for
56 /// its type definitions, or if you have to provide a writable map,
57 /// but data written to it is not required (i.e. it will be sent to
58 /// <tt>/dev/null</tt>).
59 template<typename K, typename T>
60 class NullMap : public MapBase<K, T> {
62 typedef MapBase<K, T> Parent;
63 typedef typename Parent::Key Key;
64 typedef typename Parent::Value Value;
66 /// Gives back a default constructed element.
67 T operator[](const K&) const { return T(); }
68 /// Absorbs the value.
69 void set(const K&, const T&) {}
72 ///Returns a \c NullMap class
74 ///This function just returns a \c NullMap class.
76 template <typename K, typename V>
77 NullMap<K, V> nullMap() {
78 return NullMap<K, V>();
84 /// This is a \ref concepts::ReadMap "readable" map which assigns a
85 /// specified value to each key.
86 /// In other aspects it is equivalent to \c NullMap.
87 template<typename K, typename T>
88 class ConstMap : public MapBase<K, T> {
93 typedef MapBase<K, T> Parent;
94 typedef typename Parent::Key Key;
95 typedef typename Parent::Value Value;
97 /// Default constructor
99 /// Default constructor.
100 /// The value of the map will be uninitialized.
101 /// (More exactly it will be default constructed.)
104 /// Constructor with specified initial value
106 /// Constructor with specified initial value.
107 /// \param _v is the initial value of the map.
108 ConstMap(const T &_v) : v(_v) {}
111 T operator[](const K&) const { return v; }
114 void setAll(const T &t) {
118 template<typename T1>
120 typedef ConstMap<K, T1> other;
123 template<typename T1>
124 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
127 ///Returns a \c ConstMap class
129 ///This function just returns a \c ConstMap class.
131 template<typename K, typename V>
132 inline ConstMap<K, V> constMap(const V &v) {
133 return ConstMap<K, V>(v);
137 template<typename T, T v>
140 /// Constant map with inlined constant value.
142 /// This is a \ref concepts::ReadMap "readable" map which assigns a
143 /// specified value to each key.
144 /// In other aspects it is equivalent to \c NullMap.
145 template<typename K, typename V, V v>
146 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
148 typedef MapBase<K, V> Parent;
149 typedef typename Parent::Key Key;
150 typedef typename Parent::Value Value;
154 V operator[](const K&) const { return v; }
156 void set(const K&, const V&) { }
159 ///Returns a \c ConstMap class with inlined value
161 ///This function just returns a \c ConstMap class with inlined value.
163 template<typename K, typename V, V v>
164 inline ConstMap<K, Const<V, v> > constMap() {
165 return ConstMap<K, Const<V, v> >();
168 ///Map based on \c std::map
170 ///This is essentially a wrapper for \c std::map with addition that
171 ///you can specify a default value different from \c Value() .
172 ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
173 template <typename K, typename T, typename Compare = std::less<K> >
174 class StdMap : public MapBase<K, T> {
175 template <typename K1, typename T1, typename C1>
179 typedef MapBase<K, T> Parent;
181 typedef typename Parent::Key Key;
183 typedef typename Parent::Value Value;
185 typedef T& Reference;
186 ///Const reference type
187 typedef const T& ConstReference;
189 typedef True ReferenceMapTag;
193 typedef std::map<K, T, Compare> Map;
199 /// Constructor with specified default value
200 StdMap(const T& value = T()) : _value(value) {}
201 /// \brief Constructs the map from an appropriate \c std::map, and
202 /// explicitly specifies a default value.
203 template <typename T1, typename Comp1>
204 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
205 : _map(map.begin(), map.end()), _value(value) {}
207 /// \brief Constructs a map from an other \ref StdMap.
208 template<typename T1, typename Comp1>
209 StdMap(const StdMap<Key, T1, Comp1> &c)
210 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
214 StdMap& operator=(const StdMap&);
219 Reference operator[](const Key &k) {
220 typename Map::iterator it = _map.lower_bound(k);
221 if (it != _map.end() && !_map.key_comp()(k, it->first))
224 return _map.insert(it, std::make_pair(k, _value))->second;
228 ConstReference operator[](const Key &k) const {
229 typename Map::const_iterator it = _map.find(k);
230 if (it != _map.end())
237 void set(const Key &k, const T &t) {
238 typename Map::iterator it = _map.lower_bound(k);
239 if (it != _map.end() && !_map.key_comp()(k, it->first))
242 _map.insert(it, std::make_pair(k, t));
246 void setAll(const T &t) {
251 template <typename T1, typename C1 = std::less<T1> >
253 typedef StdMap<Key, T1, C1> other;
257 ///Returns a \c StdMap class
259 ///This function just returns a \c StdMap class with specified
262 template<typename K, typename V, typename Compare>
263 inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
264 return StdMap<K, V, Compare>(value);
267 template<typename K, typename V>
268 inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {
269 return StdMap<K, V, std::less<K> >(value);
272 ///Returns a \c StdMap class created from an appropriate \c std::map
274 ///This function just returns a \c StdMap class created from an
275 ///appropriate \c std::map.
277 template<typename K, typename V, typename Compare>
278 inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,
279 const V& value = V() ) {
280 return StdMap<K, V, Compare>(map, value);
283 /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
285 /// This map has the <tt>[0..size-1]</tt> keyset and the values
286 /// are stored in a \c std::vector<T> container. It can be used with
287 /// some data structures, for example \c UnionFind, \c BinHeap, when
288 /// the used items are small integer numbers.
289 template <typename T>
290 class IntegerMap : public MapBase<int, T> {
292 template <typename T1>
293 friend class IntegerMap;
297 typedef MapBase<int, T> Parent;
299 typedef typename Parent::Key Key;
301 typedef typename Parent::Value Value;
303 typedef T& Reference;
305 typedef const T& ConstReference;
307 typedef True ReferenceMapTag;
311 typedef std::vector<T> Vector;
316 /// Constructor with specified default value
317 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
319 /// \brief Constructs the map from an appropriate \c std::vector.
320 template <typename T1>
321 IntegerMap(const std::vector<T1>& vector)
322 : _vector(vector.begin(), vector.end()) {}
324 /// \brief Constructs a map from an other \ref IntegerMap.
325 template <typename T1>
326 IntegerMap(const IntegerMap<T1> &c)
327 : _vector(c._vector.begin(), c._vector.end()) {}
329 /// \brief Resize the container
330 void resize(int size, const T& value = T()) {
331 _vector.resize(size, value);
336 IntegerMap& operator=(const IntegerMap&);
341 Reference operator[](Key k) {
346 ConstReference operator[](Key k) const {
351 void set(const Key &k, const T& t) {
357 ///Returns an \c IntegerMap class
359 ///This function just returns an \c IntegerMap class.
360 ///\relates IntegerMap
362 inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
363 return IntegerMap<T>(size, value);
368 /// \addtogroup map_adaptors
371 /// \brief Identity map.
373 /// This map gives back the given key as value without any
375 template <typename T>
376 class IdentityMap : public MapBase<T, T> {
378 typedef MapBase<T, T> Parent;
379 typedef typename Parent::Key Key;
380 typedef typename Parent::Value Value;
383 const T& operator[](const T& t) const {
388 ///Returns an \c IdentityMap class
390 ///This function just returns an \c IdentityMap class.
391 ///\relates IdentityMap
393 inline IdentityMap<T> identityMap() {
394 return IdentityMap<T>();
398 ///\brief Convert the \c Value of a map to another type using
399 ///the default conversion.
401 ///This \ref concepts::ReadMap "read only map"
402 ///converts the \c Value of a map to type \c T.
403 ///Its \c Key is inherited from \c M.
404 template <typename M, typename T>
405 class ConvertMap : public MapBase<typename M::Key, T> {
408 typedef MapBase<typename M::Key, T> Parent;
409 typedef typename Parent::Key Key;
410 typedef typename Parent::Value Value;
415 ///\param _m is the underlying map
416 ConvertMap(const M &_m) : m(_m) {};
419 Value operator[](const Key& k) const {return m[k];}
422 ///Returns a \c ConvertMap class
424 ///This function just returns a \c ConvertMap class.
425 ///\relates ConvertMap
426 template<typename T, typename M>
427 inline ConvertMap<M, T> convertMap(const M &m) {
428 return ConvertMap<M, T>(m);
431 ///Simple wrapping of a map
433 ///This \ref concepts::ReadMap "read only map" returns the simple
434 ///wrapping of the given map. Sometimes the reference maps cannot be
435 ///combined with simple read maps. This map adaptor wraps the given
436 ///map to simple read map.
438 ///\sa SimpleWriteMap
440 /// \todo Revise the misleading name
442 class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
446 typedef MapBase<typename M::Key, typename M::Value> Parent;
447 typedef typename Parent::Key Key;
448 typedef typename Parent::Value Value;
451 SimpleMap(const M &_m) : m(_m) {};
453 Value operator[](Key k) const {return m[k];}
456 ///Returns a \c SimpleMap class
458 ///This function just returns a \c SimpleMap class.
459 ///\relates SimpleMap
461 inline SimpleMap<M> simpleMap(const M &m) {
462 return SimpleMap<M>(m);
465 ///Simple writable wrapping of a map
467 ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
468 ///wrapping of the given map. Sometimes the reference maps cannot be
469 ///combined with simple read-write maps. This map adaptor wraps the
470 ///given map to simple read-write map.
474 /// \todo Revise the misleading name
476 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
480 typedef MapBase<typename M::Key, typename M::Value> Parent;
481 typedef typename Parent::Key Key;
482 typedef typename Parent::Value Value;
485 SimpleWriteMap(M &_m) : m(_m) {};
487 Value operator[](Key k) const {return m[k];}
489 void set(Key k, const Value& c) { m.set(k, c); }
492 ///Returns a \c SimpleWriteMap class
494 ///This function just returns a \c SimpleWriteMap class.
495 ///\relates SimpleWriteMap
497 inline SimpleWriteMap<M> simpleWriteMap(M &m) {
498 return SimpleWriteMap<M>(m);
503 ///This \ref concepts::ReadMap "read only map" returns the sum of the two
505 ///Its \c Key and \c Value are inherited from \c M1.
506 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
507 template<typename M1, typename M2>
508 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
513 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
514 typedef typename Parent::Key Key;
515 typedef typename Parent::Value Value;
518 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
520 Value operator[](Key k) const {return m1[k]+m2[k];}
523 ///Returns an \c AddMap class
525 ///This function just returns an \c AddMap class.
526 ///\todo How to call these type of functions?
529 template<typename M1, typename M2>
530 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
531 return AddMap<M1, M2>(m1,m2);
534 ///Shift a map with a constant.
536 ///This \ref concepts::ReadMap "read only map" returns the sum of the
537 ///given map and a constant value.
538 ///Its \c Key and \c Value is inherited from \c M.
542 /// ShiftMap<X> sh(x,v);
546 /// ConstMap<X::Key, X::Value> c_tmp(v);
547 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
551 template<typename M, typename C = typename M::Value>
552 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
556 typedef MapBase<typename M::Key, typename M::Value> Parent;
557 typedef typename Parent::Key Key;
558 typedef typename Parent::Value Value;
563 ///\param _m is the undelying map
564 ///\param _v is the shift value
565 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
567 Value operator[](Key k) const {return m[k] + v;}
570 ///Shift a map with a constant (ReadWrite version).
572 ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
573 ///given map and a constant value. It makes also possible to write the map.
574 ///Its \c Key and \c Value are inherited from \c M.
577 template<typename M, typename C = typename M::Value>
578 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
582 typedef MapBase<typename M::Key, typename M::Value> Parent;
583 typedef typename Parent::Key Key;
584 typedef typename Parent::Value Value;
589 ///\param _m is the undelying map
590 ///\param _v is the shift value
591 ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
593 Value operator[](Key k) const {return m[k] + v;}
595 void set(Key k, const Value& c) { m.set(k, c - v); }
598 ///Returns a \c ShiftMap class
600 ///This function just returns an \c ShiftMap class.
602 template<typename M, typename C>
603 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
604 return ShiftMap<M, C>(m,v);
607 ///Returns a \c ShiftWriteMap class
609 ///This function just returns a \c ShiftWriteMap class.
610 ///\relates ShiftWriteMap
611 template<typename M, typename C>
612 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
613 return ShiftWriteMap<M, C>(m,v);
616 ///Difference of two maps
618 ///This \ref concepts::ReadMap "read only map" returns the difference
619 ///of the values of the two given maps.
620 ///Its \c Key and \c Value are inherited from \c M1.
621 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
623 template<typename M1, typename M2>
624 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
628 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
629 typedef typename Parent::Key Key;
630 typedef typename Parent::Value Value;
633 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
635 Value operator[](Key k) const {return m1[k]-m2[k];}
638 ///Returns a \c SubMap class
640 ///This function just returns a \c SubMap class.
643 template<typename M1, typename M2>
644 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
645 return SubMap<M1, M2>(m1, m2);
648 ///Product of two maps
650 ///This \ref concepts::ReadMap "read only map" returns the product of the
651 ///values of the two given maps.
652 ///Its \c Key and \c Value are inherited from \c M1.
653 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
654 template<typename M1, typename M2>
655 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
659 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
660 typedef typename Parent::Key Key;
661 typedef typename Parent::Value Value;
664 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
666 Value operator[](Key k) const {return m1[k]*m2[k];}
669 ///Returns a \c MulMap class
671 ///This function just returns a \c MulMap class.
673 template<typename M1, typename M2>
674 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
675 return MulMap<M1, M2>(m1,m2);
678 ///Scales a map with a constant.
680 ///This \ref concepts::ReadMap "read only map" returns the value of the
681 ///given map multiplied from the left side with a constant value.
682 ///Its \c Key and \c Value are inherited from \c M.
686 /// ScaleMap<X> sc(x,v);
690 /// ConstMap<X::Key, X::Value> c_tmp(v);
691 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
695 template<typename M, typename C = typename M::Value>
696 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
700 typedef MapBase<typename M::Key, typename M::Value> Parent;
701 typedef typename Parent::Key Key;
702 typedef typename Parent::Value Value;
707 ///\param _m is the undelying map
708 ///\param _v is the scaling value
709 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
711 Value operator[](Key k) const {return v * m[k];}
714 ///Scales a map with a constant (ReadWrite version).
716 ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
717 ///given map multiplied from the left side with a constant value. It can
718 ///also be used as write map if the \c / operator is defined between
719 ///\c Value and \c C and the given multiplier is not zero.
720 ///Its \c Key and \c Value are inherited from \c M.
723 template<typename M, typename C = typename M::Value>
724 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
728 typedef MapBase<typename M::Key, typename M::Value> Parent;
729 typedef typename Parent::Key Key;
730 typedef typename Parent::Value Value;
735 ///\param _m is the undelying map
736 ///\param _v is the scaling value
737 ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
739 Value operator[](Key k) const {return v * m[k];}
741 void set(Key k, const Value& c) { m.set(k, c / v);}
744 ///Returns a \c ScaleMap class
746 ///This function just returns a \c ScaleMap class.
748 template<typename M, typename C>
749 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
750 return ScaleMap<M, C>(m,v);
753 ///Returns a \c ScaleWriteMap class
755 ///This function just returns a \c ScaleWriteMap class.
756 ///\relates ScaleWriteMap
757 template<typename M, typename C>
758 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
759 return ScaleWriteMap<M, C>(m,v);
762 ///Quotient of two maps
764 ///This \ref concepts::ReadMap "read only map" returns the quotient of the
765 ///values of the two given maps.
766 ///Its \c Key and \c Value are inherited from \c M1.
767 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
768 template<typename M1, typename M2>
769 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
773 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
774 typedef typename Parent::Key Key;
775 typedef typename Parent::Value Value;
778 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
780 Value operator[](Key k) const {return m1[k]/m2[k];}
783 ///Returns a \c DivMap class
785 ///This function just returns a \c DivMap class.
787 template<typename M1, typename M2>
788 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
789 return DivMap<M1, M2>(m1,m2);
792 ///Composition of two maps
794 ///This \ref concepts::ReadMap "read only map" returns the composition of
796 ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
799 /// ComposeMap<M1, M2> cm(m1,m2);
801 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
803 ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
804 ///\c M2::Value must be convertible to \c M1::Key.
808 ///\todo Check the requirements.
809 template <typename M1, typename M2>
810 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
814 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
815 typedef typename Parent::Key Key;
816 typedef typename Parent::Value Value;
819 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
821 typename MapTraits<M1>::ConstReturnValue
823 operator[](Key k) const {return m1[m2[k]];}
825 ///Returns a \c ComposeMap class
827 ///This function just returns a \c ComposeMap class.
829 ///\relates ComposeMap
830 template <typename M1, typename M2>
831 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
832 return ComposeMap<M1, M2>(m1,m2);
835 ///Combine of two maps using an STL (binary) functor.
837 ///Combine of two maps using an STL (binary) functor.
839 ///This \ref concepts::ReadMap "read only map" takes two maps and a
840 ///binary functor and returns the composition of the two
841 ///given maps unsing the functor.
842 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
843 ///and \c f is of \c F, then for
845 /// CombineMap<M1, M2,F,V> cm(m1,m2,f);
847 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
849 ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
850 ///\c M2::Value and \c M1::Value must be convertible to the corresponding
851 ///input parameter of \c F and the return type of \c F must be convertible
856 ///\todo Check the requirements.
857 template<typename M1, typename M2, typename F,
858 typename V = typename F::result_type>
859 class CombineMap : public MapBase<typename M1::Key, V> {
864 typedef MapBase<typename M1::Key, V> Parent;
865 typedef typename Parent::Key Key;
866 typedef typename Parent::Value Value;
869 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
870 : m1(_m1), m2(_m2), f(_f) {};
872 Value operator[](Key k) const {return f(m1[k],m2[k]);}
875 ///Returns a \c CombineMap class
877 ///This function just returns a \c CombineMap class.
879 ///For example if \c m1 and \c m2 are both \c double valued maps, then
881 ///combineMap(m1,m2,std::plus<double>())
888 ///This function is specialized for adaptable binary function
889 ///classes and C++ functions.
891 ///\relates CombineMap
892 template<typename M1, typename M2, typename F, typename V>
893 inline CombineMap<M1, M2, F, V>
894 combineMap(const M1& m1,const M2& m2, const F& f) {
895 return CombineMap<M1, M2, F, V>(m1,m2,f);
898 template<typename M1, typename M2, typename F>
899 inline CombineMap<M1, M2, F, typename F::result_type>
900 combineMap(const M1& m1, const M2& m2, const F& f) {
901 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
904 template<typename M1, typename M2, typename K1, typename K2, typename V>
905 inline CombineMap<M1, M2, V (*)(K1, K2), V>
906 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
907 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
910 ///Negative value of a map
912 ///This \ref concepts::ReadMap "read only map" returns the negative
913 ///value of the value returned by the given map.
914 ///Its \c Key and \c Value are inherited from \c M.
915 ///The unary \c - operator must be defined for \c Value, of course.
919 class NegMap : public MapBase<typename M::Key, typename M::Value> {
922 typedef MapBase<typename M::Key, typename M::Value> Parent;
923 typedef typename Parent::Key Key;
924 typedef typename Parent::Value Value;
927 NegMap(const M &_m) : m(_m) {};
929 Value operator[](Key k) const {return -m[k];}
932 ///Negative value of a map (ReadWrite version)
934 ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
935 ///value of the value returned by the given map.
936 ///Its \c Key and \c Value are inherited from \c M.
937 ///The unary \c - operator must be defined for \c Value, of course.
941 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
944 typedef MapBase<typename M::Key, typename M::Value> Parent;
945 typedef typename Parent::Key Key;
946 typedef typename Parent::Value Value;
949 NegWriteMap(M &_m) : m(_m) {};
951 Value operator[](Key k) const {return -m[k];}
953 void set(Key k, const Value& v) { m.set(k, -v); }
956 ///Returns a \c NegMap class
958 ///This function just returns a \c NegMap class.
960 template <typename M>
961 inline NegMap<M> negMap(const M &m) {
965 ///Returns a \c NegWriteMap class
967 ///This function just returns a \c NegWriteMap class.
968 ///\relates NegWriteMap
969 template <typename M>
970 inline NegWriteMap<M> negMap(M &m) {
971 return NegWriteMap<M>(m);
974 ///Absolute value of a map
976 ///This \ref concepts::ReadMap "read only map" returns the absolute value
977 ///of the value returned by the given map.
978 ///Its \c Key and \c Value are inherited from \c M.
979 ///\c Value must be comparable to \c 0 and the unary \c -
980 ///operator must be defined for it, of course.
982 ///\bug We need a unified way to handle the situation below:
984 /// struct _UnConvertible {};
985 /// template<class A> inline A t_abs(A a) {return _UnConvertible();}
986 /// template<> inline int t_abs<>(int n) {return abs(n);}
987 /// template<> inline long int t_abs<>(long int n) {return labs(n);}
988 /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
989 /// template<> inline float t_abs<>(float n) {return fabsf(n);}
990 /// template<> inline double t_abs<>(double n) {return fabs(n);}
991 /// template<> inline long double t_abs<>(long double n) {return fabsl(n);}
996 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
999 typedef MapBase<typename M::Key, typename M::Value> Parent;
1000 typedef typename Parent::Key Key;
1001 typedef typename Parent::Value Value;
1004 AbsMap(const M &_m) : m(_m) {};
1006 Value operator[](Key k) const {
1008 return tmp >= 0 ? tmp : -tmp;
1013 ///Returns an \c AbsMap class
1015 ///This function just returns an \c AbsMap class.
1017 template<typename M>
1018 inline AbsMap<M> absMap(const M &m) {
1019 return AbsMap<M>(m);
1022 ///Converts an STL style functor to a map
1024 ///This \ref concepts::ReadMap "read only map" returns the value
1025 ///of a given functor.
1027 ///Template parameters \c K and \c V will become its
1028 ///\c Key and \c Value.
1029 ///In most cases they have to be given explicitly because a
1030 ///functor typically does not provide \c argument_type and
1031 ///\c result_type typedefs.
1033 ///Parameter \c F is the type of the used functor.
1036 template<typename F,
1037 typename K = typename F::argument_type,
1038 typename V = typename F::result_type>
1039 class FunctorMap : public MapBase<K, V> {
1042 typedef MapBase<K, V> Parent;
1043 typedef typename Parent::Key Key;
1044 typedef typename Parent::Value Value;
1047 FunctorMap(const F &_f = F()) : f(_f) {}
1049 Value operator[](Key k) const { return f(k);}
1052 ///Returns a \c FunctorMap class
1054 ///This function just returns a \c FunctorMap class.
1056 ///This function is specialized for adaptable binary function
1057 ///classes and C++ functions.
1059 ///\relates FunctorMap
1060 template<typename K, typename V, typename F> inline
1061 FunctorMap<F, K, V> functorMap(const F &f) {
1062 return FunctorMap<F, K, V>(f);
1065 template <typename F> inline
1066 FunctorMap<F, typename F::argument_type, typename F::result_type>
1067 functorMap(const F &f) {
1068 return FunctorMap<F, typename F::argument_type,
1069 typename F::result_type>(f);
1072 template <typename K, typename V> inline
1073 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
1074 return FunctorMap<V (*)(K), K, V>(f);
1078 ///Converts a map to an STL style (unary) functor
1080 ///This class Converts a map to an STL style (unary) functor.
1081 ///That is it provides an <tt>operator()</tt> to read its values.
1083 ///For the sake of convenience it also works as
1084 ///a ususal \ref concepts::ReadMap "readable map",
1085 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1088 template <typename M>
1089 class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1092 typedef MapBase<typename M::Key, typename M::Value> Parent;
1093 typedef typename Parent::Key Key;
1094 typedef typename Parent::Value Value;
1096 typedef typename M::Key argument_type;
1097 typedef typename M::Value result_type;
1100 MapFunctor(const M &_m) : m(_m) {};
1102 Value operator()(Key k) const {return m[k];}
1104 Value operator[](Key k) const {return m[k];}
1107 ///Returns a \c MapFunctor class
1109 ///This function just returns a \c MapFunctor class.
1110 ///\relates MapFunctor
1111 template<typename M>
1112 inline MapFunctor<M> mapFunctor(const M &m) {
1113 return MapFunctor<M>(m);
1116 ///Just readable version of \ref ForkWriteMap
1118 ///This map has two \ref concepts::ReadMap "readable map"
1119 ///parameters and each read request will be passed just to the
1120 ///first map. This class is the just readable map type of \c ForkWriteMap.
1122 ///The \c Key and \c Value are inherited from \c M1.
1123 ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1127 template<typename M1, typename M2>
1128 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1132 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1133 typedef typename Parent::Key Key;
1134 typedef typename Parent::Value Value;
1137 ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1139 Value operator[](Key k) const {return m1[k];}
1143 ///Applies all map setting operations to two maps
1145 ///This map has two \ref concepts::WriteMap "writable map"
1146 ///parameters and each write request will be passed to both of them.
1147 ///If \c M1 is also \ref concepts::ReadMap "readable",
1148 ///then the read operations will return the
1149 ///corresponding values of \c M1.
1151 ///The \c Key and \c Value are inherited from \c M1.
1152 ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1155 template<typename M1, typename M2>
1156 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1160 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1161 typedef typename Parent::Key Key;
1162 typedef typename Parent::Value Value;
1165 ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1167 Value operator[](Key k) const {return m1[k];}
1169 void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1172 ///Returns a \c ForkMap class
1174 ///This function just returns a \c ForkMap class.
1176 template <typename M1, typename M2>
1177 inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1178 return ForkMap<M1, M2>(m1,m2);
1181 ///Returns a \c ForkWriteMap class
1183 ///This function just returns a \c ForkWriteMap class.
1184 ///\relates ForkWriteMap
1185 template <typename M1, typename M2>
1186 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1187 return ForkWriteMap<M1, M2>(m1,m2);
1192 /* ************* BOOL MAPS ******************* */
1194 ///Logical 'not' of a map
1196 ///This bool \ref concepts::ReadMap "read only map" returns the
1197 ///logical negation of the value returned by the given map.
1198 ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1201 template <typename M>
1202 class NotMap : public MapBase<typename M::Key, bool> {
1205 typedef MapBase<typename M::Key, bool> Parent;
1206 typedef typename Parent::Key Key;
1207 typedef typename Parent::Value Value;
1210 NotMap(const M &_m) : m(_m) {};
1212 Value operator[](Key k) const {return !m[k];}
1215 ///Logical 'not' of a map (ReadWrie version)
1217 ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
1218 ///logical negation of the value returned by the given map. When it is set,
1219 ///the opposite value is set to the original map.
1220 ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1223 template <typename M>
1224 class NotWriteMap : public MapBase<typename M::Key, bool> {
1227 typedef MapBase<typename M::Key, bool> Parent;
1228 typedef typename Parent::Key Key;
1229 typedef typename Parent::Value Value;
1232 NotWriteMap(M &_m) : m(_m) {};
1234 Value operator[](Key k) const {return !m[k];}
1236 void set(Key k, bool v) { m.set(k, !v); }
1239 ///Returns a \c NotMap class
1241 ///This function just returns a \c NotMap class.
1243 template <typename M>
1244 inline NotMap<M> notMap(const M &m) {
1245 return NotMap<M>(m);
1248 ///Returns a \c NotWriteMap class
1250 ///This function just returns a \c NotWriteMap class.
1251 ///\relates NotWriteMap
1252 template <typename M>
1253 inline NotWriteMap<M> notMap(M &m) {
1254 return NotWriteMap<M>(m);
1257 namespace _maps_bits {
1259 template <typename Value>
1261 typedef Value argument_type;
1262 typedef Value result_type;
1263 Value operator()(const Value& val) const {
1268 template <typename _Iterator, typename Enable = void>
1269 struct IteratorTraits {
1270 typedef typename std::iterator_traits<_Iterator>::value_type Value;
1273 template <typename _Iterator>
1274 struct IteratorTraits<_Iterator,
1275 typename exists<typename _Iterator::container_type>::type>
1277 typedef typename _Iterator::container_type::value_type Value;
1283 /// \brief Writable bool map for logging each \c true assigned element
1285 /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
1286 /// each \c true assigned element, i.e it copies all the keys set
1287 /// to \c true to the given iterator.
1289 /// \note The container of the iterator should contain space
1290 /// for each element.
1292 /// The following example shows how you can write the edges found by
1293 /// the \ref Prim algorithm directly to the standard output.
1295 /// typedef IdMap<UGraph, UEdge> UEdgeIdMap;
1296 /// UEdgeIdMap uedgeId(ugraph);
1298 /// typedef MapFunctor<UEdgeIdMap> UEdgeIdFunctor;
1299 /// UEdgeIdFunctor uedgeIdFunctor(uedgeId);
1301 /// StoreBoolMap<ostream_iterator<int>, UEdgeIdFunctor>
1302 /// writerMap(ostream_iterator<int>(cout, " "), uedgeIdFunctor);
1304 /// prim(ugraph, cost, writerMap);
1307 ///\sa BackInserterBoolMap
1308 ///\sa FrontInserterBoolMap
1309 ///\sa InserterBoolMap
1310 template <typename _Iterator,
1312 _maps_bits::Identity<typename _maps_bits::
1313 IteratorTraits<_Iterator>::Value> >
1314 class StoreBoolMap {
1316 typedef _Iterator Iterator;
1318 typedef typename _Functor::argument_type Key;
1321 typedef _Functor Functor;
1324 StoreBoolMap(Iterator it, const Functor& functor = Functor())
1325 : _begin(it), _end(it), _functor(functor) {}
1327 /// Gives back the given iterator set for the first key
1328 Iterator begin() const {
1332 /// Gives back the the 'after the last' iterator
1333 Iterator end() const {
1337 /// The \c set function of the map
1338 void set(const Key& key, Value value) const {
1340 *_end++ = _functor(key);
1346 mutable Iterator _end;
1350 /// \brief Writable bool map for logging each \c true assigned element in
1351 /// a back insertable container.
1353 /// Writable bool map for logging each \c true assigned element by pushing
1354 /// them into a back insertable container.
1355 /// It can be used to retrieve the items into a standard
1356 /// container. The next example shows how you can store the
1357 /// edges found by the Prim algorithm in a vector.
1360 /// vector<UEdge> span_tree_uedges;
1361 /// BackInserterBoolMap<vector<UEdge> > inserter_map(span_tree_uedges);
1362 /// prim(ugraph, cost, inserter_map);
1366 ///\sa FrontInserterBoolMap
1367 ///\sa InserterBoolMap
1368 template <typename Container,
1370 _maps_bits::Identity<typename Container::value_type> >
1371 class BackInserterBoolMap {
1373 typedef typename Functor::argument_type Key;
1377 BackInserterBoolMap(Container& _container,
1378 const Functor& _functor = Functor())
1379 : container(_container), functor(_functor) {}
1381 /// The \c set function of the map
1382 void set(const Key& key, Value value) {
1384 container.push_back(functor(key));
1389 Container& container;
1393 /// \brief Writable bool map for logging each \c true assigned element in
1394 /// a front insertable container.
1396 /// Writable bool map for logging each \c true assigned element by pushing
1397 /// them into a front insertable container.
1398 /// It can be used to retrieve the items into a standard
1399 /// container. For example see \ref BackInserterBoolMap.
1401 ///\sa BackInserterBoolMap
1402 ///\sa InserterBoolMap
1403 template <typename Container,
1405 _maps_bits::Identity<typename Container::value_type> >
1406 class FrontInserterBoolMap {
1408 typedef typename Functor::argument_type Key;
1412 FrontInserterBoolMap(Container& _container,
1413 const Functor& _functor = Functor())
1414 : container(_container), functor(_functor) {}
1416 /// The \c set function of the map
1417 void set(const Key& key, Value value) {
1419 container.push_front(functor(key));
1424 Container& container;
1428 /// \brief Writable bool map for storing each \c true assigned element in
1429 /// an insertable container.
1431 /// Writable bool map for storing each \c true assigned element in an
1432 /// insertable container. It will insert all the keys set to \c true into
1435 /// For example, if you want to store the cut arcs of the strongly
1436 /// connected components in a set you can use the next code:
1439 /// set<Edge> cut_edges;
1440 /// InserterBoolMap<set<Edge> > inserter_map(cut_edges);
1441 /// stronglyConnectedCutEdges(graph, cost, inserter_map);
1444 ///\sa BackInserterBoolMap
1445 ///\sa FrontInserterBoolMap
1446 template <typename Container,
1448 _maps_bits::Identity<typename Container::value_type> >
1449 class InserterBoolMap {
1451 typedef typename Container::value_type Key;
1454 /// Constructor with specified iterator
1456 /// Constructor with specified iterator.
1457 /// \param _container The container for storing the elements.
1458 /// \param _it The elements will be inserted before this iterator.
1459 /// \param _functor The functor that is used when an element is stored.
1460 InserterBoolMap(Container& _container, typename Container::iterator _it,
1461 const Functor& _functor = Functor())
1462 : container(_container), it(_it), functor(_functor) {}
1466 /// Constructor without specified iterator.
1467 /// The elements will be inserted before <tt>_container.end()</tt>.
1468 /// \param _container The container for storing the elements.
1469 /// \param _functor The functor that is used when an element is stored.
1470 InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1471 : container(_container), it(_container.end()), functor(_functor) {}
1473 /// The \c set function of the map
1474 void set(const Key& key, Value value) {
1476 it = container.insert(it, functor(key));
1482 Container& container;
1483 typename Container::iterator it;
1487 /// \brief Writable bool map for filling each \c true assigned element with a
1490 /// Writable bool map for filling each \c true assigned element with a
1491 /// given value. The value can set the container.
1493 /// The following code finds the connected components of a graph
1494 /// and stores it in the \c comp map:
1496 /// typedef UGraph::NodeMap<int> ComponentMap;
1497 /// ComponentMap comp(ugraph);
1498 /// typedef FillBoolMap<UGraph::NodeMap<int> > ComponentFillerMap;
1499 /// ComponentFillerMap filler(comp, 0);
1501 /// Dfs<UGraph>::DefProcessedMap<ComponentFillerMap>::Create dfs(ugraph);
1502 /// dfs.processedMap(filler);
1504 /// for (NodeIt it(ugraph); it != INVALID; ++it) {
1505 /// if (!dfs.reached(it)) {
1506 /// dfs.addSource(it);
1508 /// ++filler.fillValue();
1512 template <typename Map>
1515 typedef typename Map::Key Key;
1519 FillBoolMap(Map& _map, const typename Map::Value& _fill)
1520 : map(_map), fill(_fill) {}
1523 FillBoolMap(Map& _map)
1524 : map(_map), fill() {}
1526 /// Gives back the current fill value
1527 const typename Map::Value& fillValue() const {
1531 /// Gives back the current fill value
1532 typename Map::Value& fillValue() {
1536 /// Sets the current fill value
1537 void fillValue(const typename Map::Value& _fill) {
1541 /// The \c set function of the map
1542 void set(const Key& key, Value value) {
1550 typename Map::Value fill;
1554 /// \brief Writable bool map for storing the sequence number of
1555 /// \c true assignments.
1557 /// Writable bool map that stores for each \c true assigned elements
1558 /// the sequence number of this setting.
1559 /// It makes it easy to calculate the leaving
1560 /// order of the nodes in the \c Dfs algorithm.
1563 /// typedef Graph::NodeMap<int> OrderMap;
1564 /// OrderMap order(graph);
1565 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1566 /// OrderSetterMap setter(order);
1567 /// Dfs<Graph>::DefProcessedMap<OrderSetterMap>::Create dfs(graph);
1568 /// dfs.processedMap(setter);
1570 /// for (NodeIt it(graph); it != INVALID; ++it) {
1571 /// if (!dfs.reached(it)) {
1572 /// dfs.addSource(it);
1578 /// The storing of the discovering order is more difficult because the
1579 /// ReachedMap should be readable in the dfs algorithm but the setting
1580 /// order map is not readable. Thus we must use the fork map:
1583 /// typedef Graph::NodeMap<int> OrderMap;
1584 /// OrderMap order(graph);
1585 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1586 /// OrderSetterMap setter(order);
1587 /// typedef Graph::NodeMap<bool> StoreMap;
1588 /// StoreMap store(graph);
1590 /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1591 /// ReachedMap reached(store, setter);
1593 /// Dfs<Graph>::DefReachedMap<ReachedMap>::Create dfs(graph);
1594 /// dfs.reachedMap(reached);
1596 /// for (NodeIt it(graph); it != INVALID; ++it) {
1597 /// if (!dfs.reached(it)) {
1598 /// dfs.addSource(it);
1603 template <typename Map>
1604 class SettingOrderBoolMap {
1606 typedef typename Map::Key Key;
1610 SettingOrderBoolMap(Map& _map)
1611 : map(_map), counter(0) {}
1613 /// Number of set operations.
1618 /// The \c set function of the map
1619 void set(const Key& key, Value value) {
1621 map.set(key, counter++);
1633 #endif // LEMON_MAPS_H