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 <iterator>
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
29namespace 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 inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val; }
127
128 template <class T>
129 inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }
130
131#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
132namespace 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 get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
303 {
304 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 put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
310 {
311 static_cast<const PropertyMap&>(pa)[k] = v;
312 }
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 inline iterator_property_map(
338 RandomAccessIterator cc = RandomAccessIterator(),
339 const IndexMap& _id = IndexMap() )
340 : iter(cc), index(_id) { }
341 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 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 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 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 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 std::iterator_traits<RAIter>::value_type,
411 typename std::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 std::iterator_traits<RAIter>::value_type,
417 typename std::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 associative_property_map(C& c) : m_c(&c) { }
446 reference operator[](const key_type& k) const {
447 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 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#include <boost/property_map/vector_property_map.hpp>
599
600#endif /* BOOST_PROPERTY_MAP_HPP */
601
602