boost/boost/property_map.hpp

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