1 // (C) Copyright Jeremy Siek 1999-2001. Permission to copy, use, modify,
2 // sell and distribute this software is granted provided this
3 // copyright notice appears in all copies. This software is provided
4 // "as is" without express or implied warranty, and with no claim as
5 // to its suitability for any purpose.
7 // See http://www.boost.org/libs/property_map for documentation.
9 #ifndef BOOST_PROPERTY_MAP_HPP
10 #define BOOST_PROPERTY_MAP_HPP
13 #include <boost/config.hpp>
14 #include <boost/pending/cstddef.hpp>
15 #include <boost/detail/iterator.hpp>
16 #include <boost/concept_check.hpp>
17 #include <boost/concept_archetype.hpp>
21 //=========================================================================
22 // property_traits class
24 template <typename PA>
25 struct property_traits {
26 typedef typename PA::key_type key_type;
27 typedef typename PA::value_type value_type;
28 typedef typename PA::reference reference;
29 typedef typename PA::category category;
32 //=========================================================================
33 // property_traits category tags
36 enum ePropertyMapID { READABLE_PA, WRITABLE_PA,
37 READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA,
38 RAND_ACCESS_ITER_PA, LAST_PA };
40 struct readable_property_map_tag { enum { id = detail::READABLE_PA }; };
41 struct writable_property_map_tag { enum { id = detail::WRITABLE_PA }; };
42 struct read_write_property_map_tag :
43 public readable_property_map_tag,
44 public writable_property_map_tag
45 { enum { id = detail::READ_WRITE_PA }; };
47 struct lvalue_property_map_tag : public read_write_property_map_tag
48 { enum { id = detail::LVALUE_PA }; };
50 //=========================================================================
51 // property_traits specialization for pointers
53 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
54 // The user will just have to create their own specializations for
55 // other pointers types if the compiler does not have partial
56 // specializations. Sorry!
57 #define BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(TYPE) \
59 struct property_traits<TYPE*> { \
60 typedef TYPE value_type; \
61 typedef value_type& reference; \
62 typedef std::ptrdiff_t key_type; \
63 typedef lvalue_property_map_tag category; \
66 struct property_traits<const TYPE*> { \
67 typedef TYPE value_type; \
68 typedef const value_type& reference; \
69 typedef std::ptrdiff_t key_type; \
70 typedef lvalue_property_map_tag category; \
73 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(long);
74 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned long);
75 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(int);
76 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned int);
77 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(short);
78 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned short);
79 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(char);
80 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned char);
81 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(signed char);
82 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(bool);
83 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(float);
84 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(double);
85 BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(long double);
87 // This may need to be turned off for some older compilers that don't have
88 // wchar_t intrinsically.
89 # ifndef BOOST_NO_INTRINSIC_WCHAR_T
91 struct property_traits<wchar_t*> {
92 typedef wchar_t value_type;
93 typedef value_type& reference;
94 typedef std::ptrdiff_t key_type;
95 typedef lvalue_property_map_tag category;
98 struct property_traits<const wchar_t*> {
99 typedef wchar_t value_type;
100 typedef const value_type& reference;
101 typedef std::ptrdiff_t key_type;
102 typedef lvalue_property_map_tag category;
108 struct property_traits<T*> {
109 typedef T value_type;
110 typedef value_type& reference;
111 typedef std::ptrdiff_t key_type;
112 typedef lvalue_property_map_tag category;
115 struct property_traits<const T*> {
116 typedef T value_type;
117 typedef const value_type& reference;
118 typedef std::ptrdiff_t key_type;
119 typedef lvalue_property_map_tag category;
123 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
124 // MSVC doesn't have Koenig lookup, so the user has to
125 // do boost::get() anyways, and the using clause
126 // doesn't really work for MSVC.
130 // These need to go in global namespace because Koenig
131 // lookup does not apply to T*.
133 // V must be convertible to T
134 template <class T, class V>
135 inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val; }
138 inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }
140 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
146 //=========================================================================
147 // concept checks for property maps
149 template <class PMap, class Key>
150 struct ReadablePropertyMapConcept
152 typedef typename property_traits<PMap>::key_type key_type;
153 typedef typename property_traits<PMap>::reference reference;
154 typedef typename property_traits<PMap>::category Category;
155 typedef boost::readable_property_map_tag ReadableTag;
157 function_requires< ConvertibleConcept<Category, ReadableTag> >();
163 typename property_traits<PMap>::value_type val;
165 template <typename KeyArchetype, typename ValueArchetype>
166 struct readable_property_map_archetype {
167 typedef KeyArchetype key_type;
168 typedef ValueArchetype value_type;
169 typedef convertible_to_archetype<ValueArchetype> reference;
170 typedef readable_property_map_tag category;
172 template <typename K, typename V>
173 const typename readable_property_map_archetype<K,V>::reference&
174 get(const readable_property_map_archetype<K,V>&,
175 const typename readable_property_map_archetype<K,V>::key_type&)
177 typedef typename readable_property_map_archetype<K,V>::reference R;
178 return static_object<R>::get();
182 template <class PMap, class Key>
183 struct WritablePropertyMapConcept
185 typedef typename property_traits<PMap>::key_type key_type;
186 typedef typename property_traits<PMap>::category Category;
187 typedef boost::writable_property_map_tag WritableTag;
189 function_requires< ConvertibleConcept<Category, WritableTag> >();
194 typename property_traits<PMap>::value_type val;
196 template <typename KeyArchetype, typename ValueArchetype>
197 struct writable_property_map_archetype {
198 typedef KeyArchetype key_type;
199 typedef ValueArchetype value_type;
200 typedef void reference;
201 typedef writable_property_map_tag category;
203 template <typename K, typename V>
204 void put(const writable_property_map_archetype<K,V>&,
205 const typename writable_property_map_archetype<K,V>::key_type&,
206 const typename writable_property_map_archetype<K,V>::value_type&) { }
209 template <class PMap, class Key>
210 struct ReadWritePropertyMapConcept
212 typedef typename property_traits<PMap>::category Category;
213 typedef boost::read_write_property_map_tag ReadWriteTag;
215 function_requires< ReadablePropertyMapConcept<PMap, Key> >();
216 function_requires< WritablePropertyMapConcept<PMap, Key> >();
217 function_requires< ConvertibleConcept<Category, ReadWriteTag> >();
220 template <typename KeyArchetype, typename ValueArchetype>
221 struct read_write_property_map_archetype
222 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
223 public writable_property_map_archetype<KeyArchetype, ValueArchetype>
225 typedef KeyArchetype key_type;
226 typedef ValueArchetype value_type;
227 typedef convertible_to_archetype<ValueArchetype> reference;
228 typedef read_write_property_map_tag category;
232 template <class PMap, class Key>
233 struct LvaluePropertyMapConcept
235 typedef typename property_traits<PMap>::category Category;
236 typedef boost::lvalue_property_map_tag LvalueTag;
237 typedef typename property_traits<PMap>::reference reference;
240 function_requires< ReadablePropertyMapConcept<PMap, Key> >();
241 function_requires< ConvertibleConcept<Category, LvalueTag> >();
243 typedef typename property_traits<PMap>::value_type value_type;
244 typedef typename require_same<
245 const value_type&, reference>::type req;
247 reference ref = pmap[k];
248 ignore_unused_variable_warning(ref);
253 template <typename KeyArchetype, typename ValueArchetype>
254 struct lvalue_property_map_archetype
255 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>
257 typedef KeyArchetype key_type;
258 typedef ValueArchetype value_type;
259 typedef const ValueArchetype& reference;
260 typedef lvalue_property_map_tag category;
261 const value_type& operator[](const key_type&) const {
262 return static_object<value_type>::get();
266 template <class PMap, class Key>
267 struct Mutable_LvaluePropertyMapConcept
269 typedef typename property_traits<PMap>::category Category;
270 typedef boost::lvalue_property_map_tag LvalueTag;
271 typedef typename property_traits<PMap>::reference reference;
273 boost::function_requires< ReadWritePropertyMapConcept<PMap, Key> >();
274 boost::function_requires<ConvertibleConcept<Category, LvalueTag> >();
276 typedef typename property_traits<PMap>::value_type value_type;
277 typedef typename require_same<
279 reference>::type req;
281 reference ref = pmap[k];
282 ignore_unused_variable_warning(ref);
287 template <typename KeyArchetype, typename ValueArchetype>
288 struct mutable_lvalue_property_map_archetype
289 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
290 public writable_property_map_archetype<KeyArchetype, ValueArchetype>
292 typedef KeyArchetype key_type;
293 typedef ValueArchetype value_type;
294 typedef ValueArchetype& reference;
295 typedef lvalue_property_map_tag category;
296 value_type& operator[](const key_type&) const {
297 return static_object<value_type>::get();
301 struct identity_property_map;
303 // A helper class for constructing a property map
304 // from a class that implements operator[]
306 template <class Reference, class LvaluePropertyMap>
307 struct put_get_helper { };
309 template <class PropertyMap, class Reference, class K>
311 get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
313 Reference v = static_cast<const PropertyMap&>(pa)[k];
316 template <class PropertyMap, class Reference, class K, class V>
318 put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
320 static_cast<const PropertyMap&>(pa)[k] = v;
323 //=========================================================================
324 // Adapter to turn a RandomAccessIterator into a property map
326 template <class RandomAccessIterator,
328 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
331 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
332 , class R = typename std::iterator_traits<RandomAccessIterator>::reference
335 class iterator_property_map
336 : public boost::put_get_helper< R,
337 iterator_property_map<RandomAccessIterator, IndexMap,
341 typedef typename property_traits<IndexMap>::key_type key_type;
342 typedef T value_type;
344 typedef boost::lvalue_property_map_tag category;
346 inline iterator_property_map(
347 RandomAccessIterator cc = RandomAccessIterator(),
348 const IndexMap& _id = IndexMap() )
349 : iter(cc), index(_id) { }
350 inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }
352 RandomAccessIterator iter;
356 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
357 template <class RAIter, class ID>
358 inline iterator_property_map<
360 typename std::iterator_traits<RAIter>::value_type,
361 typename std::iterator_traits<RAIter>::reference>
362 make_iterator_property_map(RAIter iter, ID id) {
363 function_requires< RandomAccessIteratorConcept<RAIter> >();
364 typedef iterator_property_map<
366 typename std::iterator_traits<RAIter>::value_type,
367 typename std::iterator_traits<RAIter>::reference> PA;
371 template <class RAIter, class Value, class ID>
372 inline iterator_property_map<RAIter, ID, Value, Value&>
373 make_iterator_property_map(RAIter iter, ID id, Value) {
374 function_requires< RandomAccessIteratorConcept<RAIter> >();
375 typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;
376 return PMap(iter, id);
379 template <class RandomAccessIterator,
381 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
384 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
385 , class R = typename std::iterator_traits<RandomAccessIterator>::reference
388 class safe_iterator_property_map
389 : public boost::put_get_helper< R,
390 safe_iterator_property_map<RandomAccessIterator, IndexMap,
394 typedef typename property_traits<IndexMap>::key_type key_type;
395 typedef T value_type;
397 typedef boost::lvalue_property_map_tag category;
399 inline safe_iterator_property_map(
400 RandomAccessIterator first = RandomAccessIterator(),
402 const IndexMap& _id = IndexMap() )
403 : iter(first), n(n), index(_id) { }
404 inline R operator[](key_type v) const {
405 assert(get(index, v) < n);
406 return *(iter + get(index, v)) ;
408 typename property_traits<IndexMap>::value_type size() const { return n; }
410 RandomAccessIterator iter;
411 typename property_traits<IndexMap>::value_type n;
415 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
416 template <class RAIter, class ID>
417 inline safe_iterator_property_map<
419 typename boost::detail::iterator_traits<RAIter>::value_type,
420 typename boost::detail::iterator_traits<RAIter>::reference>
421 make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id) {
422 function_requires< RandomAccessIteratorConcept<RAIter> >();
423 typedef safe_iterator_property_map<
425 typename boost::detail::iterator_traits<RAIter>::value_type,
426 typename boost::detail::iterator_traits<RAIter>::reference> PA;
427 return PA(iter, n, id);
430 template <class RAIter, class Value, class ID>
431 inline safe_iterator_property_map<RAIter, ID, Value, Value&>
432 make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id, Value) {
433 function_requires< RandomAccessIteratorConcept<RAIter> >();
434 typedef safe_iterator_property_map<RAIter, ID, Value, Value&> PMap;
435 return PMap(iter, n, id);
438 //=========================================================================
439 // An adaptor to turn a Unique Pair Associative Container like std::map or
440 // std::hash_map into an Lvalue Property Map.
442 template <typename UniquePairAssociativeContainer>
443 class associative_property_map
444 : public boost::put_get_helper<
445 typename UniquePairAssociativeContainer::value_type::second_type&,
446 associative_property_map<UniquePairAssociativeContainer> >
448 typedef UniquePairAssociativeContainer C;
450 typedef typename C::key_type key_type;
451 typedef typename C::value_type::second_type value_type;
452 typedef value_type& reference;
453 typedef lvalue_property_map_tag category;
454 associative_property_map() : m_c(0) { }
455 associative_property_map(C& c) : m_c(&c) { }
456 reference operator[](const key_type& k) const {
463 template <class UniquePairAssociativeContainer>
464 associative_property_map<UniquePairAssociativeContainer>
465 make_assoc_property_map(UniquePairAssociativeContainer& c)
467 return associative_property_map<UniquePairAssociativeContainer>(c);
470 template <typename UniquePairAssociativeContainer>
471 class const_associative_property_map
472 : public boost::put_get_helper<
473 const typename UniquePairAssociativeContainer::value_type::second_type&,
474 const_associative_property_map<UniquePairAssociativeContainer> >
476 typedef UniquePairAssociativeContainer C;
478 typedef typename C::key_type key_type;
479 typedef typename C::value_type::second_type value_type;
480 typedef const value_type& reference;
481 typedef lvalue_property_map_tag category;
482 const_associative_property_map() : m_c(0) { }
483 const_associative_property_map(const C& c) : m_c(&c) { }
484 reference operator[](const key_type& k) const {
485 return m_c->find(k)->second;
491 template <class UniquePairAssociativeContainer>
492 const_associative_property_map<UniquePairAssociativeContainer>
493 make_assoc_property_map(const UniquePairAssociativeContainer& c)
495 return const_associative_property_map<UniquePairAssociativeContainer>(c);
498 //=========================================================================
499 // A property map that applies the identity function to integers
500 struct identity_property_map
501 : public boost::put_get_helper<std::size_t,
502 identity_property_map>
504 typedef std::size_t key_type;
505 typedef std::size_t value_type;
506 typedef std::size_t reference;
507 typedef boost::readable_property_map_tag category;
509 inline value_type operator[](const key_type& v) const { return v; }
512 //=========================================================================
513 // A property map that does not do anything, for
514 // when you have to supply a property map, but don't need it.
516 struct dummy_pmap_reference {
518 dummy_pmap_reference& operator=(const T&) { return *this; }
519 operator int() { return 0; }
522 class dummy_property_map
523 : public boost::put_get_helper<detail::dummy_pmap_reference,
527 typedef void key_type;
528 typedef int value_type;
529 typedef detail::dummy_pmap_reference reference;
530 typedef boost::read_write_property_map_tag category;
531 inline dummy_property_map() : c(0) { }
532 inline dummy_property_map(value_type cc) : c(cc) { }
533 inline dummy_property_map(const dummy_property_map& x)
535 template <class Vertex>
536 inline reference operator[](Vertex) const { return reference(); }
545 #endif /* BOOST_PROPERTY_MAP_HPP */