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