1.1 --- a/lemon/maps.h Thu Feb 28 17:06:02 2008 +0100
1.2 +++ b/lemon/maps.h Sun Mar 16 07:32:43 2008 +0000
1.3 @@ -24,12 +24,12 @@
1.4 #include <vector>
1.5
1.6 #include <lemon/bits/utility.h>
1.7 -// #include <lemon/bits/traits.h>
1.8 +#include <lemon/bits/traits.h>
1.9
1.10 ///\file
1.11 ///\ingroup maps
1.12 ///\brief Miscellaneous property maps
1.13 -///
1.14 +
1.15 #include <map>
1.16
1.17 namespace lemon {
1.18 @@ -39,41 +39,46 @@
1.19
1.20 /// Base class of maps.
1.21
1.22 - /// Base class of maps.
1.23 - /// It provides the necessary <tt>typedef</tt>s required by the map concept.
1.24 - template<typename K, typename T>
1.25 + /// Base class of maps. It provides the necessary type definitions
1.26 + /// required by the map %concepts.
1.27 + template<typename K, typename V>
1.28 class MapBase {
1.29 public:
1.30 - /// The key type of the map.
1.31 + /// \biref The key type of the map.
1.32 typedef K Key;
1.33 - /// The value type of the map. (The type of objects associated with the keys).
1.34 - typedef T Value;
1.35 + /// \brief The value type of the map.
1.36 + /// (The type of objects associated with the keys).
1.37 + typedef V Value;
1.38 };
1.39
1.40 +
1.41 /// Null map. (a.k.a. DoNothingMap)
1.42
1.43 /// This map can be used if you have to provide a map only for
1.44 - /// its type definitions, or if you have to provide a writable map,
1.45 - /// but data written to it is not required (i.e. it will be sent to
1.46 + /// its type definitions, or if you have to provide a writable map,
1.47 + /// but data written to it is not required (i.e. it will be sent to
1.48 /// <tt>/dev/null</tt>).
1.49 - template<typename K, typename T>
1.50 - class NullMap : public MapBase<K, T> {
1.51 + /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.52 + ///
1.53 + /// \sa ConstMap
1.54 + template<typename K, typename V>
1.55 + class NullMap : public MapBase<K, V> {
1.56 public:
1.57 - typedef MapBase<K, T> Parent;
1.58 + typedef MapBase<K, V> Parent;
1.59 typedef typename Parent::Key Key;
1.60 typedef typename Parent::Value Value;
1.61 -
1.62 +
1.63 /// Gives back a default constructed element.
1.64 - T operator[](const K&) const { return T(); }
1.65 + Value operator[](const Key&) const { return Value(); }
1.66 /// Absorbs the value.
1.67 - void set(const K&, const T&) {}
1.68 + void set(const Key&, const Value&) {}
1.69 };
1.70
1.71 - ///Returns a \c NullMap class
1.72 + /// Returns a \ref NullMap class
1.73
1.74 - ///This function just returns a \c NullMap class.
1.75 - ///\relates NullMap
1.76 - template <typename K, typename V>
1.77 + /// This function just returns a \ref NullMap class.
1.78 + /// \relates NullMap
1.79 + template <typename K, typename V>
1.80 NullMap<K, V> nullMap() {
1.81 return NullMap<K, V>();
1.82 }
1.83 @@ -81,62 +86,81 @@
1.84
1.85 /// Constant map.
1.86
1.87 - /// This is a \ref concepts::ReadMap "readable" map which assigns a
1.88 - /// specified value to each key.
1.89 - /// In other aspects it is equivalent to \c NullMap.
1.90 - template<typename K, typename T>
1.91 - class ConstMap : public MapBase<K, T> {
1.92 + /// This \ref concepts::ReadMap "readable map" assigns a specified
1.93 + /// value to each key.
1.94 + ///
1.95 + /// In other aspects it is equivalent to \ref NullMap.
1.96 + /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
1.97 + /// concept, but it absorbs the data written to it.
1.98 + ///
1.99 + /// The simplest way of using this map is through the constMap()
1.100 + /// function.
1.101 + ///
1.102 + /// \sa NullMap
1.103 + /// \sa IdentityMap
1.104 + template<typename K, typename V>
1.105 + class ConstMap : public MapBase<K, V> {
1.106 private:
1.107 - T v;
1.108 + V _value;
1.109 public:
1.110 -
1.111 - typedef MapBase<K, T> Parent;
1.112 + typedef MapBase<K, V> Parent;
1.113 typedef typename Parent::Key Key;
1.114 typedef typename Parent::Value Value;
1.115
1.116 /// Default constructor
1.117
1.118 /// Default constructor.
1.119 - /// The value of the map will be uninitialized.
1.120 - /// (More exactly it will be default constructed.)
1.121 + /// The value of the map will be default constructed.
1.122 ConstMap() {}
1.123 -
1.124 +
1.125 /// Constructor with specified initial value
1.126
1.127 /// Constructor with specified initial value.
1.128 - /// \param _v is the initial value of the map.
1.129 - ConstMap(const T &_v) : v(_v) {}
1.130 -
1.131 - ///\e
1.132 - T operator[](const K&) const { return v; }
1.133 + /// \param v is the initial value of the map.
1.134 + ConstMap(const Value &v) : _value(v) {}
1.135
1.136 - ///\e
1.137 - void setAll(const T &t) {
1.138 - v = t;
1.139 - }
1.140 + /// Gives back the specified value.
1.141 + Value operator[](const Key&) const { return _value; }
1.142
1.143 - template<typename T1>
1.144 - ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
1.145 + /// Absorbs the value.
1.146 + void set(const Key&, const Value&) {}
1.147 +
1.148 + /// Sets the value that is assigned to each key.
1.149 + void setAll(const Value &v) {
1.150 + _value = v;
1.151 + }
1.152 +
1.153 + template<typename V1>
1.154 + ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
1.155 };
1.156
1.157 - ///Returns a \c ConstMap class
1.158 + /// Returns a \ref ConstMap class
1.159
1.160 - ///This function just returns a \c ConstMap class.
1.161 - ///\relates ConstMap
1.162 - template<typename K, typename V>
1.163 + /// This function just returns a \ref ConstMap class.
1.164 + /// \relates ConstMap
1.165 + template<typename K, typename V>
1.166 inline ConstMap<K, V> constMap(const V &v) {
1.167 return ConstMap<K, V>(v);
1.168 }
1.169
1.170
1.171 template<typename T, T v>
1.172 - struct Const { };
1.173 + struct Const {};
1.174
1.175 /// Constant map with inlined constant value.
1.176
1.177 - /// This is a \ref concepts::ReadMap "readable" map which assigns a
1.178 - /// specified value to each key.
1.179 - /// In other aspects it is equivalent to \c NullMap.
1.180 + /// This \ref concepts::ReadMap "readable map" assigns a specified
1.181 + /// value to each key.
1.182 + ///
1.183 + /// In other aspects it is equivalent to \ref NullMap.
1.184 + /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
1.185 + /// concept, but it absorbs the data written to it.
1.186 + ///
1.187 + /// The simplest way of using this map is through the constMap()
1.188 + /// function.
1.189 + ///
1.190 + /// \sa NullMap
1.191 + /// \sa IdentityMap
1.192 template<typename K, typename V, V v>
1.193 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
1.194 public:
1.195 @@ -144,69 +168,230 @@
1.196 typedef typename Parent::Key Key;
1.197 typedef typename Parent::Value Value;
1.198
1.199 - ConstMap() { }
1.200 - ///\e
1.201 - V operator[](const K&) const { return v; }
1.202 - ///\e
1.203 - void set(const K&, const V&) { }
1.204 + /// Constructor.
1.205 + ConstMap() {}
1.206 +
1.207 + /// Gives back the specified value.
1.208 + Value operator[](const Key&) const { return v; }
1.209 +
1.210 + /// Absorbs the value.
1.211 + void set(const Key&, const Value&) {}
1.212 };
1.213
1.214 - ///Returns a \c ConstMap class with inlined value
1.215 + /// Returns a \ref ConstMap class with inlined constant value
1.216
1.217 - ///This function just returns a \c ConstMap class with inlined value.
1.218 - ///\relates ConstMap
1.219 - template<typename K, typename V, V v>
1.220 + /// This function just returns a \ref ConstMap class with inlined
1.221 + /// constant value.
1.222 + /// \relates ConstMap
1.223 + template<typename K, typename V, V v>
1.224 inline ConstMap<K, Const<V, v> > constMap() {
1.225 return ConstMap<K, Const<V, v> >();
1.226 }
1.227
1.228 - ///Map based on \c std::map
1.229
1.230 - ///This is essentially a wrapper for \c std::map with addition that
1.231 - ///you can specify a default value different from \c Value().
1.232 - ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
1.233 - template <typename K, typename T, typename Compare = std::less<K> >
1.234 - class StdMap : public MapBase<K, T> {
1.235 - template <typename K1, typename T1, typename C1>
1.236 - friend class StdMap;
1.237 + /// Identity map.
1.238 +
1.239 + /// This \ref concepts::ReadMap "read-only map" gives back the given
1.240 + /// key as value without any modification.
1.241 + ///
1.242 + /// \sa ConstMap
1.243 + template <typename T>
1.244 + class IdentityMap : public MapBase<T, T> {
1.245 + public:
1.246 + typedef MapBase<T, T> Parent;
1.247 + typedef typename Parent::Key Key;
1.248 + typedef typename Parent::Value Value;
1.249 +
1.250 + /// Gives back the given value without any modification.
1.251 + Value operator[](const Key &k) const {
1.252 + return k;
1.253 + }
1.254 + };
1.255 +
1.256 + /// Returns an \ref IdentityMap class
1.257 +
1.258 + /// This function just returns an \ref IdentityMap class.
1.259 + /// \relates IdentityMap
1.260 + template<typename T>
1.261 + inline IdentityMap<T> identityMap() {
1.262 + return IdentityMap<T>();
1.263 + }
1.264 +
1.265 +
1.266 + /// \brief Map for storing values for integer keys from the range
1.267 + /// <tt>[0..size-1]</tt>.
1.268 + ///
1.269 + /// This map is essentially a wrapper for \c std::vector. It assigns
1.270 + /// values to integer keys from the range <tt>[0..size-1]</tt>.
1.271 + /// It can be used with some data structures, for example
1.272 + /// \ref UnionFind, \ref BinHeap, when the used items are small
1.273 + /// integers. This map conforms the \ref concepts::ReferenceMap
1.274 + /// "ReferenceMap" concept.
1.275 + ///
1.276 + /// The simplest way of using this map is through the rangeMap()
1.277 + /// function.
1.278 + template <typename V>
1.279 + class RangeMap : public MapBase<int, V> {
1.280 + template <typename V1>
1.281 + friend class RangeMap;
1.282 + private:
1.283 +
1.284 + typedef std::vector<V> Vector;
1.285 + Vector _vector;
1.286 +
1.287 public:
1.288
1.289 - typedef MapBase<K, T> Parent;
1.290 - ///Key type
1.291 + typedef MapBase<int, V> Parent;
1.292 + /// Key type
1.293 typedef typename Parent::Key Key;
1.294 - ///Value type
1.295 + /// Value type
1.296 typedef typename Parent::Value Value;
1.297 - ///Reference Type
1.298 - typedef T& Reference;
1.299 - ///Const reference type
1.300 - typedef const T& ConstReference;
1.301 + /// Reference type
1.302 + typedef typename Vector::reference Reference;
1.303 + /// Const reference type
1.304 + typedef typename Vector::const_reference ConstReference;
1.305 +
1.306 + typedef True ReferenceMapTag;
1.307 +
1.308 + public:
1.309 +
1.310 + /// Constructor with specified default value.
1.311 + RangeMap(int size = 0, const Value &value = Value())
1.312 + : _vector(size, value) {}
1.313 +
1.314 + /// Constructs the map from an appropriate \c std::vector.
1.315 + template <typename V1>
1.316 + RangeMap(const std::vector<V1>& vector)
1.317 + : _vector(vector.begin(), vector.end()) {}
1.318 +
1.319 + /// Constructs the map from another \ref RangeMap.
1.320 + template <typename V1>
1.321 + RangeMap(const RangeMap<V1> &c)
1.322 + : _vector(c._vector.begin(), c._vector.end()) {}
1.323 +
1.324 + /// Returns the size of the map.
1.325 + int size() {
1.326 + return _vector.size();
1.327 + }
1.328 +
1.329 + /// Resizes the map.
1.330 +
1.331 + /// Resizes the underlying \c std::vector container, so changes the
1.332 + /// keyset of the map.
1.333 + /// \param size The new size of the map. The new keyset will be the
1.334 + /// range <tt>[0..size-1]</tt>.
1.335 + /// \param value The default value to assign to the new keys.
1.336 + void resize(int size, const Value &value = Value()) {
1.337 + _vector.resize(size, value);
1.338 + }
1.339 +
1.340 + private:
1.341 +
1.342 + RangeMap& operator=(const RangeMap&);
1.343 +
1.344 + public:
1.345 +
1.346 + ///\e
1.347 + Reference operator[](const Key &k) {
1.348 + return _vector[k];
1.349 + }
1.350 +
1.351 + ///\e
1.352 + ConstReference operator[](const Key &k) const {
1.353 + return _vector[k];
1.354 + }
1.355 +
1.356 + ///\e
1.357 + void set(const Key &k, const Value &v) {
1.358 + _vector[k] = v;
1.359 + }
1.360 + };
1.361 +
1.362 + /// Returns a \ref RangeMap class
1.363 +
1.364 + /// This function just returns a \ref RangeMap class.
1.365 + /// \relates RangeMap
1.366 + template<typename V>
1.367 + inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
1.368 + return RangeMap<V>(size, value);
1.369 + }
1.370 +
1.371 + /// \brief Returns a \ref RangeMap class created from an appropriate
1.372 + /// \c std::vector
1.373 +
1.374 + /// This function just returns a \ref RangeMap class created from an
1.375 + /// appropriate \c std::vector.
1.376 + /// \relates RangeMap
1.377 + template<typename V>
1.378 + inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
1.379 + return RangeMap<V>(vector);
1.380 + }
1.381 +
1.382 +
1.383 + /// Map type based on \c std::map
1.384 +
1.385 + /// This map is essentially a wrapper for \c std::map with addition
1.386 + /// that you can specify a default value for the keys that are not
1.387 + /// stored actually. This value can be different from the default
1.388 + /// contructed value (i.e. \c %Value()).
1.389 + /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
1.390 + /// concept.
1.391 + ///
1.392 + /// This map is useful if a default value should be assigned to most of
1.393 + /// the keys and different values should be assigned only to a few
1.394 + /// keys (i.e. the map is "sparse").
1.395 + /// The name of this type also refers to this important usage.
1.396 + ///
1.397 + /// Apart form that this map can be used in many other cases since it
1.398 + /// is based on \c std::map, which is a general associative container.
1.399 + /// However keep in mind that it is usually not as efficient as other
1.400 + /// maps.
1.401 + ///
1.402 + /// The simplest way of using this map is through the sparseMap()
1.403 + /// function.
1.404 + template <typename K, typename V, typename Compare = std::less<K> >
1.405 + class SparseMap : public MapBase<K, V> {
1.406 + template <typename K1, typename V1, typename C1>
1.407 + friend class SparseMap;
1.408 + public:
1.409 +
1.410 + typedef MapBase<K, V> Parent;
1.411 + /// Key type
1.412 + typedef typename Parent::Key Key;
1.413 + /// Value type
1.414 + typedef typename Parent::Value Value;
1.415 + /// Reference type
1.416 + typedef Value& Reference;
1.417 + /// Const reference type
1.418 + typedef const Value& ConstReference;
1.419
1.420 typedef True ReferenceMapTag;
1.421
1.422 private:
1.423 -
1.424 - typedef std::map<K, T, Compare> Map;
1.425 +
1.426 + typedef std::map<K, V, Compare> Map;
1.427 + Map _map;
1.428 Value _value;
1.429 - Map _map;
1.430
1.431 public:
1.432
1.433 - /// Constructor with specified default value
1.434 - StdMap(const T& value = T()) : _value(value) {}
1.435 - /// \brief Constructs the map from an appropriate \c std::map, and
1.436 + /// \brief Constructor with specified default value.
1.437 + SparseMap(const Value &value = Value()) : _value(value) {}
1.438 + /// \brief Constructs the map from an appropriate \c std::map, and
1.439 /// explicitly specifies a default value.
1.440 - template <typename T1, typename Comp1>
1.441 - StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
1.442 + template <typename V1, typename Comp1>
1.443 + SparseMap(const std::map<Key, V1, Comp1> &map,
1.444 + const Value &value = Value())
1.445 : _map(map.begin(), map.end()), _value(value) {}
1.446 -
1.447 - /// \brief Constructs a map from an other \ref StdMap.
1.448 - template<typename T1, typename Comp1>
1.449 - StdMap(const StdMap<Key, T1, Comp1> &c)
1.450 +
1.451 + /// \brief Constructs the map from another \ref SparseMap.
1.452 + template<typename V1, typename Comp1>
1.453 + SparseMap(const SparseMap<Key, V1, Comp1> &c)
1.454 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
1.455
1.456 private:
1.457
1.458 - StdMap& operator=(const StdMap&);
1.459 + SparseMap& operator=(const SparseMap&);
1.460
1.461 public:
1.462
1.463 @@ -219,7 +404,7 @@
1.464 return _map.insert(it, std::make_pair(k, _value))->second;
1.465 }
1.466
1.467 - /// \e
1.468 + ///\e
1.469 ConstReference operator[](const Key &k) const {
1.470 typename Map::const_iterator it = _map.find(k);
1.471 if (it != _map.end())
1.472 @@ -228,149 +413,48 @@
1.473 return _value;
1.474 }
1.475
1.476 - /// \e
1.477 - void set(const Key &k, const T &t) {
1.478 + ///\e
1.479 + void set(const Key &k, const Value &v) {
1.480 typename Map::iterator it = _map.lower_bound(k);
1.481 if (it != _map.end() && !_map.key_comp()(k, it->first))
1.482 - it->second = t;
1.483 + it->second = v;
1.484 else
1.485 - _map.insert(it, std::make_pair(k, t));
1.486 + _map.insert(it, std::make_pair(k, v));
1.487 }
1.488
1.489 - /// \e
1.490 - void setAll(const T &t) {
1.491 - _value = t;
1.492 + ///\e
1.493 + void setAll(const Value &v) {
1.494 + _value = v;
1.495 _map.clear();
1.496 - }
1.497 + }
1.498 + };
1.499
1.500 - };
1.501 -
1.502 - ///Returns a \c StdMap class
1.503 + /// Returns a \ref SparseMap class
1.504
1.505 - ///This function just returns a \c StdMap class with specified
1.506 - ///default value.
1.507 - ///\relates StdMap
1.508 - template<typename K, typename V, typename Compare>
1.509 - inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
1.510 - return StdMap<K, V, Compare>(value);
1.511 - }
1.512 -
1.513 - ///Returns a \c StdMap class
1.514 -
1.515 - ///This function just returns a \c StdMap class with specified
1.516 - ///default value.
1.517 - ///\relates StdMap
1.518 - template<typename K, typename V>
1.519 - inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {
1.520 - return StdMap<K, V, std::less<K> >(value);
1.521 - }
1.522 -
1.523 - ///Returns a \c StdMap class created from an appropriate std::map
1.524 -
1.525 - ///This function just returns a \c StdMap class created from an
1.526 - ///appropriate std::map.
1.527 - ///\relates StdMap
1.528 - template<typename K, typename V, typename Compare>
1.529 - inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,
1.530 - const V& value = V() ) {
1.531 - return StdMap<K, V, Compare>(map, value);
1.532 + /// This function just returns a \ref SparseMap class with specified
1.533 + /// default value.
1.534 + /// \relates SparseMap
1.535 + template<typename K, typename V, typename Compare>
1.536 + inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
1.537 + return SparseMap<K, V, Compare>(value);
1.538 }
1.539
1.540 - ///Returns a \c StdMap class created from an appropriate std::map
1.541 -
1.542 - ///This function just returns a \c StdMap class created from an
1.543 - ///appropriate std::map.
1.544 - ///\relates StdMap
1.545 - template<typename K, typename V>
1.546 - inline StdMap<K, V, std::less<K> > stdMap( const std::map<K, V, std::less<K> > &map,
1.547 - const V& value = V() ) {
1.548 - return StdMap<K, V, std::less<K> >(map, value);
1.549 + template<typename K, typename V>
1.550 + inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
1.551 + return SparseMap<K, V, std::less<K> >(value);
1.552 }
1.553
1.554 - /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
1.555 - ///
1.556 - /// This map has the <tt>[0..size-1]</tt> keyset and the values
1.557 - /// are stored in a \c std::vector<T> container. It can be used with
1.558 - /// some data structures, for example \c UnionFind, \c BinHeap, when
1.559 - /// the used items are small integer numbers.
1.560 - /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
1.561 - ///
1.562 - /// \todo Revise its name
1.563 - template <typename T>
1.564 - class IntegerMap : public MapBase<int, T> {
1.565 + /// \brief Returns a \ref SparseMap class created from an appropriate
1.566 + /// \c std::map
1.567
1.568 - template <typename T1>
1.569 - friend class IntegerMap;
1.570 -
1.571 - public:
1.572 -
1.573 - typedef MapBase<int, T> Parent;
1.574 - ///\e
1.575 - typedef typename Parent::Key Key;
1.576 - ///\e
1.577 - typedef typename Parent::Value Value;
1.578 - ///\e
1.579 - typedef T& Reference;
1.580 - ///\e
1.581 - typedef const T& ConstReference;
1.582 -
1.583 - typedef True ReferenceMapTag;
1.584 -
1.585 - private:
1.586 -
1.587 - typedef std::vector<T> Vector;
1.588 - Vector _vector;
1.589 -
1.590 - public:
1.591 -
1.592 - /// Constructor with specified default value
1.593 - IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
1.594 -
1.595 - /// \brief Constructs the map from an appropriate \c std::vector.
1.596 - template <typename T1>
1.597 - IntegerMap(const std::vector<T1>& vector)
1.598 - : _vector(vector.begin(), vector.end()) {}
1.599 -
1.600 - /// \brief Constructs a map from an other \ref IntegerMap.
1.601 - template <typename T1>
1.602 - IntegerMap(const IntegerMap<T1> &c)
1.603 - : _vector(c._vector.begin(), c._vector.end()) {}
1.604 -
1.605 - /// \brief Resize the container
1.606 - void resize(int size, const T& value = T()) {
1.607 - _vector.resize(size, value);
1.608 - }
1.609 -
1.610 - private:
1.611 -
1.612 - IntegerMap& operator=(const IntegerMap&);
1.613 -
1.614 - public:
1.615 -
1.616 - ///\e
1.617 - Reference operator[](Key k) {
1.618 - return _vector[k];
1.619 - }
1.620 -
1.621 - /// \e
1.622 - ConstReference operator[](Key k) const {
1.623 - return _vector[k];
1.624 - }
1.625 -
1.626 - /// \e
1.627 - void set(const Key &k, const T& t) {
1.628 - _vector[k] = t;
1.629 - }
1.630 -
1.631 - };
1.632 -
1.633 - ///Returns an \c IntegerMap class
1.634 -
1.635 - ///This function just returns an \c IntegerMap class.
1.636 - ///\relates IntegerMap
1.637 - template<typename T>
1.638 - inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
1.639 - return IntegerMap<T>(size, value);
1.640 + /// This function just returns a \ref SparseMap class created from an
1.641 + /// appropriate \c std::map.
1.642 + /// \relates SparseMap
1.643 + template<typename K, typename V, typename Compare>
1.644 + inline SparseMap<K, V, Compare>
1.645 + sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
1.646 + {
1.647 + return SparseMap<K, V, Compare>(map, value);
1.648 }
1.649
1.650 /// @}
1.651 @@ -378,1260 +462,1210 @@
1.652 /// \addtogroup map_adaptors
1.653 /// @{
1.654
1.655 - /// \brief Identity map.
1.656 + /// Composition of two maps
1.657 +
1.658 + /// This \ref concepts::ReadMap "read-only map" returns the
1.659 + /// composition of two given maps. That is to say, if \c m1 is of
1.660 + /// type \c M1 and \c m2 is of \c M2, then for
1.661 + /// \code
1.662 + /// ComposeMap<M1, M2> cm(m1,m2);
1.663 + /// \endcode
1.664 + /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
1.665 ///
1.666 - /// This map gives back the given key as value without any
1.667 - /// modification.
1.668 - template <typename T>
1.669 - class IdentityMap : public MapBase<T, T> {
1.670 + /// The \c Key type of the map is inherited from \c M2 and the
1.671 + /// \c Value type is from \c M1.
1.672 + /// \c M2::Value must be convertible to \c M1::Key.
1.673 + ///
1.674 + /// The simplest way of using this map is through the composeMap()
1.675 + /// function.
1.676 + ///
1.677 + /// \sa CombineMap
1.678 + ///
1.679 + /// \todo Check the requirements.
1.680 + template <typename M1, typename M2>
1.681 + class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
1.682 + const M1 &_m1;
1.683 + const M2 &_m2;
1.684 public:
1.685 - typedef MapBase<T, T> Parent;
1.686 + typedef MapBase<typename M2::Key, typename M1::Value> Parent;
1.687 typedef typename Parent::Key Key;
1.688 typedef typename Parent::Value Value;
1.689
1.690 + /// Constructor
1.691 + ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.692 +
1.693 /// \e
1.694 - const T& operator[](const T& t) const {
1.695 - return t;
1.696 - }
1.697 + typename MapTraits<M1>::ConstReturnValue
1.698 + operator[](const Key &k) const { return _m1[_m2[k]]; }
1.699 };
1.700
1.701 - ///Returns an \c IdentityMap class
1.702 + /// Returns a \ref ComposeMap class
1.703
1.704 - ///This function just returns an \c IdentityMap class.
1.705 - ///\relates IdentityMap
1.706 - template<typename T>
1.707 - inline IdentityMap<T> identityMap() {
1.708 - return IdentityMap<T>();
1.709 + /// This function just returns a \ref ComposeMap class.
1.710 + ///
1.711 + /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
1.712 + /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
1.713 + /// will be equal to <tt>m1[m2[x]]</tt>.
1.714 + ///
1.715 + /// \relates ComposeMap
1.716 + template <typename M1, typename M2>
1.717 + inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
1.718 + return ComposeMap<M1, M2>(m1, m2);
1.719 }
1.720 -
1.721
1.722 - ///\brief Convert the \c Value of a map to another type using
1.723 - ///the default conversion.
1.724 +
1.725 + /// Combination of two maps using an STL (binary) functor.
1.726 +
1.727 + /// This \ref concepts::ReadMap "read-only map" takes two maps and a
1.728 + /// binary functor and returns the combination of the two given maps
1.729 + /// using the functor.
1.730 + /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
1.731 + /// and \c f is of \c F, then for
1.732 + /// \code
1.733 + /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
1.734 + /// \endcode
1.735 + /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
1.736 ///
1.737 - ///This \ref concepts::ReadMap "read only map"
1.738 - ///converts the \c Value of a map to type \c T.
1.739 - ///Its \c Key is inherited from \c M.
1.740 - template <typename M, typename T>
1.741 - class ConvertMap : public MapBase<typename M::Key, T> {
1.742 - const M& m;
1.743 + /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
1.744 + /// must be convertible to \c M2::Key) and the \c Value type is \c V.
1.745 + /// \c M2::Value and \c M1::Value must be convertible to the
1.746 + /// corresponding input parameter of \c F and the return type of \c F
1.747 + /// must be convertible to \c V.
1.748 + ///
1.749 + /// The simplest way of using this map is through the combineMap()
1.750 + /// function.
1.751 + ///
1.752 + /// \sa ComposeMap
1.753 + ///
1.754 + /// \todo Check the requirements.
1.755 + template<typename M1, typename M2, typename F,
1.756 + typename V = typename F::result_type>
1.757 + class CombineMap : public MapBase<typename M1::Key, V> {
1.758 + const M1 &_m1;
1.759 + const M2 &_m2;
1.760 + F _f;
1.761 public:
1.762 - typedef MapBase<typename M::Key, T> Parent;
1.763 + typedef MapBase<typename M1::Key, V> Parent;
1.764 typedef typename Parent::Key Key;
1.765 typedef typename Parent::Value Value;
1.766
1.767 - ///Constructor
1.768 + /// Constructor
1.769 + CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
1.770 + : _m1(m1), _m2(m2), _f(f) {}
1.771 + /// \e
1.772 + Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
1.773 + };
1.774
1.775 - ///Constructor.
1.776 - ///\param _m is the underlying map.
1.777 - ConvertMap(const M &_m) : m(_m) {};
1.778 + /// Returns a \ref CombineMap class
1.779
1.780 - ///\e
1.781 - Value operator[](const Key& k) const {return m[k];}
1.782 - };
1.783 -
1.784 - ///Returns a \c ConvertMap class
1.785 -
1.786 - ///This function just returns a \c ConvertMap class.
1.787 - ///\relates ConvertMap
1.788 - template<typename T, typename M>
1.789 - inline ConvertMap<M, T> convertMap(const M &m) {
1.790 - return ConvertMap<M, T>(m);
1.791 + /// This function just returns a \ref CombineMap class.
1.792 + ///
1.793 + /// For example, if \c m1 and \c m2 are both maps with \c double
1.794 + /// values, then
1.795 + /// \code
1.796 + /// combineMap(m1,m2,std::plus<double>())
1.797 + /// \endcode
1.798 + /// is equivalent to
1.799 + /// \code
1.800 + /// addMap(m1,m2)
1.801 + /// \endcode
1.802 + ///
1.803 + /// This function is specialized for adaptable binary function
1.804 + /// classes and C++ functions.
1.805 + ///
1.806 + /// \relates CombineMap
1.807 + template<typename M1, typename M2, typename F, typename V>
1.808 + inline CombineMap<M1, M2, F, V>
1.809 + combineMap(const M1 &m1, const M2 &m2, const F &f) {
1.810 + return CombineMap<M1, M2, F, V>(m1,m2,f);
1.811 }
1.812
1.813 - ///Simple wrapping of a map
1.814 + template<typename M1, typename M2, typename F>
1.815 + inline CombineMap<M1, M2, F, typename F::result_type>
1.816 + combineMap(const M1 &m1, const M2 &m2, const F &f) {
1.817 + return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
1.818 + }
1.819
1.820 - ///This \ref concepts::ReadMap "read only map" returns the simple
1.821 - ///wrapping of the given map. Sometimes the reference maps cannot be
1.822 - ///combined with simple read maps. This map adaptor wraps the given
1.823 - ///map to simple read map.
1.824 + template<typename M1, typename M2, typename K1, typename K2, typename V>
1.825 + inline CombineMap<M1, M2, V (*)(K1, K2), V>
1.826 + combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
1.827 + return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
1.828 + }
1.829 +
1.830 +
1.831 + /// Converts an STL style (unary) functor to a map
1.832 +
1.833 + /// This \ref concepts::ReadMap "read-only map" returns the value
1.834 + /// of a given functor. Actually, it just wraps the functor and
1.835 + /// provides the \c Key and \c Value typedefs.
1.836 ///
1.837 - ///\sa SimpleWriteMap
1.838 + /// Template parameters \c K and \c V will become its \c Key and
1.839 + /// \c Value. In most cases they have to be given explicitly because
1.840 + /// a functor typically does not provide \c argument_type and
1.841 + /// \c result_type typedefs.
1.842 + /// Parameter \c F is the type of the used functor.
1.843 ///
1.844 - /// \todo Revise the misleading name
1.845 - template<typename M>
1.846 - class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
1.847 - const M& m;
1.848 + /// The simplest way of using this map is through the functorToMap()
1.849 + /// function.
1.850 + ///
1.851 + /// \sa MapToFunctor
1.852 + template<typename F,
1.853 + typename K = typename F::argument_type,
1.854 + typename V = typename F::result_type>
1.855 + class FunctorToMap : public MapBase<K, V> {
1.856 + const F &_f;
1.857 + public:
1.858 + typedef MapBase<K, V> Parent;
1.859 + typedef typename Parent::Key Key;
1.860 + typedef typename Parent::Value Value;
1.861
1.862 + /// Constructor
1.863 + FunctorToMap(const F &f = F()) : _f(f) {}
1.864 + /// \e
1.865 + Value operator[](const Key &k) const { return _f(k); }
1.866 + };
1.867 +
1.868 + /// Returns a \ref FunctorToMap class
1.869 +
1.870 + /// This function just returns a \ref FunctorToMap class.
1.871 + ///
1.872 + /// This function is specialized for adaptable binary function
1.873 + /// classes and C++ functions.
1.874 + ///
1.875 + /// \relates FunctorToMap
1.876 + template<typename K, typename V, typename F>
1.877 + inline FunctorToMap<F, K, V> functorToMap(const F &f) {
1.878 + return FunctorToMap<F, K, V>(f);
1.879 + }
1.880 +
1.881 + template <typename F>
1.882 + inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
1.883 + functorToMap(const F &f)
1.884 + {
1.885 + return FunctorToMap<F, typename F::argument_type,
1.886 + typename F::result_type>(f);
1.887 + }
1.888 +
1.889 + template <typename K, typename V>
1.890 + inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
1.891 + return FunctorToMap<V (*)(K), K, V>(f);
1.892 + }
1.893 +
1.894 +
1.895 + /// Converts a map to an STL style (unary) functor
1.896 +
1.897 + /// This class converts a map to an STL style (unary) functor.
1.898 + /// That is it provides an <tt>operator()</tt> to read its values.
1.899 + ///
1.900 + /// For the sake of convenience it also works as a usual
1.901 + /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
1.902 + /// and the \c Key and \c Value typedefs also exist.
1.903 + ///
1.904 + /// The simplest way of using this map is through the mapToFunctor()
1.905 + /// function.
1.906 + ///
1.907 + ///\sa FunctorToMap
1.908 + template <typename M>
1.909 + class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
1.910 + const M &_m;
1.911 public:
1.912 typedef MapBase<typename M::Key, typename M::Value> Parent;
1.913 typedef typename Parent::Key Key;
1.914 typedef typename Parent::Value Value;
1.915
1.916 - ///Constructor
1.917 - SimpleMap(const M &_m) : m(_m) {};
1.918 - ///\e
1.919 - Value operator[](Key k) const {return m[k];}
1.920 + typedef typename Parent::Key argument_type;
1.921 + typedef typename Parent::Value result_type;
1.922 +
1.923 + /// Constructor
1.924 + MapToFunctor(const M &m) : _m(m) {}
1.925 + /// \e
1.926 + Value operator()(const Key &k) const { return _m[k]; }
1.927 + /// \e
1.928 + Value operator[](const Key &k) const { return _m[k]; }
1.929 };
1.930 -
1.931 - ///Returns a \c SimpleMap class
1.932
1.933 - ///This function just returns a \c SimpleMap class.
1.934 - ///\relates SimpleMap
1.935 + /// Returns a \ref MapToFunctor class
1.936 +
1.937 + /// This function just returns a \ref MapToFunctor class.
1.938 + /// \relates MapToFunctor
1.939 template<typename M>
1.940 - inline SimpleMap<M> simpleMap(const M &m) {
1.941 - return SimpleMap<M>(m);
1.942 + inline MapToFunctor<M> mapToFunctor(const M &m) {
1.943 + return MapToFunctor<M>(m);
1.944 }
1.945
1.946 - ///Simple writable wrapping of a map
1.947
1.948 - ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
1.949 - ///wrapping of the given map. Sometimes the reference maps cannot be
1.950 - ///combined with simple read-write maps. This map adaptor wraps the
1.951 - ///given map to simple read-write map.
1.952 + /// \brief Map adaptor to convert the \c Value type of a map to
1.953 + /// another type using the default conversion.
1.954 +
1.955 + /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
1.956 + /// "readable map" to another type using the default conversion.
1.957 + /// The \c Key type of it is inherited from \c M and the \c Value
1.958 + /// type is \c V.
1.959 + /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
1.960 ///
1.961 - ///\sa SimpleMap
1.962 + /// The simplest way of using this map is through the convertMap()
1.963 + /// function.
1.964 + template <typename M, typename V>
1.965 + class ConvertMap : public MapBase<typename M::Key, V> {
1.966 + const M &_m;
1.967 + public:
1.968 + typedef MapBase<typename M::Key, V> Parent;
1.969 + typedef typename Parent::Key Key;
1.970 + typedef typename Parent::Value Value;
1.971 +
1.972 + /// Constructor
1.973 +
1.974 + /// Constructor.
1.975 + /// \param m The underlying map.
1.976 + ConvertMap(const M &m) : _m(m) {}
1.977 +
1.978 + /// \e
1.979 + Value operator[](const Key &k) const { return _m[k]; }
1.980 + };
1.981 +
1.982 + /// Returns a \ref ConvertMap class
1.983 +
1.984 + /// This function just returns a \ref ConvertMap class.
1.985 + /// \relates ConvertMap
1.986 + template<typename V, typename M>
1.987 + inline ConvertMap<M, V> convertMap(const M &map) {
1.988 + return ConvertMap<M, V>(map);
1.989 + }
1.990 +
1.991 +
1.992 + /// Applies all map setting operations to two maps
1.993 +
1.994 + /// This map has two \ref concepts::WriteMap "writable map" parameters
1.995 + /// and each write request will be passed to both of them.
1.996 + /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
1.997 + /// operations will return the corresponding values of \c M1.
1.998 ///
1.999 - /// \todo Revise the misleading name
1.1000 - template<typename M>
1.1001 - class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.1002 - M& m;
1.1003 + /// The \c Key and \c Value types are inherited from \c M1.
1.1004 + /// The \c Key and \c Value of \c M2 must be convertible from those
1.1005 + /// of \c M1.
1.1006 + ///
1.1007 + /// The simplest way of using this map is through the forkMap()
1.1008 + /// function.
1.1009 + template<typename M1, typename M2>
1.1010 + class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1011 + M1 &_m1;
1.1012 + M2 &_m2;
1.1013 + public:
1.1014 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1015 + typedef typename Parent::Key Key;
1.1016 + typedef typename Parent::Value Value;
1.1017
1.1018 + /// Constructor
1.1019 + ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
1.1020 + /// Returns the value associated with the given key in the first map.
1.1021 + Value operator[](const Key &k) const { return _m1[k]; }
1.1022 + /// Sets the value associated with the given key in both maps.
1.1023 + void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
1.1024 + };
1.1025 +
1.1026 + /// Returns a \ref ForkMap class
1.1027 +
1.1028 + /// This function just returns a \ref ForkMap class.
1.1029 + /// \relates ForkMap
1.1030 + template <typename M1, typename M2>
1.1031 + inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
1.1032 + return ForkMap<M1,M2>(m1,m2);
1.1033 + }
1.1034 +
1.1035 +
1.1036 + /// Sum of two maps
1.1037 +
1.1038 + /// This \ref concepts::ReadMap "read-only map" returns the sum
1.1039 + /// of the values of the two given maps.
1.1040 + /// Its \c Key and \c Value types are inherited from \c M1.
1.1041 + /// The \c Key and \c Value of \c M2 must be convertible to those of
1.1042 + /// \c M1.
1.1043 + ///
1.1044 + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1.1045 + /// \code
1.1046 + /// AddMap<M1,M2> am(m1,m2);
1.1047 + /// \endcode
1.1048 + /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
1.1049 + ///
1.1050 + /// The simplest way of using this map is through the addMap()
1.1051 + /// function.
1.1052 + ///
1.1053 + /// \sa SubMap, MulMap, DivMap
1.1054 + /// \sa ShiftMap, ShiftWriteMap
1.1055 + template<typename M1, typename M2>
1.1056 + class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1057 + const M1 &_m1;
1.1058 + const M2 &_m2;
1.1059 + public:
1.1060 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1061 + typedef typename Parent::Key Key;
1.1062 + typedef typename Parent::Value Value;
1.1063 +
1.1064 + /// Constructor
1.1065 + AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.1066 + /// \e
1.1067 + Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
1.1068 + };
1.1069 +
1.1070 + /// Returns an \ref AddMap class
1.1071 +
1.1072 + /// This function just returns an \ref AddMap class.
1.1073 + ///
1.1074 + /// For example, if \c m1 and \c m2 are both maps with \c double
1.1075 + /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
1.1076 + /// <tt>m1[x]+m2[x]</tt>.
1.1077 + ///
1.1078 + /// \relates AddMap
1.1079 + template<typename M1, typename M2>
1.1080 + inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
1.1081 + return AddMap<M1, M2>(m1,m2);
1.1082 + }
1.1083 +
1.1084 +
1.1085 + /// Difference of two maps
1.1086 +
1.1087 + /// This \ref concepts::ReadMap "read-only map" returns the difference
1.1088 + /// of the values of the two given maps.
1.1089 + /// Its \c Key and \c Value types are inherited from \c M1.
1.1090 + /// The \c Key and \c Value of \c M2 must be convertible to those of
1.1091 + /// \c M1.
1.1092 + ///
1.1093 + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1.1094 + /// \code
1.1095 + /// SubMap<M1,M2> sm(m1,m2);
1.1096 + /// \endcode
1.1097 + /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
1.1098 + ///
1.1099 + /// The simplest way of using this map is through the subMap()
1.1100 + /// function.
1.1101 + ///
1.1102 + /// \sa AddMap, MulMap, DivMap
1.1103 + template<typename M1, typename M2>
1.1104 + class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1105 + const M1 &_m1;
1.1106 + const M2 &_m2;
1.1107 + public:
1.1108 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1109 + typedef typename Parent::Key Key;
1.1110 + typedef typename Parent::Value Value;
1.1111 +
1.1112 + /// Constructor
1.1113 + SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.1114 + /// \e
1.1115 + Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
1.1116 + };
1.1117 +
1.1118 + /// Returns a \ref SubMap class
1.1119 +
1.1120 + /// This function just returns a \ref SubMap class.
1.1121 + ///
1.1122 + /// For example, if \c m1 and \c m2 are both maps with \c double
1.1123 + /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
1.1124 + /// <tt>m1[x]-m2[x]</tt>.
1.1125 + ///
1.1126 + /// \relates SubMap
1.1127 + template<typename M1, typename M2>
1.1128 + inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
1.1129 + return SubMap<M1, M2>(m1,m2);
1.1130 + }
1.1131 +
1.1132 +
1.1133 + /// Product of two maps
1.1134 +
1.1135 + /// This \ref concepts::ReadMap "read-only map" returns the product
1.1136 + /// of the values of the two given maps.
1.1137 + /// Its \c Key and \c Value types are inherited from \c M1.
1.1138 + /// The \c Key and \c Value of \c M2 must be convertible to those of
1.1139 + /// \c M1.
1.1140 + ///
1.1141 + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1.1142 + /// \code
1.1143 + /// MulMap<M1,M2> mm(m1,m2);
1.1144 + /// \endcode
1.1145 + /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
1.1146 + ///
1.1147 + /// The simplest way of using this map is through the mulMap()
1.1148 + /// function.
1.1149 + ///
1.1150 + /// \sa AddMap, SubMap, DivMap
1.1151 + /// \sa ScaleMap, ScaleWriteMap
1.1152 + template<typename M1, typename M2>
1.1153 + class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1154 + const M1 &_m1;
1.1155 + const M2 &_m2;
1.1156 + public:
1.1157 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1158 + typedef typename Parent::Key Key;
1.1159 + typedef typename Parent::Value Value;
1.1160 +
1.1161 + /// Constructor
1.1162 + MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
1.1163 + /// \e
1.1164 + Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
1.1165 + };
1.1166 +
1.1167 + /// Returns a \ref MulMap class
1.1168 +
1.1169 + /// This function just returns a \ref MulMap class.
1.1170 + ///
1.1171 + /// For example, if \c m1 and \c m2 are both maps with \c double
1.1172 + /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
1.1173 + /// <tt>m1[x]*m2[x]</tt>.
1.1174 + ///
1.1175 + /// \relates MulMap
1.1176 + template<typename M1, typename M2>
1.1177 + inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
1.1178 + return MulMap<M1, M2>(m1,m2);
1.1179 + }
1.1180 +
1.1181 +
1.1182 + /// Quotient of two maps
1.1183 +
1.1184 + /// This \ref concepts::ReadMap "read-only map" returns the quotient
1.1185 + /// of the values of the two given maps.
1.1186 + /// Its \c Key and \c Value types are inherited from \c M1.
1.1187 + /// The \c Key and \c Value of \c M2 must be convertible to those of
1.1188 + /// \c M1.
1.1189 + ///
1.1190 + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1.1191 + /// \code
1.1192 + /// DivMap<M1,M2> dm(m1,m2);
1.1193 + /// \endcode
1.1194 + /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
1.1195 + ///
1.1196 + /// The simplest way of using this map is through the divMap()
1.1197 + /// function.
1.1198 + ///
1.1199 + /// \sa AddMap, SubMap, MulMap
1.1200 + template<typename M1, typename M2>
1.1201 + class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1202 + const M1 &_m1;
1.1203 + const M2 &_m2;
1.1204 + public:
1.1205 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1206 + typedef typename Parent::Key Key;
1.1207 + typedef typename Parent::Value Value;
1.1208 +
1.1209 + /// Constructor
1.1210 + DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
1.1211 + /// \e
1.1212 + Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
1.1213 + };
1.1214 +
1.1215 + /// Returns a \ref DivMap class
1.1216 +
1.1217 + /// This function just returns a \ref DivMap class.
1.1218 + ///
1.1219 + /// For example, if \c m1 and \c m2 are both maps with \c double
1.1220 + /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
1.1221 + /// <tt>m1[x]/m2[x]</tt>.
1.1222 + ///
1.1223 + /// \relates DivMap
1.1224 + template<typename M1, typename M2>
1.1225 + inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
1.1226 + return DivMap<M1, M2>(m1,m2);
1.1227 + }
1.1228 +
1.1229 +
1.1230 + /// Shifts a map with a constant.
1.1231 +
1.1232 + /// This \ref concepts::ReadMap "read-only map" returns the sum of
1.1233 + /// the given map and a constant value (i.e. it shifts the map with
1.1234 + /// the constant). Its \c Key and \c Value are inherited from \c M.
1.1235 + ///
1.1236 + /// Actually,
1.1237 + /// \code
1.1238 + /// ShiftMap<M> sh(m,v);
1.1239 + /// \endcode
1.1240 + /// is equivalent to
1.1241 + /// \code
1.1242 + /// ConstMap<M::Key, M::Value> cm(v);
1.1243 + /// AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
1.1244 + /// \endcode
1.1245 + ///
1.1246 + /// The simplest way of using this map is through the shiftMap()
1.1247 + /// function.
1.1248 + ///
1.1249 + /// \sa ShiftWriteMap
1.1250 + template<typename M, typename C = typename M::Value>
1.1251 + class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
1.1252 + const M &_m;
1.1253 + C _v;
1.1254 public:
1.1255 typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1256 typedef typename Parent::Key Key;
1.1257 typedef typename Parent::Value Value;
1.1258
1.1259 - ///Constructor
1.1260 - SimpleWriteMap(M &_m) : m(_m) {};
1.1261 - ///\e
1.1262 - Value operator[](Key k) const {return m[k];}
1.1263 - ///\e
1.1264 - void set(Key k, const Value& c) { m.set(k, c); }
1.1265 + /// Constructor
1.1266 +
1.1267 + /// Constructor.
1.1268 + /// \param m The undelying map.
1.1269 + /// \param v The constant value.
1.1270 + ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1.1271 + /// \e
1.1272 + Value operator[](const Key &k) const { return _m[k]+_v; }
1.1273 };
1.1274
1.1275 - ///Returns a \c SimpleWriteMap class
1.1276 + /// Shifts a map with a constant (read-write version).
1.1277
1.1278 - ///This function just returns a \c SimpleWriteMap class.
1.1279 - ///\relates SimpleWriteMap
1.1280 - template<typename M>
1.1281 - inline SimpleWriteMap<M> simpleWriteMap(M &m) {
1.1282 - return SimpleWriteMap<M>(m);
1.1283 - }
1.1284 -
1.1285 - ///Sum of two maps
1.1286 -
1.1287 - ///This \ref concepts::ReadMap "read only map" returns the sum of the two
1.1288 - ///given maps.
1.1289 - ///Its \c Key and \c Value are inherited from \c M1.
1.1290 - ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.1291 - template<typename M1, typename M2>
1.1292 - class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1293 - const M1& m1;
1.1294 - const M2& m2;
1.1295 -
1.1296 - public:
1.1297 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1298 - typedef typename Parent::Key Key;
1.1299 - typedef typename Parent::Value Value;
1.1300 -
1.1301 - ///Constructor
1.1302 - AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.1303 - ///\e
1.1304 - Value operator[](Key k) const {return m1[k]+m2[k];}
1.1305 - };
1.1306 -
1.1307 - ///Returns an \c AddMap class
1.1308 -
1.1309 - ///This function just returns an \c AddMap class.
1.1310 - ///\todo Extend the documentation: how to call these type of functions?
1.1311 + /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
1.1312 + /// of the given map and a constant value (i.e. it shifts the map with
1.1313 + /// the constant). Its \c Key and \c Value are inherited from \c M.
1.1314 + /// It makes also possible to write the map.
1.1315 ///
1.1316 - ///\relates AddMap
1.1317 - template<typename M1, typename M2>
1.1318 - inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
1.1319 - return AddMap<M1, M2>(m1,m2);
1.1320 - }
1.1321 -
1.1322 - ///Shift a map with a constant.
1.1323 -
1.1324 - ///This \ref concepts::ReadMap "read only map" returns the sum of the
1.1325 - ///given map and a constant value.
1.1326 - ///Its \c Key and \c Value are inherited from \c M.
1.1327 + /// The simplest way of using this map is through the shiftWriteMap()
1.1328 + /// function.
1.1329 ///
1.1330 - ///Actually,
1.1331 - ///\code
1.1332 - /// ShiftMap<X> sh(x,v);
1.1333 - ///\endcode
1.1334 - ///is equivalent to
1.1335 - ///\code
1.1336 - /// ConstMap<X::Key, X::Value> c_tmp(v);
1.1337 - /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
1.1338 - ///\endcode
1.1339 - ///
1.1340 - ///\sa ShiftWriteMap
1.1341 - template<typename M, typename C = typename M::Value>
1.1342 - class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
1.1343 - const M& m;
1.1344 - C v;
1.1345 + /// \sa ShiftMap
1.1346 + template<typename M, typename C = typename M::Value>
1.1347 + class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.1348 + M &_m;
1.1349 + C _v;
1.1350 public:
1.1351 typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1352 typedef typename Parent::Key Key;
1.1353 typedef typename Parent::Value Value;
1.1354
1.1355 - ///Constructor
1.1356 + /// Constructor
1.1357
1.1358 - ///Constructor.
1.1359 - ///\param _m is the undelying map.
1.1360 - ///\param _v is the shift value.
1.1361 - ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
1.1362 - ///\e
1.1363 - Value operator[](Key k) const {return m[k] + v;}
1.1364 + /// Constructor.
1.1365 + /// \param m The undelying map.
1.1366 + /// \param v The constant value.
1.1367 + ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1.1368 + /// \e
1.1369 + Value operator[](const Key &k) const { return _m[k]+_v; }
1.1370 + /// \e
1.1371 + void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
1.1372 };
1.1373
1.1374 - ///Shift a map with a constant (ReadWrite version).
1.1375 + /// Returns a \ref ShiftMap class
1.1376
1.1377 - ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
1.1378 - ///given map and a constant value. It makes also possible to write the map.
1.1379 - ///Its \c Key and \c Value are inherited from \c M.
1.1380 + /// This function just returns a \ref ShiftMap class.
1.1381 ///
1.1382 - ///\sa ShiftMap
1.1383 - template<typename M, typename C = typename M::Value>
1.1384 - class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.1385 - M& m;
1.1386 - C v;
1.1387 + /// For example, if \c m is a map with \c double values and \c v is
1.1388 + /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
1.1389 + /// <tt>m[x]+v</tt>.
1.1390 + ///
1.1391 + /// \relates ShiftMap
1.1392 + template<typename M, typename C>
1.1393 + inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
1.1394 + return ShiftMap<M, C>(m,v);
1.1395 + }
1.1396 +
1.1397 + /// Returns a \ref ShiftWriteMap class
1.1398 +
1.1399 + /// This function just returns a \ref ShiftWriteMap class.
1.1400 + ///
1.1401 + /// For example, if \c m is a map with \c double values and \c v is
1.1402 + /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
1.1403 + /// <tt>m[x]+v</tt>.
1.1404 + /// Moreover it makes also possible to write the map.
1.1405 + ///
1.1406 + /// \relates ShiftWriteMap
1.1407 + template<typename M, typename C>
1.1408 + inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
1.1409 + return ShiftWriteMap<M, C>(m,v);
1.1410 + }
1.1411 +
1.1412 +
1.1413 + /// Scales a map with a constant.
1.1414 +
1.1415 + /// This \ref concepts::ReadMap "read-only map" returns the value of
1.1416 + /// the given map multiplied from the left side with a constant value.
1.1417 + /// Its \c Key and \c Value are inherited from \c M.
1.1418 + ///
1.1419 + /// Actually,
1.1420 + /// \code
1.1421 + /// ScaleMap<M> sc(m,v);
1.1422 + /// \endcode
1.1423 + /// is equivalent to
1.1424 + /// \code
1.1425 + /// ConstMap<M::Key, M::Value> cm(v);
1.1426 + /// MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
1.1427 + /// \endcode
1.1428 + ///
1.1429 + /// The simplest way of using this map is through the scaleMap()
1.1430 + /// function.
1.1431 + ///
1.1432 + /// \sa ScaleWriteMap
1.1433 + template<typename M, typename C = typename M::Value>
1.1434 + class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1.1435 + const M &_m;
1.1436 + C _v;
1.1437 public:
1.1438 typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1439 typedef typename Parent::Key Key;
1.1440 typedef typename Parent::Value Value;
1.1441
1.1442 - ///Constructor
1.1443 + /// Constructor
1.1444
1.1445 - ///Constructor.
1.1446 - ///\param _m is the undelying map.
1.1447 - ///\param _v is the shift value.
1.1448 - ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
1.1449 + /// Constructor.
1.1450 + /// \param m The undelying map.
1.1451 + /// \param v The constant value.
1.1452 + ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
1.1453 /// \e
1.1454 - Value operator[](Key k) const {return m[k] + v;}
1.1455 - /// \e
1.1456 - void set(Key k, const Value& c) { m.set(k, c - v); }
1.1457 + Value operator[](const Key &k) const { return _v*_m[k]; }
1.1458 };
1.1459 -
1.1460 - ///Returns a \c ShiftMap class
1.1461
1.1462 - ///This function just returns a \c ShiftMap class.
1.1463 - ///\relates ShiftMap
1.1464 - template<typename M, typename C>
1.1465 - inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
1.1466 - return ShiftMap<M, C>(m,v);
1.1467 - }
1.1468 + /// Scales a map with a constant (read-write version).
1.1469
1.1470 - ///Returns a \c ShiftWriteMap class
1.1471 -
1.1472 - ///This function just returns a \c ShiftWriteMap class.
1.1473 - ///\relates ShiftWriteMap
1.1474 - template<typename M, typename C>
1.1475 - inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
1.1476 - return ShiftWriteMap<M, C>(m,v);
1.1477 - }
1.1478 -
1.1479 - ///Difference of two maps
1.1480 -
1.1481 - ///This \ref concepts::ReadMap "read only map" returns the difference
1.1482 - ///of the values of the two given maps.
1.1483 - ///Its \c Key and \c Value are inherited from \c M1.
1.1484 - ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.1485 + /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
1.1486 + /// the given map multiplied from the left side with a constant value.
1.1487 + /// Its \c Key and \c Value are inherited from \c M.
1.1488 + /// It can also be used as write map if the \c / operator is defined
1.1489 + /// between \c Value and \c C and the given multiplier is not zero.
1.1490 ///
1.1491 - /// \todo Revise the misleading name
1.1492 - template<typename M1, typename M2>
1.1493 - class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1494 - const M1& m1;
1.1495 - const M2& m2;
1.1496 - public:
1.1497 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1498 - typedef typename Parent::Key Key;
1.1499 - typedef typename Parent::Value Value;
1.1500 -
1.1501 - ///Constructor
1.1502 - SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.1503 - /// \e
1.1504 - Value operator[](Key k) const {return m1[k]-m2[k];}
1.1505 - };
1.1506 -
1.1507 - ///Returns a \c SubMap class
1.1508 -
1.1509 - ///This function just returns a \c SubMap class.
1.1510 + /// The simplest way of using this map is through the scaleWriteMap()
1.1511 + /// function.
1.1512 ///
1.1513 - ///\relates SubMap
1.1514 - template<typename M1, typename M2>
1.1515 - inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
1.1516 - return SubMap<M1, M2>(m1, m2);
1.1517 - }
1.1518 -
1.1519 - ///Product of two maps
1.1520 -
1.1521 - ///This \ref concepts::ReadMap "read only map" returns the product of the
1.1522 - ///values of the two given maps.
1.1523 - ///Its \c Key and \c Value are inherited from \c M1.
1.1524 - ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.1525 - template<typename M1, typename M2>
1.1526 - class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1527 - const M1& m1;
1.1528 - const M2& m2;
1.1529 - public:
1.1530 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1531 - typedef typename Parent::Key Key;
1.1532 - typedef typename Parent::Value Value;
1.1533 -
1.1534 - ///Constructor
1.1535 - MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.1536 - /// \e
1.1537 - Value operator[](Key k) const {return m1[k]*m2[k];}
1.1538 - };
1.1539 -
1.1540 - ///Returns a \c MulMap class
1.1541 -
1.1542 - ///This function just returns a \c MulMap class.
1.1543 - ///\relates MulMap
1.1544 - template<typename M1, typename M2>
1.1545 - inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
1.1546 - return MulMap<M1, M2>(m1,m2);
1.1547 - }
1.1548 -
1.1549 - ///Scales a map with a constant.
1.1550 -
1.1551 - ///This \ref concepts::ReadMap "read only map" returns the value of the
1.1552 - ///given map multiplied from the left side with a constant value.
1.1553 - ///Its \c Key and \c Value are inherited from \c M.
1.1554 - ///
1.1555 - ///Actually,
1.1556 - ///\code
1.1557 - /// ScaleMap<X> sc(x,v);
1.1558 - ///\endcode
1.1559 - ///is equivalent to
1.1560 - ///\code
1.1561 - /// ConstMap<X::Key, X::Value> c_tmp(v);
1.1562 - /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
1.1563 - ///\endcode
1.1564 - ///
1.1565 - ///\sa ScaleWriteMap
1.1566 - template<typename M, typename C = typename M::Value>
1.1567 - class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1.1568 - const M& m;
1.1569 - C v;
1.1570 + /// \sa ScaleMap
1.1571 + template<typename M, typename C = typename M::Value>
1.1572 + class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.1573 + M &_m;
1.1574 + C _v;
1.1575 public:
1.1576 typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1577 typedef typename Parent::Key Key;
1.1578 typedef typename Parent::Value Value;
1.1579
1.1580 - ///Constructor
1.1581 + /// Constructor
1.1582
1.1583 - ///Constructor.
1.1584 - ///\param _m is the undelying map.
1.1585 - ///\param _v is the scaling value.
1.1586 - ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
1.1587 + /// Constructor.
1.1588 + /// \param m The undelying map.
1.1589 + /// \param v The constant value.
1.1590 + ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1.1591 /// \e
1.1592 - Value operator[](Key k) const {return v * m[k];}
1.1593 + Value operator[](const Key &k) const { return _v*_m[k]; }
1.1594 + /// \e
1.1595 + void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
1.1596 };
1.1597
1.1598 - ///Scales a map with a constant (ReadWrite version).
1.1599 + /// Returns a \ref ScaleMap class
1.1600
1.1601 - ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
1.1602 - ///given map multiplied from the left side with a constant value. It can
1.1603 - ///also be used as write map if the \c / operator is defined between
1.1604 - ///\c Value and \c C and the given multiplier is not zero.
1.1605 - ///Its \c Key and \c Value are inherited from \c M.
1.1606 + /// This function just returns a \ref ScaleMap class.
1.1607 ///
1.1608 - ///\sa ScaleMap
1.1609 - template<typename M, typename C = typename M::Value>
1.1610 - class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.1611 - M& m;
1.1612 - C v;
1.1613 + /// For example, if \c m is a map with \c double values and \c v is
1.1614 + /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
1.1615 + /// <tt>v*m[x]</tt>.
1.1616 + ///
1.1617 + /// \relates ScaleMap
1.1618 + template<typename M, typename C>
1.1619 + inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
1.1620 + return ScaleMap<M, C>(m,v);
1.1621 + }
1.1622 +
1.1623 + /// Returns a \ref ScaleWriteMap class
1.1624 +
1.1625 + /// This function just returns a \ref ScaleWriteMap class.
1.1626 + ///
1.1627 + /// For example, if \c m is a map with \c double values and \c v is
1.1628 + /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
1.1629 + /// <tt>v*m[x]</tt>.
1.1630 + /// Moreover it makes also possible to write the map.
1.1631 + ///
1.1632 + /// \relates ScaleWriteMap
1.1633 + template<typename M, typename C>
1.1634 + inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
1.1635 + return ScaleWriteMap<M, C>(m,v);
1.1636 + }
1.1637 +
1.1638 +
1.1639 + /// Negative of a map
1.1640 +
1.1641 + /// This \ref concepts::ReadMap "read-only map" returns the negative
1.1642 + /// of the values of the given map (using the unary \c - operator).
1.1643 + /// Its \c Key and \c Value are inherited from \c M.
1.1644 + ///
1.1645 + /// If M::Value is \c int, \c double etc., then
1.1646 + /// \code
1.1647 + /// NegMap<M> neg(m);
1.1648 + /// \endcode
1.1649 + /// is equivalent to
1.1650 + /// \code
1.1651 + /// ScaleMap<M> neg(m,-1);
1.1652 + /// \endcode
1.1653 + ///
1.1654 + /// The simplest way of using this map is through the negMap()
1.1655 + /// function.
1.1656 + ///
1.1657 + /// \sa NegWriteMap
1.1658 + template<typename M>
1.1659 + class NegMap : public MapBase<typename M::Key, typename M::Value> {
1.1660 + const M& _m;
1.1661 public:
1.1662 typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1663 typedef typename Parent::Key Key;
1.1664 typedef typename Parent::Value Value;
1.1665
1.1666 - ///Constructor
1.1667 -
1.1668 - ///Constructor.
1.1669 - ///\param _m is the undelying map.
1.1670 - ///\param _v is the scaling value.
1.1671 - ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
1.1672 + /// Constructor
1.1673 + NegMap(const M &m) : _m(m) {}
1.1674 /// \e
1.1675 - Value operator[](Key k) const {return v * m[k];}
1.1676 - /// \e
1.1677 - void set(Key k, const Value& c) { m.set(k, c / v);}
1.1678 - };
1.1679 -
1.1680 - ///Returns a \c ScaleMap class
1.1681 -
1.1682 - ///This function just returns a \c ScaleMap class.
1.1683 - ///\relates ScaleMap
1.1684 - template<typename M, typename C>
1.1685 - inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
1.1686 - return ScaleMap<M, C>(m,v);
1.1687 - }
1.1688 -
1.1689 - ///Returns a \c ScaleWriteMap class
1.1690 -
1.1691 - ///This function just returns a \c ScaleWriteMap class.
1.1692 - ///\relates ScaleWriteMap
1.1693 - template<typename M, typename C>
1.1694 - inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
1.1695 - return ScaleWriteMap<M, C>(m,v);
1.1696 - }
1.1697 -
1.1698 - ///Quotient of two maps
1.1699 -
1.1700 - ///This \ref concepts::ReadMap "read only map" returns the quotient of the
1.1701 - ///values of the two given maps.
1.1702 - ///Its \c Key and \c Value are inherited from \c M1.
1.1703 - ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.1704 - template<typename M1, typename M2>
1.1705 - class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1706 - const M1& m1;
1.1707 - const M2& m2;
1.1708 - public:
1.1709 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1710 - typedef typename Parent::Key Key;
1.1711 - typedef typename Parent::Value Value;
1.1712 -
1.1713 - ///Constructor
1.1714 - DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.1715 - /// \e
1.1716 - Value operator[](Key k) const {return m1[k]/m2[k];}
1.1717 - };
1.1718 -
1.1719 - ///Returns a \c DivMap class
1.1720 -
1.1721 - ///This function just returns a \c DivMap class.
1.1722 - ///\relates DivMap
1.1723 - template<typename M1, typename M2>
1.1724 - inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
1.1725 - return DivMap<M1, M2>(m1,m2);
1.1726 - }
1.1727 -
1.1728 - ///Composition of two maps
1.1729 -
1.1730 - ///This \ref concepts::ReadMap "read only map" returns the composition of
1.1731 - ///two given maps.
1.1732 - ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
1.1733 - ///then for
1.1734 - ///\code
1.1735 - /// ComposeMap<M1, M2> cm(m1,m2);
1.1736 - ///\endcode
1.1737 - /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
1.1738 - ///
1.1739 - ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
1.1740 - ///\c M2::Value must be convertible to \c M1::Key.
1.1741 - ///
1.1742 - ///\sa CombineMap
1.1743 - ///
1.1744 - ///\todo Check the requirements.
1.1745 - template <typename M1, typename M2>
1.1746 - class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
1.1747 - const M1& m1;
1.1748 - const M2& m2;
1.1749 - public:
1.1750 - typedef MapBase<typename M2::Key, typename M1::Value> Parent;
1.1751 - typedef typename Parent::Key Key;
1.1752 - typedef typename Parent::Value Value;
1.1753 -
1.1754 - ///Constructor
1.1755 - ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.1756 -
1.1757 - /// \e
1.1758 -
1.1759 -
1.1760 - /// \todo Use the MapTraits once it is ported.
1.1761 - ///
1.1762 -
1.1763 - //typename MapTraits<M1>::ConstReturnValue
1.1764 - typename M1::Value
1.1765 - operator[](Key k) const {return m1[m2[k]];}
1.1766 + Value operator[](const Key &k) const { return -_m[k]; }
1.1767 };
1.1768
1.1769 - ///Returns a \c ComposeMap class
1.1770 + /// Negative of a map (read-write version)
1.1771
1.1772 - ///This function just returns a \c ComposeMap class.
1.1773 - ///\relates ComposeMap
1.1774 - template <typename M1, typename M2>
1.1775 - inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
1.1776 - return ComposeMap<M1, M2>(m1,m2);
1.1777 - }
1.1778 -
1.1779 - ///Combine of two maps using an STL (binary) functor.
1.1780 -
1.1781 - ///Combine of two maps using an STL (binary) functor.
1.1782 + /// This \ref concepts::ReadWriteMap "read-write map" returns the
1.1783 + /// negative of the values of the given map (using the unary \c -
1.1784 + /// operator).
1.1785 + /// Its \c Key and \c Value are inherited from \c M.
1.1786 + /// It makes also possible to write the map.
1.1787 ///
1.1788 - ///This \ref concepts::ReadMap "read only map" takes two maps and a
1.1789 - ///binary functor and returns the composition of the two
1.1790 - ///given maps unsing the functor.
1.1791 - ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
1.1792 - ///and \c f is of \c F, then for
1.1793 - ///\code
1.1794 - /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
1.1795 - ///\endcode
1.1796 - /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
1.1797 + /// If M::Value is \c int, \c double etc., then
1.1798 + /// \code
1.1799 + /// NegWriteMap<M> neg(m);
1.1800 + /// \endcode
1.1801 + /// is equivalent to
1.1802 + /// \code
1.1803 + /// ScaleWriteMap<M> neg(m,-1);
1.1804 + /// \endcode
1.1805 ///
1.1806 - ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
1.1807 - ///\c M2::Value and \c M1::Value must be convertible to the corresponding
1.1808 - ///input parameter of \c F and the return type of \c F must be convertible
1.1809 - ///to \c V.
1.1810 + /// The simplest way of using this map is through the negWriteMap()
1.1811 + /// function.
1.1812 ///
1.1813 - ///\sa ComposeMap
1.1814 - ///
1.1815 - ///\todo Check the requirements.
1.1816 - template<typename M1, typename M2, typename F,
1.1817 - typename V = typename F::result_type>
1.1818 - class CombineMap : public MapBase<typename M1::Key, V> {
1.1819 - const M1& m1;
1.1820 - const M2& m2;
1.1821 - F f;
1.1822 - public:
1.1823 - typedef MapBase<typename M1::Key, V> Parent;
1.1824 - typedef typename Parent::Key Key;
1.1825 - typedef typename Parent::Value Value;
1.1826 -
1.1827 - ///Constructor
1.1828 - CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
1.1829 - : m1(_m1), m2(_m2), f(_f) {};
1.1830 - /// \e
1.1831 - Value operator[](Key k) const {return f(m1[k],m2[k]);}
1.1832 - };
1.1833 -
1.1834 - ///Returns a \c CombineMap class
1.1835 -
1.1836 - ///This function just returns a \c CombineMap class.
1.1837 - ///
1.1838 - ///For example if \c m1 and \c m2 are both \c double valued maps, then
1.1839 - ///\code
1.1840 - ///combineMap(m1,m2,std::plus<double>())
1.1841 - ///\endcode
1.1842 - ///is equivalent to
1.1843 - ///\code
1.1844 - ///addMap(m1,m2)
1.1845 - ///\endcode
1.1846 - ///
1.1847 - ///This function is specialized for adaptable binary function
1.1848 - ///classes and C++ functions.
1.1849 - ///
1.1850 - ///\relates CombineMap
1.1851 - template<typename M1, typename M2, typename F, typename V>
1.1852 - inline CombineMap<M1, M2, F, V>
1.1853 - combineMap(const M1& m1,const M2& m2, const F& f) {
1.1854 - return CombineMap<M1, M2, F, V>(m1,m2,f);
1.1855 - }
1.1856 -
1.1857 - template<typename M1, typename M2, typename F>
1.1858 - inline CombineMap<M1, M2, F, typename F::result_type>
1.1859 - combineMap(const M1& m1, const M2& m2, const F& f) {
1.1860 - return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
1.1861 - }
1.1862 -
1.1863 - template<typename M1, typename M2, typename K1, typename K2, typename V>
1.1864 - inline CombineMap<M1, M2, V (*)(K1, K2), V>
1.1865 - combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
1.1866 - return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
1.1867 - }
1.1868 -
1.1869 - ///Negative value of a map
1.1870 -
1.1871 - ///This \ref concepts::ReadMap "read only map" returns the negative
1.1872 - ///value of the value returned by the given map.
1.1873 - ///Its \c Key and \c Value are inherited from \c M.
1.1874 - ///The unary \c - operator must be defined for \c Value, of course.
1.1875 - ///
1.1876 - ///\sa NegWriteMap
1.1877 - template<typename M>
1.1878 - class NegMap : public MapBase<typename M::Key, typename M::Value> {
1.1879 - const M& m;
1.1880 + /// \sa NegMap
1.1881 + template<typename M>
1.1882 + class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.1883 + M &_m;
1.1884 public:
1.1885 typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1886 typedef typename Parent::Key Key;
1.1887 typedef typename Parent::Value Value;
1.1888
1.1889 - ///Constructor
1.1890 - NegMap(const M &_m) : m(_m) {};
1.1891 + /// Constructor
1.1892 + NegWriteMap(M &m) : _m(m) {}
1.1893 /// \e
1.1894 - Value operator[](Key k) const {return -m[k];}
1.1895 + Value operator[](const Key &k) const { return -_m[k]; }
1.1896 + /// \e
1.1897 + void set(const Key &k, const Value &v) { _m.set(k, -v); }
1.1898 };
1.1899 -
1.1900 - ///Negative value of a map (ReadWrite version)
1.1901
1.1902 - ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
1.1903 - ///value of the value returned by the given map.
1.1904 - ///Its \c Key and \c Value are inherited from \c M.
1.1905 - ///The unary \c - operator must be defined for \c Value, of course.
1.1906 + /// Returns a \ref NegMap class
1.1907 +
1.1908 + /// This function just returns a \ref NegMap class.
1.1909 ///
1.1910 - /// \sa NegMap
1.1911 - template<typename M>
1.1912 - class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.1913 - M& m;
1.1914 + /// For example, if \c m is a map with \c double values, then
1.1915 + /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1.1916 + ///
1.1917 + /// \relates NegMap
1.1918 + template <typename M>
1.1919 + inline NegMap<M> negMap(const M &m) {
1.1920 + return NegMap<M>(m);
1.1921 + }
1.1922 +
1.1923 + /// Returns a \ref NegWriteMap class
1.1924 +
1.1925 + /// This function just returns a \ref NegWriteMap class.
1.1926 + ///
1.1927 + /// For example, if \c m is a map with \c double values, then
1.1928 + /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1.1929 + /// Moreover it makes also possible to write the map.
1.1930 + ///
1.1931 + /// \relates NegWriteMap
1.1932 + template <typename M>
1.1933 + inline NegWriteMap<M> negWriteMap(M &m) {
1.1934 + return NegWriteMap<M>(m);
1.1935 + }
1.1936 +
1.1937 +
1.1938 + /// Absolute value of a map
1.1939 +
1.1940 + /// This \ref concepts::ReadMap "read-only map" returns the absolute
1.1941 + /// value of the values of the given map.
1.1942 + /// Its \c Key and \c Value are inherited from \c M.
1.1943 + /// \c Value must be comparable to \c 0 and the unary \c -
1.1944 + /// operator must be defined for it, of course.
1.1945 + ///
1.1946 + /// The simplest way of using this map is through the absMap()
1.1947 + /// function.
1.1948 + template<typename M>
1.1949 + class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1.1950 + const M &_m;
1.1951 public:
1.1952 typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1953 typedef typename Parent::Key Key;
1.1954 typedef typename Parent::Value Value;
1.1955
1.1956 - ///Constructor
1.1957 - NegWriteMap(M &_m) : m(_m) {};
1.1958 + /// Constructor
1.1959 + AbsMap(const M &m) : _m(m) {}
1.1960 /// \e
1.1961 - Value operator[](Key k) const {return -m[k];}
1.1962 - /// \e
1.1963 - void set(Key k, const Value& v) { m.set(k, -v); }
1.1964 - };
1.1965 -
1.1966 - ///Returns a \c NegMap class
1.1967 -
1.1968 - ///This function just returns a \c NegMap class.
1.1969 - ///\relates NegMap
1.1970 - template <typename M>
1.1971 - inline NegMap<M> negMap(const M &m) {
1.1972 - return NegMap<M>(m);
1.1973 - }
1.1974 -
1.1975 - ///Returns a \c NegWriteMap class
1.1976 -
1.1977 - ///This function just returns a \c NegWriteMap class.
1.1978 - ///\relates NegWriteMap
1.1979 - template <typename M>
1.1980 - inline NegWriteMap<M> negMap(M &m) {
1.1981 - return NegWriteMap<M>(m);
1.1982 - }
1.1983 -
1.1984 - ///Absolute value of a map
1.1985 -
1.1986 - ///This \ref concepts::ReadMap "read only map" returns the absolute value
1.1987 - ///of the value returned by the given map.
1.1988 - ///Its \c Key and \c Value are inherited from \c M.
1.1989 - ///\c Value must be comparable to \c 0 and the unary \c -
1.1990 - ///operator must be defined for it, of course.
1.1991 - template<typename M>
1.1992 - class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1.1993 - const M& m;
1.1994 - public:
1.1995 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1996 - typedef typename Parent::Key Key;
1.1997 - typedef typename Parent::Value Value;
1.1998 -
1.1999 - ///Constructor
1.2000 - AbsMap(const M &_m) : m(_m) {};
1.2001 - /// \e
1.2002 - Value operator[](Key k) const {
1.2003 - Value tmp = m[k];
1.2004 + Value operator[](const Key &k) const {
1.2005 + Value tmp = _m[k];
1.2006 return tmp >= 0 ? tmp : -tmp;
1.2007 }
1.2008
1.2009 };
1.2010 -
1.2011 - ///Returns an \c AbsMap class
1.2012
1.2013 - ///This function just returns an \c AbsMap class.
1.2014 - ///\relates AbsMap
1.2015 - template<typename M>
1.2016 + /// Returns an \ref AbsMap class
1.2017 +
1.2018 + /// This function just returns an \ref AbsMap class.
1.2019 + ///
1.2020 + /// For example, if \c m is a map with \c double values, then
1.2021 + /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
1.2022 + /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
1.2023 + /// negative.
1.2024 + ///
1.2025 + /// \relates AbsMap
1.2026 + template<typename M>
1.2027 inline AbsMap<M> absMap(const M &m) {
1.2028 return AbsMap<M>(m);
1.2029 }
1.2030
1.2031 - ///Converts an STL style functor to a map
1.2032 + /// @}
1.2033 +
1.2034 + // Logical maps and map adaptors:
1.2035
1.2036 - ///This \ref concepts::ReadMap "read only map" returns the value
1.2037 - ///of a given functor.
1.2038 + /// \addtogroup maps
1.2039 + /// @{
1.2040 +
1.2041 + /// Constant \c true map.
1.2042 +
1.2043 + /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1.2044 + /// each key.
1.2045 ///
1.2046 - ///Template parameters \c K and \c V will become its
1.2047 - ///\c Key and \c Value.
1.2048 - ///In most cases they have to be given explicitly because a
1.2049 - ///functor typically does not provide \c argument_type and
1.2050 - ///\c result_type typedefs.
1.2051 + /// Note that
1.2052 + /// \code
1.2053 + /// TrueMap<K> tm;
1.2054 + /// \endcode
1.2055 + /// is equivalent to
1.2056 + /// \code
1.2057 + /// ConstMap<K,bool> tm(true);
1.2058 + /// \endcode
1.2059 ///
1.2060 - ///Parameter \c F is the type of the used functor.
1.2061 - ///
1.2062 - ///\sa MapFunctor
1.2063 - template<typename F,
1.2064 - typename K = typename F::argument_type,
1.2065 - typename V = typename F::result_type>
1.2066 - class FunctorMap : public MapBase<K, V> {
1.2067 - F f;
1.2068 + /// \sa FalseMap
1.2069 + /// \sa ConstMap
1.2070 + template <typename K>
1.2071 + class TrueMap : public MapBase<K, bool> {
1.2072 public:
1.2073 - typedef MapBase<K, V> Parent;
1.2074 + typedef MapBase<K, bool> Parent;
1.2075 typedef typename Parent::Key Key;
1.2076 typedef typename Parent::Value Value;
1.2077
1.2078 - ///Constructor
1.2079 - FunctorMap(const F &_f = F()) : f(_f) {}
1.2080 - /// \e
1.2081 - Value operator[](Key k) const { return f(k);}
1.2082 + /// Gives back \c true.
1.2083 + Value operator[](const Key&) const { return true; }
1.2084 };
1.2085 -
1.2086 - ///Returns a \c FunctorMap class
1.2087
1.2088 - ///This function just returns a \c FunctorMap class.
1.2089 - ///
1.2090 - ///This function is specialized for adaptable binary function
1.2091 - ///classes and C++ functions.
1.2092 - ///
1.2093 - ///\relates FunctorMap
1.2094 - template<typename K, typename V, typename F> inline
1.2095 - FunctorMap<F, K, V> functorMap(const F &f) {
1.2096 - return FunctorMap<F, K, V>(f);
1.2097 + /// Returns a \ref TrueMap class
1.2098 +
1.2099 + /// This function just returns a \ref TrueMap class.
1.2100 + /// \relates TrueMap
1.2101 + template<typename K>
1.2102 + inline TrueMap<K> trueMap() {
1.2103 + return TrueMap<K>();
1.2104 }
1.2105
1.2106 - template <typename F> inline
1.2107 - FunctorMap<F, typename F::argument_type, typename F::result_type>
1.2108 - functorMap(const F &f) {
1.2109 - return FunctorMap<F, typename F::argument_type,
1.2110 - typename F::result_type>(f);
1.2111 - }
1.2112
1.2113 - template <typename K, typename V> inline
1.2114 - FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
1.2115 - return FunctorMap<V (*)(K), K, V>(f);
1.2116 - }
1.2117 + /// Constant \c false map.
1.2118
1.2119 -
1.2120 - ///Converts a map to an STL style (unary) functor
1.2121 -
1.2122 - ///This class Converts a map to an STL style (unary) functor.
1.2123 - ///That is it provides an <tt>operator()</tt> to read its values.
1.2124 + /// This \ref concepts::ReadMap "read-only map" assigns \c false to
1.2125 + /// each key.
1.2126 ///
1.2127 - ///For the sake of convenience it also works as
1.2128 - ///a ususal \ref concepts::ReadMap "readable map",
1.2129 - ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1.2130 + /// Note that
1.2131 + /// \code
1.2132 + /// FalseMap<K> fm;
1.2133 + /// \endcode
1.2134 + /// is equivalent to
1.2135 + /// \code
1.2136 + /// ConstMap<K,bool> fm(false);
1.2137 + /// \endcode
1.2138 ///
1.2139 - ///\sa FunctorMap
1.2140 - template <typename M>
1.2141 - class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1.2142 - const M& m;
1.2143 + /// \sa TrueMap
1.2144 + /// \sa ConstMap
1.2145 + template <typename K>
1.2146 + class FalseMap : public MapBase<K, bool> {
1.2147 public:
1.2148 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.2149 + typedef MapBase<K, bool> Parent;
1.2150 typedef typename Parent::Key Key;
1.2151 typedef typename Parent::Value Value;
1.2152
1.2153 - typedef typename M::Key argument_type;
1.2154 - typedef typename M::Value result_type;
1.2155 + /// Gives back \c false.
1.2156 + Value operator[](const Key&) const { return false; }
1.2157 + };
1.2158
1.2159 - ///Constructor
1.2160 - MapFunctor(const M &_m) : m(_m) {};
1.2161 - ///\e
1.2162 - Value operator()(Key k) const {return m[k];}
1.2163 - ///\e
1.2164 - Value operator[](Key k) const {return m[k];}
1.2165 - };
1.2166 -
1.2167 - ///Returns a \c MapFunctor class
1.2168 + /// Returns a \ref FalseMap class
1.2169
1.2170 - ///This function just returns a \c MapFunctor class.
1.2171 - ///\relates MapFunctor
1.2172 - template<typename M>
1.2173 - inline MapFunctor<M> mapFunctor(const M &m) {
1.2174 - return MapFunctor<M>(m);
1.2175 + /// This function just returns a \ref FalseMap class.
1.2176 + /// \relates FalseMap
1.2177 + template<typename K>
1.2178 + inline FalseMap<K> falseMap() {
1.2179 + return FalseMap<K>();
1.2180 }
1.2181
1.2182 - ///Just readable version of \ref ForkWriteMap
1.2183 + /// @}
1.2184
1.2185 - ///This map has two \ref concepts::ReadMap "readable map"
1.2186 - ///parameters and each read request will be passed just to the
1.2187 - ///first map. This class is the just readable map type of \c ForkWriteMap.
1.2188 + /// \addtogroup map_adaptors
1.2189 + /// @{
1.2190 +
1.2191 + /// Logical 'and' of two maps
1.2192 +
1.2193 + /// This \ref concepts::ReadMap "read-only map" returns the logical
1.2194 + /// 'and' of the values of the two given maps.
1.2195 + /// Its \c Key type is inherited from \c M1 and its \c Value type is
1.2196 + /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1.2197 ///
1.2198 - ///The \c Key and \c Value are inherited from \c M1.
1.2199 - ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1.2200 + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1.2201 + /// \code
1.2202 + /// AndMap<M1,M2> am(m1,m2);
1.2203 + /// \endcode
1.2204 + /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
1.2205 ///
1.2206 - ///\sa ForkWriteMap
1.2207 + /// The simplest way of using this map is through the andMap()
1.2208 + /// function.
1.2209 ///
1.2210 - /// \todo Why is it needed?
1.2211 - template<typename M1, typename M2>
1.2212 - class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1.2213 - const M1& m1;
1.2214 - const M2& m2;
1.2215 + /// \sa OrMap
1.2216 + /// \sa NotMap, NotWriteMap
1.2217 + template<typename M1, typename M2>
1.2218 + class AndMap : public MapBase<typename M1::Key, bool> {
1.2219 + const M1 &_m1;
1.2220 + const M2 &_m2;
1.2221 public:
1.2222 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.2223 + typedef MapBase<typename M1::Key, bool> Parent;
1.2224 typedef typename Parent::Key Key;
1.2225 typedef typename Parent::Value Value;
1.2226
1.2227 - ///Constructor
1.2228 - ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1.2229 + /// Constructor
1.2230 + AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.2231 /// \e
1.2232 - Value operator[](Key k) const {return m1[k];}
1.2233 + Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1.2234 };
1.2235
1.2236 + /// Returns an \ref AndMap class
1.2237
1.2238 - ///Applies all map setting operations to two maps
1.2239 + /// This function just returns an \ref AndMap class.
1.2240 + ///
1.2241 + /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1.2242 + /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
1.2243 + /// <tt>m1[x]&&m2[x]</tt>.
1.2244 + ///
1.2245 + /// \relates AndMap
1.2246 + template<typename M1, typename M2>
1.2247 + inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
1.2248 + return AndMap<M1, M2>(m1,m2);
1.2249 + }
1.2250
1.2251 - ///This map has two \ref concepts::WriteMap "writable map"
1.2252 - ///parameters and each write request will be passed to both of them.
1.2253 - ///If \c M1 is also \ref concepts::ReadMap "readable",
1.2254 - ///then the read operations will return the
1.2255 - ///corresponding values of \c M1.
1.2256 +
1.2257 + /// Logical 'or' of two maps
1.2258 +
1.2259 + /// This \ref concepts::ReadMap "read-only map" returns the logical
1.2260 + /// 'or' of the values of the two given maps.
1.2261 + /// Its \c Key type is inherited from \c M1 and its \c Value type is
1.2262 + /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1.2263 ///
1.2264 - ///The \c Key and \c Value are inherited from \c M1.
1.2265 - ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1.2266 + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1.2267 + /// \code
1.2268 + /// OrMap<M1,M2> om(m1,m2);
1.2269 + /// \endcode
1.2270 + /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
1.2271 ///
1.2272 - ///\sa ForkMap
1.2273 - template<typename M1, typename M2>
1.2274 - class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1.2275 - M1& m1;
1.2276 - M2& m2;
1.2277 + /// The simplest way of using this map is through the orMap()
1.2278 + /// function.
1.2279 + ///
1.2280 + /// \sa AndMap
1.2281 + /// \sa NotMap, NotWriteMap
1.2282 + template<typename M1, typename M2>
1.2283 + class OrMap : public MapBase<typename M1::Key, bool> {
1.2284 + const M1 &_m1;
1.2285 + const M2 &_m2;
1.2286 public:
1.2287 - typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.2288 + typedef MapBase<typename M1::Key, bool> Parent;
1.2289 typedef typename Parent::Key Key;
1.2290 typedef typename Parent::Value Value;
1.2291
1.2292 - ///Constructor
1.2293 - ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1.2294 - ///\e
1.2295 - Value operator[](Key k) const {return m1[k];}
1.2296 - ///\e
1.2297 - void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1.2298 + /// Constructor
1.2299 + OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.2300 + /// \e
1.2301 + Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1.2302 };
1.2303 -
1.2304 - ///Returns a \c ForkMap class
1.2305
1.2306 - ///This function just returns a \c ForkMap class.
1.2307 - ///\relates ForkMap
1.2308 - template <typename M1, typename M2>
1.2309 - inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1.2310 - return ForkMap<M1, M2>(m1,m2);
1.2311 + /// Returns an \ref OrMap class
1.2312 +
1.2313 + /// This function just returns an \ref OrMap class.
1.2314 + ///
1.2315 + /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1.2316 + /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
1.2317 + /// <tt>m1[x]||m2[x]</tt>.
1.2318 + ///
1.2319 + /// \relates OrMap
1.2320 + template<typename M1, typename M2>
1.2321 + inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
1.2322 + return OrMap<M1, M2>(m1,m2);
1.2323 }
1.2324
1.2325 - ///Returns a \c ForkWriteMap class
1.2326
1.2327 - ///This function just returns a \c ForkWriteMap class.
1.2328 - ///\relates ForkWriteMap
1.2329 - template <typename M1, typename M2>
1.2330 - inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1.2331 - return ForkWriteMap<M1, M2>(m1,m2);
1.2332 - }
1.2333 + /// Logical 'not' of a map
1.2334
1.2335 -
1.2336 -
1.2337 - /* ************* BOOL MAPS ******************* */
1.2338 -
1.2339 - ///Logical 'not' of a map
1.2340 -
1.2341 - ///This bool \ref concepts::ReadMap "read only map" returns the
1.2342 - ///logical negation of the value returned by the given map.
1.2343 - ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1.2344 + /// This \ref concepts::ReadMap "read-only map" returns the logical
1.2345 + /// negation of the values of the given map.
1.2346 + /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1.2347 ///
1.2348 - ///\sa NotWriteMap
1.2349 - template <typename M>
1.2350 + /// The simplest way of using this map is through the notMap()
1.2351 + /// function.
1.2352 + ///
1.2353 + /// \sa NotWriteMap
1.2354 + template <typename M>
1.2355 class NotMap : public MapBase<typename M::Key, bool> {
1.2356 - const M& m;
1.2357 + const M &_m;
1.2358 public:
1.2359 typedef MapBase<typename M::Key, bool> Parent;
1.2360 typedef typename Parent::Key Key;
1.2361 typedef typename Parent::Value Value;
1.2362
1.2363 /// Constructor
1.2364 - NotMap(const M &_m) : m(_m) {};
1.2365 - ///\e
1.2366 - Value operator[](Key k) const {return !m[k];}
1.2367 + NotMap(const M &m) : _m(m) {}
1.2368 + /// \e
1.2369 + Value operator[](const Key &k) const { return !_m[k]; }
1.2370 };
1.2371
1.2372 - ///Logical 'not' of a map (ReadWrie version)
1.2373 -
1.2374 - ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
1.2375 - ///logical negation of the value returned by the given map. When it is set,
1.2376 - ///the opposite value is set to the original map.
1.2377 - ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1.2378 + /// Logical 'not' of a map (read-write version)
1.2379 +
1.2380 + /// This \ref concepts::ReadWriteMap "read-write map" returns the
1.2381 + /// logical negation of the values of the given map.
1.2382 + /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1.2383 + /// It makes also possible to write the map. When a value is set,
1.2384 + /// the opposite value is set to the original map.
1.2385 ///
1.2386 - ///\sa NotMap
1.2387 - template <typename M>
1.2388 + /// The simplest way of using this map is through the notWriteMap()
1.2389 + /// function.
1.2390 + ///
1.2391 + /// \sa NotMap
1.2392 + template <typename M>
1.2393 class NotWriteMap : public MapBase<typename M::Key, bool> {
1.2394 - M& m;
1.2395 + M &_m;
1.2396 public:
1.2397 typedef MapBase<typename M::Key, bool> Parent;
1.2398 typedef typename Parent::Key Key;
1.2399 typedef typename Parent::Value Value;
1.2400
1.2401 /// Constructor
1.2402 - NotWriteMap(M &_m) : m(_m) {};
1.2403 - ///\e
1.2404 - Value operator[](Key k) const {return !m[k];}
1.2405 - ///\e
1.2406 - void set(Key k, bool v) { m.set(k, !v); }
1.2407 + NotWriteMap(M &m) : _m(m) {}
1.2408 + /// \e
1.2409 + Value operator[](const Key &k) const { return !_m[k]; }
1.2410 + /// \e
1.2411 + void set(const Key &k, bool v) { _m.set(k, !v); }
1.2412 };
1.2413 -
1.2414 - ///Returns a \c NotMap class
1.2415 -
1.2416 - ///This function just returns a \c NotMap class.
1.2417 - ///\relates NotMap
1.2418 - template <typename M>
1.2419 +
1.2420 + /// Returns a \ref NotMap class
1.2421 +
1.2422 + /// This function just returns a \ref NotMap class.
1.2423 + ///
1.2424 + /// For example, if \c m is a map with \c bool values, then
1.2425 + /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1.2426 + ///
1.2427 + /// \relates NotMap
1.2428 + template <typename M>
1.2429 inline NotMap<M> notMap(const M &m) {
1.2430 return NotMap<M>(m);
1.2431 }
1.2432 -
1.2433 - ///Returns a \c NotWriteMap class
1.2434 -
1.2435 - ///This function just returns a \c NotWriteMap class.
1.2436 - ///\relates NotWriteMap
1.2437 - template <typename M>
1.2438 - inline NotWriteMap<M> notMap(M &m) {
1.2439 +
1.2440 + /// Returns a \ref NotWriteMap class
1.2441 +
1.2442 + /// This function just returns a \ref NotWriteMap class.
1.2443 + ///
1.2444 + /// For example, if \c m is a map with \c bool values, then
1.2445 + /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1.2446 + /// Moreover it makes also possible to write the map.
1.2447 + ///
1.2448 + /// \relates NotWriteMap
1.2449 + template <typename M>
1.2450 + inline NotWriteMap<M> notWriteMap(M &m) {
1.2451 return NotWriteMap<M>(m);
1.2452 }
1.2453
1.2454 - namespace _maps_bits {
1.2455
1.2456 - template <typename Value>
1.2457 - struct Identity {
1.2458 - typedef Value argument_type;
1.2459 - typedef Value result_type;
1.2460 - Value operator()(const Value& val) const {
1.2461 - return val;
1.2462 - }
1.2463 - };
1.2464 + /// Combination of two maps using the \c == operator
1.2465
1.2466 - template <typename _Iterator, typename Enable = void>
1.2467 - struct IteratorTraits {
1.2468 - typedef typename std::iterator_traits<_Iterator>::value_type Value;
1.2469 - };
1.2470 -
1.2471 - template <typename _Iterator>
1.2472 - struct IteratorTraits<_Iterator,
1.2473 - typename exists<typename _Iterator::container_type>::type>
1.2474 - {
1.2475 - typedef typename _Iterator::container_type::value_type Value;
1.2476 - };
1.2477 -
1.2478 - }
1.2479 -
1.2480 -
1.2481 - /// \brief Writable bool map for logging each \c true assigned element
1.2482 + /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1.2483 + /// the keys for which the corresponding values of the two maps are
1.2484 + /// equal.
1.2485 + /// Its \c Key type is inherited from \c M1 and its \c Value type is
1.2486 + /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1.2487 ///
1.2488 - /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
1.2489 - /// each \c true assigned element, i.e it copies all the keys set
1.2490 - /// to \c true to the given iterator.
1.2491 + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1.2492 + /// \code
1.2493 + /// EqualMap<M1,M2> em(m1,m2);
1.2494 + /// \endcode
1.2495 + /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
1.2496 ///
1.2497 - /// \note The container of the iterator should contain space
1.2498 - /// for each element.
1.2499 + /// The simplest way of using this map is through the equalMap()
1.2500 + /// function.
1.2501 ///
1.2502 - /// The following example shows how you can write the edges found by
1.2503 - /// the \ref Prim algorithm directly to the standard output.
1.2504 - ///\code
1.2505 - /// typedef IdMap<Graph, Edge> EdgeIdMap;
1.2506 - /// EdgeIdMap edgeId(graph);
1.2507 - ///
1.2508 - /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
1.2509 - /// EdgeIdFunctor edgeIdFunctor(edgeId);
1.2510 - ///
1.2511 - /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
1.2512 - /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1.2513 - ///
1.2514 - /// prim(graph, cost, writerMap);
1.2515 - ///\endcode
1.2516 - ///
1.2517 - ///\sa BackInserterBoolMap
1.2518 - ///\sa FrontInserterBoolMap
1.2519 - ///\sa InserterBoolMap
1.2520 - ///
1.2521 - ///\todo Revise the name of this class and the related ones.
1.2522 - template <typename _Iterator,
1.2523 - typename _Functor =
1.2524 - _maps_bits::Identity<typename _maps_bits::
1.2525 - IteratorTraits<_Iterator>::Value> >
1.2526 - class StoreBoolMap {
1.2527 + /// \sa LessMap
1.2528 + template<typename M1, typename M2>
1.2529 + class EqualMap : public MapBase<typename M1::Key, bool> {
1.2530 + const M1 &_m1;
1.2531 + const M2 &_m2;
1.2532 public:
1.2533 - typedef _Iterator Iterator;
1.2534 -
1.2535 - typedef typename _Functor::argument_type Key;
1.2536 - typedef bool Value;
1.2537 -
1.2538 - typedef _Functor Functor;
1.2539 + typedef MapBase<typename M1::Key, bool> Parent;
1.2540 + typedef typename Parent::Key Key;
1.2541 + typedef typename Parent::Value Value;
1.2542
1.2543 /// Constructor
1.2544 - StoreBoolMap(Iterator it, const Functor& functor = Functor())
1.2545 - : _begin(it), _end(it), _functor(functor) {}
1.2546 -
1.2547 - /// Gives back the given iterator set for the first key
1.2548 - Iterator begin() const {
1.2549 - return _begin;
1.2550 - }
1.2551 -
1.2552 - /// Gives back the the 'after the last' iterator
1.2553 - Iterator end() const {
1.2554 - return _end;
1.2555 - }
1.2556 -
1.2557 - /// The \c set function of the map
1.2558 - void set(const Key& key, Value value) const {
1.2559 - if (value) {
1.2560 - *_end++ = _functor(key);
1.2561 - }
1.2562 - }
1.2563 -
1.2564 - private:
1.2565 - Iterator _begin;
1.2566 - mutable Iterator _end;
1.2567 - Functor _functor;
1.2568 + EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.2569 + /// \e
1.2570 + Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1.2571 };
1.2572
1.2573 - /// \brief Writable bool map for logging each \c true assigned element in
1.2574 - /// a back insertable container.
1.2575 + /// Returns an \ref EqualMap class
1.2576 +
1.2577 + /// This function just returns an \ref EqualMap class.
1.2578 ///
1.2579 - /// Writable bool map for logging each \c true assigned element by pushing
1.2580 - /// them into a back insertable container.
1.2581 - /// It can be used to retrieve the items into a standard
1.2582 - /// container. The next example shows how you can store the
1.2583 - /// edges found by the Prim algorithm in a vector.
1.2584 + /// For example, if \c m1 and \c m2 are maps with keys and values of
1.2585 + /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
1.2586 + /// <tt>m1[x]==m2[x]</tt>.
1.2587 ///
1.2588 - ///\code
1.2589 - /// vector<Edge> span_tree_edges;
1.2590 - /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1.2591 - /// prim(graph, cost, inserter_map);
1.2592 - ///\endcode
1.2593 + /// \relates EqualMap
1.2594 + template<typename M1, typename M2>
1.2595 + inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
1.2596 + return EqualMap<M1, M2>(m1,m2);
1.2597 + }
1.2598 +
1.2599 +
1.2600 + /// Combination of two maps using the \c < operator
1.2601 +
1.2602 + /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1.2603 + /// the keys for which the corresponding value of the first map is
1.2604 + /// less then the value of the second map.
1.2605 + /// Its \c Key type is inherited from \c M1 and its \c Value type is
1.2606 + /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1.2607 ///
1.2608 - ///\sa StoreBoolMap
1.2609 - ///\sa FrontInserterBoolMap
1.2610 - ///\sa InserterBoolMap
1.2611 - template <typename Container,
1.2612 - typename Functor =
1.2613 - _maps_bits::Identity<typename Container::value_type> >
1.2614 - class BackInserterBoolMap {
1.2615 + /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1.2616 + /// \code
1.2617 + /// LessMap<M1,M2> lm(m1,m2);
1.2618 + /// \endcode
1.2619 + /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
1.2620 + ///
1.2621 + /// The simplest way of using this map is through the lessMap()
1.2622 + /// function.
1.2623 + ///
1.2624 + /// \sa EqualMap
1.2625 + template<typename M1, typename M2>
1.2626 + class LessMap : public MapBase<typename M1::Key, bool> {
1.2627 + const M1 &_m1;
1.2628 + const M2 &_m2;
1.2629 public:
1.2630 - typedef typename Functor::argument_type Key;
1.2631 - typedef bool Value;
1.2632 + typedef MapBase<typename M1::Key, bool> Parent;
1.2633 + typedef typename Parent::Key Key;
1.2634 + typedef typename Parent::Value Value;
1.2635
1.2636 /// Constructor
1.2637 - BackInserterBoolMap(Container& _container,
1.2638 - const Functor& _functor = Functor())
1.2639 - : container(_container), functor(_functor) {}
1.2640 -
1.2641 - /// The \c set function of the map
1.2642 - void set(const Key& key, Value value) {
1.2643 - if (value) {
1.2644 - container.push_back(functor(key));
1.2645 - }
1.2646 - }
1.2647 -
1.2648 - private:
1.2649 - Container& container;
1.2650 - Functor functor;
1.2651 + LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1.2652 + /// \e
1.2653 + Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1.2654 };
1.2655
1.2656 - /// \brief Writable bool map for logging each \c true assigned element in
1.2657 - /// a front insertable container.
1.2658 + /// Returns an \ref LessMap class
1.2659 +
1.2660 + /// This function just returns an \ref LessMap class.
1.2661 ///
1.2662 - /// Writable bool map for logging each \c true assigned element by pushing
1.2663 - /// them into a front insertable container.
1.2664 - /// It can be used to retrieve the items into a standard
1.2665 - /// container. For example see \ref BackInserterBoolMap.
1.2666 + /// For example, if \c m1 and \c m2 are maps with keys and values of
1.2667 + /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
1.2668 + /// <tt>m1[x]<m2[x]</tt>.
1.2669 ///
1.2670 - ///\sa BackInserterBoolMap
1.2671 - ///\sa InserterBoolMap
1.2672 - template <typename Container,
1.2673 - typename Functor =
1.2674 - _maps_bits::Identity<typename Container::value_type> >
1.2675 - class FrontInserterBoolMap {
1.2676 - public:
1.2677 - typedef typename Functor::argument_type Key;
1.2678 - typedef bool Value;
1.2679 -
1.2680 - /// Constructor
1.2681 - FrontInserterBoolMap(Container& _container,
1.2682 - const Functor& _functor = Functor())
1.2683 - : container(_container), functor(_functor) {}
1.2684 -
1.2685 - /// The \c set function of the map
1.2686 - void set(const Key& key, Value value) {
1.2687 - if (value) {
1.2688 - container.push_front(functor(key));
1.2689 - }
1.2690 - }
1.2691 -
1.2692 - private:
1.2693 - Container& container;
1.2694 - Functor functor;
1.2695 - };
1.2696 -
1.2697 - /// \brief Writable bool map for storing each \c true assigned element in
1.2698 - /// an insertable container.
1.2699 - ///
1.2700 - /// Writable bool map for storing each \c true assigned element in an
1.2701 - /// insertable container. It will insert all the keys set to \c true into
1.2702 - /// the container.
1.2703 - ///
1.2704 - /// For example, if you want to store the cut arcs of the strongly
1.2705 - /// connected components in a set you can use the next code:
1.2706 - ///
1.2707 - ///\code
1.2708 - /// set<Arc> cut_arcs;
1.2709 - /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1.2710 - /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1.2711 - ///\endcode
1.2712 - ///
1.2713 - ///\sa BackInserterBoolMap
1.2714 - ///\sa FrontInserterBoolMap
1.2715 - template <typename Container,
1.2716 - typename Functor =
1.2717 - _maps_bits::Identity<typename Container::value_type> >
1.2718 - class InserterBoolMap {
1.2719 - public:
1.2720 - typedef typename Container::value_type Key;
1.2721 - typedef bool Value;
1.2722 -
1.2723 - /// Constructor with specified iterator
1.2724 -
1.2725 - /// Constructor with specified iterator.
1.2726 - /// \param _container The container for storing the elements.
1.2727 - /// \param _it The elements will be inserted before this iterator.
1.2728 - /// \param _functor The functor that is used when an element is stored.
1.2729 - InserterBoolMap(Container& _container, typename Container::iterator _it,
1.2730 - const Functor& _functor = Functor())
1.2731 - : container(_container), it(_it), functor(_functor) {}
1.2732 -
1.2733 - /// Constructor
1.2734 -
1.2735 - /// Constructor without specified iterator.
1.2736 - /// The elements will be inserted before <tt>_container.end()</tt>.
1.2737 - /// \param _container The container for storing the elements.
1.2738 - /// \param _functor The functor that is used when an element is stored.
1.2739 - InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1.2740 - : container(_container), it(_container.end()), functor(_functor) {}
1.2741 -
1.2742 - /// The \c set function of the map
1.2743 - void set(const Key& key, Value value) {
1.2744 - if (value) {
1.2745 - it = container.insert(it, functor(key));
1.2746 - ++it;
1.2747 - }
1.2748 - }
1.2749 -
1.2750 - private:
1.2751 - Container& container;
1.2752 - typename Container::iterator it;
1.2753 - Functor functor;
1.2754 - };
1.2755 -
1.2756 - /// \brief Writable bool map for filling each \c true assigned element with a
1.2757 - /// given value.
1.2758 - ///
1.2759 - /// Writable bool map for filling each \c true assigned element with a
1.2760 - /// given value. The value can set the container.
1.2761 - ///
1.2762 - /// The following code finds the connected components of a graph
1.2763 - /// and stores it in the \c comp map:
1.2764 - ///\code
1.2765 - /// typedef Graph::NodeMap<int> ComponentMap;
1.2766 - /// ComponentMap comp(graph);
1.2767 - /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1.2768 - /// ComponentFillerMap filler(comp, 0);
1.2769 - ///
1.2770 - /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1.2771 - /// dfs.processedMap(filler);
1.2772 - /// dfs.init();
1.2773 - /// for (NodeIt it(graph); it != INVALID; ++it) {
1.2774 - /// if (!dfs.reached(it)) {
1.2775 - /// dfs.addSource(it);
1.2776 - /// dfs.start();
1.2777 - /// ++filler.fillValue();
1.2778 - /// }
1.2779 - /// }
1.2780 - ///\endcode
1.2781 - template <typename Map>
1.2782 - class FillBoolMap {
1.2783 - public:
1.2784 - typedef typename Map::Key Key;
1.2785 - typedef bool Value;
1.2786 -
1.2787 - /// Constructor
1.2788 - FillBoolMap(Map& _map, const typename Map::Value& _fill)
1.2789 - : map(_map), fill(_fill) {}
1.2790 -
1.2791 - /// Constructor
1.2792 - FillBoolMap(Map& _map)
1.2793 - : map(_map), fill() {}
1.2794 -
1.2795 - /// Gives back the current fill value
1.2796 - const typename Map::Value& fillValue() const {
1.2797 - return fill;
1.2798 - }
1.2799 -
1.2800 - /// Gives back the current fill value
1.2801 - typename Map::Value& fillValue() {
1.2802 - return fill;
1.2803 - }
1.2804 -
1.2805 - /// Sets the current fill value
1.2806 - void fillValue(const typename Map::Value& _fill) {
1.2807 - fill = _fill;
1.2808 - }
1.2809 -
1.2810 - /// The \c set function of the map
1.2811 - void set(const Key& key, Value value) {
1.2812 - if (value) {
1.2813 - map.set(key, fill);
1.2814 - }
1.2815 - }
1.2816 -
1.2817 - private:
1.2818 - Map& map;
1.2819 - typename Map::Value fill;
1.2820 - };
1.2821 -
1.2822 -
1.2823 - /// \brief Writable bool map for storing the sequence number of
1.2824 - /// \c true assignments.
1.2825 - ///
1.2826 - /// Writable bool map that stores for each \c true assigned elements
1.2827 - /// the sequence number of this setting.
1.2828 - /// It makes it easy to calculate the leaving
1.2829 - /// order of the nodes in the \c Dfs algorithm.
1.2830 - ///
1.2831 - ///\code
1.2832 - /// typedef Digraph::NodeMap<int> OrderMap;
1.2833 - /// OrderMap order(digraph);
1.2834 - /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1.2835 - /// OrderSetterMap setter(order);
1.2836 - /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1.2837 - /// dfs.processedMap(setter);
1.2838 - /// dfs.init();
1.2839 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.2840 - /// if (!dfs.reached(it)) {
1.2841 - /// dfs.addSource(it);
1.2842 - /// dfs.start();
1.2843 - /// }
1.2844 - /// }
1.2845 - ///\endcode
1.2846 - ///
1.2847 - /// The storing of the discovering order is more difficult because the
1.2848 - /// ReachedMap should be readable in the dfs algorithm but the setting
1.2849 - /// order map is not readable. Thus we must use the fork map:
1.2850 - ///
1.2851 - ///\code
1.2852 - /// typedef Digraph::NodeMap<int> OrderMap;
1.2853 - /// OrderMap order(digraph);
1.2854 - /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1.2855 - /// OrderSetterMap setter(order);
1.2856 - /// typedef Digraph::NodeMap<bool> StoreMap;
1.2857 - /// StoreMap store(digraph);
1.2858 - ///
1.2859 - /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1.2860 - /// ReachedMap reached(store, setter);
1.2861 - ///
1.2862 - /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1.2863 - /// dfs.reachedMap(reached);
1.2864 - /// dfs.init();
1.2865 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.2866 - /// if (!dfs.reached(it)) {
1.2867 - /// dfs.addSource(it);
1.2868 - /// dfs.start();
1.2869 - /// }
1.2870 - /// }
1.2871 - ///\endcode
1.2872 - template <typename Map>
1.2873 - class SettingOrderBoolMap {
1.2874 - public:
1.2875 - typedef typename Map::Key Key;
1.2876 - typedef bool Value;
1.2877 -
1.2878 - /// Constructor
1.2879 - SettingOrderBoolMap(Map& _map)
1.2880 - : map(_map), counter(0) {}
1.2881 -
1.2882 - /// Number of set operations.
1.2883 - int num() const {
1.2884 - return counter;
1.2885 - }
1.2886 -
1.2887 - /// The \c set function of the map
1.2888 - void set(const Key& key, Value value) {
1.2889 - if (value) {
1.2890 - map.set(key, counter++);
1.2891 - }
1.2892 - }
1.2893 -
1.2894 - private:
1.2895 - Map& map;
1.2896 - int counter;
1.2897 - };
1.2898 + /// \relates LessMap
1.2899 + template<typename M1, typename M2>
1.2900 + inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
1.2901 + return LessMap<M1, M2>(m1,m2);
1.2902 + }
1.2903
1.2904 /// @}
1.2905 }