property_map.hpp 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569
  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)
  5. // See http://www.boost.org/libs/property_map for documentation.
  6. #ifndef BOOST_PROPERTY_MAP_HPP
  7. #define BOOST_PROPERTY_MAP_HPP
  8. #include <cassert>
  9. #include <boost/config.hpp>
  10. #include <boost/pending/cstddef.hpp>
  11. #include <boost/detail/iterator.hpp>
  12. #include <boost/concept_check.hpp>
  13. #include <boost/concept_archetype.hpp>
  14. #include <boost/mpl/assert.hpp>
  15. #include <boost/mpl/or.hpp>
  16. #include <boost/type_traits/is_same.hpp>
  17. namespace boost {
  18. //=========================================================================
  19. // property_traits class
  20. template <typename PA>
  21. struct property_traits {
  22. typedef typename PA::key_type key_type;
  23. typedef typename PA::value_type value_type;
  24. typedef typename PA::reference reference;
  25. typedef typename PA::category category;
  26. };
  27. //=========================================================================
  28. // property_traits category tags
  29. namespace detail {
  30. enum ePropertyMapID { READABLE_PA, WRITABLE_PA,
  31. READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA,
  32. RAND_ACCESS_ITER_PA, LAST_PA };
  33. }
  34. struct readable_property_map_tag { enum { id = detail::READABLE_PA }; };
  35. struct writable_property_map_tag { enum { id = detail::WRITABLE_PA }; };
  36. struct read_write_property_map_tag :
  37. public readable_property_map_tag,
  38. public writable_property_map_tag
  39. { enum { id = detail::READ_WRITE_PA }; };
  40. struct lvalue_property_map_tag : public read_write_property_map_tag
  41. { enum { id = detail::LVALUE_PA }; };
  42. //=========================================================================
  43. // property_traits specialization for pointers
  44. #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  45. // The user will just have to create their own specializations for
  46. // other pointers types if the compiler does not have partial
  47. // specializations. Sorry!
  48. #define BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(TYPE) \
  49. template <> \
  50. struct property_traits<TYPE*> { \
  51. typedef TYPE value_type; \
  52. typedef value_type& reference; \
  53. typedef std::ptrdiff_t key_type; \
  54. typedef lvalue_property_map_tag category; \
  55. }; \
  56. template <> \
  57. struct property_traits<const TYPE*> { \
  58. typedef TYPE value_type; \
  59. typedef const value_type& reference; \
  60. typedef std::ptrdiff_t key_type; \
  61. typedef lvalue_property_map_tag category; \
  62. }
  63. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(long);
  64. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned long);
  65. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(int);
  66. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned int);
  67. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(short);
  68. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned short);
  69. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(char);
  70. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned char);
  71. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(signed char);
  72. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(bool);
  73. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(float);
  74. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(double);
  75. BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(long double);
  76. // This may need to be turned off for some older compilers that don't have
  77. // wchar_t intrinsically.
  78. # ifndef BOOST_NO_INTRINSIC_WCHAR_T
  79. template <>
  80. struct property_traits<wchar_t*> {
  81. typedef wchar_t value_type;
  82. typedef value_type& reference;
  83. typedef std::ptrdiff_t key_type;
  84. typedef lvalue_property_map_tag category;
  85. };
  86. template <>
  87. struct property_traits<const wchar_t*> {
  88. typedef wchar_t value_type;
  89. typedef const value_type& reference;
  90. typedef std::ptrdiff_t key_type;
  91. typedef lvalue_property_map_tag category;
  92. };
  93. # endif
  94. #else
  95. template <class T>
  96. struct property_traits<T*> {
  97. typedef T value_type;
  98. typedef value_type& reference;
  99. typedef std::ptrdiff_t key_type;
  100. typedef lvalue_property_map_tag category;
  101. };
  102. template <class T>
  103. struct property_traits<const T*> {
  104. typedef T value_type;
  105. typedef const value_type& reference;
  106. typedef std::ptrdiff_t key_type;
  107. typedef lvalue_property_map_tag category;
  108. };
  109. #endif
  110. #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
  111. // MSVC doesn't have Koenig lookup, so the user has to
  112. // do boost::get() anyways, and the using clause
  113. // doesn't really work for MSVC.
  114. } // namespace boost
  115. #endif
  116. // These need to go in global namespace because Koenig
  117. // lookup does not apply to T*.
  118. // V must be convertible to T
  119. template <class T, class V>
  120. inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val; }
  121. template <class T>
  122. inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }
  123. #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
  124. namespace boost {
  125. using ::put;
  126. using ::get;
  127. #endif
  128. //=========================================================================
  129. // concept checks for property maps
  130. template <class PMap, class Key>
  131. struct ReadablePropertyMapConcept
  132. {
  133. typedef typename property_traits<PMap>::key_type key_type;
  134. typedef typename property_traits<PMap>::reference reference;
  135. typedef typename property_traits<PMap>::category Category;
  136. typedef boost::readable_property_map_tag ReadableTag;
  137. void constraints() {
  138. function_requires< ConvertibleConcept<Category, ReadableTag> >();
  139. val = get(pmap, k);
  140. }
  141. PMap pmap;
  142. Key k;
  143. typename property_traits<PMap>::value_type val;
  144. };
  145. template <typename KeyArchetype, typename ValueArchetype>
  146. struct readable_property_map_archetype {
  147. typedef KeyArchetype key_type;
  148. typedef ValueArchetype value_type;
  149. typedef convertible_to_archetype<ValueArchetype> reference;
  150. typedef readable_property_map_tag category;
  151. };
  152. template <typename K, typename V>
  153. const typename readable_property_map_archetype<K,V>::reference&
  154. get(const readable_property_map_archetype<K,V>&,
  155. const typename readable_property_map_archetype<K,V>::key_type&)
  156. {
  157. typedef typename readable_property_map_archetype<K,V>::reference R;
  158. return static_object<R>::get();
  159. }
  160. template <class PMap, class Key>
  161. struct WritablePropertyMapConcept
  162. {
  163. typedef typename property_traits<PMap>::key_type key_type;
  164. typedef typename property_traits<PMap>::category Category;
  165. typedef boost::writable_property_map_tag WritableTag;
  166. void constraints() {
  167. function_requires< ConvertibleConcept<Category, WritableTag> >();
  168. put(pmap, k, val);
  169. }
  170. PMap pmap;
  171. Key k;
  172. typename property_traits<PMap>::value_type val;
  173. };
  174. template <typename KeyArchetype, typename ValueArchetype>
  175. struct writable_property_map_archetype {
  176. typedef KeyArchetype key_type;
  177. typedef ValueArchetype value_type;
  178. typedef void reference;
  179. typedef writable_property_map_tag category;
  180. };
  181. template <typename K, typename V>
  182. void put(const writable_property_map_archetype<K,V>&,
  183. const typename writable_property_map_archetype<K,V>::key_type&,
  184. const typename writable_property_map_archetype<K,V>::value_type&) { }
  185. template <class PMap, class Key>
  186. struct ReadWritePropertyMapConcept
  187. {
  188. typedef typename property_traits<PMap>::category Category;
  189. typedef boost::read_write_property_map_tag ReadWriteTag;
  190. void constraints() {
  191. function_requires< ReadablePropertyMapConcept<PMap, Key> >();
  192. function_requires< WritablePropertyMapConcept<PMap, Key> >();
  193. function_requires< ConvertibleConcept<Category, ReadWriteTag> >();
  194. }
  195. };
  196. template <typename KeyArchetype, typename ValueArchetype>
  197. struct read_write_property_map_archetype
  198. : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
  199. public writable_property_map_archetype<KeyArchetype, ValueArchetype>
  200. {
  201. typedef KeyArchetype key_type;
  202. typedef ValueArchetype value_type;
  203. typedef convertible_to_archetype<ValueArchetype> reference;
  204. typedef read_write_property_map_tag category;
  205. };
  206. template <class PMap, class Key>
  207. struct LvaluePropertyMapConcept
  208. {
  209. typedef typename property_traits<PMap>::category Category;
  210. typedef boost::lvalue_property_map_tag LvalueTag;
  211. typedef typename property_traits<PMap>::reference reference;
  212. void constraints() {
  213. function_requires< ReadablePropertyMapConcept<PMap, Key> >();
  214. function_requires< ConvertibleConcept<Category, LvalueTag> >();
  215. typedef typename property_traits<PMap>::value_type value_type;
  216. BOOST_MPL_ASSERT((boost::mpl::or_<
  217. boost::is_same<const value_type&, reference>,
  218. boost::is_same<value_type&, reference> >));
  219. reference ref = pmap[k];
  220. ignore_unused_variable_warning(ref);
  221. }
  222. PMap pmap;
  223. Key k;
  224. };
  225. template <typename KeyArchetype, typename ValueArchetype>
  226. struct lvalue_property_map_archetype
  227. : public readable_property_map_archetype<KeyArchetype, ValueArchetype>
  228. {
  229. typedef KeyArchetype key_type;
  230. typedef ValueArchetype value_type;
  231. typedef const ValueArchetype& reference;
  232. typedef lvalue_property_map_tag category;
  233. const value_type& operator[](const key_type&) const {
  234. return static_object<value_type>::get();
  235. }
  236. };
  237. template <class PMap, class Key>
  238. struct Mutable_LvaluePropertyMapConcept
  239. {
  240. typedef typename property_traits<PMap>::category Category;
  241. typedef boost::lvalue_property_map_tag LvalueTag;
  242. typedef typename property_traits<PMap>::reference reference;
  243. void constraints() {
  244. boost::function_requires< ReadWritePropertyMapConcept<PMap, Key> >();
  245. boost::function_requires<ConvertibleConcept<Category, LvalueTag> >();
  246. typedef typename property_traits<PMap>::value_type value_type;
  247. BOOST_MPL_ASSERT((boost::is_same<value_type&, reference>));
  248. reference ref = pmap[k];
  249. ignore_unused_variable_warning(ref);
  250. }
  251. PMap pmap;
  252. Key k;
  253. };
  254. template <typename KeyArchetype, typename ValueArchetype>
  255. struct mutable_lvalue_property_map_archetype
  256. : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
  257. public writable_property_map_archetype<KeyArchetype, ValueArchetype>
  258. {
  259. typedef KeyArchetype key_type;
  260. typedef ValueArchetype value_type;
  261. typedef ValueArchetype& reference;
  262. typedef lvalue_property_map_tag category;
  263. value_type& operator[](const key_type&) const {
  264. return static_object<value_type>::get();
  265. }
  266. };
  267. struct identity_property_map;
  268. // A helper class for constructing a property map
  269. // from a class that implements operator[]
  270. template <class Reference, class LvaluePropertyMap>
  271. struct put_get_helper { };
  272. template <class PropertyMap, class Reference, class K>
  273. inline Reference
  274. get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
  275. {
  276. Reference v = static_cast<const PropertyMap&>(pa)[k];
  277. return v;
  278. }
  279. template <class PropertyMap, class Reference, class K, class V>
  280. inline void
  281. put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
  282. {
  283. static_cast<const PropertyMap&>(pa)[k] = v;
  284. }
  285. //=========================================================================
  286. // Adapter to turn a RandomAccessIterator into a property map
  287. template <class RandomAccessIterator,
  288. class IndexMap
  289. #ifdef BOOST_NO_STD_ITERATOR_TRAITS
  290. , class T, class R
  291. #else
  292. , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
  293. , class R = typename std::iterator_traits<RandomAccessIterator>::reference
  294. #endif
  295. >
  296. class iterator_property_map
  297. : public boost::put_get_helper< R,
  298. iterator_property_map<RandomAccessIterator, IndexMap,
  299. T, R> >
  300. {
  301. public:
  302. typedef typename property_traits<IndexMap>::key_type key_type;
  303. typedef T value_type;
  304. typedef R reference;
  305. typedef boost::lvalue_property_map_tag category;
  306. inline iterator_property_map(
  307. RandomAccessIterator cc = RandomAccessIterator(),
  308. const IndexMap& _id = IndexMap() )
  309. : iter(cc), index(_id) { }
  310. inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }
  311. protected:
  312. RandomAccessIterator iter;
  313. IndexMap index;
  314. };
  315. #if !defined BOOST_NO_STD_ITERATOR_TRAITS
  316. template <class RAIter, class ID>
  317. inline iterator_property_map<
  318. RAIter, ID,
  319. typename std::iterator_traits<RAIter>::value_type,
  320. typename std::iterator_traits<RAIter>::reference>
  321. make_iterator_property_map(RAIter iter, ID id) {
  322. function_requires< RandomAccessIteratorConcept<RAIter> >();
  323. typedef iterator_property_map<
  324. RAIter, ID,
  325. typename std::iterator_traits<RAIter>::value_type,
  326. typename std::iterator_traits<RAIter>::reference> PA;
  327. return PA(iter, id);
  328. }
  329. #endif
  330. template <class RAIter, class Value, class ID>
  331. inline iterator_property_map<RAIter, ID, Value, Value&>
  332. make_iterator_property_map(RAIter iter, ID id, Value) {
  333. function_requires< RandomAccessIteratorConcept<RAIter> >();
  334. typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;
  335. return PMap(iter, id);
  336. }
  337. template <class RandomAccessIterator,
  338. class IndexMap
  339. #ifdef BOOST_NO_STD_ITERATOR_TRAITS
  340. , class T, class R
  341. #else
  342. , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
  343. , class R = typename std::iterator_traits<RandomAccessIterator>::reference
  344. #endif
  345. >
  346. class safe_iterator_property_map
  347. : public boost::put_get_helper< R,
  348. safe_iterator_property_map<RandomAccessIterator, IndexMap,
  349. T, R> >
  350. {
  351. public:
  352. typedef typename property_traits<IndexMap>::key_type key_type;
  353. typedef T value_type;
  354. typedef R reference;
  355. typedef boost::lvalue_property_map_tag category;
  356. inline safe_iterator_property_map(
  357. RandomAccessIterator first,
  358. std::size_t n_ = 0,
  359. const IndexMap& _id = IndexMap() )
  360. : iter(first), n(n_), index(_id) { }
  361. inline safe_iterator_property_map() { }
  362. inline R operator[](key_type v) const {
  363. assert(get(index, v) < n);
  364. return *(iter + get(index, v)) ;
  365. }
  366. typename property_traits<IndexMap>::value_type size() const { return n; }
  367. protected:
  368. RandomAccessIterator iter;
  369. typename property_traits<IndexMap>::value_type n;
  370. IndexMap index;
  371. };
  372. #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  373. template <class RAIter, class ID>
  374. inline safe_iterator_property_map<
  375. RAIter, ID,
  376. typename boost::detail::iterator_traits<RAIter>::value_type,
  377. typename boost::detail::iterator_traits<RAIter>::reference>
  378. make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id) {
  379. function_requires< RandomAccessIteratorConcept<RAIter> >();
  380. typedef safe_iterator_property_map<
  381. RAIter, ID,
  382. typename boost::detail::iterator_traits<RAIter>::value_type,
  383. typename boost::detail::iterator_traits<RAIter>::reference> PA;
  384. return PA(iter, n, id);
  385. }
  386. #endif
  387. template <class RAIter, class Value, class ID>
  388. inline safe_iterator_property_map<RAIter, ID, Value, Value&>
  389. make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id, Value) {
  390. function_requires< RandomAccessIteratorConcept<RAIter> >();
  391. typedef safe_iterator_property_map<RAIter, ID, Value, Value&> PMap;
  392. return PMap(iter, n, id);
  393. }
  394. //=========================================================================
  395. // An adaptor to turn a Unique Pair Associative Container like std::map or
  396. // std::hash_map into an Lvalue Property Map.
  397. template <typename UniquePairAssociativeContainer>
  398. class associative_property_map
  399. : public boost::put_get_helper<
  400. typename UniquePairAssociativeContainer::value_type::second_type&,
  401. associative_property_map<UniquePairAssociativeContainer> >
  402. {
  403. typedef UniquePairAssociativeContainer C;
  404. public:
  405. typedef typename C::key_type key_type;
  406. typedef typename C::value_type::second_type value_type;
  407. typedef value_type& reference;
  408. typedef lvalue_property_map_tag category;
  409. associative_property_map() : m_c(0) { }
  410. associative_property_map(C& c) : m_c(&c) { }
  411. reference operator[](const key_type& k) const {
  412. return (*m_c)[k];
  413. }
  414. private:
  415. C* m_c;
  416. };
  417. template <class UniquePairAssociativeContainer>
  418. associative_property_map<UniquePairAssociativeContainer>
  419. make_assoc_property_map(UniquePairAssociativeContainer& c)
  420. {
  421. return associative_property_map<UniquePairAssociativeContainer>(c);
  422. }
  423. template <typename UniquePairAssociativeContainer>
  424. class const_associative_property_map
  425. : public boost::put_get_helper<
  426. const typename UniquePairAssociativeContainer::value_type::second_type&,
  427. const_associative_property_map<UniquePairAssociativeContainer> >
  428. {
  429. typedef UniquePairAssociativeContainer C;
  430. public:
  431. typedef typename C::key_type key_type;
  432. typedef typename C::value_type::second_type value_type;
  433. typedef const value_type& reference;
  434. typedef lvalue_property_map_tag category;
  435. const_associative_property_map() : m_c(0) { }
  436. const_associative_property_map(const C& c) : m_c(&c) { }
  437. reference operator[](const key_type& k) const {
  438. return m_c->find(k)->second;
  439. }
  440. private:
  441. C const* m_c;
  442. };
  443. template <class UniquePairAssociativeContainer>
  444. const_associative_property_map<UniquePairAssociativeContainer>
  445. make_assoc_property_map(const UniquePairAssociativeContainer& c)
  446. {
  447. return const_associative_property_map<UniquePairAssociativeContainer>(c);
  448. }
  449. //=========================================================================
  450. // A property map that always returns a reference to the same object.
  451. //
  452. template <typename KeyType, typename ValueType>
  453. class ref_property_map :
  454. public
  455. boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> >
  456. {
  457. ValueType* value;
  458. public:
  459. typedef KeyType key_type;
  460. typedef ValueType value_type;
  461. typedef ValueType& reference;
  462. typedef lvalue_property_map_tag category;
  463. ref_property_map(ValueType& v) : value(&v) {}
  464. ValueType& operator[](key_type const&) const { return *value; }
  465. };
  466. //=========================================================================
  467. // A property map that applies the identity function to integers
  468. struct identity_property_map
  469. : public boost::put_get_helper<std::size_t,
  470. identity_property_map>
  471. {
  472. typedef std::size_t key_type;
  473. typedef std::size_t value_type;
  474. typedef std::size_t reference;
  475. typedef boost::readable_property_map_tag category;
  476. inline value_type operator[](const key_type& v) const { return v; }
  477. };
  478. //=========================================================================
  479. // A property map that does not do anything, for
  480. // when you have to supply a property map, but don't need it.
  481. namespace detail {
  482. struct dummy_pmap_reference {
  483. template <class T>
  484. dummy_pmap_reference& operator=(const T&) { return *this; }
  485. operator int() { return 0; }
  486. };
  487. }
  488. class dummy_property_map
  489. : public boost::put_get_helper<detail::dummy_pmap_reference,
  490. dummy_property_map >
  491. {
  492. public:
  493. typedef void key_type;
  494. typedef int value_type;
  495. typedef detail::dummy_pmap_reference reference;
  496. typedef boost::read_write_property_map_tag category;
  497. inline dummy_property_map() : c(0) { }
  498. inline dummy_property_map(value_type cc) : c(cc) { }
  499. inline dummy_property_map(const dummy_property_map& x)
  500. : c(x.c) { }
  501. template <class Vertex>
  502. inline reference operator[](Vertex) const { return reference(); }
  503. protected:
  504. value_type c;
  505. };
  506. } // namespace boost
  507. #endif /* BOOST_PROPERTY_MAP_HPP */