Line data Source code
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/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>
126 0 : inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val; }
127 :
128 : template <class T>
129 0 : 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;
147 : 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&
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;
179 : 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>
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;
205 : 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 :
230 : 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;
253 : 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;
264 : 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;
286 : 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
302 0 : get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
303 : {
304 0 : 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
309 0 : put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
310 : {
311 0 : static_cast<const PropertyMap&>(pa)[k] = v;
312 0 : }
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 :
337 0 : inline iterator_property_map(
338 : RandomAccessIterator cc = RandomAccessIterator(),
339 : const IndexMap& _id = IndexMap() )
340 : : iter(cc), index(_id) { }
341 0 : 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>
353 0 : 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 0 : return PA(iter, id);
360 : }
361 : #endif
362 : template <class RAIter, class Value, class ID>
363 : inline iterator_property_map<RAIter, ID, Value, Value&>
364 0 : 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 0 : 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 :
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) { }
395 : inline safe_iterator_property_map() { }
396 : inline R operator[](key_type v) const {
397 : BOOST_ASSERT(get(index, v) < n);
398 : return *(iter + get(index, v)) ;
399 : }
400 : 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 boost::detail::iterator_traits<RAIter>::value_type,
411 : typename boost::detail::iterator_traits<RAIter>::reference>
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 boost::detail::iterator_traits<RAIter>::value_type,
417 : typename boost::detail::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&>
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;
444 : associative_property_map() : m_c(0) { }
445 0 : associative_property_map(C& c) : m_c(&c) { }
446 0 : reference operator[](const key_type& k) const {
447 0 : return (*m_c)[k];
448 : }
449 : private:
450 : C* m_c;
451 : };
452 :
453 : template <class UniquePairAssociativeContainer>
454 : associative_property_map<UniquePairAssociativeContainer>
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;
472 : const_associative_property_map() : m_c(0) { }
473 : const_associative_property_map(const C& c) : m_c(&c) { }
474 : 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>
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;
502 : static_property_map(ValueType v) : value(v) {}
503 :
504 : template<typename T>
505 : inline reference operator[](T) const { return value; }
506 : };
507 :
508 : template <typename KeyType, typename ValueType>
509 : static_property_map<ValueType, KeyType>
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;
528 : ref_property_map(ValueType& v) : value(&v) {}
529 : 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 :
543 : 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>
556 : dummy_pmap_reference& operator=(const T&) { return *this; }
557 : 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;
569 0 : inline dummy_property_map() : c(0) { }
570 : inline dummy_property_map(value_type cc) : c(cc) { }
571 : inline dummy_property_map(const dummy_property_map& x)
572 : : c(x.c) { }
573 : template <class Vertex>
574 : 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:
585 : explicit property_map_function(const PropMap& pm): pm(pm) {}
586 : typedef typename property_traits<PropMap>::value_type result_type;
587 : result_type operator()(const param_type& k) const {return get(pm, k);}
588 : };
589 :
590 : template <typename PropMap>
591 : property_map_function<PropMap>
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 :
|
