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>&,
 175       const typename readable_property_map_archetype<K,V>::key_type&)
 176   {
 177     typedef typename readable_property_map_archetype<K,V>::reference R;
 178     return static_object<R>::get();
 179   }
 180
 181
 182   template <class PMap, class Key>
 183   struct WritablePropertyMapConcept
 184   {
 185     typedef typename property_traits<PMap>::key_type key_type;
 186     typedef typename property_traits<PMap>::category Category;
 187     typedef boost::writable_property_map_tag WritableTag;
 188     void constraints() {
 189       function_requires< ConvertibleConcept<Category, WritableTag> >();
 190       put(pmap, k, val);
 191     }
 192     PMap pmap;
 193     Key k;
 194     typename property_traits<PMap>::value_type val;
 195   };
 196   template <typename KeyArchetype, typename ValueArchetype>
 197   struct writable_property_map_archetype {
 198     typedef KeyArchetype key_type;
 199     typedef ValueArchetype value_type;
 200     typedef void reference;
 201     typedef writable_property_map_tag category;
 202   };
 203   template <typename K, typename V>
 204   void put(const writable_property_map_archetype<K,V>&,
 205            const typename writable_property_map_archetype<K,V>::key_type&,
 206            const typename writable_property_map_archetype<K,V>::value_type&) { }
 207
 208
 209   template <class PMap, class Key>
 210   struct ReadWritePropertyMapConcept
 211   {
 212     typedef typename property_traits<PMap>::category Category;
 213     typedef boost::read_write_property_map_tag ReadWriteTag;
 214     void constraints() {
 215       function_requires< ReadablePropertyMapConcept<PMap, Key> >();
 216       function_requires< WritablePropertyMapConcept<PMap, Key> >();
 217       function_requires< ConvertibleConcept<Category, ReadWriteTag> >();
 218     }
 219   };
 220   template <typename KeyArchetype, typename ValueArchetype>
 221   struct read_write_property_map_archetype
 222     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
 223       public writable_property_map_archetype<KeyArchetype, ValueArchetype>
 224   {
 225     typedef KeyArchetype key_type;
 226     typedef ValueArchetype value_type;
 227     typedef convertible_to_archetype<ValueArchetype> reference;
 228     typedef read_write_property_map_tag category;
 229   };
 230
 231
 232   template <class PMap, class Key>
 233   struct LvaluePropertyMapConcept
 234   {
 235     typedef typename property_traits<PMap>::category Category;
 236     typedef boost::lvalue_property_map_tag LvalueTag;
 237     typedef typename property_traits<PMap>::reference reference;
 238
 239     void constraints() {
 240       function_requires< ReadablePropertyMapConcept<PMap, Key> >();
 241       function_requires< ConvertibleConcept<Category, LvalueTag> >();
 242
 243       typedef typename property_traits<PMap>::value_type value_type;
 244       typedef typename require_same<
 245         const value_type&, reference>::type req;
 246
 247       reference ref = pmap[k];
 248       ignore_unused_variable_warning(ref);
 249     }
 250     PMap pmap;
 251     Key k;
 252   };
 253   template <typename KeyArchetype, typename ValueArchetype>
 254   struct lvalue_property_map_archetype
 255     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>
 256   {
 257     typedef KeyArchetype key_type;
 258     typedef ValueArchetype value_type;
 259     typedef const ValueArchetype& reference;
 260     typedef lvalue_property_map_tag category;
 261     const value_type& operator[](const key_type&) const {
 262       return static_object<value_type>::get();
 263     }
 264   };
 265
 266   template <class PMap, class Key>
 267   struct Mutable_LvaluePropertyMapConcept
 268   {
 269     typedef typename property_traits<PMap>::category Category;
 270     typedef boost::lvalue_property_map_tag LvalueTag;
 271     typedef typename property_traits<PMap>::reference reference;
 272     void constraints() {
 273       boost::function_requires< ReadWritePropertyMapConcept<PMap, Key> >();
 274       boost::function_requires<ConvertibleConcept<Category, LvalueTag> >();
 275
 276       typedef typename property_traits<PMap>::value_type value_type;
 277       typedef typename require_same<
 278         value_type&,
 279         reference>::type req;
 280
 281       reference ref = pmap[k];
 282       ignore_unused_variable_warning(ref);
 283     }
 284     PMap pmap;
 285     Key k;
 286   };
 287   template <typename KeyArchetype, typename ValueArchetype>
 288   struct mutable_lvalue_property_map_archetype
 289     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
 290       public writable_property_map_archetype<KeyArchetype, ValueArchetype>
 291   {
 292     typedef KeyArchetype key_type;
 293     typedef ValueArchetype value_type;
 294     typedef ValueArchetype& reference;
 295     typedef lvalue_property_map_tag category;
 296     value_type& operator[](const key_type&) const {
 297       return static_object<value_type>::get();
 298     }
 299   };
 300
 301   struct identity_property_map;
 302
 303   // A helper class for constructing a property map
 304   // from a class that implements operator[]
 305
 306   template <class Reference, class LvaluePropertyMap>
 307   struct put_get_helper { };
 308
 309   template <class PropertyMap, class Reference, class K>
 310   inline Reference
 311   get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
 312   {
 313     Reference v = static_cast<const PropertyMap&>(pa)[k];
 314     return v;
 315   }
 316   template <class PropertyMap, class Reference, class K, class V>
 317   inline void
 318   put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
 319   {
 320     static_cast<const PropertyMap&>(pa)[k] = v;
 321   }
 322
 323   //=========================================================================
 324   // Adapter to turn a RandomAccessIterator into a property map
 325
 326   template <class RandomAccessIterator,
 327     class IndexMap
 328 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
 329     , class T, class R
 330 #else
 331     , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
 332     , class R = typename std::iterator_traits<RandomAccessIterator>::reference
 333 #endif
 334      >
 335   class iterator_property_map
 336     : public boost::put_get_helper< R,
 337         iterator_property_map<RandomAccessIterator, IndexMap,
 338         T, R> >
 339   {
 340   public:
 341     typedef typename property_traits<IndexMap>::key_type key_type;
 342     typedef T value_type;
 343     typedef R reference;
 344     typedef boost::lvalue_property_map_tag category;
 345
 346     inline iterator_property_map(
 347       RandomAccessIterator cc = RandomAccessIterator(),
 348       const IndexMap& _id = IndexMap() )
 349       : iter(cc), index(_id) { }
 350     inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }
 351   protected:
 352     RandomAccessIterator iter;
 353     IndexMap index;
 354   };
 355
 356 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
 357   template <class RAIter, class ID>
 358   inline iterator_property_map<
 359     RAIter, ID,
 360     typename std::iterator_traits<RAIter>::value_type,
 361     typename std::iterator_traits<RAIter>::reference>
 362   make_iterator_property_map(RAIter iter, ID id) {
 363     function_requires< RandomAccessIteratorConcept<RAIter> >();
 364     typedef iterator_property_map<
 365       RAIter, ID,
 366       typename std::iterator_traits<RAIter>::value_type,
 367       typename std::iterator_traits<RAIter>::reference> PA;
 368     return PA(iter, id);
 369   }
 370 #endif
 371   template <class RAIter, class Value, class ID>
 372   inline iterator_property_map<RAIter, ID, Value, Value&>
 373   make_iterator_property_map(RAIter iter, ID id, Value) {
 374     function_requires< RandomAccessIteratorConcept<RAIter> >();
 375     typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;
 376     return PMap(iter, id);
 377   }
 378
 379   template <class RandomAccessIterator,
 380     class IndexMap
 381 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
 382     , class T, class R
 383 #else
 384     , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
 385     , class R = typename std::iterator_traits<RandomAccessIterator>::reference
 386 #endif
 387      >
 388   class safe_iterator_property_map
 389     : public boost::put_get_helper< R,
 390         safe_iterator_property_map<RandomAccessIterator, IndexMap,
 391         T, R> >
 392   {
 393   public:
 394     typedef typename property_traits<IndexMap>::key_type key_type;
 395     typedef T value_type;
 396     typedef R reference;
 397     typedef boost::lvalue_property_map_tag category;
 398
 399     inline safe_iterator_property_map(
 400       RandomAccessIterator first = RandomAccessIterator(),
 401       std::size_t n = 0,
 402       const IndexMap& _id = IndexMap() )
 403       : iter(first), n(n), index(_id) { }
 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