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