boost/boost/property_map.hpp

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