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 property_traits<PMap>::value_type value_type;
 238       typedef typename require_same<
 239         const value_type&, 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
 270       typedef typename property_traits<PMap>::value_type value_type;
 271       typedef typename require_same<
 272         value_type&,
 273         reference>::type req;
 274
 275       reference ref = pmap[k];
 276       ignore_unused_variable_warning(ref);
 277     }
 278     PMap pmap;
 279     Key k;
 280   };
 281   template <typename KeyArchetype, typename ValueArchetype>
 282   struct mutable_lvalue_property_map_archetype
 283     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
 284       public writable_property_map_archetype<KeyArchetype, ValueArchetype>
 285   {
 286     typedef KeyArchetype key_type;
 287     typedef ValueArchetype value_type;
 288     typedef ValueArchetype& reference;
 289     typedef lvalue_property_map_tag category;
 290     value_type& operator[](const key_type&) const {
 291       return static_object<value_type>::get();
 292     }
 293   };
 294
 295   struct identity_property_map;
 296
 297   // A helper class for constructing a property map
 298   // from a class that implements operator[]
 299
 300   template <class Reference, class LvaluePropertyMap>
 301   struct put_get_helper { };
 302
 303   template <class PropertyMap, class Reference, class K>
 304   inline Reference
 305   get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
 306   {
 307     Reference v = static_cast<const PropertyMap&>(pa)[k];
 308     return v;
 309   }
 310   template <class PropertyMap, class Reference, class K, class V>
 311   inline void
 312   put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
 313   {
 314     static_cast<const PropertyMap&>(pa)[k] = v;
 315   }
 316
 317   //=========================================================================
 318   // Adapter to turn a RandomAccessIterator into a property map
 319
 320   template <class RandomAccessIterator,
 321     class IndexMap
 322 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
 323     , class T, class R
 324 #else
 325     , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
 326     , class R = typename std::iterator_traits<RandomAccessIterator>::reference
 327 #endif
 328      >
 329   class iterator_property_map
 330     : public boost::put_get_helper< R,
 331         iterator_property_map<RandomAccessIterator, IndexMap,
 332         T, R> >
 333   {
 334   public:
 335     typedef typename property_traits<IndexMap>::key_type key_type;
 336     typedef T value_type;
 337     typedef R reference;
 338     typedef boost::lvalue_property_map_tag category;
 339
 340     inline iterator_property_map(
 341       RandomAccessIterator cc = RandomAccessIterator(),
 342       const IndexMap& _id = IndexMap() )
 343       : iter(cc), index(_id) { }
 344     inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }
 345   protected:
 346     RandomAccessIterator iter;
 347     IndexMap index;
 348   };
 349
 350 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
 351   template <class RAIter, class ID>
 352   inline iterator_property_map<
 353     RAIter, ID,
 354     typename std::iterator_traits<RAIter>::value_type,
 355     typename std::iterator_traits<RAIter>::reference>
 356   make_iterator_property_map(RAIter iter, ID id) {
 357     function_requires< RandomAccessIteratorConcept<RAIter> >();
 358     typedef iterator_property_map<
 359       RAIter, ID,
 360       typename std::iterator_traits<RAIter>::value_type,
 361       typename std::iterator_traits<RAIter>::reference> PA;
 362     return PA(iter, id);
 363   }
 364 #endif
 365   template <class RAIter, class Value, class ID>
 366   inline iterator_property_map<RAIter, ID, Value, Value&>
 367   make_iterator_property_map(RAIter iter, ID id, Value) {
 368     function_requires< RandomAccessIteratorConcept<RAIter> >();
 369     typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;
 370     return PMap(iter, id);
 371   }
 372
 373   template <class RandomAccessIterator,
 374     class IndexMap
 375 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
 376     , class T, class R
 377 #else
 378     , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
 379     , class R = typename std::iterator_traits<RandomAccessIterator>::reference
 380 #endif
 381      >
 382   class safe_iterator_property_map
 383     : public boost::put_get_helper< R,
 384         safe_iterator_property_map<RandomAccessIterator, IndexMap,
 385         T, R> >
 386   {
 387   public:
 388     typedef typename property_traits<IndexMap>::key_type key_type;
 389     typedef T value_type;
 390     typedef R reference;
 391     typedef boost::lvalue_property_map_tag category;
 392
 393     inline safe_iterator_property_map(
 394       RandomAccessIterator first = RandomAccessIterator(),
 395       std::size_t n = 0,
 396       const IndexMap& _id = IndexMap() )
 397       : iter(first), n(n), index(_id) { }
 398     inline R operator[](key_type v) const {
 399       assert(get(index, v) < n);
 400       return *(iter + get(index, v)) ;
 401     }
 402     typename property_traits<IndexMap>::value_type size() const { return n; }
 403   protected:
 404     RandomAccessIterator iter;
 405     typename property_traits<IndexMap>::value_type n;
 406     IndexMap index;
 407   };
 408
 409 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 410   template <class RAIter, class ID>
 411   inline safe_iterator_property_map<
 412     RAIter, ID,
 413     typename std::iterator_traits<RAIter>::value_type,
 414     typename std::iterator_traits<RAIter>::reference>
 415   make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id) {
 416     function_requires< RandomAccessIteratorConcept<RAIter> >();
 417     typedef safe_iterator_property_map<
 418       RAIter, ID,
 419       typename std::iterator_traits<RAIter>::value_type,
 420       typename std::iterator_traits<RAIter>::reference> PA;
 421     return PA(iter, n, id);
 422   }
 423 #endif
 424   template <class RAIter, class Value, class ID>
 425   inline safe_iterator_property_map<RAIter, ID, Value, Value&>
 426   make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id, Value) {
 427     function_requires< RandomAccessIteratorConcept<RAIter> >();
 428     typedef safe_iterator_property_map<RAIter, ID, Value, Value&> PMap;
 429     return PMap(iter, n, id);
 430   }
 431
 432   //=========================================================================
 433   // An adaptor to turn a Unique Pair Associative Container like std::map or
 434   // std::hash_map into an Lvalue Property Map.
 435
 436   template <typename UniquePairAssociativeContainer>
 437   class associative_property_map
 438     : public boost::put_get_helper<
 439        typename UniquePairAssociativeContainer::value_type::second_type&,
 440        associative_property_map<UniquePairAssociativeContainer> >
 441   {
 442     typedef UniquePairAssociativeContainer C;
 443   public:
 444     typedef typename C::key_type key_type;
 445     typedef typename C::value_type::second_type value_type;
 446     typedef value_type& reference;
 447     typedef lvalue_property_map_tag category;
 448     associative_property_map() : m_c(0) { }
 449     associative_property_map(C& c) : m_c(&c) { }
 450     reference operator[](const key_type& k) const {
 451       return (*m_c)[k];
 452     }
 453   private:
 454     C* m_c;
 455   };
 456
 457   template <class UniquePairAssociativeContainer>
 458   associative_property_map<UniquePairAssociativeContainer>
 459   make_assoc_property_map(UniquePairAssociativeContainer& c)
 460   {
 461     return associative_property_map<UniquePairAssociativeContainer>(c);
 462   }
 463
 464   template <typename UniquePairAssociativeContainer>
 465   class const_associative_property_map
 466     : public boost::put_get_helper<
 467        const typename UniquePairAssociativeContainer::value_type::second_type&,
 468        const_associative_property_map<UniquePairAssociativeContainer> >
 469   {
 470     typedef UniquePairAssociativeContainer C;
 471   public:
 472     typedef typename C::key_type key_type;
 473     typedef typename C::value_type::second_type value_type;
 474     typedef const value_type& reference;
 475     typedef lvalue_property_map_tag category;
 476     const_associative_property_map() : m_c(0) { }
 477     const_associative_property_map(const C& c) : m_c(&c) { }
 478     reference operator[](const key_type& k) const {
 479       return m_c->find(k)->second;
 480     }
 481   private:
 482     C const* m_c;
 483   };
 484
 485   template <class UniquePairAssociativeContainer>
 486   const_associative_property_map<UniquePairAssociativeContainer>
 487   make_assoc_property_map(const UniquePairAssociativeContainer& c)
 488   {
 489     return const_associative_property_map<UniquePairAssociativeContainer>(c);
 490   }
 491
 492   //=========================================================================
 493   // A property map that applies the identity function to integers
 494   struct identity_property_map
 495     : public boost::put_get_helper<std::size_t,
 496         identity_property_map>
 497   {
 498     typedef std::size_t key_type;
 499     typedef std::size_t value_type;
 500     typedef std::size_t reference;
 501     typedef boost::readable_property_map_tag category;
 502
 503     inline value_type operator[](const key_type& v) const { return v; }
 504   };
 505
 506   //=========================================================================
 507   // A property map that does not do anything, for
 508   // when you have to supply a property map, but don't need it.
 509   namespace detail {
 510     struct dummy_pmap_reference {
 511       template <class T>
 512       dummy_pmap_reference& operator=(const T&) { return *this; }
 513       operator int() { return 0; }
 514     };
 515   }
 516   class dummy_property_map
 517     : public boost::put_get_helper<detail::dummy_pmap_reference,
 518         dummy_property_map  >
 519   {
 520   public:
 521     typedef void key_type;
 522     typedef int value_type;
 523     typedef detail::dummy_pmap_reference reference;
 524     typedef boost::read_write_property_map_tag category;
 525     inline dummy_property_map() : c(0) { }
 526     inline dummy_property_map(value_type cc) : c(cc) { }
 527     inline dummy_property_map(const dummy_property_map& x)
 528       : c(x.c) { }
 529     template <class Vertex>
 530     inline reference operator[](Vertex) const { return reference(); }
 531    protected:
 532     value_type c;
 533   };
 534
 535
 536 } // namespace boost
 537
 538
 539 #endif /* BOOST_PROPERTY_MAP_HPP */
 540