1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/maps.h Fri Jan 04 21:45:55 2008 +0100
1.3 @@ -0,0 +1,1568 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2007
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_MAPS_H
1.23 +#define LEMON_MAPS_H
1.24 +
1.25 +#include <iterator>
1.26 +#include <functional>
1.27 +#include <vector>
1.28 +
1.29 +#include <lemon/bits/utility.h>
1.30 +// #include <lemon/bits/traits.h>
1.31 +
1.32 +///\file
1.33 +///\ingroup maps
1.34 +///\brief Miscellaneous property maps
1.35 +///
1.36 +#include <map>
1.37 +
1.38 +namespace lemon {
1.39 +
1.40 + /// \addtogroup maps
1.41 + /// @{
1.42 +
1.43 + /// Base class of maps.
1.44 +
1.45 + /// Base class of maps.
1.46 + /// It provides the necessary <tt>typedef</tt>s required by the map concept.
1.47 + template<typename K, typename T>
1.48 + class MapBase {
1.49 + public:
1.50 + ///\e
1.51 + typedef K Key;
1.52 + ///\e
1.53 + typedef T Value;
1.54 + };
1.55 +
1.56 + /// Null map. (a.k.a. DoNothingMap)
1.57 +
1.58 + /// This map can be used if you have to provide a map only for
1.59 + /// its type definitions, or if you have to provide a writable map,
1.60 + /// but data written to it is not required (i.e. it will be sent to
1.61 + /// <tt>/dev/null</tt>).
1.62 + template<typename K, typename T>
1.63 + class NullMap : public MapBase<K, T> {
1.64 + public:
1.65 + typedef MapBase<K, T> Parent;
1.66 + typedef typename Parent::Key Key;
1.67 + typedef typename Parent::Value Value;
1.68 +
1.69 + /// Gives back a default constructed element.
1.70 + T operator[](const K&) const { return T(); }
1.71 + /// Absorbs the value.
1.72 + void set(const K&, const T&) {}
1.73 + };
1.74 +
1.75 + ///Returns a \c NullMap class
1.76 +
1.77 + ///This function just returns a \c 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 +
1.84 +
1.85 + /// Constant map.
1.86 +
1.87 + /// This is a readable map which assigns a specified value to each key.
1.88 + /// In other aspects it is equivalent to the \c NullMap.
1.89 + template<typename K, typename T>
1.90 + class ConstMap : public MapBase<K, T> {
1.91 + private:
1.92 + T v;
1.93 + public:
1.94 +
1.95 + typedef MapBase<K, T> Parent;
1.96 + typedef typename Parent::Key Key;
1.97 + typedef typename Parent::Value Value;
1.98 +
1.99 + /// Default constructor
1.100 +
1.101 + /// Default constructor.
1.102 + /// The value of the map will be uninitialized.
1.103 + /// (More exactly it will be default constructed.)
1.104 + ConstMap() {}
1.105 +
1.106 + /// Constructor with specified initial value
1.107 +
1.108 + /// Constructor with specified initial value.
1.109 + /// \param _v is the initial value of the map.
1.110 + ConstMap(const T &_v) : v(_v) {}
1.111 +
1.112 + ///\e
1.113 + T operator[](const K&) const { return v; }
1.114 +
1.115 + ///\e
1.116 + void setAll(const T &t) {
1.117 + v = t;
1.118 + }
1.119 +
1.120 + template<typename T1>
1.121 + struct rebind {
1.122 + typedef ConstMap<K, T1> other;
1.123 + };
1.124 +
1.125 + template<typename T1>
1.126 + ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
1.127 + };
1.128 +
1.129 + ///Returns a \c ConstMap class
1.130 +
1.131 + ///This function just returns a \c ConstMap class.
1.132 + ///\relates ConstMap
1.133 + template<typename K, typename V>
1.134 + inline ConstMap<K, V> constMap(const V &v) {
1.135 + return ConstMap<K, V>(v);
1.136 + }
1.137 +
1.138 +
1.139 + template<typename T, T v>
1.140 + struct Const { };
1.141 +
1.142 + /// Constant map with inlined constant value.
1.143 +
1.144 + /// This is a readable map which assigns a specified value to each key.
1.145 + /// In other aspects it is equivalent to the \c NullMap.
1.146 + template<typename K, typename V, V v>
1.147 + class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
1.148 + public:
1.149 + typedef MapBase<K, V> Parent;
1.150 + typedef typename Parent::Key Key;
1.151 + typedef typename Parent::Value Value;
1.152 +
1.153 + ConstMap() { }
1.154 + ///\e
1.155 + V operator[](const K&) const { return v; }
1.156 + ///\e
1.157 + void set(const K&, const V&) { }
1.158 + };
1.159 +
1.160 + ///Returns a \c ConstMap class
1.161 +
1.162 + ///This function just returns a \c ConstMap class with inlined value.
1.163 + ///\relates ConstMap
1.164 + template<typename K, typename V, V v>
1.165 + inline ConstMap<K, Const<V, v> > constMap() {
1.166 + return ConstMap<K, Const<V, v> >();
1.167 + }
1.168 +
1.169 + ///Map based on std::map
1.170 +
1.171 + ///This is essentially a wrapper for \c std::map with addition that
1.172 + ///you can specify a default value different from \c Value().
1.173 + template <typename K, typename T, typename Compare = std::less<K> >
1.174 + class StdMap {
1.175 + template <typename K1, typename T1, typename C1>
1.176 + friend class StdMap;
1.177 + public:
1.178 +
1.179 + typedef True ReferenceMapTag;
1.180 + ///\e
1.181 + typedef K Key;
1.182 + ///\e
1.183 + typedef T Value;
1.184 + ///\e
1.185 + typedef T& Reference;
1.186 + ///\e
1.187 + typedef const T& ConstReference;
1.188 +
1.189 + private:
1.190 +
1.191 + typedef std::map<K, T, Compare> Map;
1.192 + Value _value;
1.193 + Map _map;
1.194 +
1.195 + public:
1.196 +
1.197 + /// Constructor with specified default value
1.198 + StdMap(const T& value = T()) : _value(value) {}
1.199 + /// \brief Constructs the map from an appropriate std::map, and explicitly
1.200 + /// specifies a default value.
1.201 + template <typename T1, typename Comp1>
1.202 + StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
1.203 + : _map(map.begin(), map.end()), _value(value) {}
1.204 +
1.205 + /// \brief Constructs a map from an other StdMap.
1.206 + template<typename T1, typename Comp1>
1.207 + StdMap(const StdMap<Key, T1, Comp1> &c)
1.208 + : _map(c._map.begin(), c._map.end()), _value(c._value) {}
1.209 +
1.210 + private:
1.211 +
1.212 + StdMap& operator=(const StdMap&);
1.213 +
1.214 + public:
1.215 +
1.216 + ///\e
1.217 + Reference operator[](const Key &k) {
1.218 + typename Map::iterator it = _map.lower_bound(k);
1.219 + if (it != _map.end() && !_map.key_comp()(k, it->first))
1.220 + return it->second;
1.221 + else
1.222 + return _map.insert(it, std::make_pair(k, _value))->second;
1.223 + }
1.224 +
1.225 + /// \e
1.226 + ConstReference operator[](const Key &k) const {
1.227 + typename Map::const_iterator it = _map.find(k);
1.228 + if (it != _map.end())
1.229 + return it->second;
1.230 + else
1.231 + return _value;
1.232 + }
1.233 +
1.234 + /// \e
1.235 + void set(const Key &k, const T &t) {
1.236 + typename Map::iterator it = _map.lower_bound(k);
1.237 + if (it != _map.end() && !_map.key_comp()(k, it->first))
1.238 + it->second = t;
1.239 + else
1.240 + _map.insert(it, std::make_pair(k, t));
1.241 + }
1.242 +
1.243 + /// \e
1.244 + void setAll(const T &t) {
1.245 + _value = t;
1.246 + _map.clear();
1.247 + }
1.248 +
1.249 + template <typename T1, typename C1 = std::less<T1> >
1.250 + struct rebind {
1.251 + typedef StdMap<Key, T1, C1> other;
1.252 + };
1.253 + };
1.254 +
1.255 + /// \brief Map for storing values for the range \c [0..size-1] range keys
1.256 + ///
1.257 + /// The current map has the \c [0..size-1] keyset and the values
1.258 + /// are stored in a \c std::vector<T> container. It can be used with
1.259 + /// some data structures, for example \c UnionFind, \c BinHeap, when
1.260 + /// the used items are small integer numbers.
1.261 + ///
1.262 + /// \todo Revise its name
1.263 + template <typename T>
1.264 + class IntegerMap {
1.265 +
1.266 + template <typename T1>
1.267 + friend class IntegerMap;
1.268 +
1.269 + public:
1.270 +
1.271 + typedef True ReferenceMapTag;
1.272 + ///\e
1.273 + typedef int Key;
1.274 + ///\e
1.275 + typedef T Value;
1.276 + ///\e
1.277 + typedef T& Reference;
1.278 + ///\e
1.279 + typedef const T& ConstReference;
1.280 +
1.281 + private:
1.282 +
1.283 + typedef std::vector<T> Vector;
1.284 + Vector _vector;
1.285 +
1.286 + public:
1.287 +
1.288 + /// Constructor with specified default value
1.289 + IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
1.290 +
1.291 + /// \brief Constructs the map from an appropriate std::vector.
1.292 + template <typename T1>
1.293 + IntegerMap(const std::vector<T1>& vector)
1.294 + : _vector(vector.begin(), vector.end()) {}
1.295 +
1.296 + /// \brief Constructs a map from an other IntegerMap.
1.297 + template <typename T1>
1.298 + IntegerMap(const IntegerMap<T1> &c)
1.299 + : _vector(c._vector.begin(), c._vector.end()) {}
1.300 +
1.301 + /// \brief Resize the container
1.302 + void resize(int size, const T& value = T()) {
1.303 + _vector.resize(size, value);
1.304 + }
1.305 +
1.306 + private:
1.307 +
1.308 + IntegerMap& operator=(const IntegerMap&);
1.309 +
1.310 + public:
1.311 +
1.312 + ///\e
1.313 + Reference operator[](Key k) {
1.314 + return _vector[k];
1.315 + }
1.316 +
1.317 + /// \e
1.318 + ConstReference operator[](Key k) const {
1.319 + return _vector[k];
1.320 + }
1.321 +
1.322 + /// \e
1.323 + void set(const Key &k, const T& t) {
1.324 + _vector[k] = t;
1.325 + }
1.326 +
1.327 + };
1.328 +
1.329 + /// @}
1.330 +
1.331 + /// \addtogroup map_adaptors
1.332 + /// @{
1.333 +
1.334 + /// \brief Identity map.
1.335 + ///
1.336 + /// This map gives back the given key as value without any
1.337 + /// modification.
1.338 + template <typename T>
1.339 + class IdentityMap : public MapBase<T, T> {
1.340 + public:
1.341 + typedef MapBase<T, T> Parent;
1.342 + typedef typename Parent::Key Key;
1.343 + typedef typename Parent::Value Value;
1.344 +
1.345 + /// \e
1.346 + const T& operator[](const T& t) const {
1.347 + return t;
1.348 + }
1.349 + };
1.350 +
1.351 + ///Returns an \c IdentityMap class
1.352 +
1.353 + ///This function just returns an \c IdentityMap class.
1.354 + ///\relates IdentityMap
1.355 + template<typename T>
1.356 + inline IdentityMap<T> identityMap() {
1.357 + return IdentityMap<T>();
1.358 + }
1.359 +
1.360 +
1.361 + ///\brief Convert the \c Value of a map to another type using
1.362 + ///the default conversion.
1.363 + ///
1.364 + ///This \c concepts::ReadMap "read only map"
1.365 + ///converts the \c Value of a map to type \c T.
1.366 + ///Its \c Key is inherited from \c M.
1.367 + template <typename M, typename T>
1.368 + class ConvertMap : public MapBase<typename M::Key, T> {
1.369 + const M& m;
1.370 + public:
1.371 + typedef MapBase<typename M::Key, T> Parent;
1.372 + typedef typename Parent::Key Key;
1.373 + typedef typename Parent::Value Value;
1.374 +
1.375 + ///Constructor
1.376 +
1.377 + ///Constructor.
1.378 + ///\param _m is the underlying map.
1.379 + ConvertMap(const M &_m) : m(_m) {};
1.380 +
1.381 + /// \brief The subscript operator.
1.382 + ///
1.383 + /// The subscript operator.
1.384 + Value operator[](const Key& k) const {return m[k];}
1.385 + };
1.386 +
1.387 + ///Returns a \c ConvertMap class
1.388 +
1.389 + ///This function just returns a \c ConvertMap class.
1.390 + ///\relates ConvertMap
1.391 + template<typename T, typename M>
1.392 + inline ConvertMap<M, T> convertMap(const M &m) {
1.393 + return ConvertMap<M, T>(m);
1.394 + }
1.395 +
1.396 + ///Simple wrapping of a map
1.397 +
1.398 + ///This \c concepts::ReadMap "read only map" returns the simple
1.399 + ///wrapping of the given map. Sometimes the reference maps cannot be
1.400 + ///combined with simple read maps. This map adaptor wraps the given
1.401 + ///map to simple read map.
1.402 + ///
1.403 + ///\sa SimpleWriteMap
1.404 + ///
1.405 + /// \todo Revise the misleading name
1.406 + template<typename M>
1.407 + class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
1.408 + const M& m;
1.409 +
1.410 + public:
1.411 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.412 + typedef typename Parent::Key Key;
1.413 + typedef typename Parent::Value Value;
1.414 +
1.415 + ///Constructor
1.416 + SimpleMap(const M &_m) : m(_m) {};
1.417 + ///\e
1.418 + Value operator[](Key k) const {return m[k];}
1.419 + };
1.420 +
1.421 + ///Simple writable wrapping of the map
1.422 +
1.423 + ///This \c concepts::WriteMap "write map" returns the simple
1.424 + ///wrapping of the given map. Sometimes the reference maps cannot be
1.425 + ///combined with simple read-write maps. This map adaptor wraps the
1.426 + ///given map to simple read-write map.
1.427 + ///
1.428 + ///\sa SimpleMap
1.429 + ///
1.430 + /// \todo Revise the misleading name
1.431 + template<typename M>
1.432 + class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.433 + M& m;
1.434 +
1.435 + public:
1.436 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.437 + typedef typename Parent::Key Key;
1.438 + typedef typename Parent::Value Value;
1.439 +
1.440 + ///Constructor
1.441 + SimpleWriteMap(M &_m) : m(_m) {};
1.442 + ///\e
1.443 + Value operator[](Key k) const {return m[k];}
1.444 + ///\e
1.445 + void set(Key k, const Value& c) { m.set(k, c); }
1.446 + };
1.447 +
1.448 + ///Sum of two maps
1.449 +
1.450 + ///This \c concepts::ReadMap "read only map" returns the sum of the two
1.451 + ///given maps.
1.452 + ///Its \c Key and \c Value are inherited from \c M1.
1.453 + ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
1.454 + template<typename M1, typename M2>
1.455 + class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
1.456 + const M1& m1;
1.457 + const M2& m2;
1.458 +
1.459 + public:
1.460 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.461 + typedef typename Parent::Key Key;
1.462 + typedef typename Parent::Value Value;
1.463 +
1.464 + ///Constructor
1.465 + AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.466 + ///\e
1.467 + Value operator[](Key k) const {return m1[k]+m2[k];}
1.468 + };
1.469 +
1.470 + ///Returns an \c AddMap class
1.471 +
1.472 + ///This function just returns an \c AddMap class.
1.473 + ///\todo How to call these type of functions?
1.474 + ///
1.475 + ///\relates AddMap
1.476 + template<typename M1, typename M2>
1.477 + inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
1.478 + return AddMap<M1, M2>(m1,m2);
1.479 + }
1.480 +
1.481 + ///Shift a map with a constant.
1.482 +
1.483 + ///This \c concepts::ReadMap "read only map" returns the sum of the
1.484 + ///given map and a constant value.
1.485 + ///Its \c Key and \c Value are inherited from \c M.
1.486 + ///
1.487 + ///Actually,
1.488 + ///\code
1.489 + /// ShiftMap<X> sh(x,v);
1.490 + ///\endcode
1.491 + ///is equivalent to
1.492 + ///\code
1.493 + /// ConstMap<X::Key, X::Value> c_tmp(v);
1.494 + /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
1.495 + ///\endcode
1.496 + ///
1.497 + ///\sa ShiftWriteMap
1.498 + template<typename M, typename C = typename M::Value>
1.499 + class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
1.500 + const M& m;
1.501 + C v;
1.502 + public:
1.503 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.504 + typedef typename Parent::Key Key;
1.505 + typedef typename Parent::Value Value;
1.506 +
1.507 + ///Constructor
1.508 +
1.509 + ///Constructor.
1.510 + ///\param _m is the undelying map.
1.511 + ///\param _v is the shift value.
1.512 + ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
1.513 + ///\e
1.514 + Value operator[](Key k) const {return m[k] + v;}
1.515 + };
1.516 +
1.517 + ///Shift a map with a constant (ReadWrite version).
1.518 +
1.519 + ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
1.520 + ///given map and a constant value. It makes also possible to write the map.
1.521 + ///Its \c Key and \c Value are inherited from \c M.
1.522 + ///
1.523 + ///\sa ShiftMap
1.524 + template<typename M, typename C = typename M::Value>
1.525 + class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.526 + M& m;
1.527 + C v;
1.528 + public:
1.529 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.530 + typedef typename Parent::Key Key;
1.531 + typedef typename Parent::Value Value;
1.532 +
1.533 + ///Constructor
1.534 +
1.535 + ///Constructor.
1.536 + ///\param _m is the undelying map.
1.537 + ///\param _v is the shift value.
1.538 + ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
1.539 + /// \e
1.540 + Value operator[](Key k) const {return m[k] + v;}
1.541 + /// \e
1.542 + void set(Key k, const Value& c) { m.set(k, c - v); }
1.543 + };
1.544 +
1.545 + ///Returns a \c ShiftMap class
1.546 +
1.547 + ///This function just returns a \c ShiftMap class.
1.548 + ///\relates ShiftMap
1.549 + template<typename M, typename C>
1.550 + inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
1.551 + return ShiftMap<M, C>(m,v);
1.552 + }
1.553 +
1.554 + ///Returns a \c ShiftWriteMap class
1.555 +
1.556 + ///This function just returns a \c ShiftWriteMap class.
1.557 + ///\relates ShiftWriteMap
1.558 + template<typename M, typename C>
1.559 + inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
1.560 + return ShiftWriteMap<M, C>(m,v);
1.561 + }
1.562 +
1.563 + ///Difference of two maps
1.564 +
1.565 + ///This \c concepts::ReadMap "read only map" returns the difference
1.566 + ///of the values of the two given maps.
1.567 + ///Its \c Key and \c Value are inherited from \c M1.
1.568 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.569 + ///
1.570 + /// \todo Revise the misleading name
1.571 + template<typename M1, typename M2>
1.572 + class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
1.573 + const M1& m1;
1.574 + const M2& m2;
1.575 + public:
1.576 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.577 + typedef typename Parent::Key Key;
1.578 + typedef typename Parent::Value Value;
1.579 +
1.580 + ///Constructor
1.581 + SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.582 + /// \e
1.583 + Value operator[](Key k) const {return m1[k]-m2[k];}
1.584 + };
1.585 +
1.586 + ///Returns a \c SubMap class
1.587 +
1.588 + ///This function just returns a \c SubMap class.
1.589 + ///
1.590 + ///\relates SubMap
1.591 + template<typename M1, typename M2>
1.592 + inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
1.593 + return SubMap<M1, M2>(m1, m2);
1.594 + }
1.595 +
1.596 + ///Product of two maps
1.597 +
1.598 + ///This \c concepts::ReadMap "read only map" returns the product of the
1.599 + ///values of the two given maps.
1.600 + ///Its \c Key and \c Value are inherited from \c M1.
1.601 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.602 + template<typename M1, typename M2>
1.603 + class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
1.604 + const M1& m1;
1.605 + const M2& m2;
1.606 + public:
1.607 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.608 + typedef typename Parent::Key Key;
1.609 + typedef typename Parent::Value Value;
1.610 +
1.611 + ///Constructor
1.612 + MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.613 + /// \e
1.614 + Value operator[](Key k) const {return m1[k]*m2[k];}
1.615 + };
1.616 +
1.617 + ///Returns a \c MulMap class
1.618 +
1.619 + ///This function just returns a \c MulMap class.
1.620 + ///\relates MulMap
1.621 + template<typename M1, typename M2>
1.622 + inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
1.623 + return MulMap<M1, M2>(m1,m2);
1.624 + }
1.625 +
1.626 + ///Scales a map with a constant.
1.627 +
1.628 + ///This \c concepts::ReadMap "read only map" returns the value of the
1.629 + ///given map multiplied from the left side with a constant value.
1.630 + ///Its \c Key and \c Value are inherited from \c M.
1.631 + ///
1.632 + ///Actually,
1.633 + ///\code
1.634 + /// ScaleMap<X> sc(x,v);
1.635 + ///\endcode
1.636 + ///is equivalent to
1.637 + ///\code
1.638 + /// ConstMap<X::Key, X::Value> c_tmp(v);
1.639 + /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
1.640 + ///\endcode
1.641 + ///
1.642 + ///\sa ScaleWriteMap
1.643 + template<typename M, typename C = typename M::Value>
1.644 + class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1.645 + const M& m;
1.646 + C v;
1.647 + public:
1.648 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.649 + typedef typename Parent::Key Key;
1.650 + typedef typename Parent::Value Value;
1.651 +
1.652 + ///Constructor
1.653 +
1.654 + ///Constructor.
1.655 + ///\param _m is the undelying map.
1.656 + ///\param _v is the scaling value.
1.657 + ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
1.658 + /// \e
1.659 + Value operator[](Key k) const {return v * m[k];}
1.660 + };
1.661 +
1.662 + ///Scales a map with a constant (ReadWrite version).
1.663 +
1.664 + ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
1.665 + ///given map multiplied from the left side with a constant value. It can
1.666 + ///also be used as write map if the \c / operator is defined between
1.667 + ///\c Value and \c C and the given multiplier is not zero.
1.668 + ///Its \c Key and \c Value are inherited from \c M.
1.669 + ///
1.670 + ///\sa ScaleMap
1.671 + template<typename M, typename C = typename M::Value>
1.672 + class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.673 + M& m;
1.674 + C v;
1.675 + public:
1.676 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.677 + typedef typename Parent::Key Key;
1.678 + typedef typename Parent::Value Value;
1.679 +
1.680 + ///Constructor
1.681 +
1.682 + ///Constructor.
1.683 + ///\param _m is the undelying map.
1.684 + ///\param _v is the scaling value.
1.685 + ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
1.686 + /// \e
1.687 + Value operator[](Key k) const {return v * m[k];}
1.688 + /// \e
1.689 + void set(Key k, const Value& c) { m.set(k, c / v);}
1.690 + };
1.691 +
1.692 + ///Returns a \c ScaleMap class
1.693 +
1.694 + ///This function just returns a \c ScaleMap class.
1.695 + ///\relates ScaleMap
1.696 + template<typename M, typename C>
1.697 + inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
1.698 + return ScaleMap<M, C>(m,v);
1.699 + }
1.700 +
1.701 + ///Returns a \c ScaleWriteMap class
1.702 +
1.703 + ///This function just returns a \c ScaleWriteMap class.
1.704 + ///\relates ScaleWriteMap
1.705 + template<typename M, typename C>
1.706 + inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
1.707 + return ScaleWriteMap<M, C>(m,v);
1.708 + }
1.709 +
1.710 + ///Quotient of two maps
1.711 +
1.712 + ///This \c concepts::ReadMap "read only map" returns the quotient of the
1.713 + ///values of the two given maps.
1.714 + ///Its \c Key and \c Value are inherited from \c M1.
1.715 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.716 + template<typename M1, typename M2>
1.717 + class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
1.718 + const M1& m1;
1.719 + const M2& m2;
1.720 + public:
1.721 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.722 + typedef typename Parent::Key Key;
1.723 + typedef typename Parent::Value Value;
1.724 +
1.725 + ///Constructor
1.726 + DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.727 + /// \e
1.728 + Value operator[](Key k) const {return m1[k]/m2[k];}
1.729 + };
1.730 +
1.731 + ///Returns a \c DivMap class
1.732 +
1.733 + ///This function just returns a \c DivMap class.
1.734 + ///\relates DivMap
1.735 + template<typename M1, typename M2>
1.736 + inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
1.737 + return DivMap<M1, M2>(m1,m2);
1.738 + }
1.739 +
1.740 + ///Composition of two maps
1.741 +
1.742 + ///This \c concepts::ReadMap "read only map" returns the composition of
1.743 + ///two given maps.
1.744 + ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
1.745 + ///then for
1.746 + ///\code
1.747 + /// ComposeMap<M1, M2> cm(m1,m2);
1.748 + ///\endcode
1.749 + /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
1.750 + ///
1.751 + ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
1.752 + ///\c M2::Value must be convertible to \c M1::Key.
1.753 + ///
1.754 + ///\sa CombineMap
1.755 + ///
1.756 + ///\todo Check the requirements.
1.757 + template <typename M1, typename M2>
1.758 + class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
1.759 + const M1& m1;
1.760 + const M2& m2;
1.761 + public:
1.762 + typedef MapBase<typename M2::Key, typename M1::Value> Parent;
1.763 + typedef typename Parent::Key Key;
1.764 + typedef typename Parent::Value Value;
1.765 +
1.766 + ///Constructor
1.767 + ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
1.768 +
1.769 + /// \e
1.770 +
1.771 +
1.772 + /// \todo Use the MapTraits once it is ported.
1.773 + ///
1.774 +
1.775 + //typename MapTraits<M1>::ConstReturnValue
1.776 + typename M1::Value
1.777 + operator[](Key k) const {return m1[m2[k]];}
1.778 + };
1.779 +
1.780 + ///Returns a \c ComposeMap class
1.781 +
1.782 + ///This function just returns a \c ComposeMap class.
1.783 + ///\relates ComposeMap
1.784 + template <typename M1, typename M2>
1.785 + inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
1.786 + return ComposeMap<M1, M2>(m1,m2);
1.787 + }
1.788 +
1.789 + ///Combine of two maps using an STL (binary) functor.
1.790 +
1.791 + ///Combine of two maps using an STL (binary) functor.
1.792 + ///
1.793 + ///This \c concepts::ReadMap "read only map" takes two maps and a
1.794 + ///binary functor and returns the composition of the two
1.795 + ///given maps unsing the functor.
1.796 + ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
1.797 + ///and \c f is of \c F, then for
1.798 + ///\code
1.799 + /// CombineMap<M1,M2,F,V> cm(m1,m2,f);
1.800 + ///\endcode
1.801 + /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
1.802 + ///
1.803 + ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
1.804 + ///\c M2::Value and \c M1::Value must be convertible to the corresponding
1.805 + ///input parameter of \c F and the return type of \c F must be convertible
1.806 + ///to \c V.
1.807 + ///
1.808 + ///\sa ComposeMap
1.809 + ///
1.810 + ///\todo Check the requirements.
1.811 + template<typename M1, typename M2, typename F,
1.812 + typename V = typename F::result_type>
1.813 + class CombineMap : public MapBase<typename M1::Key, V> {
1.814 + const M1& m1;
1.815 + const M2& m2;
1.816 + F f;
1.817 + public:
1.818 + typedef MapBase<typename M1::Key, V> Parent;
1.819 + typedef typename Parent::Key Key;
1.820 + typedef typename Parent::Value Value;
1.821 +
1.822 + ///Constructor
1.823 + CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
1.824 + : m1(_m1), m2(_m2), f(_f) {};
1.825 + /// \e
1.826 + Value operator[](Key k) const {return f(m1[k],m2[k]);}
1.827 + };
1.828 +
1.829 + ///Returns a \c CombineMap class
1.830 +
1.831 + ///This function just returns a \c CombineMap class.
1.832 + ///
1.833 + ///For example if \c m1 and \c m2 are both \c double valued maps, then
1.834 + ///\code
1.835 + ///combineMap<double>(m1,m2,std::plus<double>())
1.836 + ///\endcode
1.837 + ///is equivalent to
1.838 + ///\code
1.839 + ///addMap(m1,m2)
1.840 + ///\endcode
1.841 + ///
1.842 + ///This function is specialized for adaptable binary function
1.843 + ///classes and C++ functions.
1.844 + ///
1.845 + ///\relates CombineMap
1.846 + template<typename M1, typename M2, typename F, typename V>
1.847 + inline CombineMap<M1, M2, F, V>
1.848 + combineMap(const M1& m1,const M2& m2, const F& f) {
1.849 + return CombineMap<M1, M2, F, V>(m1,m2,f);
1.850 + }
1.851 +
1.852 + template<typename M1, typename M2, typename F>
1.853 + inline CombineMap<M1, M2, F, typename F::result_type>
1.854 + combineMap(const M1& m1, const M2& m2, const F& f) {
1.855 + return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
1.856 + }
1.857 +
1.858 + template<typename M1, typename M2, typename K1, typename K2, typename V>
1.859 + inline CombineMap<M1, M2, V (*)(K1, K2), V>
1.860 + combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
1.861 + return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
1.862 + }
1.863 +
1.864 + ///Negative value of a map
1.865 +
1.866 + ///This \c concepts::ReadMap "read only map" returns the negative
1.867 + ///value of the value returned by the given map.
1.868 + ///Its \c Key and \c Value are inherited from \c M.
1.869 + ///The unary \c - operator must be defined for \c Value, of course.
1.870 + ///
1.871 + ///\sa NegWriteMap
1.872 + template<typename M>
1.873 + class NegMap : public MapBase<typename M::Key, typename M::Value> {
1.874 + const M& m;
1.875 + public:
1.876 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.877 + typedef typename Parent::Key Key;
1.878 + typedef typename Parent::Value Value;
1.879 +
1.880 + ///Constructor
1.881 + NegMap(const M &_m) : m(_m) {};
1.882 + /// \e
1.883 + Value operator[](Key k) const {return -m[k];}
1.884 + };
1.885 +
1.886 + ///Negative value of a map (ReadWrite version)
1.887 +
1.888 + ///This \c concepts::ReadWriteMap "read-write map" returns the negative
1.889 + ///value of the value returned by the given map.
1.890 + ///Its \c Key and \c Value are inherited from \c M.
1.891 + ///The unary \c - operator must be defined for \c Value, of course.
1.892 + ///
1.893 + /// \sa NegMap
1.894 + template<typename M>
1.895 + class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.896 + M& m;
1.897 + public:
1.898 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.899 + typedef typename Parent::Key Key;
1.900 + typedef typename Parent::Value Value;
1.901 +
1.902 + ///Constructor
1.903 + NegWriteMap(M &_m) : m(_m) {};
1.904 + /// \e
1.905 + Value operator[](Key k) const {return -m[k];}
1.906 + /// \e
1.907 + void set(Key k, const Value& v) { m.set(k, -v); }
1.908 + };
1.909 +
1.910 + ///Returns a \c NegMap class
1.911 +
1.912 + ///This function just returns a \c NegMap class.
1.913 + ///\relates NegMap
1.914 + template <typename M>
1.915 + inline NegMap<M> negMap(const M &m) {
1.916 + return NegMap<M>(m);
1.917 + }
1.918 +
1.919 + ///Returns a \c NegWriteMap class
1.920 +
1.921 + ///This function just returns a \c NegWriteMap class.
1.922 + ///\relates NegWriteMap
1.923 + template <typename M>
1.924 + inline NegWriteMap<M> negMap(M &m) {
1.925 + return NegWriteMap<M>(m);
1.926 + }
1.927 +
1.928 + ///Absolute value of a map
1.929 +
1.930 + ///This \c concepts::ReadMap "read only map" returns the absolute value
1.931 + ///of the value returned by the given map.
1.932 + ///Its \c Key and \c Value are inherited from \c M.
1.933 + ///\c Value must be comparable to \c 0 and the unary \c -
1.934 + ///operator must be defined for it, of course.
1.935 + template<typename M>
1.936 + class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1.937 + const M& m;
1.938 + public:
1.939 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.940 + typedef typename Parent::Key Key;
1.941 + typedef typename Parent::Value Value;
1.942 +
1.943 + ///Constructor
1.944 + AbsMap(const M &_m) : m(_m) {};
1.945 + /// \e
1.946 + Value operator[](Key k) const {
1.947 + Value tmp = m[k];
1.948 + return tmp >= 0 ? tmp : -tmp;
1.949 + }
1.950 +
1.951 + };
1.952 +
1.953 + ///Returns an \c AbsMap class
1.954 +
1.955 + ///This function just returns an \c AbsMap class.
1.956 + ///\relates AbsMap
1.957 + template<typename M>
1.958 + inline AbsMap<M> absMap(const M &m) {
1.959 + return AbsMap<M>(m);
1.960 + }
1.961 +
1.962 + ///Converts an STL style functor to a map
1.963 +
1.964 + ///This \c concepts::ReadMap "read only map" returns the value
1.965 + ///of a given functor.
1.966 + ///
1.967 + ///Template parameters \c K and \c V will become its
1.968 + ///\c Key and \c Value. They must be given explicitly
1.969 + ///because a functor does not provide such typedefs.
1.970 + ///
1.971 + ///Parameter \c F is the type of the used functor.
1.972 + ///
1.973 + ///\sa MapFunctor
1.974 + template<typename F,
1.975 + typename K = typename F::argument_type,
1.976 + typename V = typename F::result_type>
1.977 + class FunctorMap : public MapBase<K, V> {
1.978 + F f;
1.979 + public:
1.980 + typedef MapBase<K, V> Parent;
1.981 + typedef typename Parent::Key Key;
1.982 + typedef typename Parent::Value Value;
1.983 +
1.984 + ///Constructor
1.985 + FunctorMap(const F &_f = F()) : f(_f) {}
1.986 + /// \e
1.987 + Value operator[](Key k) const { return f(k);}
1.988 + };
1.989 +
1.990 + ///Returns a \c FunctorMap class
1.991 +
1.992 + ///This function just returns a \c FunctorMap class.
1.993 + ///
1.994 + ///It is specialized for adaptable function classes and
1.995 + ///C++ functions.
1.996 + ///\relates FunctorMap
1.997 + template<typename K, typename V, typename F> inline
1.998 + FunctorMap<F, K, V> functorMap(const F &f) {
1.999 + return FunctorMap<F, K, V>(f);
1.1000 + }
1.1001 +
1.1002 + template <typename F> inline
1.1003 + FunctorMap<F, typename F::argument_type, typename F::result_type>
1.1004 + functorMap(const F &f) {
1.1005 + return FunctorMap<F, typename F::argument_type,
1.1006 + typename F::result_type>(f);
1.1007 + }
1.1008 +
1.1009 + template <typename K, typename V> inline
1.1010 + FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
1.1011 + return FunctorMap<V (*)(K), K, V>(f);
1.1012 + }
1.1013 +
1.1014 +
1.1015 + ///Converts a map to an STL style (unary) functor
1.1016 +
1.1017 + ///This class Converts a map to an STL style (unary) functor.
1.1018 + ///that is it provides an <tt>operator()</tt> to read its values.
1.1019 + ///
1.1020 + ///For the sake of convenience it also works as
1.1021 + ///a ususal \c concepts::ReadMap "readable map",
1.1022 + ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1.1023 + ///
1.1024 + ///\sa FunctorMap
1.1025 + template <typename M>
1.1026 + class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1.1027 + const M& m;
1.1028 + public:
1.1029 + typedef MapBase<typename M::Key, typename M::Value> Parent;
1.1030 + typedef typename Parent::Key Key;
1.1031 + typedef typename Parent::Value Value;
1.1032 +
1.1033 + typedef typename M::Key argument_type;
1.1034 + typedef typename M::Value result_type;
1.1035 +
1.1036 + ///Constructor
1.1037 + MapFunctor(const M &_m) : m(_m) {};
1.1038 + ///\e
1.1039 + Value operator()(Key k) const {return m[k];}
1.1040 + ///\e
1.1041 + Value operator[](Key k) const {return m[k];}
1.1042 + };
1.1043 +
1.1044 + ///Returns a \c MapFunctor class
1.1045 +
1.1046 + ///This function just returns a \c MapFunctor class.
1.1047 + ///\relates MapFunctor
1.1048 + template<typename M>
1.1049 + inline MapFunctor<M> mapFunctor(const M &m) {
1.1050 + return MapFunctor<M>(m);
1.1051 + }
1.1052 +
1.1053 + ///Applies all map setting operations to two maps
1.1054 +
1.1055 + ///This map has two \c concepts::ReadMap "readable map"
1.1056 + ///parameters and each read request will be passed just to the
1.1057 + ///first map. This class is the just readable map type of the ForkWriteMap.
1.1058 + ///
1.1059 + ///The \c Key and \c Value are inherited from \c M1.
1.1060 + ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1.1061 + ///
1.1062 + ///\sa ForkWriteMap
1.1063 + ///
1.1064 + /// \todo Why is it needed?
1.1065 + template<typename M1, typename M2>
1.1066 + class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1067 + const M1& m1;
1.1068 + const M2& m2;
1.1069 + public:
1.1070 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1071 + typedef typename Parent::Key Key;
1.1072 + typedef typename Parent::Value Value;
1.1073 +
1.1074 + ///Constructor
1.1075 + ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1.1076 + /// \e
1.1077 + Value operator[](Key k) const {return m1[k];}
1.1078 + };
1.1079 +
1.1080 +
1.1081 + ///Applies all map setting operations to two maps
1.1082 +
1.1083 + ///This map has two \c concepts::WriteMap "writable map"
1.1084 + ///parameters and each write request will be passed to both of them.
1.1085 + ///If \c M1 is also \c concepts::ReadMap "readable",
1.1086 + ///then the read operations will return the
1.1087 + ///corresponding values of \c M1.
1.1088 + ///
1.1089 + ///The \c Key and \c Value are inherited from \c M1.
1.1090 + ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1.1091 + ///
1.1092 + ///\sa ForkMap
1.1093 + template<typename M1, typename M2>
1.1094 + class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1.1095 + M1& m1;
1.1096 + M2& m2;
1.1097 + public:
1.1098 + typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1.1099 + typedef typename Parent::Key Key;
1.1100 + typedef typename Parent::Value Value;
1.1101 +
1.1102 + ///Constructor
1.1103 + ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1.1104 + ///\e
1.1105 + Value operator[](Key k) const {return m1[k];}
1.1106 + ///\e
1.1107 + void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1.1108 + };
1.1109 +
1.1110 + ///Returns a \c ForkMap class
1.1111 +
1.1112 + ///This function just returns a \c ForkMap class.
1.1113 + ///\relates ForkMap
1.1114 + template <typename M1, typename M2>
1.1115 + inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1.1116 + return ForkMap<M1, M2>(m1,m2);
1.1117 + }
1.1118 +
1.1119 + ///Returns a \c ForkWriteMap class
1.1120 +
1.1121 + ///This function just returns a \c ForkWriteMap class.
1.1122 + ///\relates ForkWriteMap
1.1123 + template <typename M1, typename M2>
1.1124 + inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1.1125 + return ForkWriteMap<M1, M2>(m1,m2);
1.1126 + }
1.1127 +
1.1128 +
1.1129 +
1.1130 + /* ************* BOOL MAPS ******************* */
1.1131 +
1.1132 + ///Logical 'not' of a map
1.1133 +
1.1134 + ///This bool \c concepts::ReadMap "read only map" returns the
1.1135 + ///logical negation of the value returned by the given map.
1.1136 + ///Its \c Key is inherited from \c M, its Value is \c bool.
1.1137 + ///
1.1138 + ///\sa NotWriteMap
1.1139 + template <typename M>
1.1140 + class NotMap : public MapBase<typename M::Key, bool> {
1.1141 + const M& m;
1.1142 + public:
1.1143 + typedef MapBase<typename M::Key, bool> Parent;
1.1144 + typedef typename Parent::Key Key;
1.1145 + typedef typename Parent::Value Value;
1.1146 +
1.1147 + /// Constructor
1.1148 + NotMap(const M &_m) : m(_m) {};
1.1149 + ///\e
1.1150 + Value operator[](Key k) const {return !m[k];}
1.1151 + };
1.1152 +
1.1153 + ///Logical 'not' of a map (ReadWrie version)
1.1154 +
1.1155 + ///This bool \c concepts::ReadWriteMap "read-write map" returns the
1.1156 + ///logical negation of the value returned by the given map. When it is set,
1.1157 + ///the opposite value is set to the original map.
1.1158 + ///Its \c Key is inherited from \c M, its Value is \c bool.
1.1159 + ///
1.1160 + ///\sa NotMap
1.1161 + template <typename M>
1.1162 + class NotWriteMap : public MapBase<typename M::Key, bool> {
1.1163 + M& m;
1.1164 + public:
1.1165 + typedef MapBase<typename M::Key, bool> Parent;
1.1166 + typedef typename Parent::Key Key;
1.1167 + typedef typename Parent::Value Value;
1.1168 +
1.1169 + /// Constructor
1.1170 + NotWriteMap(M &_m) : m(_m) {};
1.1171 + ///\e
1.1172 + Value operator[](Key k) const {return !m[k];}
1.1173 + ///\e
1.1174 + void set(Key k, bool v) { m.set(k, !v); }
1.1175 + };
1.1176 +
1.1177 + ///Returns a \c NotMap class
1.1178 +
1.1179 + ///This function just returns a \c NotMap class.
1.1180 + ///\relates NotMap
1.1181 + template <typename M>
1.1182 + inline NotMap<M> notMap(const M &m) {
1.1183 + return NotMap<M>(m);
1.1184 + }
1.1185 +
1.1186 + ///Returns a \c NotWriteMap class
1.1187 +
1.1188 + ///This function just returns a \c NotWriteMap class.
1.1189 + ///\relates NotWriteMap
1.1190 + template <typename M>
1.1191 + inline NotWriteMap<M> notMap(M &m) {
1.1192 + return NotWriteMap<M>(m);
1.1193 + }
1.1194 +
1.1195 + namespace _maps_bits {
1.1196 +
1.1197 + template <typename Value>
1.1198 + struct Identity {
1.1199 + typedef Value argument_type;
1.1200 + typedef Value result_type;
1.1201 + Value operator()(const Value& val) const {
1.1202 + return val;
1.1203 + }
1.1204 + };
1.1205 +
1.1206 + template <typename _Iterator, typename Enable = void>
1.1207 + struct IteratorTraits {
1.1208 + typedef typename std::iterator_traits<_Iterator>::value_type Value;
1.1209 + };
1.1210 +
1.1211 + template <typename _Iterator>
1.1212 + struct IteratorTraits<_Iterator,
1.1213 + typename exists<typename _Iterator::container_type>::type>
1.1214 + {
1.1215 + typedef typename _Iterator::container_type::value_type Value;
1.1216 + };
1.1217 +
1.1218 + }
1.1219 +
1.1220 +
1.1221 + /// \brief Writable bool map for logging each \c true assigned element
1.1222 + ///
1.1223 + /// Writable bool map for logging each \c true assigned element, i.e it
1.1224 + /// copies all the keys set to \c true to the given iterator.
1.1225 + ///
1.1226 + /// \note The container of the iterator should contain space
1.1227 + /// for each element.
1.1228 + ///
1.1229 + /// The following example shows how you can write the edges found by the Prim
1.1230 + /// algorithm directly
1.1231 + /// to the standard output.
1.1232 + ///\code
1.1233 + /// typedef IdMap<Graph, Edge> EdgeIdMap;
1.1234 + /// EdgeIdMap edgeId(graph);
1.1235 + ///
1.1236 + /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
1.1237 + /// EdgeIdFunctor edgeIdFunctor(edgeId);
1.1238 + ///
1.1239 + /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
1.1240 + /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1.1241 + ///
1.1242 + /// prim(graph, cost, writerMap);
1.1243 + ///\endcode
1.1244 + ///
1.1245 + ///\sa BackInserterBoolMap
1.1246 + ///
1.1247 + ///\todo Revise the name of this class and the related ones.
1.1248 + template <typename _Iterator,
1.1249 + typename _Functor =
1.1250 + _maps_bits::Identity<typename _maps_bits::
1.1251 + IteratorTraits<_Iterator>::Value> >
1.1252 + class StoreBoolMap {
1.1253 + public:
1.1254 + typedef _Iterator Iterator;
1.1255 +
1.1256 + typedef typename _Functor::argument_type Key;
1.1257 + typedef bool Value;
1.1258 +
1.1259 + typedef _Functor Functor;
1.1260 +
1.1261 + /// Constructor
1.1262 + StoreBoolMap(Iterator it, const Functor& functor = Functor())
1.1263 + : _begin(it), _end(it), _functor(functor) {}
1.1264 +
1.1265 + /// Gives back the given iterator set for the first key
1.1266 + Iterator begin() const {
1.1267 + return _begin;
1.1268 + }
1.1269 +
1.1270 + /// Gives back the the 'after the last' iterator
1.1271 + Iterator end() const {
1.1272 + return _end;
1.1273 + }
1.1274 +
1.1275 + /// The \c set function of the map
1.1276 + void set(const Key& key, Value value) const {
1.1277 + if (value) {
1.1278 + *_end++ = _functor(key);
1.1279 + }
1.1280 + }
1.1281 +
1.1282 + private:
1.1283 + Iterator _begin;
1.1284 + mutable Iterator _end;
1.1285 + Functor _functor;
1.1286 + };
1.1287 +
1.1288 + /// \brief Writable bool map for logging each \c true assigned element in
1.1289 + /// a back insertable container.
1.1290 + ///
1.1291 + /// Writable bool map for logging each \c true assigned element by pushing
1.1292 + /// them into a back insertable container.
1.1293 + /// It can be used to retrieve the items into a standard
1.1294 + /// container. The next example shows how you can store the
1.1295 + /// edges found by the Prim algorithm in a vector.
1.1296 + ///
1.1297 + ///\code
1.1298 + /// vector<Edge> span_tree_edges;
1.1299 + /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1.1300 + /// prim(graph, cost, inserter_map);
1.1301 + ///\endcode
1.1302 + ///
1.1303 + ///\sa StoreBoolMap
1.1304 + ///\sa FrontInserterBoolMap
1.1305 + ///\sa InserterBoolMap
1.1306 + template <typename Container,
1.1307 + typename Functor =
1.1308 + _maps_bits::Identity<typename Container::value_type> >
1.1309 + class BackInserterBoolMap {
1.1310 + public:
1.1311 + typedef typename Container::value_type Key;
1.1312 + typedef bool Value;
1.1313 +
1.1314 + /// Constructor
1.1315 + BackInserterBoolMap(Container& _container,
1.1316 + const Functor& _functor = Functor())
1.1317 + : container(_container), functor(_functor) {}
1.1318 +
1.1319 + /// The \c set function of the map
1.1320 + void set(const Key& key, Value value) {
1.1321 + if (value) {
1.1322 + container.push_back(functor(key));
1.1323 + }
1.1324 + }
1.1325 +
1.1326 + private:
1.1327 + Container& container;
1.1328 + Functor functor;
1.1329 + };
1.1330 +
1.1331 + /// \brief Writable bool map for logging each \c true assigned element in
1.1332 + /// a front insertable container.
1.1333 + ///
1.1334 + /// Writable bool map for logging each \c true assigned element by pushing
1.1335 + /// them into a front insertable container.
1.1336 + /// It can be used to retrieve the items into a standard
1.1337 + /// container. For example see \ref BackInserterBoolMap.
1.1338 + ///
1.1339 + ///\sa BackInserterBoolMap
1.1340 + ///\sa InserterBoolMap
1.1341 + template <typename Container,
1.1342 + typename Functor =
1.1343 + _maps_bits::Identity<typename Container::value_type> >
1.1344 + class FrontInserterBoolMap {
1.1345 + public:
1.1346 + typedef typename Container::value_type Key;
1.1347 + typedef bool Value;
1.1348 +
1.1349 + /// Constructor
1.1350 + FrontInserterBoolMap(Container& _container,
1.1351 + const Functor& _functor = Functor())
1.1352 + : container(_container), functor(_functor) {}
1.1353 +
1.1354 + /// The \c set function of the map
1.1355 + void set(const Key& key, Value value) {
1.1356 + if (value) {
1.1357 + container.push_front(functor(key));
1.1358 + }
1.1359 + }
1.1360 +
1.1361 + private:
1.1362 + Container& container;
1.1363 + Functor functor;
1.1364 + };
1.1365 +
1.1366 + /// \brief Writable bool map for storing each \c true assigned element in
1.1367 + /// an insertable container.
1.1368 + ///
1.1369 + /// Writable bool map for storing each \c true assigned element in an
1.1370 + /// insertable container. It will insert all the keys set to \c true into
1.1371 + /// the container.
1.1372 + ///
1.1373 + /// For example, if you want to store the cut arcs of the strongly
1.1374 + /// connected components in a set you can use the next code:
1.1375 + ///
1.1376 + ///\code
1.1377 + /// set<Arc> cut_arcs;
1.1378 + /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1.1379 + /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1.1380 + ///\endcode
1.1381 + ///
1.1382 + ///\sa BackInserterBoolMap
1.1383 + ///\sa FrontInserterBoolMap
1.1384 + template <typename Container,
1.1385 + typename Functor =
1.1386 + _maps_bits::Identity<typename Container::value_type> >
1.1387 + class InserterBoolMap {
1.1388 + public:
1.1389 + typedef typename Container::value_type Key;
1.1390 + typedef bool Value;
1.1391 +
1.1392 + /// Constructor with specified iterator
1.1393 +
1.1394 + /// Constructor with specified iterator.
1.1395 + /// \param _container The container for storing the elements.
1.1396 + /// \param _it The elements will be inserted before this iterator.
1.1397 + /// \param _functor The functor that is used when an element is stored.
1.1398 + InserterBoolMap(Container& _container, typename Container::iterator _it,
1.1399 + const Functor& _functor = Functor())
1.1400 + : container(_container), it(_it), functor(_functor) {}
1.1401 +
1.1402 + /// Constructor
1.1403 +
1.1404 + /// Constructor without specified iterator.
1.1405 + /// The elements will be inserted before <tt>_container.end()</tt>.
1.1406 + /// \param _container The container for storing the elements.
1.1407 + /// \param _functor The functor that is used when an element is stored.
1.1408 + InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1.1409 + : container(_container), it(_container.end()), functor(_functor) {}
1.1410 +
1.1411 + /// The \c set function of the map
1.1412 + void set(const Key& key, Value value) {
1.1413 + if (value) {
1.1414 + it = container.insert(it, functor(key));
1.1415 + ++it;
1.1416 + }
1.1417 + }
1.1418 +
1.1419 + private:
1.1420 + Container& container;
1.1421 + typename Container::iterator it;
1.1422 + Functor functor;
1.1423 + };
1.1424 +
1.1425 + /// \brief Writable bool map for filling each \c true assigned element with a
1.1426 + /// given value.
1.1427 + ///
1.1428 + /// Writable bool map for filling each \c true assigned element with a
1.1429 + /// given value. The value can set the container.
1.1430 + ///
1.1431 + /// The following code finds the connected components of a graph
1.1432 + /// and stores it in the \c comp map:
1.1433 + ///\code
1.1434 + /// typedef Graph::NodeMap<int> ComponentMap;
1.1435 + /// ComponentMap comp(graph);
1.1436 + /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1.1437 + /// ComponentFillerMap filler(comp, 0);
1.1438 + ///
1.1439 + /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1.1440 + /// dfs.processedMap(filler);
1.1441 + /// dfs.init();
1.1442 + /// for (NodeIt it(graph); it != INVALID; ++it) {
1.1443 + /// if (!dfs.reached(it)) {
1.1444 + /// dfs.addSource(it);
1.1445 + /// dfs.start();
1.1446 + /// ++filler.fillValue();
1.1447 + /// }
1.1448 + /// }
1.1449 + ///\endcode
1.1450 + template <typename Map>
1.1451 + class FillBoolMap {
1.1452 + public:
1.1453 + typedef typename Map::Key Key;
1.1454 + typedef bool Value;
1.1455 +
1.1456 + /// Constructor
1.1457 + FillBoolMap(Map& _map, const typename Map::Value& _fill)
1.1458 + : map(_map), fill(_fill) {}
1.1459 +
1.1460 + /// Constructor
1.1461 + FillBoolMap(Map& _map)
1.1462 + : map(_map), fill() {}
1.1463 +
1.1464 + /// Gives back the current fill value
1.1465 + const typename Map::Value& fillValue() const {
1.1466 + return fill;
1.1467 + }
1.1468 +
1.1469 + /// Gives back the current fill value
1.1470 + typename Map::Value& fillValue() {
1.1471 + return fill;
1.1472 + }
1.1473 +
1.1474 + /// Sets the current fill value
1.1475 + void fillValue(const typename Map::Value& _fill) {
1.1476 + fill = _fill;
1.1477 + }
1.1478 +
1.1479 + /// The \c set function of the map
1.1480 + void set(const Key& key, Value value) {
1.1481 + if (value) {
1.1482 + map.set(key, fill);
1.1483 + }
1.1484 + }
1.1485 +
1.1486 + private:
1.1487 + Map& map;
1.1488 + typename Map::Value fill;
1.1489 + };
1.1490 +
1.1491 +
1.1492 + /// \brief Writable bool map for storing the sequence number of
1.1493 + /// \c true assignments.
1.1494 + ///
1.1495 + /// Writable bool map that stores for each \c true assigned elements
1.1496 + /// the sequence number of this setting.
1.1497 + /// It makes it easy to calculate the leaving
1.1498 + /// order of the nodes in the \c Dfs algorithm.
1.1499 + ///
1.1500 + ///\code
1.1501 + /// typedef Digraph::NodeMap<int> OrderMap;
1.1502 + /// OrderMap order(digraph);
1.1503 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1.1504 + /// OrderSetterMap setter(order);
1.1505 + /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1.1506 + /// dfs.processedMap(setter);
1.1507 + /// dfs.init();
1.1508 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.1509 + /// if (!dfs.reached(it)) {
1.1510 + /// dfs.addSource(it);
1.1511 + /// dfs.start();
1.1512 + /// }
1.1513 + /// }
1.1514 + ///\endcode
1.1515 + ///
1.1516 + /// The storing of the discovering order is more difficult because the
1.1517 + /// ReachedMap should be readable in the dfs algorithm but the setting
1.1518 + /// order map is not readable. Thus we must use the fork map:
1.1519 + ///
1.1520 + ///\code
1.1521 + /// typedef Digraph::NodeMap<int> OrderMap;
1.1522 + /// OrderMap order(digraph);
1.1523 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1.1524 + /// OrderSetterMap setter(order);
1.1525 + /// typedef Digraph::NodeMap<bool> StoreMap;
1.1526 + /// StoreMap store(digraph);
1.1527 + ///
1.1528 + /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1.1529 + /// ReachedMap reached(store, setter);
1.1530 + ///
1.1531 + /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1.1532 + /// dfs.reachedMap(reached);
1.1533 + /// dfs.init();
1.1534 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.1535 + /// if (!dfs.reached(it)) {
1.1536 + /// dfs.addSource(it);
1.1537 + /// dfs.start();
1.1538 + /// }
1.1539 + /// }
1.1540 + ///\endcode
1.1541 + template <typename Map>
1.1542 + class SettingOrderBoolMap {
1.1543 + public:
1.1544 + typedef typename Map::Key Key;
1.1545 + typedef bool Value;
1.1546 +
1.1547 + /// Constructor
1.1548 + SettingOrderBoolMap(Map& _map)
1.1549 + : map(_map), counter(0) {}
1.1550 +
1.1551 + /// Number of set operations.
1.1552 + int num() const {
1.1553 + return counter;
1.1554 + }
1.1555 +
1.1556 + /// Setter function of the map
1.1557 + void set(const Key& key, Value value) {
1.1558 + if (value) {
1.1559 + map.set(key, counter++);
1.1560 + }
1.1561 + }
1.1562 +
1.1563 + private:
1.1564 + Map& map;
1.1565 + int counter;
1.1566 + };
1.1567 +
1.1568 + /// @}
1.1569 +}
1.1570 +
1.1571 +#endif // LEMON_MAPS_H