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