1 // (C) Copyright Jeremy Siek 1999-2001.
2 // Copyright (C) 2006 Trustees of Indiana University
3 // Authors: Douglas Gregor and Jeremy Siek
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)
9 // See http://www.boost.org/libs/property_map for documentation.
11 #ifndef BOOST_PROPERTY_MAP_HPP
12 #define BOOST_PROPERTY_MAP_HPP
14 #include <boost/assert.hpp>
15 #include <boost/config.hpp>
16 #include <boost/static_assert.hpp>
18 #include <boost/detail/iterator.hpp>
19 #include <boost/concept_check.hpp>
20 #include <boost/concept_archetype.hpp>
21 #include <boost/mpl/assert.hpp>
22 #include <boost/mpl/or.hpp>
23 #include <boost/mpl/and.hpp>
24 #include <boost/mpl/has_xxx.hpp>
25 #include <boost/type_traits/is_same.hpp>
29 //=========================================================================
30 // property_traits class
32 BOOST_MPL_HAS_XXX_TRAIT_DEF(key_type)
33 BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
34 BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
35 BOOST_MPL_HAS_XXX_TRAIT_DEF(category)
38 struct is_property_map :
47 template <typename PA>
48 struct default_property_traits {
49 typedef typename PA::key_type key_type;
50 typedef typename PA::value_type value_type;
51 typedef typename PA::reference reference;
52 typedef typename PA::category category;
55 struct null_property_traits {};
57 template <typename PA>
58 struct property_traits :
59 boost::mpl::if_<is_property_map<PA>,
60 default_property_traits<PA>,
61 null_property_traits>::type
65 template <typename PA>
66 struct property_traits {
67 typedef typename PA::key_type key_type;
68 typedef typename PA::value_type value_type;
69 typedef typename PA::reference reference;
70 typedef typename PA::category category;
74 //=========================================================================
75 // property_traits category tags
78 enum ePropertyMapID { READABLE_PA, WRITABLE_PA,
79 READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA,
80 RAND_ACCESS_ITER_PA, LAST_PA };
82 struct readable_property_map_tag { enum { id = detail::READABLE_PA }; };
83 struct writable_property_map_tag { enum { id = detail::WRITABLE_PA }; };
84 struct read_write_property_map_tag :
85 public readable_property_map_tag,
86 public writable_property_map_tag
87 { enum { id = detail::READ_WRITE_PA }; };
89 struct lvalue_property_map_tag : public read_write_property_map_tag
90 { enum { id = detail::LVALUE_PA }; };
92 //=========================================================================
93 // property_traits specialization for pointers
96 struct property_traits<T*> {
97 // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
99 typedef value_type& reference;
100 typedef std::ptrdiff_t key_type;
101 typedef lvalue_property_map_tag category;
104 struct property_traits<const T*> {
105 // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
106 typedef T value_type;
107 typedef const value_type& reference;
108 typedef std::ptrdiff_t key_type;
109 typedef lvalue_property_map_tag category;
112 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
113 // MSVC doesn't have Koenig lookup, so the user has to
114 // do boost::get() anyways, and the using clause
115 // doesn't really work for MSVC.
119 // These need to go in global namespace because Koenig
120 // lookup does not apply to T*.
122 // V must be convertible to T
123 template <class T, class V>
124 inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val; }
127 inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }
129 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
135 //=========================================================================
136 // concept checks for property maps
138 template <class PMap, class Key>
139 struct ReadablePropertyMapConcept
141 typedef typename property_traits<PMap>::key_type key_type;
142 typedef typename property_traits<PMap>::reference reference;
143 typedef typename property_traits<PMap>::category Category;
144 typedef boost::readable_property_map_tag ReadableTag;
146 function_requires< ConvertibleConcept<Category, ReadableTag> >();
152 typename property_traits<PMap>::value_type val;
154 template <typename KeyArchetype, typename ValueArchetype>
155 struct readable_property_map_archetype {
156 typedef KeyArchetype key_type;
157 typedef ValueArchetype value_type;
158 typedef convertible_to_archetype<ValueArchetype> reference;
159 typedef readable_property_map_tag category;
161 template <typename K, typename V>
162 const typename readable_property_map_archetype<K,V>::reference&
163 get(const readable_property_map_archetype<K,V>&,
164 const typename readable_property_map_archetype<K,V>::key_type&)
166 typedef typename readable_property_map_archetype<K,V>::reference R;
167 return static_object<R>::get();
171 template <class PMap, class Key>
172 struct WritablePropertyMapConcept
174 typedef typename property_traits<PMap>::key_type key_type;
175 typedef typename property_traits<PMap>::category Category;
176 typedef boost::writable_property_map_tag WritableTag;
178 function_requires< ConvertibleConcept<Category, WritableTag> >();
183 typename property_traits<PMap>::value_type val;
185 template <typename KeyArchetype, typename ValueArchetype>
186 struct writable_property_map_archetype {
187 typedef KeyArchetype key_type;
188 typedef ValueArchetype value_type;
189 typedef void reference;
190 typedef writable_property_map_tag category;
192 template <typename K, typename V>
193 void put(const writable_property_map_archetype<K,V>&,
194 const typename writable_property_map_archetype<K,V>::key_type&,
195 const typename writable_property_map_archetype<K,V>::value_type&) { }
198 template <class PMap, class Key>
199 struct ReadWritePropertyMapConcept
201 typedef typename property_traits<PMap>::category Category;
202 typedef boost::read_write_property_map_tag ReadWriteTag;
204 function_requires< ReadablePropertyMapConcept<PMap, Key> >();
205 function_requires< WritablePropertyMapConcept<PMap, Key> >();
206 function_requires< ConvertibleConcept<Category, ReadWriteTag> >();
209 template <typename KeyArchetype, typename ValueArchetype>
210 struct read_write_property_map_archetype
211 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
212 public writable_property_map_archetype<KeyArchetype, ValueArchetype>
214 typedef KeyArchetype key_type;
215 typedef ValueArchetype value_type;
216 typedef convertible_to_archetype<ValueArchetype> reference;
217 typedef read_write_property_map_tag category;
221 template <class PMap, class Key>
222 struct LvaluePropertyMapConcept
224 typedef typename property_traits<PMap>::category Category;
225 typedef boost::lvalue_property_map_tag LvalueTag;
226 typedef typename property_traits<PMap>::reference reference;
229 function_requires< ReadablePropertyMapConcept<PMap, Key> >();
230 function_requires< ConvertibleConcept<Category, LvalueTag> >();
232 typedef typename property_traits<PMap>::value_type value_type;
233 BOOST_MPL_ASSERT((boost::mpl::or_<
234 boost::is_same<const value_type&, reference>,
235 boost::is_same<value_type&, reference> >));
237 reference ref = pmap[k];
238 ignore_unused_variable_warning(ref);
243 template <typename KeyArchetype, typename ValueArchetype>
244 struct lvalue_property_map_archetype
245 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>
247 typedef KeyArchetype key_type;
248 typedef ValueArchetype value_type;
249 typedef const ValueArchetype& reference;
250 typedef lvalue_property_map_tag category;
251 const value_type& operator[](const key_type&) const {
252 return static_object<value_type>::get();
256 template <class PMap, class Key>
257 struct Mutable_LvaluePropertyMapConcept
259 typedef typename property_traits<PMap>::category Category;
260 typedef boost::lvalue_property_map_tag LvalueTag;
261 typedef typename property_traits<PMap>::reference reference;
263 boost::function_requires< ReadWritePropertyMapConcept<PMap, Key> >();
264 boost::function_requires<ConvertibleConcept<Category, LvalueTag> >();
266 typedef typename property_traits<PMap>::value_type value_type;
267 BOOST_MPL_ASSERT((boost::is_same<value_type&, reference>));
269 reference ref = pmap[k];
270 ignore_unused_variable_warning(ref);
275 template <typename KeyArchetype, typename ValueArchetype>
276 struct mutable_lvalue_property_map_archetype
277 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
278 public writable_property_map_archetype<KeyArchetype, ValueArchetype>
280 typedef KeyArchetype key_type;
281 typedef ValueArchetype value_type;
282 typedef ValueArchetype& reference;
283 typedef lvalue_property_map_tag category;
284 value_type& operator[](const key_type&) const {
285 return static_object<value_type>::get();
289 template <typename T>
290 struct typed_identity_property_map;
292 // A helper class for constructing a property map
293 // from a class that implements operator[]
295 template <class Reference, class LvaluePropertyMap>
296 struct put_get_helper { };
298 template <class PropertyMap, class Reference, class K>
300 get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
302 Reference v = static_cast<const PropertyMap&>(pa)[k];
305 template <class PropertyMap, class Reference, class K, class V>
307 put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
309 static_cast<const PropertyMap&>(pa)[k] = v;
312 //=========================================================================
313 // Adapter to turn a RandomAccessIterator into a property map
315 template <class RandomAccessIterator,
317 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
320 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
321 , class R = typename std::iterator_traits<RandomAccessIterator>::reference
324 class iterator_property_map
325 : public boost::put_get_helper< R,
326 iterator_property_map<RandomAccessIterator, IndexMap,
330 typedef typename property_traits<IndexMap>::key_type key_type;
331 typedef T value_type;
333 typedef boost::lvalue_property_map_tag category;
335 inline iterator_property_map(
336 RandomAccessIterator cc = RandomAccessIterator(),
337 const IndexMap& _id = IndexMap() )
338 : iter(cc), index(_id) { }
339 inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }
341 RandomAccessIterator iter;
345 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
346 template <class RAIter, class ID>
347 inline iterator_property_map<
349 typename std::iterator_traits<RAIter>::value_type,
350 typename std::iterator_traits<RAIter>::reference>
351 make_iterator_property_map(RAIter iter, ID id) {
352 function_requires< RandomAccessIteratorConcept<RAIter> >();
353 typedef iterator_property_map<
355 typename std::iterator_traits<RAIter>::value_type,
356 typename std::iterator_traits<RAIter>::reference> PA;
360 template <class RAIter, class Value, class ID>
361 inline iterator_property_map<RAIter, ID, Value, Value&>
362 make_iterator_property_map(RAIter iter, ID id, Value) {
363 function_requires< RandomAccessIteratorConcept<RAIter> >();
364 typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;
365 return PMap(iter, id);
368 template <class RandomAccessIterator,
370 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
373 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
374 , class R = typename std::iterator_traits<RandomAccessIterator>::reference
377 class safe_iterator_property_map
378 : public boost::put_get_helper< R,
379 safe_iterator_property_map<RandomAccessIterator, IndexMap,
383 typedef typename property_traits<IndexMap>::key_type key_type;
384 typedef T value_type;
386 typedef boost::lvalue_property_map_tag category;
388 inline safe_iterator_property_map(
389 RandomAccessIterator first,
391 const IndexMap& _id = IndexMap() )
392 : iter(first), n(n_), index(_id) { }
393 inline safe_iterator_property_map() { }
394 inline R operator[](key_type v) const {
395 BOOST_ASSERT(get(index, v) < n);
396 return *(iter + get(index, v)) ;
398 typename property_traits<IndexMap>::value_type size() const { return n; }
400 RandomAccessIterator iter;
401 typename property_traits<IndexMap>::value_type n;
405 template <class RAIter, class ID>
406 inline safe_iterator_property_map<
408 typename boost::detail::iterator_traits<RAIter>::value_type,
409 typename boost::detail::iterator_traits<RAIter>::reference>
410 make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id) {
411 function_requires< RandomAccessIteratorConcept<RAIter> >();
412 typedef safe_iterator_property_map<
414 typename boost::detail::iterator_traits<RAIter>::value_type,
415 typename boost::detail::iterator_traits<RAIter>::reference> PA;
416 return PA(iter, n, id);
418 template <class RAIter, class Value, class ID>
419 inline safe_iterator_property_map<RAIter, ID, Value, Value&>
420 make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id, Value) {
421 function_requires< RandomAccessIteratorConcept<RAIter> >();
422 typedef safe_iterator_property_map<RAIter, ID, Value, Value&> PMap;
423 return PMap(iter, n, id);
426 //=========================================================================
427 // An adaptor to turn a Unique Pair Associative Container like std::map or
428 // std::hash_map into an Lvalue Property Map.
430 template <typename UniquePairAssociativeContainer>
431 class associative_property_map
432 : public boost::put_get_helper<
433 typename UniquePairAssociativeContainer::value_type::second_type&,
434 associative_property_map<UniquePairAssociativeContainer> >
436 typedef UniquePairAssociativeContainer C;
438 typedef typename C::key_type key_type;
439 typedef typename C::value_type::second_type value_type;
440 typedef value_type& reference;
441 typedef lvalue_property_map_tag category;
442 associative_property_map() : m_c(0) { }
443 associative_property_map(C& c) : m_c(&c) { }
444 reference operator[](const key_type& k) const {
451 template <class UniquePairAssociativeContainer>
452 associative_property_map<UniquePairAssociativeContainer>
453 make_assoc_property_map(UniquePairAssociativeContainer& c)
455 return associative_property_map<UniquePairAssociativeContainer>(c);
458 template <typename UniquePairAssociativeContainer>
459 class const_associative_property_map
460 : public boost::put_get_helper<
461 const typename UniquePairAssociativeContainer::value_type::second_type&,
462 const_associative_property_map<UniquePairAssociativeContainer> >
464 typedef UniquePairAssociativeContainer C;
466 typedef typename C::key_type key_type;
467 typedef typename C::value_type::second_type value_type;
468 typedef const value_type& reference;
469 typedef lvalue_property_map_tag category;
470 const_associative_property_map() : m_c(0) { }
471 const_associative_property_map(const C& c) : m_c(&c) { }
472 reference operator[](const key_type& k) const {
473 return m_c->find(k)->second;
479 template <class UniquePairAssociativeContainer>
480 const_associative_property_map<UniquePairAssociativeContainer>
481 make_assoc_property_map(const UniquePairAssociativeContainer& c)
483 return const_associative_property_map<UniquePairAssociativeContainer>(c);
486 //=========================================================================
487 // A property map that always returns the same object by value.
489 template <typename ValueType, typename KeyType = void>
490 class static_property_map :
492 boost::put_get_helper<ValueType,static_property_map<ValueType> >
496 typedef KeyType key_type;
497 typedef ValueType value_type;
498 typedef ValueType reference;
499 typedef readable_property_map_tag category;
500 static_property_map(ValueType v) : value(v) {}
503 inline reference operator[](T) const { return value; }
506 template <typename KeyType, typename ValueType>
507 static_property_map<ValueType, KeyType>
508 make_static_property_map(const ValueType& v) {
509 return static_property_map<ValueType, KeyType>(v);
512 //=========================================================================
513 // A property map that always returns a reference to the same object.
515 template <typename KeyType, typename ValueType>
516 class ref_property_map :
518 boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> >
522 typedef KeyType key_type;
523 typedef ValueType value_type;
524 typedef ValueType& reference;
525 typedef lvalue_property_map_tag category;
526 ref_property_map(ValueType& v) : value(&v) {}
527 ValueType& operator[](key_type const&) const { return *value; }
530 //=========================================================================
531 // A generalized identity property map
532 template <typename T>
533 struct typed_identity_property_map
534 : public boost::put_get_helper<T, typed_identity_property_map<T> >
537 typedef T value_type;
539 typedef boost::readable_property_map_tag category;
541 inline value_type operator[](const key_type& v) const { return v; }
544 //=========================================================================
545 // A property map that applies the identity function to integers
546 typedef typed_identity_property_map<std::size_t> identity_property_map;
548 //=========================================================================
549 // A property map that does not do anything, for
550 // when you have to supply a property map, but don't need it.
552 struct dummy_pmap_reference {
554 dummy_pmap_reference& operator=(const T&) { return *this; }
555 operator int() { return 0; }
558 class dummy_property_map
559 : public boost::put_get_helper<detail::dummy_pmap_reference,
563 typedef void key_type;
564 typedef int value_type;
565 typedef detail::dummy_pmap_reference reference;
566 typedef boost::read_write_property_map_tag category;
567 inline dummy_property_map() : c(0) { }
568 inline dummy_property_map(value_type cc) : c(cc) { }
569 inline dummy_property_map(const dummy_property_map& x)
571 template <class Vertex>
572 inline reference operator[](Vertex) const { return reference(); }
577 // Convert a Readable property map into a function object
578 template <typename PropMap>
579 class property_map_function {
581 typedef typename property_traits<PropMap>::key_type param_type;
583 explicit property_map_function(const PropMap& pm): pm(pm) {}
584 typedef typename property_traits<PropMap>::value_type result_type;
585 result_type operator()(const param_type& k) const {return get(pm, k);}
588 template <typename PropMap>
589 property_map_function<PropMap>
590 make_property_map_function(const PropMap& pm) {
591 return property_map_function<PropMap>(pm);
596 #ifdef BOOST_GRAPH_USE_MPI
597 #include <boost/property_map/parallel/parallel_property_maps.hpp>
600 #include <boost/property_map/vector_property_map.hpp>
602 #endif /* BOOST_PROPERTY_MAP_HPP */