Doc improvements is some files.
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 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 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> >
167 template <typename K1, typename T1, typename C1>
171 typedef True ReferenceMapTag;
177 typedef T& Reference;
178 ///Const reference type
179 typedef const T& ConstReference;
183 typedef std::map<K, T, Compare> Map;
189 /// Constructor with specified default value
190 StdMap(const T& value = T()) : _value(value) {}
191 /// \brief Constructs the map from an appropriate std::map, and explicitly
192 /// specifies a default value.
193 template <typename T1, typename Comp1>
194 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
195 : _map(map.begin(), map.end()), _value(value) {}
197 /// \brief Constructs a map from an other StdMap.
198 template<typename T1, typename Comp1>
199 StdMap(const StdMap<Key, T1, Comp1> &c)
200 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
204 StdMap& operator=(const StdMap&);
209 Reference operator[](const Key &k) {
210 typename Map::iterator it = _map.lower_bound(k);
211 if (it != _map.end() && !_map.key_comp()(k, it->first))
214 return _map.insert(it, std::make_pair(k, _value))->second;
218 ConstReference operator[](const Key &k) const {
219 typename Map::const_iterator it = _map.find(k);
220 if (it != _map.end())
227 void set(const Key &k, const T &t) {
228 typename Map::iterator it = _map.lower_bound(k);
229 if (it != _map.end() && !_map.key_comp()(k, it->first))
232 _map.insert(it, std::make_pair(k, t));
236 void setAll(const T &t) {
243 /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
245 /// The current map has the <tt>[0..size-1]</tt> keyset and the values
246 /// are stored in a \c std::vector<T> container. It can be used with
247 /// some data structures, for example \c UnionFind, \c BinHeap, when
248 /// the used items are small integer numbers.
250 /// \todo Revise its name
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 map.
324 /// This map 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 ///\brief Convert the \c Value of a map to another type using
350 ///the default conversion.
352 ///This \c concepts::ReadMap "read only map"
353 ///converts the \c Value of a map to type \c T.
354 ///Its \c Key is inherited from \c M.
355 template <typename M, typename T>
356 class ConvertMap : public MapBase<typename M::Key, T> {
359 typedef MapBase<typename M::Key, T> Parent;
360 typedef typename Parent::Key Key;
361 typedef typename Parent::Value Value;
366 ///\param _m is the underlying map.
367 ConvertMap(const M &_m) : m(_m) {};
369 /// \brief The subscript operator.
371 /// The subscript operator.
372 Value operator[](const Key& k) const {return m[k];}
375 ///Returns a \c ConvertMap class
377 ///This function just returns a \c ConvertMap class.
378 ///\relates ConvertMap
379 template<typename T, typename M>
380 inline ConvertMap<M, T> convertMap(const M &m) {
381 return ConvertMap<M, T>(m);
384 ///Simple wrapping of a map
386 ///This \ref concepts::ReadMap "read only map" returns the simple
387 ///wrapping of the given map. Sometimes the reference maps cannot be
388 ///combined with simple read maps. This map adaptor wraps the given
389 ///map to simple read map.
391 ///\sa SimpleWriteMap
393 /// \todo Revise the misleading name
395 class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
399 typedef MapBase<typename M::Key, typename M::Value> Parent;
400 typedef typename Parent::Key Key;
401 typedef typename Parent::Value Value;
404 SimpleMap(const M &_m) : m(_m) {};
406 Value operator[](Key k) const {return m[k];}
409 ///Simple writable wrapping of a map
411 ///This \ref concepts::WriteMap "write map" returns the simple
412 ///wrapping of the given map. Sometimes the reference maps cannot be
413 ///combined with simple read-write maps. This map adaptor wraps the
414 ///given map to simple read-write map.
418 /// \todo Revise the misleading name
420 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
424 typedef MapBase<typename M::Key, typename M::Value> Parent;
425 typedef typename Parent::Key Key;
426 typedef typename Parent::Value Value;
429 SimpleWriteMap(M &_m) : m(_m) {};
431 Value operator[](Key k) const {return m[k];}
433 void set(Key k, const Value& c) { m.set(k, c); }
438 ///This \c concepts::ReadMap "read only map" returns the sum of the two
440 ///Its \c Key and \c Value are inherited from \c M1.
441 ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
442 template<typename M1, typename M2>
443 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
448 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
449 typedef typename Parent::Key Key;
450 typedef typename Parent::Value Value;
453 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
455 Value operator[](Key k) const {return m1[k]+m2[k];}
458 ///Returns an \c AddMap class
460 ///This function just returns an \c AddMap class.
461 ///\todo How to call these type of functions?
464 template<typename M1, typename M2>
465 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
466 return AddMap<M1, M2>(m1,m2);
469 ///Shift a map with a constant.
471 ///This \c concepts::ReadMap "read only map" returns the sum of the
472 ///given map and a constant value.
473 ///Its \c Key and \c Value are inherited from \c M.
477 /// ShiftMap<X> sh(x,v);
481 /// ConstMap<X::Key, X::Value> c_tmp(v);
482 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
486 template<typename M, typename C = typename M::Value>
487 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
491 typedef MapBase<typename M::Key, typename M::Value> Parent;
492 typedef typename Parent::Key Key;
493 typedef typename Parent::Value Value;
498 ///\param _m is the undelying map.
499 ///\param _v is the shift value.
500 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
502 Value operator[](Key k) const {return m[k] + v;}
505 ///Shift a map with a constant (ReadWrite version).
507 ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
508 ///given map and a constant value. It makes also possible to write the map.
509 ///Its \c Key and \c Value are inherited from \c M.
512 template<typename M, typename C = typename M::Value>
513 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
517 typedef MapBase<typename M::Key, typename M::Value> Parent;
518 typedef typename Parent::Key Key;
519 typedef typename Parent::Value Value;
524 ///\param _m is the undelying map.
525 ///\param _v is the shift value.
526 ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
528 Value operator[](Key k) const {return m[k] + v;}
530 void set(Key k, const Value& c) { m.set(k, c - v); }
533 ///Returns a \c ShiftMap class
535 ///This function just returns a \c ShiftMap class.
537 template<typename M, typename C>
538 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
539 return ShiftMap<M, C>(m,v);
542 ///Returns a \c ShiftWriteMap class
544 ///This function just returns a \c ShiftWriteMap class.
545 ///\relates ShiftWriteMap
546 template<typename M, typename C>
547 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
548 return ShiftWriteMap<M, C>(m,v);
551 ///Difference of two maps
553 ///This \c concepts::ReadMap "read only map" returns the difference
554 ///of the values of the two given maps.
555 ///Its \c Key and \c Value are inherited from \c M1.
556 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
558 /// \todo Revise the misleading name
559 template<typename M1, typename M2>
560 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
564 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
565 typedef typename Parent::Key Key;
566 typedef typename Parent::Value Value;
569 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
571 Value operator[](Key k) const {return m1[k]-m2[k];}
574 ///Returns a \c SubMap class
576 ///This function just returns a \c SubMap class.
579 template<typename M1, typename M2>
580 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
581 return SubMap<M1, M2>(m1, m2);
584 ///Product of two maps
586 ///This \c concepts::ReadMap "read only map" returns the product of the
587 ///values of the two given maps.
588 ///Its \c Key and \c Value are inherited from \c M1.
589 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
590 template<typename M1, typename M2>
591 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
595 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
596 typedef typename Parent::Key Key;
597 typedef typename Parent::Value Value;
600 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
602 Value operator[](Key k) const {return m1[k]*m2[k];}
605 ///Returns a \c MulMap class
607 ///This function just returns a \c MulMap class.
609 template<typename M1, typename M2>
610 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
611 return MulMap<M1, M2>(m1,m2);
614 ///Scales a map with a constant.
616 ///This \c concepts::ReadMap "read only map" returns the value of the
617 ///given map multiplied from the left side with a constant value.
618 ///Its \c Key and \c Value are inherited from \c M.
622 /// ScaleMap<X> sc(x,v);
626 /// ConstMap<X::Key, X::Value> c_tmp(v);
627 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
631 template<typename M, typename C = typename M::Value>
632 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
636 typedef MapBase<typename M::Key, typename M::Value> Parent;
637 typedef typename Parent::Key Key;
638 typedef typename Parent::Value Value;
643 ///\param _m is the undelying map.
644 ///\param _v is the scaling value.
645 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
647 Value operator[](Key k) const {return v * m[k];}
650 ///Scales a map with a constant (ReadWrite version).
652 ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
653 ///given map multiplied from the left side with a constant value. It can
654 ///also be used as write map if the \c / operator is defined between
655 ///\c Value and \c C and the given multiplier is not zero.
656 ///Its \c Key and \c Value are inherited from \c M.
659 template<typename M, typename C = typename M::Value>
660 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
664 typedef MapBase<typename M::Key, typename M::Value> Parent;
665 typedef typename Parent::Key Key;
666 typedef typename Parent::Value Value;
671 ///\param _m is the undelying map.
672 ///\param _v is the scaling value.
673 ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
675 Value operator[](Key k) const {return v * m[k];}
677 void set(Key k, const Value& c) { m.set(k, c / v);}
680 ///Returns a \c ScaleMap class
682 ///This function just returns a \c ScaleMap class.
684 template<typename M, typename C>
685 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
686 return ScaleMap<M, C>(m,v);
689 ///Returns a \c ScaleWriteMap class
691 ///This function just returns a \c ScaleWriteMap class.
692 ///\relates ScaleWriteMap
693 template<typename M, typename C>
694 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
695 return ScaleWriteMap<M, C>(m,v);
698 ///Quotient of two maps
700 ///This \c concepts::ReadMap "read only map" returns the quotient of the
701 ///values of the two given maps.
702 ///Its \c Key and \c Value are inherited from \c M1.
703 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
704 template<typename M1, typename M2>
705 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
709 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
710 typedef typename Parent::Key Key;
711 typedef typename Parent::Value Value;
714 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
716 Value operator[](Key k) const {return m1[k]/m2[k];}
719 ///Returns a \c DivMap class
721 ///This function just returns a \c DivMap class.
723 template<typename M1, typename M2>
724 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
725 return DivMap<M1, M2>(m1,m2);
728 ///Composition of two maps
730 ///This \c concepts::ReadMap "read only map" returns the composition of
732 ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
735 /// ComposeMap<M1, M2> cm(m1,m2);
737 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
739 ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
740 ///\c M2::Value must be convertible to \c M1::Key.
744 ///\todo Check the requirements.
745 template <typename M1, typename M2>
746 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
750 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
751 typedef typename Parent::Key Key;
752 typedef typename Parent::Value Value;
755 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
760 /// \todo Use the MapTraits once it is ported.
763 //typename MapTraits<M1>::ConstReturnValue
765 operator[](Key k) const {return m1[m2[k]];}
768 ///Returns a \c ComposeMap class
770 ///This function just returns a \c ComposeMap class.
771 ///\relates ComposeMap
772 template <typename M1, typename M2>
773 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
774 return ComposeMap<M1, M2>(m1,m2);
777 ///Combine of two maps using an STL (binary) functor.
779 ///Combine of two maps using an STL (binary) functor.
781 ///This \c concepts::ReadMap "read only map" takes two maps and a
782 ///binary functor and returns the composition of the two
783 ///given maps unsing the functor.
784 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
785 ///and \c f is of \c F, then for
787 /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
789 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
791 ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
792 ///\c M2::Value and \c M1::Value must be convertible to the corresponding
793 ///input parameter of \c F and the return type of \c F must be convertible
798 ///\todo Check the requirements.
799 template<typename M1, typename M2, typename F,
800 typename V = typename F::result_type>
801 class CombineMap : public MapBase<typename M1::Key, V> {
806 typedef MapBase<typename M1::Key, V> Parent;
807 typedef typename Parent::Key Key;
808 typedef typename Parent::Value Value;
811 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
812 : m1(_m1), m2(_m2), f(_f) {};
814 Value operator[](Key k) const {return f(m1[k],m2[k]);}
817 ///Returns a \c CombineMap class
819 ///This function just returns a \c CombineMap class.
821 ///For example if \c m1 and \c m2 are both \c double valued maps, then
823 ///combineMap(m1,m2,std::plus<double>())
830 ///This function is specialized for adaptable binary function
831 ///classes and C++ functions.
833 ///\relates CombineMap
834 template<typename M1, typename M2, typename F, typename V>
835 inline CombineMap<M1, M2, F, V>
836 combineMap(const M1& m1,const M2& m2, const F& f) {
837 return CombineMap<M1, M2, F, V>(m1,m2,f);
840 template<typename M1, typename M2, typename F>
841 inline CombineMap<M1, M2, F, typename F::result_type>
842 combineMap(const M1& m1, const M2& m2, const F& f) {
843 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
846 template<typename M1, typename M2, typename K1, typename K2, typename V>
847 inline CombineMap<M1, M2, V (*)(K1, K2), V>
848 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
849 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
852 ///Negative value of a map
854 ///This \c concepts::ReadMap "read only map" returns the negative
855 ///value of the value returned by the given map.
856 ///Its \c Key and \c Value are inherited from \c M.
857 ///The unary \c - operator must be defined for \c Value, of course.
861 class NegMap : public MapBase<typename M::Key, typename M::Value> {
864 typedef MapBase<typename M::Key, typename M::Value> Parent;
865 typedef typename Parent::Key Key;
866 typedef typename Parent::Value Value;
869 NegMap(const M &_m) : m(_m) {};
871 Value operator[](Key k) const {return -m[k];}
874 ///Negative value of a map (ReadWrite version)
876 ///This \c concepts::ReadWriteMap "read-write map" returns the negative
877 ///value of the value returned by the given map.
878 ///Its \c Key and \c Value are inherited from \c M.
879 ///The unary \c - operator must be defined for \c Value, of course.
883 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
886 typedef MapBase<typename M::Key, typename M::Value> Parent;
887 typedef typename Parent::Key Key;
888 typedef typename Parent::Value Value;
891 NegWriteMap(M &_m) : m(_m) {};
893 Value operator[](Key k) const {return -m[k];}
895 void set(Key k, const Value& v) { m.set(k, -v); }
898 ///Returns a \c NegMap class
900 ///This function just returns a \c NegMap class.
902 template <typename M>
903 inline NegMap<M> negMap(const M &m) {
907 ///Returns a \c NegWriteMap class
909 ///This function just returns a \c NegWriteMap class.
910 ///\relates NegWriteMap
911 template <typename M>
912 inline NegWriteMap<M> negMap(M &m) {
913 return NegWriteMap<M>(m);
916 ///Absolute value of a map
918 ///This \c concepts::ReadMap "read only map" returns the absolute value
919 ///of the value returned by the given map.
920 ///Its \c Key and \c Value are inherited from \c M.
921 ///\c Value must be comparable to \c 0 and the unary \c -
922 ///operator must be defined for it, of course.
924 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
927 typedef MapBase<typename M::Key, typename M::Value> Parent;
928 typedef typename Parent::Key Key;
929 typedef typename Parent::Value Value;
932 AbsMap(const M &_m) : m(_m) {};
934 Value operator[](Key k) const {
936 return tmp >= 0 ? tmp : -tmp;
941 ///Returns an \c AbsMap class
943 ///This function just returns an \c AbsMap class.
946 inline AbsMap<M> absMap(const M &m) {
950 ///Converts an STL style functor to a map
952 ///This \c concepts::ReadMap "read only map" returns the value
953 ///of a given functor.
955 ///Template parameters \c K and \c V will become its
956 ///\c Key and \c Value.
957 ///In most cases they have to be given explicitly because a
958 ///functor typically does not provide such typedefs.
960 ///Parameter \c F is the type of the used functor.
964 typename K = typename F::argument_type,
965 typename V = typename F::result_type>
966 class FunctorMap : public MapBase<K, V> {
969 typedef MapBase<K, V> Parent;
970 typedef typename Parent::Key Key;
971 typedef typename Parent::Value Value;
974 FunctorMap(const F &_f = F()) : f(_f) {}
976 Value operator[](Key k) const { return f(k);}
979 ///Returns a \c FunctorMap class
981 ///This function just returns a \c FunctorMap class.
983 ///It is specialized for adaptable function classes and
985 ///\relates FunctorMap
986 template<typename K, typename V, typename F> inline
987 FunctorMap<F, K, V> functorMap(const F &f) {
988 return FunctorMap<F, K, V>(f);
991 template <typename F> inline
992 FunctorMap<F, typename F::argument_type, typename F::result_type>
993 functorMap(const F &f) {
994 return FunctorMap<F, typename F::argument_type,
995 typename F::result_type>(f);
998 template <typename K, typename V> inline
999 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
1000 return FunctorMap<V (*)(K), K, V>(f);
1004 ///Converts a map to an STL style (unary) functor
1006 ///This class Converts a map to an STL style (unary) functor.
1007 ///that is it provides an <tt>operator()</tt> to read its values.
1009 ///For the sake of convenience it also works as
1010 ///a ususal \c concepts::ReadMap "readable map",
1011 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1014 template <typename M>
1015 class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1018 typedef MapBase<typename M::Key, typename M::Value> Parent;
1019 typedef typename Parent::Key Key;
1020 typedef typename Parent::Value Value;
1022 typedef typename M::Key argument_type;
1023 typedef typename M::Value result_type;
1026 MapFunctor(const M &_m) : m(_m) {};
1028 Value operator()(Key k) const {return m[k];}
1030 Value operator[](Key k) const {return m[k];}
1033 ///Returns a \c MapFunctor class
1035 ///This function just returns a \c MapFunctor class.
1036 ///\relates MapFunctor
1037 template<typename M>
1038 inline MapFunctor<M> mapFunctor(const M &m) {
1039 return MapFunctor<M>(m);
1042 ///Applies all map setting operations to two maps
1044 ///This map has two \c concepts::ReadMap "readable map"
1045 ///parameters and each read request will be passed just to the
1046 ///first map. This class is the just readable map type of the ForkWriteMap.
1048 ///The \c Key and \c Value are inherited from \c M1.
1049 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1053 /// \todo Why is it needed?
1054 template<typename M1, typename M2>
1055 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1059 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1060 typedef typename Parent::Key Key;
1061 typedef typename Parent::Value Value;
1064 ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1066 Value operator[](Key k) const {return m1[k];}
1070 ///Applies all map setting operations to two maps
1072 ///This map has two \c concepts::WriteMap "writable map"
1073 ///parameters and each write request will be passed to both of them.
1074 ///If \c M1 is also \c concepts::ReadMap "readable",
1075 ///then the read operations will return the
1076 ///corresponding values of \c M1.
1078 ///The \c Key and \c Value are inherited from \c M1.
1079 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1082 template<typename M1, typename M2>
1083 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1087 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1088 typedef typename Parent::Key Key;
1089 typedef typename Parent::Value Value;
1092 ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1094 Value operator[](Key k) const {return m1[k];}
1096 void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1099 ///Returns a \c ForkMap class
1101 ///This function just returns a \c ForkMap class.
1103 template <typename M1, typename M2>
1104 inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1105 return ForkMap<M1, M2>(m1,m2);
1108 ///Returns a \c ForkWriteMap class
1110 ///This function just returns a \c ForkWriteMap class.
1111 ///\relates ForkWriteMap
1112 template <typename M1, typename M2>
1113 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1114 return ForkWriteMap<M1, M2>(m1,m2);
1119 /* ************* BOOL MAPS ******************* */
1121 ///Logical 'not' of a map
1123 ///This bool \c concepts::ReadMap "read only map" returns the
1124 ///logical negation of the value returned by the given map.
1125 ///Its \c Key is inherited from \c M, its Value is \c bool.
1128 template <typename M>
1129 class NotMap : public MapBase<typename M::Key, bool> {
1132 typedef MapBase<typename M::Key, bool> Parent;
1133 typedef typename Parent::Key Key;
1134 typedef typename Parent::Value Value;
1137 NotMap(const M &_m) : m(_m) {};
1139 Value operator[](Key k) const {return !m[k];}
1142 ///Logical 'not' of a map (ReadWrie version)
1144 ///This bool \c concepts::ReadWriteMap "read-write map" returns the
1145 ///logical negation of the value returned by the given map. When it is set,
1146 ///the opposite value is set to the original map.
1147 ///Its \c Key is inherited from \c M, its Value is \c bool.
1150 template <typename M>
1151 class NotWriteMap : public MapBase<typename M::Key, bool> {
1154 typedef MapBase<typename M::Key, bool> Parent;
1155 typedef typename Parent::Key Key;
1156 typedef typename Parent::Value Value;
1159 NotWriteMap(M &_m) : m(_m) {};
1161 Value operator[](Key k) const {return !m[k];}
1163 void set(Key k, bool v) { m.set(k, !v); }
1166 ///Returns a \c NotMap class
1168 ///This function just returns a \c NotMap class.
1170 template <typename M>
1171 inline NotMap<M> notMap(const M &m) {
1172 return NotMap<M>(m);
1175 ///Returns a \c NotWriteMap class
1177 ///This function just returns a \c NotWriteMap class.
1178 ///\relates NotWriteMap
1179 template <typename M>
1180 inline NotWriteMap<M> notMap(M &m) {
1181 return NotWriteMap<M>(m);
1184 namespace _maps_bits {
1186 template <typename Value>
1188 typedef Value argument_type;
1189 typedef Value result_type;
1190 Value operator()(const Value& val) const {
1195 template <typename _Iterator, typename Enable = void>
1196 struct IteratorTraits {
1197 typedef typename std::iterator_traits<_Iterator>::value_type Value;
1200 template <typename _Iterator>
1201 struct IteratorTraits<_Iterator,
1202 typename exists<typename _Iterator::container_type>::type>
1204 typedef typename _Iterator::container_type::value_type Value;
1210 /// \brief Writable bool map for logging each \c true assigned element
1212 /// Writable bool map for logging each \c true assigned element, i.e it
1213 /// copies all the keys set to \c true to the given iterator.
1215 /// \note The container of the iterator should contain space
1216 /// for each element.
1218 /// The following example shows how you can write the edges found by the Prim
1219 /// algorithm directly
1220 /// to the standard output.
1222 /// typedef IdMap<Graph, Edge> EdgeIdMap;
1223 /// EdgeIdMap edgeId(graph);
1225 /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
1226 /// EdgeIdFunctor edgeIdFunctor(edgeId);
1228 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
1229 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1231 /// prim(graph, cost, writerMap);
1234 ///\sa BackInserterBoolMap
1235 ///\sa FrontInserterBoolMap
1236 ///\sa InserterBoolMap
1238 ///\todo Revise the name of this class and the related ones.
1239 template <typename _Iterator,
1241 _maps_bits::Identity<typename _maps_bits::
1242 IteratorTraits<_Iterator>::Value> >
1243 class StoreBoolMap {
1245 typedef _Iterator Iterator;
1247 typedef typename _Functor::argument_type Key;
1250 typedef _Functor Functor;
1253 StoreBoolMap(Iterator it, const Functor& functor = Functor())
1254 : _begin(it), _end(it), _functor(functor) {}
1256 /// Gives back the given iterator set for the first key
1257 Iterator begin() const {
1261 /// Gives back the the 'after the last' iterator
1262 Iterator end() const {
1266 /// The \c set function of the map
1267 void set(const Key& key, Value value) const {
1269 *_end++ = _functor(key);
1275 mutable Iterator _end;
1279 /// \brief Writable bool map for logging each \c true assigned element in
1280 /// a back insertable container.
1282 /// Writable bool map for logging each \c true assigned element by pushing
1283 /// them into a back insertable container.
1284 /// It can be used to retrieve the items into a standard
1285 /// container. The next example shows how you can store the
1286 /// edges found by the Prim algorithm in a vector.
1289 /// vector<Edge> span_tree_edges;
1290 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1291 /// prim(graph, cost, inserter_map);
1295 ///\sa FrontInserterBoolMap
1296 ///\sa InserterBoolMap
1297 template <typename Container,
1299 _maps_bits::Identity<typename Container::value_type> >
1300 class BackInserterBoolMap {
1302 typedef typename Functor::argument_type Key;
1306 BackInserterBoolMap(Container& _container,
1307 const Functor& _functor = Functor())
1308 : container(_container), functor(_functor) {}
1310 /// The \c set function of the map
1311 void set(const Key& key, Value value) {
1313 container.push_back(functor(key));
1318 Container& container;
1322 /// \brief Writable bool map for logging each \c true assigned element in
1323 /// a front insertable container.
1325 /// Writable bool map for logging each \c true assigned element by pushing
1326 /// them into a front insertable container.
1327 /// It can be used to retrieve the items into a standard
1328 /// container. For example see \ref BackInserterBoolMap.
1330 ///\sa BackInserterBoolMap
1331 ///\sa InserterBoolMap
1332 template <typename Container,
1334 _maps_bits::Identity<typename Container::value_type> >
1335 class FrontInserterBoolMap {
1337 typedef typename Functor::argument_type Key;
1341 FrontInserterBoolMap(Container& _container,
1342 const Functor& _functor = Functor())
1343 : container(_container), functor(_functor) {}
1345 /// The \c set function of the map
1346 void set(const Key& key, Value value) {
1348 container.push_front(functor(key));
1353 Container& container;
1357 /// \brief Writable bool map for storing each \c true assigned element in
1358 /// an insertable container.
1360 /// Writable bool map for storing each \c true assigned element in an
1361 /// insertable container. It will insert all the keys set to \c true into
1364 /// For example, if you want to store the cut arcs of the strongly
1365 /// connected components in a set you can use the next code:
1368 /// set<Arc> cut_arcs;
1369 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1370 /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1373 ///\sa BackInserterBoolMap
1374 ///\sa FrontInserterBoolMap
1375 template <typename Container,
1377 _maps_bits::Identity<typename Container::value_type> >
1378 class InserterBoolMap {
1380 typedef typename Container::value_type Key;
1383 /// Constructor with specified iterator
1385 /// Constructor with specified iterator.
1386 /// \param _container The container for storing the elements.
1387 /// \param _it The elements will be inserted before this iterator.
1388 /// \param _functor The functor that is used when an element is stored.
1389 InserterBoolMap(Container& _container, typename Container::iterator _it,
1390 const Functor& _functor = Functor())
1391 : container(_container), it(_it), functor(_functor) {}
1395 /// Constructor without specified iterator.
1396 /// The elements will be inserted before <tt>_container.end()</tt>.
1397 /// \param _container The container for storing the elements.
1398 /// \param _functor The functor that is used when an element is stored.
1399 InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1400 : container(_container), it(_container.end()), functor(_functor) {}
1402 /// The \c set function of the map
1403 void set(const Key& key, Value value) {
1405 it = container.insert(it, functor(key));
1411 Container& container;
1412 typename Container::iterator it;
1416 /// \brief Writable bool map for filling each \c true assigned element with a
1419 /// Writable bool map for filling each \c true assigned element with a
1420 /// given value. The value can set the container.
1422 /// The following code finds the connected components of a graph
1423 /// and stores it in the \c comp map:
1425 /// typedef Graph::NodeMap<int> ComponentMap;
1426 /// ComponentMap comp(graph);
1427 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1428 /// ComponentFillerMap filler(comp, 0);
1430 /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1431 /// dfs.processedMap(filler);
1433 /// for (NodeIt it(graph); it != INVALID; ++it) {
1434 /// if (!dfs.reached(it)) {
1435 /// dfs.addSource(it);
1437 /// ++filler.fillValue();
1441 template <typename Map>
1444 typedef typename Map::Key Key;
1448 FillBoolMap(Map& _map, const typename Map::Value& _fill)
1449 : map(_map), fill(_fill) {}
1452 FillBoolMap(Map& _map)
1453 : map(_map), fill() {}
1455 /// Gives back the current fill value
1456 const typename Map::Value& fillValue() const {
1460 /// Gives back the current fill value
1461 typename Map::Value& fillValue() {
1465 /// Sets the current fill value
1466 void fillValue(const typename Map::Value& _fill) {
1470 /// The \c set function of the map
1471 void set(const Key& key, Value value) {
1479 typename Map::Value fill;
1483 /// \brief Writable bool map for storing the sequence number of
1484 /// \c true assignments.
1486 /// Writable bool map that stores for each \c true assigned elements
1487 /// the sequence number of this setting.
1488 /// It makes it easy to calculate the leaving
1489 /// order of the nodes in the \c Dfs algorithm.
1492 /// typedef Digraph::NodeMap<int> OrderMap;
1493 /// OrderMap order(digraph);
1494 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1495 /// OrderSetterMap setter(order);
1496 /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1497 /// dfs.processedMap(setter);
1499 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1500 /// if (!dfs.reached(it)) {
1501 /// dfs.addSource(it);
1507 /// The storing of the discovering order is more difficult because the
1508 /// ReachedMap should be readable in the dfs algorithm but the setting
1509 /// order map is not readable. Thus we must use the fork map:
1512 /// typedef Digraph::NodeMap<int> OrderMap;
1513 /// OrderMap order(digraph);
1514 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1515 /// OrderSetterMap setter(order);
1516 /// typedef Digraph::NodeMap<bool> StoreMap;
1517 /// StoreMap store(digraph);
1519 /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1520 /// ReachedMap reached(store, setter);
1522 /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1523 /// dfs.reachedMap(reached);
1525 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1526 /// if (!dfs.reached(it)) {
1527 /// dfs.addSource(it);
1532 template <typename Map>
1533 class SettingOrderBoolMap {
1535 typedef typename Map::Key Key;
1539 SettingOrderBoolMap(Map& _map)
1540 : map(_map), counter(0) {}
1542 /// Number of set operations.
1547 /// The \c set function of the map
1548 void set(const Key& key, Value value) {
1550 map.set(key, counter++);
1562 #endif // LEMON_MAPS_H