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@877: * Copyright (C) 2003-2010 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 <iterator> alpar@25: #include <functional> alpar@25: #include <vector> kpeter@694: #include <map> alpar@25: deba@220: #include <lemon/core.h> alpar@25: alpar@25: ///\file alpar@25: ///\ingroup maps alpar@25: ///\brief Miscellaneous property maps kpeter@80: 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<typename K, typename V> 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: /// <tt>/dev/null</tt>). kpeter@722: /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. kpeter@80: /// kpeter@80: /// \sa ConstMap kpeter@80: template<typename K, typename V> kpeter@80: class NullMap : public MapBase<K, V> { alpar@25: public: kpeter@559: ///\e kpeter@559: typedef K Key; kpeter@559: ///\e kpeter@559: 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 <typename K, typename V> alpar@25: NullMap<K, V> nullMap() { alpar@25: return NullMap<K, V>(); 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@722: /// So it conforms to 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<typename K, typename V> kpeter@80: class ConstMap : public MapBase<K, V> { alpar@25: private: kpeter@80: V _value; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef K Key; kpeter@559: ///\e kpeter@559: 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<typename V1> kpeter@80: ConstMap(const ConstMap<K, V1> &, 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<typename K, typename V> alpar@25: inline ConstMap<K, V> constMap(const V &v) { alpar@25: return ConstMap<K, V>(v); alpar@25: } alpar@25: kpeter@123: template<typename K, typename V> kpeter@123: inline ConstMap<K, V> constMap() { kpeter@123: return ConstMap<K, V>(); kpeter@123: } kpeter@123: alpar@25: alpar@25: template<typename T, T v> 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@722: /// So it conforms to 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<typename K, typename V, V v> alpar@25: class ConstMap<K, Const<V, v> > : public MapBase<K, V> { alpar@25: public: kpeter@559: ///\e kpeter@559: typedef K Key; kpeter@559: ///\e kpeter@559: 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<typename K, typename V, V v> alpar@25: inline ConstMap<K, Const<V, v> > constMap() { alpar@25: return ConstMap<K, Const<V, v> >(); 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 <typename T> kpeter@80: class IdentityMap : public MapBase<T, T> { kpeter@80: public: kpeter@559: ///\e kpeter@559: typedef T Key; kpeter@559: ///\e kpeter@559: 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<typename T> kpeter@80: inline IdentityMap<T> identityMap() { kpeter@80: return IdentityMap<T>(); kpeter@80: } kpeter@80: kpeter@80: kpeter@80: /// \brief Map for storing values for integer keys from the range kpeter@80: /// <tt>[0..size-1]</tt>. 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 <tt>[0..size-1]</tt>. kpeter@786: /// It can be used together with some data structures, e.g. kpeter@786: /// heap types and \c UnionFind, when the used items are small kpeter@722: /// integers. This map conforms to the \ref concepts::ReferenceMap alpar@877: /// "ReferenceMap" concept. kpeter@80: /// kpeter@80: /// The simplest way of using this map is through the rangeMap() kpeter@80: /// function. kpeter@80: template <typename V> kpeter@80: class RangeMap : public MapBase<int, V> { kpeter@80: template <typename V1> kpeter@80: friend class RangeMap; kpeter@80: private: kpeter@80: kpeter@80: typedef std::vector<V> Vector; kpeter@80: Vector _vector; kpeter@80: alpar@25: public: alpar@25: kpeter@80: /// Key type kpeter@559: typedef int Key; kpeter@80: /// Value type kpeter@559: 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 <typename V1> kpeter@80: RangeMap(const std::vector<V1>& vector) kpeter@80: : _vector(vector.begin(), vector.end()) {} kpeter@80: kpeter@301: /// Constructs the map from another \c RangeMap. kpeter@80: template <typename V1> kpeter@80: RangeMap(const RangeMap<V1> &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 <tt>[0..size-1]</tt>. 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<typename V> kpeter@80: inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) { kpeter@80: return RangeMap<V>(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<typename V> kpeter@80: inline RangeMap<V> rangeMap(const std::vector<V> &vector) { kpeter@80: return RangeMap<V>(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@722: /// This type conforms to 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@786: /// 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@786: /// 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@559: template <typename K, typename V, typename Comp = std::less<K> > kpeter@80: class SparseMap : public MapBase<K, V> { kpeter@80: template <typename K1, typename V1, typename C1> kpeter@80: friend class SparseMap; kpeter@80: public: kpeter@80: kpeter@80: /// Key type kpeter@559: typedef K Key; kpeter@80: /// Value type kpeter@559: 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@559: typedef std::map<K, V, Comp> 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 <typename V1, typename Comp1> kpeter@80: SparseMap(const std::map<Key, V1, Comp1> &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<typename V1, typename Comp1> kpeter@80: SparseMap(const SparseMap<Key, V1, Comp1> &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<typename K, typename V, typename Compare> kpeter@80: inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) { kpeter@80: return SparseMap<K, V, Compare>(value); kpeter@54: } kpeter@45: kpeter@80: template<typename K, typename V> kpeter@80: inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) { kpeter@80: return SparseMap<K, V, std::less<K> >(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<typename K, typename V, typename Compare> kpeter@80: inline SparseMap<K, V, Compare> kpeter@80: sparseMap(const std::map<K, V, Compare> &map, const V& value = V()) kpeter@80: { kpeter@80: return SparseMap<K, V, Compare>(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<M1, M2> cm(m1,m2); kpeter@80: /// \endcode kpeter@80: /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>. 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 <typename M1, typename M2> kpeter@80: class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M2::Key Key; kpeter@559: ///\e kpeter@559: 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@559: ///\e kpeter@80: typename MapTraits<M1>::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 <tt>composeMap(m1,m2)[x]</tt> kpeter@80: /// will be equal to <tt>m1[m2[x]]</tt>. kpeter@80: /// kpeter@80: /// \relates ComposeMap kpeter@80: template <typename M1, typename M2> kpeter@80: inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) { kpeter@80: return ComposeMap<M1, M2>(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<M1,M2,F,V> cm(m1,m2,f); kpeter@80: /// \endcode kpeter@80: /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>. 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<typename M1, typename M2, typename F, alpar@209: typename V = typename F::result_type> kpeter@80: class CombineMap : public MapBase<typename M1::Key, V> { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; kpeter@80: F _f; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: 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@559: ///\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<double>()) 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<typename M1, typename M2, typename F, typename V> kpeter@80: inline CombineMap<M1, M2, F, V> kpeter@80: combineMap(const M1 &m1, const M2 &m2, const F &f) { kpeter@80: return CombineMap<M1, M2, F, V>(m1,m2,f); alpar@25: } alpar@25: kpeter@80: template<typename M1, typename M2, typename F> kpeter@80: inline CombineMap<M1, M2, F, typename F::result_type> kpeter@80: combineMap(const M1 &m1, const M2 &m2, const F &f) { kpeter@80: return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f); kpeter@80: } alpar@25: kpeter@80: template<typename M1, typename M2, typename K1, typename K2, typename V> kpeter@80: inline CombineMap<M1, M2, V (*)(K1, K2), V> kpeter@80: combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { kpeter@80: return combineMap<M1, M2, V (*)(K1, K2), V>(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<typename F, alpar@209: typename K = typename F::argument_type, alpar@209: typename V = typename F::result_type> kpeter@80: class FunctorToMap : public MapBase<K, V> { kpeter@123: F _f; kpeter@80: public: kpeter@559: ///\e kpeter@559: typedef K Key; kpeter@559: ///\e kpeter@559: typedef V Value; alpar@25: kpeter@80: /// Constructor kpeter@80: FunctorToMap(const F &f = F()) : _f(f) {} kpeter@559: ///\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<typename K, typename V, typename F> kpeter@80: inline FunctorToMap<F, K, V> functorToMap(const F &f) { kpeter@80: return FunctorToMap<F, K, V>(f); kpeter@80: } kpeter@80: kpeter@80: template <typename F> kpeter@80: inline FunctorToMap<F, typename F::argument_type, typename F::result_type> kpeter@80: functorToMap(const F &f) kpeter@80: { kpeter@80: return FunctorToMap<F, typename F::argument_type, kpeter@80: typename F::result_type>(f); kpeter@80: } kpeter@80: kpeter@80: template <typename K, typename V> kpeter@80: inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) { kpeter@80: return FunctorToMap<V (*)(K), K, V>(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 <tt>operator()</tt> 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. <tt>operator[]</tt> 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 <typename M> kpeter@80: class MapToFunctor : public MapBase<typename M::Key, typename M::Value> { kpeter@80: const M &_m; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: typedef typename M::Value Value; kpeter@559: kpeter@559: typedef typename M::Key argument_type; kpeter@559: typedef typename M::Value result_type; kpeter@80: kpeter@80: /// Constructor kpeter@80: MapToFunctor(const M &m) : _m(m) {} kpeter@559: ///\e kpeter@80: Value operator()(const Key &k) const { return _m[k]; } kpeter@559: ///\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<typename M> kpeter@80: inline MapToFunctor<M> mapToFunctor(const M &m) { kpeter@80: return MapToFunctor<M>(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@722: /// This type conforms to 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 <typename M, typename V> kpeter@80: class ConvertMap : public MapBase<typename M::Key, V> { kpeter@80: const M &_m; kpeter@80: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: 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@559: ///\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<typename V, typename M> kpeter@80: inline ConvertMap<M, V> convertMap(const M &map) { kpeter@80: return ConvertMap<M, V>(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<typename M1, typename M2> kpeter@80: class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { kpeter@80: M1 &_m1; kpeter@80: M2 &_m2; kpeter@80: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: 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 <typename M1, typename M2> kpeter@80: inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) { kpeter@80: return ForkMap<M1,M2>(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<M1,M2> am(m1,m2); kpeter@80: /// \endcode kpeter@80: /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>. 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<typename M1, typename M2> alpar@25: class AddMap : public MapBase<typename M1::Key, typename M1::Value> { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: typedef typename M1::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@559: ///\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 <tt>addMap(m1,m2)[x]</tt> will be equal to kpeter@80: /// <tt>m1[x]+m2[x]</tt>. kpeter@80: /// kpeter@80: /// \relates AddMap kpeter@80: template<typename M1, typename M2> kpeter@80: inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) { alpar@25: return AddMap<M1, M2>(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<M1,M2> sm(m1,m2); kpeter@80: /// \endcode kpeter@80: /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>. 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<typename M1, typename M2> kpeter@80: class SubMap : public MapBase<typename M1::Key, typename M1::Value> { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; kpeter@80: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: typedef typename M1::Value Value; kpeter@80: kpeter@80: /// Constructor kpeter@80: SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@559: ///\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 <tt>subMap(m1,m2)[x]</tt> will be equal to kpeter@80: /// <tt>m1[x]-m2[x]</tt>. kpeter@80: /// kpeter@80: /// \relates SubMap kpeter@80: template<typename M1, typename M2> kpeter@80: inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) { kpeter@80: return SubMap<M1, M2>(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<M1,M2> mm(m1,m2); kpeter@80: /// \endcode kpeter@80: /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>. 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<typename M1, typename M2> kpeter@80: class MulMap : public MapBase<typename M1::Key, typename M1::Value> { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; kpeter@80: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: typedef typename M1::Value Value; kpeter@80: kpeter@80: /// Constructor kpeter@80: MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@559: ///\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 <tt>mulMap(m1,m2)[x]</tt> will be equal to kpeter@80: /// <tt>m1[x]*m2[x]</tt>. kpeter@80: /// kpeter@80: /// \relates MulMap kpeter@80: template<typename M1, typename M2> kpeter@80: inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) { kpeter@80: return MulMap<M1, M2>(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<M1,M2> dm(m1,m2); kpeter@80: /// \endcode kpeter@80: /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>. 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<typename M1, typename M2> kpeter@80: class DivMap : public MapBase<typename M1::Key, typename M1::Value> { kpeter@80: const M1 &_m1; kpeter@80: const M2 &_m2; kpeter@80: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: typedef typename M1::Value Value; kpeter@80: kpeter@80: /// Constructor kpeter@80: DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@559: ///\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 <tt>divMap(m1,m2)[x]</tt> will be equal to kpeter@80: /// <tt>m1[x]/m2[x]</tt>. kpeter@80: /// kpeter@80: /// \relates DivMap kpeter@80: template<typename M1, typename M2> kpeter@80: inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) { kpeter@80: return DivMap<M1, M2>(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<M> sh(m,v); kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// ConstMap<M::Key, M::Value> cm(v); kpeter@80: /// AddMap<M, ConstMap<M::Key, M::Value> > 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<typename M, typename C = typename M::Value> alpar@25: class ShiftMap : public MapBase<typename M::Key, typename M::Value> { kpeter@80: const M &_m; kpeter@80: C _v; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: 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@559: ///\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<typename M, typename C = typename M::Value> alpar@25: class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> { kpeter@80: M &_m; kpeter@80: C _v; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: 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@559: ///\e kpeter@80: Value operator[](const Key &k) const { return _m[k]+_v; } kpeter@559: ///\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 <tt>shiftMap(m,v)[x]</tt> will be equal to kpeter@80: /// <tt>m[x]+v</tt>. kpeter@80: /// kpeter@80: /// \relates ShiftMap kpeter@80: template<typename M, typename C> kpeter@80: inline ShiftMap<M, C> shiftMap(const M &m, const C &v) { alpar@25: return ShiftMap<M, C>(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 <tt>shiftWriteMap(m,v)[x]</tt> will be equal to kpeter@80: /// <tt>m[x]+v</tt>. kpeter@80: /// Moreover it makes also possible to write the map. kpeter@80: /// kpeter@80: /// \relates ShiftWriteMap kpeter@80: template<typename M, typename C> kpeter@80: inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) { alpar@25: return ShiftWriteMap<M, C>(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<M> sc(m,v); kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// ConstMap<M::Key, M::Value> cm(v); kpeter@80: /// MulMap<ConstMap<M::Key, M::Value>, 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<typename M, typename C = typename M::Value> alpar@25: class ScaleMap : public MapBase<typename M::Key, typename M::Value> { kpeter@80: const M &_m; kpeter@80: C _v; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: 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@559: ///\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<typename M, typename C = typename M::Value> alpar@25: class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> { kpeter@80: M &_m; kpeter@80: C _v; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: 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@559: ///\e kpeter@80: Value operator[](const Key &k) const { return _v*_m[k]; } kpeter@559: ///\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 <tt>scaleMap(m,v)[x]</tt> will be equal to kpeter@80: /// <tt>v*m[x]</tt>. kpeter@80: /// kpeter@80: /// \relates ScaleMap kpeter@80: template<typename M, typename C> kpeter@80: inline ScaleMap<M, C> scaleMap(const M &m, const C &v) { alpar@25: return ScaleMap<M, C>(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 <tt>scaleWriteMap(m,v)[x]</tt> will be equal to kpeter@80: /// <tt>v*m[x]</tt>. kpeter@80: /// Moreover it makes also possible to write the map. kpeter@80: /// kpeter@80: /// \relates ScaleWriteMap kpeter@80: template<typename M, typename C> kpeter@80: inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) { alpar@25: return ScaleWriteMap<M, C>(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<M> neg(m); kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// ScaleMap<M> 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<typename M> alpar@25: class NegMap : public MapBase<typename M::Key, typename M::Value> { kpeter@80: const M& _m; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: NegMap(const M &m) : _m(m) {} kpeter@559: ///\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<M> neg(m); kpeter@80: /// \endcode kpeter@80: /// is equivalent to kpeter@80: /// \code kpeter@80: /// ScaleWriteMap<M> 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<typename M> alpar@25: class NegWriteMap : public MapBase<typename M::Key, typename M::Value> { kpeter@80: M &_m; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: NegWriteMap(M &m) : _m(m) {} kpeter@559: ///\e kpeter@80: Value operator[](const Key &k) const { return -_m[k]; } kpeter@559: ///\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: /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>. kpeter@80: /// kpeter@80: /// \relates NegMap kpeter@80: template <typename M> alpar@25: inline NegMap<M> negMap(const M &m) { alpar@25: return NegMap<M>(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: /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>. kpeter@80: /// Moreover it makes also possible to write the map. kpeter@80: /// kpeter@80: /// \relates NegWriteMap kpeter@80: template <typename M> kpeter@80: inline NegWriteMap<M> negWriteMap(M &m) { alpar@25: return NegWriteMap<M>(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<typename M> alpar@25: class AbsMap : public MapBase<typename M::Key, typename M::Value> { kpeter@80: const M &_m; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: typedef typename M::Value Value; alpar@25: kpeter@80: /// Constructor kpeter@80: AbsMap(const M &m) : _m(m) {} kpeter@559: ///\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: /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if kpeter@80: /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is kpeter@80: /// negative. kpeter@80: /// kpeter@80: /// \relates AbsMap kpeter@80: template<typename M> alpar@25: inline AbsMap<M> absMap(const M &m) { alpar@25: return AbsMap<M>(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<K> tm; kpeter@82: /// \endcode kpeter@82: /// is equivalent to kpeter@82: /// \code kpeter@82: /// ConstMap<K,bool> tm(true); kpeter@82: /// \endcode kpeter@82: /// kpeter@82: /// \sa FalseMap kpeter@82: /// \sa ConstMap kpeter@82: template <typename K> kpeter@82: class TrueMap : public MapBase<K, bool> { kpeter@82: public: kpeter@559: ///\e kpeter@559: typedef K Key; kpeter@559: ///\e kpeter@559: 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<typename K> kpeter@82: inline TrueMap<K> trueMap() { kpeter@82: return TrueMap<K>(); 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<K> fm; kpeter@82: /// \endcode kpeter@82: /// is equivalent to kpeter@82: /// \code kpeter@82: /// ConstMap<K,bool> fm(false); kpeter@82: /// \endcode kpeter@82: /// kpeter@82: /// \sa TrueMap kpeter@82: /// \sa ConstMap kpeter@82: template <typename K> kpeter@82: class FalseMap : public MapBase<K, bool> { kpeter@82: public: kpeter@559: ///\e kpeter@559: typedef K Key; kpeter@559: ///\e kpeter@559: 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<typename K> kpeter@82: inline FalseMap<K> falseMap() { kpeter@82: return FalseMap<K>(); 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<M1,M2> am(m1,m2); kpeter@82: /// \endcode kpeter@82: /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>. 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<typename M1, typename M2> kpeter@82: class AndMap : public MapBase<typename M1::Key, bool> { kpeter@82: const M1 &_m1; kpeter@82: const M2 &_m2; kpeter@82: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: typedef bool Value; kpeter@82: kpeter@82: /// Constructor kpeter@82: AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@559: ///\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 <tt>andMap(m1,m2)[x]</tt> will be equal to kpeter@82: /// <tt>m1[x]&&m2[x]</tt>. kpeter@82: /// kpeter@82: /// \relates AndMap kpeter@82: template<typename M1, typename M2> kpeter@82: inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) { kpeter@82: return AndMap<M1, M2>(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<M1,M2> om(m1,m2); kpeter@82: /// \endcode kpeter@82: /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>. 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<typename M1, typename M2> kpeter@82: class OrMap : public MapBase<typename M1::Key, bool> { kpeter@82: const M1 &_m1; kpeter@82: const M2 &_m2; kpeter@82: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: typedef bool Value; kpeter@82: kpeter@82: /// Constructor kpeter@82: OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@559: ///\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 <tt>orMap(m1,m2)[x]</tt> will be equal to kpeter@82: /// <tt>m1[x]||m2[x]</tt>. kpeter@82: /// kpeter@82: /// \relates OrMap kpeter@82: template<typename M1, typename M2> kpeter@82: inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) { kpeter@82: return OrMap<M1, M2>(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 <typename M> alpar@25: class NotMap : public MapBase<typename M::Key, bool> { kpeter@80: const M &_m; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: typedef bool Value; alpar@25: alpar@25: /// Constructor kpeter@80: NotMap(const M &m) : _m(m) {} kpeter@559: ///\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 <typename M> alpar@25: class NotWriteMap : public MapBase<typename M::Key, bool> { kpeter@80: M &_m; alpar@25: public: kpeter@559: ///\e kpeter@559: typedef typename M::Key Key; kpeter@559: ///\e kpeter@559: typedef bool Value; alpar@25: alpar@25: /// Constructor kpeter@80: NotWriteMap(M &m) : _m(m) {} kpeter@559: ///\e kpeter@80: Value operator[](const Key &k) const { return !_m[k]; } kpeter@559: ///\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: /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>. kpeter@80: /// kpeter@80: /// \relates NotMap kpeter@80: template <typename M> alpar@25: inline NotMap<M> notMap(const M &m) { alpar@25: return NotMap<M>(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: /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>. kpeter@80: /// Moreover it makes also possible to write the map. kpeter@80: /// kpeter@80: /// \relates NotWriteMap kpeter@80: template <typename M> kpeter@80: inline NotWriteMap<M> notWriteMap(M &m) { alpar@25: return NotWriteMap<M>(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<M1,M2> em(m1,m2); kpeter@82: /// \endcode kpeter@82: /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>. 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<typename M1, typename M2> kpeter@82: class EqualMap : public MapBase<typename M1::Key, bool> { kpeter@82: const M1 &_m1; kpeter@82: const M2 &_m2; kpeter@82: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: typedef bool Value; kpeter@82: kpeter@82: /// Constructor kpeter@82: EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@559: ///\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 <tt>equalMap(m1,m2)[x]</tt> will be equal to kpeter@82: /// <tt>m1[x]==m2[x]</tt>. kpeter@82: /// kpeter@82: /// \relates EqualMap kpeter@82: template<typename M1, typename M2> kpeter@82: inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) { kpeter@82: return EqualMap<M1, M2>(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<M1,M2> lm(m1,m2); kpeter@82: /// \endcode kpeter@82: /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>. 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<typename M1, typename M2> kpeter@82: class LessMap : public MapBase<typename M1::Key, bool> { kpeter@82: const M1 &_m1; kpeter@82: const M2 &_m2; kpeter@82: public: kpeter@559: ///\e kpeter@559: typedef typename M1::Key Key; kpeter@559: ///\e kpeter@559: typedef bool Value; kpeter@82: kpeter@82: /// Constructor kpeter@82: LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} kpeter@559: ///\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 <tt>lessMap(m1,m2)[x]</tt> will be equal to kpeter@82: /// <tt>m1[x]<m2[x]</tt>. kpeter@82: /// kpeter@82: /// \relates LessMap kpeter@82: template<typename M1, typename M2> kpeter@82: inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) { kpeter@82: return LessMap<M1, M2>(m1,m2); kpeter@82: } kpeter@82: alpar@104: namespace _maps_bits { alpar@104: alpar@104: template <typename _Iterator, typename Enable = void> alpar@104: struct IteratorTraits { alpar@104: typedef typename std::iterator_traits<_Iterator>::value_type Value; alpar@104: }; alpar@104: alpar@104: template <typename _Iterator> alpar@104: struct IteratorTraits<_Iterator, alpar@104: typename exists<typename _Iterator::container_type>::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@559: /// \tparam IT The type of the iterator. kpeter@559: /// \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@559: template <typename IT, typename KEY> kpeter@159: #else kpeter@559: template <typename IT, kpeter@559: typename KEY = typename _maps_bits::IteratorTraits<IT>::Value> kpeter@159: #endif kpeter@559: class LoggerBoolMap : public MapBase<KEY, bool> { alpar@104: public: kpeter@559: kpeter@559: ///\e kpeter@559: typedef KEY Key; kpeter@559: ///\e alpar@104: typedef bool Value; kpeter@559: ///\e kpeter@559: 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@786: /// 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<Node> v; kpeter@716: /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s); kpeter@159: /// \endcode kpeter@159: /// \code kpeter@159: /// std::vector<Node> v(countNodes(g)); kpeter@716: /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s); 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@786: /// 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<typename Iterator> kpeter@167: inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) { kpeter@167: return LoggerBoolMap<Iterator>(it); kpeter@159: } alpar@104: kpeter@314: /// @} kpeter@314: kpeter@314: /// \addtogroup graph_maps kpeter@314: /// @{ kpeter@314: kpeter@559: /// \brief Provides an immutable and unique id for each item in a graph. kpeter@559: /// kpeter@559: /// IdMap provides a unique and immutable id for each item of the deba@693: /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is kpeter@559: /// - \b unique: different items get different ids, kpeter@559: /// - \b immutable: the id of an item does not change (even if you kpeter@559: /// delete other nodes). kpeter@559: /// kpeter@559: /// Using this map you get access (i.e. can read) the inner id values of kpeter@559: /// the items stored in the graph, which is returned by the \c id() kpeter@559: /// function of the graph. This map can be inverted with its member kpeter@720: /// class \c InverseMap or with the \c operator()() member. deba@220: /// kpeter@559: /// \tparam GR The graph type. kpeter@559: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@559: /// \c GR::Edge). kpeter@559: /// alpar@572: /// \see RangeIdMap kpeter@559: template <typename GR, typename K> kpeter@559: class IdMap : public MapBase<K, int> { deba@220: public: kpeter@559: /// The graph type of IdMap. kpeter@559: typedef GR Graph; kpeter@617: typedef GR Digraph; kpeter@559: /// The key type of IdMap (\c Node, \c Arc or \c Edge). kpeter@559: typedef K Item; kpeter@559: /// The key type of IdMap (\c Node, \c Arc or \c Edge). kpeter@559: typedef K Key; kpeter@559: /// 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@559: /// \brief Gives back the \e item by its id. deba@220: /// kpeter@559: /// 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@722: /// \brief The inverse map type of IdMap. deba@220: /// kpeter@722: /// The inverse map type of IdMap. The subscript operator gives back kpeter@722: /// an item by its id. kpeter@722: /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. 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: kpeter@722: /// \brief Gives back an item by its id. deba@220: /// kpeter@722: /// Gives back an item by 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: kpeter@725: /// \brief Returns an \c IdMap class. kpeter@725: /// kpeter@725: /// This function just returns an \c IdMap class. kpeter@725: /// \relates IdMap kpeter@725: template <typename K, typename GR> kpeter@725: inline IdMap<GR, K> idMap(const GR& graph) { kpeter@725: return IdMap<GR, K>(graph); kpeter@725: } deba@220: alpar@572: /// \brief General cross reference graph map type. kpeter@559: kpeter@559: /// This class provides simple invertable graph maps. kpeter@684: /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) kpeter@684: /// and if a key is set to a new value, then stores it in the inverse map. kpeter@722: /// The graph items can be accessed by their values either using kpeter@722: /// \c InverseMap or \c operator()(), and the values of the map can be kpeter@724: /// accessed with an STL compatible forward iterator (\c ValueIt). alpar@877: /// kpeter@722: /// This map is intended to be used when all associated values are kpeter@722: /// different (the map is actually invertable) or there are only a few kpeter@722: /// items with the same value. alpar@877: /// Otherwise consider to use \c IterableValueMap, which is more kpeter@722: /// suitable and more efficient for such cases. It provides iterators kpeter@786: /// to traverse the items with the same associated value, but kpeter@722: /// it does not have \c InverseMap. deba@220: /// kpeter@694: /// This type is not reference map, so it cannot be modified with kpeter@684: /// the subscript operator. kpeter@694: /// kpeter@559: /// \tparam GR The graph type. kpeter@559: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@559: /// \c GR::Edge). kpeter@559: /// \tparam V The value type of the map. deba@220: /// deba@220: /// \see IterableValueMap kpeter@559: template <typename GR, typename K, typename V> alpar@572: class CrossRefMap kpeter@559: : protected ItemSetTraits<GR, K>::template Map<V>::Type { deba@220: private: deba@220: kpeter@559: typedef typename ItemSetTraits<GR, K>:: kpeter@559: template Map<V>::Type Map; kpeter@559: kpeter@684: typedef std::multimap<V, K> Container; deba@220: Container _inv_map; deba@220: deba@220: public: deba@220: alpar@572: /// The graph type of CrossRefMap. kpeter@559: typedef GR Graph; kpeter@617: typedef GR Digraph; alpar@572: /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge). kpeter@559: typedef K Item; alpar@572: /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge). kpeter@559: typedef K Key; alpar@572: /// The value type of CrossRefMap. kpeter@559: typedef V Value; deba@220: deba@220: /// \brief Constructor. deba@220: /// alpar@572: /// Construct a new CrossRefMap for the given graph. alpar@572: explicit CrossRefMap(const Graph& graph) : Map(graph) {} deba@220: deba@220: /// \brief Forward iterator for values. deba@220: /// kpeter@722: /// This iterator is an STL compatible forward deba@220: /// iterator on the values of the map. The values can kpeter@559: /// be accessed in the <tt>[beginValue, endValue)</tt> range. kpeter@684: /// They are considered with multiplicity, so each value is kpeter@684: /// traversed for each item it is assigned to. kpeter@724: class ValueIt deba@220: : public std::iterator<std::forward_iterator_tag, Value> { alpar@572: friend class CrossRefMap; deba@220: private: kpeter@724: ValueIt(typename Container::const_iterator _it) deba@220: : it(_it) {} deba@220: public: deba@220: kpeter@722: /// Constructor kpeter@724: ValueIt() {} kpeter@694: kpeter@722: /// \e kpeter@724: ValueIt& operator++() { ++it; return *this; } kpeter@722: /// \e kpeter@724: ValueIt operator++(int) { kpeter@724: ValueIt tmp(*this); deba@220: operator++(); deba@220: return tmp; deba@220: } deba@220: kpeter@722: /// \e deba@220: const Value& operator*() const { return it->first; } kpeter@722: /// \e deba@220: const Value* operator->() const { return &(it->first); } deba@220: kpeter@722: /// \e kpeter@724: bool operator==(ValueIt jt) const { return it == jt.it; } kpeter@722: /// \e kpeter@724: bool operator!=(ValueIt jt) const { return it != jt.it; } deba@220: deba@220: private: deba@220: typename Container::const_iterator it; deba@220: }; alpar@877: kpeter@724: /// Alias for \c ValueIt kpeter@724: typedef ValueIt ValueIterator; deba@220: deba@220: /// \brief Returns an iterator to the first value. deba@220: /// kpeter@722: /// Returns an STL compatible iterator to the deba@220: /// first value of the map. The values of the kpeter@559: /// map can be accessed in the <tt>[beginValue, endValue)</tt> deba@220: /// range. kpeter@724: ValueIt beginValue() const { kpeter@724: return ValueIt(_inv_map.begin()); deba@220: } deba@220: deba@220: /// \brief Returns an iterator after the last value. deba@220: /// kpeter@722: /// Returns an STL compatible iterator after the deba@220: /// last value of the map. The values of the kpeter@559: /// map can be accessed in the <tt>[beginValue, endValue)</tt> deba@220: /// range. kpeter@724: ValueIt endValue() const { kpeter@724: return ValueIt(_inv_map.end()); deba@220: } deba@220: kpeter@559: /// \brief Sets the value associated with the given key. deba@220: /// kpeter@559: /// 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); kpeter@684: typename Container::iterator it; kpeter@684: for (it = _inv_map.equal_range(oldval).first; kpeter@684: it != _inv_map.equal_range(oldval).second; ++it) { kpeter@684: if (it->second == key) { kpeter@684: _inv_map.erase(it); kpeter@684: break; kpeter@684: } deba@220: } deba@693: _inv_map.insert(std::make_pair(val, key)); deba@220: Map::set(key, val); deba@220: } deba@220: kpeter@559: /// \brief Returns the value associated with the given key. deba@220: /// kpeter@559: /// Returns the value associated with the given key. deba@220: typename MapTraits<Map>::ConstReturnValue deba@220: operator[](const Key& key) const { deba@220: return Map::operator[](key); deba@220: } deba@220: kpeter@684: /// \brief Gives back an item by its value. deba@220: /// kpeter@684: /// This function gives back an item that is assigned to kpeter@684: /// the given value or \c INVALID if no such item exists. kpeter@684: /// If there are more items with the same associated value, kpeter@684: /// only one of them is returned. kpeter@684: Key operator()(const Value& val) const { kpeter@684: typename Container::const_iterator it = _inv_map.find(val); deba@220: return it != _inv_map.end() ? it->second : INVALID; deba@220: } alpar@877: kpeter@720: /// \brief Returns the number of items with the given value. kpeter@720: /// kpeter@720: /// This function returns the number of items with the given value kpeter@720: /// associated with it. kpeter@720: int count(const Value &val) const { kpeter@720: return _inv_map.count(val); kpeter@720: } deba@220: deba@220: protected: deba@220: kpeter@559: /// \brief Erase the key from the map and the inverse map. deba@220: /// kpeter@559: /// 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); kpeter@684: typename Container::iterator it; kpeter@684: for (it = _inv_map.equal_range(val).first; kpeter@684: it != _inv_map.equal_range(val).second; ++it) { kpeter@684: if (it->second == key) { kpeter@684: _inv_map.erase(it); kpeter@684: break; kpeter@684: } deba@220: } deba@220: Map::erase(key); deba@220: } deba@220: kpeter@559: /// \brief Erase more keys from the map and the inverse map. deba@220: /// kpeter@559: /// 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<Key>& keys) { deba@220: for (int i = 0; i < int(keys.size()); ++i) { deba@220: Value val = Map::operator[](keys[i]); kpeter@684: typename Container::iterator it; kpeter@684: for (it = _inv_map.equal_range(val).first; kpeter@684: it != _inv_map.equal_range(val).second; ++it) { kpeter@684: if (it->second == keys[i]) { kpeter@684: _inv_map.erase(it); kpeter@684: break; kpeter@684: } deba@220: } deba@220: } deba@220: Map::erase(keys); deba@220: } deba@220: kpeter@559: /// \brief Clear the keys from the map and the inverse map. deba@220: /// kpeter@559: /// 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: kpeter@722: /// \brief The inverse map type of CrossRefMap. deba@220: /// kpeter@722: /// The inverse map type of CrossRefMap. The subscript operator gives kpeter@722: /// back an item by its value. kpeter@722: /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. kpeter@722: /// \see inverse() deba@220: class InverseMap { deba@220: public: kpeter@559: /// \brief Constructor deba@220: /// deba@220: /// Constructor of the InverseMap. alpar@572: explicit InverseMap(const CrossRefMap& inverted) deba@220: : _inverted(inverted) {} deba@220: deba@220: /// The value type of the InverseMap. alpar@572: typedef typename CrossRefMap::Key Value; deba@220: /// The key type of the InverseMap. alpar@572: typedef typename CrossRefMap::Value Key; deba@220: deba@220: /// \brief Subscript operator. deba@220: /// kpeter@684: /// Subscript operator. It gives back an item kpeter@684: /// that is assigned to the given value or \c INVALID kpeter@684: /// if no such item exists. deba@220: Value operator[](const Key& key) const { deba@220: return _inverted(key); deba@220: } deba@220: deba@220: private: alpar@572: const CrossRefMap& _inverted; deba@220: }; deba@220: kpeter@722: /// \brief Gives back the inverse of the map. deba@220: /// kpeter@722: /// Gives back the inverse of the CrossRefMap. deba@220: InverseMap inverse() const { deba@220: return InverseMap(*this); deba@220: } deba@220: deba@220: }; deba@220: kpeter@720: /// \brief Provides continuous and unique id for the alpar@572: /// items of a graph. deba@220: /// alpar@572: /// RangeIdMap provides a unique and continuous kpeter@720: /// id for each item of a given type (\c Node, \c Arc or kpeter@559: /// \c Edge) in a graph. This id is kpeter@559: /// - \b unique: different items get different ids, kpeter@559: /// - \b continuous: the range of the ids is the set of integers kpeter@559: /// between 0 and \c n-1, where \c n is the number of the items of alpar@572: /// this type (\c Node, \c Arc or \c Edge). alpar@572: /// - So, the ids can change when deleting an item of the same type. deba@220: /// kpeter@559: /// Thus this id is not (necessarily) the same as what can get using kpeter@559: /// the \c id() function of the graph or \ref IdMap. kpeter@559: /// This map can be inverted with its member class \c InverseMap, kpeter@720: /// or with the \c operator()() member. kpeter@559: /// kpeter@559: /// \tparam GR The graph type. kpeter@559: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@559: /// \c GR::Edge). kpeter@559: /// kpeter@559: /// \see IdMap kpeter@559: template <typename GR, typename K> alpar@572: class RangeIdMap kpeter@559: : protected ItemSetTraits<GR, K>::template Map<int>::Type { kpeter@559: kpeter@559: typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map; deba@220: deba@220: public: alpar@572: /// The graph type of RangeIdMap. kpeter@559: typedef GR Graph; kpeter@617: typedef GR Digraph; alpar@572: /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge). kpeter@559: typedef K Item; alpar@572: /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge). kpeter@559: typedef K Key; alpar@572: /// The value type of RangeIdMap. kpeter@559: typedef int Value; deba@220: deba@220: /// \brief Constructor. deba@220: /// alpar@572: /// Constructor. alpar@572: 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@559: /// \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<Item>& 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<Item>& 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: kpeter@722: /// \brief Gives back the \e range \e id of the item deba@220: /// kpeter@722: /// Gives back the \e range \e id of the item. deba@220: int operator[](const Item& item) const { deba@220: return Map::operator[](item); deba@220: } deba@220: kpeter@722: /// \brief Gives back the item belonging to a \e range \e id deba@693: /// kpeter@722: /// Gives back the item belonging to the given \e range \e id. 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<Item> Container; deba@220: Container _inv_map; deba@220: deba@220: public: kpeter@559: alpar@572: /// \brief The inverse map type of RangeIdMap. deba@220: /// kpeter@722: /// The inverse map type of RangeIdMap. The subscript operator gives kpeter@722: /// back an item by its \e range \e id. kpeter@722: /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. deba@220: class InverseMap { deba@220: public: kpeter@559: /// \brief Constructor deba@220: /// deba@220: /// Constructor of the InverseMap. alpar@572: explicit InverseMap(const RangeIdMap& inverted) deba@220: : _inverted(inverted) {} deba@220: deba@220: deba@220: /// The value type of the InverseMap. alpar@572: typedef typename RangeIdMap::Key Value; deba@220: /// The key type of the InverseMap. alpar@572: typedef typename RangeIdMap::Value Key; deba@220: deba@220: /// \brief Subscript operator. deba@220: /// deba@220: /// Subscript operator. It gives back the item kpeter@722: /// that the given \e range \e id 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@572: const RangeIdMap& _inverted; deba@220: }; deba@220: deba@220: /// \brief Gives back the inverse of the map. deba@220: /// kpeter@722: /// Gives back the inverse of the RangeIdMap. deba@220: const InverseMap inverse() const { deba@220: return InverseMap(*this); deba@220: } deba@220: }; deba@220: kpeter@725: /// \brief Returns a \c RangeIdMap class. kpeter@725: /// kpeter@725: /// This function just returns an \c RangeIdMap class. kpeter@725: /// \relates RangeIdMap kpeter@725: template <typename K, typename GR> kpeter@725: inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) { kpeter@725: return RangeIdMap<GR, K>(graph); kpeter@725: } alpar@877: kpeter@694: /// \brief Dynamic iterable \c bool map. deba@693: /// kpeter@694: /// This class provides a special graph map type which can store a kpeter@694: /// \c bool value for graph items (\c Node, \c Arc or \c Edge). kpeter@694: /// For both \c true and \c false values it is possible to iterate on kpeter@722: /// the keys mapped to the value. deba@693: /// kpeter@694: /// This type is a reference map, so it can be modified with the alpar@695: /// subscript operator. kpeter@694: /// kpeter@694: /// \tparam GR The graph type. kpeter@694: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@694: /// \c GR::Edge). kpeter@694: /// kpeter@694: /// \see IterableIntMap, IterableValueMap kpeter@694: /// \see CrossRefMap kpeter@694: template <typename GR, typename K> deba@693: class IterableBoolMap kpeter@694: : protected ItemSetTraits<GR, K>::template Map<int>::Type { deba@693: private: deba@693: typedef GR Graph; deba@693: kpeter@694: typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt; kpeter@694: typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent; kpeter@694: kpeter@694: std::vector<K> _array; deba@693: int _sep; deba@693: deba@693: public: deba@693: kpeter@694: /// Indicates that the map is reference map. deba@693: typedef True ReferenceMapTag; deba@693: deba@693: /// The key type kpeter@694: typedef K Key; deba@693: /// The value type deba@693: typedef bool Value; deba@693: /// The const reference type. deba@693: typedef const Value& ConstReference; deba@693: deba@693: private: deba@693: deba@693: int position(const Key& key) const { deba@693: return Parent::operator[](key); deba@693: } deba@693: deba@693: public: deba@693: kpeter@694: /// \brief Reference to the value of the map. deba@693: /// kpeter@694: /// This class is similar to the \c bool type. It can be converted to kpeter@694: /// \c bool and it provides the same operators. deba@693: class Reference { deba@693: friend class IterableBoolMap; deba@693: private: deba@693: Reference(IterableBoolMap& map, const Key& key) deba@693: : _key(key), _map(map) {} deba@693: public: deba@693: deba@693: Reference& operator=(const Reference& value) { deba@693: _map.set(_key, static_cast<bool>(value)); deba@693: return *this; deba@693: } deba@693: deba@693: operator bool() const { deba@693: return static_cast<const IterableBoolMap&>(_map)[_key]; deba@693: } deba@693: deba@693: Reference& operator=(bool value) { deba@693: _map.set(_key, value); deba@693: return *this; deba@693: } deba@693: Reference& operator&=(bool value) { deba@693: _map.set(_key, _map[_key] & value); deba@693: return *this; deba@693: } deba@693: Reference& operator|=(bool value) { deba@693: _map.set(_key, _map[_key] | value); deba@693: return *this; deba@693: } deba@693: Reference& operator^=(bool value) { deba@693: _map.set(_key, _map[_key] ^ value); deba@693: return *this; deba@693: } deba@693: private: deba@693: Key _key; deba@693: IterableBoolMap& _map; deba@693: }; deba@693: deba@693: /// \brief Constructor of the map with a default value. deba@693: /// deba@693: /// Constructor of the map with a default value. deba@693: explicit IterableBoolMap(const Graph& graph, bool def = false) deba@693: : Parent(graph) { deba@693: typename Parent::Notifier* nf = Parent::notifier(); deba@693: Key it; deba@693: for (nf->first(it); it != INVALID; nf->next(it)) { deba@693: Parent::set(it, _array.size()); deba@693: _array.push_back(it); deba@693: } deba@693: _sep = (def ? _array.size() : 0); deba@693: } deba@693: deba@693: /// \brief Const subscript operator of the map. deba@693: /// deba@693: /// Const subscript operator of the map. deba@693: bool operator[](const Key& key) const { deba@693: return position(key) < _sep; deba@693: } deba@693: deba@693: /// \brief Subscript operator of the map. deba@693: /// deba@693: /// Subscript operator of the map. deba@693: Reference operator[](const Key& key) { deba@693: return Reference(*this, key); deba@693: } deba@693: deba@693: /// \brief Set operation of the map. deba@693: /// deba@693: /// Set operation of the map. deba@693: void set(const Key& key, bool value) { deba@693: int pos = position(key); deba@693: if (value) { deba@693: if (pos < _sep) return; deba@693: Key tmp = _array[_sep]; deba@693: _array[_sep] = key; deba@693: Parent::set(key, _sep); deba@693: _array[pos] = tmp; deba@693: Parent::set(tmp, pos); deba@693: ++_sep; deba@693: } else { deba@693: if (pos >= _sep) return; deba@693: --_sep; deba@693: Key tmp = _array[_sep]; deba@693: _array[_sep] = key; deba@693: Parent::set(key, _sep); deba@693: _array[pos] = tmp; deba@693: Parent::set(tmp, pos); deba@693: } deba@693: } deba@693: deba@693: /// \brief Set all items. deba@693: /// deba@693: /// Set all items in the map. deba@693: /// \note Constant time operation. deba@693: void setAll(bool value) { deba@693: _sep = (value ? _array.size() : 0); deba@693: } deba@693: kpeter@694: /// \brief Returns the number of the keys mapped to \c true. deba@693: /// kpeter@694: /// Returns the number of the keys mapped to \c true. deba@693: int trueNum() const { deba@693: return _sep; deba@693: } deba@693: kpeter@694: /// \brief Returns the number of the keys mapped to \c false. deba@693: /// kpeter@694: /// Returns the number of the keys mapped to \c false. deba@693: int falseNum() const { deba@693: return _array.size() - _sep; deba@693: } deba@693: kpeter@694: /// \brief Iterator for the keys mapped to \c true. deba@693: /// kpeter@694: /// Iterator for the keys mapped to \c true. It works kpeter@694: /// like a graph item iterator, it can be converted to deba@693: /// the key type of the map, incremented with \c ++ operator, and kpeter@694: /// if the iterator leaves the last valid key, it will be equal to deba@693: /// \c INVALID. deba@693: class TrueIt : public Key { deba@693: public: deba@693: typedef Key Parent; deba@693: deba@693: /// \brief Creates an iterator. deba@693: /// deba@693: /// Creates an iterator. It iterates on the kpeter@694: /// keys mapped to \c true. kpeter@694: /// \param map The IterableBoolMap. deba@693: explicit TrueIt(const IterableBoolMap& map) deba@693: : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID), deba@693: _map(&map) {} deba@693: deba@693: /// \brief Invalid constructor \& conversion. deba@693: /// kpeter@694: /// This constructor initializes the iterator to be invalid. deba@693: /// \sa Invalid for more details. deba@693: TrueIt(Invalid) : Parent(INVALID), _map(0) {} deba@693: deba@693: /// \brief Increment operator. deba@693: /// kpeter@694: /// Increment operator. deba@693: TrueIt& operator++() { deba@693: int pos = _map->position(*this); deba@693: Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID); deba@693: return *this; deba@693: } deba@693: deba@693: private: deba@693: const IterableBoolMap* _map; deba@693: }; deba@693: kpeter@694: /// \brief Iterator for the keys mapped to \c false. deba@693: /// kpeter@694: /// Iterator for the keys mapped to \c false. It works kpeter@694: /// like a graph item iterator, it can be converted to deba@693: /// the key type of the map, incremented with \c ++ operator, and kpeter@694: /// if the iterator leaves the last valid key, it will be equal to deba@693: /// \c INVALID. deba@693: class FalseIt : public Key { deba@693: public: deba@693: typedef Key Parent; deba@693: deba@693: /// \brief Creates an iterator. deba@693: /// deba@693: /// Creates an iterator. It iterates on the kpeter@694: /// keys mapped to \c false. kpeter@694: /// \param map The IterableBoolMap. deba@693: explicit FalseIt(const IterableBoolMap& map) deba@693: : Parent(map._sep < int(map._array.size()) ? deba@693: map._array.back() : INVALID), _map(&map) {} deba@693: deba@693: /// \brief Invalid constructor \& conversion. deba@693: /// kpeter@694: /// This constructor initializes the iterator to be invalid. deba@693: /// \sa Invalid for more details. deba@693: FalseIt(Invalid) : Parent(INVALID), _map(0) {} deba@693: deba@693: /// \brief Increment operator. deba@693: /// kpeter@694: /// Increment operator. deba@693: FalseIt& operator++() { deba@693: int pos = _map->position(*this); deba@693: Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID); deba@693: return *this; deba@693: } deba@693: deba@693: private: deba@693: const IterableBoolMap* _map; deba@693: }; deba@693: deba@693: /// \brief Iterator for the keys mapped to a given value. deba@693: /// deba@693: /// Iterator for the keys mapped to a given value. It works kpeter@694: /// like a graph item iterator, it can be converted to deba@693: /// the key type of the map, incremented with \c ++ operator, and kpeter@694: /// if the iterator leaves the last valid key, it will be equal to deba@693: /// \c INVALID. deba@693: class ItemIt : public Key { deba@693: public: deba@693: typedef Key Parent; deba@693: kpeter@694: /// \brief Creates an iterator with a value. deba@693: /// kpeter@694: /// Creates an iterator with a value. It iterates on the kpeter@694: /// keys mapped to the given value. kpeter@694: /// \param map The IterableBoolMap. kpeter@694: /// \param value The value. deba@693: ItemIt(const IterableBoolMap& map, bool value) alpar@877: : Parent(value ? deba@693: (map._sep > 0 ? deba@693: map._array[map._sep - 1] : INVALID) : deba@693: (map._sep < int(map._array.size()) ? deba@693: map._array.back() : INVALID)), _map(&map) {} deba@693: deba@693: /// \brief Invalid constructor \& conversion. deba@693: /// kpeter@694: /// This constructor initializes the iterator to be invalid. deba@693: /// \sa Invalid for more details. deba@693: ItemIt(Invalid) : Parent(INVALID), _map(0) {} deba@693: deba@693: /// \brief Increment operator. deba@693: /// kpeter@694: /// Increment operator. deba@693: ItemIt& operator++() { deba@693: int pos = _map->position(*this); deba@693: int _sep = pos >= _map->_sep ? _map->_sep : 0; deba@693: Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID); deba@693: return *this; deba@693: } deba@693: deba@693: private: deba@693: const IterableBoolMap* _map; deba@693: }; deba@693: deba@693: protected: deba@693: deba@693: virtual void add(const Key& key) { deba@693: Parent::add(key); deba@693: Parent::set(key, _array.size()); deba@693: _array.push_back(key); deba@693: } deba@693: deba@693: virtual void add(const std::vector<Key>& keys) { deba@693: Parent::add(keys); deba@693: for (int i = 0; i < int(keys.size()); ++i) { deba@693: Parent::set(keys[i], _array.size()); deba@693: _array.push_back(keys[i]); deba@693: } deba@693: } deba@693: deba@693: virtual void erase(const Key& key) { deba@693: int pos = position(key); deba@693: if (pos < _sep) { deba@693: --_sep; deba@693: Parent::set(_array[_sep], pos); deba@693: _array[pos] = _array[_sep]; deba@693: Parent::set(_array.back(), _sep); deba@693: _array[_sep] = _array.back(); deba@693: _array.pop_back(); deba@693: } else { deba@693: Parent::set(_array.back(), pos); deba@693: _array[pos] = _array.back(); deba@693: _array.pop_back(); deba@693: } deba@693: Parent::erase(key); deba@693: } deba@693: deba@693: virtual void erase(const std::vector<Key>& keys) { deba@693: for (int i = 0; i < int(keys.size()); ++i) { deba@693: int pos = position(keys[i]); deba@693: if (pos < _sep) { deba@693: --_sep; deba@693: Parent::set(_array[_sep], pos); deba@693: _array[pos] = _array[_sep]; deba@693: Parent::set(_array.back(), _sep); deba@693: _array[_sep] = _array.back(); deba@693: _array.pop_back(); deba@693: } else { deba@693: Parent::set(_array.back(), pos); deba@693: _array[pos] = _array.back(); deba@693: _array.pop_back(); deba@693: } deba@693: } deba@693: Parent::erase(keys); deba@693: } deba@693: deba@693: virtual void build() { deba@693: Parent::build(); deba@693: typename Parent::Notifier* nf = Parent::notifier(); deba@693: Key it; deba@693: for (nf->first(it); it != INVALID; nf->next(it)) { deba@693: Parent::set(it, _array.size()); deba@693: _array.push_back(it); deba@693: } deba@693: _sep = 0; deba@693: } deba@693: deba@693: virtual void clear() { deba@693: _array.clear(); deba@693: _sep = 0; deba@693: Parent::clear(); deba@693: } deba@693: deba@693: }; deba@693: deba@693: deba@693: namespace _maps_bits { deba@693: template <typename Item> deba@693: struct IterableIntMapNode { deba@693: IterableIntMapNode() : value(-1) {} deba@693: IterableIntMapNode(int _value) : value(_value) {} deba@693: Item prev, next; deba@693: int value; deba@693: }; deba@693: } deba@693: deba@693: /// \brief Dynamic iterable integer map. deba@693: /// kpeter@694: /// This class provides a special graph map type which can store an kpeter@694: /// integer value for graph items (\c Node, \c Arc or \c Edge). kpeter@694: /// For each non-negative value it is possible to iterate on the keys kpeter@694: /// mapped to the value. deba@693: /// kpeter@722: /// This map is intended to be used with small integer values, for which kpeter@722: /// it is efficient, and supports iteration only for non-negative values. kpeter@722: /// If you need large values and/or iteration for negative integers, kpeter@722: /// consider to use \ref IterableValueMap instead. kpeter@722: /// kpeter@694: /// This type is a reference map, so it can be modified with the alpar@695: /// subscript operator. kpeter@694: /// kpeter@694: /// \note The size of the data structure depends on the largest deba@693: /// value in the map. deba@693: /// kpeter@694: /// \tparam GR The graph type. kpeter@694: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@694: /// \c GR::Edge). kpeter@694: /// kpeter@694: /// \see IterableBoolMap, IterableValueMap kpeter@694: /// \see CrossRefMap kpeter@694: template <typename GR, typename K> deba@693: class IterableIntMap kpeter@694: : protected ItemSetTraits<GR, K>:: kpeter@694: template Map<_maps_bits::IterableIntMapNode<K> >::Type { deba@693: public: kpeter@694: typedef typename ItemSetTraits<GR, K>:: kpeter@694: template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent; deba@693: deba@693: /// The key type kpeter@694: typedef K Key; deba@693: /// The value type deba@693: typedef int Value; deba@693: /// The graph type deba@693: typedef GR Graph; deba@693: deba@693: /// \brief Constructor of the map. deba@693: /// kpeter@694: /// Constructor of the map. It sets all values to -1. deba@693: explicit IterableIntMap(const Graph& graph) deba@693: : Parent(graph) {} deba@693: deba@693: /// \brief Constructor of the map with a given value. deba@693: /// deba@693: /// Constructor of the map with a given value. deba@693: explicit IterableIntMap(const Graph& graph, int value) kpeter@694: : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) { deba@693: if (value >= 0) { deba@693: for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { deba@693: lace(it); deba@693: } deba@693: } deba@693: } deba@693: deba@693: private: deba@693: deba@693: void unlace(const Key& key) { deba@693: typename Parent::Value& node = Parent::operator[](key); deba@693: if (node.value < 0) return; deba@693: if (node.prev != INVALID) { deba@693: Parent::operator[](node.prev).next = node.next; deba@693: } else { deba@693: _first[node.value] = node.next; deba@693: } deba@693: if (node.next != INVALID) { deba@693: Parent::operator[](node.next).prev = node.prev; deba@693: } deba@693: while (!_first.empty() && _first.back() == INVALID) { deba@693: _first.pop_back(); deba@693: } deba@693: } deba@693: deba@693: void lace(const Key& key) { deba@693: typename Parent::Value& node = Parent::operator[](key); deba@693: if (node.value < 0) return; deba@693: if (node.value >= int(_first.size())) { deba@693: _first.resize(node.value + 1, INVALID); deba@693: } deba@693: node.prev = INVALID; deba@693: node.next = _first[node.value]; deba@693: if (node.next != INVALID) { deba@693: Parent::operator[](node.next).prev = key; deba@693: } deba@693: _first[node.value] = key; deba@693: } deba@693: deba@693: public: deba@693: kpeter@694: /// Indicates that the map is reference map. deba@693: typedef True ReferenceMapTag; deba@693: kpeter@694: /// \brief Reference to the value of the map. deba@693: /// kpeter@694: /// This class is similar to the \c int type. It can kpeter@694: /// be converted to \c int and it has the same operators. deba@693: class Reference { deba@693: friend class IterableIntMap; deba@693: private: deba@693: Reference(IterableIntMap& map, const Key& key) deba@693: : _key(key), _map(map) {} deba@693: public: deba@693: deba@693: Reference& operator=(const Reference& value) { deba@693: _map.set(_key, static_cast<const int&>(value)); deba@693: return *this; deba@693: } deba@693: deba@693: operator const int&() const { deba@693: return static_cast<const IterableIntMap&>(_map)[_key]; deba@693: } deba@693: deba@693: Reference& operator=(int value) { deba@693: _map.set(_key, value); deba@693: return *this; deba@693: } deba@693: Reference& operator++() { deba@693: _map.set(_key, _map[_key] + 1); deba@693: return *this; deba@693: } deba@693: int operator++(int) { deba@693: int value = _map[_key]; deba@693: _map.set(_key, value + 1); deba@693: return value; deba@693: } deba@693: Reference& operator--() { deba@693: _map.set(_key, _map[_key] - 1); deba@693: return *this; deba@693: } deba@693: int operator--(int) { deba@693: int value = _map[_key]; deba@693: _map.set(_key, value - 1); deba@693: return value; deba@693: } deba@693: Reference& operator+=(int value) { deba@693: _map.set(_key, _map[_key] + value); deba@693: return *this; deba@693: } deba@693: Reference& operator-=(int value) { deba@693: _map.set(_key, _map[_key] - value); deba@693: return *this; deba@693: } deba@693: Reference& operator*=(int value) { deba@693: _map.set(_key, _map[_key] * value); deba@693: return *this; deba@693: } deba@693: Reference& operator/=(int value) { deba@693: _map.set(_key, _map[_key] / value); deba@693: return *this; deba@693: } deba@693: Reference& operator%=(int value) { deba@693: _map.set(_key, _map[_key] % value); deba@693: return *this; deba@693: } deba@693: Reference& operator&=(int value) { deba@693: _map.set(_key, _map[_key] & value); deba@693: return *this; deba@693: } deba@693: Reference& operator|=(int value) { deba@693: _map.set(_key, _map[_key] | value); deba@693: return *this; deba@693: } deba@693: Reference& operator^=(int value) { deba@693: _map.set(_key, _map[_key] ^ value); deba@693: return *this; deba@693: } deba@693: Reference& operator<<=(int value) { deba@693: _map.set(_key, _map[_key] << value); deba@693: return *this; deba@693: } deba@693: Reference& operator>>=(int value) { deba@693: _map.set(_key, _map[_key] >> value); deba@693: return *this; deba@693: } deba@693: deba@693: private: deba@693: Key _key; deba@693: IterableIntMap& _map; deba@693: }; deba@693: deba@693: /// The const reference type. deba@693: typedef const Value& ConstReference; deba@693: deba@693: /// \brief Gives back the maximal value plus one. deba@693: /// deba@693: /// Gives back the maximal value plus one. deba@693: int size() const { deba@693: return _first.size(); deba@693: } deba@693: deba@693: /// \brief Set operation of the map. deba@693: /// deba@693: /// Set operation of the map. deba@693: void set(const Key& key, const Value& value) { deba@693: unlace(key); deba@693: Parent::operator[](key).value = value; deba@693: lace(key); deba@693: } deba@693: deba@693: /// \brief Const subscript operator of the map. deba@693: /// deba@693: /// Const subscript operator of the map. deba@693: const Value& operator[](const Key& key) const { deba@693: return Parent::operator[](key).value; deba@693: } deba@693: deba@693: /// \brief Subscript operator of the map. deba@693: /// deba@693: /// Subscript operator of the map. deba@693: Reference operator[](const Key& key) { deba@693: return Reference(*this, key); deba@693: } deba@693: deba@693: /// \brief Iterator for the keys with the same value. deba@693: /// deba@693: /// Iterator for the keys with the same value. It works kpeter@694: /// like a graph item iterator, it can be converted to deba@693: /// the item type of the map, incremented with \c ++ operator, and kpeter@694: /// if the iterator leaves the last valid item, it will be equal to deba@693: /// \c INVALID. kpeter@694: class ItemIt : public Key { deba@693: public: kpeter@694: typedef Key Parent; deba@693: deba@693: /// \brief Invalid constructor \& conversion. deba@693: /// kpeter@694: /// This constructor initializes the iterator to be invalid. deba@693: /// \sa Invalid for more details. deba@693: ItemIt(Invalid) : Parent(INVALID), _map(0) {} deba@693: deba@693: /// \brief Creates an iterator with a value. deba@693: /// deba@693: /// Creates an iterator with a value. It iterates on the kpeter@694: /// keys mapped to the given value. kpeter@694: /// \param map The IterableIntMap. kpeter@694: /// \param value The value. deba@693: ItemIt(const IterableIntMap& map, int value) : _map(&map) { deba@693: if (value < 0 || value >= int(_map->_first.size())) { deba@693: Parent::operator=(INVALID); deba@693: } else { deba@693: Parent::operator=(_map->_first[value]); deba@693: } deba@693: } deba@693: deba@693: /// \brief Increment operator. deba@693: /// kpeter@694: /// Increment operator. deba@693: ItemIt& operator++() { deba@693: Parent::operator=(_map->IterableIntMap::Parent:: deba@693: operator[](static_cast<Parent&>(*this)).next); deba@693: return *this; deba@693: } deba@693: deba@693: private: deba@693: const IterableIntMap* _map; deba@693: }; deba@693: deba@693: protected: deba@693: deba@693: virtual void erase(const Key& key) { deba@693: unlace(key); deba@693: Parent::erase(key); deba@693: } deba@693: deba@693: virtual void erase(const std::vector<Key>& keys) { deba@693: for (int i = 0; i < int(keys.size()); ++i) { deba@693: unlace(keys[i]); deba@693: } deba@693: Parent::erase(keys); deba@693: } deba@693: deba@693: virtual void clear() { deba@693: _first.clear(); deba@693: Parent::clear(); deba@693: } deba@693: deba@693: private: kpeter@694: std::vector<Key> _first; deba@693: }; deba@693: deba@693: namespace _maps_bits { deba@693: template <typename Item, typename Value> deba@693: struct IterableValueMapNode { deba@693: IterableValueMapNode(Value _value = Value()) : value(_value) {} deba@693: Item prev, next; deba@693: Value value; deba@693: }; deba@693: } deba@693: deba@693: /// \brief Dynamic iterable map for comparable values. deba@693: /// kpeter@722: /// This class provides a special graph map type which can store a kpeter@694: /// comparable value for graph items (\c Node, \c Arc or \c Edge). kpeter@694: /// For each value it is possible to iterate on the keys mapped to kpeter@722: /// the value (\c ItemIt), and the values of the map can be accessed kpeter@724: /// with an STL compatible forward iterator (\c ValueIt). kpeter@722: /// The map stores a linked list for each value, which contains kpeter@722: /// the items mapped to the value, and the used values are stored kpeter@722: /// in balanced binary tree (\c std::map). kpeter@694: /// kpeter@722: /// \ref IterableBoolMap and \ref IterableIntMap are similar classes kpeter@722: /// specialized for \c bool and \c int values, respectively. deba@693: /// kpeter@694: /// This type is not reference map, so it cannot be modified with alpar@695: /// the subscript operator. deba@693: /// kpeter@694: /// \tparam GR The graph type. kpeter@694: /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or kpeter@694: /// \c GR::Edge). kpeter@694: /// \tparam V The value type of the map. It can be any comparable kpeter@694: /// value type. deba@693: /// kpeter@694: /// \see IterableBoolMap, IterableIntMap kpeter@694: /// \see CrossRefMap kpeter@694: template <typename GR, typename K, typename V> deba@693: class IterableValueMap kpeter@694: : protected ItemSetTraits<GR, K>:: kpeter@694: template Map<_maps_bits::IterableValueMapNode<K, V> >::Type { deba@693: public: kpeter@694: typedef typename ItemSetTraits<GR, K>:: kpeter@694: template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent; deba@693: deba@693: /// The key type kpeter@694: typedef K Key; deba@693: /// The value type kpeter@694: typedef V Value; deba@693: /// The graph type deba@693: typedef GR Graph; deba@693: deba@693: public: deba@693: kpeter@694: /// \brief Constructor of the map with a given value. deba@693: /// kpeter@694: /// Constructor of the map with a given value. deba@693: explicit IterableValueMap(const Graph& graph, deba@693: const Value& value = Value()) kpeter@694: : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) { deba@693: for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { deba@693: lace(it); deba@693: } deba@693: } deba@693: deba@693: protected: deba@693: deba@693: void unlace(const Key& key) { deba@693: typename Parent::Value& node = Parent::operator[](key); deba@693: if (node.prev != INVALID) { deba@693: Parent::operator[](node.prev).next = node.next; deba@693: } else { deba@693: if (node.next != INVALID) { deba@693: _first[node.value] = node.next; deba@693: } else { deba@693: _first.erase(node.value); deba@693: } deba@693: } deba@693: if (node.next != INVALID) { deba@693: Parent::operator[](node.next).prev = node.prev; deba@693: } deba@693: } deba@693: deba@693: void lace(const Key& key) { deba@693: typename Parent::Value& node = Parent::operator[](key); deba@693: typename std::map<Value, Key>::iterator it = _first.find(node.value); deba@693: if (it == _first.end()) { deba@693: node.prev = node.next = INVALID; deba@693: _first.insert(std::make_pair(node.value, key)); deba@693: } else { deba@693: node.prev = INVALID; deba@693: node.next = it->second; deba@693: if (node.next != INVALID) { deba@693: Parent::operator[](node.next).prev = key; deba@693: } deba@693: it->second = key; deba@693: } deba@693: } deba@693: deba@693: public: deba@693: deba@693: /// \brief Forward iterator for values. deba@693: /// kpeter@722: /// This iterator is an STL compatible forward deba@693: /// iterator on the values of the map. The values can kpeter@694: /// be accessed in the <tt>[beginValue, endValue)</tt> range. kpeter@724: class ValueIt deba@693: : public std::iterator<std::forward_iterator_tag, Value> { deba@693: friend class IterableValueMap; deba@693: private: kpeter@724: ValueIt(typename std::map<Value, Key>::const_iterator _it) deba@693: : it(_it) {} deba@693: public: deba@693: kpeter@722: /// Constructor kpeter@724: ValueIt() {} kpeter@694: kpeter@722: /// \e kpeter@724: ValueIt& operator++() { ++it; return *this; } kpeter@722: /// \e kpeter@724: ValueIt operator++(int) { kpeter@724: ValueIt tmp(*this); deba@693: operator++(); deba@693: return tmp; deba@693: } deba@693: kpeter@722: /// \e deba@693: const Value& operator*() const { return it->first; } kpeter@722: /// \e deba@693: const Value* operator->() const { return &(it->first); } deba@693: kpeter@722: /// \e kpeter@724: bool operator==(ValueIt jt) const { return it == jt.it; } kpeter@722: /// \e kpeter@724: bool operator!=(ValueIt jt) const { return it != jt.it; } deba@693: deba@693: private: deba@693: typename std::map<Value, Key>::const_iterator it; deba@693: }; deba@693: deba@693: /// \brief Returns an iterator to the first value. deba@693: /// kpeter@722: /// Returns an STL compatible iterator to the deba@693: /// first value of the map. The values of the kpeter@694: /// map can be accessed in the <tt>[beginValue, endValue)</tt> deba@693: /// range. kpeter@724: ValueIt beginValue() const { kpeter@724: return ValueIt(_first.begin()); deba@693: } deba@693: deba@693: /// \brief Returns an iterator after the last value. deba@693: /// kpeter@722: /// Returns an STL compatible iterator after the deba@693: /// last value of the map. The values of the kpeter@694: /// map can be accessed in the <tt>[beginValue, endValue)</tt> deba@693: /// range. kpeter@724: ValueIt endValue() const { kpeter@724: return ValueIt(_first.end()); deba@693: } deba@693: deba@693: /// \brief Set operation of the map. deba@693: /// deba@693: /// Set operation of the map. deba@693: void set(const Key& key, const Value& value) { deba@693: unlace(key); deba@693: Parent::operator[](key).value = value; deba@693: lace(key); deba@693: } deba@693: deba@693: /// \brief Const subscript operator of the map. deba@693: /// deba@693: /// Const subscript operator of the map. deba@693: const Value& operator[](const Key& key) const { deba@693: return Parent::operator[](key).value; deba@693: } deba@693: deba@693: /// \brief Iterator for the keys with the same value. deba@693: /// deba@693: /// Iterator for the keys with the same value. It works kpeter@694: /// like a graph item iterator, it can be converted to deba@693: /// the item type of the map, incremented with \c ++ operator, and kpeter@694: /// if the iterator leaves the last valid item, it will be equal to deba@693: /// \c INVALID. kpeter@694: class ItemIt : public Key { deba@693: public: kpeter@694: typedef Key Parent; deba@693: deba@693: /// \brief Invalid constructor \& conversion. deba@693: /// kpeter@694: /// This constructor initializes the iterator to be invalid. deba@693: /// \sa Invalid for more details. deba@693: ItemIt(Invalid) : Parent(INVALID), _map(0) {} deba@693: deba@693: /// \brief Creates an iterator with a value. deba@693: /// deba@693: /// Creates an iterator with a value. It iterates on the deba@693: /// keys which have the given value. deba@693: /// \param map The IterableValueMap deba@693: /// \param value The value deba@693: ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) { deba@693: typename std::map<Value, Key>::const_iterator it = deba@693: map._first.find(value); deba@693: if (it == map._first.end()) { deba@693: Parent::operator=(INVALID); deba@693: } else { deba@693: Parent::operator=(it->second); deba@693: } deba@693: } deba@693: deba@693: /// \brief Increment operator. deba@693: /// deba@693: /// Increment Operator. deba@693: ItemIt& operator++() { deba@693: Parent::operator=(_map->IterableValueMap::Parent:: deba@693: operator[](static_cast<Parent&>(*this)).next); deba@693: return *this; deba@693: } deba@693: deba@693: deba@693: private: deba@693: const IterableValueMap* _map; deba@693: }; deba@693: deba@693: protected: deba@693: deba@693: virtual void add(const Key& key) { deba@693: Parent::add(key); deba@942: lace(key); deba@693: } deba@693: deba@693: virtual void add(const std::vector<Key>& keys) { deba@693: Parent::add(keys); deba@693: for (int i = 0; i < int(keys.size()); ++i) { deba@693: lace(keys[i]); deba@693: } deba@693: } deba@693: deba@693: virtual void erase(const Key& key) { deba@693: unlace(key); deba@693: Parent::erase(key); deba@693: } deba@693: deba@693: virtual void erase(const std::vector<Key>& keys) { deba@693: for (int i = 0; i < int(keys.size()); ++i) { deba@693: unlace(keys[i]); deba@693: } deba@693: Parent::erase(keys); deba@693: } deba@693: deba@693: virtual void build() { deba@693: Parent::build(); deba@693: for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { deba@693: lace(it); deba@693: } deba@693: } deba@693: deba@693: virtual void clear() { deba@693: _first.clear(); deba@693: Parent::clear(); deba@693: } deba@693: deba@693: private: deba@693: std::map<Value, Key> _first; deba@693: }; deba@693: kpeter@559: /// \brief Map of the source nodes of arcs in a digraph. deba@220: /// kpeter@559: /// SourceMap provides access for the source node of each arc in a digraph, kpeter@559: /// which is returned by the \c source() function of the digraph. kpeter@559: /// \tparam GR The digraph type. deba@220: /// \see TargetMap kpeter@559: template <typename GR> deba@220: class SourceMap { deba@220: public: deba@220: kpeter@724: /// The key type (the \c Arc type of the digraph). kpeter@559: typedef typename GR::Arc Key; kpeter@724: /// The value type (the \c Node type of the digraph). kpeter@559: typedef typename GR::Node Value; deba@220: deba@220: /// \brief Constructor deba@220: /// kpeter@559: /// Constructor. kpeter@313: /// \param digraph The digraph that the map belongs to. kpeter@559: explicit SourceMap(const GR& digraph) : _graph(digraph) {} kpeter@559: kpeter@559: /// \brief Returns the source node of the given arc. deba@220: /// kpeter@559: /// Returns the source node of the given arc. deba@220: Value operator[](const Key& arc) const { kpeter@559: return _graph.source(arc); deba@220: } deba@220: deba@220: private: kpeter@559: 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@559: template <typename GR> kpeter@559: inline SourceMap<GR> sourceMap(const GR& graph) { kpeter@559: return SourceMap<GR>(graph); deba@220: } deba@220: kpeter@559: /// \brief Map of the target nodes of arcs in a digraph. deba@220: /// kpeter@559: /// TargetMap provides access for the target node of each arc in a digraph, kpeter@559: /// which is returned by the \c target() function of the digraph. kpeter@559: /// \tparam GR The digraph type. deba@220: /// \see SourceMap kpeter@559: template <typename GR> deba@220: class TargetMap { deba@220: public: deba@220: kpeter@724: /// The key type (the \c Arc type of the digraph). kpeter@559: typedef typename GR::Arc Key; kpeter@724: /// The value type (the \c Node type of the digraph). kpeter@559: typedef typename GR::Node Value; deba@220: deba@220: /// \brief Constructor deba@220: /// kpeter@559: /// Constructor. kpeter@313: /// \param digraph The digraph that the map belongs to. kpeter@559: explicit TargetMap(const GR& digraph) : _graph(digraph) {} kpeter@559: kpeter@559: /// \brief Returns the target node of the given arc. deba@220: /// kpeter@559: /// Returns the target node of the given arc. deba@220: Value operator[](const Key& e) const { kpeter@559: return _graph.target(e); deba@220: } deba@220: deba@220: private: kpeter@559: 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@559: template <typename GR> kpeter@559: inline TargetMap<GR> targetMap(const GR& graph) { kpeter@559: return TargetMap<GR>(graph); deba@220: } deba@220: kpeter@559: /// \brief Map of the "forward" directed arc view of edges in a graph. deba@220: /// kpeter@559: /// ForwardMap provides access for the "forward" directed arc view of kpeter@559: /// each edge in a graph, which is returned by the \c direct() function kpeter@559: /// of the graph with \c true parameter. kpeter@559: /// \tparam GR The graph type. deba@220: /// \see BackwardMap kpeter@559: template <typename GR> deba@220: class ForwardMap { deba@220: public: deba@220: kpeter@724: /// The key type (the \c Edge type of the digraph). kpeter@724: typedef typename GR::Edge Key; kpeter@724: /// The value type (the \c Arc type of the digraph). kpeter@559: typedef typename GR::Arc Value; deba@220: deba@220: /// \brief Constructor deba@220: /// kpeter@559: /// Constructor. kpeter@313: /// \param graph The graph that the map belongs to. kpeter@559: explicit ForwardMap(const GR& graph) : _graph(graph) {} kpeter@559: kpeter@559: /// \brief Returns the "forward" directed arc view of the given edge. deba@220: /// kpeter@559: /// 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@559: 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@559: template <typename GR> kpeter@559: inline ForwardMap<GR> forwardMap(const GR& graph) { kpeter@559: return ForwardMap<GR>(graph); deba@220: } deba@220: kpeter@559: /// \brief Map of the "backward" directed arc view of edges in a graph. deba@220: /// kpeter@559: /// BackwardMap provides access for the "backward" directed arc view of kpeter@559: /// each edge in a graph, which is returned by the \c direct() function kpeter@559: /// of the graph with \c false parameter. kpeter@559: /// \tparam GR The graph type. deba@220: /// \see ForwardMap kpeter@559: template <typename GR> deba@220: class BackwardMap { deba@220: public: deba@220: kpeter@724: /// The key type (the \c Edge type of the digraph). kpeter@724: typedef typename GR::Edge Key; kpeter@724: /// The value type (the \c Arc type of the digraph). kpeter@559: typedef typename GR::Arc Value; deba@220: deba@220: /// \brief Constructor deba@220: /// kpeter@559: /// Constructor. kpeter@313: /// \param graph The graph that the map belongs to. kpeter@559: explicit BackwardMap(const GR& graph) : _graph(graph) {} kpeter@559: kpeter@559: /// \brief Returns the "backward" directed arc view of the given edge. deba@220: /// kpeter@559: /// 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@559: 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@559: template <typename GR> kpeter@559: inline BackwardMap<GR> backwardMap(const GR& graph) { kpeter@559: return BackwardMap<GR>(graph); deba@220: } deba@220: kpeter@559: /// \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@559: /// 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: /// deba@693: /// \warning Besides \c addNode() and \c addArc(), a digraph structure kpeter@559: /// may provide alternative ways to modify the digraph. kpeter@559: /// The correct behavior of InDegMap is not guarantied if these additional kpeter@786: /// features are used. For example, the functions kpeter@559: /// \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@559: template <typename GR> deba@220: class InDegMap kpeter@559: : protected ItemSetTraits<GR, typename GR::Arc> deba@220: ::ItemNotifier::ObserverBase { deba@220: deba@220: public: deba@693: kpeter@617: /// The graph type of InDegMap kpeter@617: typedef GR Graph; kpeter@559: typedef GR Digraph; kpeter@559: /// The key type kpeter@559: typedef typename Digraph::Node Key; kpeter@559: /// The value type deba@220: typedef int Value; deba@220: deba@220: typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> deba@220: ::ItemNotifier::ObserverBase Parent; deba@220: deba@220: private: deba@220: deba@220: class AutoNodeMap deba@220: : public ItemSetTraits<Digraph, Key>::template Map<int>::Type { deba@220: public: deba@220: deba@220: typedef typename ItemSetTraits<Digraph, Key>:: deba@220: template Map<int>::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<Key>& 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@559: /// Constructor for creating an in-degree map. kpeter@559: explicit InDegMap(const Digraph& graph) kpeter@559: : _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@559: /// \brief Gives back the in-degree of a Node. kpeter@559: /// 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<Arc>& 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<Arc>& 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@559: /// \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@559: /// 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: /// deba@693: /// \warning Besides \c addNode() and \c addArc(), a digraph structure kpeter@559: /// may provide alternative ways to modify the digraph. kpeter@559: /// The correct behavior of OutDegMap is not guarantied if these additional kpeter@786: /// features are used. For example, the functions kpeter@559: /// \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@559: template <typename GR> deba@220: class OutDegMap kpeter@559: : protected ItemSetTraits<GR, typename GR::Arc> deba@220: ::ItemNotifier::ObserverBase { deba@220: deba@220: public: deba@220: kpeter@617: /// The graph type of OutDegMap kpeter@617: typedef GR Graph; kpeter@559: typedef GR Digraph; kpeter@559: /// The key type kpeter@559: typedef typename Digraph::Node Key; kpeter@559: /// The value type deba@220: typedef int Value; deba@220: deba@220: typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> deba@220: ::ItemNotifier::ObserverBase Parent; deba@220: deba@220: private: deba@220: deba@220: class AutoNodeMap deba@220: : public ItemSetTraits<Digraph, Key>::template Map<int>::Type { deba@220: public: deba@220: deba@220: typedef typename ItemSetTraits<Digraph, Key>:: deba@220: template Map<int>::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<Key>& 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@559: /// Constructor for creating an out-degree map. kpeter@559: explicit OutDegMap(const Digraph& graph) kpeter@559: : _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@559: /// \brief Gives back the out-degree of a Node. kpeter@559: /// 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<Arc>& 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<Arc>& 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@559: /// \brief Potential difference map kpeter@559: /// kpeter@584: /// PotentialDifferenceMap returns the difference between the potentials of kpeter@584: /// the source and target nodes of each arc in a digraph, i.e. it returns kpeter@559: /// \code kpeter@559: /// potential[gr.target(arc)] - potential[gr.source(arc)]. kpeter@559: /// \endcode kpeter@559: /// \tparam GR The digraph type. kpeter@559: /// \tparam POT A node map storing the potentials. kpeter@559: template <typename GR, typename POT> kpeter@559: class PotentialDifferenceMap { kpeter@559: public: kpeter@559: /// Key type kpeter@559: typedef typename GR::Arc Key; kpeter@559: /// Value type kpeter@559: typedef typename POT::Value Value; kpeter@559: kpeter@559: /// \brief Constructor kpeter@559: /// kpeter@559: /// Contructor of the map. kpeter@559: explicit PotentialDifferenceMap(const GR& gr, kpeter@559: const POT& potential) kpeter@559: : _digraph(gr), _potential(potential) {} kpeter@559: kpeter@559: /// \brief Returns the potential difference for the given arc. kpeter@559: /// kpeter@559: /// Returns the potential difference for the given arc, i.e. kpeter@559: /// \code kpeter@559: /// potential[gr.target(arc)] - potential[gr.source(arc)]. kpeter@559: /// \endcode kpeter@559: Value operator[](const Key& arc) const { kpeter@559: return _potential[_digraph.target(arc)] - kpeter@559: _potential[_digraph.source(arc)]; kpeter@559: } kpeter@559: kpeter@559: private: kpeter@559: const GR& _digraph; kpeter@559: const POT& _potential; kpeter@559: }; kpeter@559: kpeter@559: /// \brief Returns a PotentialDifferenceMap. kpeter@559: /// kpeter@559: /// This function just returns a PotentialDifferenceMap. kpeter@559: /// \relates PotentialDifferenceMap kpeter@559: template <typename GR, typename POT> kpeter@559: PotentialDifferenceMap<GR, POT> kpeter@559: potentialDifferenceMap(const GR& gr, const POT& potential) { kpeter@559: return PotentialDifferenceMap<GR, POT>(gr, potential); kpeter@559: } kpeter@559: kpeter@789: kpeter@789: /// \brief Copy the values of a graph map to another map. kpeter@789: /// kpeter@789: /// This function copies the values of a graph map to another graph map. kpeter@789: /// \c To::Key must be equal or convertible to \c From::Key and kpeter@789: /// \c From::Value must be equal or convertible to \c To::Value. kpeter@789: /// kpeter@789: /// For example, an edge map of \c int value type can be copied to kpeter@789: /// an arc map of \c double value type in an undirected graph, but kpeter@789: /// an arc map cannot be copied to an edge map. kpeter@789: /// Note that even a \ref ConstMap can be copied to a standard graph map, kpeter@789: /// but \ref mapFill() can also be used for this purpose. kpeter@789: /// kpeter@789: /// \param gr The graph for which the maps are defined. kpeter@789: /// \param from The map from which the values have to be copied. kpeter@789: /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. kpeter@789: /// \param to The map to which the values have to be copied. kpeter@789: /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@789: template <typename GR, typename From, typename To> kpeter@789: void mapCopy(const GR& gr, const From& from, To& to) { kpeter@789: typedef typename To::Key Item; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; alpar@877: kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: to.set(it, from[it]); kpeter@789: } kpeter@789: } kpeter@789: kpeter@789: /// \brief Compare two graph maps. kpeter@789: /// alpar@877: /// This function compares the values of two graph maps. It returns kpeter@789: /// \c true if the maps assign the same value for all items in the graph. kpeter@789: /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal kpeter@789: /// and their \c Value types must be comparable using \c %operator==(). kpeter@789: /// kpeter@789: /// \param gr The graph for which the maps are defined. kpeter@789: /// \param map1 The first map. kpeter@789: /// \param map2 The second map. kpeter@789: template <typename GR, typename Map1, typename Map2> kpeter@789: bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) { kpeter@789: typedef typename Map2::Key Item; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; alpar@877: kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: if (!(map1[it] == map2[it])) return false; kpeter@789: } kpeter@789: return true; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return an item having minimum value of a graph map. kpeter@789: /// kpeter@789: /// This function returns an item (\c Node, \c Arc or \c Edge) having kpeter@789: /// minimum value of the given graph map. kpeter@789: /// If the item set is empty, it returns \c INVALID. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: template <typename GR, typename Map> kpeter@789: typename Map::Key mapMin(const GR& gr, const Map& map) { kpeter@789: return mapMin(gr, map, std::less<typename Map::Value>()); kpeter@789: } kpeter@789: kpeter@789: /// \brief Return an item having minimum value of a graph map. kpeter@789: /// kpeter@789: /// This function returns an item (\c Node, \c Arc or \c Edge) having kpeter@789: /// minimum value of the given graph map. kpeter@789: /// If the item set is empty, it returns \c INVALID. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: /// \param comp Comparison function object. kpeter@789: template <typename GR, typename Map, typename Comp> kpeter@789: typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) { kpeter@789: typedef typename Map::Key Item; kpeter@789: typedef typename Map::Value Value; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; kpeter@789: kpeter@789: ItemIt min_item(gr); kpeter@789: if (min_item == INVALID) return INVALID; kpeter@789: Value min = map[min_item]; kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: if (comp(map[it], min)) { kpeter@789: min = map[it]; kpeter@789: min_item = it; kpeter@789: } kpeter@789: } kpeter@789: return min_item; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return an item having maximum value of a graph map. kpeter@789: /// kpeter@789: /// This function returns an item (\c Node, \c Arc or \c Edge) having kpeter@789: /// maximum value of the given graph map. kpeter@789: /// If the item set is empty, it returns \c INVALID. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: template <typename GR, typename Map> kpeter@789: typename Map::Key mapMax(const GR& gr, const Map& map) { kpeter@789: return mapMax(gr, map, std::less<typename Map::Value>()); kpeter@789: } kpeter@789: kpeter@789: /// \brief Return an item having maximum value of a graph map. kpeter@789: /// kpeter@789: /// This function returns an item (\c Node, \c Arc or \c Edge) having kpeter@789: /// maximum value of the given graph map. kpeter@789: /// If the item set is empty, it returns \c INVALID. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: /// \param comp Comparison function object. kpeter@789: template <typename GR, typename Map, typename Comp> kpeter@789: typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) { kpeter@789: typedef typename Map::Key Item; kpeter@789: typedef typename Map::Value Value; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; kpeter@789: kpeter@789: ItemIt max_item(gr); kpeter@789: if (max_item == INVALID) return INVALID; kpeter@789: Value max = map[max_item]; kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: if (comp(max, map[it])) { kpeter@789: max = map[it]; kpeter@789: max_item = it; kpeter@789: } kpeter@789: } kpeter@789: return max_item; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return the minimum value of a graph map. kpeter@789: /// kpeter@789: /// This function returns the minimum value of the given graph map. kpeter@789: /// The corresponding item set of the graph must not be empty. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: template <typename GR, typename Map> kpeter@789: typename Map::Value mapMinValue(const GR& gr, const Map& map) { kpeter@789: return map[mapMin(gr, map, std::less<typename Map::Value>())]; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return the minimum value of a graph map. kpeter@789: /// kpeter@789: /// This function returns the minimum value of the given graph map. kpeter@789: /// The corresponding item set of the graph must not be empty. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: /// \param comp Comparison function object. kpeter@789: template <typename GR, typename Map, typename Comp> kpeter@789: typename Map::Value kpeter@789: mapMinValue(const GR& gr, const Map& map, const Comp& comp) { kpeter@789: return map[mapMin(gr, map, comp)]; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return the maximum value of a graph map. kpeter@789: /// kpeter@789: /// This function returns the maximum value of the given graph map. kpeter@789: /// The corresponding item set of the graph must not be empty. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: template <typename GR, typename Map> kpeter@789: typename Map::Value mapMaxValue(const GR& gr, const Map& map) { kpeter@789: return map[mapMax(gr, map, std::less<typename Map::Value>())]; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return the maximum value of a graph map. kpeter@789: /// kpeter@789: /// This function returns the maximum value of the given graph map. kpeter@789: /// The corresponding item set of the graph must not be empty. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: /// \param comp Comparison function object. kpeter@789: template <typename GR, typename Map, typename Comp> kpeter@789: typename Map::Value kpeter@789: mapMaxValue(const GR& gr, const Map& map, const Comp& comp) { kpeter@789: return map[mapMax(gr, map, comp)]; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return an item having a specified value in a graph map. kpeter@789: /// kpeter@789: /// This function returns an item (\c Node, \c Arc or \c Edge) having kpeter@789: /// the specified assigned value in the given graph map. kpeter@789: /// If no such item exists, it returns \c INVALID. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: /// \param val The value that have to be found. kpeter@789: template <typename GR, typename Map> kpeter@789: typename Map::Key kpeter@789: mapFind(const GR& gr, const Map& map, const typename Map::Value& val) { kpeter@789: typedef typename Map::Key Item; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; kpeter@789: kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: if (map[it] == val) return it; kpeter@789: } kpeter@789: return INVALID; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return an item having value for which a certain predicate is kpeter@789: /// true in a graph map. kpeter@789: /// kpeter@789: /// This function returns an item (\c Node, \c Arc or \c Edge) having kpeter@789: /// such assigned value for which the specified predicate is true kpeter@789: /// in the given graph map. kpeter@789: /// If no such item exists, it returns \c INVALID. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: /// \param pred The predicate function object. kpeter@789: template <typename GR, typename Map, typename Pred> kpeter@789: typename Map::Key kpeter@789: mapFindIf(const GR& gr, const Map& map, const Pred& pred) { kpeter@789: typedef typename Map::Key Item; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; kpeter@789: kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: if (pred(map[it])) return it; kpeter@789: } kpeter@789: return INVALID; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return the number of items having a specified value in a kpeter@789: /// graph map. kpeter@789: /// kpeter@789: /// This function returns the number of items (\c Node, \c Arc or \c Edge) kpeter@789: /// having the specified assigned value in the given graph map. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: /// \param val The value that have to be counted. kpeter@789: template <typename GR, typename Map> kpeter@789: int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) { kpeter@789: typedef typename Map::Key Item; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; kpeter@789: kpeter@789: int cnt = 0; kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: if (map[it] == val) ++cnt; kpeter@789: } kpeter@789: return cnt; kpeter@789: } kpeter@789: kpeter@789: /// \brief Return the number of items having values for which a certain kpeter@789: /// predicate is true in a graph map. kpeter@789: /// kpeter@789: /// This function returns the number of items (\c Node, \c Arc or \c Edge) kpeter@789: /// having such assigned values for which the specified predicate is true kpeter@789: /// in the given graph map. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. kpeter@789: /// \param pred The predicate function object. kpeter@789: template <typename GR, typename Map, typename Pred> kpeter@789: int mapCountIf(const GR& gr, const Map& map, const Pred& pred) { kpeter@789: typedef typename Map::Key Item; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; kpeter@789: kpeter@789: int cnt = 0; kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: if (pred(map[it])) ++cnt; kpeter@789: } kpeter@789: return cnt; kpeter@789: } kpeter@789: kpeter@789: /// \brief Fill a graph map with a certain value. kpeter@789: /// kpeter@789: /// This function sets the specified value for all items (\c Node, kpeter@789: /// \c Arc or \c Edge) in the given graph map. kpeter@789: /// kpeter@789: /// \param gr The graph for which the map is defined. kpeter@789: /// \param map The graph map. It must conform to the kpeter@789: /// \ref concepts::WriteMap "WriteMap" concept. kpeter@789: /// \param val The value. kpeter@789: template <typename GR, typename Map> kpeter@789: void mapFill(const GR& gr, Map& map, const typename Map::Value& val) { kpeter@789: typedef typename Map::Key Item; kpeter@789: typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt; kpeter@789: kpeter@789: for (ItemIt it(gr); it != INVALID; ++it) { kpeter@789: map.set(it, val); kpeter@789: } kpeter@789: } kpeter@789: alpar@25: /// @} alpar@25: } alpar@25: alpar@25: #endif // LEMON_MAPS_H