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 

    18 namespace boost {

    19 

    20   //=========================================================================

    21   // property_traits class

    22 

    23   template <typename PA>

    24   struct property_traits {

    25     typedef typename PA::key_type key_type;

    26     typedef typename PA::value_type value_type; 

    27     typedef typename PA::reference reference;

    28     typedef typename PA::category   category;

    29   };

    30 

    31   //=========================================================================

    32   // property_traits category tags

    33 

    34   namespace detail {

    35     enum ePropertyMapID { READABLE_PA, WRITABLE_PA, 

    36                           READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA, 

    37                           RAND_ACCESS_ITER_PA, LAST_PA };

    38   }

    39   struct readable_property_map_tag { enum { id = detail::READABLE_PA }; };

    40   struct writable_property_map_tag { enum { id = detail::WRITABLE_PA }; };

    41   struct read_write_property_map_tag :

    42     public readable_property_map_tag,

    43     public writable_property_map_tag

    44   { enum { id = detail::READ_WRITE_PA }; };

    45 

    46   struct lvalue_property_map_tag : public read_write_property_map_tag

    47   { enum { id = detail::LVALUE_PA }; };

    48 

    49   //=========================================================================

    50   // property_traits specialization for pointers

    51 

    52 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    53   // The user will just have to create their own specializations for

    54   // other pointers types if the compiler does not have partial

    55   // specializations. Sorry!

    56 #define BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(TYPE) \

    57   template <> \

    58   struct property_traits<TYPE*> { \

    59     typedef TYPE value_type; \

    60     typedef value_type& reference; \

    61     typedef std::ptrdiff_t key_type; \

    62     typedef lvalue_property_map_tag   category; \

    63   }; \

    64   template <> \

    65   struct property_traits<const TYPE*> { \

    66     typedef TYPE value_type; \

    67     typedef const value_type& reference; \

    68     typedef std::ptrdiff_t key_type; \

    69     typedef lvalue_property_map_tag   category; \

    70   }

    71 

    72   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(long);

    73   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned long);

    74   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(int);

    75   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned int);

    76   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(short);

    77   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned short);

    78   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(char);

    79   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(unsigned char);

    80   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(signed char);

    81   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(bool);

    82   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(float);

    83   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(double);

    84   BOOST_SPECIALIZE_PROPERTY_TRAITS_PTR(long double);

    85 

    86   // This may need to be turned off for some older compilers that don't have

    87   // wchar_t intrinsically.

    88 # ifndef BOOST_NO_INTRINSIC_WCHAR_T

    89   template <>

    90   struct property_traits<wchar_t*> {

    91     typedef wchar_t value_type;

    92     typedef value_type& reference;

    93     typedef std::ptrdiff_t key_type;

    94     typedef lvalue_property_map_tag   category;

    95   };

    96   template <>

    97   struct property_traits<const wchar_t*> {

    98     typedef wchar_t value_type;

    99     typedef const value_type& reference;

   100     typedef std::ptrdiff_t key_type;

   101     typedef lvalue_property_map_tag   category;

   102   };

   103 # endif

   104 

   105 #else

   106   template <class T>

   107   struct property_traits<T*> {

   108     typedef T value_type;

   109     typedef value_type& reference;

   110     typedef std::ptrdiff_t key_type;

   111     typedef lvalue_property_map_tag category;

   112   };

   113   template <class T>

   114   struct property_traits<const T*> {

   115     typedef T value_type;

   116     typedef const value_type& reference;

   117     typedef std::ptrdiff_t key_type;

   118     typedef lvalue_property_map_tag category;

   119   };

   120 #endif

   121 

   122 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)

   123   // MSVC doesn't have Koenig lookup, so the user has to

   124   // do boost::get() anyways, and the using clause

   125   // doesn't really work for MSVC.

   126 } // namespace boost

   127 #endif

   128 

   129   // These need to go in global namespace because Koenig

   130   // lookup does not apply to T*.

   131 

   132   // V must be convertible to T

   133   template <class T, class V>

   134   inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val;  }

   135 

   136   template <class T>

   137   inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }

   138 

   139 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)

   140 namespace boost {

   141   using ::put;

   142   using ::get;

   143 #endif

   144 

   145   //=========================================================================

   146   // concept checks for property maps

   147 

   148   template <class PMap, class Key>

   149   struct ReadablePropertyMapConcept

   150   {

   151     typedef typename property_traits<PMap>::key_type key_type;

   152     typedef typename property_traits<PMap>::reference reference;

   153     typedef typename property_traits<PMap>::category Category;

   154     typedef boost::readable_property_map_tag ReadableTag;

   155     void constraints() {

   156       function_requires< ConvertibleConcept<Category, ReadableTag> >();

   157 

   158       val = get(pmap, k);

   159     }

   160     PMap pmap;

   161     Key k;

   162     typename property_traits<PMap>::value_type val;

   163   };

   164   template <typename KeyArchetype, typename ValueArchetype>

   165   struct readable_property_map_archetype {

   166     typedef KeyArchetype key_type;

   167     typedef ValueArchetype value_type;

   168     typedef convertible_to_archetype<ValueArchetype> reference;

   169     typedef readable_property_map_tag category;

   170   };

   171   template <typename K, typename V>

   172   const typename readable_property_map_archetype<K,V>::reference&

   173   get(const readable_property_map_archetype<K,V>&, 

   174       const typename readable_property_map_archetype<K,V>::key_type&)

   175   {

   176     typedef typename readable_property_map_archetype<K,V>::reference R;

   177     return static_object<R>::get();

   178   }

   179 

   180 

   181   template <class PMap, class Key>

   182   struct WritablePropertyMapConcept

   183   {

   184     typedef typename property_traits<PMap>::key_type key_type;

   185     typedef typename property_traits<PMap>::category Category;

   186     typedef boost::writable_property_map_tag WritableTag;

   187     void constraints() {

   188       function_requires< ConvertibleConcept<Category, WritableTag> >();

   189       put(pmap, k, val);

   190     }

   191     PMap pmap;

   192     Key k;

   193     typename property_traits<PMap>::value_type val;

   194   };

   195   template <typename KeyArchetype, typename ValueArchetype>

   196   struct writable_property_map_archetype {

   197     typedef KeyArchetype key_type;

   198     typedef ValueArchetype value_type;

   199     typedef void reference;

   200     typedef writable_property_map_tag category;

   201   };

   202   template <typename K, typename V>

   203   void put(const writable_property_map_archetype<K,V>&, 

   204            const typename writable_property_map_archetype<K,V>::key_type&, 

   205            const typename writable_property_map_archetype<K,V>::value_type&) { }

   206 

   207 

   208   template <class PMap, class Key>

   209   struct ReadWritePropertyMapConcept

   210   {

   211     typedef typename property_traits<PMap>::category Category;

   212     typedef boost::read_write_property_map_tag ReadWriteTag;

   213     void constraints() {

   214       function_requires< ReadablePropertyMapConcept<PMap, Key> >();

   215       function_requires< WritablePropertyMapConcept<PMap, Key> >();

   216       function_requires< ConvertibleConcept<Category, ReadWriteTag> >();

   217     }

   218   };

   219   template <typename KeyArchetype, typename ValueArchetype>

   220   struct read_write_property_map_archetype

   221     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,

   222       public writable_property_map_archetype<KeyArchetype, ValueArchetype>

   223   {

   224     typedef KeyArchetype key_type;

   225     typedef ValueArchetype value_type;

   226     typedef convertible_to_archetype<ValueArchetype> reference;

   227     typedef read_write_property_map_tag category;

   228   };

   229 

   230 

   231   template <class PMap, class Key>

   232   struct LvaluePropertyMapConcept

   233   {

   234     typedef typename property_traits<PMap>::category Category;

   235     typedef boost::lvalue_property_map_tag LvalueTag;

   236     typedef typename property_traits<PMap>::reference reference;

   237 

   238     void constraints() {

   239       function_requires< ReadablePropertyMapConcept<PMap, Key> >();

   240       function_requires< ConvertibleConcept<Category, LvalueTag> >();

   241 

   242       typedef typename property_traits<PMap>::value_type value_type;

   243       typedef typename require_same<

   244         const value_type&, reference>::type req;

   245 

   246       reference ref = pmap[k];

   247       ignore_unused_variable_warning(ref);

   248     }

   249     PMap pmap;

   250     Key k;

   251   };

   252   template <typename KeyArchetype, typename ValueArchetype>

   253   struct lvalue_property_map_archetype

   254     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>

   255   {

   256     typedef KeyArchetype key_type;

   257     typedef ValueArchetype value_type;

   258     typedef const ValueArchetype& reference;

   259     typedef lvalue_property_map_tag category;

   260     const value_type& operator[](const key_type&) const {

   261       return static_object<value_type>::get();

   262     }

   263   };

   264 

   265   template <class PMap, class Key>

   266   struct Mutable_LvaluePropertyMapConcept

   267   {

   268     typedef typename property_traits<PMap>::category Category;

   269     typedef boost::lvalue_property_map_tag LvalueTag;

   270     typedef typename property_traits<PMap>::reference reference;

   271     void constraints() { 

   272       boost::function_requires< ReadWritePropertyMapConcept<PMap, Key> >();

   273       boost::function_requires<ConvertibleConcept<Category, LvalueTag> >();

   274       

   275       typedef typename property_traits<PMap>::value_type value_type;

   276       typedef typename require_same<

   277         value_type&,

   278         reference>::type req;

   279 

   280       reference ref = pmap[k];

   281       ignore_unused_variable_warning(ref);

   282     }

   283     PMap pmap;

   284     Key k;

   285   };

   286   template <typename KeyArchetype, typename ValueArchetype>

   287   struct mutable_lvalue_property_map_archetype

   288     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,

   289       public writable_property_map_archetype<KeyArchetype, ValueArchetype>

   290   {

   291     typedef KeyArchetype key_type;

   292     typedef ValueArchetype value_type;

   293     typedef ValueArchetype& reference;

   294     typedef lvalue_property_map_tag category;

   295     value_type& operator[](const key_type&) const { 

   296       return static_object<value_type>::get();

   297     }

   298   };

   299 

   300   struct identity_property_map;

   301 

   302   // A helper class for constructing a property map

   303   // from a class that implements operator[]

   304 

   305   template <class Reference, class LvaluePropertyMap>

   306   struct put_get_helper { };

   307 

   308   template <class PropertyMap, class Reference, class K>

   309   inline Reference

   310   get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)

   311   {

   312     Reference v = static_cast<const PropertyMap&>(pa)[k];

   313     return v;

   314   }

   315   template <class PropertyMap, class Reference, class K, class V>

   316   inline void

   317   put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)

   318   {

   319     static_cast<const PropertyMap&>(pa)[k] = v;

   320   }

   321 

   322   //=========================================================================

   323   // Adapter to turn a RandomAccessIterator into a property map

   324 

   325   template <class RandomAccessIterator, 

   326     class IndexMap

   327 #ifdef BOOST_NO_STD_ITERATOR_TRAITS

   328     , class T, class R

   329 #else

   330     , class T = typename std::iterator_traits<RandomAccessIterator>::value_type

   331     , class R = typename std::iterator_traits<RandomAccessIterator>::reference

   332 #endif

   333      >

   334   class iterator_property_map

   335     : public boost::put_get_helper< R, 

   336         iterator_property_map<RandomAccessIterator, IndexMap,

   337         T, R> >

   338   {

   339   public:

   340     typedef typename property_traits<IndexMap>::key_type key_type;

   341     typedef T value_type;

   342     typedef R reference;

   343     typedef boost::lvalue_property_map_tag category;

   344 

   345     inline iterator_property_map(

   346       RandomAccessIterator cc = RandomAccessIterator(), 

   347       const IndexMap& _id = IndexMap() ) 

   348       : iter(cc), index(_id) { }

   349     inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }

   350   protected:

   351     RandomAccessIterator iter;

   352     IndexMap index;

   353   };

   354 

   355 #if !defined BOOST_NO_STD_ITERATOR_TRAITS

   356   template <class RAIter, class ID>

   357   inline iterator_property_map<

   358     RAIter, ID,

   359     typename std::iterator_traits<RAIter>::value_type,

   360     typename std::iterator_traits<RAIter>::reference>

   361   make_iterator_property_map(RAIter iter, ID id) {

   362     function_requires< RandomAccessIteratorConcept<RAIter> >();

   363     typedef iterator_property_map<

   364       RAIter, ID,

   365       typename std::iterator_traits<RAIter>::value_type,

   366       typename std::iterator_traits<RAIter>::reference> PA;

   367     return PA(iter, id);

   368   }

   369 #endif

   370   template <class RAIter, class Value, class ID>

   371   inline iterator_property_map<RAIter, ID, Value, Value&>

   372   make_iterator_property_map(RAIter iter, ID id, Value) {

   373     function_requires< RandomAccessIteratorConcept<RAIter> >();

   374     typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;

   375     return PMap(iter, id);

   376   }

   377 

   378   template <class RandomAccessIterator, 

   379     class IndexMap

   380 #ifdef BOOST_NO_STD_ITERATOR_TRAITS

   381     , class T, class R

   382 #else

   383     , class T = typename std::iterator_traits<RandomAccessIterator>::value_type

   384     , class R = typename std::iterator_traits<RandomAccessIterator>::reference

   385 #endif

   386      >

   387   class safe_iterator_property_map

   388     : public boost::put_get_helper< R, 

   389         safe_iterator_property_map<RandomAccessIterator, IndexMap,

   390         T, R> >

   391   {

   392   public:

   393     typedef typename property_traits<IndexMap>::key_type key_type; 

   394     typedef T value_type;

   395     typedef R reference;

   396     typedef boost::lvalue_property_map_tag category;

   397 

   398     inline safe_iterator_property_map(

   399       RandomAccessIterator first, 

   400       std::size_t n_ = 0, 

   401       const IndexMap& _id = IndexMap() ) 

   402       : iter(first), n(n_), index(_id) { }

   403     inline safe_iterator_property_map() { }

   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