1 // (C) Copyright Jeremy Siek 1999-2001. 2 // Copyright (C) 2006 Trustees of Indiana University 3 // Authors: Douglas Gregor and Jeremy Siek 4 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 9 // See http://www.boost.org/libs/property_map for documentation. 10 11 #ifndef BOOST_PROPERTY_MAP_HPP 12 #define BOOST_PROPERTY_MAP_HPP 13 14 #include <boost/assert.hpp> 15 #include <boost/config.hpp> 16 #include <boost/static_assert.hpp> 17 #include <cstddef> 18 #include <iterator> 19 #include <boost/concept/assert.hpp> 20 #include <boost/concept_check.hpp> 21 #include <boost/concept_archetype.hpp> 22 #include <boost/mpl/assert.hpp> 23 #include <boost/mpl/if.hpp> 24 #include <boost/mpl/or.hpp> 25 #include <boost/mpl/and.hpp> 26 #include <boost/mpl/has_xxx.hpp> 27 #include <boost/type_traits/is_same.hpp> 28 29 namespace boost { 30 31 //========================================================================= 32 // property_traits class 33 34 BOOST_MPL_HAS_XXX_TRAIT_DEF(key_type) 35 BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type) 36 BOOST_MPL_HAS_XXX_TRAIT_DEF(reference) 37 BOOST_MPL_HAS_XXX_TRAIT_DEF(category) 38 39 template<class PA> 40 struct is_property_map : 41 boost::mpl::and_< 42 has_key_type<PA>, 43 has_value_type<PA>, 44 has_reference<PA>, 45 has_category<PA> 46 > 47 {}; 48 49 template <typename PA> 50 struct default_property_traits { 51 typedef typename PA::key_type key_type; 52 typedef typename PA::value_type value_type; 53 typedef typename PA::reference reference; 54 typedef typename PA::category category; 55 }; 56 57 struct null_property_traits {}; 58 59 template <typename PA> 60 struct property_traits : 61 boost::mpl::if_<is_property_map<PA>, 62 default_property_traits<PA>, 63 null_property_traits>::type 64 {}; 65 66 #if 0 67 template <typename PA> 68 struct property_traits { 69 typedef typename PA::key_type key_type; 70 typedef typename PA::value_type value_type; 71 typedef typename PA::reference reference; 72 typedef typename PA::category category; 73 }; 74 #endif 75 76 //========================================================================= 77 // property_traits category tags 78 79 namespace detail { 80 enum ePropertyMapID { READABLE_PA, WRITABLE_PA, 81 READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA, 82 RAND_ACCESS_ITER_PA, LAST_PA }; 83 } 84 struct readable_property_map_tag { enum { id = detail::READABLE_PA }; }; 85 struct writable_property_map_tag { enum { id = detail::WRITABLE_PA }; }; 86 struct read_write_property_map_tag : 87 public readable_property_map_tag, 88 public writable_property_map_tag 89 { enum { id = detail::READ_WRITE_PA }; }; 90 91 struct lvalue_property_map_tag : public read_write_property_map_tag 92 { enum { id = detail::LVALUE_PA }; }; 93 94 //========================================================================= 95 // property_traits specialization for pointers 96 97 template <class T> 98 struct property_traits<T*> { 99 // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated"); 100 typedef T value_type; 101 typedef value_type& reference; 102 typedef std::ptrdiff_t key_type; 103 typedef lvalue_property_map_tag category; 104 }; 105 template <class T> 106 struct property_traits<const T*> { 107 // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated"); 108 typedef T value_type; 109 typedef const value_type& reference; 110 typedef std::ptrdiff_t key_type; 111 typedef lvalue_property_map_tag category; 112 }; 113 114 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) 115 // MSVC doesn't have Koenig lookup, so the user has to 116 // do boost::get() anyways, and the using clause 117 // doesn't really work for MSVC. 118 } // namespace boost 119 #endif 120 121 // These need to go in global namespace because Koenig 122 // lookup does not apply to T*. 123 124 // V must be convertible to T 125 template <class T, class V> put(T * pa,std::ptrdiff_t k,const V & val)126 inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val; } 127 128 template <class T> get(const T * pa,std::ptrdiff_t k)129 inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; } 130 131 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) 132 namespace boost { 133 using ::put; 134 using ::get; 135 #endif 136 137 //========================================================================= 138 // concept checks for property maps 139 140 template <class PMap, class Key> 141 struct ReadablePropertyMapConcept 142 { 143 typedef typename property_traits<PMap>::key_type key_type; 144 typedef typename property_traits<PMap>::reference reference; 145 typedef typename property_traits<PMap>::category Category; 146 typedef boost::readable_property_map_tag ReadableTag; constraintsboost::ReadablePropertyMapConcept147 void constraints() { 148 BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, ReadableTag>)); 149 150 val = get(pmap, k); 151 } 152 PMap pmap; 153 Key k; 154 typename property_traits<PMap>::value_type val; 155 }; 156 template <typename KeyArchetype, typename ValueArchetype> 157 struct readable_property_map_archetype { 158 typedef KeyArchetype key_type; 159 typedef ValueArchetype value_type; 160 typedef convertible_to_archetype<ValueArchetype> reference; 161 typedef readable_property_map_tag category; 162 }; 163 template <typename K, typename V> 164 const typename readable_property_map_archetype<K,V>::reference& get(const readable_property_map_archetype<K,V> &,const typename readable_property_map_archetype<K,V>::key_type &)165 get(const readable_property_map_archetype<K,V>&, 166 const typename readable_property_map_archetype<K,V>::key_type&) 167 { 168 typedef typename readable_property_map_archetype<K,V>::reference R; 169 return static_object<R>::get(); 170 } 171 172 173 template <class PMap, class Key> 174 struct WritablePropertyMapConcept 175 { 176 typedef typename property_traits<PMap>::key_type key_type; 177 typedef typename property_traits<PMap>::category Category; 178 typedef boost::writable_property_map_tag WritableTag; constraintsboost::WritablePropertyMapConcept179 void constraints() { 180 BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, WritableTag>)); 181 put(pmap, k, val); 182 } 183 PMap pmap; 184 Key k; 185 typename property_traits<PMap>::value_type val; 186 }; 187 template <typename KeyArchetype, typename ValueArchetype> 188 struct writable_property_map_archetype { 189 typedef KeyArchetype key_type; 190 typedef ValueArchetype value_type; 191 typedef void reference; 192 typedef writable_property_map_tag category; 193 }; 194 template <typename K, typename V> put(const writable_property_map_archetype<K,V> &,const typename writable_property_map_archetype<K,V>::key_type &,const typename writable_property_map_archetype<K,V>::value_type &)195 void put(const writable_property_map_archetype<K,V>&, 196 const typename writable_property_map_archetype<K,V>::key_type&, 197 const typename writable_property_map_archetype<K,V>::value_type&) { } 198 199 200 template <class PMap, class Key> 201 struct ReadWritePropertyMapConcept 202 { 203 typedef typename property_traits<PMap>::category Category; 204 typedef boost::read_write_property_map_tag ReadWriteTag; constraintsboost::ReadWritePropertyMapConcept205 void constraints() { 206 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<PMap, Key>)); 207 BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept<PMap, Key>)); 208 BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, ReadWriteTag>)); 209 } 210 }; 211 template <typename KeyArchetype, typename ValueArchetype> 212 struct read_write_property_map_archetype 213 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>, 214 public writable_property_map_archetype<KeyArchetype, ValueArchetype> 215 { 216 typedef KeyArchetype key_type; 217 typedef ValueArchetype value_type; 218 typedef convertible_to_archetype<ValueArchetype> reference; 219 typedef read_write_property_map_tag category; 220 }; 221 222 223 template <class PMap, class Key> 224 struct LvaluePropertyMapConcept 225 { 226 typedef typename property_traits<PMap>::category Category; 227 typedef boost::lvalue_property_map_tag LvalueTag; 228 typedef typename property_traits<PMap>::reference reference; 229 constraintsboost::LvaluePropertyMapConcept230 void constraints() { 231 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<PMap, Key>)); 232 BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, LvalueTag>)); 233 234 typedef typename property_traits<PMap>::value_type value_type; 235 BOOST_MPL_ASSERT((boost::mpl::or_< 236 boost::is_same<const value_type&, reference>, 237 boost::is_same<value_type&, reference> >)); 238 239 reference ref = pmap[k]; 240 ignore_unused_variable_warning(ref); 241 } 242 PMap pmap; 243 Key k; 244 }; 245 template <typename KeyArchetype, typename ValueArchetype> 246 struct lvalue_property_map_archetype 247 : public readable_property_map_archetype<KeyArchetype, ValueArchetype> 248 { 249 typedef KeyArchetype key_type; 250 typedef ValueArchetype value_type; 251 typedef const ValueArchetype& reference; 252 typedef lvalue_property_map_tag category; operator []boost::lvalue_property_map_archetype253 const value_type& operator[](const key_type&) const { 254 return static_object<value_type>::get(); 255 } 256 }; 257 258 template <class PMap, class Key> 259 struct Mutable_LvaluePropertyMapConcept 260 { 261 typedef typename property_traits<PMap>::category Category; 262 typedef boost::lvalue_property_map_tag LvalueTag; 263 typedef typename property_traits<PMap>::reference reference; constraintsboost::Mutable_LvaluePropertyMapConcept264 void constraints() { 265 BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<PMap, Key>)); 266 BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, LvalueTag>)); 267 268 typedef typename property_traits<PMap>::value_type value_type; 269 BOOST_MPL_ASSERT((boost::is_same<value_type&, reference>)); 270 271 reference ref = pmap[k]; 272 ignore_unused_variable_warning(ref); 273 } 274 PMap pmap; 275 Key k; 276 }; 277 template <typename KeyArchetype, typename ValueArchetype> 278 struct mutable_lvalue_property_map_archetype 279 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>, 280 public writable_property_map_archetype<KeyArchetype, ValueArchetype> 281 { 282 typedef KeyArchetype key_type; 283 typedef ValueArchetype value_type; 284 typedef ValueArchetype& reference; 285 typedef lvalue_property_map_tag category; operator []boost::mutable_lvalue_property_map_archetype286 value_type& operator[](const key_type&) const { 287 return static_object<value_type>::get(); 288 } 289 }; 290 291 template <typename T> 292 struct typed_identity_property_map; 293 294 // A helper class for constructing a property map 295 // from a class that implements operator[] 296 297 template <class Reference, class LvaluePropertyMap> 298 struct put_get_helper { }; 299 300 template <class PropertyMap, class Reference, class K> 301 inline Reference get(const put_get_helper<Reference,PropertyMap> & pa,const K & k)302 get(const put_get_helper<Reference, PropertyMap>& pa, const K& k) 303 { 304 Reference v = static_cast<const PropertyMap&>(pa)[k]; 305 return v; 306 } 307 template <class PropertyMap, class Reference, class K, class V> 308 inline void put(const put_get_helper<Reference,PropertyMap> & pa,K k,const V & v)309 put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v) 310 { 311 static_cast<const PropertyMap&>(pa)[k] = v; 312 } 313 314 //========================================================================= 315 // Adapter to turn a RandomAccessIterator into a property map 316 317 template <class RandomAccessIterator, 318 class IndexMap 319 #ifdef BOOST_NO_STD_ITERATOR_TRAITS 320 , class T, class R 321 #else 322 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type 323 , class R = typename std::iterator_traits<RandomAccessIterator>::reference 324 #endif 325 > 326 class iterator_property_map 327 : public boost::put_get_helper< R, 328 iterator_property_map<RandomAccessIterator, IndexMap, 329 T, R> > 330 { 331 public: 332 typedef typename property_traits<IndexMap>::key_type key_type; 333 typedef T value_type; 334 typedef R reference; 335 typedef boost::lvalue_property_map_tag category; 336 iterator_property_map(RandomAccessIterator cc=RandomAccessIterator (),const IndexMap & _id=IndexMap ())337 inline iterator_property_map( 338 RandomAccessIterator cc = RandomAccessIterator(), 339 const IndexMap& _id = IndexMap() ) 340 : iter(cc), index(_id) { } operator [](key_type v) const341 inline R operator[](key_type v) const { return *(iter + get(index, v)) ; } 342 protected: 343 RandomAccessIterator iter; 344 IndexMap index; 345 }; 346 347 #if !defined BOOST_NO_STD_ITERATOR_TRAITS 348 template <class RAIter, class ID> 349 inline iterator_property_map< 350 RAIter, ID, 351 typename std::iterator_traits<RAIter>::value_type, 352 typename std::iterator_traits<RAIter>::reference> make_iterator_property_map(RAIter iter,ID id)353 make_iterator_property_map(RAIter iter, ID id) { 354 BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>)); 355 typedef iterator_property_map< 356 RAIter, ID, 357 typename std::iterator_traits<RAIter>::value_type, 358 typename std::iterator_traits<RAIter>::reference> PA; 359 return PA(iter, id); 360 } 361 #endif 362 template <class RAIter, class Value, class ID> 363 inline iterator_property_map<RAIter, ID, Value, Value&> make_iterator_property_map(RAIter iter,ID id,Value)364 make_iterator_property_map(RAIter iter, ID id, Value) { 365 BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>)); 366 typedef iterator_property_map<RAIter, ID, Value, Value&> PMap; 367 return PMap(iter, id); 368 } 369 370 template <class RandomAccessIterator, 371 class IndexMap 372 #ifdef BOOST_NO_STD_ITERATOR_TRAITS 373 , class T, class R 374 #else 375 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type 376 , class R = typename std::iterator_traits<RandomAccessIterator>::reference 377 #endif 378 > 379 class safe_iterator_property_map 380 : public boost::put_get_helper< R, 381 safe_iterator_property_map<RandomAccessIterator, IndexMap, 382 T, R> > 383 { 384 public: 385 typedef typename property_traits<IndexMap>::key_type key_type; 386 typedef T value_type; 387 typedef R reference; 388 typedef boost::lvalue_property_map_tag category; 389 safe_iterator_property_map(RandomAccessIterator first,std::size_t n_=0,const IndexMap & _id=IndexMap ())390 inline safe_iterator_property_map( 391 RandomAccessIterator first, 392 std::size_t n_ = 0, 393 const IndexMap& _id = IndexMap() ) 394 : iter(first), n(n_), index(_id) { } safe_iterator_property_map()395 inline safe_iterator_property_map() { } operator [](key_type v) const396 inline R operator[](key_type v) const { 397 BOOST_ASSERT(get(index, v) < n); 398 return *(iter + get(index, v)) ; 399 } size() const400 typename property_traits<IndexMap>::value_type size() const { return n; } 401 protected: 402 RandomAccessIterator iter; 403 typename property_traits<IndexMap>::value_type n; 404 IndexMap index; 405 }; 406 407 template <class RAIter, class ID> 408 inline safe_iterator_property_map< 409 RAIter, ID, 410 typename std::iterator_traits<RAIter>::value_type, 411 typename std::iterator_traits<RAIter>::reference> make_safe_iterator_property_map(RAIter iter,std::size_t n,ID id)412 make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id) { 413 BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>)); 414 typedef safe_iterator_property_map< 415 RAIter, ID, 416 typename std::iterator_traits<RAIter>::value_type, 417 typename std::iterator_traits<RAIter>::reference> PA; 418 return PA(iter, n, id); 419 } 420 template <class RAIter, class Value, class ID> 421 inline safe_iterator_property_map<RAIter, ID, Value, Value&> make_safe_iterator_property_map(RAIter iter,std::size_t n,ID id,Value)422 make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id, Value) { 423 BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>)); 424 typedef safe_iterator_property_map<RAIter, ID, Value, Value&> PMap; 425 return PMap(iter, n, id); 426 } 427 428 //========================================================================= 429 // An adaptor to turn a Unique Pair Associative Container like std::map or 430 // std::hash_map into an Lvalue Property Map. 431 432 template <typename UniquePairAssociativeContainer> 433 class associative_property_map 434 : public boost::put_get_helper< 435 typename UniquePairAssociativeContainer::value_type::second_type&, 436 associative_property_map<UniquePairAssociativeContainer> > 437 { 438 typedef UniquePairAssociativeContainer C; 439 public: 440 typedef typename C::key_type key_type; 441 typedef typename C::value_type::second_type value_type; 442 typedef value_type& reference; 443 typedef lvalue_property_map_tag category; associative_property_map()444 associative_property_map() : m_c(0) { } associative_property_map(C & c)445 associative_property_map(C& c) : m_c(&c) { } operator [](const key_type & k) const446 reference operator[](const key_type& k) const { 447 return (*m_c)[k]; 448 } 449 private: 450 C* m_c; 451 }; 452 453 template <class UniquePairAssociativeContainer> 454 associative_property_map<UniquePairAssociativeContainer> make_assoc_property_map(UniquePairAssociativeContainer & c)455 make_assoc_property_map(UniquePairAssociativeContainer& c) 456 { 457 return associative_property_map<UniquePairAssociativeContainer>(c); 458 } 459 460 template <typename UniquePairAssociativeContainer> 461 class const_associative_property_map 462 : public boost::put_get_helper< 463 const typename UniquePairAssociativeContainer::value_type::second_type&, 464 const_associative_property_map<UniquePairAssociativeContainer> > 465 { 466 typedef UniquePairAssociativeContainer C; 467 public: 468 typedef typename C::key_type key_type; 469 typedef typename C::value_type::second_type value_type; 470 typedef const value_type& reference; 471 typedef lvalue_property_map_tag category; const_associative_property_map()472 const_associative_property_map() : m_c(0) { } const_associative_property_map(const C & c)473 const_associative_property_map(const C& c) : m_c(&c) { } operator [](const key_type & k) const474 reference operator[](const key_type& k) const { 475 return m_c->find(k)->second; 476 } 477 private: 478 C const* m_c; 479 }; 480 481 template <class UniquePairAssociativeContainer> 482 const_associative_property_map<UniquePairAssociativeContainer> make_assoc_property_map(const UniquePairAssociativeContainer & c)483 make_assoc_property_map(const UniquePairAssociativeContainer& c) 484 { 485 return const_associative_property_map<UniquePairAssociativeContainer>(c); 486 } 487 488 //========================================================================= 489 // A property map that always returns the same object by value. 490 // 491 template <typename ValueType, typename KeyType = void> 492 class static_property_map : 493 public 494 boost::put_get_helper<ValueType,static_property_map<ValueType> > 495 { 496 ValueType value; 497 public: 498 typedef KeyType key_type; 499 typedef ValueType value_type; 500 typedef ValueType reference; 501 typedef readable_property_map_tag category; static_property_map(ValueType v)502 static_property_map(ValueType v) : value(v) {} 503 504 template<typename T> operator [](T) const505 inline reference operator[](T) const { return value; } 506 }; 507 508 template <typename KeyType, typename ValueType> 509 static_property_map<ValueType, KeyType> make_static_property_map(const ValueType & v)510 make_static_property_map(const ValueType& v) { 511 return static_property_map<ValueType, KeyType>(v); 512 } 513 514 //========================================================================= 515 // A property map that always returns a reference to the same object. 516 // 517 template <typename KeyType, typename ValueType> 518 class ref_property_map : 519 public 520 boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> > 521 { 522 ValueType* value; 523 public: 524 typedef KeyType key_type; 525 typedef ValueType value_type; 526 typedef ValueType& reference; 527 typedef lvalue_property_map_tag category; ref_property_map(ValueType & v)528 ref_property_map(ValueType& v) : value(&v) {} operator [](key_type const &) const529 ValueType& operator[](key_type const&) const { return *value; } 530 }; 531 532 //========================================================================= 533 // A generalized identity property map 534 template <typename T> 535 struct typed_identity_property_map 536 : public boost::put_get_helper<T, typed_identity_property_map<T> > 537 { 538 typedef T key_type; 539 typedef T value_type; 540 typedef T reference; 541 typedef boost::readable_property_map_tag category; 542 operator []boost::typed_identity_property_map543 inline value_type operator[](const key_type& v) const { return v; } 544 }; 545 546 //========================================================================= 547 // A property map that applies the identity function to integers 548 typedef typed_identity_property_map<std::size_t> identity_property_map; 549 550 //========================================================================= 551 // A property map that does not do anything, for 552 // when you have to supply a property map, but don't need it. 553 namespace detail { 554 struct dummy_pmap_reference { 555 template <class T> operator =boost::detail::dummy_pmap_reference556 dummy_pmap_reference& operator=(const T&) { return *this; } operator intboost::detail::dummy_pmap_reference557 operator int() { return 0; } 558 }; 559 } 560 class dummy_property_map 561 : public boost::put_get_helper<detail::dummy_pmap_reference, 562 dummy_property_map > 563 { 564 public: 565 typedef void key_type; 566 typedef int value_type; 567 typedef detail::dummy_pmap_reference reference; 568 typedef boost::read_write_property_map_tag category; dummy_property_map()569 inline dummy_property_map() : c(0) { } dummy_property_map(value_type cc)570 inline dummy_property_map(value_type cc) : c(cc) { } dummy_property_map(const dummy_property_map & x)571 inline dummy_property_map(const dummy_property_map& x) 572 : c(x.c) { } 573 template <class Vertex> operator [](Vertex) const574 inline reference operator[](Vertex) const { return reference(); } 575 protected: 576 value_type c; 577 }; 578 579 // Convert a Readable property map into a function object 580 template <typename PropMap> 581 class property_map_function { 582 PropMap pm; 583 typedef typename property_traits<PropMap>::key_type param_type; 584 public: property_map_function(const PropMap & pm)585 explicit property_map_function(const PropMap& pm): pm(pm) {} 586 typedef typename property_traits<PropMap>::value_type result_type; operator ()(const param_type & k) const587 result_type operator()(const param_type& k) const {return get(pm, k);} 588 }; 589 590 template <typename PropMap> 591 property_map_function<PropMap> make_property_map_function(const PropMap & pm)592 make_property_map_function(const PropMap& pm) { 593 return property_map_function<PropMap>(pm); 594 } 595 596 } // namespace boost 597 598 #ifdef BOOST_GRAPH_USE_MPI 599 #include <boost/property_map/parallel/parallel_property_maps.hpp> 600 #endif 601 602 #include <boost/property_map/vector_property_map.hpp> 603 604 #endif /* BOOST_PROPERTY_MAP_HPP */ 605 606