Minor doc fixes.
Replaced \c by \ref and \ref by \c to work properly and to be uniform.
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>
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 readable map which assigns a specified value to each key.
85 /// In other aspects it is equivalent to the \c NullMap.
86 template<typename K, typename T>
87 class ConstMap : public MapBase<K, T> {
92 typedef MapBase<K, T> Parent;
93 typedef typename Parent::Key Key;
94 typedef typename Parent::Value Value;
96 /// Default constructor
98 /// Default constructor.
99 /// The value of the map will be uninitialized.
100 /// (More exactly it will be default constructed.)
103 /// Constructor with specified initial value
105 /// Constructor with specified initial value.
106 /// \param _v is the initial value of the map.
107 ConstMap(const T &_v) : v(_v) {}
110 T operator[](const K&) const { return v; }
113 void setAll(const T &t) {
117 template<typename T1>
118 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
121 ///Returns a \c ConstMap class
123 ///This function just returns a \c ConstMap class.
125 template<typename K, typename V>
126 inline ConstMap<K, V> constMap(const V &v) {
127 return ConstMap<K, V>(v);
131 template<typename T, T v>
134 /// Constant map with inlined constant value.
136 /// This is a readable map which assigns a specified value to each key.
137 /// In other aspects it is equivalent to the \c NullMap.
138 template<typename K, typename V, V v>
139 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
141 typedef MapBase<K, V> Parent;
142 typedef typename Parent::Key Key;
143 typedef typename Parent::Value Value;
147 V operator[](const K&) const { return v; }
149 void set(const K&, const V&) { }
152 ///Returns a \c ConstMap class
154 ///This function just returns a \c ConstMap class with inlined value.
156 template<typename K, typename V, V v>
157 inline ConstMap<K, Const<V, v> > constMap() {
158 return ConstMap<K, Const<V, v> >();
161 ///Map based on \c std::map
163 ///This is essentially a wrapper for \c std::map with addition that
164 ///you can specify a default value different from \c Value().
165 template <typename K, typename T, typename Compare = std::less<K> >
166 class StdMap : public MapBase<K, T> {
167 template <typename K1, typename T1, typename C1>
171 typedef MapBase<K, T> Parent;
173 typedef typename Parent::Key Key;
175 typedef typename Parent::Value Value;
177 typedef T& Reference;
179 typedef const T& ConstReference;
181 typedef True ReferenceMapTag;
185 typedef std::map<K, T, Compare> Map;
191 /// Constructor with specified default value
192 StdMap(const T& value = T()) : _value(value) {}
193 /// \brief Constructs the map from an appropriate std::map, and explicitly
194 /// specifies a default value.
195 template <typename T1, typename Comp1>
196 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
197 : _map(map.begin(), map.end()), _value(value) {}
199 /// \brief Constructs a map from an other StdMap.
200 template<typename T1, typename Comp1>
201 StdMap(const StdMap<Key, T1, Comp1> &c)
202 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
206 StdMap& operator=(const StdMap&);
211 Reference operator[](const Key &k) {
212 typename Map::iterator it = _map.lower_bound(k);
213 if (it != _map.end() && !_map.key_comp()(k, it->first))
216 return _map.insert(it, std::make_pair(k, _value))->second;
220 ConstReference operator[](const Key &k) const {
221 typename Map::const_iterator it = _map.find(k);
222 if (it != _map.end())
229 void set(const Key &k, const T &t) {
230 typename Map::iterator it = _map.lower_bound(k);
231 if (it != _map.end() && !_map.key_comp()(k, it->first))
234 _map.insert(it, std::make_pair(k, t));
238 void setAll(const T &t) {
245 ///Returns a \c StdMap class
247 ///This function just returns a \c StdMap class with specified
250 template<typename K, typename V, typename Compare = std::less<K> >
251 inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
252 return StdMap<K, V, Compare>(value);
255 ///Returns a \c StdMap class created from an appropriate std::map
257 ///This function just returns a \c StdMap class created from an
258 ///appropriate std::map.
260 template<typename K, typename V, typename Compare = std::less<K> >
261 inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,
262 const V& value = V() ) {
263 return StdMap<K, V, Compare>(map, value);
266 /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
268 /// The current map has the <tt>[0..size-1]</tt> keyset and the values
269 /// are stored in a \c std::vector<T> container. It can be used with
270 /// some data structures, for example \c UnionFind, \c BinHeap, when
271 /// the used items are small integer numbers.
273 /// \todo Revise its name
274 template <typename T>
275 class IntegerMap : public MapBase<int, T> {
277 template <typename T1>
278 friend class IntegerMap;
282 typedef MapBase<int, T> Parent;
284 typedef typename Parent::Key Key;
286 typedef typename Parent::Value Value;
288 typedef T& Reference;
290 typedef const T& ConstReference;
292 typedef True ReferenceMapTag;
296 typedef std::vector<T> Vector;
301 /// Constructor with specified default value
302 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
304 /// \brief Constructs the map from an appropriate std::vector.
305 template <typename T1>
306 IntegerMap(const std::vector<T1>& vector)
307 : _vector(vector.begin(), vector.end()) {}
309 /// \brief Constructs a map from an other IntegerMap.
310 template <typename T1>
311 IntegerMap(const IntegerMap<T1> &c)
312 : _vector(c._vector.begin(), c._vector.end()) {}
314 /// \brief Resize the container
315 void resize(int size, const T& value = T()) {
316 _vector.resize(size, value);
321 IntegerMap& operator=(const IntegerMap&);
326 Reference operator[](Key k) {
331 ConstReference operator[](Key k) const {
336 void set(const Key &k, const T& t) {
342 ///Returns an \c IntegerMap class
344 ///This function just returns an \c IntegerMap class.
345 ///\relates IntegerMap
347 inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
348 return IntegerMap<T>(size, value);
353 /// \addtogroup map_adaptors
356 /// \brief Identity map.
358 /// This map gives back the given key as value without any
360 template <typename T>
361 class IdentityMap : public MapBase<T, T> {
363 typedef MapBase<T, T> Parent;
364 typedef typename Parent::Key Key;
365 typedef typename Parent::Value Value;
368 const T& operator[](const T& t) const {
373 ///Returns an \c IdentityMap class
375 ///This function just returns an \c IdentityMap class.
376 ///\relates IdentityMap
378 inline IdentityMap<T> identityMap() {
379 return IdentityMap<T>();
383 ///\brief Convert the \c Value of a map to another type using
384 ///the default conversion.
386 ///This \ref concepts::ReadMap "read only map"
387 ///converts the \c Value of a map to type \c T.
388 ///Its \c Key is inherited from \c M.
389 template <typename M, typename T>
390 class ConvertMap : public MapBase<typename M::Key, T> {
393 typedef MapBase<typename M::Key, T> Parent;
394 typedef typename Parent::Key Key;
395 typedef typename Parent::Value Value;
400 ///\param _m is the underlying map.
401 ConvertMap(const M &_m) : m(_m) {};
403 /// \brief The subscript operator.
405 /// The subscript operator.
406 Value operator[](const Key& k) const {return m[k];}
409 ///Returns a \c ConvertMap class
411 ///This function just returns a \c ConvertMap class.
412 ///\relates ConvertMap
413 template<typename T, typename M>
414 inline ConvertMap<M, T> convertMap(const M &m) {
415 return ConvertMap<M, T>(m);
418 ///Simple wrapping of a map
420 ///This \ref concepts::ReadMap "read only map" returns the simple
421 ///wrapping of the given map. Sometimes the reference maps cannot be
422 ///combined with simple read maps. This map adaptor wraps the given
423 ///map to simple read map.
425 ///\sa SimpleWriteMap
427 /// \todo Revise the misleading name
429 class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
433 typedef MapBase<typename M::Key, typename M::Value> Parent;
434 typedef typename Parent::Key Key;
435 typedef typename Parent::Value Value;
438 SimpleMap(const M &_m) : m(_m) {};
440 Value operator[](Key k) const {return m[k];}
443 ///Returns a \c SimpleMap class
445 ///This function just returns a \c SimpleMap class.
446 ///\relates SimpleMap
448 inline SimpleMap<M> simpleMap(const M &m) {
449 return SimpleMap<M>(m);
452 ///Simple writable wrapping of a map
454 ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
455 ///wrapping of the given map. Sometimes the reference maps cannot be
456 ///combined with simple read-write maps. This map adaptor wraps the
457 ///given map to simple read-write map.
461 /// \todo Revise the misleading name
463 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
467 typedef MapBase<typename M::Key, typename M::Value> Parent;
468 typedef typename Parent::Key Key;
469 typedef typename Parent::Value Value;
472 SimpleWriteMap(M &_m) : m(_m) {};
474 Value operator[](Key k) const {return m[k];}
476 void set(Key k, const Value& c) { m.set(k, c); }
479 ///Returns a \c SimpleWriteMap class
481 ///This function just returns a \c SimpleWriteMap class.
482 ///\relates SimpleWriteMap
484 inline SimpleWriteMap<M> simpleWriteMap(M &m) {
485 return SimpleWriteMap<M>(m);
490 ///This \ref concepts::ReadMap "read only map" returns the sum of the two
492 ///Its \c Key and \c Value are inherited from \c M1.
493 ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
494 template<typename M1, typename M2>
495 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
500 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
501 typedef typename Parent::Key Key;
502 typedef typename Parent::Value Value;
505 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
507 Value operator[](Key k) const {return m1[k]+m2[k];}
510 ///Returns an \c AddMap class
512 ///This function just returns an \c AddMap class.
513 ///\todo How to call these type of functions?
516 template<typename M1, typename M2>
517 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
518 return AddMap<M1, M2>(m1,m2);
521 ///Shift a map with a constant.
523 ///This \ref concepts::ReadMap "read only map" returns the sum of the
524 ///given map and a constant value.
525 ///Its \c Key and \c Value are inherited from \c M.
529 /// ShiftMap<X> sh(x,v);
533 /// ConstMap<X::Key, X::Value> c_tmp(v);
534 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
538 template<typename M, typename C = typename M::Value>
539 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
543 typedef MapBase<typename M::Key, typename M::Value> Parent;
544 typedef typename Parent::Key Key;
545 typedef typename Parent::Value Value;
550 ///\param _m is the undelying map.
551 ///\param _v is the shift value.
552 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
554 Value operator[](Key k) const {return m[k] + v;}
557 ///Shift a map with a constant (ReadWrite version).
559 ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
560 ///given map and a constant value. It makes also possible to write the map.
561 ///Its \c Key and \c Value are inherited from \c M.
564 template<typename M, typename C = typename M::Value>
565 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
569 typedef MapBase<typename M::Key, typename M::Value> Parent;
570 typedef typename Parent::Key Key;
571 typedef typename Parent::Value Value;
576 ///\param _m is the undelying map.
577 ///\param _v is the shift value.
578 ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
580 Value operator[](Key k) const {return m[k] + v;}
582 void set(Key k, const Value& c) { m.set(k, c - v); }
585 ///Returns a \c ShiftMap class
587 ///This function just returns a \c ShiftMap class.
589 template<typename M, typename C>
590 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
591 return ShiftMap<M, C>(m,v);
594 ///Returns a \c ShiftWriteMap class
596 ///This function just returns a \c ShiftWriteMap class.
597 ///\relates ShiftWriteMap
598 template<typename M, typename C>
599 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
600 return ShiftWriteMap<M, C>(m,v);
603 ///Difference of two maps
605 ///This \ref concepts::ReadMap "read only map" returns the difference
606 ///of the values of the two given maps.
607 ///Its \c Key and \c Value are inherited from \c M1.
608 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
610 /// \todo Revise the misleading name
611 template<typename M1, typename M2>
612 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
616 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
617 typedef typename Parent::Key Key;
618 typedef typename Parent::Value Value;
621 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
623 Value operator[](Key k) const {return m1[k]-m2[k];}
626 ///Returns a \c SubMap class
628 ///This function just returns a \c SubMap class.
631 template<typename M1, typename M2>
632 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
633 return SubMap<M1, M2>(m1, m2);
636 ///Product of two maps
638 ///This \ref concepts::ReadMap "read only map" returns the product of the
639 ///values of the two given maps.
640 ///Its \c Key and \c Value are inherited from \c M1.
641 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
642 template<typename M1, typename M2>
643 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
647 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
648 typedef typename Parent::Key Key;
649 typedef typename Parent::Value Value;
652 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
654 Value operator[](Key k) const {return m1[k]*m2[k];}
657 ///Returns a \c MulMap class
659 ///This function just returns a \c MulMap class.
661 template<typename M1, typename M2>
662 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
663 return MulMap<M1, M2>(m1,m2);
666 ///Scales a map with a constant.
668 ///This \ref concepts::ReadMap "read only map" returns the value of the
669 ///given map multiplied from the left side with a constant value.
670 ///Its \c Key and \c Value are inherited from \c M.
674 /// ScaleMap<X> sc(x,v);
678 /// ConstMap<X::Key, X::Value> c_tmp(v);
679 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
683 template<typename M, typename C = typename M::Value>
684 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
688 typedef MapBase<typename M::Key, typename M::Value> Parent;
689 typedef typename Parent::Key Key;
690 typedef typename Parent::Value Value;
695 ///\param _m is the undelying map.
696 ///\param _v is the scaling value.
697 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
699 Value operator[](Key k) const {return v * m[k];}
702 ///Scales a map with a constant (ReadWrite version).
704 ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
705 ///given map multiplied from the left side with a constant value. It can
706 ///also be used as write map if the \c / operator is defined between
707 ///\c Value and \c C and the given multiplier is not zero.
708 ///Its \c Key and \c Value are inherited from \c M.
711 template<typename M, typename C = typename M::Value>
712 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
716 typedef MapBase<typename M::Key, typename M::Value> Parent;
717 typedef typename Parent::Key Key;
718 typedef typename Parent::Value Value;
723 ///\param _m is the undelying map.
724 ///\param _v is the scaling value.
725 ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
727 Value operator[](Key k) const {return v * m[k];}
729 void set(Key k, const Value& c) { m.set(k, c / v);}
732 ///Returns a \c ScaleMap class
734 ///This function just returns a \c ScaleMap class.
736 template<typename M, typename C>
737 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
738 return ScaleMap<M, C>(m,v);
741 ///Returns a \c ScaleWriteMap class
743 ///This function just returns a \c ScaleWriteMap class.
744 ///\relates ScaleWriteMap
745 template<typename M, typename C>
746 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
747 return ScaleWriteMap<M, C>(m,v);
750 ///Quotient of two maps
752 ///This \ref concepts::ReadMap "read only map" returns the quotient of the
753 ///values of the two given maps.
754 ///Its \c Key and \c Value are inherited from \c M1.
755 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
756 template<typename M1, typename M2>
757 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
761 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
762 typedef typename Parent::Key Key;
763 typedef typename Parent::Value Value;
766 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
768 Value operator[](Key k) const {return m1[k]/m2[k];}
771 ///Returns a \c DivMap class
773 ///This function just returns a \c DivMap class.
775 template<typename M1, typename M2>
776 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
777 return DivMap<M1, M2>(m1,m2);
780 ///Composition of two maps
782 ///This \ref concepts::ReadMap "read only map" returns the composition of
784 ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
787 /// ComposeMap<M1, M2> cm(m1,m2);
789 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
791 ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
792 ///\c M2::Value must be convertible to \c M1::Key.
796 ///\todo Check the requirements.
797 template <typename M1, typename M2>
798 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
802 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
803 typedef typename Parent::Key Key;
804 typedef typename Parent::Value Value;
807 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
812 /// \todo Use the MapTraits once it is ported.
815 //typename MapTraits<M1>::ConstReturnValue
817 operator[](Key k) const {return m1[m2[k]];}
820 ///Returns a \c ComposeMap class
822 ///This function just returns a \c ComposeMap class.
823 ///\relates ComposeMap
824 template <typename M1, typename M2>
825 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
826 return ComposeMap<M1, M2>(m1,m2);
829 ///Combine of two maps using an STL (binary) functor.
831 ///Combine of two maps using an STL (binary) functor.
833 ///This \ref concepts::ReadMap "read only map" takes two maps and a
834 ///binary functor and returns the composition of the two
835 ///given maps unsing the functor.
836 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
837 ///and \c f is of \c F, then for
839 /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
841 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
843 ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
844 ///\c M2::Value and \c M1::Value must be convertible to the corresponding
845 ///input parameter of \c F and the return type of \c F must be convertible
850 ///\todo Check the requirements.
851 template<typename M1, typename M2, typename F,
852 typename V = typename F::result_type>
853 class CombineMap : public MapBase<typename M1::Key, V> {
858 typedef MapBase<typename M1::Key, V> Parent;
859 typedef typename Parent::Key Key;
860 typedef typename Parent::Value Value;
863 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
864 : m1(_m1), m2(_m2), f(_f) {};
866 Value operator[](Key k) const {return f(m1[k],m2[k]);}
869 ///Returns a \c CombineMap class
871 ///This function just returns a \c CombineMap class.
873 ///For example if \c m1 and \c m2 are both \c double valued maps, then
875 ///combineMap(m1,m2,std::plus<double>())
882 ///This function is specialized for adaptable binary function
883 ///classes and C++ functions.
885 ///\relates CombineMap
886 template<typename M1, typename M2, typename F, typename V>
887 inline CombineMap<M1, M2, F, V>
888 combineMap(const M1& m1,const M2& m2, const F& f) {
889 return CombineMap<M1, M2, F, V>(m1,m2,f);
892 template<typename M1, typename M2, typename F>
893 inline CombineMap<M1, M2, F, typename F::result_type>
894 combineMap(const M1& m1, const M2& m2, const F& f) {
895 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
898 template<typename M1, typename M2, typename K1, typename K2, typename V>
899 inline CombineMap<M1, M2, V (*)(K1, K2), V>
900 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
901 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
904 ///Negative value of a map
906 ///This \ref concepts::ReadMap "read only map" returns the negative
907 ///value of the value returned by the given map.
908 ///Its \c Key and \c Value are inherited from \c M.
909 ///The unary \c - operator must be defined for \c Value, of course.
913 class NegMap : public MapBase<typename M::Key, typename M::Value> {
916 typedef MapBase<typename M::Key, typename M::Value> Parent;
917 typedef typename Parent::Key Key;
918 typedef typename Parent::Value Value;
921 NegMap(const M &_m) : m(_m) {};
923 Value operator[](Key k) const {return -m[k];}
926 ///Negative value of a map (ReadWrite version)
928 ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
929 ///value of the value returned by the given map.
930 ///Its \c Key and \c Value are inherited from \c M.
931 ///The unary \c - operator must be defined for \c Value, of course.
935 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
938 typedef MapBase<typename M::Key, typename M::Value> Parent;
939 typedef typename Parent::Key Key;
940 typedef typename Parent::Value Value;
943 NegWriteMap(M &_m) : m(_m) {};
945 Value operator[](Key k) const {return -m[k];}
947 void set(Key k, const Value& v) { m.set(k, -v); }
950 ///Returns a \c NegMap class
952 ///This function just returns a \c NegMap class.
954 template <typename M>
955 inline NegMap<M> negMap(const M &m) {
959 ///Returns a \c NegWriteMap class
961 ///This function just returns a \c NegWriteMap class.
962 ///\relates NegWriteMap
963 template <typename M>
964 inline NegWriteMap<M> negMap(M &m) {
965 return NegWriteMap<M>(m);
968 ///Absolute value of a map
970 ///This \ref concepts::ReadMap "read only map" returns the absolute value
971 ///of the value returned by the given map.
972 ///Its \c Key and \c Value are inherited from \c M.
973 ///\c Value must be comparable to \c 0 and the unary \c -
974 ///operator must be defined for it, of course.
976 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
979 typedef MapBase<typename M::Key, typename M::Value> Parent;
980 typedef typename Parent::Key Key;
981 typedef typename Parent::Value Value;
984 AbsMap(const M &_m) : m(_m) {};
986 Value operator[](Key k) const {
988 return tmp >= 0 ? tmp : -tmp;
993 ///Returns an \c AbsMap class
995 ///This function just returns an \c AbsMap class.
998 inline AbsMap<M> absMap(const M &m) {
1002 ///Converts an STL style functor to a map
1004 ///This \ref concepts::ReadMap "read only map" returns the value
1005 ///of a given functor.
1007 ///Template parameters \c K and \c V will become its
1008 ///\c Key and \c Value.
1009 ///In most cases they have to be given explicitly because a
1010 ///functor typically does not provide such typedefs.
1012 ///Parameter \c F is the type of the used functor.
1015 template<typename F,
1016 typename K = typename F::argument_type,
1017 typename V = typename F::result_type>
1018 class FunctorMap : public MapBase<K, V> {
1021 typedef MapBase<K, V> Parent;
1022 typedef typename Parent::Key Key;
1023 typedef typename Parent::Value Value;
1026 FunctorMap(const F &_f = F()) : f(_f) {}
1028 Value operator[](Key k) const { return f(k);}
1031 ///Returns a \c FunctorMap class
1033 ///This function just returns a \c FunctorMap class.
1035 ///It is specialized for adaptable function classes and
1037 ///\relates FunctorMap
1038 template<typename K, typename V, typename F> inline
1039 FunctorMap<F, K, V> functorMap(const F &f) {
1040 return FunctorMap<F, K, V>(f);
1043 template <typename F> inline
1044 FunctorMap<F, typename F::argument_type, typename F::result_type>
1045 functorMap(const F &f) {
1046 return FunctorMap<F, typename F::argument_type,
1047 typename F::result_type>(f);
1050 template <typename K, typename V> inline
1051 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
1052 return FunctorMap<V (*)(K), K, V>(f);
1056 ///Converts a map to an STL style (unary) functor
1058 ///This class Converts a map to an STL style (unary) functor.
1059 ///that is it provides an <tt>operator()</tt> to read its values.
1061 ///For the sake of convenience it also works as
1062 ///a ususal \ref concepts::ReadMap "readable map",
1063 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1066 template <typename M>
1067 class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1070 typedef MapBase<typename M::Key, typename M::Value> Parent;
1071 typedef typename Parent::Key Key;
1072 typedef typename Parent::Value Value;
1074 typedef typename M::Key argument_type;
1075 typedef typename M::Value result_type;
1078 MapFunctor(const M &_m) : m(_m) {};
1080 Value operator()(Key k) const {return m[k];}
1082 Value operator[](Key k) const {return m[k];}
1085 ///Returns a \c MapFunctor class
1087 ///This function just returns a \c MapFunctor class.
1088 ///\relates MapFunctor
1089 template<typename M>
1090 inline MapFunctor<M> mapFunctor(const M &m) {
1091 return MapFunctor<M>(m);
1094 ///Applies all map setting operations to two maps
1096 ///This map has two \ref concepts::ReadMap "readable map"
1097 ///parameters and each read request will be passed just to the
1098 ///first map. This class is the just readable map type of the \c ForkWriteMap.
1100 ///The \c Key and \c Value are inherited from \c M1.
1101 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1105 /// \todo Why is it needed?
1106 template<typename M1, typename M2>
1107 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1111 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1112 typedef typename Parent::Key Key;
1113 typedef typename Parent::Value Value;
1116 ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1118 Value operator[](Key k) const {return m1[k];}
1122 ///Applies all map setting operations to two maps
1124 ///This map has two \ref concepts::WriteMap "writable map"
1125 ///parameters and each write request will be passed to both of them.
1126 ///If \c M1 is also \ref concepts::ReadMap "readable",
1127 ///then the read operations will return the
1128 ///corresponding values of \c M1.
1130 ///The \c Key and \c Value are inherited from \c M1.
1131 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1134 template<typename M1, typename M2>
1135 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1139 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1140 typedef typename Parent::Key Key;
1141 typedef typename Parent::Value Value;
1144 ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1146 Value operator[](Key k) const {return m1[k];}
1148 void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1151 ///Returns a \c ForkMap class
1153 ///This function just returns a \c ForkMap class.
1155 template <typename M1, typename M2>
1156 inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1157 return ForkMap<M1, M2>(m1,m2);
1160 ///Returns a \c ForkWriteMap class
1162 ///This function just returns a \c ForkWriteMap class.
1163 ///\relates ForkWriteMap
1164 template <typename M1, typename M2>
1165 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1166 return ForkWriteMap<M1, M2>(m1,m2);
1171 /* ************* BOOL MAPS ******************* */
1173 ///Logical 'not' of a map
1175 ///This bool \ref concepts::ReadMap "read only map" returns the
1176 ///logical negation of the value returned by the given map.
1177 ///Its \c Key is inherited from \c M, its Value is \c bool.
1180 template <typename M>
1181 class NotMap : public MapBase<typename M::Key, bool> {
1184 typedef MapBase<typename M::Key, bool> Parent;
1185 typedef typename Parent::Key Key;
1186 typedef typename Parent::Value Value;
1189 NotMap(const M &_m) : m(_m) {};
1191 Value operator[](Key k) const {return !m[k];}
1194 ///Logical 'not' of a map (ReadWrie version)
1196 ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
1197 ///logical negation of the value returned by the given map. When it is set,
1198 ///the opposite value is set to the original map.
1199 ///Its \c Key is inherited from \c M, its Value is \c bool.
1202 template <typename M>
1203 class NotWriteMap : public MapBase<typename M::Key, bool> {
1206 typedef MapBase<typename M::Key, bool> Parent;
1207 typedef typename Parent::Key Key;
1208 typedef typename Parent::Value Value;
1211 NotWriteMap(M &_m) : m(_m) {};
1213 Value operator[](Key k) const {return !m[k];}
1215 void set(Key k, bool v) { m.set(k, !v); }
1218 ///Returns a \c NotMap class
1220 ///This function just returns a \c NotMap class.
1222 template <typename M>
1223 inline NotMap<M> notMap(const M &m) {
1224 return NotMap<M>(m);
1227 ///Returns a \c NotWriteMap class
1229 ///This function just returns a \c NotWriteMap class.
1230 ///\relates NotWriteMap
1231 template <typename M>
1232 inline NotWriteMap<M> notMap(M &m) {
1233 return NotWriteMap<M>(m);
1236 namespace _maps_bits {
1238 template <typename Value>
1240 typedef Value argument_type;
1241 typedef Value result_type;
1242 Value operator()(const Value& val) const {
1247 template <typename _Iterator, typename Enable = void>
1248 struct IteratorTraits {
1249 typedef typename std::iterator_traits<_Iterator>::value_type Value;
1252 template <typename _Iterator>
1253 struct IteratorTraits<_Iterator,
1254 typename exists<typename _Iterator::container_type>::type>
1256 typedef typename _Iterator::container_type::value_type Value;
1262 /// \brief Writable bool map for logging each \c true assigned element
1264 /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
1265 /// each \c true assigned element, i.e it/ copies all the keys set
1266 /// to \c true to the given iterator.
1268 /// \note The container of the iterator should contain space
1269 /// for each element.
1271 /// The following example shows how you can write the edges found by the Prim
1272 /// algorithm directly
1273 /// to the standard output.
1275 /// typedef IdMap<Graph, Edge> EdgeIdMap;
1276 /// EdgeIdMap edgeId(graph);
1278 /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
1279 /// EdgeIdFunctor edgeIdFunctor(edgeId);
1281 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
1282 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1284 /// prim(graph, cost, writerMap);
1287 ///\sa BackInserterBoolMap
1288 ///\sa FrontInserterBoolMap
1289 ///\sa InserterBoolMap
1291 ///\todo Revise the name of this class and the related ones.
1292 template <typename _Iterator,
1294 _maps_bits::Identity<typename _maps_bits::
1295 IteratorTraits<_Iterator>::Value> >
1296 class StoreBoolMap {
1298 typedef _Iterator Iterator;
1300 typedef typename _Functor::argument_type Key;
1303 typedef _Functor Functor;
1306 StoreBoolMap(Iterator it, const Functor& functor = Functor())
1307 : _begin(it), _end(it), _functor(functor) {}
1309 /// Gives back the given iterator set for the first key
1310 Iterator begin() const {
1314 /// Gives back the the 'after the last' iterator
1315 Iterator end() const {
1319 /// The \c set function of the map
1320 void set(const Key& key, Value value) const {
1322 *_end++ = _functor(key);
1328 mutable Iterator _end;
1332 /// \brief Writable bool map for logging each \c true assigned element in
1333 /// a back insertable container.
1335 /// Writable bool map for logging each \c true assigned element by pushing
1336 /// them into a back insertable container.
1337 /// It can be used to retrieve the items into a standard
1338 /// container. The next example shows how you can store the
1339 /// edges found by the Prim algorithm in a vector.
1342 /// vector<Edge> span_tree_edges;
1343 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1344 /// prim(graph, cost, inserter_map);
1348 ///\sa FrontInserterBoolMap
1349 ///\sa InserterBoolMap
1350 template <typename Container,
1352 _maps_bits::Identity<typename Container::value_type> >
1353 class BackInserterBoolMap {
1355 typedef typename Functor::argument_type Key;
1359 BackInserterBoolMap(Container& _container,
1360 const Functor& _functor = Functor())
1361 : container(_container), functor(_functor) {}
1363 /// The \c set function of the map
1364 void set(const Key& key, Value value) {
1366 container.push_back(functor(key));
1371 Container& container;
1375 /// \brief Writable bool map for logging each \c true assigned element in
1376 /// a front insertable container.
1378 /// Writable bool map for logging each \c true assigned element by pushing
1379 /// them into a front insertable container.
1380 /// It can be used to retrieve the items into a standard
1381 /// container. For example see \ref BackInserterBoolMap.
1383 ///\sa BackInserterBoolMap
1384 ///\sa InserterBoolMap
1385 template <typename Container,
1387 _maps_bits::Identity<typename Container::value_type> >
1388 class FrontInserterBoolMap {
1390 typedef typename Functor::argument_type Key;
1394 FrontInserterBoolMap(Container& _container,
1395 const Functor& _functor = Functor())
1396 : container(_container), functor(_functor) {}
1398 /// The \c set function of the map
1399 void set(const Key& key, Value value) {
1401 container.push_front(functor(key));
1406 Container& container;
1410 /// \brief Writable bool map for storing each \c true assigned element in
1411 /// an insertable container.
1413 /// Writable bool map for storing each \c true assigned element in an
1414 /// insertable container. It will insert all the keys set to \c true into
1417 /// For example, if you want to store the cut arcs of the strongly
1418 /// connected components in a set you can use the next code:
1421 /// set<Arc> cut_arcs;
1422 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1423 /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1426 ///\sa BackInserterBoolMap
1427 ///\sa FrontInserterBoolMap
1428 template <typename Container,
1430 _maps_bits::Identity<typename Container::value_type> >
1431 class InserterBoolMap {
1433 typedef typename Container::value_type Key;
1436 /// Constructor with specified iterator
1438 /// Constructor with specified iterator.
1439 /// \param _container The container for storing the elements.
1440 /// \param _it The elements will be inserted before this iterator.
1441 /// \param _functor The functor that is used when an element is stored.
1442 InserterBoolMap(Container& _container, typename Container::iterator _it,
1443 const Functor& _functor = Functor())
1444 : container(_container), it(_it), functor(_functor) {}
1448 /// Constructor without specified iterator.
1449 /// The elements will be inserted before <tt>_container.end()</tt>.
1450 /// \param _container The container for storing the elements.
1451 /// \param _functor The functor that is used when an element is stored.
1452 InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1453 : container(_container), it(_container.end()), functor(_functor) {}
1455 /// The \c set function of the map
1456 void set(const Key& key, Value value) {
1458 it = container.insert(it, functor(key));
1464 Container& container;
1465 typename Container::iterator it;
1469 /// \brief Writable bool map for filling each \c true assigned element with a
1472 /// Writable bool map for filling each \c true assigned element with a
1473 /// given value. The value can set the container.
1475 /// The following code finds the connected components of a graph
1476 /// and stores it in the \c comp map:
1478 /// typedef Graph::NodeMap<int> ComponentMap;
1479 /// ComponentMap comp(graph);
1480 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1481 /// ComponentFillerMap filler(comp, 0);
1483 /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1484 /// dfs.processedMap(filler);
1486 /// for (NodeIt it(graph); it != INVALID; ++it) {
1487 /// if (!dfs.reached(it)) {
1488 /// dfs.addSource(it);
1490 /// ++filler.fillValue();
1494 template <typename Map>
1497 typedef typename Map::Key Key;
1501 FillBoolMap(Map& _map, const typename Map::Value& _fill)
1502 : map(_map), fill(_fill) {}
1505 FillBoolMap(Map& _map)
1506 : map(_map), fill() {}
1508 /// Gives back the current fill value
1509 const typename Map::Value& fillValue() const {
1513 /// Gives back the current fill value
1514 typename Map::Value& fillValue() {
1518 /// Sets the current fill value
1519 void fillValue(const typename Map::Value& _fill) {
1523 /// The \c set function of the map
1524 void set(const Key& key, Value value) {
1532 typename Map::Value fill;
1536 /// \brief Writable bool map for storing the sequence number of
1537 /// \c true assignments.
1539 /// Writable bool map that stores for each \c true assigned elements
1540 /// the sequence number of this setting.
1541 /// It makes it easy to calculate the leaving
1542 /// order of the nodes in the \c Dfs algorithm.
1545 /// typedef Digraph::NodeMap<int> OrderMap;
1546 /// OrderMap order(digraph);
1547 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1548 /// OrderSetterMap setter(order);
1549 /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1550 /// dfs.processedMap(setter);
1552 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1553 /// if (!dfs.reached(it)) {
1554 /// dfs.addSource(it);
1560 /// The storing of the discovering order is more difficult because the
1561 /// ReachedMap should be readable in the dfs algorithm but the setting
1562 /// order map is not readable. Thus we must use the fork map:
1565 /// typedef Digraph::NodeMap<int> OrderMap;
1566 /// OrderMap order(digraph);
1567 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1568 /// OrderSetterMap setter(order);
1569 /// typedef Digraph::NodeMap<bool> StoreMap;
1570 /// StoreMap store(digraph);
1572 /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1573 /// ReachedMap reached(store, setter);
1575 /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1576 /// dfs.reachedMap(reached);
1578 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1579 /// if (!dfs.reached(it)) {
1580 /// dfs.addSource(it);
1585 template <typename Map>
1586 class SettingOrderBoolMap {
1588 typedef typename Map::Key Key;
1592 SettingOrderBoolMap(Map& _map)
1593 : map(_map), counter(0) {}
1595 /// Number of set operations.
1600 /// The \c set function of the map
1601 void set(const Key& key, Value value) {
1603 map.set(key, counter++);
1615 #endif // LEMON_MAPS_H