The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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
24 #include <lemon/utility.h>
25 #include <lemon/traits.h>
29 ///\brief Miscellaneous property maps
31 ///\todo This file has the same name as the concept file in concept/,
32 /// and this is not easily detectable in docs...
41 /// Base class of maps.
43 /// Base class of maps.
44 /// It provides the necessary <tt>typedef</tt>s required by the map concept.
45 template<typename K, typename T>
54 /// Null map. (a.k.a. DoNothingMap)
56 /// If you have to provide a map only for its type definitions,
57 /// or if you have to provide a writable map, but
58 /// data written to it will sent to <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 template <typename K, typename V>
73 NullMap<K, V> nullMap() {
74 return NullMap<K, V>();
80 /// This is a readable map which assigns a specified value to each key.
81 /// In other aspects it is equivalent to the \ref NullMap.
82 /// \todo set could be used to set the value.
83 template<typename K, typename T>
84 class ConstMap : public MapBase<K, T> {
89 typedef MapBase<K, T> Parent;
90 typedef typename Parent::Key Key;
91 typedef typename Parent::Value Value;
93 /// Default constructor
95 /// The value of the map will be uninitialized.
96 /// (More exactly it will be default constructed.)
100 /// \param _v The initial value of the map.
102 ConstMap(const T &_v) : v(_v) {}
104 T operator[](const K&) const { return v; }
105 void set(const K&, const T&) {}
107 template<typename T1>
109 typedef ConstMap<K, T1> other;
112 template<typename T1>
113 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
116 ///Returns a \ref ConstMap class
118 ///This function just returns a \ref ConstMap class.
120 template<typename K, typename V>
121 inline ConstMap<K, V> constMap(const V &v) {
122 return ConstMap<K, V>(v);
126 //\todo to document later
127 template<typename T, T v>
130 //\todo to document later
131 template<typename K, typename V, V v>
132 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
134 typedef MapBase<K, V> Parent;
135 typedef typename Parent::Key Key;
136 typedef typename Parent::Value Value;
139 V operator[](const K&) const { return v; }
140 void set(const K&, const V&) { }
143 ///Returns a \ref ConstMap class
145 ///This function just returns a \ref ConstMap class.
147 template<typename K, typename V, V v>
148 inline ConstMap<K, Const<V, v> > constMap() {
149 return ConstMap<K, Const<V, v> >();
152 /// \c std::map wrapper
154 /// This is essentially a wrapper for \c std::map. With addition that
155 /// you can specify a default value different from \c Value() .
157 /// \todo Provide allocator parameter...
158 template <typename K, typename T, typename Compare = std::less<K> >
159 class StdMap : public std::map<K, T, Compare> {
160 typedef std::map<K, T, Compare> parent;
162 typedef typename parent::value_type PairType;
170 typedef T& Reference;
172 typedef const T& ConstReference;
176 /// Constructor with specified default value
177 StdMap(const T& _v) : v(_v) {}
179 /// \brief Constructs the map from an appropriate std::map.
181 /// \warning Inefficient: copies the content of \c m !
182 StdMap(const parent &m) : parent(m) {}
183 /// \brief Constructs the map from an appropriate std::map, and explicitly
184 /// specifies a default value.
186 /// \warning Inefficient: copies the content of \c m !
187 StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
189 template<typename T1, typename Comp1>
190 StdMap(const StdMap<Key, T1,Comp1> &m, const T &_v) {
194 Reference operator[](const Key &k) {
195 return insert(PairType(k,v)).first -> second;
198 ConstReference operator[](const Key &k) const {
199 typename parent::iterator i = lower_bound(k);
200 if (i == parent::end() || parent::key_comp()(k, (*i).first))
204 void set(const Key &k, const T &t) {
205 parent::operator[](k) = t;
208 /// Changes the default value of the map.
209 /// \return Returns the previous default value.
211 /// \warning The value of some keys (which has already been queried, but
212 /// the value has been unchanged from the default) may change!
213 T setDefault(const T &_v) { T old=v; v=_v; return old; }
215 template<typename T1>
217 typedef StdMap<Key, T1,Compare> other;
223 /// \addtogroup map_adaptors
226 /// \brief Identity mapping.
228 /// This mapping gives back the given key as value without any
230 template <typename T>
231 class IdentityMap : public MapBase<T, T> {
233 typedef MapBase<T, T> Parent;
234 typedef typename Parent::Key Key;
235 typedef typename Parent::Value Value;
237 const T& operator[](const T& t) const {
242 ///Returns an \ref IdentityMap class
244 ///This function just returns an \ref IdentityMap class.
245 ///\relates IdentityMap
247 inline IdentityMap<T> identityMap() {
248 return IdentityMap<T>();
252 ///Convert the \c Value of a map to another type.
254 ///This \ref concept::ReadMap "read only map"
255 ///converts the \c Value of a maps to type \c T.
256 ///Its \c Key is inherited from \c M.
257 template <typename M, typename T>
258 class ConvertMap : public MapBase<typename M::Key, T> {
261 typedef MapBase<typename M::Key, T> Parent;
262 typedef typename Parent::Key Key;
263 typedef typename Parent::Value Value;
268 ///\param _m is the underlying map
269 ConvertMap(const M &_m) : m(_m) {};
271 /// \brief The subscript operator.
273 /// The subscript operator.
275 /// \return The target of the edge
276 Value operator[](const Key& k) const {return m[k];}
279 ///Returns an \ref ConvertMap class
281 ///This function just returns an \ref ConvertMap class.
282 ///\relates ConvertMap
283 ///\todo The order of the template parameters are changed.
284 template<typename T, typename M>
285 inline ConvertMap<M, T> convertMap(const M &m) {
286 return ConvertMap<M, T>(m);
291 ///This \ref concept::ReadMap "read only map" returns the sum of the two
292 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
293 ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
295 template<typename M1, typename M2>
296 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
301 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
302 typedef typename Parent::Key Key;
303 typedef typename Parent::Value Value;
306 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
307 Value operator[](Key k) const {return m1[k]+m2[k];}
310 ///Returns an \ref AddMap class
312 ///This function just returns an \ref AddMap class.
313 ///\todo How to call these type of functions?
316 ///\todo Wrong scope in Doxygen when \c \\relates is used
317 template<typename M1, typename M2>
318 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
319 return AddMap<M1, M2>(m1,m2);
322 ///Shift a map with a constant.
324 ///This \ref concept::ReadMap "read only map" returns the sum of the
325 ///given map and a constant value.
326 ///Its \c Key and \c Value is inherited from \c M.
330 /// ShiftMap<X> sh(x,v);
332 ///is equivalent with
334 /// ConstMap<X::Key, X::Value> c_tmp(v);
335 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
337 template<typename M, typename C = typename M::Value>
338 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
342 typedef MapBase<typename M::Key, typename M::Value> Parent;
343 typedef typename Parent::Key Key;
344 typedef typename Parent::Value Value;
349 ///\param _m is the undelying map
350 ///\param _v is the shift value
351 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
352 Value operator[](Key k) const {return m[k] + v;}
355 ///Returns an \ref ShiftMap class
357 ///This function just returns an \ref ShiftMap class.
359 ///\todo A better name is required.
360 template<typename M, typename C>
361 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
362 return ShiftMap<M, C>(m,v);
365 ///Difference of two maps
367 ///This \ref concept::ReadMap "read only map" returns the difference
368 ///of the values of the two
369 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
370 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
372 template<typename M1, typename M2>
373 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
377 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
378 typedef typename Parent::Key Key;
379 typedef typename Parent::Value Value;
382 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
383 Value operator[](Key k) const {return m1[k]-m2[k];}
386 ///Returns a \ref SubMap class
388 ///This function just returns a \ref SubMap class.
391 template<typename M1, typename M2>
392 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
393 return SubMap<M1, M2>(m1, m2);
396 ///Product of two maps
398 ///This \ref concept::ReadMap "read only map" returns the product of the
401 ///maps. Its \c Key and \c Value will be inherited from \c M1.
402 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
404 template<typename M1, typename M2>
405 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
409 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
410 typedef typename Parent::Key Key;
411 typedef typename Parent::Value Value;
414 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
415 Value operator[](Key k) const {return m1[k]*m2[k];}
418 ///Returns a \ref MulMap class
420 ///This function just returns a \ref MulMap class.
422 template<typename M1, typename M2>
423 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
424 return MulMap<M1, M2>(m1,m2);
427 ///Scales a maps with a constant.
429 ///This \ref concept::ReadMap "read only map" returns the value of the
430 ///given map multiplied from the left side with a constant value.
431 ///Its \c Key and \c Value is inherited from \c M.
435 /// ScaleMap<X> sc(x,v);
437 ///is equivalent with
439 /// ConstMap<X::Key, X::Value> c_tmp(v);
440 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
442 template<typename M, typename C = typename M::Value>
443 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
447 typedef MapBase<typename M::Key, typename M::Value> Parent;
448 typedef typename Parent::Key Key;
449 typedef typename Parent::Value Value;
454 ///\param _m is the undelying map
455 ///\param _v is the scaling value
456 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
457 Value operator[](Key k) const {return v * m[k];}
460 ///Returns an \ref ScaleMap class
462 ///This function just returns an \ref ScaleMap class.
464 ///\todo A better name is required.
465 template<typename M, typename C>
466 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
467 return ScaleMap<M, C>(m,v);
470 ///Quotient of two maps
472 ///This \ref concept::ReadMap "read only map" returns the quotient of the
474 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
475 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
477 template<typename M1, typename M2>
478 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
482 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
483 typedef typename Parent::Key Key;
484 typedef typename Parent::Value Value;
487 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
488 Value operator[](Key k) const {return m1[k]/m2[k];}
491 ///Returns a \ref DivMap class
493 ///This function just returns a \ref DivMap class.
495 template<typename M1, typename M2>
496 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
497 return DivMap<M1, M2>(m1,m2);
500 ///Composition of two maps
502 ///This \ref concept::ReadMap "read only map" returns the composition of
504 ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
508 /// ComposeMap<M1, M2> cm(m1,m2);
510 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
512 ///Its \c Key is inherited from \c M2 and its \c Value is from
514 ///The \c M2::Value must be convertible to \c M1::Key.
515 ///\todo Check the requirements.
517 template <typename M1, typename M2>
518 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
522 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
523 typedef typename Parent::Key Key;
524 typedef typename Parent::Value Value;
527 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
529 typename MapTraits<M1>::ConstReturnValue
530 operator[](Key k) const {return m1[m2[k]];}
532 ///Returns a \ref ComposeMap class
534 ///This function just returns a \ref ComposeMap class.
536 ///\relates ComposeMap
537 template <typename M1, typename M2>
538 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
539 return ComposeMap<M1, M2>(m1,m2);
542 ///Combines of two maps using an STL (binary) functor.
544 ///Combines of two maps using an STL (binary) functor.
547 ///This \ref concept::ReadMap "read only map" takes two maps and a
548 ///binary functor and returns the composition of
550 ///given maps unsing the functor.
551 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
552 ///and \c f is of \c F,
555 /// CombineMap<M1, M2,F,V> cm(m1,m2,f);
557 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
559 ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
560 ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
561 ///input parameter of \c F and the return type of \c F must be convertible
563 ///\todo Check the requirements.
565 template<typename M1, typename M2, typename F,
566 typename V = typename F::result_type,
568 class CombineMap : public MapBase<typename M1::Key, V> {
573 typedef MapBase<typename M1::Key, V> Parent;
574 typedef typename Parent::Key Key;
575 typedef typename Parent::Value Value;
578 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
579 : m1(_m1), m2(_m2), f(_f) {};
580 Value operator[](Key k) const {return f(m1[k],m2[k]);}
583 ///Returns a \ref CombineMap class
585 ///This function just returns a \ref CombineMap class.
587 ///Only the first template parameter (the value type) must be given.
589 ///For example if \c m1 and \c m2 are both \c double valued maps, then
591 ///combineMap<double>(m1,m2,std::plus<double>)
593 ///is equivalent with
598 ///\relates CombineMap
599 template<typename M1, typename M2, typename F, typename V>
600 inline CombineMap<M1, M2, F, V>
601 combineMap(const M1& m1,const M2& m2, const F& f) {
602 return CombineMap<M1, M2, F, V>(m1,m2,f);
605 template<typename M1, typename M2, typename F>
606 inline CombineMap<M1, M2, F, typename F::result_type>
607 combineMap(const M1& m1, const M2& m2, const F& f) {
608 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
611 template<typename M1, typename M2, typename K1, typename K2, typename V>
612 inline CombineMap<M1, M2, V (*)(K1, K2), V>
613 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
614 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
617 ///Negative value of a map
619 ///This \ref concept::ReadMap "read only map" returns the negative
621 ///value returned by the
622 ///given map. Its \c Key and \c Value will be inherited from \c M.
623 ///The unary \c - operator must be defined for \c Value, of course.
626 class NegMap : public MapBase<typename M::Key, typename M::Value> {
629 typedef MapBase<typename M::Key, typename M::Value> Parent;
630 typedef typename Parent::Key Key;
631 typedef typename Parent::Value Value;
634 NegMap(const M &_m) : m(_m) {};
635 Value operator[](Key k) const {return -m[k];}
638 ///Returns a \ref NegMap class
640 ///This function just returns a \ref NegMap class.
642 template <typename M>
643 inline NegMap<M> negMap(const M &m) {
648 ///Absolute value of a map
650 ///This \ref concept::ReadMap "read only map" returns the absolute value
652 ///value returned by the
653 ///given map. Its \c Key and \c Value will be inherited
654 ///from <tt>M</tt>. <tt>Value</tt>
655 ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
656 ///operator must be defined for it, of course.
658 ///\bug We need a unified way to handle the situation below:
660 /// struct _UnConvertible {};
661 /// template<class A> inline A t_abs(A a) {return _UnConvertible();}
662 /// template<> inline int t_abs<>(int n) {return abs(n);}
663 /// template<> inline long int t_abs<>(long int n) {return labs(n);}
664 /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
665 /// template<> inline float t_abs<>(float n) {return fabsf(n);}
666 /// template<> inline double t_abs<>(double n) {return fabs(n);}
667 /// template<> inline long double t_abs<>(long double n) {return fabsl(n);}
672 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
675 typedef MapBase<typename M::Key, typename M::Value> Parent;
676 typedef typename Parent::Key Key;
677 typedef typename Parent::Value Value;
680 AbsMap(const M &_m) : m(_m) {};
681 Value operator[](Key k) const {
683 return tmp >= 0 ? tmp : -tmp;
688 ///Returns a \ref AbsMap class
690 ///This function just returns a \ref AbsMap class.
693 inline AbsMap<M> absMap(const M &m) {
697 ///Converts an STL style functor to a map
699 ///This \ref concept::ReadMap "read only map" returns the value
703 ///Template parameters \c K and \c V will become its
704 ///\c Key and \c Value. They must be given explicitely
705 ///because a functor does not provide such typedefs.
707 ///Parameter \c F is the type of the used functor.
711 typename K = typename F::argument_type,
712 typename V = typename F::result_type,
714 class FunctorMap : public MapBase<K, V> {
717 typedef MapBase<K, V> Parent;
718 typedef typename Parent::Key Key;
719 typedef typename Parent::Value Value;
722 FunctorMap(const F &_f) : f(_f) {}
724 Value operator[](Key k) const { return f(k);}
727 ///Returns a \ref FunctorMap class
729 ///This function just returns a \ref FunctorMap class.
731 ///The third template parameter isn't necessary to be given.
732 ///\relates FunctorMap
733 template<typename K, typename V, typename F> inline
734 FunctorMap<F, K, V> functorMap(const F &f) {
735 return FunctorMap<F, K, V>(f);
738 template <typename F> inline
739 FunctorMap<F, typename F::argument_type, typename F::result_type>
740 functorMap(const F &f) {
741 return FunctorMap<F, typename F::argument_type,
742 typename F::result_type>(f);
745 template <typename K, typename V> inline
746 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
747 return FunctorMap<V (*)(K), K, V>(f);
751 ///Converts a map to an STL style (unary) functor
753 ///This class Converts a map to an STL style (unary) functor.
754 ///that is it provides an <tt>operator()</tt> to read its values.
756 ///For the sake of convenience it also works as
757 ///a ususal \ref concept::ReadMap "readable map",
758 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
760 template <typename M>
761 class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
764 typedef MapBase<typename M::Key, typename M::Value> Parent;
765 typedef typename Parent::Key Key;
766 typedef typename Parent::Value Value;
769 typedef typename M::Key argument_type;
771 typedef typename M::Value result_type;
774 MapFunctor(const M &_m) : m(_m) {};
775 ///Returns a value of the map
776 Value operator()(Key k) const {return m[k];}
778 Value operator[](Key k) const {return m[k];}
781 ///Returns a \ref MapFunctor class
783 ///This function just returns a \ref MapFunctor class.
784 ///\relates MapFunctor
786 inline MapFunctor<M> mapFunctor(const M &m) {
787 return MapFunctor<M>(m);
791 ///Applies all map setting operations to two maps
793 ///This map has two \ref concept::WriteMap "writable map"
794 ///parameters and each write request will be passed to both of them.
795 ///If \c M1 is also \ref concept::ReadMap "readable",
796 ///then the read operations will return the
797 ///corresponding values of \c M1.
799 ///The \c Key and \c Value will be inherited from \c M1.
800 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
802 template<typename M1, typename M2>
803 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
807 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
808 typedef typename Parent::Key Key;
809 typedef typename Parent::Value Value;
812 ForkMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
813 Value operator[](Key k) const {return m1[k];}
814 // void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
817 ///Returns an \ref ForkMap class
819 ///This function just returns an \ref ForkMap class.
820 ///\todo How to call these type of functions?
823 ///\todo Wrong scope in Doxygen when \c \\relates is used
824 template <typename M1, typename M2>
825 inline ForkMap<M1, M2> forkMap(const M1 &m1,const M2 &m2) {
826 return ForkMap<M1, M2>(m1,m2);
831 /* ************* BOOL MAPS ******************* */
833 ///Logical 'not' of a map
835 ///This bool \ref concept::ReadMap "read only map" returns the
836 ///logical negation of
837 ///value returned by the
838 ///given map. Its \c Key and will be inherited from \c M,
839 ///its Value is <tt>bool</tt>.
841 template <typename M>
842 class NotMap : public MapBase<typename M::Key, bool> {
845 typedef MapBase<typename M::Key, bool> Parent;
846 typedef typename Parent::Key Key;
847 typedef typename Parent::Value Value;
850 NotMap(const M &_m) : m(_m) {};
851 Value operator[](Key k) const {return !m[k];}
854 ///Returns a \ref NotMap class
856 ///This function just returns a \ref NotMap class.
858 template <typename M>
859 inline NotMap<M> notMap(const M &m) {
863 /// \brief Writable bool map for store each true assigned elements.
865 /// Writable bool map for store each true assigned elements. It will
866 /// copies all the true setted keys to the given iterator.
868 /// \note The container of the iterator should contain for each element.
869 template <typename _Iterator>
872 typedef _Iterator Iterator;
874 typedef typename std::iterator_traits<Iterator>::value_type Key;
878 StoreBoolMap(Iterator it) : _begin(it), _end(it) {}
880 /// Gives back the given first setted iterator.
881 Iterator begin() const {
885 /// Gives back the iterator after the last setted.
886 Iterator end() const {
890 /// Setter function of the map
891 void set(const Key& key, Value value) {
898 Iterator _begin, _end;
901 /// \brief Writable bool map for store each true assigned elements in
902 /// a back insertable container.
904 /// Writable bool map for store each true assigned elements in a back
905 /// insertable container. It will push back all the true setted keys into
907 template <typename Container>
908 class BackInserterBoolMap {
910 typedef typename Container::value_type Key;
914 BackInserterBoolMap(Container& _container) : container(_container) {}
916 /// Setter function of the map
917 void set(const Key& key, Value value) {
919 container.push_back(key);
924 Container& container;
927 /// \brief Writable bool map for store each true assigned elements in
928 /// a front insertable container.
930 /// Writable bool map for store each true assigned elements in a front
931 /// insertable container. It will push front all the true setted keys into
933 template <typename Container>
934 class FrontInserterBoolMap {
936 typedef typename Container::value_type Key;
940 FrontInserterBoolMap(Container& _container) : container(_container) {}
942 /// Setter function of the map
943 void set(const Key& key, Value value) {
945 container.push_front(key);
950 Container& container;
953 /// \brief Writable bool map for store each true assigned elements in
954 /// an insertable container.
956 /// Writable bool map for store each true assigned elements in an
957 /// insertable container. It will insert all the true setted keys into
959 template <typename Container>
960 class InserterBoolMap {
962 typedef typename Container::value_type Key;
966 InserterBoolMap(Container& _container) : container(_container) {}
968 /// Setter function of the map
969 void set(const Key& key, Value value) {
971 container.insert(key);
976 Container& container;
979 /// \brief Fill the true setted elements with a given value.
981 /// Writable bool map for fill the true setted elements with a given value.
982 /// The value can be setted
984 template <typename Map>
987 typedef typename Map::Key Key;
991 FillBoolMap(Map& _map, const typename Map::Value& _fill)
992 : map(_map), fill(_fill) {}
995 FillBoolMap(Map& _map)
996 : map(_map), fill() {}
998 /// Gives back the current fill value
999 typename Map::Value fillValue() const {
1003 /// Sets the current fill value
1004 void fillValue(const typename Map::Value& _fill) {
1008 /// Setter function of the map
1009 void set(const Key& key, Value value) {
1017 typename Map::Value fill;
1021 /// \brief Writable bool map which stores for each true assigned elements
1022 /// the setting order number.
1024 /// Writable bool map which stores for each true assigned elements
1025 /// the setting order number.
1026 template <typename Map>
1027 class SettingOrderBoolMap {
1029 typedef typename Map::Key Key;
1033 SettingOrderBoolMap(Map& _map)
1034 : map(_map), counter(0) {}
1036 /// Number of setted keys.
1041 /// Setter function of the map
1042 void set(const Key& key, Value value) {
1044 map.set(key, counter++);
1056 #endif // LEMON_MAPS_H