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. It provides the necessary type definitions
43 /// required by the map %concepts.
44 template<typename K, typename V>
47 /// \biref The key type of the map.
49 /// \brief The value type of the map.
50 /// (The type of objects associated with the keys).
55 /// Null map. (a.k.a. DoNothingMap)
57 /// This map can be used if you have to provide a map only for
58 /// its type definitions, or if you have to provide a writable map,
59 /// but data written to it is not required (i.e. it will be sent to
60 /// <tt>/dev/null</tt>).
61 /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
64 template<typename K, typename V>
65 class NullMap : public MapBase<K, V> {
67 typedef MapBase<K, V> Parent;
68 typedef typename Parent::Key Key;
69 typedef typename Parent::Value Value;
71 /// Gives back a default constructed element.
72 Value operator[](const Key&) const { return Value(); }
73 /// Absorbs the value.
74 void set(const Key&, const Value&) {}
77 /// Returns a \ref NullMap class
79 /// This function just returns a \ref NullMap class.
81 template <typename K, typename V>
82 NullMap<K, V> nullMap() {
83 return NullMap<K, V>();
89 /// This is a \ref concepts::ReadMap "readable" map which assigns a
90 /// specified value to each key.
92 /// In other aspects it is equivalent to \ref NullMap.
93 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
94 /// concept, but it absorbs the data written to it.
96 /// The simplest way of using this map is through the constMap()
101 template<typename K, typename V>
102 class ConstMap : public MapBase<K, V> {
106 typedef MapBase<K, V> Parent;
107 typedef typename Parent::Key Key;
108 typedef typename Parent::Value Value;
110 /// Default constructor
112 /// Default constructor.
113 /// The value of the map will be default constructed.
116 /// Constructor with specified initial value
118 /// Constructor with specified initial value.
119 /// \param v is the initial value of the map.
120 ConstMap(const Value &v) : _value(v) {}
122 /// Gives back the specified value.
123 Value operator[](const Key&) const { return _value; }
125 /// Absorbs the value.
126 void set(const Key&, const Value&) {}
128 /// Sets the value that is assigned to each key.
129 void setAll(const Value &v) {
133 template<typename V1>
134 ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
137 /// Returns a \ref ConstMap class
139 /// This function just returns a \ref ConstMap class.
140 /// \relates ConstMap
141 template<typename K, typename V>
142 inline ConstMap<K, V> constMap(const V &v) {
143 return ConstMap<K, V>(v);
147 template<typename T, T v>
150 /// Constant map with inlined constant value.
152 /// This is a \ref concepts::ReadMap "readable" map which assigns a
153 /// specified value to each key.
155 /// In other aspects it is equivalent to \ref NullMap.
156 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
157 /// concept, but it absorbs the data written to it.
159 /// The simplest way of using this map is through the constMap()
164 template<typename K, typename V, V v>
165 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
167 typedef MapBase<K, V> Parent;
168 typedef typename Parent::Key Key;
169 typedef typename Parent::Value Value;
174 /// Gives back the specified value.
175 Value operator[](const Key&) const { return v; }
177 /// Absorbs the value.
178 void set(const Key&, const Value&) {}
181 /// Returns a \ref ConstMap class with inlined constant value
183 /// This function just returns a \ref ConstMap class with inlined
185 /// \relates ConstMap
186 template<typename K, typename V, V v>
187 inline ConstMap<K, Const<V, v> > constMap() {
188 return ConstMap<K, Const<V, v> >();
192 /// \brief Identity map.
194 /// This map gives back the given key as value without any
198 template <typename T>
199 class IdentityMap : public MapBase<T, T> {
201 typedef MapBase<T, T> Parent;
202 typedef typename Parent::Key Key;
203 typedef typename Parent::Value Value;
205 /// Gives back the given value without any modification.
206 const T& operator[](const T& t) const {
211 /// Returns an \ref IdentityMap class
213 /// This function just returns an \ref IdentityMap class.
214 /// \relates IdentityMap
216 inline IdentityMap<T> identityMap() {
217 return IdentityMap<T>();
221 /// \brief Map for storing values for integer keys from the range
222 /// <tt>[0..size-1]</tt>.
224 /// This map is essentially a wrapper for \c std::vector. It assigns
225 /// values to integer keys from the range <tt>[0..size-1]</tt>.
226 /// It can be used with some data structures, for example
227 /// \ref UnionFind, \ref BinHeap, when the used items are small
228 /// integers. This map conforms the \ref concepts::ReferenceMap
229 /// "ReferenceMap" concept.
231 /// The simplest way of using this map is through the rangeMap()
233 template <typename V>
234 class RangeMap : public MapBase<int, V> {
235 template <typename V1>
236 friend class RangeMap;
239 typedef std::vector<V> Vector;
244 typedef MapBase<int, V> Parent;
246 typedef typename Parent::Key Key;
248 typedef typename Parent::Value Value;
250 typedef typename Vector::reference Reference;
251 /// Const reference type
252 typedef typename Vector::const_reference ConstReference;
254 typedef True ReferenceMapTag;
258 /// Constructor with specified default value.
259 RangeMap(int size = 0, const Value &value = Value())
260 : _vector(size, value) {}
262 /// Constructs the map from an appropriate \c std::vector.
263 template <typename V1>
264 RangeMap(const std::vector<V1>& vector)
265 : _vector(vector.begin(), vector.end()) {}
267 /// Constructs the map from another \ref RangeMap.
268 template <typename V1>
269 RangeMap(const RangeMap<V1> &c)
270 : _vector(c._vector.begin(), c._vector.end()) {}
272 /// Returns the size of the map.
274 return _vector.size();
279 /// Resizes the underlying \c std::vector container, so changes the
280 /// keyset of the map.
281 /// \param size The new size of the map. The new keyset will be the
282 /// range <tt>[0..size-1]</tt>.
283 /// \param value The default value to assign to the new keys.
284 void resize(int size, const Value &value = Value()) {
285 _vector.resize(size, value);
290 RangeMap& operator=(const RangeMap&);
295 Reference operator[](const Key &k) {
300 ConstReference operator[](const Key &k) const {
305 void set(const Key &k, const Value &v) {
310 /// Returns a \ref RangeMap class
312 /// This function just returns a \ref RangeMap class.
313 /// \relates RangeMap
315 inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
316 return RangeMap<V>(size, value);
319 /// \brief Returns a \ref RangeMap class created from an appropriate
322 /// This function just returns a \ref RangeMap class created from an
323 /// appropriate \c std::vector.
324 /// \relates RangeMap
326 inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
327 return RangeMap<V>(vector);
331 /// Map type based on \c std::map
333 /// This map is essentially a wrapper for \c std::map with addition
334 /// that you can specify a default value for the keys that are not
335 /// stored actually. This value can be different from the default
336 /// contructed value (i.e. \c %Value()).
337 /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
340 /// This map is useful if a default value should be assigned to most of
341 /// the keys and different values should be assigned only to a few
342 /// keys (i.e. the map is "sparse").
343 /// The name of this type also refers to this important usage.
345 /// Apart form that this map can be used in many other cases since it
346 /// is based on \c std::map, which is a general associative container.
347 /// However keep in mind that it is usually not as efficient as other
350 /// The simplest way of using this map is through the sparseMap()
352 template <typename K, typename V, typename Compare = std::less<K> >
353 class SparseMap : public MapBase<K, V> {
354 template <typename K1, typename V1, typename C1>
355 friend class SparseMap;
358 typedef MapBase<K, V> Parent;
360 typedef typename Parent::Key Key;
362 typedef typename Parent::Value Value;
364 typedef Value& Reference;
365 /// Const reference type
366 typedef const Value& ConstReference;
368 typedef True ReferenceMapTag;
372 typedef std::map<K, V, Compare> Map;
378 /// \brief Constructor with specified default value.
379 SparseMap(const Value &value = Value()) : _value(value) {}
380 /// \brief Constructs the map from an appropriate \c std::map, and
381 /// explicitly specifies a default value.
382 template <typename V1, typename Comp1>
383 SparseMap(const std::map<Key, V1, Comp1> &map,
384 const Value &value = Value())
385 : _map(map.begin(), map.end()), _value(value) {}
387 /// \brief Constructs the map from another \ref SparseMap.
388 template<typename V1, typename Comp1>
389 SparseMap(const SparseMap<Key, V1, Comp1> &c)
390 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
394 SparseMap& operator=(const SparseMap&);
399 Reference operator[](const Key &k) {
400 typename Map::iterator it = _map.lower_bound(k);
401 if (it != _map.end() && !_map.key_comp()(k, it->first))
404 return _map.insert(it, std::make_pair(k, _value))->second;
408 ConstReference operator[](const Key &k) const {
409 typename Map::const_iterator it = _map.find(k);
410 if (it != _map.end())
417 void set(const Key &k, const Value &v) {
418 typename Map::iterator it = _map.lower_bound(k);
419 if (it != _map.end() && !_map.key_comp()(k, it->first))
422 _map.insert(it, std::make_pair(k, v));
426 void setAll(const Value &v) {
432 /// Returns a \ref SparseMap class
434 /// This function just returns a \ref SparseMap class with specified
436 /// \relates SparseMap
437 template<typename K, typename V, typename Compare>
438 inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
439 return SparseMap<K, V, Compare>(value);
442 template<typename K, typename V>
443 inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
444 return SparseMap<K, V, std::less<K> >(value);
447 /// \brief Returns a \ref SparseMap class created from an appropriate
450 /// This function just returns a \ref SparseMap class created from an
451 /// appropriate \c std::map.
452 /// \relates SparseMap
453 template<typename K, typename V, typename Compare>
454 inline SparseMap<K, V, Compare>
455 sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
457 return SparseMap<K, V, Compare>(map, value);
462 /// \addtogroup map_adaptors
465 /// Composition of two maps
467 /// This \ref concepts::ReadMap "read only map" returns the
468 /// composition of two given maps. That is to say, if \c m1 is of
469 /// type \c M1 and \c m2 is of \c M2, then for
471 /// ComposeMap<M1, M2> cm(m1,m2);
473 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
475 /// The \c Key type of the map is inherited from \c M2 and the
476 /// \c Value type is from \c M1.
477 /// \c M2::Value must be convertible to \c M1::Key.
479 /// The simplest way of using this map is through the composeMap()
484 /// \todo Check the requirements.
485 template <typename M1, typename M2>
486 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
490 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
491 typedef typename Parent::Key Key;
492 typedef typename Parent::Value Value;
495 ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
498 typename MapTraits<M1>::ConstReturnValue
499 operator[](const Key &k) const { return _m1[_m2[k]]; }
502 /// Returns a \ref ComposeMap class
504 /// This function just returns a \ref ComposeMap class.
506 /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
507 /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
508 /// will be equal to <tt>m1[m2[x]]</tt>.
510 /// \relates ComposeMap
511 template <typename M1, typename M2>
512 inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
513 return ComposeMap<M1, M2>(m1, m2);
517 /// Combination of two maps using an STL (binary) functor.
519 /// This \ref concepts::ReadMap "read only map" takes two maps and a
520 /// binary functor and returns the combination of the two given maps
521 /// using the functor.
522 /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
523 /// and \c f is of \c F, then for
525 /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
527 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
529 /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
530 /// must be convertible to \c M2::Key) and the \c Value type is \c V.
531 /// \c M2::Value and \c M1::Value must be convertible to the
532 /// corresponding input parameter of \c F and the return type of \c F
533 /// must be convertible to \c V.
535 /// The simplest way of using this map is through the combineMap()
540 /// \todo Check the requirements.
541 template<typename M1, typename M2, typename F,
542 typename V = typename F::result_type>
543 class CombineMap : public MapBase<typename M1::Key, V> {
548 typedef MapBase<typename M1::Key, V> Parent;
549 typedef typename Parent::Key Key;
550 typedef typename Parent::Value Value;
553 CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
554 : _m1(m1), _m2(m2), _f(f) {}
556 Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
559 /// Returns a \ref CombineMap class
561 /// This function just returns a \ref CombineMap class.
563 /// For example, if \c m1 and \c m2 are both maps with \c double
566 /// combineMap(m1,m2,std::plus<double>())
573 /// This function is specialized for adaptable binary function
574 /// classes and C++ functions.
576 /// \relates CombineMap
577 template<typename M1, typename M2, typename F, typename V>
578 inline CombineMap<M1, M2, F, V>
579 combineMap(const M1 &m1, const M2 &m2, const F &f) {
580 return CombineMap<M1, M2, F, V>(m1,m2,f);
583 template<typename M1, typename M2, typename F>
584 inline CombineMap<M1, M2, F, typename F::result_type>
585 combineMap(const M1 &m1, const M2 &m2, const F &f) {
586 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
589 template<typename M1, typename M2, typename K1, typename K2, typename V>
590 inline CombineMap<M1, M2, V (*)(K1, K2), V>
591 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
592 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
596 /// Converts an STL style (unary) functor to a map
598 /// This \ref concepts::ReadMap "read only map" returns the value
599 /// of a given functor. Actually, it just wraps the functor and
600 /// provides the \c Key and \c Value typedefs.
602 /// Template parameters \c K and \c V will become its \c Key and
603 /// \c Value. In most cases they have to be given explicitly because
604 /// a functor typically does not provide \c argument_type and
605 /// \c result_type typedefs.
606 /// Parameter \c F is the type of the used functor.
608 /// The simplest way of using this map is through the functorToMap()
613 typename K = typename F::argument_type,
614 typename V = typename F::result_type>
615 class FunctorToMap : public MapBase<K, V> {
618 typedef MapBase<K, V> Parent;
619 typedef typename Parent::Key Key;
620 typedef typename Parent::Value Value;
623 FunctorToMap(const F &f = F()) : _f(f) {}
625 Value operator[](const Key &k) const { return _f(k); }
628 /// Returns a \ref FunctorToMap class
630 /// This function just returns a \ref FunctorToMap class.
632 /// This function is specialized for adaptable binary function
633 /// classes and C++ functions.
635 /// \relates FunctorToMap
636 template<typename K, typename V, typename F>
637 inline FunctorToMap<F, K, V> functorToMap(const F &f) {
638 return FunctorToMap<F, K, V>(f);
641 template <typename F>
642 inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
643 functorToMap(const F &f)
645 return FunctorToMap<F, typename F::argument_type,
646 typename F::result_type>(f);
649 template <typename K, typename V>
650 inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
651 return FunctorToMap<V (*)(K), K, V>(f);
655 /// Converts a map to an STL style (unary) functor
657 /// This class converts a map to an STL style (unary) functor.
658 /// That is it provides an <tt>operator()</tt> to read its values.
660 /// For the sake of convenience it also works as a usual
661 /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
662 /// and the \c Key and \c Value typedefs also exist.
664 /// The simplest way of using this map is through the mapToFunctor()
668 template <typename M>
669 class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
672 typedef MapBase<typename M::Key, typename M::Value> Parent;
673 typedef typename Parent::Key Key;
674 typedef typename Parent::Value Value;
676 typedef typename Parent::Key argument_type;
677 typedef typename Parent::Value result_type;
680 MapToFunctor(const M &m) : _m(m) {}
682 Value operator()(const Key &k) const { return _m[k]; }
684 Value operator[](const Key &k) const { return _m[k]; }
687 /// Returns a \ref MapToFunctor class
689 /// This function just returns a \ref MapToFunctor class.
690 /// \relates MapToFunctor
692 inline MapToFunctor<M> mapToFunctor(const M &m) {
693 return MapToFunctor<M>(m);
697 /// \brief Map adaptor to convert the \c Value type of a map to
698 /// another type using the default conversion.
700 /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
701 /// "readable map" to another type using the default conversion.
702 /// The \c Key type of it is inherited from \c M and the \c Value
704 /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
706 /// The simplest way of using this map is through the convertMap()
708 template <typename M, typename V>
709 class ConvertMap : public MapBase<typename M::Key, V> {
712 typedef MapBase<typename M::Key, V> Parent;
713 typedef typename Parent::Key Key;
714 typedef typename Parent::Value Value;
719 /// \param m The underlying map.
720 ConvertMap(const M &m) : _m(m) {}
723 Value operator[](const Key &k) const { return _m[k]; }
726 /// Returns a \ref ConvertMap class
728 /// This function just returns a \ref ConvertMap class.
729 /// \relates ConvertMap
730 template<typename V, typename M>
731 inline ConvertMap<M, V> convertMap(const M &map) {
732 return ConvertMap<M, V>(map);
736 /// Applies all map setting operations to two maps
738 /// This map has two \ref concepts::WriteMap "writable map" parameters
739 /// and each write request will be passed to both of them.
740 /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
741 /// operations will return the corresponding values of \c M1.
743 /// The \c Key and \c Value types are inherited from \c M1.
744 /// The \c Key and \c Value of \c M2 must be convertible from those
747 /// The simplest way of using this map is through the forkMap()
749 template<typename M1, typename M2>
750 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
754 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
755 typedef typename Parent::Key Key;
756 typedef typename Parent::Value Value;
759 ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
760 /// Returns the value associated with the given key in the first map.
761 Value operator[](const Key &k) const { return _m1[k]; }
762 /// Sets the value associated with the given key in both maps.
763 void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
766 /// Returns a \ref ForkMap class
768 /// This function just returns a \ref ForkMap class.
770 template <typename M1, typename M2>
771 inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
772 return ForkMap<M1,M2>(m1,m2);
776 /// Simple wrapping of a map
778 /// This \ref concepts::ReadMap "read only map" returns the simple
779 /// wrapping of the given map. Sometimes the reference maps cannot be
780 /// combined with simple read maps. This map adaptor wraps the given
781 /// map to simple read map.
783 /// The simplest way of using this map is through the wrapMap()
788 class WrapMap : public MapBase<typename M::Key, typename M::Value> {
791 typedef MapBase<typename M::Key, typename M::Value> Parent;
792 typedef typename Parent::Key Key;
793 typedef typename Parent::Value Value;
796 WrapMap(const M &m) : _m(m) {}
798 Value operator[](const Key &k) const { return _m[k]; }
801 /// Returns a \ref WrapMap class
803 /// This function just returns a \ref WrapMap class.
806 inline WrapMap<M> wrapMap(const M &map) {
807 return WrapMap<M>(map);
811 /// Simple writable wrapping of a map
813 /// This \ref concepts::ReadWriteMap "read-write map" returns the simple
814 /// wrapping of the given map. Sometimes the reference maps cannot be
815 /// combined with simple read-write maps. This map adaptor wraps the
816 /// given map to simple read-write map.
818 /// The simplest way of using this map is through the wrapWriteMap()
823 class WrapWriteMap : public MapBase<typename M::Key, typename M::Value> {
826 typedef MapBase<typename M::Key, typename M::Value> Parent;
827 typedef typename Parent::Key Key;
828 typedef typename Parent::Value Value;
831 WrapWriteMap(M &m) : _m(m) {}
833 Value operator[](const Key &k) const { return _m[k]; }
835 void set(const Key &k, const Value &c) { _m.set(k, c); }
838 ///Returns a \ref WrapWriteMap class
840 ///This function just returns a \ref WrapWriteMap class.
841 ///\relates WrapWriteMap
843 inline WrapWriteMap<M> wrapWriteMap(M &map) {
844 return WrapWriteMap<M>(map);
850 /// This \ref concepts::ReadMap "read only map" returns the sum
851 /// of the values of the two given maps.
852 /// Its \c Key and \c Value types are inherited from \c M1.
853 /// The \c Key and \c Value of \c M2 must be convertible to those of
856 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
858 /// AddMap<M1,M2> am(m1,m2);
860 /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
862 /// The simplest way of using this map is through the addMap()
865 /// \sa SubMap, MulMap, DivMap
866 /// \sa ShiftMap, ShiftWriteMap
867 template<typename M1, typename M2>
868 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
872 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
873 typedef typename Parent::Key Key;
874 typedef typename Parent::Value Value;
877 AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
879 Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
882 /// Returns an \ref AddMap class
884 /// This function just returns an \ref AddMap class.
886 /// For example, if \c m1 and \c m2 are both maps with \c double
887 /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
888 /// <tt>m1[x]+m2[x]</tt>.
891 template<typename M1, typename M2>
892 inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
893 return AddMap<M1, M2>(m1,m2);
897 /// Difference of two maps
899 /// This \ref concepts::ReadMap "read only map" returns the difference
900 /// of the values of the two given maps.
901 /// Its \c Key and \c Value types are inherited from \c M1.
902 /// The \c Key and \c Value of \c M2 must be convertible to those of
905 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
907 /// SubMap<M1,M2> sm(m1,m2);
909 /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
911 /// The simplest way of using this map is through the subMap()
914 /// \sa AddMap, MulMap, DivMap
915 template<typename M1, typename M2>
916 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
920 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
921 typedef typename Parent::Key Key;
922 typedef typename Parent::Value Value;
925 SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
927 Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
930 /// Returns a \ref SubMap class
932 /// This function just returns a \ref SubMap class.
934 /// For example, if \c m1 and \c m2 are both maps with \c double
935 /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
936 /// <tt>m1[x]-m2[x]</tt>.
939 template<typename M1, typename M2>
940 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
941 return SubMap<M1, M2>(m1,m2);
945 /// Product of two maps
947 /// This \ref concepts::ReadMap "read only map" returns the product
948 /// of the values of the two given maps.
949 /// Its \c Key and \c Value types are inherited from \c M1.
950 /// The \c Key and \c Value of \c M2 must be convertible to those of
953 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
955 /// MulMap<M1,M2> mm(m1,m2);
957 /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
959 /// The simplest way of using this map is through the mulMap()
962 /// \sa AddMap, SubMap, DivMap
963 /// \sa ScaleMap, ScaleWriteMap
964 template<typename M1, typename M2>
965 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
969 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
970 typedef typename Parent::Key Key;
971 typedef typename Parent::Value Value;
974 MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
976 Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
979 /// Returns a \ref MulMap class
981 /// This function just returns a \ref MulMap class.
983 /// For example, if \c m1 and \c m2 are both maps with \c double
984 /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
985 /// <tt>m1[x]*m2[x]</tt>.
988 template<typename M1, typename M2>
989 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
990 return MulMap<M1, M2>(m1,m2);
994 /// Quotient of two maps
996 /// This \ref concepts::ReadMap "read only map" returns the quotient
997 /// of the values of the two given maps.
998 /// Its \c Key and \c Value types are inherited from \c M1.
999 /// The \c Key and \c Value of \c M2 must be convertible to those of
1002 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1004 /// DivMap<M1,M2> dm(m1,m2);
1006 /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
1008 /// The simplest way of using this map is through the divMap()
1011 /// \sa AddMap, SubMap, MulMap
1012 template<typename M1, typename M2>
1013 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
1017 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1018 typedef typename Parent::Key Key;
1019 typedef typename Parent::Value Value;
1022 DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
1024 Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
1027 /// Returns a \ref DivMap class
1029 /// This function just returns a \ref DivMap class.
1031 /// For example, if \c m1 and \c m2 are both maps with \c double
1032 /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
1033 /// <tt>m1[x]/m2[x]</tt>.
1036 template<typename M1, typename M2>
1037 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
1038 return DivMap<M1, M2>(m1,m2);
1042 /// Shifts a map with a constant.
1044 /// This \ref concepts::ReadMap "read only map" returns the sum of
1045 /// the given map and a constant value (i.e. it shifts the map with
1046 /// the constant). Its \c Key and \c Value are inherited from \c M.
1050 /// ShiftMap<M> sh(m,v);
1052 /// is equivalent to
1054 /// ConstMap<M::Key, M::Value> cm(v);
1055 /// AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
1058 /// The simplest way of using this map is through the shiftMap()
1061 /// \sa ShiftWriteMap
1062 template<typename M, typename C = typename M::Value>
1063 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
1067 typedef MapBase<typename M::Key, typename M::Value> Parent;
1068 typedef typename Parent::Key Key;
1069 typedef typename Parent::Value Value;
1074 /// \param m The undelying map.
1075 /// \param v The constant value.
1076 ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1078 Value operator[](const Key &k) const { return _m[k]+_v; }
1081 /// Shifts a map with a constant (read-write version).
1083 /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
1084 /// of the given map and a constant value (i.e. it shifts the map with
1085 /// the constant). Its \c Key and \c Value are inherited from \c M.
1086 /// It makes also possible to write the map.
1088 /// The simplest way of using this map is through the shiftWriteMap()
1092 template<typename M, typename C = typename M::Value>
1093 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1097 typedef MapBase<typename M::Key, typename M::Value> Parent;
1098 typedef typename Parent::Key Key;
1099 typedef typename Parent::Value Value;
1104 /// \param m The undelying map.
1105 /// \param v The constant value.
1106 ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1108 Value operator[](const Key &k) const { return _m[k]+_v; }
1110 void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
1113 /// Returns a \ref ShiftMap class
1115 /// This function just returns a \ref ShiftMap class.
1117 /// For example, if \c m is a map with \c double values and \c v is
1118 /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
1119 /// <tt>m[x]+v</tt>.
1121 /// \relates ShiftMap
1122 template<typename M, typename C>
1123 inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
1124 return ShiftMap<M, C>(m,v);
1127 /// Returns a \ref ShiftWriteMap class
1129 /// This function just returns a \ref ShiftWriteMap class.
1131 /// For example, if \c m is a map with \c double values and \c v is
1132 /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
1133 /// <tt>m[x]+v</tt>.
1134 /// Moreover it makes also possible to write the map.
1136 /// \relates ShiftWriteMap
1137 template<typename M, typename C>
1138 inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
1139 return ShiftWriteMap<M, C>(m,v);
1143 /// Scales a map with a constant.
1145 /// This \ref concepts::ReadMap "read only map" returns the value of
1146 /// the given map multiplied from the left side with a constant value.
1147 /// Its \c Key and \c Value are inherited from \c M.
1151 /// ScaleMap<M> sc(m,v);
1153 /// is equivalent to
1155 /// ConstMap<M::Key, M::Value> cm(v);
1156 /// MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
1159 /// The simplest way of using this map is through the scaleMap()
1162 /// \sa ScaleWriteMap
1163 template<typename M, typename C = typename M::Value>
1164 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1168 typedef MapBase<typename M::Key, typename M::Value> Parent;
1169 typedef typename Parent::Key Key;
1170 typedef typename Parent::Value Value;
1175 /// \param m The undelying map.
1176 /// \param v The constant value.
1177 ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
1179 Value operator[](const Key &k) const { return _v*_m[k]; }
1182 /// Scales a map with a constant (read-write version).
1184 /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
1185 /// the given map multiplied from the left side with a constant value.
1186 /// Its \c Key and \c Value are inherited from \c M.
1187 /// It can also be used as write map if the \c / operator is defined
1188 /// between \c Value and \c C and the given multiplier is not zero.
1190 /// The simplest way of using this map is through the scaleWriteMap()
1194 template<typename M, typename C = typename M::Value>
1195 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1199 typedef MapBase<typename M::Key, typename M::Value> Parent;
1200 typedef typename Parent::Key Key;
1201 typedef typename Parent::Value Value;
1206 /// \param m The undelying map.
1207 /// \param v The constant value.
1208 ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1210 Value operator[](const Key &k) const { return _v*_m[k]; }
1212 void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
1215 /// Returns a \ref ScaleMap class
1217 /// This function just returns a \ref ScaleMap class.
1219 /// For example, if \c m is a map with \c double values and \c v is
1220 /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
1221 /// <tt>v*m[x]</tt>.
1223 /// \relates ScaleMap
1224 template<typename M, typename C>
1225 inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
1226 return ScaleMap<M, C>(m,v);
1229 /// Returns a \ref ScaleWriteMap class
1231 /// This function just returns a \ref ScaleWriteMap class.
1233 /// For example, if \c m is a map with \c double values and \c v is
1234 /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
1235 /// <tt>v*m[x]</tt>.
1236 /// Moreover it makes also possible to write the map.
1238 /// \relates ScaleWriteMap
1239 template<typename M, typename C>
1240 inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
1241 return ScaleWriteMap<M, C>(m,v);
1245 /// Negative of a map
1247 /// This \ref concepts::ReadMap "read only map" returns the negative
1248 /// of the values of the given map (using the unary \c - operator).
1249 /// Its \c Key and \c Value are inherited from \c M.
1251 /// If M::Value is \c int, \c double etc., then
1253 /// NegMap<M> neg(m);
1255 /// is equivalent to
1257 /// ScaleMap<M> neg(m,-1);
1260 /// The simplest way of using this map is through the negMap()
1264 template<typename M>
1265 class NegMap : public MapBase<typename M::Key, typename M::Value> {
1268 typedef MapBase<typename M::Key, typename M::Value> Parent;
1269 typedef typename Parent::Key Key;
1270 typedef typename Parent::Value Value;
1273 NegMap(const M &m) : _m(m) {}
1275 Value operator[](const Key &k) const { return -_m[k]; }
1278 /// Negative of a map (read-write version)
1280 /// This \ref concepts::ReadWriteMap "read-write map" returns the
1281 /// negative of the values of the given map (using the unary \c -
1283 /// Its \c Key and \c Value are inherited from \c M.
1284 /// It makes also possible to write the map.
1286 /// If M::Value is \c int, \c double etc., then
1288 /// NegWriteMap<M> neg(m);
1290 /// is equivalent to
1292 /// ScaleWriteMap<M> neg(m,-1);
1295 /// The simplest way of using this map is through the negWriteMap()
1299 template<typename M>
1300 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1303 typedef MapBase<typename M::Key, typename M::Value> Parent;
1304 typedef typename Parent::Key Key;
1305 typedef typename Parent::Value Value;
1308 NegWriteMap(M &m) : _m(m) {}
1310 Value operator[](const Key &k) const { return -_m[k]; }
1312 void set(const Key &k, const Value &v) { _m.set(k, -v); }
1315 /// Returns a \ref NegMap class
1317 /// This function just returns a \ref NegMap class.
1319 /// For example, if \c m is a map with \c double values, then
1320 /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1323 template <typename M>
1324 inline NegMap<M> negMap(const M &m) {
1325 return NegMap<M>(m);
1328 /// Returns a \ref NegWriteMap class
1330 /// This function just returns a \ref NegWriteMap class.
1332 /// For example, if \c m is a map with \c double values, then
1333 /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1334 /// Moreover it makes also possible to write the map.
1336 /// \relates NegWriteMap
1337 template <typename M>
1338 inline NegWriteMap<M> negWriteMap(M &m) {
1339 return NegWriteMap<M>(m);
1343 /// Absolute value of a map
1345 /// This \ref concepts::ReadMap "read only map" returns the absolute
1346 /// value of the values of the given map.
1347 /// Its \c Key and \c Value are inherited from \c M.
1348 /// \c Value must be comparable to \c 0 and the unary \c -
1349 /// operator must be defined for it, of course.
1351 /// The simplest way of using this map is through the absMap()
1353 template<typename M>
1354 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1357 typedef MapBase<typename M::Key, typename M::Value> Parent;
1358 typedef typename Parent::Key Key;
1359 typedef typename Parent::Value Value;
1362 AbsMap(const M &m) : _m(m) {}
1364 Value operator[](const Key &k) const {
1366 return tmp >= 0 ? tmp : -tmp;
1371 /// Returns an \ref AbsMap class
1373 /// This function just returns an \ref AbsMap class.
1375 /// For example, if \c m is a map with \c double values, then
1376 /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
1377 /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
1381 template<typename M>
1382 inline AbsMap<M> absMap(const M &m) {
1383 return AbsMap<M>(m);
1387 /// Logical 'not' of a map
1389 /// This \ref concepts::ReadMap "read only map" returns the logical
1390 /// negation of the values of the given map.
1391 /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1393 /// The simplest way of using this map is through the notMap()
1397 template <typename M>
1398 class NotMap : public MapBase<typename M::Key, bool> {
1401 typedef MapBase<typename M::Key, bool> Parent;
1402 typedef typename Parent::Key Key;
1403 typedef typename Parent::Value Value;
1406 NotMap(const M &m) : _m(m) {}
1408 Value operator[](const Key &k) const { return !_m[k]; }
1411 /// Logical 'not' of a map (read-write version)
1413 /// This \ref concepts::ReadWriteMap "read-write map" returns the
1414 /// logical negation of the values of the given map.
1415 /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1416 /// It makes also possible to write the map. When a value is set,
1417 /// the opposite value is set to the original map.
1419 /// The simplest way of using this map is through the notWriteMap()
1423 template <typename M>
1424 class NotWriteMap : public MapBase<typename M::Key, bool> {
1427 typedef MapBase<typename M::Key, bool> Parent;
1428 typedef typename Parent::Key Key;
1429 typedef typename Parent::Value Value;
1432 NotWriteMap(M &m) : _m(m) {}
1434 Value operator[](const Key &k) const { return !_m[k]; }
1436 void set(const Key &k, bool v) { _m.set(k, !v); }
1439 /// Returns a \ref NotMap class
1441 /// This function just returns a \ref NotMap class.
1443 /// For example, if \c m is a map with \c bool values, then
1444 /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1447 template <typename M>
1448 inline NotMap<M> notMap(const M &m) {
1449 return NotMap<M>(m);
1452 /// Returns a \ref NotWriteMap class
1454 /// This function just returns a \ref NotWriteMap class.
1456 /// For example, if \c m is a map with \c bool values, then
1457 /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1458 /// Moreover it makes also possible to write the map.
1460 /// \relates NotWriteMap
1461 template <typename M>
1462 inline NotWriteMap<M> notWriteMap(M &m) {
1463 return NotWriteMap<M>(m);
1467 namespace _maps_bits {
1469 template <typename Value>
1471 typedef Value argument_type;
1472 typedef Value result_type;
1473 Value operator()(const Value& val) const {
1478 template <typename _Iterator, typename Enable = void>
1479 struct IteratorTraits {
1480 typedef typename std::iterator_traits<_Iterator>::value_type Value;
1483 template <typename _Iterator>
1484 struct IteratorTraits<_Iterator,
1485 typename exists<typename _Iterator::container_type>::type>
1487 typedef typename _Iterator::container_type::value_type Value;
1493 /// \brief Writable bool map for logging each \c true assigned element
1495 /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
1496 /// each \c true assigned element, i.e it copies all the keys set
1497 /// to \c true to the given iterator.
1499 /// \note The container of the iterator should contain space
1500 /// for each element.
1502 /// The following example shows how you can write the edges found by
1503 /// the \ref Prim algorithm directly to the standard output.
1505 /// typedef IdMap<Graph, Edge> EdgeIdMap;
1506 /// EdgeIdMap edgeId(graph);
1508 /// typedef MapToFunctor<EdgeIdMap> EdgeIdFunctor;
1509 /// EdgeIdFunctor edgeIdFunctor(edgeId);
1511 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
1512 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1514 /// prim(graph, cost, writerMap);
1517 /// \sa BackInserterBoolMap
1518 /// \sa FrontInserterBoolMap
1519 /// \sa InserterBoolMap
1521 /// \todo Revise the name of this class and the related ones.
1522 template <typename _Iterator,
1524 _maps_bits::Identity<typename _maps_bits::
1525 IteratorTraits<_Iterator>::Value> >
1526 class StoreBoolMap {
1528 typedef _Iterator Iterator;
1530 typedef typename _Functor::argument_type Key;
1533 typedef _Functor Functor;
1536 StoreBoolMap(Iterator it, const Functor& functor = Functor())
1537 : _begin(it), _end(it), _functor(functor) {}
1539 /// Gives back the given iterator set for the first key
1540 Iterator begin() const {
1544 /// Gives back the the 'after the last' iterator
1545 Iterator end() const {
1549 /// The set function of the map
1550 void set(const Key& key, Value value) const {
1552 *_end++ = _functor(key);
1558 mutable Iterator _end;
1562 /// \brief Writable bool map for logging each \c true assigned element in
1563 /// a back insertable container.
1565 /// Writable bool map for logging each \c true assigned element by pushing
1566 /// them into a back insertable container.
1567 /// It can be used to retrieve the items into a standard
1568 /// container. The next example shows how you can store the
1569 /// edges found by the Prim algorithm in a vector.
1572 /// vector<Edge> span_tree_edges;
1573 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1574 /// prim(graph, cost, inserter_map);
1577 /// \sa StoreBoolMap
1578 /// \sa FrontInserterBoolMap
1579 /// \sa InserterBoolMap
1580 template <typename Container,
1582 _maps_bits::Identity<typename Container::value_type> >
1583 class BackInserterBoolMap {
1585 typedef typename Functor::argument_type Key;
1589 BackInserterBoolMap(Container& _container,
1590 const Functor& _functor = Functor())
1591 : container(_container), functor(_functor) {}
1593 /// The set function of the map
1594 void set(const Key& key, Value value) {
1596 container.push_back(functor(key));
1601 Container& container;
1605 /// \brief Writable bool map for logging each \c true assigned element in
1606 /// a front insertable container.
1608 /// Writable bool map for logging each \c true assigned element by pushing
1609 /// them into a front insertable container.
1610 /// It can be used to retrieve the items into a standard
1611 /// container. For example see \ref BackInserterBoolMap.
1613 /// \sa BackInserterBoolMap
1614 /// \sa InserterBoolMap
1615 template <typename Container,
1617 _maps_bits::Identity<typename Container::value_type> >
1618 class FrontInserterBoolMap {
1620 typedef typename Functor::argument_type Key;
1624 FrontInserterBoolMap(Container& _container,
1625 const Functor& _functor = Functor())
1626 : container(_container), functor(_functor) {}
1628 /// The set function of the map
1629 void set(const Key& key, Value value) {
1631 container.push_front(functor(key));
1636 Container& container;
1640 /// \brief Writable bool map for storing each \c true assigned element in
1641 /// an insertable container.
1643 /// Writable bool map for storing each \c true assigned element in an
1644 /// insertable container. It will insert all the keys set to \c true into
1647 /// For example, if you want to store the cut arcs of the strongly
1648 /// connected components in a set you can use the next code:
1651 /// set<Arc> cut_arcs;
1652 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1653 /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1656 /// \sa BackInserterBoolMap
1657 /// \sa FrontInserterBoolMap
1658 template <typename Container,
1660 _maps_bits::Identity<typename Container::value_type> >
1661 class InserterBoolMap {
1663 typedef typename Container::value_type Key;
1666 /// Constructor with specified iterator
1668 /// Constructor with specified iterator.
1669 /// \param _container The container for storing the elements.
1670 /// \param _it The elements will be inserted before this iterator.
1671 /// \param _functor The functor that is used when an element is stored.
1672 InserterBoolMap(Container& _container, typename Container::iterator _it,
1673 const Functor& _functor = Functor())
1674 : container(_container), it(_it), functor(_functor) {}
1678 /// Constructor without specified iterator.
1679 /// The elements will be inserted before <tt>_container.end()</tt>.
1680 /// \param _container The container for storing the elements.
1681 /// \param _functor The functor that is used when an element is stored.
1682 InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1683 : container(_container), it(_container.end()), functor(_functor) {}
1685 /// The set function of the map
1686 void set(const Key& key, Value value) {
1688 it = container.insert(it, functor(key));
1694 Container& container;
1695 typename Container::iterator it;
1699 /// \brief Writable bool map for filling each \c true assigned element with a
1702 /// Writable bool map for filling each \c true assigned element with a
1703 /// given value. The value can set the container.
1705 /// The following code finds the connected components of a graph
1706 /// and stores it in the \c comp map:
1708 /// typedef Graph::NodeMap<int> ComponentMap;
1709 /// ComponentMap comp(graph);
1710 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1711 /// ComponentFillerMap filler(comp, 0);
1713 /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1714 /// dfs.processedMap(filler);
1716 /// for (NodeIt it(graph); it != INVALID; ++it) {
1717 /// if (!dfs.reached(it)) {
1718 /// dfs.addSource(it);
1720 /// ++filler.fillValue();
1724 template <typename Map>
1727 typedef typename Map::Key Key;
1731 FillBoolMap(Map& _map, const typename Map::Value& _fill)
1732 : map(_map), fill(_fill) {}
1735 FillBoolMap(Map& _map)
1736 : map(_map), fill() {}
1738 /// Gives back the current fill value
1739 const typename Map::Value& fillValue() const {
1743 /// Gives back the current fill value
1744 typename Map::Value& fillValue() {
1748 /// Sets the current fill value
1749 void fillValue(const typename Map::Value& _fill) {
1753 /// The set function of the map
1754 void set(const Key& key, Value value) {
1762 typename Map::Value fill;
1766 /// \brief Writable bool map for storing the sequence number of
1767 /// \c true assignments.
1769 /// Writable bool map that stores for each \c true assigned elements
1770 /// the sequence number of this setting.
1771 /// It makes it easy to calculate the leaving
1772 /// order of the nodes in the \ref Dfs algorithm.
1775 /// typedef Digraph::NodeMap<int> OrderMap;
1776 /// OrderMap order(digraph);
1777 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1778 /// OrderSetterMap setter(order);
1779 /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1780 /// dfs.processedMap(setter);
1782 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1783 /// if (!dfs.reached(it)) {
1784 /// dfs.addSource(it);
1790 /// The storing of the discovering order is more difficult because the
1791 /// ReachedMap should be readable in the dfs algorithm but the setting
1792 /// order map is not readable. Thus we must use the fork map:
1795 /// typedef Digraph::NodeMap<int> OrderMap;
1796 /// OrderMap order(digraph);
1797 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1798 /// OrderSetterMap setter(order);
1799 /// typedef Digraph::NodeMap<bool> StoreMap;
1800 /// StoreMap store(digraph);
1802 /// typedef ForkMap<StoreMap, OrderSetterMap> ReachedMap;
1803 /// ReachedMap reached(store, setter);
1805 /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1806 /// dfs.reachedMap(reached);
1808 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1809 /// if (!dfs.reached(it)) {
1810 /// dfs.addSource(it);
1815 template <typename Map>
1816 class SettingOrderBoolMap {
1818 typedef typename Map::Key Key;
1822 SettingOrderBoolMap(Map& _map)
1823 : map(_map), counter(0) {}
1825 /// Number of set operations.
1830 /// The set function of the map
1831 void set(const Key& key, Value value) {
1833 map.set(key, counter++);
1845 #endif // LEMON_MAPS_H