Changeset 2564:3250756f5add in lemon-0.x
- Timestamp:
- 02/05/08 13:41:05 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3445
- Location:
- lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/maps.h
r2553 r2564 35 35 36 36 /// Readable map concept 37 38 /// Readable map concept. 39 /// 37 40 template<typename K, typename T> 38 41 class ReadMap 39 42 { 40 43 public: 41 /// Map's key type. 42 typedef K Key; 43 /// Map's value type. (The type of objects associated with the keys). 44 typedef T Value; 45 46 // \bug Value don't need to be default constructible. 44 /// The key type of the map. 45 typedef K Key; 46 /// The value type of the map. (The type of objects associated with the keys). 47 typedef T Value; 48 47 49 /// Returns the value associated with a key. 50 51 /// Returns the value associated with a key. 52 /// \bug Value shouldn't need to be default constructible. 53 /// 48 54 Value operator[](const Key &) const {return Value();} 49 55 … … 70 76 71 77 /// Writable map concept 78 79 /// Writable map concept. 80 /// 72 81 template<typename K, typename T> 73 82 class WriteMap 74 83 { 75 84 public: 76 /// Map's key type.77 typedef K Key; 78 /// Map's value type. (The type of objects associated with the keys).85 /// The key type of the map. 86 typedef K Key; 87 /// The value type of the map. (The type of objects associated with the keys). 79 88 typedef T Value; 80 89 … … 106 115 }; 107 116 108 ///Read/Writable map concept 117 /// Read/writable map concept 118 119 /// Read/writable map concept. 120 /// 109 121 template<typename K, typename T> 110 122 class ReadWriteMap : public ReadMap<K,T>, 111 112 { 113 public: 114 /// Map's key type.115 typedef K Key; 116 /// Map's value type. (The type of objects associated with the keys).123 public WriteMap<K,T> 124 { 125 public: 126 /// The key type of the map. 127 typedef K Key; 128 /// The value type of the map. (The type of objects associated with the keys). 117 129 typedef T Value; 118 130 … … 133 145 134 146 ///Dereferable map concept 147 148 /// Dereferable map concept. 149 /// 150 /// \todo Rethink this concept. 135 151 template<typename K, typename T, typename R, typename CR> 136 152 class ReferenceMap : public ReadWriteMap<K,T> … … 139 155 /// Tag for reference maps. 140 156 typedef True ReferenceMapTag; 141 /// Map's key type.142 typedef K Key; 143 /// Map's value type. (The type of objects associated with the keys).144 typedef T Value; 145 /// Map's reference type.157 /// The key type of the map. 158 typedef K Key; 159 /// The value type of the map. (The type of objects associated with the keys). 160 typedef T Value; 161 /// The reference type of the map. 146 162 typedef R Reference; 147 /// Map's const reference type.163 /// The const reference type of the map. 148 164 typedef CR ConstReference; 149 165 … … 152 168 public: 153 169 154 ///Returns a reference to the value associated toa key.170 ///Returns a reference to the value associated with a key. 155 171 Reference operator[](const Key &) { return tmp; } 156 ///Returns a const reference to the value associated to a key. 157 ConstReference operator[](const Key &) const 158 { return tmp; } 172 ///Returns a const reference to the value associated with a key. 173 ConstReference operator[](const Key &) const { return tmp; } 159 174 /// Sets the value associated with a key. 160 175 void set(const Key &k,const Value &t) { operator[](k)=t; } 161 176 162 // \todo rethink this concept163 177 template<typename _ReferenceMap> 164 struct ReferenceMapConcept{165 166 void constraints() { 167 checkConcept<ReadWriteMap , _ReferenceMap >();178 struct Constraints { 179 180 void constraints() { 181 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >(); 168 182 m[key] = val; 169 183 val = m[key]; … … 178 192 typename _ReferenceMap::Key& own_key; 179 193 typename _ReferenceMap::Value& own_val; 180 typename _ReferenceMap::Reference &own_ref;194 typename _ReferenceMap::Reference own_ref; 181 195 Key& key; 182 196 Value& val; 183 Reference &ref;197 Reference ref; 184 198 _ReferenceMap& m; 185 199 }; … … 189 203 190 204 } //namespace concepts 205 191 206 } //namespace lemon 207 192 208 #endif // LEMON_CONCEPT_MAPS_H -
lemon/maps.h
r2553 r2564 45 45 class MapBase { 46 46 public: 47 /// \e47 /// The key type of the map. 48 48 typedef K Key; 49 /// \e49 /// The value type of the map. (The type of objects associated with the keys). 50 50 typedef T Value; 51 51 }; … … 53 53 /// Null map. (a.k.a. DoNothingMap) 54 54 55 /// If you have to provide a map only for its type definitions, 56 /// or if you have to provide a writable map, but 57 /// data written to it will sent to <tt>/dev/null</tt>... 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>). 58 59 template<typename K, typename T> 59 60 class NullMap : public MapBase<K, T> { … … 69 70 }; 70 71 72 ///Returns a \c NullMap class 73 74 ///This function just returns a \c NullMap class. 75 ///\relates NullMap 71 76 template <typename K, typename V> 72 77 NullMap<K, V> nullMap() { … … 77 82 /// Constant map. 78 83 79 /// This is a readable map which assigns a specified value to each key. 80 /// In other aspects it is equivalent to the \c NullMap. 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. 81 87 template<typename K, typename T> 82 88 class ConstMap : public MapBase<K, T> { … … 91 97 /// Default constructor 92 98 99 /// Default constructor. 93 100 /// The value of the map will be uninitialized. 94 101 /// (More exactly it will be default constructed.) 95 102 ConstMap() {} 96 ///\e 97 98 /// \param _v The initial value of the map. 99 /// 103 104 /// Constructor with specified initial value 105 106 /// Constructor with specified initial value. 107 /// \param _v is the initial value of the map. 100 108 ConstMap(const T &_v) : v(_v) {} 101 109 … … 132 140 /// Constant map with inlined constant value. 133 141 134 /// This is a readable map which assigns a specified value to each key. 135 /// In other aspects it is equivalent to the \c NullMap. 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. 136 145 template<typename K, typename V, V v> 137 146 class ConstMap<K, Const<V, v> > : public MapBase<K, V> { … … 148 157 }; 149 158 150 ///Returns a \c ConstMap class 159 ///Returns a \c ConstMap class with inlined value 151 160 152 161 ///This function just returns a \c ConstMap class with inlined value. … … 157 166 } 158 167 159 ///Map based on std::map160 161 ///This is essentially a wrapper for \c std::map . With addition that168 ///Map based on \c std::map 169 170 ///This is essentially a wrapper for \c std::map with addition that 162 171 ///you can specify a default value different from \c Value() . 172 ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept. 163 173 template <typename K, typename T, typename Compare = std::less<K> > 164 class StdMap {174 class StdMap : public MapBase<K, T> { 165 175 template <typename K1, typename T1, typename C1> 166 176 friend class StdMap; 167 177 public: 168 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 169 189 typedef True ReferenceMapTag; 170 ///\e171 typedef K Key;172 ///\e173 typedef T Value;174 ///\e175 typedef T& Reference;176 ///\e177 typedef const T& ConstReference;178 190 179 191 private: … … 187 199 /// Constructor with specified default value 188 200 StdMap(const T& value = T()) : _value(value) {} 189 /// \brief Constructs the map from an appropriate std::map, and explicitly190 /// specifies a default value.201 /// \brief Constructs the map from an appropriate \c std::map, and 202 /// explicitly specifies a default value. 191 203 template <typename T1, typename Comp1> 192 204 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 193 205 : _map(map.begin(), map.end()), _value(value) {} 194 206 195 /// \brief Constructs a map from an other StdMap.207 /// \brief Constructs a map from an other \ref StdMap. 196 208 template<typename T1, typename Comp1> 197 209 StdMap(const StdMap<Key, T1, Comp1> &c) … … 243 255 }; 244 256 245 /// \brief Map for storing values for the range \c [0..size-1] range keys 246 /// 247 /// The current map has the \c [0..size-1] keyset and the values 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 248 286 /// are stored in a \c std::vector<T> container. It can be used with 249 287 /// some data structures, for example \c UnionFind, \c BinHeap, when 250 288 /// the used items are small integer numbers. 251 289 template <typename T> 252 class IntegerMap {290 class IntegerMap : public MapBase<int, T> { 253 291 254 292 template <typename T1> … … 257 295 public: 258 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 259 307 typedef True ReferenceMapTag; 260 ///\e261 typedef int Key;262 ///\e263 typedef T Value;264 ///\e265 typedef T& Reference;266 ///\e267 typedef const T& ConstReference;268 308 269 309 private: … … 277 317 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {} 278 318 279 /// \brief Constructs the map from an appropriate std::vector.319 /// \brief Constructs the map from an appropriate \c std::vector. 280 320 template <typename T1> 281 321 IntegerMap(const std::vector<T1>& vector) 282 322 : _vector(vector.begin(), vector.end()) {} 283 323 284 /// \brief Constructs a map from an other IntegerMap.324 /// \brief Constructs a map from an other \ref IntegerMap. 285 325 template <typename T1> 286 326 IntegerMap(const IntegerMap<T1> &c) … … 315 355 }; 316 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 317 366 /// @} 318 367 … … 320 369 /// @{ 321 370 322 /// \brief Identity map ping.323 /// 324 /// This map pinggives back the given key as value without any371 /// \brief Identity map. 372 /// 373 /// This map gives back the given key as value without any 325 374 /// modification. 326 375 template <typename T> … … 347 396 348 397 349 ///Convert the \c Value of a map to another type. 350 351 ///This \c concepts::ReadMap "read only map" 352 ///converts the \c Value of a maps to type \c T. 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. 353 403 ///Its \c Key is inherited from \c M. 354 404 template <typename M, typename T> … … 366 416 ConvertMap(const M &_m) : m(_m) {}; 367 417 368 /// \brief The subscript operator. 369 /// 370 /// The subscript operator. 371 /// \param k The key 372 /// \return The target of the edge 418 ///\e 373 419 Value operator[](const Key& k) const {return m[k];} 374 420 }; 375 421 376 ///Returns a n\c ConvertMap class377 378 ///This function just returns a n\c ConvertMap class.422 ///Returns a \c ConvertMap class 423 424 ///This function just returns a \c ConvertMap class. 379 425 ///\relates ConvertMap 380 426 template<typename T, typename M> … … 383 429 } 384 430 385 ///Simple wrapping of themap386 387 ///This \ cconcepts::ReadMap "read only map" returns the simple431 ///Simple wrapping of a map 432 433 ///This \ref concepts::ReadMap "read only map" returns the simple 388 434 ///wrapping of the given map. Sometimes the reference maps cannot be 389 435 ///combined with simple read maps. This map adaptor wraps the given 390 436 ///map to simple read map. 437 /// 438 ///\sa SimpleWriteMap 439 /// 440 /// \todo Revise the misleading name 391 441 template<typename M> 392 442 class SimpleMap : public MapBase<typename M::Key, typename M::Value> { … … 404 454 }; 405 455 406 ///Simple writeable wrapping of the map 407 408 ///This \c concepts::ReadMap "read only map" returns the simple 456 ///Returns a \c SimpleMap class 457 458 ///This function just returns a \c SimpleMap class. 459 ///\relates SimpleMap 460 template<typename 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 409 468 ///wrapping of the given map. Sometimes the reference maps cannot be 410 469 ///combined with simple read-write maps. This map adaptor wraps the 411 470 ///given map to simple read-write map. 471 /// 472 ///\sa SimpleMap 473 /// 474 /// \todo Revise the misleading name 412 475 template<typename M> 413 476 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> { … … 427 490 }; 428 491 492 ///Returns a \c SimpleWriteMap class 493 494 ///This function just returns a \c SimpleWriteMap class. 495 ///\relates SimpleWriteMap 496 template<typename M> 497 inline SimpleWriteMap<M> simpleWriteMap(M &m) { 498 return SimpleWriteMap<M>(m); 499 } 500 429 501 ///Sum of two maps 430 502 431 ///This \ cconcepts::ReadMap "read only map" returns the sum of the two432 ///given maps. Its \c Key and \c Value will be inherited from \c M1.433 /// The \c Key and \c Value of M2 must be convertible to those of\c M1.434 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. 435 507 template<typename M1, typename M2> 436 508 class AddMap : public MapBase<typename M1::Key, typename M1::Value> { … … 462 534 ///Shift a map with a constant. 463 535 464 ///This \ cconcepts::ReadMap "read only map" returns the sum of the536 ///This \ref concepts::ReadMap "read only map" returns the sum of the 465 537 ///given map and a constant value. 466 538 ///Its \c Key and \c Value is inherited from \c M. … … 470 542 /// ShiftMap<X> sh(x,v); 471 543 ///\endcode 472 ///is equivalent with544 ///is equivalent to 473 545 ///\code 474 546 /// ConstMap<X::Key, X::Value> c_tmp(v); 475 547 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v); 476 548 ///\endcode 549 /// 550 ///\sa ShiftWriteMap 477 551 template<typename M, typename C = typename M::Value> 478 552 class ShiftMap : public MapBase<typename M::Key, typename M::Value> { … … 494 568 }; 495 569 496 ///Shift a map with a constant .497 498 ///This \ cconcepts::ReadWriteMap "read-write map" returns the sum of the570 ///Shift a map with a constant (ReadWrite version). 571 572 ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the 499 573 ///given map and a constant value. It makes also possible to write the map. 500 ///Its \c Key and \c Value is inherited from \c M. 501 /// 502 ///Actually, 503 ///\code 504 /// ShiftMap<X> sh(x,v); 505 ///\endcode 506 ///is equivalent with 507 ///\code 508 /// ConstMap<X::Key, X::Value> c_tmp(v); 509 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v); 510 ///\endcode 574 ///Its \c Key and \c Value are inherited from \c M. 575 /// 576 ///\sa ShiftMap 511 577 template<typename M, typename C = typename M::Value> 512 578 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> { … … 530 596 }; 531 597 532 ///Returns a n\c ShiftMap class598 ///Returns a \c ShiftMap class 533 599 534 600 ///This function just returns an \c ShiftMap class. … … 539 605 } 540 606 607 ///Returns a \c ShiftWriteMap class 608 609 ///This function just returns a \c ShiftWriteMap class. 610 ///\relates ShiftWriteMap 541 611 template<typename M, typename C> 542 612 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) { … … 546 616 ///Difference of two maps 547 617 548 ///This \ cconcepts::ReadMap "read only map" returns the difference549 ///of the values of the two 550 /// given maps. Its \c Key and \c Value will be inherited from \c M1.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. 551 621 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 552 622 … … 578 648 ///Product of two maps 579 649 580 ///This \c concepts::ReadMap "read only map" returns the product of the 581 ///values of the two 582 ///given 583 ///maps. Its \c Key and \c Value will be inherited from \c M1. 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. 584 653 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 585 586 654 template<typename M1, typename M2> 587 655 class MulMap : public MapBase<typename M1::Key, typename M1::Value> { … … 608 676 } 609 677 610 ///Scales a map swith a constant.611 612 ///This \ cconcepts::ReadMap "read only map" returns the value of the678 ///Scales a map with a constant. 679 680 ///This \ref concepts::ReadMap "read only map" returns the value of the 613 681 ///given map multiplied from the left side with a constant value. 614 ///Its \c Key and \c Value isinherited from \c M.682 ///Its \c Key and \c Value are inherited from \c M. 615 683 /// 616 684 ///Actually, … … 618 686 /// ScaleMap<X> sc(x,v); 619 687 ///\endcode 620 ///is equivalent with688 ///is equivalent to 621 689 ///\code 622 690 /// ConstMap<X::Key, X::Value> c_tmp(v); 623 691 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v); 624 692 ///\endcode 693 /// 694 ///\sa ScaleWriteMap 625 695 template<typename M, typename C = typename M::Value> 626 696 class ScaleMap : public MapBase<typename M::Key, typename M::Value> { … … 642 712 }; 643 713 644 ///Scales a map s with a constant.645 646 ///This \ cconcepts::ReadWriteMap "read-write map" returns the value of the714 ///Scales a map with a constant (ReadWrite version). 715 716 ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the 647 717 ///given map multiplied from the left side with a constant value. It can 648 ///be used as write map also if the given multiplier is not zero. 649 ///Its \c Key and \c Value is inherited from \c M. 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 650 723 template<typename M, typename C = typename M::Value> 651 724 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> { … … 669 742 }; 670 743 671 ///Returns a n\c ScaleMap class672 673 ///This function just returns a n\c ScaleMap class.744 ///Returns a \c ScaleMap class 745 746 ///This function just returns a \c ScaleMap class. 674 747 ///\relates ScaleMap 675 748 template<typename M, typename C> … … 678 751 } 679 752 753 ///Returns a \c ScaleWriteMap class 754 755 ///This function just returns a \c ScaleWriteMap class. 756 ///\relates ScaleWriteMap 680 757 template<typename M, typename C> 681 758 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) { … … 685 762 ///Quotient of two maps 686 763 687 ///This \ cconcepts::ReadMap "read only map" returns the quotient of the688 ///values of the two 689 /// given maps. Its \c Key and \c Value will be inherited from \c M1.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. 690 767 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 691 692 768 template<typename M1, typename M2> 693 769 class DivMap : public MapBase<typename M1::Key, typename M1::Value> { … … 716 792 ///Composition of two maps 717 793 718 ///This \c concepts::ReadMap "read only map" returns the composition of 719 ///two 720 ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is 721 ///of \c M2, 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, 722 797 ///then for 723 798 ///\code 724 799 /// ComposeMap<M1, M2> cm(m1,m2); 725 800 ///\endcode 726 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt> 727 /// 728 ///Its \c Key is inherited from \c M2 and its \c Value is from 729 ///\c M1. 730 ///The \c M2::Value must be convertible to \c M1::Key. 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 /// 731 808 ///\todo Check the requirements. 732 809 template <typename M1, typename M2> … … 756 833 } 757 834 758 ///Combines of two maps using an STL (binary) functor. 759 760 ///Combines of two maps using an STL (binary) functor. 761 /// 762 /// 763 ///This \c concepts::ReadMap "read only map" takes two maps and a 764 ///binary functor and returns the composition of 765 ///the two 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 766 841 ///given maps unsing the functor. 767 842 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2 768 ///and \c f is of \c F, 769 ///then for 843 ///and \c f is of \c F, then for 770 844 ///\code 771 845 /// CombineMap<M1, M2,F,V> cm(m1,m2,f); … … 774 848 /// 775 849 ///Its \c Key is inherited from \c M1 and its \c Value is \c V. 776 /// The\c M2::Value and \c M1::Value must be convertible to the corresponding850 ///\c M2::Value and \c M1::Value must be convertible to the corresponding 777 851 ///input parameter of \c F and the return type of \c F must be convertible 778 852 ///to \c V. 853 /// 854 ///\sa ComposeMap 855 /// 779 856 ///\todo Check the requirements. 780 857 template<typename M1, typename M2, typename F, … … 802 879 ///For example if \c m1 and \c m2 are both \c double valued maps, then 803 880 ///\code 804 ///combineMap <double>(m1,m2,std::plus<double>())881 ///combineMap(m1,m2,std::plus<double>()) 805 882 ///\endcode 806 ///is equivalent with883 ///is equivalent to 807 884 ///\code 808 885 ///addMap(m1,m2) … … 810 887 /// 811 888 ///This function is specialized for adaptable binary function 812 ///classes and c++ functions.889 ///classes and C++ functions. 813 890 /// 814 891 ///\relates CombineMap … … 833 910 ///Negative value of a map 834 911 835 ///This \c concepts::ReadMap "read only map" returns the negative 836 ///value of the 837 ///value returned by the 838 ///given map. Its \c Key and \c Value will be inherited from \c M. 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. 839 915 ///The unary \c - operator must be defined for \c Value, of course. 840 916 /// 917 ///\sa NegWriteMap 841 918 template<typename M> 842 919 class NegMap : public MapBase<typename M::Key, typename M::Value> { … … 853 930 }; 854 931 855 ///Negative value of a map 856 857 ///This \ cconcepts::ReadWriteMap "read-write map" returns the negative858 ///value of the value returned by the 859 /// given map. Its \c Key and \c Value will be inherited from \c M.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. 860 937 ///The unary \c - operator must be defined for \c Value, of course. 861 938 /// 939 /// \sa NegMap 862 940 template<typename M> 863 941 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> { … … 885 963 } 886 964 965 ///Returns a \c NegWriteMap class 966 967 ///This function just returns a \c NegWriteMap class. 968 ///\relates NegWriteMap 887 969 template <typename M> 888 970 inline NegWriteMap<M> negMap(M &m) { … … 892 974 ///Absolute value of a map 893 975 894 ///This \c concepts::ReadMap "read only map" returns the absolute value 895 ///of the 896 ///value returned by the 897 ///given map. Its \c Key and \c Value will be inherited 898 ///from <tt>M</tt>. <tt>Value</tt> 899 ///must be comparable to <tt>0</tt> and the unary <tt>-</tt> 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 - 900 980 ///operator must be defined for it, of course. 901 981 /// … … 931 1011 }; 932 1012 933 ///Returns a \c AbsMap class934 935 ///This function just returns a \c AbsMap class.1013 ///Returns an \c AbsMap class 1014 1015 ///This function just returns an \c AbsMap class. 936 1016 ///\relates AbsMap 937 1017 template<typename M> … … 942 1022 ///Converts an STL style functor to a map 943 1023 944 ///This \c concepts::ReadMap "read only map" returns the value 945 ///of a 946 ///given map. 1024 ///This \ref concepts::ReadMap "read only map" returns the value 1025 ///of a given functor. 947 1026 /// 948 1027 ///Template parameters \c K and \c V will become its 949 ///\c Key and \c Value. They must be given explicitely 950 ///because a functor does not provide such typedefs. 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. 951 1032 /// 952 1033 ///Parameter \c F is the type of the used functor. 1034 /// 1035 ///\sa MapFunctor 953 1036 template<typename F, 954 1037 typename K = typename F::argument_type, … … 971 1054 ///This function just returns a \c FunctorMap class. 972 1055 /// 973 ///It is specialized for adaptable function classes and 974 ///c++ functions. 1056 ///This function is specialized for adaptable binary function 1057 ///classes and C++ functions. 1058 /// 975 1059 ///\relates FunctorMap 976 1060 template<typename K, typename V, typename F> inline … … 995 1079 996 1080 ///This class Converts a map to an STL style (unary) functor. 997 /// that is it provides an <tt>operator()</tt> to read its values.1081 ///That is it provides an <tt>operator()</tt> to read its values. 998 1082 /// 999 1083 ///For the sake of convenience it also works as 1000 ///a ususal \ cconcepts::ReadMap "readable map",1084 ///a ususal \ref concepts::ReadMap "readable map", 1001 1085 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist. 1086 /// 1087 ///\sa FunctorMap 1002 1088 template <typename M> 1003 1089 class MapFunctor : public MapBase<typename M::Key, typename M::Value> { … … 1028 1114 } 1029 1115 1030 /// Applies all map setting operations to two maps1031 1032 ///This map has two \ cconcepts::ReadMap "readable map"1116 ///Just readable version of \ref ForkWriteMap 1117 1118 ///This map has two \ref concepts::ReadMap "readable map" 1033 1119 ///parameters and each read request will be passed just to the 1034 ///first map. This class is the just readable map type of the ForkWriteMap. 1035 /// 1036 ///The \c Key and \c Value will be inherited from \c M1. 1037 ///The \c Key and \c Value of M2 must be convertible from those of \c M1. 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 1038 1127 template<typename M1, typename M2> 1039 1128 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { … … 1054 1143 ///Applies all map setting operations to two maps 1055 1144 1056 ///This map has two \ cconcepts::WriteMap "writable map"1145 ///This map has two \ref concepts::WriteMap "writable map" 1057 1146 ///parameters and each write request will be passed to both of them. 1058 ///If \c M1 is also \ cconcepts::ReadMap "readable",1147 ///If \c M1 is also \ref concepts::ReadMap "readable", 1059 1148 ///then the read operations will return the 1060 1149 ///corresponding values of \c M1. 1061 1150 /// 1062 ///The \c Key and \c Value will be inherited from \c M1. 1063 ///The \c Key and \c Value of M2 must be convertible from those of \c M1. 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 1064 1155 template<typename M1, typename M2> 1065 1156 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> { … … 1079 1170 }; 1080 1171 1081 ///Returns an \c ForkMap class 1082 1083 ///This function just returns an \c ForkMap class. 1084 /// 1172 ///Returns a \c ForkMap class 1173 1174 ///This function just returns a \c ForkMap class. 1085 1175 ///\relates ForkMap 1086 1176 template <typename M1, typename M2> … … 1089 1179 } 1090 1180 1181 ///Returns a \c ForkWriteMap class 1182 1183 ///This function just returns a \c ForkWriteMap class. 1184 ///\relates ForkWriteMap 1091 1185 template <typename M1, typename M2> 1092 1186 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) { … … 1100 1194 ///Logical 'not' of a map 1101 1195 1102 ///This bool \ cconcepts::ReadMap "read only map" returns the1103 ///logical negation of 1104 /// value returned by the1105 /// given map. Its \c Key and will be inherited from \c M,1106 /// its Value is <tt>bool</tt>.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 1107 1201 template <typename M> 1108 1202 class NotMap : public MapBase<typename M::Key, bool> { … … 1119 1213 }; 1120 1214 1121 ///Logical 'not' of a map with writing possibility1122 1123 ///This bool \ cconcepts::ReadWriteMap "read-write map" returns the1124 ///logical negation of value returned by the given map. When it is set,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, 1125 1219 ///the opposite value is set to the original map. 1126 ///Its \c Key and will be inherited from \c M, 1127 ///its Value is <tt>bool</tt>. 1220 ///Its \c Key is inherited from \c M, its \c Value is \c bool. 1221 /// 1222 ///\sa NotMap 1128 1223 template <typename M> 1129 1224 class NotWriteMap : public MapBase<typename M::Key, bool> { … … 1151 1246 } 1152 1247 1248 ///Returns a \c NotWriteMap class 1249 1250 ///This function just returns a \c NotWriteMap class. 1251 ///\relates NotWriteMap 1153 1252 template <typename M> 1154 1253 inline NotWriteMap<M> notMap(M &m) { … … 1182 1281 1183 1282 1184 /// \brief Writable bool map for store each true assigned elements. 1185 /// 1186 /// Writable bool map to store each true assigned elements. It will 1187 /// copies all the keys set to true to the given iterator. 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. 1188 1288 /// 1189 1289 /// \note The container of the iterator should contain space 1190 1290 /// for each element. 1191 1291 /// 1192 /// The next example shows how can you write the nodes directly1193 /// t o the standard output.1292 /// The following example shows how you can write the edges found by 1293 /// the \ref Prim algorithm directly to the standard output. 1194 1294 ///\code 1195 1295 /// typedef IdMap<UGraph, UEdge> UEdgeIdMap; … … 1204 1304 /// prim(ugraph, cost, writerMap); 1205 1305 ///\endcode 1306 /// 1307 ///\sa BackInserterBoolMap 1308 ///\sa FrontInserterBoolMap 1309 ///\sa InserterBoolMap 1206 1310 template <typename _Iterator, 1207 1311 typename _Functor = … … 1221 1325 : _begin(it), _end(it), _functor(functor) {} 1222 1326 1223 /// Gives back the given iterator set for the first time.1327 /// Gives back the given iterator set for the first key 1224 1328 Iterator begin() const { 1225 1329 return _begin; 1226 1330 } 1227 1331 1228 /// Gives back the iterator after the last set operation.1332 /// Gives back the the 'after the last' iterator 1229 1333 Iterator end() const { 1230 1334 return _end; 1231 1335 } 1232 1336 1233 /// Setterfunction of the map1337 /// The \c set function of the map 1234 1338 void set(const Key& key, Value value) const { 1235 1339 if (value) { … … 1244 1348 }; 1245 1349 1246 /// \brief Writable bool map for store each true assigned elementsin1350 /// \brief Writable bool map for logging each \c true assigned element in 1247 1351 /// a back insertable container. 1248 1352 /// 1249 /// Writable bool map for store each true assigned elements in a back1250 /// insertable container. It will push back all the keys set to true into1251 /// the container.It can be used to retrieve the items into a standard1252 /// container. The next example shows how can you store the undirected1253 /// edges in a vector with prim algorithm.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. 1254 1358 /// 1255 1359 ///\code … … 1258 1362 /// prim(ugraph, cost, inserter_map); 1259 1363 ///\endcode 1364 /// 1365 ///\sa StoreBoolMap 1366 ///\sa FrontInserterBoolMap 1367 ///\sa InserterBoolMap 1260 1368 template <typename Container, 1261 1369 typename Functor = … … 1263 1371 class BackInserterBoolMap { 1264 1372 public: 1265 typedef typename Container::value_type Key;1373 typedef typename Functor::argument_type Key; 1266 1374 typedef bool Value; 1267 1375 … … 1271 1379 : container(_container), functor(_functor) {} 1272 1380 1273 /// Setterfunction of the map1381 /// The \c set function of the map 1274 1382 void set(const Key& key, Value value) { 1275 1383 if (value) { … … 1283 1391 }; 1284 1392 1285 /// \brief Writable bool map for store each true assigned elementsin1393 /// \brief Writable bool map for logging each \c true assigned element in 1286 1394 /// a front insertable container. 1287 1395 /// 1288 /// Writable bool map for store each true assigned elements in a front 1289 /// insertable container. It will push front all the keys set to \c true into 1290 /// the container. For example see the BackInserterBoolMap. 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 1291 1403 template <typename Container, 1292 1404 typename Functor = … … 1294 1406 class FrontInserterBoolMap { 1295 1407 public: 1296 typedef typename Container::value_type Key;1408 typedef typename Functor::argument_type Key; 1297 1409 typedef bool Value; 1298 1410 … … 1302 1414 : container(_container), functor(_functor) {} 1303 1415 1304 /// Setterfunction of the map1416 /// The \c set function of the map 1305 1417 void set(const Key& key, Value value) { 1306 1418 if (value) { 1307 container.push_front( key);1419 container.push_front(functor(key)); 1308 1420 } 1309 1421 } … … 1314 1426 }; 1315 1427 1316 /// \brief Writable bool map for stor e each true assigned elementsin1428 /// \brief Writable bool map for storing each \c true assigned element in 1317 1429 /// an insertable container. 1318 1430 /// 1319 /// Writable bool map for stor e each true assigned elementsin an1431 /// Writable bool map for storing each \c true assigned element in an 1320 1432 /// insertable container. It will insert all the keys set to \c true into 1321 /// the container. If you want to store the cut edges of the strongly 1433 /// the container. 1434 /// 1435 /// For example, if you want to store the cut arcs of the strongly 1322 1436 /// connected components in a set you can use the next code: 1323 1437 /// … … 1327 1441 /// stronglyConnectedCutEdges(graph, cost, inserter_map); 1328 1442 ///\endcode 1443 /// 1444 ///\sa BackInserterBoolMap 1445 ///\sa FrontInserterBoolMap 1329 1446 template <typename Container, 1330 1447 typename Functor = … … 1335 1452 typedef bool Value; 1336 1453 1337 /// Constructor 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. 1338 1460 InserterBoolMap(Container& _container, typename Container::iterator _it, 1339 1461 const Functor& _functor = Functor()) … … 1341 1463 1342 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. 1343 1470 InserterBoolMap(Container& _container, const Functor& _functor = Functor()) 1344 1471 : container(_container), it(_container.end()), functor(_functor) {} 1345 1472 1346 /// Setterfunction of the map1473 /// The \c set function of the map 1347 1474 void set(const Key& key, Value value) { 1348 1475 if (value) { 1349 it = container.insert(it, key);1476 it = container.insert(it, functor(key)); 1350 1477 ++it; 1351 1478 } … … 1358 1485 }; 1359 1486 1360 /// \brief Fill the true set elements with a given value.1361 /// 1362 /// Writable bool map to fill the elements set to \c true with a given value.1363 /// The value can set1364 /// the container.1365 /// 1366 /// The next code finds the connected components of the undirectedgraph1487 /// \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 1367 1494 /// and stores it in the \c comp map: 1368 1495 ///\code … … 1412 1539 } 1413 1540 1414 /// Setterfunction of the map1541 /// The \c set function of the map 1415 1542 void set(const Key& key, Value value) { 1416 1543 if (value) { … … 1425 1552 1426 1553 1427 /// \brief Writable bool map which stores for each true assigned elements 1428 /// the setting order number. 1429 /// 1430 /// Writable bool map which stores for each true assigned elements 1431 /// the setting order number. It make easy to calculate the leaving 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 1432 1560 /// order of the nodes in the \c Dfs algorithm. 1433 1561 /// … … 1448 1576 ///\endcode 1449 1577 /// 1450 /// The discovering order can be stored a little harderbecause the1578 /// The storing of the discovering order is more difficult because the 1451 1579 /// ReachedMap should be readable in the dfs algorithm but the setting 1452 /// order map is not readable. Now we shoulduse the fork map:1580 /// order map is not readable. Thus we must use the fork map: 1453 1581 /// 1454 1582 ///\code … … 1488 1616 } 1489 1617 1490 /// Setterfunction of the map1618 /// The \c set function of the map 1491 1619 void set(const Key& key, Value value) { 1492 1620 if (value) {
Note: See TracChangeset
for help on using the changeset viewer.