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