# HG changeset patch # User Alpar Juttner # Date 2008-03-16 08:32:43 # Node ID 8161012eaa61898ddb8a206f7c53d17eb214e1ce # Parent c46b3453455f2ba5b0b70dcf0bffd387bf513410 # Parent 3654324ec0357b53961f90fdc66320349278bf22 Merge diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -38,13 +38,13 @@ accessed. LEMON provides several physical graph structures to meet the diverging requirements of the possible users. In order to save on running time or on memory usage, some structures may fail to provide -some graph features like edge or node deletion. +some graph features like arc/edge or node deletion. Alteration of standard containers need a very limited number of operations, these together satisfy the everyday requirements. In the case of graph structures, different operations are needed which do not alter the physical graph, but gives another view. If some nodes or -edges have to be hidden or the reverse oriented graph have to be used, then +arcs have to be hidden or the reverse oriented graph have to be used, then this is the case. It also may happen that in a flow implementation the residual graph can be accessed by another algorithm, or a node-set is to be shrunk for another algorithm. @@ -81,10 +81,10 @@ /** @defgroup graph_maps Graph Maps @ingroup maps -\brief Special Graph-Related Maps. +\brief Special graph-related maps. This group describes maps that are specifically designed to assign -values to the nodes and edges of graphs. +values to the nodes and arcs of graphs. */ @@ -96,15 +96,15 @@ This group describes map adaptors that are used to create "implicit" maps from other maps. -Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can -make arithmetic operations between one or two maps (negation, scaling, -addition, multiplication etc.) or e.g. convert a map to another one -of different Value type. +Most of them are \ref lemon::concepts::ReadMap "read-only maps". +They can make arithmetic and logical operations between one or two maps +(negation, shifting, addition, multiplication, logical 'and', 'or', +'not' etc.) or e.g. convert a map to another one of different Value type. The typical usage of this classes is passing implicit maps to algorithms. If a function type algorithm is called then the function type map adaptors can be used comfortable. For example let's see the -usage of map adaptors with the \c graphToEps() function: +usage of map adaptors with the \c digraphToEps() function. \code Color nodeColor(int deg) { if (deg >= 2) { @@ -116,39 +116,37 @@ } } - Graph::NodeMap degree_map(graph); + Digraph::NodeMap degree_map(graph); - graphToEps(graph, "graph.eps") + digraphToEps(graph, "graph.eps") .coords(coords).scaleToA4().undirected() - .nodeColors(composeMap(functorMap(nodeColor), degree_map)) + .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) .run(); \endcode -The \c functorMap() function makes an \c int to \c Color map from the +The \c functorToMap() function makes an \c int to \c Color map from the \e nodeColor() function. The \c composeMap() compose the \e degree_map -and the previous created map. The composed map is proper function to -get color of each node. +and the previously created map. The composed map is a proper function to +get the color of each node. The usage with class type algorithms is little bit harder. In this case the function type map adaptors can not be used, because the function map adaptors give back temporary objects. \code - Graph graph; - - typedef Graph::EdgeMap DoubleEdgeMap; - DoubleEdgeMap length(graph); - DoubleEdgeMap speed(graph); - - typedef DivMap TimeMap; - + Digraph graph; + + typedef Digraph::ArcMap DoubleArcMap; + DoubleArcMap length(graph); + DoubleArcMap speed(graph); + + typedef DivMap TimeMap; TimeMap time(length, speed); - Dijkstra dijkstra(graph, time); + Dijkstra dijkstra(graph, time); dijkstra.run(source, target); \endcode - -We have a length map and a maximum speed map on a graph. The minimum -time to pass the edge can be calculated as the division of the two -maps which can be done implicitly with the \c DivMap template +We have a length map and a maximum speed map on the arcs of a digraph. +The minimum time to pass the arc can be calculated as the division of +the two maps which can be done implicitly with the \c DivMap template class. We use the implicit minimum time map as the length map of the \c Dijkstra algorithm. */ @@ -315,7 +313,7 @@ This group contains algorithm objects and functions to calculate matchings in graphs and bipartite graphs. The general matching problem is -finding a subset of the edges which does not shares common endpoints. +finding a subset of the arcs which does not shares common endpoints. There are several different algorithms for calculate matchings in graphs. The matching problems in bipartite graphs are generally diff --git a/lemon/concepts/maps.h b/lemon/concepts/maps.h --- a/lemon/concepts/maps.h +++ b/lemon/concepts/maps.h @@ -29,7 +29,7 @@ namespace lemon { namespace concepts { - + /// \addtogroup concept /// @{ @@ -42,39 +42,39 @@ { public: /// The key type of the map. - typedef K Key; + typedef K Key; /// The value type of the map. (The type of objects associated with the keys). typedef T Value; - /// Returns the value associated with a key. + /// Returns the value associated with the given key. - /// Returns the value associated with a key. - /// \bug Value shouldn't need to be default constructible. - /// - Value operator[](const Key &) const {return Value();} + /// Returns the value associated with the given key. + /// \bug Value shouldn't need to be default constructible. + Value operator[](const Key &) const { return Value(); } template struct Constraints { void constraints() { Value val = m[key]; val = m[key]; - typename _ReadMap::Value own_val = m[own_key]; - own_val = m[own_key]; + typename _ReadMap::Value own_val = m[own_key]; + own_val = m[own_key]; + ignore_unused_variable_warning(key); ignore_unused_variable_warning(val); + ignore_unused_variable_warning(own_key); ignore_unused_variable_warning(own_val); - ignore_unused_variable_warning(key); } - Key& key; - typename _ReadMap::Key& own_key; - _ReadMap& m; + const Key& key; + const typename _ReadMap::Key& own_key; + const _ReadMap& m; }; - + }; /// Writable map concept - + /// Writable map concept. /// template @@ -82,39 +82,37 @@ { public: /// The key type of the map. - typedef K Key; + typedef K Key; /// The value type of the map. (The type of objects associated with the keys). typedef T Value; - /// Sets the value associated with a key. - void set(const Key &,const Value &) {} + /// Sets the value associated with the given key. + void set(const Key &, const Value &) {} - ///Default constructor + /// Default constructor. WriteMap() {} template struct Constraints { void constraints() { - // No constraints for constructor. m.set(key, val); m.set(own_key, own_val); + ignore_unused_variable_warning(key); ignore_unused_variable_warning(val); ignore_unused_variable_warning(own_key); ignore_unused_variable_warning(own_val); } - - Value& val; - typename _WriteMap::Value own_val; - Key& key; - typename _WriteMap::Key& own_key; + const Key& key; + const Value& val; + const typename _WriteMap::Key& own_key; + const typename _WriteMap::Value own_val; _WriteMap& m; - }; }; /// Read/writable map concept - + /// Read/writable map concept. /// template @@ -123,14 +121,15 @@ { public: /// The key type of the map. - typedef K Key; + typedef K Key; /// The value type of the map. (The type of objects associated with the keys). typedef T Value; - /// Returns the value associated with a key. - Value operator[](const Key &) const {return Value();} - /// Sets the value associated with a key. - void set(const Key & ,const Value &) {} + /// Returns the value associated with the given key. + Value operator[](const Key &) const { return Value(); } + + /// Sets the value associated with the given key. + void set(const Key &, const Value &) {} template struct Constraints { @@ -140,13 +139,12 @@ } }; }; - - + + /// Dereferable map concept - + /// Dereferable map concept. /// - /// \todo Rethink this concept. template class ReferenceMap : public ReadWriteMap { @@ -154,7 +152,7 @@ /// Tag for reference maps. typedef True ReferenceMapTag; /// The key type of the map. - typedef K Key; + typedef K Key; /// The value type of the map. (The type of objects associated with the keys). typedef T Value; /// The reference type of the map. @@ -166,33 +164,38 @@ Value tmp; public: - ///Returns a reference to the value associated with a key. + /// Returns a reference to the value associated with the given key. Reference operator[](const Key &) { return tmp; } - ///Returns a const reference to the value associated with a key. + + /// Returns a const reference to the value associated with the given key. ConstReference operator[](const Key &) const { return tmp; } - /// Sets the value associated with a key. + + /// Sets the value associated with the given key. void set(const Key &k,const Value &t) { operator[](k)=t; } template struct Constraints { void constraints() { checkConcept, _ReferenceMap >(); + ref = m[key]; m[key] = val; - val = m[key]; m[key] = ref; - ref = m[key]; + m[key] = cref; + own_ref = m[own_key]; m[own_key] = own_val; - own_val = m[own_key]; m[own_key] = own_ref; - own_ref = m[own_key]; + m[own_key] = own_cref; + m[key] = m[own_key]; + m[own_key] = m[key]; } - - typename _ReferenceMap::Key& own_key; + const Key& key; + Value& val; + Reference ref; + ConstReference cref; + const typename _ReferenceMap::Key& own_key; typename _ReferenceMap::Value& own_val; typename _ReferenceMap::Reference own_ref; - Key& key; - Value& val; - Reference ref; + typename _ReferenceMap::ConstReference own_cref; _ReferenceMap& m; }; }; diff --git a/lemon/maps.h b/lemon/maps.h --- a/lemon/maps.h +++ b/lemon/maps.h @@ -24,12 +24,12 @@ #include #include -// #include +#include ///\file ///\ingroup maps ///\brief Miscellaneous property maps -/// + #include namespace lemon { @@ -39,41 +39,46 @@ /// Base class of maps. - /// Base class of maps. - /// It provides the necessary typedefs required by the map concept. - template + /// Base class of maps. It provides the necessary type definitions + /// required by the map %concepts. + template class MapBase { public: - /// The key type of the map. + /// \biref The key type of the map. typedef K Key; - /// The value type of the map. (The type of objects associated with the keys). - typedef T Value; + /// \brief The value type of the map. + /// (The type of objects associated with the keys). + typedef V Value; }; + /// Null map. (a.k.a. DoNothingMap) /// This map can be used if you have to provide a map only for - /// its type definitions, or if you have to provide a writable map, - /// but data written to it is not required (i.e. it will be sent to + /// its type definitions, or if you have to provide a writable map, + /// but data written to it is not required (i.e. it will be sent to /// /dev/null). - template - class NullMap : public MapBase { + /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// + /// \sa ConstMap + template + class NullMap : public MapBase { public: - typedef MapBase Parent; + typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - + /// Gives back a default constructed element. - T operator[](const K&) const { return T(); } + Value operator[](const Key&) const { return Value(); } /// Absorbs the value. - void set(const K&, const T&) {} + void set(const Key&, const Value&) {} }; - ///Returns a \c NullMap class + /// Returns a \ref NullMap class - ///This function just returns a \c NullMap class. - ///\relates NullMap - template + /// This function just returns a \ref NullMap class. + /// \relates NullMap + template NullMap nullMap() { return NullMap(); } @@ -81,62 +86,81 @@ /// Constant map. - /// This is a \ref concepts::ReadMap "readable" map which assigns a - /// specified value to each key. - /// In other aspects it is equivalent to \c NullMap. - template - class ConstMap : public MapBase { + /// This \ref concepts::ReadMap "readable map" assigns a specified + /// value to each key. + /// + /// In other aspects it is equivalent to \ref NullMap. + /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" + /// concept, but it absorbs the data written to it. + /// + /// The simplest way of using this map is through the constMap() + /// function. + /// + /// \sa NullMap + /// \sa IdentityMap + template + class ConstMap : public MapBase { private: - T v; + V _value; public: - - typedef MapBase Parent; + typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; /// Default constructor /// Default constructor. - /// The value of the map will be uninitialized. - /// (More exactly it will be default constructed.) + /// The value of the map will be default constructed. ConstMap() {} - + /// Constructor with specified initial value /// Constructor with specified initial value. - /// \param _v is the initial value of the map. - ConstMap(const T &_v) : v(_v) {} - - ///\e - T operator[](const K&) const { return v; } + /// \param v is the initial value of the map. + ConstMap(const Value &v) : _value(v) {} - ///\e - void setAll(const T &t) { - v = t; - } + /// Gives back the specified value. + Value operator[](const Key&) const { return _value; } - template - ConstMap(const ConstMap &, const T &_v) : v(_v) {} + /// Absorbs the value. + void set(const Key&, const Value&) {} + + /// Sets the value that is assigned to each key. + void setAll(const Value &v) { + _value = v; + } + + template + ConstMap(const ConstMap &, const Value &v) : _value(v) {} }; - ///Returns a \c ConstMap class + /// Returns a \ref ConstMap class - ///This function just returns a \c ConstMap class. - ///\relates ConstMap - template + /// This function just returns a \ref ConstMap class. + /// \relates ConstMap + template inline ConstMap constMap(const V &v) { return ConstMap(v); } template - struct Const { }; + struct Const {}; /// Constant map with inlined constant value. - /// This is a \ref concepts::ReadMap "readable" map which assigns a - /// specified value to each key. - /// In other aspects it is equivalent to \c NullMap. + /// This \ref concepts::ReadMap "readable map" assigns a specified + /// value to each key. + /// + /// In other aspects it is equivalent to \ref NullMap. + /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" + /// concept, but it absorbs the data written to it. + /// + /// The simplest way of using this map is through the constMap() + /// function. + /// + /// \sa NullMap + /// \sa IdentityMap template class ConstMap > : public MapBase { public: @@ -144,69 +168,230 @@ typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ConstMap() { } - ///\e - V operator[](const K&) const { return v; } - ///\e - void set(const K&, const V&) { } + /// Constructor. + ConstMap() {} + + /// Gives back the specified value. + Value operator[](const Key&) const { return v; } + + /// Absorbs the value. + void set(const Key&, const Value&) {} }; - ///Returns a \c ConstMap class with inlined value + /// Returns a \ref ConstMap class with inlined constant value - ///This function just returns a \c ConstMap class with inlined value. - ///\relates ConstMap - template + /// This function just returns a \ref ConstMap class with inlined + /// constant value. + /// \relates ConstMap + template inline ConstMap > constMap() { return ConstMap >(); } - ///Map based on \c std::map - ///This is essentially a wrapper for \c std::map with addition that - ///you can specify a default value different from \c Value(). - ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept. - template > - class StdMap : public MapBase { - template - friend class StdMap; + /// Identity map. + + /// This \ref concepts::ReadMap "read-only map" gives back the given + /// key as value without any modification. + /// + /// \sa ConstMap + template + class IdentityMap : public MapBase { + public: + typedef MapBase Parent; + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + /// Gives back the given value without any modification. + Value operator[](const Key &k) const { + return k; + } + }; + + /// Returns an \ref IdentityMap class + + /// This function just returns an \ref IdentityMap class. + /// \relates IdentityMap + template + inline IdentityMap identityMap() { + return IdentityMap(); + } + + + /// \brief Map for storing values for integer keys from the range + /// [0..size-1]. + /// + /// This map is essentially a wrapper for \c std::vector. It assigns + /// values to integer keys from the range [0..size-1]. + /// It can be used with some data structures, for example + /// \ref UnionFind, \ref BinHeap, when the used items are small + /// integers. This map conforms the \ref concepts::ReferenceMap + /// "ReferenceMap" concept. + /// + /// The simplest way of using this map is through the rangeMap() + /// function. + template + class RangeMap : public MapBase { + template + friend class RangeMap; + private: + + typedef std::vector Vector; + Vector _vector; + public: - typedef MapBase Parent; - ///Key type + typedef MapBase Parent; + /// Key type typedef typename Parent::Key Key; - ///Value type + /// Value type typedef typename Parent::Value Value; - ///Reference Type - typedef T& Reference; - ///Const reference type - typedef const T& ConstReference; + /// Reference type + typedef typename Vector::reference Reference; + /// Const reference type + typedef typename Vector::const_reference ConstReference; + + typedef True ReferenceMapTag; + + public: + + /// Constructor with specified default value. + RangeMap(int size = 0, const Value &value = Value()) + : _vector(size, value) {} + + /// Constructs the map from an appropriate \c std::vector. + template + RangeMap(const std::vector& vector) + : _vector(vector.begin(), vector.end()) {} + + /// Constructs the map from another \ref RangeMap. + template + RangeMap(const RangeMap &c) + : _vector(c._vector.begin(), c._vector.end()) {} + + /// Returns the size of the map. + int size() { + return _vector.size(); + } + + /// Resizes the map. + + /// Resizes the underlying \c std::vector container, so changes the + /// keyset of the map. + /// \param size The new size of the map. The new keyset will be the + /// range [0..size-1]. + /// \param value The default value to assign to the new keys. + void resize(int size, const Value &value = Value()) { + _vector.resize(size, value); + } + + private: + + RangeMap& operator=(const RangeMap&); + + public: + + ///\e + Reference operator[](const Key &k) { + return _vector[k]; + } + + ///\e + ConstReference operator[](const Key &k) const { + return _vector[k]; + } + + ///\e + void set(const Key &k, const Value &v) { + _vector[k] = v; + } + }; + + /// Returns a \ref RangeMap class + + /// This function just returns a \ref RangeMap class. + /// \relates RangeMap + template + inline RangeMap rangeMap(int size = 0, const V &value = V()) { + return RangeMap(size, value); + } + + /// \brief Returns a \ref RangeMap class created from an appropriate + /// \c std::vector + + /// This function just returns a \ref RangeMap class created from an + /// appropriate \c std::vector. + /// \relates RangeMap + template + inline RangeMap rangeMap(const std::vector &vector) { + return RangeMap(vector); + } + + + /// Map type based on \c std::map + + /// This map is essentially a wrapper for \c std::map with addition + /// that you can specify a default value for the keys that are not + /// stored actually. This value can be different from the default + /// contructed value (i.e. \c %Value()). + /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap" + /// concept. + /// + /// This map is useful if a default value should be assigned to most of + /// the keys and different values should be assigned only to a few + /// keys (i.e. the map is "sparse"). + /// The name of this type also refers to this important usage. + /// + /// Apart form that this map can be used in many other cases since it + /// is based on \c std::map, which is a general associative container. + /// However keep in mind that it is usually not as efficient as other + /// maps. + /// + /// The simplest way of using this map is through the sparseMap() + /// function. + template > + class SparseMap : public MapBase { + template + friend class SparseMap; + public: + + typedef MapBase Parent; + /// Key type + typedef typename Parent::Key Key; + /// Value type + typedef typename Parent::Value Value; + /// Reference type + typedef Value& Reference; + /// Const reference type + typedef const Value& ConstReference; typedef True ReferenceMapTag; private: - - typedef std::map Map; + + typedef std::map Map; + Map _map; Value _value; - Map _map; public: - /// Constructor with specified default value - StdMap(const T& value = T()) : _value(value) {} - /// \brief Constructs the map from an appropriate \c std::map, and + /// \brief Constructor with specified default value. + SparseMap(const Value &value = Value()) : _value(value) {} + /// \brief Constructs the map from an appropriate \c std::map, and /// explicitly specifies a default value. - template - StdMap(const std::map &map, const T& value = T()) + template + SparseMap(const std::map &map, + const Value &value = Value()) : _map(map.begin(), map.end()), _value(value) {} - - /// \brief Constructs a map from an other \ref StdMap. - template - StdMap(const StdMap &c) + + /// \brief Constructs the map from another \ref SparseMap. + template + SparseMap(const SparseMap &c) : _map(c._map.begin(), c._map.end()), _value(c._value) {} private: - StdMap& operator=(const StdMap&); + SparseMap& operator=(const SparseMap&); public: @@ -219,7 +404,7 @@ return _map.insert(it, std::make_pair(k, _value))->second; } - /// \e + ///\e ConstReference operator[](const Key &k) const { typename Map::const_iterator it = _map.find(k); if (it != _map.end()) @@ -228,149 +413,48 @@ return _value; } - /// \e - void set(const Key &k, const T &t) { + ///\e + void set(const Key &k, const Value &v) { typename Map::iterator it = _map.lower_bound(k); if (it != _map.end() && !_map.key_comp()(k, it->first)) - it->second = t; + it->second = v; else - _map.insert(it, std::make_pair(k, t)); + _map.insert(it, std::make_pair(k, v)); } - /// \e - void setAll(const T &t) { - _value = t; + ///\e + void setAll(const Value &v) { + _value = v; _map.clear(); - } + } + }; - }; - - ///Returns a \c StdMap class + /// Returns a \ref SparseMap class - ///This function just returns a \c StdMap class with specified - ///default value. - ///\relates StdMap - template - inline StdMap stdMap(const V& value = V()) { - return StdMap(value); - } - - ///Returns a \c StdMap class - - ///This function just returns a \c StdMap class with specified - ///default value. - ///\relates StdMap - template - inline StdMap > stdMap(const V& value = V()) { - return StdMap >(value); - } - - ///Returns a \c StdMap class created from an appropriate std::map - - ///This function just returns a \c StdMap class created from an - ///appropriate std::map. - ///\relates StdMap - template - inline StdMap stdMap( const std::map &map, - const V& value = V() ) { - return StdMap(map, value); + /// This function just returns a \ref SparseMap class with specified + /// default value. + /// \relates SparseMap + template + inline SparseMap sparseMap(const V& value = V()) { + return SparseMap(value); } - ///Returns a \c StdMap class created from an appropriate std::map - - ///This function just returns a \c StdMap class created from an - ///appropriate std::map. - ///\relates StdMap - template - inline StdMap > stdMap( const std::map > &map, - const V& value = V() ) { - return StdMap >(map, value); + template + inline SparseMap > sparseMap(const V& value = V()) { + return SparseMap >(value); } - /// \brief Map for storing values for keys from the range [0..size-1] - /// - /// This map has the [0..size-1] keyset and the values - /// are stored in a \c std::vector container. It can be used with - /// some data structures, for example \c UnionFind, \c BinHeap, when - /// the used items are small integer numbers. - /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept. - /// - /// \todo Revise its name - template - class IntegerMap : public MapBase { + /// \brief Returns a \ref SparseMap class created from an appropriate + /// \c std::map - template - friend class IntegerMap; - - public: - - typedef MapBase Parent; - ///\e - typedef typename Parent::Key Key; - ///\e - typedef typename Parent::Value Value; - ///\e - typedef T& Reference; - ///\e - typedef const T& ConstReference; - - typedef True ReferenceMapTag; - - private: - - typedef std::vector Vector; - Vector _vector; - - public: - - /// Constructor with specified default value - IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {} - - /// \brief Constructs the map from an appropriate \c std::vector. - template - IntegerMap(const std::vector& vector) - : _vector(vector.begin(), vector.end()) {} - - /// \brief Constructs a map from an other \ref IntegerMap. - template - IntegerMap(const IntegerMap &c) - : _vector(c._vector.begin(), c._vector.end()) {} - - /// \brief Resize the container - void resize(int size, const T& value = T()) { - _vector.resize(size, value); - } - - private: - - IntegerMap& operator=(const IntegerMap&); - - public: - - ///\e - Reference operator[](Key k) { - return _vector[k]; - } - - /// \e - ConstReference operator[](Key k) const { - return _vector[k]; - } - - /// \e - void set(const Key &k, const T& t) { - _vector[k] = t; - } - - }; - - ///Returns an \c IntegerMap class - - ///This function just returns an \c IntegerMap class. - ///\relates IntegerMap - template - inline IntegerMap integerMap(int size = 0, const T& value = T()) { - return IntegerMap(size, value); + /// This function just returns a \ref SparseMap class created from an + /// appropriate \c std::map. + /// \relates SparseMap + template + inline SparseMap + sparseMap(const std::map &map, const V& value = V()) + { + return SparseMap(map, value); } /// @} @@ -378,1260 +462,1210 @@ /// \addtogroup map_adaptors /// @{ - /// \brief Identity map. + /// Composition of two maps + + /// This \ref concepts::ReadMap "read-only map" returns the + /// composition of two given maps. That is to say, if \c m1 is of + /// type \c M1 and \c m2 is of \c M2, then for + /// \code + /// ComposeMap cm(m1,m2); + /// \endcode + /// cm[x] will be equal to m1[m2[x]]. /// - /// This map gives back the given key as value without any - /// modification. - template - class IdentityMap : public MapBase { + /// The \c Key type of the map is inherited from \c M2 and the + /// \c Value type is from \c M1. + /// \c M2::Value must be convertible to \c M1::Key. + /// + /// The simplest way of using this map is through the composeMap() + /// function. + /// + /// \sa CombineMap + /// + /// \todo Check the requirements. + template + class ComposeMap : public MapBase { + const M1 &_m1; + const M2 &_m2; public: - typedef MapBase Parent; + typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; + /// Constructor + ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} + /// \e - const T& operator[](const T& t) const { - return t; - } + typename MapTraits::ConstReturnValue + operator[](const Key &k) const { return _m1[_m2[k]]; } }; - ///Returns an \c IdentityMap class + /// Returns a \ref ComposeMap class - ///This function just returns an \c IdentityMap class. - ///\relates IdentityMap - template - inline IdentityMap identityMap() { - return IdentityMap(); + /// This function just returns a \ref ComposeMap class. + /// + /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is + /// convertible to the \c Key of \c m1, then composeMap(m1,m2)[x] + /// will be equal to m1[m2[x]]. + /// + /// \relates ComposeMap + template + inline ComposeMap composeMap(const M1 &m1, const M2 &m2) { + return ComposeMap(m1, m2); } - - ///\brief Convert the \c Value of a map to another type using - ///the default conversion. + + /// Combination of two maps using an STL (binary) functor. + + /// This \ref concepts::ReadMap "read-only map" takes two maps and a + /// binary functor and returns the combination of the two given maps + /// using the functor. + /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2 + /// and \c f is of \c F, then for + /// \code + /// CombineMap cm(m1,m2,f); + /// \endcode + /// cm[x] will be equal to f(m1[x],m2[x]). /// - ///This \ref concepts::ReadMap "read only map" - ///converts the \c Value of a map to type \c T. - ///Its \c Key is inherited from \c M. - template - class ConvertMap : public MapBase { - const M& m; + /// The \c Key type of the map is inherited from \c M1 (\c M1::Key + /// must be convertible to \c M2::Key) and the \c Value type is \c V. + /// \c M2::Value and \c M1::Value must be convertible to the + /// corresponding input parameter of \c F and the return type of \c F + /// must be convertible to \c V. + /// + /// The simplest way of using this map is through the combineMap() + /// function. + /// + /// \sa ComposeMap + /// + /// \todo Check the requirements. + template + class CombineMap : public MapBase { + const M1 &_m1; + const M2 &_m2; + F _f; public: - typedef MapBase Parent; + typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor + /// Constructor + CombineMap(const M1 &m1, const M2 &m2, const F &f = F()) + : _m1(m1), _m2(m2), _f(f) {} + /// \e + Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); } + }; - ///Constructor. - ///\param _m is the underlying map. - ConvertMap(const M &_m) : m(_m) {}; + /// Returns a \ref CombineMap class - ///\e - Value operator[](const Key& k) const {return m[k];} - }; - - ///Returns a \c ConvertMap class - - ///This function just returns a \c ConvertMap class. - ///\relates ConvertMap - template - inline ConvertMap convertMap(const M &m) { - return ConvertMap(m); + /// This function just returns a \ref CombineMap class. + /// + /// For example, if \c m1 and \c m2 are both maps with \c double + /// values, then + /// \code + /// combineMap(m1,m2,std::plus()) + /// \endcode + /// is equivalent to + /// \code + /// addMap(m1,m2) + /// \endcode + /// + /// This function is specialized for adaptable binary function + /// classes and C++ functions. + /// + /// \relates CombineMap + template + inline CombineMap + combineMap(const M1 &m1, const M2 &m2, const F &f) { + return CombineMap(m1,m2,f); } - ///Simple wrapping of a map + template + inline CombineMap + combineMap(const M1 &m1, const M2 &m2, const F &f) { + return combineMap(m1,m2,f); + } - ///This \ref concepts::ReadMap "read only map" returns the simple - ///wrapping of the given map. Sometimes the reference maps cannot be - ///combined with simple read maps. This map adaptor wraps the given - ///map to simple read map. + template + inline CombineMap + combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { + return combineMap(m1,m2,f); + } + + + /// Converts an STL style (unary) functor to a map + + /// This \ref concepts::ReadMap "read-only map" returns the value + /// of a given functor. Actually, it just wraps the functor and + /// provides the \c Key and \c Value typedefs. /// - ///\sa SimpleWriteMap + /// Template parameters \c K and \c V will become its \c Key and + /// \c Value. In most cases they have to be given explicitly because + /// a functor typically does not provide \c argument_type and + /// \c result_type typedefs. + /// Parameter \c F is the type of the used functor. /// - /// \todo Revise the misleading name - template - class SimpleMap : public MapBase { - const M& m; + /// The simplest way of using this map is through the functorToMap() + /// function. + /// + /// \sa MapToFunctor + template + class FunctorToMap : public MapBase { + const F &_f; + public: + typedef MapBase Parent; + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + /// Constructor + FunctorToMap(const F &f = F()) : _f(f) {} + /// \e + Value operator[](const Key &k) const { return _f(k); } + }; + + /// Returns a \ref FunctorToMap class + + /// This function just returns a \ref FunctorToMap class. + /// + /// This function is specialized for adaptable binary function + /// classes and C++ functions. + /// + /// \relates FunctorToMap + template + inline FunctorToMap functorToMap(const F &f) { + return FunctorToMap(f); + } + + template + inline FunctorToMap + functorToMap(const F &f) + { + return FunctorToMap(f); + } + + template + inline FunctorToMap functorToMap(V (*f)(K)) { + return FunctorToMap(f); + } + + + /// Converts a map to an STL style (unary) functor + + /// This class converts a map to an STL style (unary) functor. + /// That is it provides an operator() to read its values. + /// + /// For the sake of convenience it also works as a usual + /// \ref concepts::ReadMap "readable map", i.e. operator[] + /// and the \c Key and \c Value typedefs also exist. + /// + /// The simplest way of using this map is through the mapToFunctor() + /// function. + /// + ///\sa FunctorToMap + template + class MapToFunctor : public MapBase { + const M &_m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor - SimpleMap(const M &_m) : m(_m) {}; - ///\e - Value operator[](Key k) const {return m[k];} + typedef typename Parent::Key argument_type; + typedef typename Parent::Value result_type; + + /// Constructor + MapToFunctor(const M &m) : _m(m) {} + /// \e + Value operator()(const Key &k) const { return _m[k]; } + /// \e + Value operator[](const Key &k) const { return _m[k]; } }; - - ///Returns a \c SimpleMap class - ///This function just returns a \c SimpleMap class. - ///\relates SimpleMap + /// Returns a \ref MapToFunctor class + + /// This function just returns a \ref MapToFunctor class. + /// \relates MapToFunctor template - inline SimpleMap simpleMap(const M &m) { - return SimpleMap(m); + inline MapToFunctor mapToFunctor(const M &m) { + return MapToFunctor(m); } - ///Simple writable wrapping of a map - ///This \ref concepts::ReadWriteMap "read-write map" returns the simple - ///wrapping of the given map. Sometimes the reference maps cannot be - ///combined with simple read-write maps. This map adaptor wraps the - ///given map to simple read-write map. + /// \brief Map adaptor to convert the \c Value type of a map to + /// another type using the default conversion. + + /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap + /// "readable map" to another type using the default conversion. + /// The \c Key type of it is inherited from \c M and the \c Value + /// type is \c V. + /// This type conforms the \ref concepts::ReadMap "ReadMap" concept. /// - ///\sa SimpleMap + /// The simplest way of using this map is through the convertMap() + /// function. + template + class ConvertMap : public MapBase { + const M &_m; + public: + typedef MapBase Parent; + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + /// Constructor + + /// Constructor. + /// \param m The underlying map. + ConvertMap(const M &m) : _m(m) {} + + /// \e + Value operator[](const Key &k) const { return _m[k]; } + }; + + /// Returns a \ref ConvertMap class + + /// This function just returns a \ref ConvertMap class. + /// \relates ConvertMap + template + inline ConvertMap convertMap(const M &map) { + return ConvertMap(map); + } + + + /// Applies all map setting operations to two maps + + /// This map has two \ref concepts::WriteMap "writable map" parameters + /// and each write request will be passed to both of them. + /// If \c M1 is also \ref concepts::ReadMap "readable", then the read + /// operations will return the corresponding values of \c M1. /// - /// \todo Revise the misleading name - template - class SimpleWriteMap : public MapBase { - M& m; + /// The \c Key and \c Value types are inherited from \c M1. + /// The \c Key and \c Value of \c M2 must be convertible from those + /// of \c M1. + /// + /// The simplest way of using this map is through the forkMap() + /// function. + template + class ForkMap : public MapBase { + M1 &_m1; + M2 &_m2; + public: + typedef MapBase Parent; + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + /// Constructor + ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {} + /// Returns the value associated with the given key in the first map. + Value operator[](const Key &k) const { return _m1[k]; } + /// Sets the value associated with the given key in both maps. + void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); } + }; + + /// Returns a \ref ForkMap class + + /// This function just returns a \ref ForkMap class. + /// \relates ForkMap + template + inline ForkMap forkMap(M1 &m1, M2 &m2) { + return ForkMap(m1,m2); + } + + + /// Sum of two maps + + /// This \ref concepts::ReadMap "read-only map" returns the sum + /// of the values of the two given maps. + /// Its \c Key and \c Value types are inherited from \c M1. + /// The \c Key and \c Value of \c M2 must be convertible to those of + /// \c M1. + /// + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for + /// \code + /// AddMap am(m1,m2); + /// \endcode + /// am[x] will be equal to m1[x]+m2[x]. + /// + /// The simplest way of using this map is through the addMap() + /// function. + /// + /// \sa SubMap, MulMap, DivMap + /// \sa ShiftMap, ShiftWriteMap + template + class AddMap : public MapBase { + const M1 &_m1; + const M2 &_m2; + public: + typedef MapBase Parent; + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + /// Constructor + AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} + /// \e + Value operator[](const Key &k) const { return _m1[k]+_m2[k]; } + }; + + /// Returns an \ref AddMap class + + /// This function just returns an \ref AddMap class. + /// + /// For example, if \c m1 and \c m2 are both maps with \c double + /// values, then addMap(m1,m2)[x] will be equal to + /// m1[x]+m2[x]. + /// + /// \relates AddMap + template + inline AddMap addMap(const M1 &m1, const M2 &m2) { + return AddMap(m1,m2); + } + + + /// Difference of two maps + + /// This \ref concepts::ReadMap "read-only map" returns the difference + /// of the values of the two given maps. + /// Its \c Key and \c Value types are inherited from \c M1. + /// The \c Key and \c Value of \c M2 must be convertible to those of + /// \c M1. + /// + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for + /// \code + /// SubMap sm(m1,m2); + /// \endcode + /// sm[x] will be equal to m1[x]-m2[x]. + /// + /// The simplest way of using this map is through the subMap() + /// function. + /// + /// \sa AddMap, MulMap, DivMap + template + class SubMap : public MapBase { + const M1 &_m1; + const M2 &_m2; + public: + typedef MapBase Parent; + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + /// Constructor + SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} + /// \e + Value operator[](const Key &k) const { return _m1[k]-_m2[k]; } + }; + + /// Returns a \ref SubMap class + + /// This function just returns a \ref SubMap class. + /// + /// For example, if \c m1 and \c m2 are both maps with \c double + /// values, then subMap(m1,m2)[x] will be equal to + /// m1[x]-m2[x]. + /// + /// \relates SubMap + template + inline SubMap subMap(const M1 &m1, const M2 &m2) { + return SubMap(m1,m2); + } + + + /// Product of two maps + + /// This \ref concepts::ReadMap "read-only map" returns the product + /// of the values of the two given maps. + /// Its \c Key and \c Value types are inherited from \c M1. + /// The \c Key and \c Value of \c M2 must be convertible to those of + /// \c M1. + /// + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for + /// \code + /// MulMap mm(m1,m2); + /// \endcode + /// mm[x] will be equal to m1[x]*m2[x]. + /// + /// The simplest way of using this map is through the mulMap() + /// function. + /// + /// \sa AddMap, SubMap, DivMap + /// \sa ScaleMap, ScaleWriteMap + template + class MulMap : public MapBase { + const M1 &_m1; + const M2 &_m2; + public: + typedef MapBase Parent; + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + /// Constructor + MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} + /// \e + Value operator[](const Key &k) const { return _m1[k]*_m2[k]; } + }; + + /// Returns a \ref MulMap class + + /// This function just returns a \ref MulMap class. + /// + /// For example, if \c m1 and \c m2 are both maps with \c double + /// values, then mulMap(m1,m2)[x] will be equal to + /// m1[x]*m2[x]. + /// + /// \relates MulMap + template + inline MulMap mulMap(const M1 &m1,const M2 &m2) { + return MulMap(m1,m2); + } + + + /// Quotient of two maps + + /// This \ref concepts::ReadMap "read-only map" returns the quotient + /// of the values of the two given maps. + /// Its \c Key and \c Value types are inherited from \c M1. + /// The \c Key and \c Value of \c M2 must be convertible to those of + /// \c M1. + /// + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for + /// \code + /// DivMap dm(m1,m2); + /// \endcode + /// dm[x] will be equal to m1[x]/m2[x]. + /// + /// The simplest way of using this map is through the divMap() + /// function. + /// + /// \sa AddMap, SubMap, MulMap + template + class DivMap : public MapBase { + const M1 &_m1; + const M2 &_m2; + public: + typedef MapBase Parent; + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + /// Constructor + DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} + /// \e + Value operator[](const Key &k) const { return _m1[k]/_m2[k]; } + }; + + /// Returns a \ref DivMap class + + /// This function just returns a \ref DivMap class. + /// + /// For example, if \c m1 and \c m2 are both maps with \c double + /// values, then divMap(m1,m2)[x] will be equal to + /// m1[x]/m2[x]. + /// + /// \relates DivMap + template + inline DivMap divMap(const M1 &m1,const M2 &m2) { + return DivMap(m1,m2); + } + + + /// Shifts a map with a constant. + + /// This \ref concepts::ReadMap "read-only map" returns the sum of + /// the given map and a constant value (i.e. it shifts the map with + /// the constant). Its \c Key and \c Value are inherited from \c M. + /// + /// Actually, + /// \code + /// ShiftMap sh(m,v); + /// \endcode + /// is equivalent to + /// \code + /// ConstMap cm(v); + /// AddMap > sh(m,cm); + /// \endcode + /// + /// The simplest way of using this map is through the shiftMap() + /// function. + /// + /// \sa ShiftWriteMap + template + class ShiftMap : public MapBase { + const M &_m; + C _v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor - SimpleWriteMap(M &_m) : m(_m) {}; - ///\e - Value operator[](Key k) const {return m[k];} - ///\e - void set(Key k, const Value& c) { m.set(k, c); } + /// Constructor + + /// Constructor. + /// \param m The undelying map. + /// \param v The constant value. + ShiftMap(const M &m, const C &v) : _m(m), _v(v) {} + /// \e + Value operator[](const Key &k) const { return _m[k]+_v; } }; - ///Returns a \c SimpleWriteMap class + /// Shifts a map with a constant (read-write version). - ///This function just returns a \c SimpleWriteMap class. - ///\relates SimpleWriteMap - template - inline SimpleWriteMap simpleWriteMap(M &m) { - return SimpleWriteMap(m); - } - - ///Sum of two maps - - ///This \ref concepts::ReadMap "read only map" returns the sum of the two - ///given maps. - ///Its \c Key and \c Value are inherited from \c M1. - ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. - template - class AddMap : public MapBase { - const M1& m1; - const M2& m2; - - public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; - - ///Constructor - AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; - ///\e - Value operator[](Key k) const {return m1[k]+m2[k];} - }; - - ///Returns an \c AddMap class - - ///This function just returns an \c AddMap class. - ///\todo Extend the documentation: how to call these type of functions? + /// This \ref concepts::ReadWriteMap "read-write map" returns the sum + /// of the given map and a constant value (i.e. it shifts the map with + /// the constant). Its \c Key and \c Value are inherited from \c M. + /// It makes also possible to write the map. /// - ///\relates AddMap - template - inline AddMap addMap(const M1 &m1,const M2 &m2) { - return AddMap(m1,m2); - } - - ///Shift a map with a constant. - - ///This \ref concepts::ReadMap "read only map" returns the sum of the - ///given map and a constant value. - ///Its \c Key and \c Value are inherited from \c M. + /// The simplest way of using this map is through the shiftWriteMap() + /// function. /// - ///Actually, - ///\code - /// ShiftMap sh(x,v); - ///\endcode - ///is equivalent to - ///\code - /// ConstMap c_tmp(v); - /// AddMap > sh(x,v); - ///\endcode - /// - ///\sa ShiftWriteMap - template - class ShiftMap : public MapBase { - const M& m; - C v; + /// \sa ShiftMap + template + class ShiftWriteMap : public MapBase { + M &_m; + C _v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor + /// Constructor - ///Constructor. - ///\param _m is the undelying map. - ///\param _v is the shift value. - ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; - ///\e - Value operator[](Key k) const {return m[k] + v;} + /// Constructor. + /// \param m The undelying map. + /// \param v The constant value. + ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {} + /// \e + Value operator[](const Key &k) const { return _m[k]+_v; } + /// \e + void set(const Key &k, const Value &v) { _m.set(k, v-_v); } }; - ///Shift a map with a constant (ReadWrite version). + /// Returns a \ref ShiftMap class - ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the - ///given map and a constant value. It makes also possible to write the map. - ///Its \c Key and \c Value are inherited from \c M. + /// This function just returns a \ref ShiftMap class. /// - ///\sa ShiftMap - template - class ShiftWriteMap : public MapBase { - M& m; - C v; + /// For example, if \c m is a map with \c double values and \c v is + /// \c double, then shiftMap(m,v)[x] will be equal to + /// m[x]+v. + /// + /// \relates ShiftMap + template + inline ShiftMap shiftMap(const M &m, const C &v) { + return ShiftMap(m,v); + } + + /// Returns a \ref ShiftWriteMap class + + /// This function just returns a \ref ShiftWriteMap class. + /// + /// For example, if \c m is a map with \c double values and \c v is + /// \c double, then shiftWriteMap(m,v)[x] will be equal to + /// m[x]+v. + /// Moreover it makes also possible to write the map. + /// + /// \relates ShiftWriteMap + template + inline ShiftWriteMap shiftWriteMap(M &m, const C &v) { + return ShiftWriteMap(m,v); + } + + + /// Scales a map with a constant. + + /// This \ref concepts::ReadMap "read-only map" returns the value of + /// the given map multiplied from the left side with a constant value. + /// Its \c Key and \c Value are inherited from \c M. + /// + /// Actually, + /// \code + /// ScaleMap sc(m,v); + /// \endcode + /// is equivalent to + /// \code + /// ConstMap cm(v); + /// MulMap, M> sc(cm,m); + /// \endcode + /// + /// The simplest way of using this map is through the scaleMap() + /// function. + /// + /// \sa ScaleWriteMap + template + class ScaleMap : public MapBase { + const M &_m; + C _v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor + /// Constructor - ///Constructor. - ///\param _m is the undelying map. - ///\param _v is the shift value. - ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {}; + /// Constructor. + /// \param m The undelying map. + /// \param v The constant value. + ScaleMap(const M &m, const C &v) : _m(m), _v(v) {} /// \e - Value operator[](Key k) const {return m[k] + v;} - /// \e - void set(Key k, const Value& c) { m.set(k, c - v); } + Value operator[](const Key &k) const { return _v*_m[k]; } }; - - ///Returns a \c ShiftMap class - ///This function just returns a \c ShiftMap class. - ///\relates ShiftMap - template - inline ShiftMap shiftMap(const M &m,const C &v) { - return ShiftMap(m,v); - } + /// Scales a map with a constant (read-write version). - ///Returns a \c ShiftWriteMap class - - ///This function just returns a \c ShiftWriteMap class. - ///\relates ShiftWriteMap - template - inline ShiftWriteMap shiftMap(M &m,const C &v) { - return ShiftWriteMap(m,v); - } - - ///Difference of two maps - - ///This \ref concepts::ReadMap "read only map" returns the difference - ///of the values of the two given maps. - ///Its \c Key and \c Value are inherited from \c M1. - ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. + /// This \ref concepts::ReadWriteMap "read-write map" returns the value of + /// the given map multiplied from the left side with a constant value. + /// Its \c Key and \c Value are inherited from \c M. + /// It can also be used as write map if the \c / operator is defined + /// between \c Value and \c C and the given multiplier is not zero. /// - /// \todo Revise the misleading name - template - class SubMap : public MapBase { - const M1& m1; - const M2& m2; - public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; - - ///Constructor - SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; - /// \e - Value operator[](Key k) const {return m1[k]-m2[k];} - }; - - ///Returns a \c SubMap class - - ///This function just returns a \c SubMap class. + /// The simplest way of using this map is through the scaleWriteMap() + /// function. /// - ///\relates SubMap - template - inline SubMap subMap(const M1 &m1, const M2 &m2) { - return SubMap(m1, m2); - } - - ///Product of two maps - - ///This \ref concepts::ReadMap "read only map" returns the product of the - ///values of the two given maps. - ///Its \c Key and \c Value are inherited from \c M1. - ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. - template - class MulMap : public MapBase { - const M1& m1; - const M2& m2; - public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; - - ///Constructor - MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; - /// \e - Value operator[](Key k) const {return m1[k]*m2[k];} - }; - - ///Returns a \c MulMap class - - ///This function just returns a \c MulMap class. - ///\relates MulMap - template - inline MulMap mulMap(const M1 &m1,const M2 &m2) { - return MulMap(m1,m2); - } - - ///Scales a map with a constant. - - ///This \ref concepts::ReadMap "read only map" returns the value of the - ///given map multiplied from the left side with a constant value. - ///Its \c Key and \c Value are inherited from \c M. - /// - ///Actually, - ///\code - /// ScaleMap sc(x,v); - ///\endcode - ///is equivalent to - ///\code - /// ConstMap c_tmp(v); - /// MulMap > sc(x,v); - ///\endcode - /// - ///\sa ScaleWriteMap - template - class ScaleMap : public MapBase { - const M& m; - C v; + /// \sa ScaleMap + template + class ScaleWriteMap : public MapBase { + M &_m; + C _v; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor + /// Constructor - ///Constructor. - ///\param _m is the undelying map. - ///\param _v is the scaling value. - ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; + /// Constructor. + /// \param m The undelying map. + /// \param v The constant value. + ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {} /// \e - Value operator[](Key k) const {return v * m[k];} + Value operator[](const Key &k) const { return _v*_m[k]; } + /// \e + void set(const Key &k, const Value &v) { _m.set(k, v/_v); } }; - ///Scales a map with a constant (ReadWrite version). + /// Returns a \ref ScaleMap class - ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the - ///given map multiplied from the left side with a constant value. It can - ///also be used as write map if the \c / operator is defined between - ///\c Value and \c C and the given multiplier is not zero. - ///Its \c Key and \c Value are inherited from \c M. + /// This function just returns a \ref ScaleMap class. /// - ///\sa ScaleMap - template - class ScaleWriteMap : public MapBase { - M& m; - C v; + /// For example, if \c m is a map with \c double values and \c v is + /// \c double, then scaleMap(m,v)[x] will be equal to + /// v*m[x]. + /// + /// \relates ScaleMap + template + inline ScaleMap scaleMap(const M &m, const C &v) { + return ScaleMap(m,v); + } + + /// Returns a \ref ScaleWriteMap class + + /// This function just returns a \ref ScaleWriteMap class. + /// + /// For example, if \c m is a map with \c double values and \c v is + /// \c double, then scaleWriteMap(m,v)[x] will be equal to + /// v*m[x]. + /// Moreover it makes also possible to write the map. + /// + /// \relates ScaleWriteMap + template + inline ScaleWriteMap scaleWriteMap(M &m, const C &v) { + return ScaleWriteMap(m,v); + } + + + /// Negative of a map + + /// This \ref concepts::ReadMap "read-only map" returns the negative + /// of the values of the given map (using the unary \c - operator). + /// Its \c Key and \c Value are inherited from \c M. + /// + /// If M::Value is \c int, \c double etc., then + /// \code + /// NegMap neg(m); + /// \endcode + /// is equivalent to + /// \code + /// ScaleMap neg(m,-1); + /// \endcode + /// + /// The simplest way of using this map is through the negMap() + /// function. + /// + /// \sa NegWriteMap + template + class NegMap : public MapBase { + const M& _m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor - - ///Constructor. - ///\param _m is the undelying map. - ///\param _v is the scaling value. - ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {}; + /// Constructor + NegMap(const M &m) : _m(m) {} /// \e - Value operator[](Key k) const {return v * m[k];} - /// \e - void set(Key k, const Value& c) { m.set(k, c / v);} - }; - - ///Returns a \c ScaleMap class - - ///This function just returns a \c ScaleMap class. - ///\relates ScaleMap - template - inline ScaleMap scaleMap(const M &m,const C &v) { - return ScaleMap(m,v); - } - - ///Returns a \c ScaleWriteMap class - - ///This function just returns a \c ScaleWriteMap class. - ///\relates ScaleWriteMap - template - inline ScaleWriteMap scaleMap(M &m,const C &v) { - return ScaleWriteMap(m,v); - } - - ///Quotient of two maps - - ///This \ref concepts::ReadMap "read only map" returns the quotient of the - ///values of the two given maps. - ///Its \c Key and \c Value are inherited from \c M1. - ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. - template - class DivMap : public MapBase { - const M1& m1; - const M2& m2; - public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; - - ///Constructor - DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; - /// \e - Value operator[](Key k) const {return m1[k]/m2[k];} - }; - - ///Returns a \c DivMap class - - ///This function just returns a \c DivMap class. - ///\relates DivMap - template - inline DivMap divMap(const M1 &m1,const M2 &m2) { - return DivMap(m1,m2); - } - - ///Composition of two maps - - ///This \ref concepts::ReadMap "read only map" returns the composition of - ///two given maps. - ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2, - ///then for - ///\code - /// ComposeMap cm(m1,m2); - ///\endcode - /// cm[x] will be equal to m1[m2[x]]. - /// - ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1. - ///\c M2::Value must be convertible to \c M1::Key. - /// - ///\sa CombineMap - /// - ///\todo Check the requirements. - template - class ComposeMap : public MapBase { - const M1& m1; - const M2& m2; - public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; - - ///Constructor - ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; - - /// \e - - - /// \todo Use the MapTraits once it is ported. - /// - - //typename MapTraits::ConstReturnValue - typename M1::Value - operator[](Key k) const {return m1[m2[k]];} + Value operator[](const Key &k) const { return -_m[k]; } }; - ///Returns a \c ComposeMap class + /// Negative of a map (read-write version) - ///This function just returns a \c ComposeMap class. - ///\relates ComposeMap - template - inline ComposeMap composeMap(const M1 &m1,const M2 &m2) { - return ComposeMap(m1,m2); - } - - ///Combine of two maps using an STL (binary) functor. - - ///Combine of two maps using an STL (binary) functor. + /// This \ref concepts::ReadWriteMap "read-write map" returns the + /// negative of the values of the given map (using the unary \c - + /// operator). + /// Its \c Key and \c Value are inherited from \c M. + /// It makes also possible to write the map. /// - ///This \ref concepts::ReadMap "read only map" takes two maps and a - ///binary functor and returns the composition of the two - ///given maps unsing the functor. - ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2 - ///and \c f is of \c F, then for - ///\code - /// CombineMap cm(m1,m2,f); - ///\endcode - /// cm[x] will be equal to f(m1[x],m2[x]) + /// If M::Value is \c int, \c double etc., then + /// \code + /// NegWriteMap neg(m); + /// \endcode + /// is equivalent to + /// \code + /// ScaleWriteMap neg(m,-1); + /// \endcode /// - ///Its \c Key is inherited from \c M1 and its \c Value is \c V. - ///\c M2::Value and \c M1::Value must be convertible to the corresponding - ///input parameter of \c F and the return type of \c F must be convertible - ///to \c V. + /// The simplest way of using this map is through the negWriteMap() + /// function. /// - ///\sa ComposeMap - /// - ///\todo Check the requirements. - template - class CombineMap : public MapBase { - const M1& m1; - const M2& m2; - F f; - public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; - - ///Constructor - CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F()) - : m1(_m1), m2(_m2), f(_f) {}; - /// \e - Value operator[](Key k) const {return f(m1[k],m2[k]);} - }; - - ///Returns a \c CombineMap class - - ///This function just returns a \c CombineMap class. - /// - ///For example if \c m1 and \c m2 are both \c double valued maps, then - ///\code - ///combineMap(m1,m2,std::plus()) - ///\endcode - ///is equivalent to - ///\code - ///addMap(m1,m2) - ///\endcode - /// - ///This function is specialized for adaptable binary function - ///classes and C++ functions. - /// - ///\relates CombineMap - template - inline CombineMap - combineMap(const M1& m1,const M2& m2, const F& f) { - return CombineMap(m1,m2,f); - } - - template - inline CombineMap - combineMap(const M1& m1, const M2& m2, const F& f) { - return combineMap(m1,m2,f); - } - - template - inline CombineMap - combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { - return combineMap(m1,m2,f); - } - - ///Negative value of a map - - ///This \ref concepts::ReadMap "read only map" returns the negative - ///value of the value returned by the given map. - ///Its \c Key and \c Value are inherited from \c M. - ///The unary \c - operator must be defined for \c Value, of course. - /// - ///\sa NegWriteMap - template - class NegMap : public MapBase { - const M& m; + /// \sa NegMap + template + class NegWriteMap : public MapBase { + M &_m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor - NegMap(const M &_m) : m(_m) {}; + /// Constructor + NegWriteMap(M &m) : _m(m) {} /// \e - Value operator[](Key k) const {return -m[k];} + Value operator[](const Key &k) const { return -_m[k]; } + /// \e + void set(const Key &k, const Value &v) { _m.set(k, -v); } }; - - ///Negative value of a map (ReadWrite version) - ///This \ref concepts::ReadWriteMap "read-write map" returns the negative - ///value of the value returned by the given map. - ///Its \c Key and \c Value are inherited from \c M. - ///The unary \c - operator must be defined for \c Value, of course. + /// Returns a \ref NegMap class + + /// This function just returns a \ref NegMap class. /// - /// \sa NegMap - template - class NegWriteMap : public MapBase { - M& m; + /// For example, if \c m is a map with \c double values, then + /// negMap(m)[x] will be equal to -m[x]. + /// + /// \relates NegMap + template + inline NegMap negMap(const M &m) { + return NegMap(m); + } + + /// Returns a \ref NegWriteMap class + + /// This function just returns a \ref NegWriteMap class. + /// + /// For example, if \c m is a map with \c double values, then + /// negWriteMap(m)[x] will be equal to -m[x]. + /// Moreover it makes also possible to write the map. + /// + /// \relates NegWriteMap + template + inline NegWriteMap negWriteMap(M &m) { + return NegWriteMap(m); + } + + + /// Absolute value of a map + + /// This \ref concepts::ReadMap "read-only map" returns the absolute + /// value of the values of the given map. + /// Its \c Key and \c Value are inherited from \c M. + /// \c Value must be comparable to \c 0 and the unary \c - + /// operator must be defined for it, of course. + /// + /// The simplest way of using this map is through the absMap() + /// function. + template + class AbsMap : public MapBase { + const M &_m; public: typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor - NegWriteMap(M &_m) : m(_m) {}; + /// Constructor + AbsMap(const M &m) : _m(m) {} /// \e - Value operator[](Key k) const {return -m[k];} - /// \e - void set(Key k, const Value& v) { m.set(k, -v); } - }; - - ///Returns a \c NegMap class - - ///This function just returns a \c NegMap class. - ///\relates NegMap - template - inline NegMap negMap(const M &m) { - return NegMap(m); - } - - ///Returns a \c NegWriteMap class - - ///This function just returns a \c NegWriteMap class. - ///\relates NegWriteMap - template - inline NegWriteMap negMap(M &m) { - return NegWriteMap(m); - } - - ///Absolute value of a map - - ///This \ref concepts::ReadMap "read only map" returns the absolute value - ///of the value returned by the given map. - ///Its \c Key and \c Value are inherited from \c M. - ///\c Value must be comparable to \c 0 and the unary \c - - ///operator must be defined for it, of course. - template - class AbsMap : public MapBase { - const M& m; - public: - typedef MapBase Parent; - typedef typename Parent::Key Key; - typedef typename Parent::Value Value; - - ///Constructor - AbsMap(const M &_m) : m(_m) {}; - /// \e - Value operator[](Key k) const { - Value tmp = m[k]; + Value operator[](const Key &k) const { + Value tmp = _m[k]; return tmp >= 0 ? tmp : -tmp; } }; - - ///Returns an \c AbsMap class - ///This function just returns an \c AbsMap class. - ///\relates AbsMap - template + /// Returns an \ref AbsMap class + + /// This function just returns an \ref AbsMap class. + /// + /// For example, if \c m is a map with \c double values, then + /// absMap(m)[x] will be equal to m[x] if + /// it is positive or zero and -m[x] if m[x] is + /// negative. + /// + /// \relates AbsMap + template inline AbsMap absMap(const M &m) { return AbsMap(m); } - ///Converts an STL style functor to a map + /// @} + + // Logical maps and map adaptors: - ///This \ref concepts::ReadMap "read only map" returns the value - ///of a given functor. + /// \addtogroup maps + /// @{ + + /// Constant \c true map. + + /// This \ref concepts::ReadMap "read-only map" assigns \c true to + /// each key. /// - ///Template parameters \c K and \c V will become its - ///\c Key and \c Value. - ///In most cases they have to be given explicitly because a - ///functor typically does not provide \c argument_type and - ///\c result_type typedefs. + /// Note that + /// \code + /// TrueMap tm; + /// \endcode + /// is equivalent to + /// \code + /// ConstMap tm(true); + /// \endcode /// - ///Parameter \c F is the type of the used functor. - /// - ///\sa MapFunctor - template - class FunctorMap : public MapBase { - F f; + /// \sa FalseMap + /// \sa ConstMap + template + class TrueMap : public MapBase { public: - typedef MapBase Parent; + typedef MapBase Parent; typedef typename Parent::Key Key; typedef typename Parent::Value Value; - ///Constructor - FunctorMap(const F &_f = F()) : f(_f) {} - /// \e - Value operator[](Key k) const { return f(k);} + /// Gives back \c true. + Value operator[](const Key&) const { return true; } }; - - ///Returns a \c FunctorMap class - ///This function just returns a \c FunctorMap class. - /// - ///This function is specialized for adaptable binary function - ///classes and C++ functions. - /// - ///\relates FunctorMap - template inline - FunctorMap functorMap(const F &f) { - return FunctorMap(f); + /// Returns a \ref TrueMap class + + /// This function just returns a \ref TrueMap class. + /// \relates TrueMap + template + inline TrueMap trueMap() { + return TrueMap(); } - template inline - FunctorMap - functorMap(const F &f) { - return FunctorMap(f); - } - template inline - FunctorMap functorMap(V (*f)(K)) { - return FunctorMap(f); - } + /// Constant \c false map. - - ///Converts a map to an STL style (unary) functor - - ///This class Converts a map to an STL style (unary) functor. - ///That is it provides an operator() to read its values. + /// This \ref concepts::ReadMap "read-only map" assigns \c false to + /// each key. /// - ///For the sake of convenience it also works as - ///a ususal \ref concepts::ReadMap "readable map", - ///i.e. operator[] and the \c Key and \c Value typedefs also exist. + /// Note that + /// \code + /// FalseMap fm; + /// \endcode + /// is equivalent to + /// \code + /// ConstMap fm(false); + /// \endcode /// - ///\sa FunctorMap - template - class MapFunctor : public MapBase { - const M& m; + /// \sa TrueMap + /// \sa ConstMap + template + class FalseMap : public MapBase { public: - typedef MapBase Parent; + typedef MapBase