1 // (C) Copyright Jeremy Siek 1999-2001.
2 // Distributed under the Boost Software License, Version 1.0. (See
3 // accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
6 // See http://www.boost.org/libs/property_map for documentation.
8 #ifndef BOOST_PROPERTY_MAP_HPP
9 #define BOOST_PROPERTY_MAP_HPP
12 #include <boost/config.hpp>
13 #include <boost/pending/cstddef.hpp>
14 #include <boost/detail/iterator.hpp>
15 #include <boost/concept_check.hpp>
16 #include <boost/concept_archetype.hpp>
17 #include <boost/mpl/assert.hpp>
18 #include <boost/mpl/or.hpp>
19 #include <boost/type_traits/is_same.hpp>
23 //=========================================================================
24 // property_traits class
26 template <typename PA>
27 struct property_traits {
28 typedef typename PA::key_type key_type;
29 typedef typename PA::value_type value_type;
30 typedef typename PA::reference reference;
31 typedef typename PA::category category;
34 //=========================================================================
35 // property_traits category tags
38 enum ePropertyMapID { READABLE_PA, WRITABLE_PA,
39 READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA,
40 RAND_ACCESS_ITER_PA, LAST_PA };
42 struct readable_property_map_tag { enum { id = detail::READABLE_PA }; };
43 struct writable_property_map_tag { enum { id = detail::WRITABLE_PA }; };
44 struct read_write_property_map_tag :
45 public readable_property_map_tag,
46 public writable_property_map_tag
47 { enum { id = detail::READ_WRITE_PA }; };
49 struct lvalue_property_map_tag : public read_write_property_map_tag
50 { enum { id = detail::LVALUE_PA }; };
52 //=========================================================================
53 // property_traits specialization for pointers
55 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
56 // The user will just have to create their own specializations for
57 // other pointers types if the compiler does not have partial
58 // specializations. Sorry!
59 #define BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(TYPE) \
61 struct property_traits<TYPE*> { \
62 typedef TYPE value_type; \
63 typedef value_type& reference; \
64 typedef std::ptrdiff_t key_type; \
65 typedef lvalue_property_map_tag category; \
68 struct property_traits<const TYPE*> { \
69 typedef TYPE value_type; \
70 typedef const value_type& reference; \
71 typedef std::ptrdiff_t key_type; \
72 typedef lvalue_property_map_tag category; \
75 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(long);
76 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned long);
77 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(int);
78 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned int);
79 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(short);
80 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned short);
81 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(char);
82 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned char);
83 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(signed char);
84 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(bool);
85 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(float);
86 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(double);
87 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(long double);
89 // This may need to be turned off for some older compilers that don't have
90 // wchar_t intrinsically.
91 # ifndef BOOST_NO_INTRINSIC_WCHAR_T
93 struct property_traits<wchar_t*> {
94 typedef wchar_t value_type;
95 typedef value_type& reference;
96 typedef std::ptrdiff_t key_type;
97 typedef lvalue_property_map_tag category;
100 struct property_traits<const wchar_t*> {
101 typedef wchar_t value_type;
102 typedef const value_type& reference;
103 typedef std::ptrdiff_t key_type;
104 typedef lvalue_property_map_tag category;
110 struct property_traits<T*> {
111 typedef T value_type;
112 typedef value_type& reference;
113 typedef std::ptrdiff_t key_type;
114 typedef lvalue_property_map_tag category;
117 struct property_traits<const T*> {
118 typedef T value_type;
119 typedef const value_type& reference;
120 typedef std::ptrdiff_t key_type;
121 typedef lvalue_property_map_tag category;
125 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
126 // MSVC doesn't have Koenig lookup, so the user has to
127 // do boost::get() anyways, and the using clause
128 // doesn't really work for MSVC.
132 // These need to go in global namespace because Koenig
133 // lookup does not apply to T*.
135 // V must be convertible to T
136 template <class T, class V>
137 inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val; }
140 inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }
142 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
148 //=========================================================================
149 // concept checks for property maps
151 template <class PMap, class Key>
152 struct ReadablePropertyMapConcept
154 typedef typename property_traits<PMap>::key_type key_type;
155 typedef typename property_traits<PMap>::reference reference;
156 typedef typename property_traits<PMap>::category Category;
157 typedef boost::readable_property_map_tag ReadableTag;
159 function_requires< ConvertibleConcept<Category, ReadableTag> >();
165 typename property_traits<PMap>::value_type val;
167 template <typename KeyArchetype, typename ValueArchetype>
168 struct readable_property_map_archetype {
169 typedef KeyArchetype key_type;
170 typedef ValueArchetype value_type;
171 typedef convertible_to_archetype<ValueArchetype> reference;
172 typedef readable_property_map_tag category;
174 template <typename K, typename V>
175 const typename readable_property_map_archetype<K,V>::reference&
176 get(const readable_property_map_archetype<K,V>&,
177 const typename readable_property_map_archetype<K,V>::key_type&)
179 typedef typename readable_property_map_archetype<K,V>::reference R;
180 return static_object<R>::get();
184 template <class PMap, class Key>
185 struct WritablePropertyMapConcept
187 typedef typename property_traits<PMap>::key_type key_type;
188 typedef typename property_traits<PMap>::category Category;
189 typedef boost::writable_property_map_tag WritableTag;
191 function_requires< ConvertibleConcept<Category, WritableTag> >();
196 typename property_traits<PMap>::value_type val;
198 template <typename KeyArchetype, typename ValueArchetype>
199 struct writable_property_map_archetype {
200 typedef KeyArchetype key_type;
201 typedef ValueArchetype value_type;
202 typedef void reference;
203 typedef writable_property_map_tag category;
205 template <typename K, typename V>
206 void put(const writable_property_map_archetype<K,V>&,
207 const typename writable_property_map_archetype<K,V>::key_type&,
208 const typename writable_property_map_archetype<K,V>::value_type&) { }
211 template <class PMap, class Key>
212 struct ReadWritePropertyMapConcept
214 typedef typename property_traits<PMap>::category Category;
215 typedef boost::read_write_property_map_tag ReadWriteTag;
217 function_requires< ReadablePropertyMapConcept<PMap, Key> >();
218 function_requires< WritablePropertyMapConcept<PMap, Key> >();
219 function_requires< ConvertibleConcept<Category, ReadWriteTag> >();
222 template <typename KeyArchetype, typename ValueArchetype>
223 struct read_write_property_map_archetype
224 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
225 public writable_property_map_archetype<KeyArchetype, ValueArchetype>
227 typedef KeyArchetype key_type;
228 typedef ValueArchetype value_type;
229 typedef convertible_to_archetype<ValueArchetype> reference;
230 typedef read_write_property_map_tag category;
234 template <class PMap, class Key>
235 struct LvaluePropertyMapConcept
237 typedef typename property_traits<PMap>::category Category;
238 typedef boost::lvalue_property_map_tag LvalueTag;
239 typedef typename property_traits<PMap>::reference reference;
242 function_requires< ReadablePropertyMapConcept<PMap, Key> >();
243 function_requires< ConvertibleConcept<Category, LvalueTag> >();
245 typedef typename property_traits<PMap>::value_type value_type;
246 BOOST_MPL_ASSERT((boost::mpl::or_<
247 boost::is_same<const value_type&, reference>,
248 boost::is_same<value_type&, reference> >));
250 reference ref = pmap[k];
251 ignore_unused_variable_warning(ref);
256 template <typename KeyArchetype, typename ValueArchetype>
257 struct lvalue_property_map_archetype
258 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>
260 typedef KeyArchetype key_type;
261 typedef ValueArchetype value_type;
262 typedef const ValueArchetype& reference;
263 typedef lvalue_property_map_tag category;
264 const value_type& operator[](const key_type&) const {
265 return static_object<value_type>::get();
269 template <class PMap, class Key>
270 struct Mutable_LvaluePropertyMapConcept
272 typedef typename property_traits<PMap>::category Category;
273 typedef boost::lvalue_property_map_tag LvalueTag;
274 typedef typename property_traits<PMap>::reference reference;
276 boost::function_requires< ReadWritePropertyMapConcept<PMap, Key> >();
277 boost::function_requires<ConvertibleConcept<Category, LvalueTag> >();
279 typedef typename property_traits<PMap>::value_type value_type;
280 BOOST_MPL_ASSERT((boost::is_same<value_type&, reference>));
282 reference ref = pmap[k];
283 ignore_unused_variable_warning(ref);
288 template <typename KeyArchetype, typename ValueArchetype>
289 struct mutable_lvalue_property_map_archetype
290 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
291 public writable_property_map_archetype<KeyArchetype, ValueArchetype>
293 typedef KeyArchetype key_type;
294 typedef ValueArchetype value_type;
295 typedef ValueArchetype& reference;
296 typedef lvalue_property_map_tag category;
297 value_type& operator[](const key_type&) const {
298 return static_object<value_type>::get();
302 struct identity_property_map;
304 // A helper class for constructing a property map
305 // from a class that implements operator[]
307 template <class Reference, class LvaluePropertyMap>
308 struct put_get_helper { };
310 template <class PropertyMap, class Reference, class K>
312 get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
314 Reference v = static_cast<const PropertyMap&>(pa)[k];
317 template <class PropertyMap, class Reference, class K, class V>
319 put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
321 static_cast<const PropertyMap&>(pa)[k] = v;
324 //=========================================================================
325 // Adapter to turn a RandomAccessIterator into a property map
327 template <class RandomAccessIterator,
329 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
332 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
333 , class R = typename std::iterator_traits<RandomAccessIterator>::reference
336 class iterator_property_map
337 : public boost::put_get_helper< R,
338 iterator_property_map<RandomAccessIterator, IndexMap,
342 typedef typename property_traits<IndexMap>::key_type key_type;
343 typedef T value_type;
345 typedef boost::lvalue_property_map_tag category;
347 inline iterator_property_map(
348 RandomAccessIterator cc = RandomAccessIterator(),
349 const IndexMap& _id = IndexMap() )
350 : iter(cc), index(_id) { }
351 inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }
353 RandomAccessIterator iter;
357 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
358 template <class RAIter, class ID>
359 inline iterator_property_map<
361 typename std::iterator_traits<RAIter>::value_type,
362 typename std::iterator_traits<RAIter>::reference>
363 make_iterator_property_map(RAIter iter, ID id) {
364 function_requires< RandomAccessIteratorConcept<RAIter> >();
365 typedef iterator_property_map<
367 typename std::iterator_traits<RAIter>::value_type,
368 typename std::iterator_traits<RAIter>::reference> PA;
372 template <class RAIter, class Value, class ID>
373 inline iterator_property_map<RAIter, ID, Value, Value&>
374 make_iterator_property_map(RAIter iter, ID id, Value) {
375 function_requires< RandomAccessIteratorConcept<RAIter> >();
376 typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;
377 return PMap(iter, id);
380 template <class RandomAccessIterator,
382 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
385 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
386 , class R = typename std::iterator_traits<RandomAccessIterator>::reference
389 class safe_iterator_property_map
390 : public boost::put_get_helper< R,
391 safe_iterator_property_map<RandomAccessIterator, IndexMap,
395 typedef typename property_traits<IndexMap>::key_type key_type;
396 typedef T value_type;
398 typedef boost::lvalue_property_map_tag category;
400 inline safe_iterator_property_map(
401 RandomAccessIterator first,
403 const IndexMap& _id = IndexMap() )
404 : iter(first), n(n_), index(_id) { }
405 inline safe_iterator_property_map() { }
406 inline R operator[](key_type v) const {
407 assert(get(index, v) < n);
408 return *(iter + get(index, v)) ;
410 typename property_traits<IndexMap>::value_type size() const { return n; }
412 RandomAccessIterator iter;
413 typename property_traits<IndexMap>::value_type n;
417 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
418 template <class RAIter, class ID>
419 inline safe_iterator_property_map<
421 typename boost::detail::iterator_traits<RAIter>::value_type,
422 typename boost::detail::iterator_traits<RAIter>::reference>
423 make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id) {
424 function_requires< RandomAccessIteratorConcept<RAIter> >();
425 typedef safe_iterator_property_map<
427 typename boost::detail::iterator_traits<RAIter>::value_type,
428 typename boost::detail::iterator_traits<RAIter>::reference> PA;
429 return PA(iter, n, id);
432 template <class RAIter, class Value, class ID>
433 inline safe_iterator_property_map<RAIter, ID, Value, Value&>
434 make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id, Value) {
435 function_requires< RandomAccessIteratorConcept<RAIter> >();
436 typedef safe_iterator_property_map<RAIter, ID, Value, Value&> PMap;
437 return PMap(iter, n, id);
440 //=========================================================================
441 // An adaptor to turn a Unique Pair Associative Container like std::map or
442 // std::hash_map into an Lvalue Property Map.
444 template <typename UniquePairAssociativeContainer>
445 class associative_property_map
446 : public boost::put_get_helper<
447 typename UniquePairAssociativeContainer::value_type::second_type&,
448 associative_property_map<UniquePairAssociativeContainer> >
450 typedef UniquePairAssociativeContainer C;
452 typedef typename C::key_type key_type;
453 typedef typename C::value_type::second_type value_type;
454 typedef value_type& reference;
455 typedef lvalue_property_map_tag category;
456 associative_property_map() : m_c(0) { }
457 associative_property_map(C& c) : m_c(&c) { }
458 reference operator[](const key_type& k) const {
465 template <class UniquePairAssociativeContainer>
466 associative_property_map<UniquePairAssociativeContainer>
467 make_assoc_property_map(UniquePairAssociativeContainer& c)
469 return associative_property_map<UniquePairAssociativeContainer>(c);
472 template <typename UniquePairAssociativeContainer>
473 class const_associative_property_map
474 : public boost::put_get_helper<
475 const typename UniquePairAssociativeContainer::value_type::second_type&,
476 const_associative_property_map<UniquePairAssociativeContainer> >
478 typedef UniquePairAssociativeContainer C;
480 typedef typename C::key_type key_type;
481 typedef typename C::value_type::second_type value_type;
482 typedef const value_type& reference;
483 typedef lvalue_property_map_tag category;
484 const_associative_property_map() : m_c(0) { }
485 const_associative_property_map(const C& c) : m_c(&c) { }
486 reference operator[](const key_type& k) const {
487 return m_c->find(k)->second;
493 template <class UniquePairAssociativeContainer>
494 const_associative_property_map<UniquePairAssociativeContainer>
495 make_assoc_property_map(const UniquePairAssociativeContainer& c)
497 return const_associative_property_map<UniquePairAssociativeContainer>(c);
500 //=========================================================================
501 // A property map that always returns a reference to the same object.
503 template <typename KeyType, typename ValueType>
504 class ref_property_map :
506 boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> >
510 typedef KeyType key_type;
511 typedef ValueType value_type;
512 typedef ValueType& reference;
513 typedef lvalue_property_map_tag category;
514 ref_property_map(ValueType& v) : value(&v) {}
515 ValueType& operator[](key_type const&) const { return *value; }
520 //=========================================================================
521 // A property map that applies the identity function to integers
522 struct identity_property_map
523 : public boost::put_get_helper<std::size_t,
524 identity_property_map>
526 typedef std::size_t key_type;
527 typedef std::size_t value_type;
528 typedef std::size_t reference;
529 typedef boost::readable_property_map_tag category;
531 inline value_type operator[](const key_type& v) const { return v; }
534 //=========================================================================
535 // A property map that does not do anything, for
536 // when you have to supply a property map, but don't need it.
538 struct dummy_pmap_reference {
540 dummy_pmap_reference& operator=(const T&) { return *this; }
541 operator int() { return 0; }
544 class dummy_property_map
545 : public boost::put_get_helper<detail::dummy_pmap_reference,
549 typedef void key_type;
550 typedef int value_type;
551 typedef detail::dummy_pmap_reference reference;
552 typedef boost::read_write_property_map_tag category;
553 inline dummy_property_map() : c(0) { }
554 inline dummy_property_map(value_type cc) : c(cc) { }
555 inline dummy_property_map(const dummy_property_map& x)
557 template <class Vertex>
558 inline reference operator[](Vertex) const { return reference(); }
567 #endif /* BOOST_PROPERTY_MAP_HPP */