Changes in lemon/maps.h [54:ff9bac2351bf:82:bce6c8f93d10] in lemon1.2
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/maps.h
r54 r82 25 25 26 26 #include <lemon/bits/utility.h> 27 //#include <lemon/bits/traits.h>27 #include <lemon/bits/traits.h> 28 28 29 29 ///\file 30 30 ///\ingroup maps 31 31 ///\brief Miscellaneous property maps 32 /// 32 33 33 #include <map> 34 34 … … 40 40 /// Base class of maps. 41 41 42 /// Base class of maps. 43 /// It provides the necessary <tt>typedef</tt>s required by the map concept.44 template<typename K, typename T>42 /// Base class of maps. It provides the necessary type definitions 43 /// required by the map %concepts. 44 template<typename K, typename V> 45 45 class MapBase { 46 46 public: 47 /// The key type of the map.47 /// \biref The key type of the map. 48 48 typedef K Key; 49 /// The value type of the map. (The type of objects associated with the keys). 50 typedef T Value; 51 }; 49 /// \brief The value type of the map. 50 /// (The type of objects associated with the keys). 51 typedef V Value; 52 }; 53 52 54 53 55 /// Null map. (a.k.a. DoNothingMap) 54 56 55 57 /// This map can be used if you have to provide a map only for 56 /// its type definitions, or if you have to provide a writable map, 57 /// but data written to it is not required (i.e. it will be sent to 58 /// its type definitions, or if you have to provide a writable map, 59 /// but data written to it is not required (i.e. it will be sent to 58 60 /// <tt>/dev/null</tt>). 59 template<typename K, typename T> 60 class NullMap : public MapBase<K, T> { 61 public: 62 typedef MapBase<K, T> Parent; 63 typedef typename Parent::Key Key; 64 typedef typename Parent::Value Value; 65 61 /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 62 /// 63 /// \sa ConstMap 64 template<typename K, typename V> 65 class NullMap : public MapBase<K, V> { 66 public: 67 typedef MapBase<K, V> Parent; 68 typedef typename Parent::Key Key; 69 typedef typename Parent::Value Value; 70 66 71 /// Gives back a default constructed element. 67 T operator[](const K&) const { return T(); }72 Value operator[](const Key&) const { return Value(); } 68 73 /// Absorbs the value. 69 void set(const K &, const T&) {}70 }; 71 72 /// Returns a \cNullMap class73 74 /// This function just returns a \cNullMap class.75 /// \relates NullMap76 template <typename K, typename V> 74 void set(const Key&, const Value&) {} 75 }; 76 77 /// Returns a \ref NullMap class 78 79 /// This function just returns a \ref NullMap class. 80 /// \relates NullMap 81 template <typename K, typename V> 77 82 NullMap<K, V> nullMap() { 78 83 return NullMap<K, V>(); … … 82 87 /// Constant map. 83 88 84 /// This is a \ref concepts::ReadMap "readable" map which assigns a 85 /// specified value to each key. 86 /// In other aspects it is equivalent to \c NullMap. 87 template<typename K, typename T> 88 class ConstMap : public MapBase<K, T> { 89 /// This \ref concepts::ReadMap "readable map" assigns a specified 90 /// value to each key. 91 /// 92 /// In other aspects it is equivalent to \ref NullMap. 93 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" 94 /// concept, but it absorbs the data written to it. 95 /// 96 /// The simplest way of using this map is through the constMap() 97 /// function. 98 /// 99 /// \sa NullMap 100 /// \sa IdentityMap 101 template<typename K, typename V> 102 class ConstMap : public MapBase<K, V> { 89 103 private: 90 T v; 91 public: 92 93 typedef MapBase<K, T> Parent; 104 V _value; 105 public: 106 typedef MapBase<K, V> Parent; 94 107 typedef typename Parent::Key Key; 95 108 typedef typename Parent::Value Value; … … 98 111 99 112 /// Default constructor. 100 /// The value of the map will be uninitialized. 101 /// (More exactly it will be default constructed.) 113 /// The value of the map will be default constructed. 102 114 ConstMap() {} 103 115 104 116 /// Constructor with specified initial value 105 117 106 118 /// Constructor with specified initial value. 107 /// \param _v is the initial value of the map. 108 ConstMap(const T &_v) : v(_v) {} 109 110 ///\e 111 T operator[](const K&) const { return v; } 112 113 ///\e 114 void setAll(const T &t) { 115 v = t; 116 } 117 118 template<typename T1> 119 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {} 120 }; 121 122 ///Returns a \c ConstMap class 123 124 ///This function just returns a \c ConstMap class. 125 ///\relates ConstMap 126 template<typename K, typename V> 119 /// \param v is the initial value of the map. 120 ConstMap(const Value &v) : _value(v) {} 121 122 /// Gives back the specified value. 123 Value operator[](const Key&) const { return _value; } 124 125 /// Absorbs the value. 126 void set(const Key&, const Value&) {} 127 128 /// Sets the value that is assigned to each key. 129 void setAll(const Value &v) { 130 _value = v; 131 } 132 133 template<typename V1> 134 ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {} 135 }; 136 137 /// Returns a \ref ConstMap class 138 139 /// This function just returns a \ref ConstMap class. 140 /// \relates ConstMap 141 template<typename K, typename V> 127 142 inline ConstMap<K, V> constMap(const V &v) { 128 143 return ConstMap<K, V>(v); … … 131 146 132 147 template<typename T, T v> 133 struct Const { 148 struct Const {}; 134 149 135 150 /// Constant map with inlined constant value. 136 151 137 /// This is a \ref concepts::ReadMap "readable" map which assigns a 138 /// specified value to each key. 139 /// In other aspects it is equivalent to \c NullMap. 152 /// This \ref concepts::ReadMap "readable map" assigns a specified 153 /// value to each key. 154 /// 155 /// In other aspects it is equivalent to \ref NullMap. 156 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" 157 /// concept, but it absorbs the data written to it. 158 /// 159 /// The simplest way of using this map is through the constMap() 160 /// function. 161 /// 162 /// \sa NullMap 163 /// \sa IdentityMap 140 164 template<typename K, typename V, V v> 141 165 class ConstMap<K, Const<V, v> > : public MapBase<K, V> { … … 145 169 typedef typename Parent::Value Value; 146 170 147 ConstMap() { } 148 ///\e 149 V operator[](const K&) const { return v; } 150 ///\e 151 void set(const K&, const V&) { } 152 }; 153 154 ///Returns a \c ConstMap class with inlined value 155 156 ///This function just returns a \c ConstMap class with inlined value. 157 ///\relates ConstMap 158 template<typename K, typename V, V v> 171 /// Constructor. 172 ConstMap() {} 173 174 /// Gives back the specified value. 175 Value operator[](const Key&) const { return v; } 176 177 /// Absorbs the value. 178 void set(const Key&, const Value&) {} 179 }; 180 181 /// Returns a \ref ConstMap class with inlined constant value 182 183 /// This function just returns a \ref ConstMap class with inlined 184 /// constant value. 185 /// \relates ConstMap 186 template<typename K, typename V, V v> 159 187 inline ConstMap<K, Const<V, v> > constMap() { 160 188 return ConstMap<K, Const<V, v> >(); 161 189 } 162 190 163 ///Map based on \c std::map 164 165 ///This is essentially a wrapper for \c std::map with addition that 166 ///you can specify a default value different from \c Value(). 167 ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept. 168 template <typename K, typename T, typename Compare = std::less<K> > 169 class StdMap : public MapBase<K, T> { 170 template <typename K1, typename T1, typename C1> 171 friend class StdMap; 172 public: 173 174 typedef MapBase<K, T> Parent; 175 ///Key type 176 typedef typename Parent::Key Key; 177 ///Value type 178 typedef typename Parent::Value Value; 179 ///Reference Type 180 typedef T& Reference; 181 ///Const reference type 182 typedef const T& ConstReference; 191 192 /// Identity map. 193 194 /// This \ref concepts::ReadMap "readonly map" gives back the given 195 /// key as value without any modification. 196 /// 197 /// \sa ConstMap 198 template <typename T> 199 class IdentityMap : public MapBase<T, T> { 200 public: 201 typedef MapBase<T, T> Parent; 202 typedef typename Parent::Key Key; 203 typedef typename Parent::Value Value; 204 205 /// Gives back the given value without any modification. 206 Value operator[](const Key &k) const { 207 return k; 208 } 209 }; 210 211 /// Returns an \ref IdentityMap class 212 213 /// This function just returns an \ref IdentityMap class. 214 /// \relates IdentityMap 215 template<typename T> 216 inline IdentityMap<T> identityMap() { 217 return IdentityMap<T>(); 218 } 219 220 221 /// \brief Map for storing values for integer keys from the range 222 /// <tt>[0..size1]</tt>. 223 /// 224 /// This map is essentially a wrapper for \c std::vector. It assigns 225 /// values to integer keys from the range <tt>[0..size1]</tt>. 226 /// It can be used with some data structures, for example 227 /// \ref UnionFind, \ref BinHeap, when the used items are small 228 /// integers. This map conforms the \ref concepts::ReferenceMap 229 /// "ReferenceMap" concept. 230 /// 231 /// The simplest way of using this map is through the rangeMap() 232 /// function. 233 template <typename V> 234 class RangeMap : public MapBase<int, V> { 235 template <typename V1> 236 friend class RangeMap; 237 private: 238 239 typedef std::vector<V> Vector; 240 Vector _vector; 241 242 public: 243 244 typedef MapBase<int, V> Parent; 245 /// Key type 246 typedef typename Parent::Key Key; 247 /// Value type 248 typedef typename Parent::Value Value; 249 /// Reference type 250 typedef typename Vector::reference Reference; 251 /// Const reference type 252 typedef typename Vector::const_reference ConstReference; 183 253 184 254 typedef True ReferenceMapTag; 185 255 256 public: 257 258 /// Constructor with specified default value. 259 RangeMap(int size = 0, const Value &value = Value()) 260 : _vector(size, value) {} 261 262 /// Constructs the map from an appropriate \c std::vector. 263 template <typename V1> 264 RangeMap(const std::vector<V1>& vector) 265 : _vector(vector.begin(), vector.end()) {} 266 267 /// Constructs the map from another \ref RangeMap. 268 template <typename V1> 269 RangeMap(const RangeMap<V1> &c) 270 : _vector(c._vector.begin(), c._vector.end()) {} 271 272 /// Returns the size of the map. 273 int size() { 274 return _vector.size(); 275 } 276 277 /// Resizes the map. 278 279 /// Resizes the underlying \c std::vector container, so changes the 280 /// keyset of the map. 281 /// \param size The new size of the map. The new keyset will be the 282 /// range <tt>[0..size1]</tt>. 283 /// \param value The default value to assign to the new keys. 284 void resize(int size, const Value &value = Value()) { 285 _vector.resize(size, value); 286 } 287 186 288 private: 187 188 typedef std::map<K, T, Compare> Map; 289 290 RangeMap& operator=(const RangeMap&); 291 292 public: 293 294 ///\e 295 Reference operator[](const Key &k) { 296 return _vector[k]; 297 } 298 299 ///\e 300 ConstReference operator[](const Key &k) const { 301 return _vector[k]; 302 } 303 304 ///\e 305 void set(const Key &k, const Value &v) { 306 _vector[k] = v; 307 } 308 }; 309 310 /// Returns a \ref RangeMap class 311 312 /// This function just returns a \ref RangeMap class. 313 /// \relates RangeMap 314 template<typename V> 315 inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) { 316 return RangeMap<V>(size, value); 317 } 318 319 /// \brief Returns a \ref RangeMap class created from an appropriate 320 /// \c std::vector 321 322 /// This function just returns a \ref RangeMap class created from an 323 /// appropriate \c std::vector. 324 /// \relates RangeMap 325 template<typename V> 326 inline RangeMap<V> rangeMap(const std::vector<V> &vector) { 327 return RangeMap<V>(vector); 328 } 329 330 331 /// Map type based on \c std::map 332 333 /// This map is essentially a wrapper for \c std::map with addition 334 /// that you can specify a default value for the keys that are not 335 /// stored actually. This value can be different from the default 336 /// contructed value (i.e. \c %Value()). 337 /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap" 338 /// concept. 339 /// 340 /// This map is useful if a default value should be assigned to most of 341 /// the keys and different values should be assigned only to a few 342 /// keys (i.e. the map is "sparse"). 343 /// The name of this type also refers to this important usage. 344 /// 345 /// Apart form that this map can be used in many other cases since it 346 /// is based on \c std::map, which is a general associative container. 347 /// However keep in mind that it is usually not as efficient as other 348 /// maps. 349 /// 350 /// The simplest way of using this map is through the sparseMap() 351 /// function. 352 template <typename K, typename V, typename Compare = std::less<K> > 353 class SparseMap : public MapBase<K, V> { 354 template <typename K1, typename V1, typename C1> 355 friend class SparseMap; 356 public: 357 358 typedef MapBase<K, V> Parent; 359 /// Key type 360 typedef typename Parent::Key Key; 361 /// Value type 362 typedef typename Parent::Value Value; 363 /// Reference type 364 typedef Value& Reference; 365 /// Const reference type 366 typedef const Value& ConstReference; 367 368 typedef True ReferenceMapTag; 369 370 private: 371 372 typedef std::map<K, V, Compare> Map; 373 Map _map; 189 374 Value _value; 190 Map _map; 191 192 public: 193 194 /// Constructor with specified default value 195 StdMap(const T& value = T()) : _value(value) {} 196 /// \brief Constructs the map from an appropriate \c std::map, and 375 376 public: 377 378 /// \brief Constructor with specified default value. 379 SparseMap(const Value &value = Value()) : _value(value) {} 380 /// \brief Constructs the map from an appropriate \c std::map, and 197 381 /// explicitly specifies a default value. 198 template <typename T1, typename Comp1> 199 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 382 template <typename V1, typename Comp1> 383 SparseMap(const std::map<Key, V1, Comp1> &map, 384 const Value &value = Value()) 200 385 : _map(map.begin(), map.end()), _value(value) {} 201 202 /// \brief Constructs a map from an other \ref StdMap.203 template<typename T1, typename Comp1>204 S tdMap(const StdMap<Key, T1, Comp1> &c)386 387 /// \brief Constructs the map from another \ref SparseMap. 388 template<typename V1, typename Comp1> 389 SparseMap(const SparseMap<Key, V1, Comp1> &c) 205 390 : _map(c._map.begin(), c._map.end()), _value(c._value) {} 206 391 207 392 private: 208 393 209 S tdMap& operator=(const StdMap&);394 SparseMap& operator=(const SparseMap&); 210 395 211 396 public: … … 220 405 } 221 406 222 /// \e407 ///\e 223 408 ConstReference operator[](const Key &k) const { 224 409 typename Map::const_iterator it = _map.find(k); … … 229 414 } 230 415 231 /// \e232 void set(const Key &k, const T &t) {416 ///\e 417 void set(const Key &k, const Value &v) { 233 418 typename Map::iterator it = _map.lower_bound(k); 234 419 if (it != _map.end() && !_map.key_comp()(k, it>first)) 235 it>second = t;420 it>second = v; 236 421 else 237 _map.insert(it, std::make_pair(k, t));422 _map.insert(it, std::make_pair(k, v)); 238 423 } 239 424 240 /// 241 void setAll(const T &t) {242 _value = t;425 ///\e 426 void setAll(const Value &v) { 427 _value = v; 243 428 _map.clear(); 244 }245 246 };247 248 ///Returns a \c StdMap class249 250 ///This function just returns a \c StdMap class with specified251 ///default value.252 ///\relates StdMap253 template<typename K, typename V, typename Compare>254 inline StdMap<K, V, Compare> stdMap(const V& value = V()) {255 return StdMap<K, V, Compare>(value);256 }257 258 ///Returns a \c StdMap class259 260 ///This function just returns a \c StdMap class with specified261 ///default value.262 ///\relates StdMap263 template<typename K, typename V>264 inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {265 return StdMap<K, V, std::less<K> >(value);266 }267 268 ///Returns a \c StdMap class created from an appropriate std::map269 270 ///This function just returns a \c StdMap class created from an271 ///appropriate std::map.272 ///\relates StdMap273 template<typename K, typename V, typename Compare>274 inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,275 const V& value = V() ) {276 return StdMap<K, V, Compare>(map, value);277 }278 279 ///Returns a \c StdMap class created from an appropriate std::map280 281 ///This function just returns a \c StdMap class created from an282 ///appropriate std::map.283 ///\relates StdMap284 template<typename K, typename V>285 inline StdMap<K, V, std::less<K> > stdMap( const std::map<K, V, std::less<K> > &map,286 const V& value = V() ) {287 return StdMap<K, V, std::less<K> >(map, value);288 }289 290 /// \brief Map for storing values for keys from the range <tt>[0..size1]</tt>291 ///292 /// This map has the <tt>[0..size1]</tt> keyset and the values293 /// are stored in a \c std::vector<T> container. It can be used with294 /// some data structures, for example \c UnionFind, \c BinHeap, when295 /// the used items are small integer numbers.296 /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.297 ///298 /// \todo Revise its name299 template <typename T>300 class IntegerMap : public MapBase<int, T> {301 302 template <typename T1>303 friend class IntegerMap;304 305 public:306 307 typedef MapBase<int, T> Parent;308 ///\e309 typedef typename Parent::Key Key;310 ///\e311 typedef typename Parent::Value Value;312 ///\e313 typedef T& Reference;314 ///\e315 typedef const T& ConstReference;316 317 typedef True ReferenceMapTag;318 319 private:320 321 typedef std::vector<T> Vector;322 Vector _vector;323 324 public:325 326 /// Constructor with specified default value327 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}328 329 /// \brief Constructs the map from an appropriate \c std::vector.330 template <typename T1>331 IntegerMap(const std::vector<T1>& vector)332 : _vector(vector.begin(), vector.end()) {}333 334 /// \brief Constructs a map from an other \ref IntegerMap.335 template <typename T1>336 IntegerMap(const IntegerMap<T1> &c)337 : _vector(c._vector.begin(), c._vector.end()) {}338 339 /// \brief Resize the container340 void resize(int size, const T& value = T()) {341 _vector.resize(size, value);342 429 } 343 344 private: 345 346 IntegerMap& operator=(const IntegerMap&); 347 348 public: 349 350 ///\e 351 Reference operator[](Key k) { 352 return _vector[k]; 353 } 354 355 /// \e 356 ConstReference operator[](Key k) const { 357 return _vector[k]; 358 } 359 360 /// \e 361 void set(const Key &k, const T& t) { 362 _vector[k] = t; 363 } 364 365 }; 366 367 ///Returns an \c IntegerMap class 368 369 ///This function just returns an \c IntegerMap class. 370 ///\relates IntegerMap 371 template<typename T> 372 inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) { 373 return IntegerMap<T>(size, value); 430 }; 431 432 /// Returns a \ref SparseMap class 433 434 /// This function just returns a \ref SparseMap class with specified 435 /// default value. 436 /// \relates SparseMap 437 template<typename K, typename V, typename Compare> 438 inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) { 439 return SparseMap<K, V, Compare>(value); 440 } 441 442 template<typename K, typename V> 443 inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) { 444 return SparseMap<K, V, std::less<K> >(value); 445 } 446 447 /// \brief Returns a \ref SparseMap class created from an appropriate 448 /// \c std::map 449 450 /// This function just returns a \ref SparseMap class created from an 451 /// appropriate \c std::map. 452 /// \relates SparseMap 453 template<typename K, typename V, typename Compare> 454 inline SparseMap<K, V, Compare> 455 sparseMap(const std::map<K, V, Compare> &map, const V& value = V()) 456 { 457 return SparseMap<K, V, Compare>(map, value); 374 458 } 375 459 … … 379 463 /// @{ 380 464 381 /// \brief Identity map. 382 /// 383 /// This map gives back the given key as value without any 384 /// modification. 385 template <typename T> 386 class IdentityMap : public MapBase<T, T> { 387 public: 388 typedef MapBase<T, T> Parent; 389 typedef typename Parent::Key Key; 390 typedef typename Parent::Value Value; 391 392 /// \e 393 const T& operator[](const T& t) const { 394 return t; 395 } 396 }; 397 398 ///Returns an \c IdentityMap class 399 400 ///This function just returns an \c IdentityMap class. 401 ///\relates IdentityMap 402 template<typename T> 403 inline IdentityMap<T> identityMap() { 404 return IdentityMap<T>(); 405 } 406 407 408 ///\brief Convert the \c Value of a map to another type using 409 ///the default conversion. 410 /// 411 ///This \ref concepts::ReadMap "read only map" 412 ///converts the \c Value of a map to type \c T. 413 ///Its \c Key is inherited from \c M. 414 template <typename M, typename T> 415 class ConvertMap : public MapBase<typename M::Key, T> { 416 const M& m; 417 public: 418 typedef MapBase<typename M::Key, T> Parent; 419 typedef typename Parent::Key Key; 420 typedef typename Parent::Value Value; 421 422 ///Constructor 423 424 ///Constructor. 425 ///\param _m is the underlying map. 426 ConvertMap(const M &_m) : m(_m) {}; 427 428 ///\e 429 Value operator[](const Key& k) const {return m[k];} 430 }; 431 432 ///Returns a \c ConvertMap class 433 434 ///This function just returns a \c ConvertMap class. 435 ///\relates ConvertMap 436 template<typename T, typename M> 437 inline ConvertMap<M, T> convertMap(const M &m) { 438 return ConvertMap<M, T>(m); 439 } 440 441 ///Simple wrapping of a map 442 443 ///This \ref concepts::ReadMap "read only map" returns the simple 444 ///wrapping of the given map. Sometimes the reference maps cannot be 445 ///combined with simple read maps. This map adaptor wraps the given 446 ///map to simple read map. 447 /// 448 ///\sa SimpleWriteMap 449 /// 450 /// \todo Revise the misleading name 451 template<typename M> 452 class SimpleMap : public MapBase<typename M::Key, typename M::Value> { 453 const M& m; 454 465 /// Composition of two maps 466 467 /// This \ref concepts::ReadMap "readonly map" returns the 468 /// composition of two given maps. That is to say, if \c m1 is of 469 /// type \c M1 and \c m2 is of \c M2, then for 470 /// \code 471 /// ComposeMap<M1, M2> cm(m1,m2); 472 /// \endcode 473 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>. 474 /// 475 /// The \c Key type of the map is inherited from \c M2 and the 476 /// \c Value type is from \c M1. 477 /// \c M2::Value must be convertible to \c M1::Key. 478 /// 479 /// The simplest way of using this map is through the composeMap() 480 /// function. 481 /// 482 /// \sa CombineMap 483 /// 484 /// \todo Check the requirements. 485 template <typename M1, typename M2> 486 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> { 487 const M1 &_m1; 488 const M2 &_m2; 489 public: 490 typedef MapBase<typename M2::Key, typename M1::Value> Parent; 491 typedef typename Parent::Key Key; 492 typedef typename Parent::Value Value; 493 494 /// Constructor 495 ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 496 497 /// \e 498 typename MapTraits<M1>::ConstReturnValue 499 operator[](const Key &k) const { return _m1[_m2[k]]; } 500 }; 501 502 /// Returns a \ref ComposeMap class 503 504 /// This function just returns a \ref ComposeMap class. 505 /// 506 /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is 507 /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt> 508 /// will be equal to <tt>m1[m2[x]]</tt>. 509 /// 510 /// \relates ComposeMap 511 template <typename M1, typename M2> 512 inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) { 513 return ComposeMap<M1, M2>(m1, m2); 514 } 515 516 517 /// Combination of two maps using an STL (binary) functor. 518 519 /// This \ref concepts::ReadMap "readonly map" takes two maps and a 520 /// binary functor and returns the combination of the two given maps 521 /// using the functor. 522 /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2 523 /// and \c f is of \c F, then for 524 /// \code 525 /// CombineMap<M1,M2,F,V> cm(m1,m2,f); 526 /// \endcode 527 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>. 528 /// 529 /// The \c Key type of the map is inherited from \c M1 (\c M1::Key 530 /// must be convertible to \c M2::Key) and the \c Value type is \c V. 531 /// \c M2::Value and \c M1::Value must be convertible to the 532 /// corresponding input parameter of \c F and the return type of \c F 533 /// must be convertible to \c V. 534 /// 535 /// The simplest way of using this map is through the combineMap() 536 /// function. 537 /// 538 /// \sa ComposeMap 539 /// 540 /// \todo Check the requirements. 541 template<typename M1, typename M2, typename F, 542 typename V = typename F::result_type> 543 class CombineMap : public MapBase<typename M1::Key, V> { 544 const M1 &_m1; 545 const M2 &_m2; 546 F _f; 547 public: 548 typedef MapBase<typename M1::Key, V> Parent; 549 typedef typename Parent::Key Key; 550 typedef typename Parent::Value Value; 551 552 /// Constructor 553 CombineMap(const M1 &m1, const M2 &m2, const F &f = F()) 554 : _m1(m1), _m2(m2), _f(f) {} 555 /// \e 556 Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); } 557 }; 558 559 /// Returns a \ref CombineMap class 560 561 /// This function just returns a \ref CombineMap class. 562 /// 563 /// For example, if \c m1 and \c m2 are both maps with \c double 564 /// values, then 565 /// \code 566 /// combineMap(m1,m2,std::plus<double>()) 567 /// \endcode 568 /// is equivalent to 569 /// \code 570 /// addMap(m1,m2) 571 /// \endcode 572 /// 573 /// This function is specialized for adaptable binary function 574 /// classes and C++ functions. 575 /// 576 /// \relates CombineMap 577 template<typename M1, typename M2, typename F, typename V> 578 inline CombineMap<M1, M2, F, V> 579 combineMap(const M1 &m1, const M2 &m2, const F &f) { 580 return CombineMap<M1, M2, F, V>(m1,m2,f); 581 } 582 583 template<typename M1, typename M2, typename F> 584 inline CombineMap<M1, M2, F, typename F::result_type> 585 combineMap(const M1 &m1, const M2 &m2, const F &f) { 586 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f); 587 } 588 589 template<typename M1, typename M2, typename K1, typename K2, typename V> 590 inline CombineMap<M1, M2, V (*)(K1, K2), V> 591 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { 592 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f); 593 } 594 595 596 /// Converts an STL style (unary) functor to a map 597 598 /// This \ref concepts::ReadMap "readonly map" returns the value 599 /// of a given functor. Actually, it just wraps the functor and 600 /// provides the \c Key and \c Value typedefs. 601 /// 602 /// Template parameters \c K and \c V will become its \c Key and 603 /// \c Value. In most cases they have to be given explicitly because 604 /// a functor typically does not provide \c argument_type and 605 /// \c result_type typedefs. 606 /// Parameter \c F is the type of the used functor. 607 /// 608 /// The simplest way of using this map is through the functorToMap() 609 /// function. 610 /// 611 /// \sa MapToFunctor 612 template<typename F, 613 typename K = typename F::argument_type, 614 typename V = typename F::result_type> 615 class FunctorToMap : public MapBase<K, V> { 616 const F &_f; 617 public: 618 typedef MapBase<K, V> Parent; 619 typedef typename Parent::Key Key; 620 typedef typename Parent::Value Value; 621 622 /// Constructor 623 FunctorToMap(const F &f = F()) : _f(f) {} 624 /// \e 625 Value operator[](const Key &k) const { return _f(k); } 626 }; 627 628 /// Returns a \ref FunctorToMap class 629 630 /// This function just returns a \ref FunctorToMap class. 631 /// 632 /// This function is specialized for adaptable binary function 633 /// classes and C++ functions. 634 /// 635 /// \relates FunctorToMap 636 template<typename K, typename V, typename F> 637 inline FunctorToMap<F, K, V> functorToMap(const F &f) { 638 return FunctorToMap<F, K, V>(f); 639 } 640 641 template <typename F> 642 inline FunctorToMap<F, typename F::argument_type, typename F::result_type> 643 functorToMap(const F &f) 644 { 645 return FunctorToMap<F, typename F::argument_type, 646 typename F::result_type>(f); 647 } 648 649 template <typename K, typename V> 650 inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) { 651 return FunctorToMap<V (*)(K), K, V>(f); 652 } 653 654 655 /// Converts a map to an STL style (unary) functor 656 657 /// This class converts a map to an STL style (unary) functor. 658 /// That is it provides an <tt>operator()</tt> to read its values. 659 /// 660 /// For the sake of convenience it also works as a usual 661 /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt> 662 /// and the \c Key and \c Value typedefs also exist. 663 /// 664 /// The simplest way of using this map is through the mapToFunctor() 665 /// function. 666 /// 667 ///\sa FunctorToMap 668 template <typename M> 669 class MapToFunctor : public MapBase<typename M::Key, typename M::Value> { 670 const M &_m; 455 671 public: 456 672 typedef MapBase<typename M::Key, typename M::Value> Parent; … … 458 674 typedef typename Parent::Value Value; 459 675 460 ///Constructor 461 SimpleMap(const M &_m) : m(_m) {}; 462 ///\e 463 Value operator[](Key k) const {return m[k];} 464 }; 465 466 ///Returns a \c SimpleMap class 467 468 ///This function just returns a \c SimpleMap class. 469 ///\relates SimpleMap 676 typedef typename Parent::Key argument_type; 677 typedef typename Parent::Value result_type; 678 679 /// Constructor 680 MapToFunctor(const M &m) : _m(m) {} 681 /// \e 682 Value operator()(const Key &k) const { return _m[k]; } 683 /// \e 684 Value operator[](const Key &k) const { return _m[k]; } 685 }; 686 687 /// Returns a \ref MapToFunctor class 688 689 /// This function just returns a \ref MapToFunctor class. 690 /// \relates MapToFunctor 470 691 template<typename M> 471 inline SimpleMap<M> simpleMap(const M &m) { 472 return SimpleMap<M>(m); 473 } 474 475 ///Simple writable wrapping of a map 476 477 ///This \ref concepts::ReadWriteMap "readwrite map" returns the simple 478 ///wrapping of the given map. Sometimes the reference maps cannot be 479 ///combined with simple readwrite maps. This map adaptor wraps the 480 ///given map to simple readwrite map. 481 /// 482 ///\sa SimpleMap 483 /// 484 /// \todo Revise the misleading name 485 template<typename M> 486 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> { 487 M& m; 488 489 public: 490 typedef MapBase<typename M::Key, typename M::Value> Parent; 491 typedef typename Parent::Key Key; 492 typedef typename Parent::Value Value; 493 494 ///Constructor 495 SimpleWriteMap(M &_m) : m(_m) {}; 496 ///\e 497 Value operator[](Key k) const {return m[k];} 498 ///\e 499 void set(Key k, const Value& c) { m.set(k, c); } 500 }; 501 502 ///Returns a \c SimpleWriteMap class 503 504 ///This function just returns a \c SimpleWriteMap class. 505 ///\relates SimpleWriteMap 506 template<typename M> 507 inline SimpleWriteMap<M> simpleWriteMap(M &m) { 508 return SimpleWriteMap<M>(m); 509 } 510 511 ///Sum of two maps 512 513 ///This \ref concepts::ReadMap "read only map" returns the sum of the two 514 ///given maps. 515 ///Its \c Key and \c Value are inherited from \c M1. 516 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 517 template<typename M1, typename M2> 692 inline MapToFunctor<M> mapToFunctor(const M &m) { 693 return MapToFunctor<M>(m); 694 } 695 696 697 /// \brief Map adaptor to convert the \c Value type of a map to 698 /// another type using the default conversion. 699 700 /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap 701 /// "readable map" to another type using the default conversion. 702 /// The \c Key type of it is inherited from \c M and the \c Value 703 /// type is \c V. 704 /// This type conforms the \ref concepts::ReadMap "ReadMap" concept. 705 /// 706 /// The simplest way of using this map is through the convertMap() 707 /// function. 708 template <typename M, typename V> 709 class ConvertMap : public MapBase<typename M::Key, V> { 710 const M &_m; 711 public: 712 typedef MapBase<typename M::Key, V> Parent; 713 typedef typename Parent::Key Key; 714 typedef typename Parent::Value Value; 715 716 /// Constructor 717 718 /// Constructor. 719 /// \param m The underlying map. 720 ConvertMap(const M &m) : _m(m) {} 721 722 /// \e 723 Value operator[](const Key &k) const { return _m[k]; } 724 }; 725 726 /// Returns a \ref ConvertMap class 727 728 /// This function just returns a \ref ConvertMap class. 729 /// \relates ConvertMap 730 template<typename V, typename M> 731 inline ConvertMap<M, V> convertMap(const M &map) { 732 return ConvertMap<M, V>(map); 733 } 734 735 736 /// Applies all map setting operations to two maps 737 738 /// This map has two \ref concepts::WriteMap "writable map" parameters 739 /// and each write request will be passed to both of them. 740 /// If \c M1 is also \ref concepts::ReadMap "readable", then the read 741 /// operations will return the corresponding values of \c M1. 742 /// 743 /// The \c Key and \c Value types are inherited from \c M1. 744 /// The \c Key and \c Value of \c M2 must be convertible from those 745 /// of \c M1. 746 /// 747 /// The simplest way of using this map is through the forkMap() 748 /// function. 749 template<typename M1, typename M2> 750 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { 751 M1 &_m1; 752 M2 &_m2; 753 public: 754 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 755 typedef typename Parent::Key Key; 756 typedef typename Parent::Value Value; 757 758 /// Constructor 759 ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {} 760 /// Returns the value associated with the given key in the first map. 761 Value operator[](const Key &k) const { return _m1[k]; } 762 /// Sets the value associated with the given key in both maps. 763 void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); } 764 }; 765 766 /// Returns a \ref ForkMap class 767 768 /// This function just returns a \ref ForkMap class. 769 /// \relates ForkMap 770 template <typename M1, typename M2> 771 inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) { 772 return ForkMap<M1,M2>(m1,m2); 773 } 774 775 776 /// Sum of two maps 777 778 /// This \ref concepts::ReadMap "readonly map" returns the sum 779 /// of the values of the two given maps. 780 /// Its \c Key and \c Value types are inherited from \c M1. 781 /// The \c Key and \c Value of \c M2 must be convertible to those of 782 /// \c M1. 783 /// 784 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 785 /// \code 786 /// AddMap<M1,M2> am(m1,m2); 787 /// \endcode 788 /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>. 789 /// 790 /// The simplest way of using this map is through the addMap() 791 /// function. 792 /// 793 /// \sa SubMap, MulMap, DivMap 794 /// \sa ShiftMap, ShiftWriteMap 795 template<typename M1, typename M2> 518 796 class AddMap : public MapBase<typename M1::Key, typename M1::Value> { 519 const M1& m1; 520 const M2& m2; 521 797 const M1 &_m1; 798 const M2 &_m2; 522 799 public: 523 800 typedef MapBase<typename M1::Key, typename M1::Value> Parent; … … 525 802 typedef typename Parent::Value Value; 526 803 527 ///Constructor 528 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 529 ///\e 530 Value operator[](Key k) const {return m1[k]+m2[k];} 531 }; 532 533 ///Returns an \c AddMap class 534 535 ///This function just returns an \c AddMap class. 536 ///\todo Extend the documentation: how to call these type of functions? 537 /// 538 ///\relates AddMap 539 template<typename M1, typename M2> 540 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) { 804 /// Constructor 805 AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 806 /// \e 807 Value operator[](const Key &k) const { return _m1[k]+_m2[k]; } 808 }; 809 810 /// Returns an \ref AddMap class 811 812 /// This function just returns an \ref AddMap class. 813 /// 814 /// For example, if \c m1 and \c m2 are both maps with \c double 815 /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to 816 /// <tt>m1[x]+m2[x]</tt>. 817 /// 818 /// \relates AddMap 819 template<typename M1, typename M2> 820 inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) { 541 821 return AddMap<M1, M2>(m1,m2); 542 822 } 543 823 544 ///Shift a map with a constant. 545 546 ///This \ref concepts::ReadMap "read only map" returns the sum of the 547 ///given map and a constant value. 548 ///Its \c Key and \c Value are inherited from \c M. 549 /// 550 ///Actually, 551 ///\code 552 /// ShiftMap<X> sh(x,v); 553 ///\endcode 554 ///is equivalent to 555 ///\code 556 /// ConstMap<X::Key, X::Value> c_tmp(v); 557 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v); 558 ///\endcode 559 /// 560 ///\sa ShiftWriteMap 561 template<typename M, typename C = typename M::Value> 562 class ShiftMap : public MapBase<typename M::Key, typename M::Value> { 563 const M& m; 564 C v; 565 public: 566 typedef MapBase<typename M::Key, typename M::Value> Parent; 567 typedef typename Parent::Key Key; 568 typedef typename Parent::Value Value; 569 570 ///Constructor 571 572 ///Constructor. 573 ///\param _m is the undelying map. 574 ///\param _v is the shift value. 575 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; 576 ///\e 577 Value operator[](Key k) const {return m[k] + v;} 578 }; 579 580 ///Shift a map with a constant (ReadWrite version). 581 582 ///This \ref concepts::ReadWriteMap "readwrite map" returns the sum of the 583 ///given map and a constant value. It makes also possible to write the map. 584 ///Its \c Key and \c Value are inherited from \c M. 585 /// 586 ///\sa ShiftMap 587 template<typename M, typename C = typename M::Value> 588 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> { 589 M& m; 590 C v; 591 public: 592 typedef MapBase<typename M::Key, typename M::Value> Parent; 593 typedef typename Parent::Key Key; 594 typedef typename Parent::Value Value; 595 596 ///Constructor 597 598 ///Constructor. 599 ///\param _m is the undelying map. 600 ///\param _v is the shift value. 601 ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {}; 602 /// \e 603 Value operator[](Key k) const {return m[k] + v;} 604 /// \e 605 void set(Key k, const Value& c) { m.set(k, c  v); } 606 }; 607 608 ///Returns a \c ShiftMap class 609 610 ///This function just returns a \c ShiftMap class. 611 ///\relates ShiftMap 612 template<typename M, typename C> 613 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) { 614 return ShiftMap<M, C>(m,v); 615 } 616 617 ///Returns a \c ShiftWriteMap class 618 619 ///This function just returns a \c ShiftWriteMap class. 620 ///\relates ShiftWriteMap 621 template<typename M, typename C> 622 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) { 623 return ShiftWriteMap<M, C>(m,v); 624 } 625 626 ///Difference of two maps 627 628 ///This \ref concepts::ReadMap "read only map" returns the difference 629 ///of the values of the two given maps. 630 ///Its \c Key and \c Value are inherited from \c M1. 631 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 632 /// 633 /// \todo Revise the misleading name 634 template<typename M1, typename M2> 824 825 /// Difference of two maps 826 827 /// This \ref concepts::ReadMap "readonly map" returns the difference 828 /// of the values of the two given maps. 829 /// Its \c Key and \c Value types are inherited from \c M1. 830 /// The \c Key and \c Value of \c M2 must be convertible to those of 831 /// \c M1. 832 /// 833 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 834 /// \code 835 /// SubMap<M1,M2> sm(m1,m2); 836 /// \endcode 837 /// <tt>sm[x]</tt> will be equal to <tt>m1[x]m2[x]</tt>. 838 /// 839 /// The simplest way of using this map is through the subMap() 840 /// function. 841 /// 842 /// \sa AddMap, MulMap, DivMap 843 template<typename M1, typename M2> 635 844 class SubMap : public MapBase<typename M1::Key, typename M1::Value> { 636 const M1 &m1;637 const M2 &m2;845 const M1 &_m1; 846 const M2 &_m2; 638 847 public: 639 848 typedef MapBase<typename M1::Key, typename M1::Value> Parent; … … 641 850 typedef typename Parent::Value Value; 642 851 643 ///Constructor 644 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 645 /// \e 646 Value operator[](Key k) const {return m1[k]m2[k];} 647 }; 648 649 ///Returns a \c SubMap class 650 651 ///This function just returns a \c SubMap class. 652 /// 653 ///\relates SubMap 654 template<typename M1, typename M2> 852 /// Constructor 853 SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 854 /// \e 855 Value operator[](const Key &k) const { return _m1[k]_m2[k]; } 856 }; 857 858 /// Returns a \ref SubMap class 859 860 /// This function just returns a \ref SubMap class. 861 /// 862 /// For example, if \c m1 and \c m2 are both maps with \c double 863 /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to 864 /// <tt>m1[x]m2[x]</tt>. 865 /// 866 /// \relates SubMap 867 template<typename M1, typename M2> 655 868 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) { 656 return SubMap<M1, M2>(m1, m2); 657 } 658 659 ///Product of two maps 660 661 ///This \ref concepts::ReadMap "read only map" returns the product of the 662 ///values of the two given maps. 663 ///Its \c Key and \c Value are inherited from \c M1. 664 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 665 template<typename M1, typename M2> 869 return SubMap<M1, M2>(m1,m2); 870 } 871 872 873 /// Product of two maps 874 875 /// This \ref concepts::ReadMap "readonly map" returns the product 876 /// of the values of the two given maps. 877 /// Its \c Key and \c Value types are inherited from \c M1. 878 /// The \c Key and \c Value of \c M2 must be convertible to those of 879 /// \c M1. 880 /// 881 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 882 /// \code 883 /// MulMap<M1,M2> mm(m1,m2); 884 /// \endcode 885 /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>. 886 /// 887 /// The simplest way of using this map is through the mulMap() 888 /// function. 889 /// 890 /// \sa AddMap, SubMap, DivMap 891 /// \sa ScaleMap, ScaleWriteMap 892 template<typename M1, typename M2> 666 893 class MulMap : public MapBase<typename M1::Key, typename M1::Value> { 667 const M1 &m1;668 const M2 &m2;894 const M1 &_m1; 895 const M2 &_m2; 669 896 public: 670 897 typedef MapBase<typename M1::Key, typename M1::Value> Parent; … … 672 899 typedef typename Parent::Value Value; 673 900 674 ///Constructor 675 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 676 /// \e 677 Value operator[](Key k) const {return m1[k]*m2[k];} 678 }; 679 680 ///Returns a \c MulMap class 681 682 ///This function just returns a \c MulMap class. 683 ///\relates MulMap 684 template<typename M1, typename M2> 901 /// Constructor 902 MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} 903 /// \e 904 Value operator[](const Key &k) const { return _m1[k]*_m2[k]; } 905 }; 906 907 /// Returns a \ref MulMap class 908 909 /// This function just returns a \ref MulMap class. 910 /// 911 /// For example, if \c m1 and \c m2 are both maps with \c double 912 /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to 913 /// <tt>m1[x]*m2[x]</tt>. 914 /// 915 /// \relates MulMap 916 template<typename M1, typename M2> 685 917 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) { 686 918 return MulMap<M1, M2>(m1,m2); 687 919 } 688 689 ///Scales a map with a constant. 690 691 ///This \ref concepts::ReadMap "read only map" returns the value of the 692 ///given map multiplied from the left side with a constant value. 693 ///Its \c Key and \c Value are inherited from \c M. 694 /// 695 ///Actually, 696 ///\code 697 /// ScaleMap<X> sc(x,v); 698 ///\endcode 699 ///is equivalent to 700 ///\code 701 /// ConstMap<X::Key, X::Value> c_tmp(v); 702 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v); 703 ///\endcode 704 /// 705 ///\sa ScaleWriteMap 706 template<typename M, typename C = typename M::Value> 707 class ScaleMap : public MapBase<typename M::Key, typename M::Value> { 708 const M& m; 709 C v; 710 public: 711 typedef MapBase<typename M::Key, typename M::Value> Parent; 712 typedef typename Parent::Key Key; 713 typedef typename Parent::Value Value; 714 715 ///Constructor 716 717 ///Constructor. 718 ///\param _m is the undelying map. 719 ///\param _v is the scaling value. 720 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; 721 /// \e 722 Value operator[](Key k) const {return v * m[k];} 723 }; 724 725 ///Scales a map with a constant (ReadWrite version). 726 727 ///This \ref concepts::ReadWriteMap "readwrite map" returns the value of the 728 ///given map multiplied from the left side with a constant value. It can 729 ///also be used as write map if the \c / operator is defined between 730 ///\c Value and \c C and the given multiplier is not zero. 731 ///Its \c Key and \c Value are inherited from \c M. 732 /// 733 ///\sa ScaleMap 734 template<typename M, typename C = typename M::Value> 735 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> { 736 M& m; 737 C v; 738 public: 739 typedef MapBase<typename M::Key, typename M::Value> Parent; 740 typedef typename Parent::Key Key; 741 typedef typename Parent::Value Value; 742 743 ///Constructor 744 745 ///Constructor. 746 ///\param _m is the undelying map. 747 ///\param _v is the scaling value. 748 ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {}; 749 /// \e 750 Value operator[](Key k) const {return v * m[k];} 751 /// \e 752 void set(Key k, const Value& c) { m.set(k, c / v);} 753 }; 754 755 ///Returns a \c ScaleMap class 756 757 ///This function just returns a \c ScaleMap class. 758 ///\relates ScaleMap 759 template<typename M, typename C> 760 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) { 761 return ScaleMap<M, C>(m,v); 762 } 763 764 ///Returns a \c ScaleWriteMap class 765 766 ///This function just returns a \c ScaleWriteMap class. 767 ///\relates ScaleWriteMap 768 template<typename M, typename C> 769 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) { 770 return ScaleWriteMap<M, C>(m,v); 771 } 772 773 ///Quotient of two maps 774 775 ///This \ref concepts::ReadMap "read only map" returns the quotient of the 776 ///values of the two given maps. 777 ///Its \c Key and \c Value are inherited from \c M1. 778 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 779 template<typename M1, typename M2> 920 921 922 /// Quotient of two maps 923 924 /// This \ref concepts::ReadMap "readonly map" returns the quotient 925 /// of the values of the two given maps. 926 /// Its \c Key and \c Value types are inherited from \c M1. 927 /// The \c Key and \c Value of \c M2 must be convertible to those of 928 /// \c M1. 929 /// 930 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 931 /// \code 932 /// DivMap<M1,M2> dm(m1,m2); 933 /// \endcode 934 /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>. 935 /// 936 /// The simplest way of using this map is through the divMap() 937 /// function. 938 /// 939 /// \sa AddMap, SubMap, MulMap 940 template<typename M1, typename M2> 780 941 class DivMap : public MapBase<typename M1::Key, typename M1::Value> { 781 const M1 &m1;782 const M2 &m2;942 const M1 &_m1; 943 const M2 &_m2; 783 944 public: 784 945 typedef MapBase<typename M1::Key, typename M1::Value> Parent; … … 786 947 typedef typename Parent::Value Value; 787 948 788 ///Constructor 789 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 790 /// \e 791 Value operator[](Key k) const {return m1[k]/m2[k];} 792 }; 793 794 ///Returns a \c DivMap class 795 796 ///This function just returns a \c DivMap class. 797 ///\relates DivMap 798 template<typename M1, typename M2> 949 /// Constructor 950 DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} 951 /// \e 952 Value operator[](const Key &k) const { return _m1[k]/_m2[k]; } 953 }; 954 955 /// Returns a \ref DivMap class 956 957 /// This function just returns a \ref DivMap class. 958 /// 959 /// For example, if \c m1 and \c m2 are both maps with \c double 960 /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to 961 /// <tt>m1[x]/m2[x]</tt>. 962 /// 963 /// \relates DivMap 964 template<typename M1, typename M2> 799 965 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) { 800 966 return DivMap<M1, M2>(m1,m2); 801 967 } 802 803 ///Composition of two maps 804 805 ///This \ref concepts::ReadMap "read only map" returns the composition of 806 ///two given maps. 807 ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2, 808 ///then for 809 ///\code 810 /// ComposeMap<M1, M2> cm(m1,m2); 811 ///\endcode 812 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>. 813 /// 814 ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1. 815 ///\c M2::Value must be convertible to \c M1::Key. 816 /// 817 ///\sa CombineMap 818 /// 819 ///\todo Check the requirements. 820 template <typename M1, typename M2> 821 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> { 822 const M1& m1; 823 const M2& m2; 824 public: 825 typedef MapBase<typename M2::Key, typename M1::Value> Parent; 826 typedef typename Parent::Key Key; 827 typedef typename Parent::Value Value; 828 829 ///Constructor 830 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 831 832 /// \e 833 834 835 /// \todo Use the MapTraits once it is ported. 836 /// 837 838 //typename MapTraits<M1>::ConstReturnValue 839 typename M1::Value 840 operator[](Key k) const {return m1[m2[k]];} 841 }; 842 843 ///Returns a \c ComposeMap class 844 845 ///This function just returns a \c ComposeMap class. 846 ///\relates ComposeMap 847 template <typename M1, typename M2> 848 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) { 849 return ComposeMap<M1, M2>(m1,m2); 850 } 851 852 ///Combine of two maps using an STL (binary) functor. 853 854 ///Combine of two maps using an STL (binary) functor. 855 /// 856 ///This \ref concepts::ReadMap "read only map" takes two maps and a 857 ///binary functor and returns the composition of the two 858 ///given maps unsing the functor. 859 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2 860 ///and \c f is of \c F, then for 861 ///\code 862 /// CombineMap<M1,M2,F,V> cm(m1,m2,f); 863 ///\endcode 864 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt> 865 /// 866 ///Its \c Key is inherited from \c M1 and its \c Value is \c V. 867 ///\c M2::Value and \c M1::Value must be convertible to the corresponding 868 ///input parameter of \c F and the return type of \c F must be convertible 869 ///to \c V. 870 /// 871 ///\sa ComposeMap 872 /// 873 ///\todo Check the requirements. 874 template<typename M1, typename M2, typename F, 875 typename V = typename F::result_type> 876 class CombineMap : public MapBase<typename M1::Key, V> { 877 const M1& m1; 878 const M2& m2; 879 F f; 880 public: 881 typedef MapBase<typename M1::Key, V> Parent; 882 typedef typename Parent::Key Key; 883 typedef typename Parent::Value Value; 884 885 ///Constructor 886 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F()) 887 : m1(_m1), m2(_m2), f(_f) {}; 888 /// \e 889 Value operator[](Key k) const {return f(m1[k],m2[k]);} 890 }; 891 892 ///Returns a \c CombineMap class 893 894 ///This function just returns a \c CombineMap class. 895 /// 896 ///For example if \c m1 and \c m2 are both \c double valued maps, then 897 ///\code 898 ///combineMap(m1,m2,std::plus<double>()) 899 ///\endcode 900 ///is equivalent to 901 ///\code 902 ///addMap(m1,m2) 903 ///\endcode 904 /// 905 ///This function is specialized for adaptable binary function 906 ///classes and C++ functions. 907 /// 908 ///\relates CombineMap 909 template<typename M1, typename M2, typename F, typename V> 910 inline CombineMap<M1, M2, F, V> 911 combineMap(const M1& m1,const M2& m2, const F& f) { 912 return CombineMap<M1, M2, F, V>(m1,m2,f); 913 } 914 915 template<typename M1, typename M2, typename F> 916 inline CombineMap<M1, M2, F, typename F::result_type> 917 combineMap(const M1& m1, const M2& m2, const F& f) { 918 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f); 919 } 920 921 template<typename M1, typename M2, typename K1, typename K2, typename V> 922 inline CombineMap<M1, M2, V (*)(K1, K2), V> 923 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { 924 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f); 925 } 926 927 ///Negative value of a map 928 929 ///This \ref concepts::ReadMap "read only map" returns the negative 930 ///value of the value returned by the given map. 931 ///Its \c Key and \c Value are inherited from \c M. 932 ///The unary \c  operator must be defined for \c Value, of course. 933 /// 934 ///\sa NegWriteMap 935 template<typename M> 968 969 970 /// Shifts a map with a constant. 971 972 /// This \ref concepts::ReadMap "readonly map" returns the sum of 973 /// the given map and a constant value (i.e. it shifts the map with 974 /// the constant). Its \c Key and \c Value are inherited from \c M. 975 /// 976 /// Actually, 977 /// \code 978 /// ShiftMap<M> sh(m,v); 979 /// \endcode 980 /// is equivalent to 981 /// \code 982 /// ConstMap<M::Key, M::Value> cm(v); 983 /// AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm); 984 /// \endcode 985 /// 986 /// The simplest way of using this map is through the shiftMap() 987 /// function. 988 /// 989 /// \sa ShiftWriteMap 990 template<typename M, typename C = typename M::Value> 991 class ShiftMap : public MapBase<typename M::Key, typename M::Value> { 992 const M &_m; 993 C _v; 994 public: 995 typedef MapBase<typename M::Key, typename M::Value> Parent; 996 typedef typename Parent::Key Key; 997 typedef typename Parent::Value Value; 998 999 /// Constructor 1000 1001 /// Constructor. 1002 /// \param m The undelying map. 1003 /// \param v The constant value. 1004 ShiftMap(const M &m, const C &v) : _m(m), _v(v) {} 1005 /// \e 1006 Value operator[](const Key &k) const { return _m[k]+_v; } 1007 }; 1008 1009 /// Shifts a map with a constant (readwrite version). 1010 1011 /// This \ref concepts::ReadWriteMap "readwrite map" returns the sum 1012 /// of the given map and a constant value (i.e. it shifts the map with 1013 /// the constant). Its \c Key and \c Value are inherited from \c M. 1014 /// It makes also possible to write the map. 1015 /// 1016 /// The simplest way of using this map is through the shiftWriteMap() 1017 /// function. 1018 /// 1019 /// \sa ShiftMap 1020 template<typename M, typename C = typename M::Value> 1021 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> { 1022 M &_m; 1023 C _v; 1024 public: 1025 typedef MapBase<typename M::Key, typename M::Value> Parent; 1026 typedef typename Parent::Key Key; 1027 typedef typename Parent::Value Value; 1028 1029 /// Constructor 1030 1031 /// Constructor. 1032 /// \param m The undelying map. 1033 /// \param v The constant value. 1034 ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {} 1035 /// \e 1036 Value operator[](const Key &k) const { return _m[k]+_v; } 1037 /// \e 1038 void set(const Key &k, const Value &v) { _m.set(k, v_v); } 1039 }; 1040 1041 /// Returns a \ref ShiftMap class 1042 1043 /// This function just returns a \ref ShiftMap class. 1044 /// 1045 /// For example, if \c m is a map with \c double values and \c v is 1046 /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to 1047 /// <tt>m[x]+v</tt>. 1048 /// 1049 /// \relates ShiftMap 1050 template<typename M, typename C> 1051 inline ShiftMap<M, C> shiftMap(const M &m, const C &v) { 1052 return ShiftMap<M, C>(m,v); 1053 } 1054 1055 /// Returns a \ref ShiftWriteMap class 1056 1057 /// This function just returns a \ref ShiftWriteMap class. 1058 /// 1059 /// For example, if \c m is a map with \c double values and \c v is 1060 /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to 1061 /// <tt>m[x]+v</tt>. 1062 /// Moreover it makes also possible to write the map. 1063 /// 1064 /// \relates ShiftWriteMap 1065 template<typename M, typename C> 1066 inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) { 1067 return ShiftWriteMap<M, C>(m,v); 1068 } 1069 1070 1071 /// Scales a map with a constant. 1072 1073 /// This \ref concepts::ReadMap "readonly map" returns the value of 1074 /// the given map multiplied from the left side with a constant value. 1075 /// Its \c Key and \c Value are inherited from \c M. 1076 /// 1077 /// Actually, 1078 /// \code 1079 /// ScaleMap<M> sc(m,v); 1080 /// \endcode 1081 /// is equivalent to 1082 /// \code 1083 /// ConstMap<M::Key, M::Value> cm(v); 1084 /// MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m); 1085 /// \endcode 1086 /// 1087 /// The simplest way of using this map is through the scaleMap() 1088 /// function. 1089 /// 1090 /// \sa ScaleWriteMap 1091 template<typename M, typename C = typename M::Value> 1092 class ScaleMap : public MapBase<typename M::Key, typename M::Value> { 1093 const M &_m; 1094 C _v; 1095 public: 1096 typedef MapBase<typename M::Key, typename M::Value> Parent; 1097 typedef typename Parent::Key Key; 1098 typedef typename Parent::Value Value; 1099 1100 /// Constructor 1101 1102 /// Constructor. 1103 /// \param m The undelying map. 1104 /// \param v The constant value. 1105 ScaleMap(const M &m, const C &v) : _m(m), _v(v) {} 1106 /// \e 1107 Value operator[](const Key &k) const { return _v*_m[k]; } 1108 }; 1109 1110 /// Scales a map with a constant (readwrite version). 1111 1112 /// This \ref concepts::ReadWriteMap "readwrite map" returns the value of 1113 /// the given map multiplied from the left side with a constant value. 1114 /// Its \c Key and \c Value are inherited from \c M. 1115 /// It can also be used as write map if the \c / operator is defined 1116 /// between \c Value and \c C and the given multiplier is not zero. 1117 /// 1118 /// The simplest way of using this map is through the scaleWriteMap() 1119 /// function. 1120 /// 1121 /// \sa ScaleMap 1122 template<typename M, typename C = typename M::Value> 1123 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> { 1124 M &_m; 1125 C _v; 1126 public: 1127 typedef MapBase<typename M::Key, typename M::Value> Parent; 1128 typedef typename Parent::Key Key; 1129 typedef typename Parent::Value Value; 1130 1131 /// Constructor 1132 1133 /// Constructor. 1134 /// \param m The undelying map. 1135 /// \param v The constant value. 1136 ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {} 1137 /// \e 1138 Value operator[](const Key &k) const { return _v*_m[k]; } 1139 /// \e 1140 void set(const Key &k, const Value &v) { _m.set(k, v/_v); } 1141 }; 1142 1143 /// Returns a \ref ScaleMap class 1144 1145 /// This function just returns a \ref ScaleMap class. 1146 /// 1147 /// For example, if \c m is a map with \c double values and \c v is 1148 /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to 1149 /// <tt>v*m[x]</tt>. 1150 /// 1151 /// \relates ScaleMap 1152 template<typename M, typename C> 1153 inline ScaleMap<M, C> scaleMap(const M &m, const C &v) { 1154 return ScaleMap<M, C>(m,v); 1155 } 1156 1157 /// Returns a \ref ScaleWriteMap class 1158 1159 /// This function just returns a \ref ScaleWriteMap class. 1160 /// 1161 /// For example, if \c m is a map with \c double values and \c v is 1162 /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to 1163 /// <tt>v*m[x]</tt>. 1164 /// Moreover it makes also possible to write the map. 1165 /// 1166 /// \relates ScaleWriteMap 1167 template<typename M, typename C> 1168 inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) { 1169 return ScaleWriteMap<M, C>(m,v); 1170 } 1171 1172 1173 /// Negative of a map 1174 1175 /// This \ref concepts::ReadMap "readonly map" returns the negative 1176 /// of the values of the given map (using the unary \c  operator). 1177 /// Its \c Key and \c Value are inherited from \c M. 1178 /// 1179 /// If M::Value is \c int, \c double etc., then 1180 /// \code 1181 /// NegMap<M> neg(m); 1182 /// \endcode 1183 /// is equivalent to 1184 /// \code 1185 /// ScaleMap<M> neg(m,1); 1186 /// \endcode 1187 /// 1188 /// The simplest way of using this map is through the negMap() 1189 /// function. 1190 /// 1191 /// \sa NegWriteMap 1192 template<typename M> 936 1193 class NegMap : public MapBase<typename M::Key, typename M::Value> { 937 const M& m;1194 const M& _m; 938 1195 public: 939 1196 typedef MapBase<typename M::Key, typename M::Value> Parent; … … 941 1198 typedef typename Parent::Value Value; 942 1199 943 ///Constructor 944 NegMap(const M &_m) : m(_m) {}; 945 /// \e 946 Value operator[](Key k) const {return m[k];} 947 }; 948 949 ///Negative value of a map (ReadWrite version) 950 951 ///This \ref concepts::ReadWriteMap "readwrite map" returns the negative 952 ///value of the value returned by the given map. 953 ///Its \c Key and \c Value are inherited from \c M. 954 ///The unary \c  operator must be defined for \c Value, of course. 1200 /// Constructor 1201 NegMap(const M &m) : _m(m) {} 1202 /// \e 1203 Value operator[](const Key &k) const { return _m[k]; } 1204 }; 1205 1206 /// Negative of a map (readwrite version) 1207 1208 /// This \ref concepts::ReadWriteMap "readwrite map" returns the 1209 /// negative of the values of the given map (using the unary \c  1210 /// operator). 1211 /// Its \c Key and \c Value are inherited from \c M. 1212 /// It makes also possible to write the map. 1213 /// 1214 /// If M::Value is \c int, \c double etc., then 1215 /// \code 1216 /// NegWriteMap<M> neg(m); 1217 /// \endcode 1218 /// is equivalent to 1219 /// \code 1220 /// ScaleWriteMap<M> neg(m,1); 1221 /// \endcode 1222 /// 1223 /// The simplest way of using this map is through the negWriteMap() 1224 /// function. 955 1225 /// 956 1226 /// \sa NegMap 957 template<typename M> 1227 template<typename M> 958 1228 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> { 959 M &m;1229 M &_m; 960 1230 public: 961 1231 typedef MapBase<typename M::Key, typename M::Value> Parent; … … 963 1233 typedef typename Parent::Value Value; 964 1234 965 ///Constructor 966 NegWriteMap(M &_m) : m(_m) {}; 967 /// \e 968 Value operator[](Key k) const {return m[k];} 969 /// \e 970 void set(Key k, const Value& v) { m.set(k, v); } 971 }; 972 973 ///Returns a \c NegMap class 974 975 ///This function just returns a \c NegMap class. 976 ///\relates NegMap 977 template <typename M> 1235 /// Constructor 1236 NegWriteMap(M &m) : _m(m) {} 1237 /// \e 1238 Value operator[](const Key &k) const { return _m[k]; } 1239 /// \e 1240 void set(const Key &k, const Value &v) { _m.set(k, v); } 1241 }; 1242 1243 /// Returns a \ref NegMap class 1244 1245 /// This function just returns a \ref NegMap class. 1246 /// 1247 /// For example, if \c m is a map with \c double values, then 1248 /// <tt>negMap(m)[x]</tt> will be equal to <tt>m[x]</tt>. 1249 /// 1250 /// \relates NegMap 1251 template <typename M> 978 1252 inline NegMap<M> negMap(const M &m) { 979 1253 return NegMap<M>(m); 980 1254 } 981 1255 982 ///Returns a \c NegWriteMap class 983 984 ///This function just returns a \c NegWriteMap class. 985 ///\relates NegWriteMap 986 template <typename M> 987 inline NegWriteMap<M> negMap(M &m) { 1256 /// Returns a \ref NegWriteMap class 1257 1258 /// This function just returns a \ref NegWriteMap class. 1259 /// 1260 /// For example, if \c m is a map with \c double values, then 1261 /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>m[x]</tt>. 1262 /// Moreover it makes also possible to write the map. 1263 /// 1264 /// \relates NegWriteMap 1265 template <typename M> 1266 inline NegWriteMap<M> negWriteMap(M &m) { 988 1267 return NegWriteMap<M>(m); 989 1268 } 990 1269 991 ///Absolute value of a map 992 993 ///This \ref concepts::ReadMap "read only map" returns the absolute value 994 ///of the value returned by the given map. 995 ///Its \c Key and \c Value are inherited from \c M. 996 ///\c Value must be comparable to \c 0 and the unary \c  997 ///operator must be defined for it, of course. 998 template<typename M> 1270 1271 /// Absolute value of a map 1272 1273 /// This \ref concepts::ReadMap "readonly map" returns the absolute 1274 /// value of the values of the given map. 1275 /// Its \c Key and \c Value are inherited from \c M. 1276 /// \c Value must be comparable to \c 0 and the unary \c  1277 /// operator must be defined for it, of course. 1278 /// 1279 /// The simplest way of using this map is through the absMap() 1280 /// function. 1281 template<typename M> 999 1282 class AbsMap : public MapBase<typename M::Key, typename M::Value> { 1000 const M &m;1283 const M &_m; 1001 1284 public: 1002 1285 typedef MapBase<typename M::Key, typename M::Value> Parent; … … 1004 1287 typedef typename Parent::Value Value; 1005 1288 1006 /// Constructor1007 AbsMap(const M & _m) : m(_m) {};1008 /// \e 1009 Value operator[]( Keyk) const {1010 Value tmp = m[k];1289 /// Constructor 1290 AbsMap(const M &m) : _m(m) {} 1291 /// \e 1292 Value operator[](const Key &k) const { 1293 Value tmp = _m[k]; 1011 1294 return tmp >= 0 ? tmp : tmp; 1012 1295 } 1013 1296 1014 1297 }; 1015 1016 ///Returns an \c AbsMap class 1017 1018 ///This function just returns an \c AbsMap class. 1019 ///\relates AbsMap 1020 template<typename M> 1298 1299 /// Returns an \ref AbsMap class 1300 1301 /// This function just returns an \ref AbsMap class. 1302 /// 1303 /// For example, if \c m is a map with \c double values, then 1304 /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if 1305 /// it is positive or zero and <tt>m[x]</tt> if <tt>m[x]</tt> is 1306 /// negative. 1307 /// 1308 /// \relates AbsMap 1309 template<typename M> 1021 1310 inline AbsMap<M> absMap(const M &m) { 1022 1311 return AbsMap<M>(m); 1023 1312 } 1024 1313 1025 ///Converts an STL style functor to a map 1026 1027 ///This \ref concepts::ReadMap "read only map" returns the value 1028 ///of a given functor. 1029 /// 1030 ///Template parameters \c K and \c V will become its 1031 ///\c Key and \c Value. 1032 ///In most cases they have to be given explicitly because a 1033 ///functor typically does not provide \c argument_type and 1034 ///\c result_type typedefs. 1035 /// 1036 ///Parameter \c F is the type of the used functor. 1037 /// 1038 ///\sa MapFunctor 1039 template<typename F, 1040 typename K = typename F::argument_type, 1041 typename V = typename F::result_type> 1042 class FunctorMap : public MapBase<K, V> { 1043 F f; 1044 public: 1045 typedef MapBase<K, V> Parent; 1046 typedef typename Parent::Key Key; 1047 typedef typename Parent::Value Value; 1048 1049 ///Constructor 1050 FunctorMap(const F &_f = F()) : f(_f) {} 1051 /// \e 1052 Value operator[](Key k) const { return f(k);} 1053 }; 1314 /// @} 1054 1315 1055 ///Returns a \c FunctorMap class 1056 1057 ///This function just returns a \c FunctorMap class. 1058 /// 1059 ///This function is specialized for adaptable binary function 1060 ///classes and C++ functions. 1061 /// 1062 ///\relates FunctorMap 1063 template<typename K, typename V, typename F> inline 1064 FunctorMap<F, K, V> functorMap(const F &f) { 1065 return FunctorMap<F, K, V>(f); 1066 } 1067 1068 template <typename F> inline 1069 FunctorMap<F, typename F::argument_type, typename F::result_type> 1070 functorMap(const F &f) { 1071 return FunctorMap<F, typename F::argument_type, 1072 typename F::result_type>(f); 1073 } 1074 1075 template <typename K, typename V> inline 1076 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) { 1077 return FunctorMap<V (*)(K), K, V>(f); 1078 } 1079 1080 1081 ///Converts a map to an STL style (unary) functor 1082 1083 ///This class Converts a map to an STL style (unary) functor. 1084 ///That is it provides an <tt>operator()</tt> to read its values. 1085 /// 1086 ///For the sake of convenience it also works as 1087 ///a ususal \ref concepts::ReadMap "readable map", 1088 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist. 1089 /// 1090 ///\sa FunctorMap 1091 template <typename M> 1092 class MapFunctor : public MapBase<typename M::Key, typename M::Value> { 1093 const M& m; 1094 public: 1095 typedef MapBase<typename M::Key, typename M::Value> Parent; 1096 typedef typename Parent::Key Key; 1097 typedef typename Parent::Value Value; 1098 1099 typedef typename M::Key argument_type; 1100 typedef typename M::Value result_type; 1101 1102 ///Constructor 1103 MapFunctor(const M &_m) : m(_m) {}; 1104 ///\e 1105 Value operator()(Key k) const {return m[k];} 1106 ///\e 1107 Value operator[](Key k) const {return m[k];} 1108 }; 1109 1110 ///Returns a \c MapFunctor class 1111 1112 ///This function just returns a \c MapFunctor class. 1113 ///\relates MapFunctor 1114 template<typename M> 1115 inline MapFunctor<M> mapFunctor(const M &m) { 1116 return MapFunctor<M>(m); 1117 } 1118 1119 ///Just readable version of \ref ForkWriteMap 1120 1121 ///This map has two \ref concepts::ReadMap "readable map" 1122 ///parameters and each read request will be passed just to the 1123 ///first map. This class is the just readable map type of \c ForkWriteMap. 1124 /// 1125 ///The \c Key and \c Value are inherited from \c M1. 1126 ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1. 1127 /// 1128 ///\sa ForkWriteMap 1129 /// 1130 /// \todo Why is it needed? 1131 template<typename M1, typename M2> 1132 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { 1133 const M1& m1; 1134 const M2& m2; 1135 public: 1136 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 1137 typedef typename Parent::Key Key; 1138 typedef typename Parent::Value Value; 1139 1140 ///Constructor 1141 ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {}; 1142 /// \e 1143 Value operator[](Key k) const {return m1[k];} 1144 }; 1145 1146 1147 ///Applies all map setting operations to two maps 1148 1149 ///This map has two \ref concepts::WriteMap "writable map" 1150 ///parameters and each write request will be passed to both of them. 1151 ///If \c M1 is also \ref concepts::ReadMap "readable", 1152 ///then the read operations will return the 1153 ///corresponding values of \c M1. 1154 /// 1155 ///The \c Key and \c Value are inherited from \c M1. 1156 ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1. 1157 /// 1158 ///\sa ForkMap 1159 template<typename M1, typename M2> 1160 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> { 1161 M1& m1; 1162 M2& m2; 1163 public: 1164 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 1165 typedef typename Parent::Key Key; 1166 typedef typename Parent::Value Value; 1167 1168 ///Constructor 1169 ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {}; 1170 ///\e 1171 Value operator[](Key k) const {return m1[k];} 1172 ///\e 1173 void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);} 1174 }; 1175 1176 ///Returns a \c ForkMap class 1177 1178 ///This function just returns a \c ForkMap class. 1179 ///\relates ForkMap 1180 template <typename M1, typename M2> 1181 inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) { 1182 return ForkMap<M1, M2>(m1,m2); 1183 } 1184 1185 ///Returns a \c ForkWriteMap class 1186 1187 ///This function just returns a \c ForkWriteMap class. 1188 ///\relates ForkWriteMap 1189 template <typename M1, typename M2> 1190 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) { 1191 return ForkWriteMap<M1, M2>(m1,m2); 1192 } 1193 1194 1195 1196 /* ************* BOOL MAPS ******************* */ 1197 1198 ///Logical 'not' of a map 1199 1200 ///This bool \ref concepts::ReadMap "read only map" returns the 1201 ///logical negation of the value returned by the given map. 1202 ///Its \c Key is inherited from \c M, its \c Value is \c bool. 1203 /// 1204 ///\sa NotWriteMap 1205 template <typename M> 1316 // Logical maps and map adaptors: 1317 1318 /// \addtogroup maps 1319 /// @{ 1320 1321 /// Constant \c true map. 1322 1323 /// This \ref concepts::ReadMap "readonly map" assigns \c true to 1324 /// each key. 1325 /// 1326 /// Note that 1327 /// \code 1328 /// TrueMap<K> tm; 1329 /// \endcode 1330 /// is equivalent to 1331 /// \code 1332 /// ConstMap<K,bool> tm(true); 1333 /// \endcode 1334 /// 1335 /// \sa FalseMap 1336 /// \sa ConstMap 1337 template <typename K> 1338 class TrueMap : public MapBase<K, bool> { 1339 public: 1340 typedef MapBase<K, bool> Parent; 1341 typedef typename Parent::Key Key; 1342 typedef typename Parent::Value Value; 1343 1344 /// Gives back \c true. 1345 Value operator[](const Key&) const { return true; } 1346 }; 1347 1348 /// Returns a \ref TrueMap class 1349 1350 /// This function just returns a \ref TrueMap class. 1351 /// \relates TrueMap 1352 template<typename K> 1353 inline TrueMap<K> trueMap() { 1354 return TrueMap<K>(); 1355 } 1356 1357 1358 /// Constant \c false map. 1359 1360 /// This \ref concepts::ReadMap "readonly map" assigns \c false to 1361 /// each key. 1362 /// 1363 /// Note that 1364 /// \code 1365 /// FalseMap<K> fm; 1366 /// \endcode 1367 /// is equivalent to 1368 /// \code 1369 /// ConstMap<K,bool> fm(false); 1370 /// \endcode 1371 /// 1372 /// \sa TrueMap 1373 /// \sa ConstMap 1374 template <typename K> 1375 class FalseMap : public MapBase<K, bool> { 1376 public: 1377 typedef MapBase<K, bool> Parent; 1378 typedef typename Parent::Key Key; 1379 typedef typename Parent::Value Value; 1380 1381 /// Gives back \c false. 1382 Value operator[](const Key&) const { return false; } 1383 }; 1384 1385 /// Returns a \ref FalseMap class 1386 1387 /// This function just returns a \ref FalseMap class. 1388 /// \relates FalseMap 1389 template<typename K> 1390 inline FalseMap<K> falseMap() { 1391 return FalseMap<K>(); 1392 } 1393 1394 /// @} 1395 1396 /// \addtogroup map_adaptors 1397 /// @{ 1398 1399 /// Logical 'and' of two maps 1400 1401 /// This \ref concepts::ReadMap "readonly map" returns the logical 1402 /// 'and' of the values of the two given maps. 1403 /// Its \c Key type is inherited from \c M1 and its \c Value type is 1404 /// \c bool. \c M2::Key must be convertible to \c M1::Key. 1405 /// 1406 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 1407 /// \code 1408 /// AndMap<M1,M2> am(m1,m2); 1409 /// \endcode 1410 /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>. 1411 /// 1412 /// The simplest way of using this map is through the andMap() 1413 /// function. 1414 /// 1415 /// \sa OrMap 1416 /// \sa NotMap, NotWriteMap 1417 template<typename M1, typename M2> 1418 class AndMap : public MapBase<typename M1::Key, bool> { 1419 const M1 &_m1; 1420 const M2 &_m2; 1421 public: 1422 typedef MapBase<typename M1::Key, bool> Parent; 1423 typedef typename Parent::Key Key; 1424 typedef typename Parent::Value Value; 1425 1426 /// Constructor 1427 AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1428 /// \e 1429 Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; } 1430 }; 1431 1432 /// Returns an \ref AndMap class 1433 1434 /// This function just returns an \ref AndMap class. 1435 /// 1436 /// For example, if \c m1 and \c m2 are both maps with \c bool values, 1437 /// then <tt>andMap(m1,m2)[x]</tt> will be equal to 1438 /// <tt>m1[x]&&m2[x]</tt>. 1439 /// 1440 /// \relates AndMap 1441 template<typename M1, typename M2> 1442 inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) { 1443 return AndMap<M1, M2>(m1,m2); 1444 } 1445 1446 1447 /// Logical 'or' of two maps 1448 1449 /// This \ref concepts::ReadMap "readonly map" returns the logical 1450 /// 'or' of the values of the two given maps. 1451 /// Its \c Key type is inherited from \c M1 and its \c Value type is 1452 /// \c bool. \c M2::Key must be convertible to \c M1::Key. 1453 /// 1454 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 1455 /// \code 1456 /// OrMap<M1,M2> om(m1,m2); 1457 /// \endcode 1458 /// <tt>om[x]</tt> will be equal to <tt>m1[x]m2[x]</tt>. 1459 /// 1460 /// The simplest way of using this map is through the orMap() 1461 /// function. 1462 /// 1463 /// \sa AndMap 1464 /// \sa NotMap, NotWriteMap 1465 template<typename M1, typename M2> 1466 class OrMap : public MapBase<typename M1::Key, bool> { 1467 const M1 &_m1; 1468 const M2 &_m2; 1469 public: 1470 typedef MapBase<typename M1::Key, bool> Parent; 1471 typedef typename Parent::Key Key; 1472 typedef typename Parent::Value Value; 1473 1474 /// Constructor 1475 OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1476 /// \e 1477 Value operator[](const Key &k) const { return _m1[k]_m2[k]; } 1478 }; 1479 1480 /// Returns an \ref OrMap class 1481 1482 /// This function just returns an \ref OrMap class. 1483 /// 1484 /// For example, if \c m1 and \c m2 are both maps with \c bool values, 1485 /// then <tt>orMap(m1,m2)[x]</tt> will be equal to 1486 /// <tt>m1[x]m2[x]</tt>. 1487 /// 1488 /// \relates OrMap 1489 template<typename M1, typename M2> 1490 inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) { 1491 return OrMap<M1, M2>(m1,m2); 1492 } 1493 1494 1495 /// Logical 'not' of a map 1496 1497 /// This \ref concepts::ReadMap "readonly map" returns the logical 1498 /// negation of the values of the given map. 1499 /// Its \c Key is inherited from \c M and its \c Value is \c bool. 1500 /// 1501 /// The simplest way of using this map is through the notMap() 1502 /// function. 1503 /// 1504 /// \sa NotWriteMap 1505 template <typename M> 1206 1506 class NotMap : public MapBase<typename M::Key, bool> { 1207 const M &m;1507 const M &_m; 1208 1508 public: 1209 1509 typedef MapBase<typename M::Key, bool> Parent; … … 1212 1512 1213 1513 /// Constructor 1214 NotMap(const M &_m) : m(_m) {}; 1215 ///\e 1216 Value operator[](Key k) const {return !m[k];} 1217 }; 1218 1219 ///Logical 'not' of a map (ReadWrie version) 1220 1221 ///This bool \ref concepts::ReadWriteMap "readwrite map" returns the 1222 ///logical negation of the value returned by the given map. When it is set, 1223 ///the opposite value is set to the original map. 1224 ///Its \c Key is inherited from \c M, its \c Value is \c bool. 1225 /// 1226 ///\sa NotMap 1227 template <typename M> 1514 NotMap(const M &m) : _m(m) {} 1515 /// \e 1516 Value operator[](const Key &k) const { return !_m[k]; } 1517 }; 1518 1519 /// Logical 'not' of a map (readwrite version) 1520 1521 /// This \ref concepts::ReadWriteMap "readwrite map" returns the 1522 /// logical negation of the values of the given map. 1523 /// Its \c Key is inherited from \c M and its \c Value is \c bool. 1524 /// It makes also possible to write the map. When a value is set, 1525 /// the opposite value is set to the original map. 1526 /// 1527 /// The simplest way of using this map is through the notWriteMap() 1528 /// function. 1529 /// 1530 /// \sa NotMap 1531 template <typename M> 1228 1532 class NotWriteMap : public MapBase<typename M::Key, bool> { 1229 M &m;1533 M &_m; 1230 1534 public: 1231 1535 typedef MapBase<typename M::Key, bool> Parent; … … 1234 1538 1235 1539 /// Constructor 1236 NotWriteMap(M &_m) : m(_m) {}; 1237 ///\e 1238 Value operator[](Key k) const {return !m[k];} 1239 ///\e 1240 void set(Key k, bool v) { m.set(k, !v); } 1241 }; 1242 1243 ///Returns a \c NotMap class 1244 1245 ///This function just returns a \c NotMap class. 1246 ///\relates NotMap 1247 template <typename M> 1540 NotWriteMap(M &m) : _m(m) {} 1541 /// \e 1542 Value operator[](const Key &k) const { return !_m[k]; } 1543 /// \e 1544 void set(const Key &k, bool v) { _m.set(k, !v); } 1545 }; 1546 1547 /// Returns a \ref NotMap class 1548 1549 /// This function just returns a \ref NotMap class. 1550 /// 1551 /// For example, if \c m is a map with \c bool values, then 1552 /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>. 1553 /// 1554 /// \relates NotMap 1555 template <typename M> 1248 1556 inline NotMap<M> notMap(const M &m) { 1249 1557 return NotMap<M>(m); 1250 1558 } 1251 1252 ///Returns a \c NotWriteMap class 1253 1254 ///This function just returns a \c NotWriteMap class. 1255 ///\relates NotWriteMap 1256 template <typename M> 1257 inline NotWriteMap<M> notMap(M &m) { 1559 1560 /// Returns a \ref NotWriteMap class 1561 1562 /// This function just returns a \ref NotWriteMap class. 1563 /// 1564 /// For example, if \c m is a map with \c bool values, then 1565 /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>. 1566 /// Moreover it makes also possible to write the map. 1567 /// 1568 /// \relates NotWriteMap 1569 template <typename M> 1570 inline NotWriteMap<M> notWriteMap(M &m) { 1258 1571 return NotWriteMap<M>(m); 1259 1572 } 1260 1573 1261 namespace _maps_bits { 1262 1263 template <typename Value> 1264 struct Identity { 1265 typedef Value argument_type; 1266 typedef Value result_type; 1267 Value operator()(const Value& val) const { 1268 return val; 1269 } 1270 }; 1271 1272 template <typename _Iterator, typename Enable = void> 1273 struct IteratorTraits { 1274 typedef typename std::iterator_traits<_Iterator>::value_type Value; 1275 }; 1276 1277 template <typename _Iterator> 1278 struct IteratorTraits<_Iterator, 1279 typename exists<typename _Iterator::container_type>::type> 1280 { 1281 typedef typename _Iterator::container_type::value_type Value; 1282 }; 1283 1284 } 1285 1286 1287 /// \brief Writable bool map for logging each \c true assigned element 1288 /// 1289 /// A \ref concepts::ReadWriteMap "readwrite" bool map for logging 1290 /// each \c true assigned element, i.e it copies all the keys set 1291 /// to \c true to the given iterator. 1292 /// 1293 /// \note The container of the iterator should contain space 1294 /// for each element. 1295 /// 1296 /// The following example shows how you can write the edges found by 1297 /// the \ref Prim algorithm directly to the standard output. 1298 ///\code 1299 /// typedef IdMap<Graph, Edge> EdgeIdMap; 1300 /// EdgeIdMap edgeId(graph); 1301 /// 1302 /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor; 1303 /// EdgeIdFunctor edgeIdFunctor(edgeId); 1304 /// 1305 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor> 1306 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor); 1307 /// 1308 /// prim(graph, cost, writerMap); 1309 ///\endcode 1310 /// 1311 ///\sa BackInserterBoolMap 1312 ///\sa FrontInserterBoolMap 1313 ///\sa InserterBoolMap 1314 /// 1315 ///\todo Revise the name of this class and the related ones. 1316 template <typename _Iterator, 1317 typename _Functor = 1318 _maps_bits::Identity<typename _maps_bits:: 1319 IteratorTraits<_Iterator>::Value> > 1320 class StoreBoolMap { 1321 public: 1322 typedef _Iterator Iterator; 1323 1324 typedef typename _Functor::argument_type Key; 1325 typedef bool Value; 1326 1327 typedef _Functor Functor; 1328 1329 /// Constructor 1330 StoreBoolMap(Iterator it, const Functor& functor = Functor()) 1331 : _begin(it), _end(it), _functor(functor) {} 1332 1333 /// Gives back the given iterator set for the first key 1334 Iterator begin() const { 1335 return _begin; 1336 } 1337 1338 /// Gives back the the 'after the last' iterator 1339 Iterator end() const { 1340 return _end; 1341 } 1342 1343 /// The \c set function of the map 1344 void set(const Key& key, Value value) const { 1345 if (value) { 1346 *_end++ = _functor(key); 1347 } 1348 } 1349 1350 private: 1351 Iterator _begin; 1352 mutable Iterator _end; 1353 Functor _functor; 1354 }; 1355 1356 /// \brief Writable bool map for logging each \c true assigned element in 1357 /// a back insertable container. 1358 /// 1359 /// Writable bool map for logging each \c true assigned element by pushing 1360 /// them into a back insertable container. 1361 /// It can be used to retrieve the items into a standard 1362 /// container. The next example shows how you can store the 1363 /// edges found by the Prim algorithm in a vector. 1364 /// 1365 ///\code 1366 /// vector<Edge> span_tree_edges; 1367 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges); 1368 /// prim(graph, cost, inserter_map); 1369 ///\endcode 1370 /// 1371 ///\sa StoreBoolMap 1372 ///\sa FrontInserterBoolMap 1373 ///\sa InserterBoolMap 1374 template <typename Container, 1375 typename Functor = 1376 _maps_bits::Identity<typename Container::value_type> > 1377 class BackInserterBoolMap { 1378 public: 1379 typedef typename Functor::argument_type Key; 1380 typedef bool Value; 1381 1382 /// Constructor 1383 BackInserterBoolMap(Container& _container, 1384 const Functor& _functor = Functor()) 1385 : container(_container), functor(_functor) {} 1386 1387 /// The \c set function of the map 1388 void set(const Key& key, Value value) { 1389 if (value) { 1390 container.push_back(functor(key)); 1391 } 1392 } 1393 1394 private: 1395 Container& container; 1396 Functor functor; 1397 }; 1398 1399 /// \brief Writable bool map for logging each \c true assigned element in 1400 /// a front insertable container. 1401 /// 1402 /// Writable bool map for logging each \c true assigned element by pushing 1403 /// them into a front insertable container. 1404 /// It can be used to retrieve the items into a standard 1405 /// container. For example see \ref BackInserterBoolMap. 1406 /// 1407 ///\sa BackInserterBoolMap 1408 ///\sa InserterBoolMap 1409 template <typename Container, 1410 typename Functor = 1411 _maps_bits::Identity<typename Container::value_type> > 1412 class FrontInserterBoolMap { 1413 public: 1414 typedef typename Functor::argument_type Key; 1415 typedef bool Value; 1416 1417 /// Constructor 1418 FrontInserterBoolMap(Container& _container, 1419 const Functor& _functor = Functor()) 1420 : container(_container), functor(_functor) {} 1421 1422 /// The \c set function of the map 1423 void set(const Key& key, Value value) { 1424 if (value) { 1425 container.push_front(functor(key)); 1426 } 1427 } 1428 1429 private: 1430 Container& container; 1431 Functor functor; 1432 }; 1433 1434 /// \brief Writable bool map for storing each \c true assigned element in 1435 /// an insertable container. 1436 /// 1437 /// Writable bool map for storing each \c true assigned element in an 1438 /// insertable container. It will insert all the keys set to \c true into 1439 /// the container. 1440 /// 1441 /// For example, if you want to store the cut arcs of the strongly 1442 /// connected components in a set you can use the next code: 1443 /// 1444 ///\code 1445 /// set<Arc> cut_arcs; 1446 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs); 1447 /// stronglyConnectedCutArcs(digraph, cost, inserter_map); 1448 ///\endcode 1449 /// 1450 ///\sa BackInserterBoolMap 1451 ///\sa FrontInserterBoolMap 1452 template <typename Container, 1453 typename Functor = 1454 _maps_bits::Identity<typename Container::value_type> > 1455 class InserterBoolMap { 1456 public: 1457 typedef typename Container::value_type Key; 1458 typedef bool Value; 1459 1460 /// Constructor with specified iterator 1461 1462 /// Constructor with specified iterator. 1463 /// \param _container The container for storing the elements. 1464 /// \param _it The elements will be inserted before this iterator. 1465 /// \param _functor The functor that is used when an element is stored. 1466 InserterBoolMap(Container& _container, typename Container::iterator _it, 1467 const Functor& _functor = Functor()) 1468 : container(_container), it(_it), functor(_functor) {} 1469 1470 /// Constructor 1471 1472 /// Constructor without specified iterator. 1473 /// The elements will be inserted before <tt>_container.end()</tt>. 1474 /// \param _container The container for storing the elements. 1475 /// \param _functor The functor that is used when an element is stored. 1476 InserterBoolMap(Container& _container, const Functor& _functor = Functor()) 1477 : container(_container), it(_container.end()), functor(_functor) {} 1478 1479 /// The \c set function of the map 1480 void set(const Key& key, Value value) { 1481 if (value) { 1482 it = container.insert(it, functor(key)); 1483 ++it; 1484 } 1485 } 1486 1487 private: 1488 Container& container; 1489 typename Container::iterator it; 1490 Functor functor; 1491 }; 1492 1493 /// \brief Writable bool map for filling each \c true assigned element with a 1494 /// given value. 1495 /// 1496 /// Writable bool map for filling each \c true assigned element with a 1497 /// given value. The value can set the container. 1498 /// 1499 /// The following code finds the connected components of a graph 1500 /// and stores it in the \c comp map: 1501 ///\code 1502 /// typedef Graph::NodeMap<int> ComponentMap; 1503 /// ComponentMap comp(graph); 1504 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap; 1505 /// ComponentFillerMap filler(comp, 0); 1506 /// 1507 /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph); 1508 /// dfs.processedMap(filler); 1509 /// dfs.init(); 1510 /// for (NodeIt it(graph); it != INVALID; ++it) { 1511 /// if (!dfs.reached(it)) { 1512 /// dfs.addSource(it); 1513 /// dfs.start(); 1514 /// ++filler.fillValue(); 1515 /// } 1516 /// } 1517 ///\endcode 1518 template <typename Map> 1519 class FillBoolMap { 1520 public: 1521 typedef typename Map::Key Key; 1522 typedef bool Value; 1523 1524 /// Constructor 1525 FillBoolMap(Map& _map, const typename Map::Value& _fill) 1526 : map(_map), fill(_fill) {} 1527 1528 /// Constructor 1529 FillBoolMap(Map& _map) 1530 : map(_map), fill() {} 1531 1532 /// Gives back the current fill value 1533 const typename Map::Value& fillValue() const { 1534 return fill; 1535 } 1536 1537 /// Gives back the current fill value 1538 typename Map::Value& fillValue() { 1539 return fill; 1540 } 1541 1542 /// Sets the current fill value 1543 void fillValue(const typename Map::Value& _fill) { 1544 fill = _fill; 1545 } 1546 1547 /// The \c set function of the map 1548 void set(const Key& key, Value value) { 1549 if (value) { 1550 map.set(key, fill); 1551 } 1552 } 1553 1554 private: 1555 Map& map; 1556 typename Map::Value fill; 1557 }; 1558 1559 1560 /// \brief Writable bool map for storing the sequence number of 1561 /// \c true assignments. 1562 /// 1563 /// Writable bool map that stores for each \c true assigned elements 1564 /// the sequence number of this setting. 1565 /// It makes it easy to calculate the leaving 1566 /// order of the nodes in the \c Dfs algorithm. 1567 /// 1568 ///\code 1569 /// typedef Digraph::NodeMap<int> OrderMap; 1570 /// OrderMap order(digraph); 1571 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap; 1572 /// OrderSetterMap setter(order); 1573 /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph); 1574 /// dfs.processedMap(setter); 1575 /// dfs.init(); 1576 /// for (NodeIt it(digraph); it != INVALID; ++it) { 1577 /// if (!dfs.reached(it)) { 1578 /// dfs.addSource(it); 1579 /// dfs.start(); 1580 /// } 1581 /// } 1582 ///\endcode 1583 /// 1584 /// The storing of the discovering order is more difficult because the 1585 /// ReachedMap should be readable in the dfs algorithm but the setting 1586 /// order map is not readable. Thus we must use the fork map: 1587 /// 1588 ///\code 1589 /// typedef Digraph::NodeMap<int> OrderMap; 1590 /// OrderMap order(digraph); 1591 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap; 1592 /// OrderSetterMap setter(order); 1593 /// typedef Digraph::NodeMap<bool> StoreMap; 1594 /// StoreMap store(digraph); 1595 /// 1596 /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap; 1597 /// ReachedMap reached(store, setter); 1598 /// 1599 /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph); 1600 /// dfs.reachedMap(reached); 1601 /// dfs.init(); 1602 /// for (NodeIt it(digraph); it != INVALID; ++it) { 1603 /// if (!dfs.reached(it)) { 1604 /// dfs.addSource(it); 1605 /// dfs.start(); 1606 /// } 1607 /// } 1608 ///\endcode 1609 template <typename Map> 1610 class SettingOrderBoolMap { 1611 public: 1612 typedef typename Map::Key Key; 1613 typedef bool Value; 1614 1615 /// Constructor 1616 SettingOrderBoolMap(Map& _map) 1617 : map(_map), counter(0) {} 1618 1619 /// Number of set operations. 1620 int num() const { 1621 return counter; 1622 } 1623 1624 /// The \c set function of the map 1625 void set(const Key& key, Value value) { 1626 if (value) { 1627 map.set(key, counter++); 1628 } 1629 } 1630 1631 private: 1632 Map& map; 1633 int counter; 1634 }; 1574 1575 /// Combination of two maps using the \c == operator 1576 1577 /// This \ref concepts::ReadMap "readonly map" assigns \c true to 1578 /// the keys for which the corresponding values of the two maps are 1579 /// equal. 1580 /// Its \c Key type is inherited from \c M1 and its \c Value type is 1581 /// \c bool. \c M2::Key must be convertible to \c M1::Key. 1582 /// 1583 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 1584 /// \code 1585 /// EqualMap<M1,M2> em(m1,m2); 1586 /// \endcode 1587 /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>. 1588 /// 1589 /// The simplest way of using this map is through the equalMap() 1590 /// function. 1591 /// 1592 /// \sa LessMap 1593 template<typename M1, typename M2> 1594 class EqualMap : public MapBase<typename M1::Key, bool> { 1595 const M1 &_m1; 1596 const M2 &_m2; 1597 public: 1598 typedef MapBase<typename M1::Key, bool> Parent; 1599 typedef typename Parent::Key Key; 1600 typedef typename Parent::Value Value; 1601 1602 /// Constructor 1603 EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1604 /// \e 1605 Value operator[](const Key &k) const { return _m1[k]==_m2[k]; } 1606 }; 1607 1608 /// Returns an \ref EqualMap class 1609 1610 /// This function just returns an \ref EqualMap class. 1611 /// 1612 /// For example, if \c m1 and \c m2 are maps with keys and values of 1613 /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to 1614 /// <tt>m1[x]==m2[x]</tt>. 1615 /// 1616 /// \relates EqualMap 1617 template<typename M1, typename M2> 1618 inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) { 1619 return EqualMap<M1, M2>(m1,m2); 1620 } 1621 1622 1623 /// Combination of two maps using the \c < operator 1624 1625 /// This \ref concepts::ReadMap "readonly map" assigns \c true to 1626 /// the keys for which the corresponding value of the first map is 1627 /// less then the value of the second map. 1628 /// Its \c Key type is inherited from \c M1 and its \c Value type is 1629 /// \c bool. \c M2::Key must be convertible to \c M1::Key. 1630 /// 1631 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 1632 /// \code 1633 /// LessMap<M1,M2> lm(m1,m2); 1634 /// \endcode 1635 /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>. 1636 /// 1637 /// The simplest way of using this map is through the lessMap() 1638 /// function. 1639 /// 1640 /// \sa EqualMap 1641 template<typename M1, typename M2> 1642 class LessMap : public MapBase<typename M1::Key, bool> { 1643 const M1 &_m1; 1644 const M2 &_m2; 1645 public: 1646 typedef MapBase<typename M1::Key, bool> Parent; 1647 typedef typename Parent::Key Key; 1648 typedef typename Parent::Value Value; 1649 1650 /// Constructor 1651 LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1652 /// \e 1653 Value operator[](const Key &k) const { return _m1[k]<_m2[k]; } 1654 }; 1655 1656 /// Returns an \ref LessMap class 1657 1658 /// This function just returns an \ref LessMap class. 1659 /// 1660 /// For example, if \c m1 and \c m2 are maps with keys and values of 1661 /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to 1662 /// <tt>m1[x]<m2[x]</tt>. 1663 /// 1664 /// \relates LessMap 1665 template<typename M1, typename M2> 1666 inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) { 1667 return LessMap<M1, M2>(m1,m2); 1668 } 1635 1669 1636 1670 /// @}
Note: See TracChangeset
for help on using the changeset viewer.