/* -*- C++ -*- * * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2007 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #ifndef LEMON_MAPS_H #define LEMON_MAPS_H #include #include #include #include // #include ///\file ///\ingroup maps ///\brief Miscellaneous property maps /// #include namespace lemon { /// \addtogroup maps /// @{ /// Base class of maps. /// Base class of maps. /// It provides the necessary typedefs required by the map concept. template class MapBase { public: /// The key type of the map. typedef K Key; /// The value type of the map. (The type of objects associated with the keys). typedef T Value; }; /// Null map. (a.k.a. DoNothingMap) /// This map can be used if you have to provide a map only for /// its type definitions, or if you have to provide a writable map, /// but data written to it is not required (i.e. it will be sent to /// /dev/null). template class NullMap : public MapBase { public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; /// Gives back a default constructed element. T operator[](const K&) const { return T(); } /// Absorbs the value. void set(const K&, const T&) {} }; ///Returns a \c NullMap class ///This function just returns a \c NullMap class. ///\relates NullMap template NullMap nullMap() { return NullMap(); } /// Constant map. /// This is a readable map which assigns a specified value to each key. /// In other aspects it is equivalent to the \c NullMap. template class ConstMap : public MapBase { private: T v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; /// Default constructor /// Default constructor. /// The value of the map will be uninitialized. /// (More exactly it will be default constructed.) ConstMap() {} /// Constructor with specified initial value /// Constructor with specified initial value. /// \param _v is the initial value of the map. ConstMap(const T &_v) : v(_v) {} ///\e T operator[](const K&) const { return v; } ///\e void setAll(const T &t) { v = t; } template ConstMap(const ConstMap &, const T &_v) : v(_v) {} }; ///Returns a \c ConstMap class ///This function just returns a \c ConstMap class. ///\relates ConstMap template inline ConstMap constMap(const V &v) { return ConstMap(v); } template struct Const { }; /// Constant map with inlined constant value. /// This is a readable map which assigns a specified value to each key. /// In other aspects it is equivalent to the \c NullMap. template class ConstMap > : public MapBase { public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ConstMap() { } ///\e V operator[](const K&) const { return v; } ///\e void set(const K&, const V&) { } }; ///Returns a \c ConstMap class ///This function just returns a \c ConstMap class with inlined value. ///\relates ConstMap template inline ConstMap > constMap() { return ConstMap >(); } ///Map based on std::map ///This is essentially a wrapper for \c std::map with addition that ///you can specify a default value different from \c Value(). template > class StdMap : public MapBase { template friend class StdMap; public: typedef MapBase Parent; ///\e typedef typename Parent::Key Key; ///\e typedef typename Parent::Value Value; ///\e typedef T& Reference; ///\e typedef const T& ConstReference; typedef True ReferenceMapTag; private: typedef std::map Map; Value _value; Map _map; public: /// Constructor with specified default value StdMap(const T& value = T()) : _value(value) {} /// \brief Constructs the map from an appropriate std::map, and explicitly /// specifies a default value. template StdMap(const std::map &map, const T& value = T()) : _map(map.begin(), map.end()), _value(value) {} /// \brief Constructs a map from an other StdMap. template StdMap(const StdMap &c) : _map(c._map.begin(), c._map.end()), _value(c._value) {} private: StdMap& operator=(const StdMap&); public: ///\e Reference operator[](const Key &k) { typename Map::iterator it = _map.lower_bound(k); if (it != _map.end() && !_map.key_comp()(k, it->first)) return it->second; else return _map.insert(it, std::make_pair(k, _value))->second; } /// \e ConstReference operator[](const Key &k) const { typename Map::const_iterator it = _map.find(k); if (it != _map.end()) return it->second; else return _value; } /// \e void set(const Key &k, const T &t) { typename Map::iterator it = _map.lower_bound(k); if (it != _map.end() && !_map.key_comp()(k, it->first)) it->second = t; else _map.insert(it, std::make_pair(k, t)); } /// \e void setAll(const T &t) { _value = t; _map.clear(); } }; ///Returns a \ref StdMap class ///This function just returns a \ref StdMap class with specified ///default value. ///\relates StdMap template > inline StdMap stdMap(const V& value = V()) { return StdMap(value); } ///Returns a \ref StdMap class created from an appropriate std::map ///This function just returns a \ref StdMap class created from an ///appropriate std::map. ///\relates StdMap template > inline StdMap stdMap( const std::map &map, const V& value = V() ) { return StdMap(map, value); } /// \brief Map for storing values for keys from the range [0..size-1] /// /// The current map has the [0..size-1] keyset and the values /// are stored in a \c std::vector container. It can be used with /// some data structures, for example \c UnionFind, \c BinHeap, when /// the used items are small integer numbers. /// /// \todo Revise its name template class IntegerMap : public MapBase { template friend class IntegerMap; public: typedef MapBase Parent; ///\e typedef typename Parent::Key Key; ///\e typedef typename Parent::Value Value; ///\e typedef T& Reference; ///\e typedef const T& ConstReference; typedef True ReferenceMapTag; private: typedef std::vector Vector; Vector _vector; public: /// Constructor with specified default value IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {} /// \brief Constructs the map from an appropriate std::vector. template IntegerMap(const std::vector& vector) : _vector(vector.begin(), vector.end()) {} /// \brief Constructs a map from an other IntegerMap. template IntegerMap(const IntegerMap &c) : _vector(c._vector.begin(), c._vector.end()) {} /// \brief Resize the container void resize(int size, const T& value = T()) { _vector.resize(size, value); } private: IntegerMap& operator=(const IntegerMap&); public: ///\e Reference operator[](Key k) { return _vector[k]; } /// \e ConstReference operator[](Key k) const { return _vector[k]; } /// \e void set(const Key &k, const T& t) { _vector[k] = t; } }; ///Returns an \ref IntegerMap class ///This function just returns an \ref IntegerMap class. ///\relates IntegerMap template inline IntegerMap integerMap(int size = 0, const T& value = T()) { return IntegerMap(size, value); } /// @} /// \addtogroup map_adaptors /// @{ /// \brief Identity map. /// /// This map gives back the given key as value without any /// modification. template class IdentityMap : public MapBase { public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; /// \e const T& operator[](const T& t) const { return t; } }; ///Returns an \c IdentityMap class ///This function just returns an \c IdentityMap class. ///\relates IdentityMap template inline IdentityMap identityMap() { return IdentityMap(); } ///\brief Convert the \c Value of a map to another type using ///the default conversion. /// ///This \c concepts::ReadMap "read only map" ///converts the \c Value of a map to type \c T. ///Its \c Key is inherited from \c M. template class ConvertMap : public MapBase { const M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor ///Constructor. ///\param _m is the underlying map. ConvertMap(const M &_m) : m(_m) {}; /// \brief The subscript operator. /// /// The subscript operator. Value operator[](const Key& k) const {return m[k];} }; ///Returns a \c ConvertMap class ///This function just returns a \c ConvertMap class. ///\relates ConvertMap template inline ConvertMap convertMap(const M &m) { return ConvertMap(m); } ///Simple wrapping of a map ///This \ref concepts::ReadMap "read only map" returns the simple ///wrapping of the given map. Sometimes the reference maps cannot be ///combined with simple read maps. This map adaptor wraps the given ///map to simple read map. /// ///\sa SimpleWriteMap /// /// \todo Revise the misleading name template class SimpleMap : public MapBase { const M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor SimpleMap(const M &_m) : m(_m) {}; ///\e Value operator[](Key k) const {return m[k];} }; ///Returns a \ref SimpleMap class ///This function just returns a \ref SimpleMap class. ///\relates SimpleMap template inline SimpleMap simpleMap(const M &m) { return SimpleMap(m); } ///Simple writable wrapping of a map ///This \ref concepts::WriteMap "write map" returns the simple ///wrapping of the given map. Sometimes the reference maps cannot be ///combined with simple read-write maps. This map adaptor wraps the ///given map to simple read-write map. /// ///\sa SimpleMap /// /// \todo Revise the misleading name template class SimpleWriteMap : public MapBase { M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor SimpleWriteMap(M &_m) : m(_m) {}; ///\e Value operator[](Key k) const {return m[k];} ///\e void set(Key k, const Value& c) { m.set(k, c); } }; ///Returns a \ref SimpleWriteMap class ///This function just returns a \ref SimpleWriteMap class. ///\relates SimpleWriteMap template inline SimpleWriteMap simpleWriteMap(M &m) { return SimpleWriteMap(m); } ///Sum of two maps ///This \c concepts::ReadMap "read only map" returns the sum of the two ///given maps. ///Its \c Key and \c Value are inherited from \c M1. ///The \c Key and \c Value of M2 must be convertible to those of \c M1. template class AddMap : public MapBase { const M1& m1; const M2& m2; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; ///\e Value operator[](Key k) const {return m1[k]+m2[k];} }; ///Returns an \c AddMap class ///This function just returns an \c AddMap class. ///\todo How to call these type of functions? /// ///\relates AddMap template inline AddMap addMap(const M1 &m1,const M2 &m2) { return AddMap(m1,m2); } ///Shift a map with a constant. ///This \c concepts::ReadMap "read only map" returns the sum of the ///given map and a constant value. ///Its \c Key and \c Value are inherited from \c M. /// ///Actually, ///\code /// ShiftMap sh(x,v); ///\endcode ///is equivalent to ///\code /// ConstMap c_tmp(v); /// AddMap > sh(x,v); ///\endcode /// ///\sa ShiftWriteMap template class ShiftMap : public MapBase { const M& m; C v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor ///Constructor. ///\param _m is the undelying map. ///\param _v is the shift value. ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; ///\e Value operator[](Key k) const {return m[k] + v;} }; ///Shift a map with a constant (ReadWrite version). ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the ///given map and a constant value. It makes also possible to write the map. ///Its \c Key and \c Value are inherited from \c M. /// ///\sa ShiftMap template class ShiftWriteMap : public MapBase { M& m; C v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor ///Constructor. ///\param _m is the undelying map. ///\param _v is the shift value. ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {}; /// \e Value operator[](Key k) const {return m[k] + v;} /// \e void set(Key k, const Value& c) { m.set(k, c - v); } }; ///Returns a \c ShiftMap class ///This function just returns a \c ShiftMap class. ///\relates ShiftMap template inline ShiftMap shiftMap(const M &m,const C &v) { return ShiftMap(m,v); } ///Returns a \c ShiftWriteMap class ///This function just returns a \c ShiftWriteMap class. ///\relates ShiftWriteMap template inline ShiftWriteMap shiftMap(M &m,const C &v) { return ShiftWriteMap(m,v); } ///Difference of two maps ///This \c concepts::ReadMap "read only map" returns the difference ///of the values of the two given maps. ///Its \c Key and \c Value are inherited from \c M1. ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. /// /// \todo Revise the misleading name template class SubMap : public MapBase { const M1& m1; const M2& m2; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; /// \e Value operator[](Key k) const {return m1[k]-m2[k];} }; ///Returns a \c SubMap class ///This function just returns a \c SubMap class. /// ///\relates SubMap template inline SubMap subMap(const M1 &m1, const M2 &m2) { return SubMap(m1, m2); } ///Product of two maps ///This \c concepts::ReadMap "read only map" returns the product of the ///values of the two given maps. ///Its \c Key and \c Value are inherited from \c M1. ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. template class MulMap : public MapBase { const M1& m1; const M2& m2; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; /// \e Value operator[](Key k) const {return m1[k]*m2[k];} }; ///Returns a \c MulMap class ///This function just returns a \c MulMap class. ///\relates MulMap template inline MulMap mulMap(const M1 &m1,const M2 &m2) { return MulMap(m1,m2); } ///Scales a map with a constant. ///This \c concepts::ReadMap "read only map" returns the value of the ///given map multiplied from the left side with a constant value. ///Its \c Key and \c Value are inherited from \c M. /// ///Actually, ///\code /// ScaleMap sc(x,v); ///\endcode ///is equivalent to ///\code /// ConstMap c_tmp(v); /// MulMap > sc(x,v); ///\endcode /// ///\sa ScaleWriteMap template class ScaleMap : public MapBase { const M& m; C v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor ///Constructor. ///\param _m is the undelying map. ///\param _v is the scaling value. ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; /// \e Value operator[](Key k) const {return v * m[k];} }; ///Scales a map with a constant (ReadWrite version). ///This \c concepts::ReadWriteMap "read-write map" returns the value of the ///given map multiplied from the left side with a constant value. It can ///also be used as write map if the \c / operator is defined between ///\c Value and \c C and the given multiplier is not zero. ///Its \c Key and \c Value are inherited from \c M. /// ///\sa ScaleMap template class ScaleWriteMap : public MapBase { M& m; C v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor ///Constructor. ///\param _m is the undelying map. ///\param _v is the scaling value. ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {}; /// \e Value operator[](Key k) const {return v * m[k];} /// \e void set(Key k, const Value& c) { m.set(k, c / v);} }; ///Returns a \c ScaleMap class ///This function just returns a \c ScaleMap class. ///\relates ScaleMap template inline ScaleMap scaleMap(const M &m,const C &v) { return ScaleMap(m,v); } ///Returns a \c ScaleWriteMap class ///This function just returns a \c ScaleWriteMap class. ///\relates ScaleWriteMap template inline ScaleWriteMap scaleMap(M &m,const C &v) { return ScaleWriteMap(m,v); } ///Quotient of two maps ///This \c concepts::ReadMap "read only map" returns the quotient of the ///values of the two given maps. ///Its \c Key and \c Value are inherited from \c M1. ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. template class DivMap : public MapBase { const M1& m1; const M2& m2; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; /// \e Value operator[](Key k) const {return m1[k]/m2[k];} }; ///Returns a \c DivMap class ///This function just returns a \c DivMap class. ///\relates DivMap template inline DivMap divMap(const M1 &m1,const M2 &m2) { return DivMap(m1,m2); } ///Composition of two maps ///This \c concepts::ReadMap "read only map" returns the composition of ///two given maps. ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2, ///then for ///\code /// ComposeMap cm(m1,m2); ///\endcode /// cm[x] will be equal to m1[m2[x]]. /// ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1. ///\c M2::Value must be convertible to \c M1::Key. /// ///\sa CombineMap /// ///\todo Check the requirements. template class ComposeMap : public MapBase { const M1& m1; const M2& m2; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; /// \e /// \todo Use the MapTraits once it is ported. /// //typename MapTraits::ConstReturnValue typename M1::Value operator[](Key k) const {return m1[m2[k]];} }; ///Returns a \c ComposeMap class ///This function just returns a \c ComposeMap class. ///\relates ComposeMap template inline ComposeMap composeMap(const M1 &m1,const M2 &m2) { return ComposeMap(m1,m2); } ///Combine of two maps using an STL (binary) functor. ///Combine of two maps using an STL (binary) functor. /// ///This \c concepts::ReadMap "read only map" takes two maps and a ///binary functor and returns the composition of the two ///given maps unsing the functor. ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2 ///and \c f is of \c F, then for ///\code /// CombineMap cm(m1,m2,f); ///\endcode /// cm[x] will be equal to f(m1[x],m2[x]) /// ///Its \c Key is inherited from \c M1 and its \c Value is \c V. ///\c M2::Value and \c M1::Value must be convertible to the corresponding ///input parameter of \c F and the return type of \c F must be convertible ///to \c V. /// ///\sa ComposeMap /// ///\todo Check the requirements. template class CombineMap : public MapBase { const M1& m1; const M2& m2; F f; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F()) : m1(_m1), m2(_m2), f(_f) {}; /// \e Value operator[](Key k) const {return f(m1[k],m2[k]);} }; ///Returns a \c CombineMap class ///This function just returns a \c CombineMap class. /// ///For example if \c m1 and \c m2 are both \c double valued maps, then ///\code ///combineMap(m1,m2,std::plus()) ///\endcode ///is equivalent to ///\code ///addMap(m1,m2) ///\endcode /// ///This function is specialized for adaptable binary function ///classes and C++ functions. /// ///\relates CombineMap template inline CombineMap combineMap(const M1& m1,const M2& m2, const F& f) { return CombineMap(m1,m2,f); } template inline CombineMap combineMap(const M1& m1, const M2& m2, const F& f) { return combineMap(m1,m2,f); } template inline CombineMap combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { return combineMap(m1,m2,f); } ///Negative value of a map ///This \c concepts::ReadMap "read only map" returns the negative ///value of the value returned by the given map. ///Its \c Key and \c Value are inherited from \c M. ///The unary \c - operator must be defined for \c Value, of course. /// ///\sa NegWriteMap template class NegMap : public MapBase { const M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor NegMap(const M &_m) : m(_m) {}; /// \e Value operator[](Key k) const {return -m[k];} }; ///Negative value of a map (ReadWrite version) ///This \c concepts::ReadWriteMap "read-write map" returns the negative ///value of the value returned by the given map. ///Its \c Key and \c Value are inherited from \c M. ///The unary \c - operator must be defined for \c Value, of course. /// /// \sa NegMap template class NegWriteMap : public MapBase { M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor NegWriteMap(M &_m) : m(_m) {}; /// \e Value operator[](Key k) const {return -m[k];} /// \e void set(Key k, const Value& v) { m.set(k, -v); } }; ///Returns a \c NegMap class ///This function just returns a \c NegMap class. ///\relates NegMap template inline NegMap negMap(const M &m) { return NegMap(m); } ///Returns a \c NegWriteMap class ///This function just returns a \c NegWriteMap class. ///\relates NegWriteMap template inline NegWriteMap negMap(M &m) { return NegWriteMap(m); } ///Absolute value of a map ///This \c concepts::ReadMap "read only map" returns the absolute value ///of the value returned by the given map. ///Its \c Key and \c Value are inherited from \c M. ///\c Value must be comparable to \c 0 and the unary \c - ///operator must be defined for it, of course. template class AbsMap : public MapBase { const M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor AbsMap(const M &_m) : m(_m) {}; /// \e Value operator[](Key k) const { Value tmp = m[k]; return tmp >= 0 ? tmp : -tmp; } }; ///Returns an \c AbsMap class ///This function just returns an \c AbsMap class. ///\relates AbsMap template inline AbsMap absMap(const M &m) { return AbsMap(m); } ///Converts an STL style functor to a map ///This \c concepts::ReadMap "read only map" returns the value ///of a given functor. /// ///Template parameters \c K and \c V will become its ///\c Key and \c Value. ///In most cases they have to be given explicitly because a ///functor typically does not provide such typedefs. /// ///Parameter \c F is the type of the used functor. /// ///\sa MapFunctor template class FunctorMap : public MapBase { F f; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor FunctorMap(const F &_f = F()) : f(_f) {} /// \e Value operator[](Key k) const { return f(k);} }; ///Returns a \c FunctorMap class ///This function just returns a \c FunctorMap class. /// ///It is specialized for adaptable function classes and ///C++ functions. ///\relates FunctorMap template inline FunctorMap functorMap(const F &f) { return FunctorMap(f); } template inline FunctorMap functorMap(const F &f) { return FunctorMap(f); } template inline FunctorMap functorMap(V (*f)(K)) { return FunctorMap(f); } ///Converts a map to an STL style (unary) functor ///This class Converts a map to an STL style (unary) functor. ///that is it provides an operator() to read its values. /// ///For the sake of convenience it also works as ///a ususal \c concepts::ReadMap "readable map", ///i.e. operator[] and the \c Key and \c Value typedefs also exist. /// ///\sa FunctorMap template class MapFunctor : public MapBase { const M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; typedef typename M::Key argument_type; typedef typename M::Value result_type; ///Constructor MapFunctor(const M &_m) : m(_m) {}; ///\e Value operator()(Key k) const {return m[k];} ///\e Value operator[](Key k) const {return m[k];} }; ///Returns a \c MapFunctor class ///This function just returns a \c MapFunctor class. ///\relates MapFunctor template inline MapFunctor mapFunctor(const M &m) { return MapFunctor(m); } ///Applies all map setting operations to two maps ///This map has two \c concepts::ReadMap "readable map" ///parameters and each read request will be passed just to the ///first map. This class is the just readable map type of the ForkWriteMap. /// ///The \c Key and \c Value are inherited from \c M1. ///The \c Key and \c Value of M2 must be convertible from those of \c M1. /// ///\sa ForkWriteMap /// /// \todo Why is it needed? template class ForkMap : public MapBase { const M1& m1; const M2& m2; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {}; /// \e Value operator[](Key k) const {return m1[k];} }; ///Applies all map setting operations to two maps ///This map has two \c concepts::WriteMap "writable map" ///parameters and each write request will be passed to both of them. ///If \c M1 is also \c concepts::ReadMap "readable", ///then the read operations will return the ///corresponding values of \c M1. /// ///The \c Key and \c Value are inherited from \c M1. ///The \c Key and \c Value of M2 must be convertible from those of \c M1. /// ///\sa ForkMap template class ForkWriteMap : public MapBase { M1& m1; M2& m2; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; ///Constructor ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {}; ///\e Value operator[](Key k) const {return m1[k];} ///\e void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);} }; ///Returns a \c ForkMap class ///This function just returns a \c ForkMap class. ///\relates ForkMap template inline ForkMap forkMap(const M1 &m1, const M2 &m2) { return ForkMap(m1,m2); } ///Returns a \c ForkWriteMap class ///This function just returns a \c ForkWriteMap class. ///\relates ForkWriteMap template inline ForkWriteMap forkMap(M1 &m1, M2 &m2) { return ForkWriteMap(m1,m2); } /* ************* BOOL MAPS ******************* */ ///Logical 'not' of a map ///This bool \c concepts::ReadMap "read only map" returns the ///logical negation of the value returned by the given map. ///Its \c Key is inherited from \c M, its Value is \c bool. /// ///\sa NotWriteMap template class NotMap : public MapBase { const M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; /// Constructor NotMap(const M &_m) : m(_m) {}; ///\e Value operator[](Key k) const {return !m[k];} }; ///Logical 'not' of a map (ReadWrie version) ///This bool \c concepts::ReadWriteMap "read-write map" returns the ///logical negation of the value returned by the given map. When it is set, ///the opposite value is set to the original map. ///Its \c Key is inherited from \c M, its Value is \c bool. /// ///\sa NotMap template class NotWriteMap : public MapBase { M& m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; /// Constructor NotWriteMap(M &_m) : m(_m) {}; ///\e Value operator[](Key k) const {return !m[k];} ///\e void set(Key k, bool v) { m.set(k, !v); } }; ///Returns a \c NotMap class ///This function just returns a \c NotMap class. ///\relates NotMap template inline NotMap notMap(const M &m) { return NotMap(m); } ///Returns a \c NotWriteMap class ///This function just returns a \c NotWriteMap class. ///\relates NotWriteMap template inline NotWriteMap notMap(M &m) { return NotWriteMap(m); } namespace _maps_bits { template struct Identity { typedef Value argument_type; typedef Value result_type; Value operator()(const Value& val) const { return val; } }; template struct IteratorTraits { typedef typename std::iterator_traits<_Iterator>::value_type Value; }; template struct IteratorTraits<_Iterator, typename exists::type> { typedef typename _Iterator::container_type::value_type Value; }; } /// \brief Writable bool map for logging each \c true assigned element /// /// Writable bool map for logging each \c true assigned element, i.e it /// copies all the keys set to \c true to the given iterator. /// /// \note The container of the iterator should contain space /// for each element. /// /// The following example shows how you can write the edges found by the Prim /// algorithm directly /// to the standard output. ///\code /// typedef IdMap EdgeIdMap; /// EdgeIdMap edgeId(graph); /// /// typedef MapFunctor EdgeIdFunctor; /// EdgeIdFunctor edgeIdFunctor(edgeId); /// /// StoreBoolMap, EdgeIdFunctor> /// writerMap(ostream_iterator(cout, " "), edgeIdFunctor); /// /// prim(graph, cost, writerMap); ///\endcode /// ///\sa BackInserterBoolMap ///\sa FrontInserterBoolMap ///\sa InserterBoolMap /// ///\todo Revise the name of this class and the related ones. template ::Value> > class StoreBoolMap { public: typedef _Iterator Iterator; typedef typename _Functor::argument_type Key; typedef bool Value; typedef _Functor Functor; /// Constructor StoreBoolMap(Iterator it, const Functor& functor = Functor()) : _begin(it), _end(it), _functor(functor) {} /// Gives back the given iterator set for the first key Iterator begin() const { return _begin; } /// Gives back the the 'after the last' iterator Iterator end() const { return _end; } /// The \c set function of the map void set(const Key& key, Value value) const { if (value) { *_end++ = _functor(key); } } private: Iterator _begin; mutable Iterator _end; Functor _functor; }; /// \brief Writable bool map for logging each \c true assigned element in /// a back insertable container. /// /// Writable bool map for logging each \c true assigned element by pushing /// them into a back insertable container. /// It can be used to retrieve the items into a standard /// container. The next example shows how you can store the /// edges found by the Prim algorithm in a vector. /// ///\code /// vector span_tree_edges; /// BackInserterBoolMap > inserter_map(span_tree_edges); /// prim(graph, cost, inserter_map); ///\endcode /// ///\sa StoreBoolMap ///\sa FrontInserterBoolMap ///\sa InserterBoolMap template > class BackInserterBoolMap { public: typedef typename Functor::argument_type Key; typedef bool Value; /// Constructor BackInserterBoolMap(Container& _container, const Functor& _functor = Functor()) : container(_container), functor(_functor) {} /// The \c set function of the map void set(const Key& key, Value value) { if (value) { container.push_back(functor(key)); } } private: Container& container; Functor functor; }; /// \brief Writable bool map for logging each \c true assigned element in /// a front insertable container. /// /// Writable bool map for logging each \c true assigned element by pushing /// them into a front insertable container. /// It can be used to retrieve the items into a standard /// container. For example see \ref BackInserterBoolMap. /// ///\sa BackInserterBoolMap ///\sa InserterBoolMap template > class FrontInserterBoolMap { public: typedef typename Functor::argument_type Key; typedef bool Value; /// Constructor FrontInserterBoolMap(Container& _container, const Functor& _functor = Functor()) : container(_container), functor(_functor) {} /// The \c set function of the map void set(const Key& key, Value value) { if (value) { container.push_front(functor(key)); } } private: Container& container; Functor functor; }; /// \brief Writable bool map for storing each \c true assigned element in /// an insertable container. /// /// Writable bool map for storing each \c true assigned element in an /// insertable container. It will insert all the keys set to \c true into /// the container. /// /// For example, if you want to store the cut arcs of the strongly /// connected components in a set you can use the next code: /// ///\code /// set cut_arcs; /// InserterBoolMap > inserter_map(cut_arcs); /// stronglyConnectedCutArcs(digraph, cost, inserter_map); ///\endcode /// ///\sa BackInserterBoolMap ///\sa FrontInserterBoolMap template > class InserterBoolMap { public: typedef typename Container::value_type Key; typedef bool Value; /// Constructor with specified iterator /// Constructor with specified iterator. /// \param _container The container for storing the elements. /// \param _it The elements will be inserted before this iterator. /// \param _functor The functor that is used when an element is stored. InserterBoolMap(Container& _container, typename Container::iterator _it, const Functor& _functor = Functor()) : container(_container), it(_it), functor(_functor) {} /// Constructor /// Constructor without specified iterator. /// The elements will be inserted before _container.end(). /// \param _container The container for storing the elements. /// \param _functor The functor that is used when an element is stored. InserterBoolMap(Container& _container, const Functor& _functor = Functor()) : container(_container), it(_container.end()), functor(_functor) {} /// The \c set function of the map void set(const Key& key, Value value) { if (value) { it = container.insert(it, functor(key)); ++it; } } private: Container& container; typename Container::iterator it; Functor functor; }; /// \brief Writable bool map for filling each \c true assigned element with a /// given value. /// /// Writable bool map for filling each \c true assigned element with a /// given value. The value can set the container. /// /// The following code finds the connected components of a graph /// and stores it in the \c comp map: ///\code /// typedef Graph::NodeMap ComponentMap; /// ComponentMap comp(graph); /// typedef FillBoolMap > ComponentFillerMap; /// ComponentFillerMap filler(comp, 0); /// /// Dfs::DefProcessedMap::Create dfs(graph); /// dfs.processedMap(filler); /// dfs.init(); /// for (NodeIt it(graph); it != INVALID; ++it) { /// if (!dfs.reached(it)) { /// dfs.addSource(it); /// dfs.start(); /// ++filler.fillValue(); /// } /// } ///\endcode template class FillBoolMap { public: typedef typename Map::Key Key; typedef bool Value; /// Constructor FillBoolMap(Map& _map, const typename Map::Value& _fill) : map(_map), fill(_fill) {} /// Constructor FillBoolMap(Map& _map) : map(_map), fill() {} /// Gives back the current fill value const typename Map::Value& fillValue() const { return fill; } /// Gives back the current fill value typename Map::Value& fillValue() { return fill; } /// Sets the current fill value void fillValue(const typename Map::Value& _fill) { fill = _fill; } /// The \c set function of the map void set(const Key& key, Value value) { if (value) { map.set(key, fill); } } private: Map& map; typename Map::Value fill; }; /// \brief Writable bool map for storing the sequence number of /// \c true assignments. /// /// Writable bool map that stores for each \c true assigned elements /// the sequence number of this setting. /// It makes it easy to calculate the leaving /// order of the nodes in the \c Dfs algorithm. /// ///\code /// typedef Digraph::NodeMap OrderMap; /// OrderMap order(digraph); /// typedef SettingOrderBoolMap OrderSetterMap; /// OrderSetterMap setter(order); /// Dfs::DefProcessedMap::Create dfs(digraph); /// dfs.processedMap(setter); /// dfs.init(); /// for (NodeIt it(digraph); it != INVALID; ++it) { /// if (!dfs.reached(it)) { /// dfs.addSource(it); /// dfs.start(); /// } /// } ///\endcode /// /// The storing of the discovering order is more difficult because the /// ReachedMap should be readable in the dfs algorithm but the setting /// order map is not readable. Thus we must use the fork map: /// ///\code /// typedef Digraph::NodeMap OrderMap; /// OrderMap order(digraph); /// typedef SettingOrderBoolMap OrderSetterMap; /// OrderSetterMap setter(order); /// typedef Digraph::NodeMap StoreMap; /// StoreMap store(digraph); /// /// typedef ForkWriteMap ReachedMap; /// ReachedMap reached(store, setter); /// /// Dfs::DefReachedMap::Create dfs(digraph); /// dfs.reachedMap(reached); /// dfs.init(); /// for (NodeIt it(digraph); it != INVALID; ++it) { /// if (!dfs.reached(it)) { /// dfs.addSource(it); /// dfs.start(); /// } /// } ///\endcode template class SettingOrderBoolMap { public: typedef typename Map::Key Key; typedef bool Value; /// Constructor SettingOrderBoolMap(Map& _map) : map(_map), counter(0) {} /// Number of set operations. int num() const { return counter; } /// The \c set function of the map void set(const Key& key, Value value) { if (value) { map.set(key, counter++); } } private: Map& map; int counter; }; /// @} } #endif // LEMON_MAPS_H