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 <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>
26
27namespace boost {
28
29 //=========================================================================
30 // property_traits class
31
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)
36
37 template<class PA>
38 struct is_property_map :
39 boost::mpl::and_<
40 has_key_type<PA>,
41 has_value_type<PA>,
42 has_reference<PA>,
43 has_category<PA>
44 >
45 {};
46
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;
53 };
54
55 struct null_property_traits {};
56
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
62 {};
63
64#if 0
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;
71 };
72#endif
73
74 //=========================================================================
75 // property_traits category tags
76
77 namespace detail {
78 enum ePropertyMapID { READABLE_PA, WRITABLE_PA,
79 READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA,
80 RAND_ACCESS_ITER_PA, LAST_PA };
81 }
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 }; };
88
89 struct lvalue_property_map_tag : public read_write_property_map_tag
90 { enum { id = detail::LVALUE_PA }; };
91
92 //=========================================================================
93 // property_traits specialization for pointers
94
95 template <class T>
96 struct property_traits<T*> {
97 // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
98 typedef T value_type;
99 typedef value_type& reference;
100 typedef std::ptrdiff_t key_type;
101 typedef lvalue_property_map_tag category;
102 };
103 template <class T>
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;
110 };
111
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.
116} // namespace boost
117#endif
118
119 // These need to go in global namespace because Koenig
120 // lookup does not apply to T*.
121
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; }
125
126 template <class T>
127 inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }
128
129#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
130namespace boost {
131 using ::put;
132 using ::get;
133#endif
134
135 //=========================================================================
136 // concept checks for property maps
137
138 template <class PMap, class Key>
139 struct ReadablePropertyMapConcept
140 {
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;
145 void constraints() {
146 function_requires< ConvertibleConcept<Category, ReadableTag> >();
147
148 val = get(pmap, k);
149 }
150 PMap pmap;
151 Key k;
152 typename property_traits<PMap>::value_type val;
153 };
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;
160 };
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&)
165 {
166 typedef typename readable_property_map_archetype<K,V>::reference R;
167 return static_object<R>::get();
168 }
169
170
171 template <class PMap, class Key>
172 struct WritablePropertyMapConcept
173 {
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;
177 void constraints() {
178 function_requires< ConvertibleConcept<Category, WritableTag> >();
179 put(pmap, k, val);
180 }
181 PMap pmap;
182 Key k;
183 typename property_traits<PMap>::value_type val;
184 };
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;
191 };
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&) { }
196
197
198 template <class PMap, class Key>
199 struct ReadWritePropertyMapConcept
200 {
201 typedef typename property_traits<PMap>::category Category;
202 typedef boost::read_write_property_map_tag ReadWriteTag;
203 void constraints() {
204 function_requires< ReadablePropertyMapConcept<PMap, Key> >();
205 function_requires< WritablePropertyMapConcept<PMap, Key> >();
206 function_requires< ConvertibleConcept<Category, ReadWriteTag> >();
207 }
208 };
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>
213 {
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;
218 };
219
220
221 template <class PMap, class Key>
222 struct LvaluePropertyMapConcept
223 {
224 typedef typename property_traits<PMap>::category Category;
225 typedef boost::lvalue_property_map_tag LvalueTag;
226 typedef typename property_traits<PMap>::reference reference;
227
228 void constraints() {
229 function_requires< ReadablePropertyMapConcept<PMap, Key> >();
230 function_requires< ConvertibleConcept<Category, LvalueTag> >();
231
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> >));
236
237 reference ref = pmap[k];
238 ignore_unused_variable_warning(ref);
239 }
240 PMap pmap;
241 Key k;
242 };
243 template <typename KeyArchetype, typename ValueArchetype>
244 struct lvalue_property_map_archetype
245 : public readable_property_map_archetype<KeyArchetype, ValueArchetype>
246 {
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();
253 }
254 };
255
256 template <class PMap, class Key>
257 struct Mutable_LvaluePropertyMapConcept
258 {
259 typedef typename property_traits<PMap>::category Category;
260 typedef boost::lvalue_property_map_tag LvalueTag;
261 typedef typename property_traits<PMap>::reference reference;
262 void constraints() {
263 boost::function_requires< ReadWritePropertyMapConcept<PMap, Key> >();
264 boost::function_requires<ConvertibleConcept<Category, LvalueTag> >();
265
266 typedef typename property_traits<PMap>::value_type value_type;
267 BOOST_MPL_ASSERT((boost::is_same<value_type&, reference>));
268
269 reference ref = pmap[k];
270 ignore_unused_variable_warning(ref);
271 }
272 PMap pmap;
273 Key k;
274 };
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>
279 {
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();
286 }
287 };
288
289 template <typename T>
290 struct typed_identity_property_map;
291
292 // A helper class for constructing a property map
293 // from a class that implements operator[]
294
295 template <class Reference, class LvaluePropertyMap>
296 struct put_get_helper { };
297
298 template <class PropertyMap, class Reference, class K>
299 inline Reference
300 get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
301 {
302 Reference v = static_cast<const PropertyMap&>(pa)[k];
303 return v;
304 }
305 template <class PropertyMap, class Reference, class K, class V>
306 inline void
307 put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
308 {
309 static_cast<const PropertyMap&>(pa)[k] = v;
310 }
311
312 //=========================================================================
313 // Adapter to turn a RandomAccessIterator into a property map
314
315 template <class RandomAccessIterator,
316 class IndexMap
317#ifdef BOOST_NO_STD_ITERATOR_TRAITS
318 , class T, class R
319#else
320 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
321 , class R = typename std::iterator_traits<RandomAccessIterator>::reference
322#endif
323 >
324 class iterator_property_map
325 : public boost::put_get_helper< R,
326 iterator_property_map<RandomAccessIterator, IndexMap,
327 T, R> >
328 {
329 public:
330 typedef typename property_traits<IndexMap>::key_type key_type;
331 typedef T value_type;
332 typedef R reference;
333 typedef boost::lvalue_property_map_tag category;
334
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)) ; }
340 protected:
341 RandomAccessIterator iter;
342 IndexMap index;
343 };
344
345#if !defined BOOST_NO_STD_ITERATOR_TRAITS
346 template <class RAIter, class ID>
347 inline iterator_property_map<
348 RAIter, ID,
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<
354 RAIter, ID,
355 typename std::iterator_traits<RAIter>::value_type,
356 typename std::iterator_traits<RAIter>::reference> PA;
357 return PA(iter, id);
358 }
359#endif
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);
366 }
367
368 template <class RandomAccessIterator,
369 class IndexMap
370#ifdef BOOST_NO_STD_ITERATOR_TRAITS
371 , class T, class R
372#else
373 , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
374 , class R = typename std::iterator_traits<RandomAccessIterator>::reference
375#endif
376 >
377 class safe_iterator_property_map
378 : public boost::put_get_helper< R,
379 safe_iterator_property_map<RandomAccessIterator, IndexMap,
380 T, R> >
381 {
382 public:
383 typedef typename property_traits<IndexMap>::key_type key_type;
384 typedef T value_type;
385 typedef R reference;
386 typedef boost::lvalue_property_map_tag category;
387
388 inline safe_iterator_property_map(
389 RandomAccessIterator first,
390 std::size_t n_ = 0,
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)) ;
397 }
398 typename property_traits<IndexMap>::value_type size() const { return n; }
399 protected:
400 RandomAccessIterator iter;
401 typename property_traits<IndexMap>::value_type n;
402 IndexMap index;
403 };
404
405 template <class RAIter, class ID>
406 inline safe_iterator_property_map<
407 RAIter, ID,
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<
413 RAIter, ID,
414 typename boost::detail::iterator_traits<RAIter>::value_type,
415 typename boost::detail::iterator_traits<RAIter>::reference> PA;
416 return PA(iter, n, id);
417 }
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);
424 }
425
426 //=========================================================================
427 // An adaptor to turn a Unique Pair Associative Container like std::map or
428 // std::hash_map into an Lvalue Property Map.
429
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> >
435 {
436 typedef UniquePairAssociativeContainer C;
437 public:
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 {
445 return (*m_c)[k];
446 }
447 private:
448 C* m_c;
449 };
450
451 template <class UniquePairAssociativeContainer>
452 associative_property_map<UniquePairAssociativeContainer>
453 make_assoc_property_map(UniquePairAssociativeContainer& c)
454 {
455 return associative_property_map<UniquePairAssociativeContainer>(c);
456 }
457
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> >
463 {
464 typedef UniquePairAssociativeContainer C;
465 public:
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;
474 }
475 private:
476 C const* m_c;
477 };
478
479 template <class UniquePairAssociativeContainer>
480 const_associative_property_map<UniquePairAssociativeContainer>
481 make_assoc_property_map(const UniquePairAssociativeContainer& c)
482 {
483 return const_associative_property_map<UniquePairAssociativeContainer>(c);
484 }
485
486 //=========================================================================
487 // A property map that always returns the same object by value.
488 //
489 template <typename ValueType, typename KeyType = void>
490 class static_property_map :
491 public
492 boost::put_get_helper<ValueType,static_property_map<ValueType> >
493 {
494 ValueType value;
495 public:
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) {}
501
502 template<typename T>
503 inline reference operator[](T) const { return value; }
504 };
505
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);
510 }
511
512 //=========================================================================
513 // A property map that always returns a reference to the same object.
514 //
515 template <typename KeyType, typename ValueType>
516 class ref_property_map :
517 public
518 boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> >
519 {
520 ValueType* value;
521 public:
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; }
528 };
529
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> >
535 {
536 typedef T key_type;
537 typedef T value_type;
538 typedef T reference;
539 typedef boost::readable_property_map_tag category;
540
541 inline value_type operator[](const key_type& v) const { return v; }
542 };
543
544//=========================================================================
545 // A property map that applies the identity function to integers
546 typedef typed_identity_property_map<std::size_t> identity_property_map;
547
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.
551 namespace detail {
552 struct dummy_pmap_reference {
553 template <class T>
554 dummy_pmap_reference& operator=(const T&) { return *this; }
555 operator int() { return 0; }
556 };
557 }
558 class dummy_property_map
559 : public boost::put_get_helper<detail::dummy_pmap_reference,
560 dummy_property_map >
561 {
562 public:
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)
570 : c(x.c) { }
571 template <class Vertex>
572 inline reference operator[](Vertex) const { return reference(); }
573 protected:
574 value_type c;
575 };
576
577 // Convert a Readable property map into a function object
578 template <typename PropMap>
579 class property_map_function {
580 PropMap pm;
581 typedef typename property_traits<PropMap>::key_type param_type;
582 public:
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);}
586 };
587
588 template <typename PropMap>
589 property_map_function<PropMap>
590 make_property_map_function(const PropMap& pm) {
591 return property_map_function<PropMap>(pm);
592 }
593
594} // namespace boost
595
596#ifdef BOOST_GRAPH_USE_MPI
597#include <boost/property_map/parallel/parallel_property_maps.hpp>
598#endif
599
600#include <boost/property_map/vector_property_map.hpp>
601
602#endif /* BOOST_PROPERTY_MAP_HPP */
603
604

source code of boost/boost/property_map/property_map.hpp