alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@25: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@25: * alpar@440: * Copyright (C) 2003-2009 alpar@25: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@25: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@25: * alpar@25: * Permission to use, modify and distribute this software is granted alpar@25: * provided that this copyright notice appears in all copies. For alpar@25: * precise terms see the accompanying LICENSE file. alpar@25: * alpar@25: * This software is provided "AS IS" with no warranty of any kind, alpar@25: * express or implied, and with no claim as to its suitability for any alpar@25: * purpose. alpar@25: * alpar@25: */ alpar@25: alpar@25: #ifndef LEMON_MAPS_H alpar@25: #define LEMON_MAPS_H alpar@25: alpar@25: #include alpar@25: #include alpar@25: #include alpar@25: deba@220: #include alpar@25: alpar@25: ///\file alpar@25: ///\ingroup maps alpar@25: ///\brief Miscellaneous property maps kpeter@80: alpar@25: #include alpar@25: alpar@25: namespace lemon { alpar@25: alpar@25: /// \addtogroup maps alpar@25: /// @{ alpar@25: alpar@25: /// Base class of maps. alpar@25: kpeter@80: /// Base class of maps. It provides the necessary type definitions kpeter@80: /// required by the map %concepts. kpeter@80: template alpar@25: class MapBase { alpar@25: public: kpeter@313: /// \brief The key type of the map. alpar@25: typedef K Key; kpeter@80: /// \brief The value type of the map. kpeter@80: /// (The type of objects associated with the keys). kpeter@80: typedef V Value; alpar@25: }; alpar@25: kpeter@80: alpar@25: /// Null map. (a.k.a. DoNothingMap) alpar@25: kpeter@29: /// This map can be used if you have to provide a map only for kpeter@80: /// its type definitions, or if you have to provide a writable map, kpeter@80: /// but data written to it is not required (i.e. it will be sent to kpeter@29: /// /dev/null). kpeter@80: /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept. kpeter@80: /// kpeter@80: /// \sa ConstMap kpeter@80: template kpeter@80: class NullMap : public MapBase { alpar@25: public: kpeter@550: ///\e kpeter@550: typedef K Key; kpeter@550: ///\e kpeter@550: typedef V Value; kpeter@80: alpar@25: /// Gives back a default constructed element. kpeter@80: Value operator[](const Key&) const { return Value(); } alpar@25: /// Absorbs the value. kpeter@80: void set(const Key&, const Value&) {} alpar@25: }; alpar@25: kpeter@301: /// Returns a \c NullMap class kpeter@301: kpeter@301: /// This function just returns a \c NullMap class. kpeter@80: /// \relates NullMap kpeter@80: template alpar@25: NullMap nullMap() { alpar@25: return NullMap(); alpar@25: } alpar@25: alpar@25: alpar@25: /// Constant map. alpar@25: kpeter@82: /// This \ref concepts::ReadMap "readable map" assigns a specified kpeter@82: /// value to each key. kpeter@80: /// kpeter@301: /// In other aspects it is equivalent to \c NullMap. kpeter@80: /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" kpeter@80: /// concept, but it absorbs the data written to it. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the constMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa NullMap kpeter@80: /// \sa IdentityMap kpeter@80: template kpeter@80: class ConstMap : public MapBase { alpar@25: private: kpeter@80: V _value; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef K Key; kpeter@550: ///\e kpeter@550: typedef V Value; alpar@25: alpar@25: /// Default constructor alpar@25: kpeter@29: /// Default constructor. kpeter@80: /// The value of the map will be default constructed. alpar@25: ConstMap() {} kpeter@80: kpeter@29: /// Constructor with specified initial value alpar@25: kpeter@29: /// Constructor with specified initial value. kpeter@123: /// \param v The initial value of the map. kpeter@80: ConstMap(const Value &v) : _value(v) {} alpar@25: kpeter@80: /// Gives back the specified value. kpeter@80: Value operator[](const Key&) const { return _value; } alpar@25: kpeter@80: /// Absorbs the value. kpeter@80: void set(const Key&, const Value&) {} kpeter@80: kpeter@80: /// Sets the value that is assigned to each key. kpeter@80: void setAll(const Value &v) { kpeter@80: _value = v; kpeter@80: } kpeter@80: kpeter@80: template kpeter@80: ConstMap(const ConstMap &, const Value &v) : _value(v) {} alpar@25: }; alpar@25: kpeter@301: /// Returns a \c ConstMap class kpeter@301: kpeter@301: /// This function just returns a \c ConstMap class. kpeter@80: /// \relates ConstMap kpeter@80: template alpar@25: inline ConstMap constMap(const V &v) { alpar@25: return ConstMap(v); alpar@25: } alpar@25: kpeter@123: template kpeter@123: inline ConstMap constMap() { kpeter@123: return ConstMap(); kpeter@123: } kpeter@123: alpar@25: alpar@25: template kpeter@80: struct Const {}; alpar@25: alpar@25: /// Constant map with inlined constant value. alpar@25: kpeter@82: /// This \ref concepts::ReadMap "readable map" assigns a specified kpeter@82: /// value to each key. kpeter@80: /// kpeter@301: /// In other aspects it is equivalent to \c NullMap. kpeter@80: /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" kpeter@80: /// concept, but it absorbs the data written to it. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the constMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa NullMap kpeter@80: /// \sa IdentityMap alpar@25: template alpar@25: class ConstMap > : public MapBase { alpar@25: public: kpeter@550: ///\e kpeter@550: typedef K Key; kpeter@550: ///\e kpeter@550: typedef V Value; alpar@25: kpeter@80: /// Constructor. kpeter@80: ConstMap() {} kpeter@80: kpeter@80: /// Gives back the specified value. kpeter@80: Value operator[](const Key&) const { return v; } kpeter@80: kpeter@80: /// Absorbs the value. kpeter@80: void set(const Key&, const Value&) {} alpar@25: }; alpar@25: kpeter@301: /// Returns a \c ConstMap class with inlined constant value kpeter@301: kpeter@301: /// This function just returns a \c ConstMap class with inlined kpeter@80: /// constant value. kpeter@80: /// \relates ConstMap kpeter@80: template alpar@25: inline ConstMap > constMap() { alpar@25: return ConstMap >(); alpar@25: } alpar@25: alpar@25: kpeter@82: /// Identity map. kpeter@82: kpeter@82: /// This \ref concepts::ReadMap "read-only map" gives back the given kpeter@82: /// key as value without any modification. kpeter@80: /// kpeter@80: /// \sa ConstMap kpeter@80: template kpeter@80: class IdentityMap : public MapBase { kpeter@80: public: kpeter@550: ///\e kpeter@550: typedef T Key; kpeter@550: ///\e kpeter@550: typedef T Value; kpeter@80: kpeter@80: /// Gives back the given value without any modification. kpeter@82: Value operator[](const Key &k) const { kpeter@82: return k; kpeter@80: } kpeter@80: }; kpeter@80: kpeter@301: /// Returns an \c IdentityMap class kpeter@301: kpeter@301: /// This function just returns an \c IdentityMap class. kpeter@80: /// \relates IdentityMap kpeter@80: template kpeter@80: inline IdentityMap identityMap() { kpeter@80: return IdentityMap(); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// \brief Map for storing values for integer keys from the range kpeter@80: /// [0..size-1]. kpeter@80: /// kpeter@80: /// This map is essentially a wrapper for \c std::vector. It assigns kpeter@80: /// values to integer keys from the range [0..size-1]. kpeter@80: /// It can be used with some data structures, for example kpeter@301: /// \c UnionFind, \c BinHeap, when the used items are small kpeter@80: /// integers. This map conforms the \ref concepts::ReferenceMap kpeter@80: /// "ReferenceMap" concept. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the rangeMap() kpeter@80: /// function. kpeter@80: template kpeter@80: class RangeMap : public MapBase { kpeter@80: template kpeter@80: friend class RangeMap; kpeter@80: private: kpeter@80: kpeter@80: typedef std::vector Vector; kpeter@80: Vector _vector; kpeter@80: alpar@25: public: alpar@25: kpeter@80: /// Key type kpeter@550: typedef int Key; kpeter@80: /// Value type kpeter@550: typedef V Value; kpeter@80: /// Reference type kpeter@80: typedef typename Vector::reference Reference; kpeter@80: /// Const reference type kpeter@80: typedef typename Vector::const_reference ConstReference; kpeter@80: kpeter@80: typedef True ReferenceMapTag; kpeter@80: kpeter@80: public: kpeter@80: kpeter@80: /// Constructor with specified default value. kpeter@80: RangeMap(int size = 0, const Value &value = Value()) kpeter@80: : _vector(size, value) {} kpeter@80: kpeter@80: /// Constructs the map from an appropriate \c std::vector. kpeter@80: template kpeter@80: RangeMap(const std::vector& vector) kpeter@80: : _vector(vector.begin(), vector.end()) {} kpeter@80: kpeter@301: /// Constructs the map from another \c RangeMap. kpeter@80: template kpeter@80: RangeMap(const RangeMap &c) kpeter@80: : _vector(c._vector.begin(), c._vector.end()) {} kpeter@80: kpeter@80: /// Returns the size of the map. kpeter@80: int size() { kpeter@80: return _vector.size(); kpeter@80: } kpeter@80: kpeter@80: /// Resizes the map. kpeter@80: kpeter@80: /// Resizes the underlying \c std::vector container, so changes the kpeter@80: /// keyset of the map. kpeter@80: /// \param size The new size of the map. The new keyset will be the kpeter@80: /// range [0..size-1]. kpeter@80: /// \param value The default value to assign to the new keys. kpeter@80: void resize(int size, const Value &value = Value()) { kpeter@80: _vector.resize(size, value); kpeter@80: } kpeter@80: kpeter@80: private: kpeter@80: kpeter@80: RangeMap& operator=(const RangeMap&); kpeter@80: kpeter@80: public: kpeter@80: kpeter@80: ///\e kpeter@80: Reference operator[](const Key &k) { kpeter@80: return _vector[k]; kpeter@80: } kpeter@80: kpeter@80: ///\e kpeter@80: ConstReference operator[](const Key &k) const { kpeter@80: return _vector[k]; kpeter@80: } kpeter@80: kpeter@80: ///\e kpeter@80: void set(const Key &k, const Value &v) { kpeter@80: _vector[k] = v; kpeter@80: } kpeter@80: }; kpeter@80: kpeter@301: /// Returns a \c RangeMap class kpeter@301: kpeter@301: /// This function just returns a \c RangeMap class. kpeter@80: /// \relates RangeMap kpeter@80: template kpeter@80: inline RangeMap rangeMap(int size = 0, const V &value = V()) { kpeter@80: return RangeMap(size, value); kpeter@80: } kpeter@80: kpeter@301: /// \brief Returns a \c RangeMap class created from an appropriate kpeter@80: /// \c std::vector kpeter@80: kpeter@301: /// This function just returns a \c RangeMap class created from an kpeter@80: /// appropriate \c std::vector. kpeter@80: /// \relates RangeMap kpeter@80: template kpeter@80: inline RangeMap rangeMap(const std::vector &vector) { kpeter@80: return RangeMap(vector); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// Map type based on \c std::map kpeter@80: kpeter@80: /// This map is essentially a wrapper for \c std::map with addition kpeter@80: /// that you can specify a default value for the keys that are not kpeter@80: /// stored actually. This value can be different from the default kpeter@80: /// contructed value (i.e. \c %Value()). kpeter@80: /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap" kpeter@80: /// concept. kpeter@80: /// kpeter@80: /// This map is useful if a default value should be assigned to most of kpeter@80: /// the keys and different values should be assigned only to a few kpeter@80: /// keys (i.e. the map is "sparse"). kpeter@80: /// The name of this type also refers to this important usage. kpeter@80: /// kpeter@80: /// Apart form that this map can be used in many other cases since it kpeter@80: /// is based on \c std::map, which is a general associative container. kpeter@80: /// However keep in mind that it is usually not as efficient as other kpeter@80: /// maps. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the sparseMap() kpeter@80: /// function. kpeter@550: template > kpeter@80: class SparseMap : public MapBase { kpeter@80: template kpeter@80: friend class SparseMap; kpeter@80: public: kpeter@80: kpeter@80: /// Key type kpeter@550: typedef K Key; kpeter@80: /// Value type kpeter@550: typedef V Value; kpeter@80: /// Reference type kpeter@80: typedef Value& Reference; kpeter@80: /// Const reference type kpeter@80: typedef const Value& ConstReference; alpar@25: kpeter@45: typedef True ReferenceMapTag; kpeter@45: alpar@25: private: kpeter@80: kpeter@550: typedef std::map Map; kpeter@80: Map _map; alpar@25: Value _value; alpar@25: alpar@25: public: alpar@25: kpeter@80: /// \brief Constructor with specified default value. kpeter@80: SparseMap(const Value &value = Value()) : _value(value) {} kpeter@80: /// \brief Constructs the map from an appropriate \c std::map, and kpeter@47: /// explicitly specifies a default value. kpeter@80: template kpeter@80: SparseMap(const std::map &map, kpeter@80: const Value &value = Value()) alpar@25: : _map(map.begin(), map.end()), _value(value) {} kpeter@80: kpeter@301: /// \brief Constructs the map from another \c SparseMap. kpeter@80: template kpeter@80: SparseMap(const SparseMap &c) alpar@25: : _map(c._map.begin(), c._map.end()), _value(c._value) {} alpar@25: alpar@25: private: alpar@25: kpeter@80: SparseMap& operator=(const SparseMap&); alpar@25: alpar@25: public: alpar@25: alpar@25: ///\e alpar@25: Reference operator[](const Key &k) { alpar@25: typename Map::iterator it = _map.lower_bound(k); alpar@25: if (it != _map.end() && !_map.key_comp()(k, it->first)) alpar@209: return it->second; alpar@25: else alpar@209: return _map.insert(it, std::make_pair(k, _value))->second; alpar@25: } alpar@25: kpeter@80: ///\e alpar@25: ConstReference operator[](const Key &k) const { alpar@25: typename Map::const_iterator it = _map.find(k); alpar@25: if (it != _map.end()) alpar@209: return it->second; alpar@25: else alpar@209: return _value; alpar@25: } alpar@25: kpeter@80: ///\e kpeter@80: void set(const Key &k, const Value &v) { alpar@25: typename Map::iterator it = _map.lower_bound(k); alpar@25: if (it != _map.end() && !_map.key_comp()(k, it->first)) alpar@209: it->second = v; alpar@25: else alpar@209: _map.insert(it, std::make_pair(k, v)); alpar@25: } alpar@25: kpeter@80: ///\e kpeter@80: void setAll(const Value &v) { kpeter@80: _value = v; alpar@25: _map.clear(); kpeter@80: } kpeter@80: }; alpar@25: kpeter@301: /// Returns a \c SparseMap class kpeter@301: kpeter@301: /// This function just returns a \c SparseMap class with specified kpeter@80: /// default value. kpeter@80: /// \relates SparseMap kpeter@80: template kpeter@80: inline SparseMap sparseMap(const V& value = V()) { kpeter@80: return SparseMap(value); kpeter@54: } kpeter@45: kpeter@80: template kpeter@80: inline SparseMap > sparseMap(const V& value = V()) { kpeter@80: return SparseMap >(value); kpeter@45: } alpar@25: kpeter@301: /// \brief Returns a \c SparseMap class created from an appropriate kpeter@80: /// \c std::map alpar@25: kpeter@301: /// This function just returns a \c SparseMap class created from an kpeter@80: /// appropriate \c std::map. kpeter@80: /// \relates SparseMap kpeter@80: template kpeter@80: inline SparseMap kpeter@80: sparseMap(const std::map &map, const V& value = V()) kpeter@80: { kpeter@80: return SparseMap(map, value); kpeter@45: } alpar@25: alpar@25: /// @} alpar@25: alpar@25: /// \addtogroup map_adaptors alpar@25: /// @{ alpar@25: kpeter@80: /// Composition of two maps kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the kpeter@80: /// composition of two given maps. That is to say, if \c m1 is of kpeter@80: /// type \c M1 and \c m2 is of \c M2, then for kpeter@80: /// \code kpeter@80: /// ComposeMap cm(m1,m2); kpeter@80: /// \endcode kpeter@80: /// cm[x] will be equal to m1[m2[x]]. alpar@25: /// kpeter@80: /// The \c Key type of the map is inherited from \c M2 and the kpeter@80: /// \c Value type is from \c M1. kpeter@80: /// \c M2::Value must be convertible to \c M1::Key. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the composeMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa CombineMap kpeter@80: template kpeter@80: class ComposeMap : public MapBase { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M2::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M1::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@80: kpeter@550: ///\e kpeter@80: typename MapTraits::ConstReturnValue kpeter@80: operator[](const Key &k) const { return _m1[_m2[k]]; } alpar@25: }; alpar@25: kpeter@301: /// Returns a \c ComposeMap class kpeter@301: kpeter@301: /// This function just returns a \c ComposeMap class. kpeter@80: /// kpeter@80: /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is kpeter@80: /// convertible to the \c Key of \c m1, then composeMap(m1,m2)[x] kpeter@80: /// will be equal to m1[m2[x]]. kpeter@80: /// kpeter@80: /// \relates ComposeMap kpeter@80: template kpeter@80: inline ComposeMap composeMap(const M1 &m1, const M2 &m2) { kpeter@80: return ComposeMap(m1, m2); alpar@25: } alpar@25: kpeter@80: kpeter@80: /// Combination of two maps using an STL (binary) functor. kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" takes two maps and a kpeter@80: /// binary functor and returns the combination of the two given maps kpeter@80: /// using the functor. kpeter@80: /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2 kpeter@80: /// and \c f is of \c F, then for kpeter@80: /// \code kpeter@80: /// CombineMap cm(m1,m2,f); kpeter@80: /// \endcode kpeter@80: /// cm[x] will be equal to f(m1[x],m2[x]). alpar@26: /// kpeter@80: /// The \c Key type of the map is inherited from \c M1 (\c M1::Key kpeter@80: /// must be convertible to \c M2::Key) and the \c Value type is \c V. kpeter@80: /// \c M2::Value and \c M1::Value must be convertible to the kpeter@80: /// corresponding input parameter of \c F and the return type of \c F kpeter@80: /// must be convertible to \c V. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the combineMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa ComposeMap kpeter@80: template kpeter@80: class CombineMap : public MapBase { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; kpeter@80: F _f; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef V Value; alpar@25: kpeter@80: /// Constructor kpeter@80: CombineMap(const M1 &m1, const M2 &m2, const F &f = F()) kpeter@80: : _m1(m1), _m2(m2), _f(f) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); } kpeter@80: }; alpar@25: kpeter@301: /// Returns a \c CombineMap class kpeter@301: kpeter@301: /// This function just returns a \c CombineMap class. kpeter@80: /// kpeter@80: /// For example, if \c m1 and \c m2 are both maps with \c double kpeter@80: /// values, then kpeter@80: /// \code kpeter@80: /// combineMap(m1,m2,std::plus()) kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// addMap(m1,m2) kpeter@80: /// \endcode kpeter@80: /// kpeter@80: /// This function is specialized for adaptable binary function kpeter@80: /// classes and C++ functions. kpeter@80: /// kpeter@80: /// \relates CombineMap kpeter@80: template kpeter@80: inline CombineMap kpeter@80: combineMap(const M1 &m1, const M2 &m2, const F &f) { kpeter@80: return CombineMap(m1,m2,f); alpar@25: } alpar@25: kpeter@80: template kpeter@80: inline CombineMap kpeter@80: combineMap(const M1 &m1, const M2 &m2, const F &f) { kpeter@80: return combineMap(m1,m2,f); kpeter@80: } alpar@25: kpeter@80: template kpeter@80: inline CombineMap kpeter@80: combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { kpeter@80: return combineMap(m1,m2,f); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// Converts an STL style (unary) functor to a map kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the value kpeter@80: /// of a given functor. Actually, it just wraps the functor and kpeter@80: /// provides the \c Key and \c Value typedefs. alpar@26: /// kpeter@80: /// Template parameters \c K and \c V will become its \c Key and kpeter@80: /// \c Value. In most cases they have to be given explicitly because kpeter@80: /// a functor typically does not provide \c argument_type and kpeter@80: /// \c result_type typedefs. kpeter@80: /// Parameter \c F is the type of the used functor. kpeter@29: /// kpeter@80: /// The simplest way of using this map is through the functorToMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa MapToFunctor kpeter@80: template kpeter@80: class FunctorToMap : public MapBase { kpeter@123: F _f; kpeter@80: public: kpeter@550: ///\e kpeter@550: typedef K Key; kpeter@550: ///\e kpeter@550: typedef V Value; alpar@25: kpeter@80: /// Constructor kpeter@80: FunctorToMap(const F &f = F()) : _f(f) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _f(k); } kpeter@80: }; kpeter@80: kpeter@301: /// Returns a \c FunctorToMap class kpeter@301: kpeter@301: /// This function just returns a \c FunctorToMap class. kpeter@80: /// kpeter@80: /// This function is specialized for adaptable binary function kpeter@80: /// classes and C++ functions. kpeter@80: /// kpeter@80: /// \relates FunctorToMap kpeter@80: template kpeter@80: inline FunctorToMap functorToMap(const F &f) { kpeter@80: return FunctorToMap(f); kpeter@80: } kpeter@80: kpeter@80: template kpeter@80: inline FunctorToMap kpeter@80: functorToMap(const F &f) kpeter@80: { kpeter@80: return FunctorToMap(f); kpeter@80: } kpeter@80: kpeter@80: template kpeter@80: inline FunctorToMap functorToMap(V (*f)(K)) { kpeter@80: return FunctorToMap(f); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// Converts a map to an STL style (unary) functor kpeter@80: kpeter@80: /// This class converts a map to an STL style (unary) functor. kpeter@80: /// That is it provides an operator() to read its values. kpeter@80: /// kpeter@80: /// For the sake of convenience it also works as a usual kpeter@80: /// \ref concepts::ReadMap "readable map", i.e. operator[] kpeter@80: /// and the \c Key and \c Value typedefs also exist. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the mapToFunctor() kpeter@80: /// function. kpeter@80: /// kpeter@80: ///\sa FunctorToMap kpeter@80: template kpeter@80: class MapToFunctor : public MapBase { kpeter@80: const M &_m; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M::Value Value; kpeter@550: kpeter@550: typedef typename M::Key argument_type; kpeter@550: typedef typename M::Value result_type; kpeter@80: kpeter@80: /// Constructor kpeter@80: MapToFunctor(const M &m) : _m(m) {} kpeter@550: ///\e kpeter@80: Value operator()(const Key &k) const { return _m[k]; } kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _m[k]; } alpar@25: }; kpeter@45: kpeter@301: /// Returns a \c MapToFunctor class kpeter@301: kpeter@301: /// This function just returns a \c MapToFunctor class. kpeter@80: /// \relates MapToFunctor kpeter@45: template kpeter@80: inline MapToFunctor mapToFunctor(const M &m) { kpeter@80: return MapToFunctor(m); kpeter@45: } alpar@25: alpar@25: kpeter@80: /// \brief Map adaptor to convert the \c Value type of a map to kpeter@80: /// another type using the default conversion. kpeter@80: kpeter@80: /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap kpeter@80: /// "readable map" to another type using the default conversion. kpeter@80: /// The \c Key type of it is inherited from \c M and the \c Value kpeter@80: /// type is \c V. kpeter@80: /// This type conforms the \ref concepts::ReadMap "ReadMap" concept. alpar@26: /// kpeter@80: /// The simplest way of using this map is through the convertMap() kpeter@80: /// function. kpeter@80: template kpeter@80: class ConvertMap : public MapBase { kpeter@80: const M &_m; kpeter@80: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef V Value; kpeter@80: kpeter@80: /// Constructor kpeter@80: kpeter@80: /// Constructor. kpeter@80: /// \param m The underlying map. kpeter@80: ConvertMap(const M &m) : _m(m) {} kpeter@80: kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _m[k]; } kpeter@80: }; kpeter@80: kpeter@301: /// Returns a \c ConvertMap class kpeter@301: kpeter@301: /// This function just returns a \c ConvertMap class. kpeter@80: /// \relates ConvertMap kpeter@80: template kpeter@80: inline ConvertMap convertMap(const M &map) { kpeter@80: return ConvertMap(map); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// Applies all map setting operations to two maps kpeter@80: kpeter@80: /// This map has two \ref concepts::WriteMap "writable map" parameters kpeter@80: /// and each write request will be passed to both of them. kpeter@80: /// If \c M1 is also \ref concepts::ReadMap "readable", then the read kpeter@80: /// operations will return the corresponding values of \c M1. kpeter@29: /// kpeter@80: /// The \c Key and \c Value types are inherited from \c M1. kpeter@80: /// The \c Key and \c Value of \c M2 must be convertible from those kpeter@80: /// of \c M1. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the forkMap() kpeter@80: /// function. kpeter@80: template kpeter@80: class ForkMap : public MapBase { kpeter@80: M1 &_m1; kpeter@80: M2 &_m2; kpeter@80: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M1::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {} kpeter@80: /// Returns the value associated with the given key in the first map. kpeter@80: Value operator[](const Key &k) const { return _m1[k]; } kpeter@80: /// Sets the value associated with the given key in both maps. kpeter@80: void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); } kpeter@80: }; kpeter@80: kpeter@301: /// Returns a \c ForkMap class kpeter@301: kpeter@301: /// This function just returns a \c ForkMap class. kpeter@80: /// \relates ForkMap kpeter@80: template kpeter@80: inline ForkMap forkMap(M1 &m1, M2 &m2) { kpeter@80: return ForkMap(m1,m2); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// Sum of two maps kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the sum kpeter@80: /// of the values of the two given maps. kpeter@80: /// Its \c Key and \c Value types are inherited from \c M1. kpeter@80: /// The \c Key and \c Value of \c M2 must be convertible to those of kpeter@80: /// \c M1. kpeter@80: /// kpeter@80: /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for kpeter@80: /// \code kpeter@80: /// AddMap am(m1,m2); kpeter@80: /// \endcode kpeter@80: /// am[x] will be equal to m1[x]+m2[x]. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the addMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa SubMap, MulMap, DivMap kpeter@80: /// \sa ShiftMap, ShiftWriteMap kpeter@80: template alpar@25: class AddMap : public MapBase { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M1::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _m1[k]+_m2[k]; } alpar@25: }; alpar@25: kpeter@301: /// Returns an \c AddMap class kpeter@301: kpeter@301: /// This function just returns an \c AddMap class. alpar@25: /// kpeter@80: /// For example, if \c m1 and \c m2 are both maps with \c double kpeter@80: /// values, then addMap(m1,m2)[x] will be equal to kpeter@80: /// m1[x]+m2[x]. kpeter@80: /// kpeter@80: /// \relates AddMap kpeter@80: template kpeter@80: inline AddMap addMap(const M1 &m1, const M2 &m2) { alpar@25: return AddMap(m1,m2); alpar@25: } alpar@25: alpar@25: kpeter@80: /// Difference of two maps kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the difference kpeter@80: /// of the values of the two given maps. kpeter@80: /// Its \c Key and \c Value types are inherited from \c M1. kpeter@80: /// The \c Key and \c Value of \c M2 must be convertible to those of kpeter@80: /// \c M1. alpar@25: /// kpeter@80: /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for kpeter@80: /// \code kpeter@80: /// SubMap sm(m1,m2); kpeter@80: /// \endcode kpeter@80: /// sm[x] will be equal to m1[x]-m2[x]. kpeter@29: /// kpeter@80: /// The simplest way of using this map is through the subMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa AddMap, MulMap, DivMap kpeter@80: template kpeter@80: class SubMap : public MapBase { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; kpeter@80: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M1::Value Value; kpeter@80: kpeter@80: /// Constructor kpeter@80: SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _m1[k]-_m2[k]; } kpeter@80: }; kpeter@80: kpeter@301: /// Returns a \c SubMap class kpeter@301: kpeter@301: /// This function just returns a \c SubMap class. kpeter@80: /// kpeter@80: /// For example, if \c m1 and \c m2 are both maps with \c double kpeter@80: /// values, then subMap(m1,m2)[x] will be equal to kpeter@80: /// m1[x]-m2[x]. kpeter@80: /// kpeter@80: /// \relates SubMap kpeter@80: template kpeter@80: inline SubMap subMap(const M1 &m1, const M2 &m2) { kpeter@80: return SubMap(m1,m2); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// Product of two maps kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the product kpeter@80: /// of the values of the two given maps. kpeter@80: /// Its \c Key and \c Value types are inherited from \c M1. kpeter@80: /// The \c Key and \c Value of \c M2 must be convertible to those of kpeter@80: /// \c M1. kpeter@80: /// kpeter@80: /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for kpeter@80: /// \code kpeter@80: /// MulMap mm(m1,m2); kpeter@80: /// \endcode kpeter@80: /// mm[x] will be equal to m1[x]*m2[x]. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the mulMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa AddMap, SubMap, DivMap kpeter@80: /// \sa ScaleMap, ScaleWriteMap kpeter@80: template kpeter@80: class MulMap : public MapBase { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; kpeter@80: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M1::Value Value; kpeter@80: kpeter@80: /// Constructor kpeter@80: MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _m1[k]*_m2[k]; } kpeter@80: }; kpeter@80: kpeter@301: /// Returns a \c MulMap class kpeter@301: kpeter@301: /// This function just returns a \c MulMap class. kpeter@80: /// kpeter@80: /// For example, if \c m1 and \c m2 are both maps with \c double kpeter@80: /// values, then mulMap(m1,m2)[x] will be equal to kpeter@80: /// m1[x]*m2[x]. kpeter@80: /// kpeter@80: /// \relates MulMap kpeter@80: template kpeter@80: inline MulMap mulMap(const M1 &m1,const M2 &m2) { kpeter@80: return MulMap(m1,m2); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// Quotient of two maps kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the quotient kpeter@80: /// of the values of the two given maps. kpeter@80: /// Its \c Key and \c Value types are inherited from \c M1. kpeter@80: /// The \c Key and \c Value of \c M2 must be convertible to those of kpeter@80: /// \c M1. kpeter@80: /// kpeter@80: /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for kpeter@80: /// \code kpeter@80: /// DivMap dm(m1,m2); kpeter@80: /// \endcode kpeter@80: /// dm[x] will be equal to m1[x]/m2[x]. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the divMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa AddMap, SubMap, MulMap kpeter@80: template kpeter@80: class DivMap : public MapBase { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; kpeter@80: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M1::Value Value; kpeter@80: kpeter@80: /// Constructor kpeter@80: DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _m1[k]/_m2[k]; } kpeter@80: }; kpeter@80: kpeter@301: /// Returns a \c DivMap class kpeter@301: kpeter@301: /// This function just returns a \c DivMap class. kpeter@80: /// kpeter@80: /// For example, if \c m1 and \c m2 are both maps with \c double kpeter@80: /// values, then divMap(m1,m2)[x] will be equal to kpeter@80: /// m1[x]/m2[x]. kpeter@80: /// kpeter@80: /// \relates DivMap kpeter@80: template kpeter@80: inline DivMap divMap(const M1 &m1,const M2 &m2) { kpeter@80: return DivMap(m1,m2); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// Shifts a map with a constant. kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the sum of kpeter@80: /// the given map and a constant value (i.e. it shifts the map with kpeter@80: /// the constant). Its \c Key and \c Value are inherited from \c M. kpeter@80: /// kpeter@80: /// Actually, kpeter@80: /// \code kpeter@80: /// ShiftMap sh(m,v); kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// ConstMap cm(v); kpeter@80: /// AddMap > sh(m,cm); kpeter@80: /// \endcode kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the shiftMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa ShiftWriteMap kpeter@80: template alpar@25: class ShiftMap : public MapBase { kpeter@80: const M &_m; kpeter@80: C _v; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor alpar@25: kpeter@80: /// Constructor. kpeter@80: /// \param m The undelying map. kpeter@80: /// \param v The constant value. kpeter@80: ShiftMap(const M &m, const C &v) : _m(m), _v(v) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _m[k]+_v; } alpar@25: }; alpar@25: kpeter@80: /// Shifts a map with a constant (read-write version). alpar@25: kpeter@80: /// This \ref concepts::ReadWriteMap "read-write map" returns the sum kpeter@80: /// of the given map and a constant value (i.e. it shifts the map with kpeter@80: /// the constant). Its \c Key and \c Value are inherited from \c M. kpeter@80: /// It makes also possible to write the map. alpar@25: /// kpeter@80: /// The simplest way of using this map is through the shiftWriteMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa ShiftMap kpeter@80: template alpar@25: class ShiftWriteMap : public MapBase { kpeter@80: M &_m; kpeter@80: C _v; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor alpar@25: kpeter@80: /// Constructor. kpeter@80: /// \param m The undelying map. kpeter@80: /// \param v The constant value. kpeter@80: ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _m[k]+_v; } kpeter@550: ///\e kpeter@80: void set(const Key &k, const Value &v) { _m.set(k, v-_v); } alpar@25: }; alpar@25: kpeter@301: /// Returns a \c ShiftMap class kpeter@301: kpeter@301: /// This function just returns a \c ShiftMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c double values and \c v is kpeter@80: /// \c double, then shiftMap(m,v)[x] will be equal to kpeter@80: /// m[x]+v. kpeter@80: /// kpeter@80: /// \relates ShiftMap kpeter@80: template kpeter@80: inline ShiftMap shiftMap(const M &m, const C &v) { alpar@25: return ShiftMap(m,v); alpar@25: } alpar@25: kpeter@301: /// Returns a \c ShiftWriteMap class kpeter@301: kpeter@301: /// This function just returns a \c ShiftWriteMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c double values and \c v is kpeter@80: /// \c double, then shiftWriteMap(m,v)[x] will be equal to kpeter@80: /// m[x]+v. kpeter@80: /// Moreover it makes also possible to write the map. kpeter@80: /// kpeter@80: /// \relates ShiftWriteMap kpeter@80: template kpeter@80: inline ShiftWriteMap shiftWriteMap(M &m, const C &v) { alpar@25: return ShiftWriteMap(m,v); alpar@25: } alpar@25: alpar@25: kpeter@80: /// Scales a map with a constant. kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the value of kpeter@80: /// the given map multiplied from the left side with a constant value. kpeter@80: /// Its \c Key and \c Value are inherited from \c M. alpar@26: /// kpeter@80: /// Actually, kpeter@80: /// \code kpeter@80: /// ScaleMap sc(m,v); kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// ConstMap cm(v); kpeter@80: /// MulMap, M> sc(cm,m); kpeter@80: /// \endcode alpar@25: /// kpeter@80: /// The simplest way of using this map is through the scaleMap() kpeter@80: /// function. alpar@25: /// kpeter@80: /// \sa ScaleWriteMap kpeter@80: template alpar@25: class ScaleMap : public MapBase { kpeter@80: const M &_m; kpeter@80: C _v; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor alpar@25: kpeter@80: /// Constructor. kpeter@80: /// \param m The undelying map. kpeter@80: /// \param v The constant value. kpeter@80: ScaleMap(const M &m, const C &v) : _m(m), _v(v) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _v*_m[k]; } alpar@25: }; alpar@25: kpeter@80: /// Scales a map with a constant (read-write version). alpar@25: kpeter@80: /// This \ref concepts::ReadWriteMap "read-write map" returns the value of kpeter@80: /// the given map multiplied from the left side with a constant value. kpeter@80: /// Its \c Key and \c Value are inherited from \c M. kpeter@80: /// It can also be used as write map if the \c / operator is defined kpeter@80: /// between \c Value and \c C and the given multiplier is not zero. kpeter@29: /// kpeter@80: /// The simplest way of using this map is through the scaleWriteMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa ScaleMap kpeter@80: template alpar@25: class ScaleWriteMap : public MapBase { kpeter@80: M &_m; kpeter@80: C _v; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor alpar@25: kpeter@80: /// Constructor. kpeter@80: /// \param m The undelying map. kpeter@80: /// \param v The constant value. kpeter@80: ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return _v*_m[k]; } kpeter@550: ///\e kpeter@80: void set(const Key &k, const Value &v) { _m.set(k, v/_v); } alpar@25: }; alpar@25: kpeter@301: /// Returns a \c ScaleMap class kpeter@301: kpeter@301: /// This function just returns a \c ScaleMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c double values and \c v is kpeter@80: /// \c double, then scaleMap(m,v)[x] will be equal to kpeter@80: /// v*m[x]. kpeter@80: /// kpeter@80: /// \relates ScaleMap kpeter@80: template kpeter@80: inline ScaleMap scaleMap(const M &m, const C &v) { alpar@25: return ScaleMap(m,v); alpar@25: } alpar@25: kpeter@301: /// Returns a \c ScaleWriteMap class kpeter@301: kpeter@301: /// This function just returns a \c ScaleWriteMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c double values and \c v is kpeter@80: /// \c double, then scaleWriteMap(m,v)[x] will be equal to kpeter@80: /// v*m[x]. kpeter@80: /// Moreover it makes also possible to write the map. kpeter@80: /// kpeter@80: /// \relates ScaleWriteMap kpeter@80: template kpeter@80: inline ScaleWriteMap scaleWriteMap(M &m, const C &v) { alpar@25: return ScaleWriteMap(m,v); alpar@25: } alpar@25: alpar@25: kpeter@80: /// Negative of a map alpar@25: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the negative kpeter@80: /// of the values of the given map (using the unary \c - operator). kpeter@80: /// Its \c Key and \c Value are inherited from \c M. alpar@25: /// kpeter@80: /// If M::Value is \c int, \c double etc., then kpeter@80: /// \code kpeter@80: /// NegMap neg(m); kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// ScaleMap neg(m,-1); kpeter@80: /// \endcode kpeter@29: /// kpeter@80: /// The simplest way of using this map is through the negMap() kpeter@80: /// function. kpeter@29: /// kpeter@80: /// \sa NegWriteMap kpeter@80: template alpar@25: class NegMap : public MapBase { kpeter@80: const M& _m; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: NegMap(const M &m) : _m(m) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return -_m[k]; } alpar@25: }; alpar@25: kpeter@80: /// Negative of a map (read-write version) kpeter@80: kpeter@80: /// This \ref concepts::ReadWriteMap "read-write map" returns the kpeter@80: /// negative of the values of the given map (using the unary \c - kpeter@80: /// operator). kpeter@80: /// Its \c Key and \c Value are inherited from \c M. kpeter@80: /// It makes also possible to write the map. kpeter@80: /// kpeter@80: /// If M::Value is \c int, \c double etc., then kpeter@80: /// \code kpeter@80: /// NegWriteMap neg(m); kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// ScaleWriteMap neg(m,-1); kpeter@80: /// \endcode kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the negWriteMap() kpeter@80: /// function. kpeter@29: /// kpeter@29: /// \sa NegMap kpeter@80: template alpar@25: class NegWriteMap : public MapBase { kpeter@80: M &_m; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: NegWriteMap(M &m) : _m(m) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return -_m[k]; } kpeter@550: ///\e kpeter@80: void set(const Key &k, const Value &v) { _m.set(k, -v); } alpar@25: }; alpar@25: kpeter@301: /// Returns a \c NegMap class kpeter@301: kpeter@301: /// This function just returns a \c NegMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c double values, then kpeter@80: /// negMap(m)[x] will be equal to -m[x]. kpeter@80: /// kpeter@80: /// \relates NegMap kpeter@80: template alpar@25: inline NegMap negMap(const M &m) { alpar@25: return NegMap(m); alpar@25: } alpar@25: kpeter@301: /// Returns a \c NegWriteMap class kpeter@301: kpeter@301: /// This function just returns a \c NegWriteMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c double values, then kpeter@80: /// negWriteMap(m)[x] will be equal to -m[x]. kpeter@80: /// Moreover it makes also possible to write the map. kpeter@80: /// kpeter@80: /// \relates NegWriteMap kpeter@80: template kpeter@80: inline NegWriteMap negWriteMap(M &m) { alpar@25: return NegWriteMap(m); alpar@25: } alpar@25: alpar@25: kpeter@80: /// Absolute value of a map kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the absolute kpeter@80: /// value of the values of the given map. kpeter@80: /// Its \c Key and \c Value are inherited from \c M. kpeter@80: /// \c Value must be comparable to \c 0 and the unary \c - kpeter@80: /// operator must be defined for it, of course. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the absMap() kpeter@80: /// function. kpeter@80: template alpar@25: class AbsMap : public MapBase { kpeter@80: const M &_m; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: AbsMap(const M &m) : _m(m) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { kpeter@80: Value tmp = _m[k]; alpar@25: return tmp >= 0 ? tmp : -tmp; alpar@25: } alpar@25: alpar@25: }; alpar@25: kpeter@301: /// Returns an \c AbsMap class kpeter@301: kpeter@301: /// This function just returns an \c AbsMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c double values, then kpeter@80: /// absMap(m)[x] will be equal to m[x] if kpeter@80: /// it is positive or zero and -m[x] if m[x] is kpeter@80: /// negative. kpeter@80: /// kpeter@80: /// \relates AbsMap kpeter@80: template alpar@25: inline AbsMap absMap(const M &m) { alpar@25: return AbsMap(m); alpar@25: } alpar@25: kpeter@82: /// @} alpar@209: kpeter@82: // Logical maps and map adaptors: kpeter@82: kpeter@82: /// \addtogroup maps kpeter@82: /// @{ kpeter@82: kpeter@82: /// Constant \c true map. kpeter@82: kpeter@82: /// This \ref concepts::ReadMap "read-only map" assigns \c true to kpeter@82: /// each key. kpeter@82: /// kpeter@82: /// Note that kpeter@82: /// \code kpeter@82: /// TrueMap tm; kpeter@82: /// \endcode kpeter@82: /// is equivalent to kpeter@82: /// \code kpeter@82: /// ConstMap tm(true); kpeter@82: /// \endcode kpeter@82: /// kpeter@82: /// \sa FalseMap kpeter@82: /// \sa ConstMap kpeter@82: template kpeter@82: class TrueMap : public MapBase { kpeter@82: public: kpeter@550: ///\e kpeter@550: typedef K Key; kpeter@550: ///\e kpeter@550: typedef bool Value; kpeter@82: kpeter@82: /// Gives back \c true. kpeter@82: Value operator[](const Key&) const { return true; } kpeter@82: }; kpeter@82: kpeter@301: /// Returns a \c TrueMap class kpeter@301: kpeter@301: /// This function just returns a \c TrueMap class. kpeter@82: /// \relates TrueMap kpeter@82: template kpeter@82: inline TrueMap trueMap() { kpeter@82: return TrueMap(); kpeter@82: } kpeter@82: kpeter@82: kpeter@82: /// Constant \c false map. kpeter@82: kpeter@82: /// This \ref concepts::ReadMap "read-only map" assigns \c false to kpeter@82: /// each key. kpeter@82: /// kpeter@82: /// Note that kpeter@82: /// \code kpeter@82: /// FalseMap fm; kpeter@82: /// \endcode kpeter@82: /// is equivalent to kpeter@82: /// \code kpeter@82: /// ConstMap fm(false); kpeter@82: /// \endcode kpeter@82: /// kpeter@82: /// \sa TrueMap kpeter@82: /// \sa ConstMap kpeter@82: template kpeter@82: class FalseMap : public MapBase { kpeter@82: public: kpeter@550: ///\e kpeter@550: typedef K Key; kpeter@550: ///\e kpeter@550: typedef bool Value; kpeter@82: kpeter@82: /// Gives back \c false. kpeter@82: Value operator[](const Key&) const { return false; } kpeter@82: }; kpeter@82: kpeter@301: /// Returns a \c FalseMap class kpeter@301: kpeter@301: /// This function just returns a \c FalseMap class. kpeter@82: /// \relates FalseMap kpeter@82: template kpeter@82: inline FalseMap falseMap() { kpeter@82: return FalseMap(); kpeter@82: } kpeter@82: kpeter@82: /// @} kpeter@82: kpeter@82: /// \addtogroup map_adaptors kpeter@82: /// @{ kpeter@82: kpeter@82: /// Logical 'and' of two maps kpeter@82: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the logical kpeter@82: /// 'and' of the values of the two given maps. kpeter@82: /// Its \c Key type is inherited from \c M1 and its \c Value type is kpeter@82: /// \c bool. \c M2::Key must be convertible to \c M1::Key. kpeter@82: /// kpeter@82: /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for kpeter@82: /// \code kpeter@82: /// AndMap am(m1,m2); kpeter@82: /// \endcode kpeter@82: /// am[x] will be equal to m1[x]&&m2[x]. kpeter@82: /// kpeter@82: /// The simplest way of using this map is through the andMap() kpeter@82: /// function. kpeter@82: /// kpeter@82: /// \sa OrMap kpeter@82: /// \sa NotMap, NotWriteMap kpeter@82: template kpeter@82: class AndMap : public MapBase { kpeter@82: const M1 &_m1; kpeter@82: const M2 &_m2; kpeter@82: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef bool Value; kpeter@82: kpeter@82: /// Constructor kpeter@82: AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@550: ///\e kpeter@82: Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; } kpeter@82: }; kpeter@82: kpeter@301: /// Returns an \c AndMap class kpeter@301: kpeter@301: /// This function just returns an \c AndMap class. kpeter@82: /// kpeter@82: /// For example, if \c m1 and \c m2 are both maps with \c bool values, kpeter@82: /// then andMap(m1,m2)[x] will be equal to kpeter@82: /// m1[x]&&m2[x]. kpeter@82: /// kpeter@82: /// \relates AndMap kpeter@82: template kpeter@82: inline AndMap andMap(const M1 &m1, const M2 &m2) { kpeter@82: return AndMap(m1,m2); kpeter@82: } kpeter@82: kpeter@82: kpeter@82: /// Logical 'or' of two maps kpeter@82: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the logical kpeter@82: /// 'or' of the values of the two given maps. kpeter@82: /// Its \c Key type is inherited from \c M1 and its \c Value type is kpeter@82: /// \c bool. \c M2::Key must be convertible to \c M1::Key. kpeter@82: /// kpeter@82: /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for kpeter@82: /// \code kpeter@82: /// OrMap om(m1,m2); kpeter@82: /// \endcode kpeter@82: /// om[x] will be equal to m1[x]||m2[x]. kpeter@82: /// kpeter@82: /// The simplest way of using this map is through the orMap() kpeter@82: /// function. kpeter@82: /// kpeter@82: /// \sa AndMap kpeter@82: /// \sa NotMap, NotWriteMap kpeter@82: template kpeter@82: class OrMap : public MapBase { kpeter@82: const M1 &_m1; kpeter@82: const M2 &_m2; kpeter@82: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef bool Value; kpeter@82: kpeter@82: /// Constructor kpeter@82: OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@550: ///\e kpeter@82: Value operator[](const Key &k) const { return _m1[k]||_m2[k]; } kpeter@82: }; kpeter@82: kpeter@301: /// Returns an \c OrMap class kpeter@301: kpeter@301: /// This function just returns an \c OrMap class. kpeter@82: /// kpeter@82: /// For example, if \c m1 and \c m2 are both maps with \c bool values, kpeter@82: /// then orMap(m1,m2)[x] will be equal to kpeter@82: /// m1[x]||m2[x]. kpeter@82: /// kpeter@82: /// \relates OrMap kpeter@82: template kpeter@82: inline OrMap orMap(const M1 &m1, const M2 &m2) { kpeter@82: return OrMap(m1,m2); kpeter@82: } kpeter@82: alpar@25: kpeter@80: /// Logical 'not' of a map kpeter@80: kpeter@82: /// This \ref concepts::ReadMap "read-only map" returns the logical kpeter@80: /// negation of the values of the given map. kpeter@80: /// Its \c Key is inherited from \c M and its \c Value is \c bool. alpar@25: /// kpeter@80: /// The simplest way of using this map is through the notMap() kpeter@80: /// function. alpar@25: /// kpeter@80: /// \sa NotWriteMap kpeter@80: template alpar@25: class NotMap : public MapBase { kpeter@80: const M &_m; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef bool Value; alpar@25: alpar@25: /// Constructor kpeter@80: NotMap(const M &m) : _m(m) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return !_m[k]; } alpar@25: }; alpar@25: kpeter@80: /// Logical 'not' of a map (read-write version) kpeter@80: kpeter@80: /// This \ref concepts::ReadWriteMap "read-write map" returns the kpeter@80: /// logical negation of the values of the given map. kpeter@80: /// Its \c Key is inherited from \c M and its \c Value is \c bool. kpeter@80: /// It makes also possible to write the map. When a value is set, kpeter@80: /// the opposite value is set to the original map. kpeter@29: /// kpeter@80: /// The simplest way of using this map is through the notWriteMap() kpeter@80: /// function. kpeter@80: /// kpeter@80: /// \sa NotMap kpeter@80: template alpar@25: class NotWriteMap : public MapBase { kpeter@80: M &_m; alpar@25: public: kpeter@550: ///\e kpeter@550: typedef typename M::Key Key; kpeter@550: ///\e kpeter@550: typedef bool Value; alpar@25: alpar@25: /// Constructor kpeter@80: NotWriteMap(M &m) : _m(m) {} kpeter@550: ///\e kpeter@80: Value operator[](const Key &k) const { return !_m[k]; } kpeter@550: ///\e kpeter@80: void set(const Key &k, bool v) { _m.set(k, !v); } alpar@25: }; kpeter@80: kpeter@301: /// Returns a \c NotMap class kpeter@301: kpeter@301: /// This function just returns a \c NotMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c bool values, then kpeter@80: /// notMap(m)[x] will be equal to !m[x]. kpeter@80: /// kpeter@80: /// \relates NotMap kpeter@80: template alpar@25: inline NotMap notMap(const M &m) { alpar@25: return NotMap(m); alpar@25: } kpeter@80: kpeter@301: /// Returns a \c NotWriteMap class kpeter@301: kpeter@301: /// This function just returns a \c NotWriteMap class. kpeter@80: /// kpeter@80: /// For example, if \c m is a map with \c bool values, then kpeter@80: /// notWriteMap(m)[x] will be equal to !m[x]. kpeter@80: /// Moreover it makes also possible to write the map. kpeter@80: /// kpeter@80: /// \relates NotWriteMap kpeter@80: template kpeter@80: inline NotWriteMap notWriteMap(M &m) { alpar@25: return NotWriteMap(m); alpar@25: } alpar@25: kpeter@82: kpeter@82: /// Combination of two maps using the \c == operator kpeter@82: kpeter@82: /// This \ref concepts::ReadMap "read-only map" assigns \c true to kpeter@82: /// the keys for which the corresponding values of the two maps are kpeter@82: /// equal. kpeter@82: /// Its \c Key type is inherited from \c M1 and its \c Value type is kpeter@82: /// \c bool. \c M2::Key must be convertible to \c M1::Key. kpeter@82: /// kpeter@82: /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for kpeter@82: /// \code kpeter@82: /// EqualMap em(m1,m2); kpeter@82: /// \endcode kpeter@82: /// em[x] will be equal to m1[x]==m2[x]. kpeter@82: /// kpeter@82: /// The simplest way of using this map is through the equalMap() kpeter@82: /// function. kpeter@82: /// kpeter@82: /// \sa LessMap kpeter@82: template kpeter@82: class EqualMap : public MapBase { kpeter@82: const M1 &_m1; kpeter@82: const M2 &_m2; kpeter@82: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef bool Value; kpeter@82: kpeter@82: /// Constructor kpeter@82: EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@550: ///\e kpeter@82: Value operator[](const Key &k) const { return _m1[k]==_m2[k]; } kpeter@82: }; kpeter@82: kpeter@301: /// Returns an \c EqualMap class kpeter@301: kpeter@301: /// This function just returns an \c EqualMap class. kpeter@82: /// kpeter@82: /// For example, if \c m1 and \c m2 are maps with keys and values of kpeter@82: /// the same type, then equalMap(m1,m2)[x] will be equal to kpeter@82: /// m1[x]==m2[x]. kpeter@82: /// kpeter@82: /// \relates EqualMap kpeter@82: template kpeter@82: inline EqualMap equalMap(const M1 &m1, const M2 &m2) { kpeter@82: return EqualMap(m1,m2); kpeter@82: } kpeter@82: kpeter@82: kpeter@82: /// Combination of two maps using the \c < operator kpeter@82: kpeter@82: /// This \ref concepts::ReadMap "read-only map" assigns \c true to kpeter@82: /// the keys for which the corresponding value of the first map is kpeter@82: /// less then the value of the second map. kpeter@82: /// Its \c Key type is inherited from \c M1 and its \c Value type is kpeter@82: /// \c bool. \c M2::Key must be convertible to \c M1::Key. kpeter@82: /// kpeter@82: /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for kpeter@82: /// \code kpeter@82: /// LessMap lm(m1,m2); kpeter@82: /// \endcode kpeter@82: /// lm[x] will be equal to m1[x]. kpeter@82: /// kpeter@82: /// The simplest way of using this map is through the lessMap() kpeter@82: /// function. kpeter@82: /// kpeter@82: /// \sa EqualMap kpeter@82: template kpeter@82: class LessMap : public MapBase { kpeter@82: const M1 &_m1; kpeter@82: const M2 &_m2; kpeter@82: public: kpeter@550: ///\e kpeter@550: typedef typename M1::Key Key; kpeter@550: ///\e kpeter@550: typedef bool Value; kpeter@82: kpeter@82: /// Constructor kpeter@82: LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@550: ///\e kpeter@82: Value operator[](const Key &k) const { return _m1[k]<_m2[k]; } kpeter@82: }; kpeter@82: kpeter@301: /// Returns an \c LessMap class kpeter@301: kpeter@301: /// This function just returns an \c LessMap class. kpeter@82: /// kpeter@82: /// For example, if \c m1 and \c m2 are maps with keys and values of kpeter@82: /// the same type, then lessMap(m1,m2)[x] will be equal to kpeter@82: /// m1[x]. kpeter@82: /// kpeter@82: /// \relates LessMap kpeter@82: template kpeter@82: inline LessMap lessMap(const M1 &m1, const M2 &m2) { kpeter@82: return LessMap(m1,m2); kpeter@82: } kpeter@82: alpar@104: namespace _maps_bits { alpar@104: alpar@104: template alpar@104: struct IteratorTraits { alpar@104: typedef typename std::iterator_traits<_Iterator>::value_type Value; alpar@104: }; alpar@104: alpar@104: template alpar@104: struct IteratorTraits<_Iterator, alpar@104: typename exists::type> alpar@104: { alpar@104: typedef typename _Iterator::container_type::value_type Value; alpar@104: }; alpar@104: alpar@104: } alpar@104: kpeter@314: /// @} kpeter@314: kpeter@314: /// \addtogroup maps kpeter@314: /// @{ kpeter@314: alpar@104: /// \brief Writable bool map for logging each \c true assigned element alpar@104: /// kpeter@159: /// A \ref concepts::WriteMap "writable" bool map for logging alpar@104: /// each \c true assigned element, i.e it copies subsequently each alpar@104: /// keys set to \c true to the given iterator. kpeter@159: /// The most important usage of it is storing certain nodes or arcs kpeter@159: /// that were marked \c true by an algorithm. alpar@104: /// kpeter@159: /// There are several algorithms that provide solutions through bool kpeter@159: /// maps and most of them assign \c true at most once for each key. kpeter@159: /// In these cases it is a natural request to store each \c true kpeter@159: /// assigned elements (in order of the assignment), which can be kpeter@167: /// easily done with LoggerBoolMap. kpeter@159: /// kpeter@167: /// The simplest way of using this map is through the loggerBoolMap() kpeter@159: /// function. kpeter@159: /// kpeter@550: /// \tparam IT The type of the iterator. kpeter@550: /// \tparam KEY The key type of the map. The default value set kpeter@159: /// according to the iterator type should work in most cases. alpar@104: /// alpar@104: /// \note The container of the iterator must contain enough space kpeter@159: /// for the elements or the iterator should be an inserter iterator. kpeter@159: #ifdef DOXYGEN kpeter@550: template kpeter@159: #else kpeter@550: template ::Value> kpeter@159: #endif kpeter@550: class LoggerBoolMap : public MapBase { alpar@104: public: kpeter@550: kpeter@550: ///\e kpeter@550: typedef KEY Key; kpeter@550: ///\e alpar@104: typedef bool Value; kpeter@550: ///\e kpeter@550: typedef IT Iterator; alpar@104: alpar@104: /// Constructor kpeter@167: LoggerBoolMap(Iterator it) alpar@104: : _begin(it), _end(it) {} alpar@104: alpar@104: /// Gives back the given iterator set for the first key alpar@104: Iterator begin() const { alpar@104: return _begin; alpar@104: } alpar@104: alpar@104: /// Gives back the the 'after the last' iterator alpar@104: Iterator end() const { alpar@104: return _end; alpar@104: } alpar@104: alpar@104: /// The set function of the map kpeter@159: void set(const Key& key, Value value) { alpar@104: if (value) { alpar@209: *_end++ = key; alpar@104: } alpar@104: } alpar@104: alpar@104: private: alpar@104: Iterator _begin; kpeter@159: Iterator _end; alpar@104: }; alpar@209: kpeter@301: /// Returns a \c LoggerBoolMap class kpeter@301: kpeter@301: /// This function just returns a \c LoggerBoolMap class. kpeter@159: /// kpeter@159: /// The most important usage of it is storing certain nodes or arcs kpeter@159: /// that were marked \c true by an algorithm. kpeter@159: /// For example it makes easier to store the nodes in the processing kpeter@159: /// order of Dfs algorithm, as the following examples show. kpeter@159: /// \code kpeter@159: /// std::vector v; kpeter@167: /// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run(); kpeter@159: /// \endcode kpeter@159: /// \code kpeter@159: /// std::vector v(countNodes(g)); kpeter@167: /// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run(); kpeter@159: /// \endcode kpeter@159: /// kpeter@159: /// \note The container of the iterator must contain enough space kpeter@159: /// for the elements or the iterator should be an inserter iterator. kpeter@159: /// kpeter@167: /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so kpeter@159: /// it cannot be used when a readable map is needed, for example as kpeter@301: /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms. kpeter@159: /// kpeter@167: /// \relates LoggerBoolMap kpeter@159: template kpeter@167: inline LoggerBoolMap loggerBoolMap(Iterator it) { kpeter@167: return LoggerBoolMap(it); kpeter@159: } alpar@104: kpeter@314: /// @} kpeter@314: kpeter@314: /// \addtogroup graph_maps kpeter@314: /// @{ kpeter@314: kpeter@550: /// \brief Provides an immutable and unique id for each item in a graph. kpeter@550: /// kpeter@550: /// IdMap provides a unique and immutable id for each item of the kpeter@550: /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is kpeter@550: /// - \b unique: different items get different ids, kpeter@550: /// - \b immutable: the id of an item does not change (even if you kpeter@550: /// delete other nodes). kpeter@550: /// kpeter@550: /// Using this map you get access (i.e. can read) the inner id values of kpeter@550: /// the items stored in the graph, which is returned by the \c id() kpeter@550: /// function of the graph. This map can be inverted with its member deba@220: /// class \c InverseMap or with the \c operator() member. deba@220: /// kpeter@550: /// \tparam GR The graph type. kpeter@550: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@550: /// \c GR::Edge). kpeter@550: /// alpar@564: /// \see RangeIdMap kpeter@550: template kpeter@550: class IdMap : public MapBase { deba@220: public: kpeter@550: /// The graph type of IdMap. kpeter@550: typedef GR Graph; kpeter@550: /// The key type of IdMap (\c Node, \c Arc or \c Edge). kpeter@550: typedef K Item; kpeter@550: /// The key type of IdMap (\c Node, \c Arc or \c Edge). kpeter@550: typedef K Key; kpeter@550: /// The value type of IdMap. deba@220: typedef int Value; deba@220: deba@220: /// \brief Constructor. deba@220: /// deba@220: /// Constructor of the map. deba@220: explicit IdMap(const Graph& graph) : _graph(&graph) {} deba@220: deba@220: /// \brief Gives back the \e id of the item. deba@220: /// deba@220: /// Gives back the immutable and unique \e id of the item. deba@220: int operator[](const Item& item) const { return _graph->id(item);} deba@220: kpeter@550: /// \brief Gives back the \e item by its id. deba@220: /// kpeter@550: /// Gives back the \e item by its id. deba@220: Item operator()(int id) { return _graph->fromId(id, Item()); } deba@220: deba@220: private: deba@220: const Graph* _graph; deba@220: deba@220: public: deba@220: kpeter@550: /// \brief This class represents the inverse of its owner (IdMap). deba@220: /// kpeter@550: /// This class represents the inverse of its owner (IdMap). deba@220: /// \see inverse() deba@220: class InverseMap { deba@220: public: deba@220: deba@220: /// \brief Constructor. deba@220: /// deba@220: /// Constructor for creating an id-to-item map. deba@220: explicit InverseMap(const Graph& graph) : _graph(&graph) {} deba@220: deba@220: /// \brief Constructor. deba@220: /// deba@220: /// Constructor for creating an id-to-item map. deba@220: explicit InverseMap(const IdMap& map) : _graph(map._graph) {} deba@220: deba@220: /// \brief Gives back the given item from its id. deba@220: /// deba@220: /// Gives back the given item from its id. deba@220: Item operator[](int id) const { return _graph->fromId(id, Item());} deba@220: deba@220: private: deba@220: const Graph* _graph; deba@220: }; deba@220: deba@220: /// \brief Gives back the inverse of the map. deba@220: /// deba@220: /// Gives back the inverse of the IdMap. deba@220: InverseMap inverse() const { return InverseMap(*_graph);} deba@220: }; deba@220: deba@220: alpar@564: /// \brief General cross reference graph map type. kpeter@550: kpeter@550: /// This class provides simple invertable graph maps. kpeter@550: /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" deba@220: /// and if a key is set to a new value then store it deba@220: /// in the inverse map. deba@220: /// deba@220: /// The values of the map can be accessed deba@220: /// with stl compatible forward iterator. deba@220: /// kpeter@550: /// \tparam GR The graph type. kpeter@550: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@550: /// \c GR::Edge). kpeter@550: /// \tparam V The value type of the map. deba@220: /// deba@220: /// \see IterableValueMap kpeter@550: template alpar@564: class CrossRefMap kpeter@550: : protected ItemSetTraits::template Map::Type { deba@220: private: deba@220: kpeter@550: typedef typename ItemSetTraits:: kpeter@550: template Map::Type Map; kpeter@550: kpeter@550: typedef std::map Container; deba@220: Container _inv_map; deba@220: deba@220: public: deba@220: alpar@564: /// The graph type of CrossRefMap. kpeter@550: typedef GR Graph; alpar@564: /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge). kpeter@550: typedef K Item; alpar@564: /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge). kpeter@550: typedef K Key; alpar@564: /// The value type of CrossRefMap. kpeter@550: typedef V Value; deba@220: deba@220: /// \brief Constructor. deba@220: /// alpar@564: /// Construct a new CrossRefMap for the given graph. alpar@564: explicit CrossRefMap(const Graph& graph) : Map(graph) {} deba@220: deba@220: /// \brief Forward iterator for values. deba@220: /// deba@220: /// This iterator is an stl compatible forward deba@220: /// iterator on the values of the map. The values can kpeter@550: /// be accessed in the [beginValue, endValue) range. deba@220: class ValueIterator deba@220: : public std::iterator { alpar@564: friend class CrossRefMap; deba@220: private: deba@220: ValueIterator(typename Container::const_iterator _it) deba@220: : it(_it) {} deba@220: public: deba@220: deba@220: ValueIterator() {} deba@220: deba@220: ValueIterator& operator++() { ++it; return *this; } deba@220: ValueIterator operator++(int) { deba@220: ValueIterator tmp(*this); deba@220: operator++(); deba@220: return tmp; deba@220: } deba@220: deba@220: const Value& operator*() const { return it->first; } deba@220: const Value* operator->() const { return &(it->first); } deba@220: deba@220: bool operator==(ValueIterator jt) const { return it == jt.it; } deba@220: bool operator!=(ValueIterator jt) const { return it != jt.it; } deba@220: deba@220: private: deba@220: typename Container::const_iterator it; deba@220: }; deba@220: deba@220: /// \brief Returns an iterator to the first value. deba@220: /// deba@220: /// Returns an stl compatible iterator to the deba@220: /// first value of the map. The values of the kpeter@550: /// map can be accessed in the [beginValue, endValue) deba@220: /// range. deba@220: ValueIterator beginValue() const { deba@220: return ValueIterator(_inv_map.begin()); deba@220: } deba@220: deba@220: /// \brief Returns an iterator after the last value. deba@220: /// deba@220: /// Returns an stl compatible iterator after the deba@220: /// last value of the map. The values of the kpeter@550: /// map can be accessed in the [beginValue, endValue) deba@220: /// range. deba@220: ValueIterator endValue() const { deba@220: return ValueIterator(_inv_map.end()); deba@220: } deba@220: kpeter@550: /// \brief Sets the value associated with the given key. deba@220: /// kpeter@550: /// Sets the value associated with the given key. deba@220: void set(const Key& key, const Value& val) { deba@220: Value oldval = Map::operator[](key); deba@220: typename Container::iterator it = _inv_map.find(oldval); deba@220: if (it != _inv_map.end() && it->second == key) { deba@220: _inv_map.erase(it); deba@220: } deba@220: _inv_map.insert(make_pair(val, key)); deba@220: Map::set(key, val); deba@220: } deba@220: kpeter@550: /// \brief Returns the value associated with the given key. deba@220: /// kpeter@550: /// Returns the value associated with the given key. deba@220: typename MapTraits::ConstReturnValue deba@220: operator[](const Key& key) const { deba@220: return Map::operator[](key); deba@220: } deba@220: deba@220: /// \brief Gives back the item by its value. deba@220: /// deba@220: /// Gives back the item by its value. deba@220: Key operator()(const Value& key) const { deba@220: typename Container::const_iterator it = _inv_map.find(key); deba@220: return it != _inv_map.end() ? it->second : INVALID; deba@220: } deba@220: deba@220: protected: deba@220: kpeter@550: /// \brief Erase the key from the map and the inverse map. deba@220: /// kpeter@550: /// Erase the key from the map and the inverse map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void erase(const Key& key) { deba@220: Value val = Map::operator[](key); deba@220: typename Container::iterator it = _inv_map.find(val); deba@220: if (it != _inv_map.end() && it->second == key) { deba@220: _inv_map.erase(it); deba@220: } deba@220: Map::erase(key); deba@220: } deba@220: kpeter@550: /// \brief Erase more keys from the map and the inverse map. deba@220: /// kpeter@550: /// Erase more keys from the map and the inverse map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void erase(const std::vector& keys) { deba@220: for (int i = 0; i < int(keys.size()); ++i) { deba@220: Value val = Map::operator[](keys[i]); deba@220: typename Container::iterator it = _inv_map.find(val); deba@220: if (it != _inv_map.end() && it->second == keys[i]) { deba@220: _inv_map.erase(it); deba@220: } deba@220: } deba@220: Map::erase(keys); deba@220: } deba@220: kpeter@550: /// \brief Clear the keys from the map and the inverse map. deba@220: /// kpeter@550: /// Clear the keys from the map and the inverse map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void clear() { deba@220: _inv_map.clear(); deba@220: Map::clear(); deba@220: } deba@220: deba@220: public: deba@220: deba@220: /// \brief The inverse map type. deba@220: /// deba@220: /// The inverse of this map. The subscript operator of the map kpeter@550: /// gives back the item that was last assigned to the value. deba@220: class InverseMap { deba@220: public: kpeter@550: /// \brief Constructor deba@220: /// deba@220: /// Constructor of the InverseMap. alpar@564: explicit InverseMap(const CrossRefMap& inverted) deba@220: : _inverted(inverted) {} deba@220: deba@220: /// The value type of the InverseMap. alpar@564: typedef typename CrossRefMap::Key Value; deba@220: /// The key type of the InverseMap. alpar@564: typedef typename CrossRefMap::Value Key; deba@220: deba@220: /// \brief Subscript operator. deba@220: /// kpeter@550: /// Subscript operator. It gives back the item kpeter@550: /// that was last assigned to the given value. deba@220: Value operator[](const Key& key) const { deba@220: return _inverted(key); deba@220: } deba@220: deba@220: private: alpar@564: const CrossRefMap& _inverted; deba@220: }; deba@220: kpeter@550: /// \brief It gives back the read-only inverse map. deba@220: /// kpeter@550: /// It gives back the read-only inverse map. deba@220: InverseMap inverse() const { deba@220: return InverseMap(*this); deba@220: } deba@220: deba@220: }; deba@220: alpar@564: /// \brief Provides continuous and unique ID for the alpar@564: /// items of a graph. deba@220: /// alpar@564: /// RangeIdMap provides a unique and continuous alpar@564: /// ID for each item of a given type (\c Node, \c Arc or kpeter@550: /// \c Edge) in a graph. This id is kpeter@550: /// - \b unique: different items get different ids, kpeter@550: /// - \b continuous: the range of the ids is the set of integers kpeter@550: /// between 0 and \c n-1, where \c n is the number of the items of alpar@564: /// this type (\c Node, \c Arc or \c Edge). alpar@564: /// - So, the ids can change when deleting an item of the same type. deba@220: /// kpeter@550: /// Thus this id is not (necessarily) the same as what can get using kpeter@550: /// the \c id() function of the graph or \ref IdMap. kpeter@550: /// This map can be inverted with its member class \c InverseMap, kpeter@550: /// or with the \c operator() member. kpeter@550: /// kpeter@550: /// \tparam GR The graph type. kpeter@550: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@550: /// \c GR::Edge). kpeter@550: /// kpeter@550: /// \see IdMap kpeter@550: template alpar@564: class RangeIdMap kpeter@550: : protected ItemSetTraits::template Map::Type { kpeter@550: kpeter@550: typedef typename ItemSetTraits::template Map::Type Map; deba@220: deba@220: public: alpar@564: /// The graph type of RangeIdMap. kpeter@550: typedef GR Graph; alpar@564: /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge). kpeter@550: typedef K Item; alpar@564: /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge). kpeter@550: typedef K Key; alpar@564: /// The value type of RangeIdMap. kpeter@550: typedef int Value; deba@220: deba@220: /// \brief Constructor. deba@220: /// alpar@564: /// Constructor. alpar@564: explicit RangeIdMap(const Graph& gr) : Map(gr) { deba@220: Item it; deba@220: const typename Map::Notifier* nf = Map::notifier(); deba@220: for (nf->first(it); it != INVALID; nf->next(it)) { deba@220: Map::set(it, _inv_map.size()); deba@220: _inv_map.push_back(it); deba@220: } deba@220: } deba@220: deba@220: protected: deba@220: kpeter@550: /// \brief Adds a new key to the map. deba@220: /// deba@220: /// Add a new key to the map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void add(const Item& item) { deba@220: Map::add(item); deba@220: Map::set(item, _inv_map.size()); deba@220: _inv_map.push_back(item); deba@220: } deba@220: deba@220: /// \brief Add more new keys to the map. deba@220: /// deba@220: /// Add more new keys to the map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void add(const std::vector& items) { deba@220: Map::add(items); deba@220: for (int i = 0; i < int(items.size()); ++i) { deba@220: Map::set(items[i], _inv_map.size()); deba@220: _inv_map.push_back(items[i]); deba@220: } deba@220: } deba@220: deba@220: /// \brief Erase the key from the map. deba@220: /// deba@220: /// Erase the key from the map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void erase(const Item& item) { deba@220: Map::set(_inv_map.back(), Map::operator[](item)); deba@220: _inv_map[Map::operator[](item)] = _inv_map.back(); deba@220: _inv_map.pop_back(); deba@220: Map::erase(item); deba@220: } deba@220: deba@220: /// \brief Erase more keys from the map. deba@220: /// deba@220: /// Erase more keys from the map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void erase(const std::vector& items) { deba@220: for (int i = 0; i < int(items.size()); ++i) { deba@220: Map::set(_inv_map.back(), Map::operator[](items[i])); deba@220: _inv_map[Map::operator[](items[i])] = _inv_map.back(); deba@220: _inv_map.pop_back(); deba@220: } deba@220: Map::erase(items); deba@220: } deba@220: deba@220: /// \brief Build the unique map. deba@220: /// deba@220: /// Build the unique map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void build() { deba@220: Map::build(); deba@220: Item it; deba@220: const typename Map::Notifier* nf = Map::notifier(); deba@220: for (nf->first(it); it != INVALID; nf->next(it)) { deba@220: Map::set(it, _inv_map.size()); deba@220: _inv_map.push_back(it); deba@220: } deba@220: } deba@220: deba@220: /// \brief Clear the keys from the map. deba@220: /// deba@220: /// Clear the keys from the map. It is called by the deba@220: /// \c AlterationNotifier. deba@220: virtual void clear() { deba@220: _inv_map.clear(); deba@220: Map::clear(); deba@220: } deba@220: deba@220: public: deba@220: deba@220: /// \brief Returns the maximal value plus one. deba@220: /// deba@220: /// Returns the maximal value plus one in the map. deba@220: unsigned int size() const { deba@220: return _inv_map.size(); deba@220: } deba@220: deba@220: /// \brief Swaps the position of the two items in the map. deba@220: /// deba@220: /// Swaps the position of the two items in the map. deba@220: void swap(const Item& p, const Item& q) { deba@220: int pi = Map::operator[](p); deba@220: int qi = Map::operator[](q); deba@220: Map::set(p, qi); deba@220: _inv_map[qi] = p; deba@220: Map::set(q, pi); deba@220: _inv_map[pi] = q; deba@220: } deba@220: alpar@564: /// \brief Gives back the \e RangeId of the item deba@220: /// alpar@564: /// Gives back the \e RangeId of the item. deba@220: int operator[](const Item& item) const { deba@220: return Map::operator[](item); deba@220: } deba@220: alpar@564: /// \brief Gives back the item belonging to a \e RangeId alpar@564: /// alpar@564: /// Gives back the item belonging to a \e RangeId. deba@220: Item operator()(int id) const { deba@220: return _inv_map[id]; deba@220: } deba@220: deba@220: private: deba@220: deba@220: typedef std::vector Container; deba@220: Container _inv_map; deba@220: deba@220: public: kpeter@550: alpar@564: /// \brief The inverse map type of RangeIdMap. deba@220: /// alpar@564: /// The inverse map type of RangeIdMap. deba@220: class InverseMap { deba@220: public: kpeter@550: /// \brief Constructor deba@220: /// deba@220: /// Constructor of the InverseMap. alpar@564: explicit InverseMap(const RangeIdMap& inverted) deba@220: : _inverted(inverted) {} deba@220: deba@220: deba@220: /// The value type of the InverseMap. alpar@564: typedef typename RangeIdMap::Key Value; deba@220: /// The key type of the InverseMap. alpar@564: typedef typename RangeIdMap::Value Key; deba@220: deba@220: /// \brief Subscript operator. deba@220: /// deba@220: /// Subscript operator. It gives back the item kpeter@550: /// that the descriptor currently belongs to. deba@220: Value operator[](const Key& key) const { deba@220: return _inverted(key); deba@220: } deba@220: deba@220: /// \brief Size of the map. deba@220: /// deba@220: /// Returns the size of the map. deba@220: unsigned int size() const { deba@220: return _inverted.size(); deba@220: } deba@220: deba@220: private: alpar@564: const RangeIdMap& _inverted; deba@220: }; deba@220: deba@220: /// \brief Gives back the inverse of the map. deba@220: /// deba@220: /// Gives back the inverse of the map. deba@220: const InverseMap inverse() const { deba@220: return InverseMap(*this); deba@220: } deba@220: }; deba@220: kpeter@550: /// \brief Map of the source nodes of arcs in a digraph. deba@220: /// kpeter@550: /// SourceMap provides access for the source node of each arc in a digraph, kpeter@550: /// which is returned by the \c source() function of the digraph. kpeter@550: /// \tparam GR The digraph type. deba@220: /// \see TargetMap kpeter@550: template deba@220: class SourceMap { deba@220: public: deba@220: kpeter@550: ///\e kpeter@550: typedef typename GR::Arc Key; kpeter@550: ///\e kpeter@550: typedef typename GR::Node Value; deba@220: deba@220: /// \brief Constructor deba@220: /// kpeter@550: /// Constructor. kpeter@313: /// \param digraph The digraph that the map belongs to. kpeter@550: explicit SourceMap(const GR& digraph) : _graph(digraph) {} kpeter@550: kpeter@550: /// \brief Returns the source node of the given arc. deba@220: /// kpeter@550: /// Returns the source node of the given arc. deba@220: Value operator[](const Key& arc) const { kpeter@550: return _graph.source(arc); deba@220: } deba@220: deba@220: private: kpeter@550: const GR& _graph; deba@220: }; deba@220: kpeter@301: /// \brief Returns a \c SourceMap class. deba@220: /// kpeter@301: /// This function just returns an \c SourceMap class. deba@220: /// \relates SourceMap kpeter@550: template kpeter@550: inline SourceMap sourceMap(const GR& graph) { kpeter@550: return SourceMap(graph); deba@220: } deba@220: kpeter@550: /// \brief Map of the target nodes of arcs in a digraph. deba@220: /// kpeter@550: /// TargetMap provides access for the target node of each arc in a digraph, kpeter@550: /// which is returned by the \c target() function of the digraph. kpeter@550: /// \tparam GR The digraph type. deba@220: /// \see SourceMap kpeter@550: template deba@220: class TargetMap { deba@220: public: deba@220: kpeter@550: ///\e kpeter@550: typedef typename GR::Arc Key; kpeter@550: ///\e kpeter@550: typedef typename GR::Node Value; deba@220: deba@220: /// \brief Constructor deba@220: /// kpeter@550: /// Constructor. kpeter@313: /// \param digraph The digraph that the map belongs to. kpeter@550: explicit TargetMap(const GR& digraph) : _graph(digraph) {} kpeter@550: kpeter@550: /// \brief Returns the target node of the given arc. deba@220: /// kpeter@550: /// Returns the target node of the given arc. deba@220: Value operator[](const Key& e) const { kpeter@550: return _graph.target(e); deba@220: } deba@220: deba@220: private: kpeter@550: const GR& _graph; deba@220: }; deba@220: kpeter@301: /// \brief Returns a \c TargetMap class. deba@220: /// kpeter@301: /// This function just returns a \c TargetMap class. deba@220: /// \relates TargetMap kpeter@550: template kpeter@550: inline TargetMap targetMap(const GR& graph) { kpeter@550: return TargetMap(graph); deba@220: } deba@220: kpeter@550: /// \brief Map of the "forward" directed arc view of edges in a graph. deba@220: /// kpeter@550: /// ForwardMap provides access for the "forward" directed arc view of kpeter@550: /// each edge in a graph, which is returned by the \c direct() function kpeter@550: /// of the graph with \c true parameter. kpeter@550: /// \tparam GR The graph type. deba@220: /// \see BackwardMap kpeter@550: template deba@220: class ForwardMap { deba@220: public: deba@220: kpeter@550: typedef typename GR::Arc Value; kpeter@550: typedef typename GR::Edge Key; deba@220: deba@220: /// \brief Constructor deba@220: /// kpeter@550: /// Constructor. kpeter@313: /// \param graph The graph that the map belongs to. kpeter@550: explicit ForwardMap(const GR& graph) : _graph(graph) {} kpeter@550: kpeter@550: /// \brief Returns the "forward" directed arc view of the given edge. deba@220: /// kpeter@550: /// Returns the "forward" directed arc view of the given edge. deba@220: Value operator[](const Key& key) const { deba@220: return _graph.direct(key, true); deba@220: } deba@220: deba@220: private: kpeter@550: const GR& _graph; deba@220: }; deba@220: kpeter@301: /// \brief Returns a \c ForwardMap class. deba@220: /// kpeter@301: /// This function just returns an \c ForwardMap class. deba@220: /// \relates ForwardMap kpeter@550: template kpeter@550: inline ForwardMap forwardMap(const GR& graph) { kpeter@550: return ForwardMap(graph); deba@220: } deba@220: kpeter@550: /// \brief Map of the "backward" directed arc view of edges in a graph. deba@220: /// kpeter@550: /// BackwardMap provides access for the "backward" directed arc view of kpeter@550: /// each edge in a graph, which is returned by the \c direct() function kpeter@550: /// of the graph with \c false parameter. kpeter@550: /// \tparam GR The graph type. deba@220: /// \see ForwardMap kpeter@550: template deba@220: class BackwardMap { deba@220: public: deba@220: kpeter@550: typedef typename GR::Arc Value; kpeter@550: typedef typename GR::Edge Key; deba@220: deba@220: /// \brief Constructor deba@220: /// kpeter@550: /// Constructor. kpeter@313: /// \param graph The graph that the map belongs to. kpeter@550: explicit BackwardMap(const GR& graph) : _graph(graph) {} kpeter@550: kpeter@550: /// \brief Returns the "backward" directed arc view of the given edge. deba@220: /// kpeter@550: /// Returns the "backward" directed arc view of the given edge. deba@220: Value operator[](const Key& key) const { deba@220: return _graph.direct(key, false); deba@220: } deba@220: deba@220: private: kpeter@550: const GR& _graph; deba@220: }; deba@220: kpeter@301: /// \brief Returns a \c BackwardMap class kpeter@301: kpeter@301: /// This function just returns a \c BackwardMap class. deba@220: /// \relates BackwardMap kpeter@550: template kpeter@550: inline BackwardMap backwardMap(const GR& graph) { kpeter@550: return BackwardMap(graph); deba@220: } deba@220: kpeter@550: /// \brief Map of the in-degrees of nodes in a digraph. deba@220: /// deba@220: /// This map returns the in-degree of a node. Once it is constructed, kpeter@550: /// the degrees are stored in a standard \c NodeMap, so each query is done deba@220: /// in constant time. On the other hand, the values are updated automatically deba@220: /// whenever the digraph changes. deba@220: /// kpeter@550: /// \warning Besides \c addNode() and \c addArc(), a digraph structure kpeter@550: /// may provide alternative ways to modify the digraph. kpeter@550: /// The correct behavior of InDegMap is not guarantied if these additional kpeter@550: /// features are used. For example the functions kpeter@550: /// \ref ListDigraph::changeSource() "changeSource()", deba@220: /// \ref ListDigraph::changeTarget() "changeTarget()" and deba@220: /// \ref ListDigraph::reverseArc() "reverseArc()" deba@220: /// of \ref ListDigraph will \e not update the degree values correctly. deba@220: /// deba@220: /// \sa OutDegMap kpeter@550: template deba@220: class InDegMap kpeter@550: : protected ItemSetTraits deba@220: ::ItemNotifier::ObserverBase { deba@220: deba@220: public: kpeter@550: kpeter@550: /// The digraph type kpeter@550: typedef GR Digraph; kpeter@550: /// The key type kpeter@550: typedef typename Digraph::Node Key; kpeter@550: /// The value type deba@220: typedef int Value; deba@220: deba@220: typedef typename ItemSetTraits deba@220: ::ItemNotifier::ObserverBase Parent; deba@220: deba@220: private: deba@220: deba@220: class AutoNodeMap deba@220: : public ItemSetTraits::template Map::Type { deba@220: public: deba@220: deba@220: typedef typename ItemSetTraits:: deba@220: template Map::Type Parent; deba@220: deba@220: AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} deba@220: deba@220: virtual void add(const Key& key) { deba@220: Parent::add(key); deba@220: Parent::set(key, 0); deba@220: } deba@220: deba@220: virtual void add(const std::vector& keys) { deba@220: Parent::add(keys); deba@220: for (int i = 0; i < int(keys.size()); ++i) { deba@220: Parent::set(keys[i], 0); deba@220: } deba@220: } deba@220: deba@220: virtual void build() { deba@220: Parent::build(); deba@220: Key it; deba@220: typename Parent::Notifier* nf = Parent::notifier(); deba@220: for (nf->first(it); it != INVALID; nf->next(it)) { deba@220: Parent::set(it, 0); deba@220: } deba@220: } deba@220: }; deba@220: deba@220: public: deba@220: deba@220: /// \brief Constructor. deba@220: /// kpeter@550: /// Constructor for creating an in-degree map. kpeter@550: explicit InDegMap(const Digraph& graph) kpeter@550: : _digraph(graph), _deg(graph) { deba@220: Parent::attach(_digraph.notifier(typename Digraph::Arc())); deba@220: deba@220: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@220: _deg[it] = countInArcs(_digraph, it); deba@220: } deba@220: } deba@220: kpeter@550: /// \brief Gives back the in-degree of a Node. kpeter@550: /// deba@220: /// Gives back the in-degree of a Node. deba@220: int operator[](const Key& key) const { deba@220: return _deg[key]; deba@220: } deba@220: deba@220: protected: deba@220: deba@220: typedef typename Digraph::Arc Arc; deba@220: deba@220: virtual void add(const Arc& arc) { deba@220: ++_deg[_digraph.target(arc)]; deba@220: } deba@220: deba@220: virtual void add(const std::vector& arcs) { deba@220: for (int i = 0; i < int(arcs.size()); ++i) { deba@220: ++_deg[_digraph.target(arcs[i])]; deba@220: } deba@220: } deba@220: deba@220: virtual void erase(const Arc& arc) { deba@220: --_deg[_digraph.target(arc)]; deba@220: } deba@220: deba@220: virtual void erase(const std::vector& arcs) { deba@220: for (int i = 0; i < int(arcs.size()); ++i) { deba@220: --_deg[_digraph.target(arcs[i])]; deba@220: } deba@220: } deba@220: deba@220: virtual void build() { deba@220: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@220: _deg[it] = countInArcs(_digraph, it); deba@220: } deba@220: } deba@220: deba@220: virtual void clear() { deba@220: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@220: _deg[it] = 0; deba@220: } deba@220: } deba@220: private: deba@220: deba@220: const Digraph& _digraph; deba@220: AutoNodeMap _deg; deba@220: }; deba@220: kpeter@550: /// \brief Map of the out-degrees of nodes in a digraph. deba@220: /// deba@220: /// This map returns the out-degree of a node. Once it is constructed, kpeter@550: /// the degrees are stored in a standard \c NodeMap, so each query is done deba@220: /// in constant time. On the other hand, the values are updated automatically deba@220: /// whenever the digraph changes. deba@220: /// kpeter@550: /// \warning Besides \c addNode() and \c addArc(), a digraph structure kpeter@550: /// may provide alternative ways to modify the digraph. kpeter@550: /// The correct behavior of OutDegMap is not guarantied if these additional kpeter@550: /// features are used. For example the functions kpeter@550: /// \ref ListDigraph::changeSource() "changeSource()", deba@220: /// \ref ListDigraph::changeTarget() "changeTarget()" and deba@220: /// \ref ListDigraph::reverseArc() "reverseArc()" deba@220: /// of \ref ListDigraph will \e not update the degree values correctly. deba@220: /// deba@220: /// \sa InDegMap kpeter@550: template deba@220: class OutDegMap kpeter@550: : protected ItemSetTraits deba@220: ::ItemNotifier::ObserverBase { deba@220: deba@220: public: deba@220: kpeter@550: /// The digraph type kpeter@550: typedef GR Digraph; kpeter@550: /// The key type kpeter@550: typedef typename Digraph::Node Key; kpeter@550: /// The value type deba@220: typedef int Value; deba@220: deba@220: typedef typename ItemSetTraits deba@220: ::ItemNotifier::ObserverBase Parent; deba@220: deba@220: private: deba@220: deba@220: class AutoNodeMap deba@220: : public ItemSetTraits::template Map::Type { deba@220: public: deba@220: deba@220: typedef typename ItemSetTraits:: deba@220: template Map::Type Parent; deba@220: deba@220: AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} deba@220: deba@220: virtual void add(const Key& key) { deba@220: Parent::add(key); deba@220: Parent::set(key, 0); deba@220: } deba@220: virtual void add(const std::vector& keys) { deba@220: Parent::add(keys); deba@220: for (int i = 0; i < int(keys.size()); ++i) { deba@220: Parent::set(keys[i], 0); deba@220: } deba@220: } deba@220: virtual void build() { deba@220: Parent::build(); deba@220: Key it; deba@220: typename Parent::Notifier* nf = Parent::notifier(); deba@220: for (nf->first(it); it != INVALID; nf->next(it)) { deba@220: Parent::set(it, 0); deba@220: } deba@220: } deba@220: }; deba@220: deba@220: public: deba@220: deba@220: /// \brief Constructor. deba@220: /// kpeter@550: /// Constructor for creating an out-degree map. kpeter@550: explicit OutDegMap(const Digraph& graph) kpeter@550: : _digraph(graph), _deg(graph) { deba@220: Parent::attach(_digraph.notifier(typename Digraph::Arc())); deba@220: deba@220: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@220: _deg[it] = countOutArcs(_digraph, it); deba@220: } deba@220: } deba@220: kpeter@550: /// \brief Gives back the out-degree of a Node. kpeter@550: /// deba@220: /// Gives back the out-degree of a Node. deba@220: int operator[](const Key& key) const { deba@220: return _deg[key]; deba@220: } deba@220: deba@220: protected: deba@220: deba@220: typedef typename Digraph::Arc Arc; deba@220: deba@220: virtual void add(const Arc& arc) { deba@220: ++_deg[_digraph.source(arc)]; deba@220: } deba@220: deba@220: virtual void add(const std::vector& arcs) { deba@220: for (int i = 0; i < int(arcs.size()); ++i) { deba@220: ++_deg[_digraph.source(arcs[i])]; deba@220: } deba@220: } deba@220: deba@220: virtual void erase(const Arc& arc) { deba@220: --_deg[_digraph.source(arc)]; deba@220: } deba@220: deba@220: virtual void erase(const std::vector& arcs) { deba@220: for (int i = 0; i < int(arcs.size()); ++i) { deba@220: --_deg[_digraph.source(arcs[i])]; deba@220: } deba@220: } deba@220: deba@220: virtual void build() { deba@220: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@220: _deg[it] = countOutArcs(_digraph, it); deba@220: } deba@220: } deba@220: deba@220: virtual void clear() { deba@220: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@220: _deg[it] = 0; deba@220: } deba@220: } deba@220: private: deba@220: deba@220: const Digraph& _digraph; deba@220: AutoNodeMap _deg; deba@220: }; deba@220: kpeter@550: /// \brief Potential difference map kpeter@550: /// kpeter@576: /// PotentialDifferenceMap returns the difference between the potentials of kpeter@576: /// the source and target nodes of each arc in a digraph, i.e. it returns kpeter@550: /// \code kpeter@550: /// potential[gr.target(arc)] - potential[gr.source(arc)]. kpeter@550: /// \endcode kpeter@550: /// \tparam GR The digraph type. kpeter@550: /// \tparam POT A node map storing the potentials. kpeter@550: template kpeter@550: class PotentialDifferenceMap { kpeter@550: public: kpeter@550: /// Key type kpeter@550: typedef typename GR::Arc Key; kpeter@550: /// Value type kpeter@550: typedef typename POT::Value Value; kpeter@550: kpeter@550: /// \brief Constructor kpeter@550: /// kpeter@550: /// Contructor of the map. kpeter@550: explicit PotentialDifferenceMap(const GR& gr, kpeter@550: const POT& potential) kpeter@550: : _digraph(gr), _potential(potential) {} kpeter@550: kpeter@550: /// \brief Returns the potential difference for the given arc. kpeter@550: /// kpeter@550: /// Returns the potential difference for the given arc, i.e. kpeter@550: /// \code kpeter@550: /// potential[gr.target(arc)] - potential[gr.source(arc)]. kpeter@550: /// \endcode kpeter@550: Value operator[](const Key& arc) const { kpeter@550: return _potential[_digraph.target(arc)] - kpeter@550: _potential[_digraph.source(arc)]; kpeter@550: } kpeter@550: kpeter@550: private: kpeter@550: const GR& _digraph; kpeter@550: const POT& _potential; kpeter@550: }; kpeter@550: kpeter@550: /// \brief Returns a PotentialDifferenceMap. kpeter@550: /// kpeter@550: /// This function just returns a PotentialDifferenceMap. kpeter@550: /// \relates PotentialDifferenceMap kpeter@550: template kpeter@550: PotentialDifferenceMap kpeter@550: potentialDifferenceMap(const GR& gr, const POT& potential) { kpeter@550: return PotentialDifferenceMap(gr, potential); kpeter@550: } kpeter@550: alpar@25: /// @} alpar@25: } alpar@25: alpar@25: #endif // LEMON_MAPS_H