boost/property_map/property_map.hpp

0001 //  (C) Copyright Jeremy Siek 1999-2001.
0002 //  Copyright (C) 2006 Trustees of Indiana University
0003 //  Authors: Douglas Gregor and Jeremy Siek
0004
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 //  See http://www.boost.org/libs/property_map for documentation.
0010
0011 #ifndef BOOST_PROPERTY_MAP_HPP
0012 #define BOOST_PROPERTY_MAP_HPP
0013
0014 #include <boost/assert.hpp>
0015 #include <boost/config.hpp>
0016 #include <boost/static_assert.hpp>
0017 #include <cstddef>
0018 #include <iterator>
0019 #include <boost/concept/assert.hpp>
0020 #include <boost/concept_check.hpp>
0021 #include <boost/concept_archetype.hpp>
0022 #include <boost/mpl/assert.hpp>
0023 #include <boost/mpl/if.hpp>
0024 #include <boost/mpl/or.hpp>
0025 #include <boost/mpl/and.hpp>
0026 #include <boost/mpl/has_xxx.hpp>
0027 #include <boost/type_traits/is_same.hpp>
0028
0029 namespace boost {
0030
0031   //=========================================================================
0032   // property_traits class
0033
0034   BOOST_MPL_HAS_XXX_TRAIT_DEF(key_type)
0035   BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
0036   BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
0037   BOOST_MPL_HAS_XXX_TRAIT_DEF(category)
0038
0039   template<class PA>
0040   struct is_property_map :
0041     boost::mpl::and_<
0042       has_key_type<PA>,
0043       has_value_type<PA>,
0044       has_reference<PA>,
0045       has_category<PA>
0046     >
0047   {};
0048
0049   template <typename PA>
0050   struct default_property_traits {
0051     typedef typename PA::key_type key_type;
0052     typedef typename PA::value_type value_type;
0053     typedef typename PA::reference reference;
0054     typedef typename PA::category   category;
0055   };
0056
0057   struct null_property_traits {};
0058
0059   template <typename PA>
0060   struct property_traits :
0061     boost::mpl::if_<is_property_map<PA>,
0062       default_property_traits<PA>,
0063       null_property_traits>::type
0064   {};
0065
0066 #if 0
0067   template <typename PA>
0068   struct property_traits {
0069     typedef typename PA::key_type key_type;
0070     typedef typename PA::value_type value_type;
0071     typedef typename PA::reference reference;
0072     typedef typename PA::category   category;
0073   };
0074 #endif
0075
0076   //=========================================================================
0077   // property_traits category tags
0078
0079   namespace detail {
0080     enum ePropertyMapID { READABLE_PA, WRITABLE_PA,
0081                           READ_WRITE_PA, LVALUE_PA, OP_BRACKET_PA,
0082                           RAND_ACCESS_ITER_PA, LAST_PA };
0083   }
0084   struct readable_property_map_tag { enum { id = detail::READABLE_PA }; };
0085   struct writable_property_map_tag { enum { id = detail::WRITABLE_PA }; };
0086   struct read_write_property_map_tag :
0087     public readable_property_map_tag,
0088     public writable_property_map_tag
0089   { enum { id = detail::READ_WRITE_PA }; };
0090
0091   struct lvalue_property_map_tag : public read_write_property_map_tag
0092   { enum { id = detail::LVALUE_PA }; };
0093
0094   //=========================================================================
0095   // property_traits specialization for pointers
0096
0097   template <class T>
0098   struct property_traits<T*> {
0099     // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
0100     typedef T value_type;
0101     typedef value_type& reference;
0102     typedef std::ptrdiff_t key_type;
0103     typedef lvalue_property_map_tag category;
0104   };
0105   template <class T>
0106   struct property_traits<const T*> {
0107     // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
0108     typedef T value_type;
0109     typedef const value_type& reference;
0110     typedef std::ptrdiff_t key_type;
0111     typedef lvalue_property_map_tag category;
0112   };
0113
0114 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
0115   // MSVC doesn't have Koenig lookup, so the user has to
0116   // do boost::get() anyways, and the using clause
0117   // doesn't really work for MSVC.
0118 } // namespace boost
0119 #endif
0120
0121   // These need to go in global namespace because Koenig
0122   // lookup does not apply to T*.
0123
0124   // V must be convertible to T
0125   template <class T, class V>
0126   inline void put(T* pa, std::ptrdiff_t k, const V& val) { pa[k] = val;  }
0127
0128   template <class T>
0129   inline const T& get(const T* pa, std::ptrdiff_t k) { return pa[k]; }
0130
0131 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
0132 namespace boost {
0133   using ::put;
0134   using ::get;
0135 #endif
0136
0137   //=========================================================================
0138   // concept checks for property maps
0139
0140   template <class PMap, class Key>
0141   struct ReadablePropertyMapConcept
0142   {
0143     typedef typename property_traits<PMap>::key_type key_type;
0144     typedef typename property_traits<PMap>::reference reference;
0145     typedef typename property_traits<PMap>::category Category;
0146     typedef boost::readable_property_map_tag ReadableTag;
0147     void constraints() {
0148       BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, ReadableTag>));
0149
0150       val = get(pmap, k);
0151     }
0152     PMap pmap;
0153     Key k;
0154     typename property_traits<PMap>::value_type val;
0155   };
0156   template <typename KeyArchetype, typename ValueArchetype>
0157   struct readable_property_map_archetype {
0158     typedef KeyArchetype key_type;
0159     typedef ValueArchetype value_type;
0160     typedef convertible_to_archetype<ValueArchetype> reference;
0161     typedef readable_property_map_tag category;
0162   };
0163   template <typename K, typename V>
0164   const typename readable_property_map_archetype<K,V>::reference&
0165   get(const readable_property_map_archetype<K,V>&,
0166       const typename readable_property_map_archetype<K,V>::key_type&)
0167   {
0168     typedef typename readable_property_map_archetype<K,V>::reference R;
0169     return static_object<R>::get();
0170   }
0171
0172
0173   template <class PMap, class Key>
0174   struct WritablePropertyMapConcept
0175   {
0176     typedef typename property_traits<PMap>::key_type key_type;
0177     typedef typename property_traits<PMap>::category Category;
0178     typedef boost::writable_property_map_tag WritableTag;
0179     void constraints() {
0180       BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, WritableTag>));
0181       put(pmap, k, val);
0182     }
0183     PMap pmap;
0184     Key k;
0185     typename property_traits<PMap>::value_type val;
0186   };
0187   template <typename KeyArchetype, typename ValueArchetype>
0188   struct writable_property_map_archetype {
0189     typedef KeyArchetype key_type;
0190     typedef ValueArchetype value_type;
0191     typedef void reference;
0192     typedef writable_property_map_tag category;
0193   };
0194   template <typename K, typename V>
0195   void put(const writable_property_map_archetype<K,V>&,
0196            const typename writable_property_map_archetype<K,V>::key_type&,
0197            const typename writable_property_map_archetype<K,V>::value_type&) { }
0198
0199
0200   template <class PMap, class Key>
0201   struct ReadWritePropertyMapConcept
0202   {
0203     typedef typename property_traits<PMap>::category Category;
0204     typedef boost::read_write_property_map_tag ReadWriteTag;
0205     void constraints() {
0206       BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<PMap, Key>));
0207       BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept<PMap, Key>));
0208       BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, ReadWriteTag>));
0209     }
0210   };
0211   template <typename KeyArchetype, typename ValueArchetype>
0212   struct read_write_property_map_archetype
0213     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
0214       public writable_property_map_archetype<KeyArchetype, ValueArchetype>
0215   {
0216     typedef KeyArchetype key_type;
0217     typedef ValueArchetype value_type;
0218     typedef convertible_to_archetype<ValueArchetype> reference;
0219     typedef read_write_property_map_tag category;
0220   };
0221
0222
0223   template <class PMap, class Key>
0224   struct LvaluePropertyMapConcept
0225   {
0226     typedef typename property_traits<PMap>::category Category;
0227     typedef boost::lvalue_property_map_tag LvalueTag;
0228     typedef typename property_traits<PMap>::reference reference;
0229
0230     void constraints() {
0231       BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<PMap, Key>));
0232       BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, LvalueTag>));
0233
0234       typedef typename property_traits<PMap>::value_type value_type;
0235       BOOST_MPL_ASSERT((boost::mpl::or_<
0236                           boost::is_same<const value_type&, reference>,
0237                           boost::is_same<value_type&, reference> >));
0238
0239       reference ref = pmap[k];
0240       ignore_unused_variable_warning(ref);
0241     }
0242     PMap pmap;
0243     Key k;
0244   };
0245   template <typename KeyArchetype, typename ValueArchetype>
0246   struct lvalue_property_map_archetype
0247     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>
0248   {
0249     typedef KeyArchetype key_type;
0250     typedef ValueArchetype value_type;
0251     typedef const ValueArchetype& reference;
0252     typedef lvalue_property_map_tag category;
0253     const value_type& operator[](const key_type&) const {
0254       return static_object<value_type>::get();
0255     }
0256   };
0257
0258   template <class PMap, class Key>
0259   struct Mutable_LvaluePropertyMapConcept
0260   {
0261     typedef typename property_traits<PMap>::category Category;
0262     typedef boost::lvalue_property_map_tag LvalueTag;
0263     typedef typename property_traits<PMap>::reference reference;
0264     void constraints() {
0265       BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<PMap, Key>));
0266       BOOST_CONCEPT_ASSERT((ConvertibleConcept<Category, LvalueTag>));
0267
0268       typedef typename property_traits<PMap>::value_type value_type;
0269       BOOST_MPL_ASSERT((boost::is_same<value_type&, reference>));
0270
0271       reference ref = pmap[k];
0272       ignore_unused_variable_warning(ref);
0273     }
0274     PMap pmap;
0275     Key k;
0276   };
0277   template <typename KeyArchetype, typename ValueArchetype>
0278   struct mutable_lvalue_property_map_archetype
0279     : public readable_property_map_archetype<KeyArchetype, ValueArchetype>,
0280       public writable_property_map_archetype<KeyArchetype, ValueArchetype>
0281   {
0282     typedef KeyArchetype key_type;
0283     typedef ValueArchetype value_type;
0284     typedef ValueArchetype& reference;
0285     typedef lvalue_property_map_tag category;
0286     value_type& operator[](const key_type&) const {
0287       return static_object<value_type>::get();
0288     }
0289   };
0290
0291   template <typename T>
0292   struct typed_identity_property_map;
0293
0294   // A helper class for constructing a property map
0295   // from a class that implements operator[]
0296
0297   template <class Reference, class LvaluePropertyMap>
0298   struct put_get_helper { };
0299
0300   template <class PropertyMap, class Reference, class K>
0301   inline Reference
0302   get(const put_get_helper<Reference, PropertyMap>& pa, const K& k)
0303   {
0304     Reference v = static_cast<const PropertyMap&>(pa)[k];
0305     return v;
0306   }
0307   template <class PropertyMap, class Reference, class K, class V>
0308   inline void
0309   put(const put_get_helper<Reference, PropertyMap>& pa, K k, const V& v)
0310   {
0311     static_cast<const PropertyMap&>(pa)[k] = v;
0312   }
0313
0314   //=========================================================================
0315   // Adapter to turn a RandomAccessIterator into a property map
0316
0317   template <class RandomAccessIterator,
0318     class IndexMap
0319 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0320     , class T, class R
0321 #else
0322     , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
0323     , class R = typename std::iterator_traits<RandomAccessIterator>::reference
0324 #endif
0325      >
0326   class iterator_property_map
0327     : public boost::put_get_helper< R,
0328         iterator_property_map<RandomAccessIterator, IndexMap,
0329         T, R> >
0330   {
0331   public:
0332     typedef typename property_traits<IndexMap>::key_type key_type;
0333     typedef T value_type;
0334     typedef R reference;
0335     typedef boost::lvalue_property_map_tag category;
0336
0337     inline iterator_property_map(
0338       RandomAccessIterator cc = RandomAccessIterator(),
0339       const IndexMap& _id = IndexMap() )
0340       : iter(cc), index(_id) { }
0341     inline R operator[](key_type v) const { return *(iter + get(index, v)) ; }
0342   protected:
0343     RandomAccessIterator iter;
0344     IndexMap index;
0345   };
0346
0347 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
0348   template <class RAIter, class ID>
0349   inline iterator_property_map<
0350     RAIter, ID,
0351     typename std::iterator_traits<RAIter>::value_type,
0352     typename std::iterator_traits<RAIter>::reference>
0353   make_iterator_property_map(RAIter iter, ID id) {
0354     BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>));
0355     typedef iterator_property_map<
0356       RAIter, ID,
0357       typename std::iterator_traits<RAIter>::value_type,
0358       typename std::iterator_traits<RAIter>::reference> PA;
0359     return PA(iter, id);
0360   }
0361 #endif
0362   template <class RAIter, class Value, class ID>
0363   inline iterator_property_map<RAIter, ID, Value, Value&>
0364   make_iterator_property_map(RAIter iter, ID id, Value) {
0365     BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>));
0366     typedef iterator_property_map<RAIter, ID, Value, Value&> PMap;
0367     return PMap(iter, id);
0368   }
0369
0370   template <class RandomAccessIterator,
0371     class IndexMap
0372 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0373     , class T, class R
0374 #else
0375     , class T = typename std::iterator_traits<RandomAccessIterator>::value_type
0376     , class R = typename std::iterator_traits<RandomAccessIterator>::reference
0377 #endif
0378      >
0379   class safe_iterator_property_map
0380     : public boost::put_get_helper< R,
0381         safe_iterator_property_map<RandomAccessIterator, IndexMap,
0382         T, R> >
0383   {
0384   public:
0385     typedef typename property_traits<IndexMap>::key_type key_type;
0386     typedef T value_type;
0387     typedef R reference;
0388     typedef boost::lvalue_property_map_tag category;
0389
0390     inline safe_iterator_property_map(
0391       RandomAccessIterator first,
0392       std::size_t n_ = 0,
0393       const IndexMap& _id = IndexMap() )
0394       : iter(first), n(n_), index(_id) { }
0395     inline safe_iterator_property_map() { }
0396     inline R operator[](key_type v) const {
0397       BOOST_ASSERT(get(index, v) < n);
0398       return *(iter + get(index, v)) ;
0399     }
0400     typename property_traits<IndexMap>::value_type size() const { return n; }
0401   protected:
0402     RandomAccessIterator iter;
0403     typename property_traits<IndexMap>::value_type n;
0404     IndexMap index;
0405   };
0406
0407   template <class RAIter, class ID>
0408   inline safe_iterator_property_map<
0409     RAIter, ID,
0410     typename std::iterator_traits<RAIter>::value_type,
0411     typename std::iterator_traits<RAIter>::reference>
0412   make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id) {
0413     BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>));
0414     typedef safe_iterator_property_map<
0415       RAIter, ID,
0416       typename std::iterator_traits<RAIter>::value_type,
0417       typename std::iterator_traits<RAIter>::reference> PA;
0418     return PA(iter, n, id);
0419   }
0420   template <class RAIter, class Value, class ID>
0421   inline safe_iterator_property_map<RAIter, ID, Value, Value&>
0422   make_safe_iterator_property_map(RAIter iter, std::size_t n, ID id, Value) {
0423     BOOST_CONCEPT_ASSERT((RandomAccessIteratorConcept<RAIter>));
0424     typedef safe_iterator_property_map<RAIter, ID, Value, Value&> PMap;
0425     return PMap(iter, n, id);
0426   }
0427
0428   //=========================================================================
0429   // An adaptor to turn a Unique Pair Associative Container like std::map or
0430   // std::hash_map into an Lvalue Property Map.
0431
0432   template <typename UniquePairAssociativeContainer>
0433   class associative_property_map
0434     : public boost::put_get_helper<
0435        typename UniquePairAssociativeContainer::value_type::second_type&,
0436        associative_property_map<UniquePairAssociativeContainer> >
0437   {
0438     typedef UniquePairAssociativeContainer C;
0439   public:
0440     typedef typename C::key_type key_type;
0441     typedef typename C::value_type::second_type value_type;
0442     typedef value_type& reference;
0443     typedef lvalue_property_map_tag category;
0444     associative_property_map() : m_c(0) { }
0445     associative_property_map(C& c) : m_c(&c) { }
0446     reference operator[](const key_type& k) const {
0447       return (*m_c)[k];
0448     }
0449   private:
0450     C* m_c;
0451   };
0452
0453   template <class UniquePairAssociativeContainer>
0454   associative_property_map<UniquePairAssociativeContainer>
0455   make_assoc_property_map(UniquePairAssociativeContainer& c)
0456   {
0457     return associative_property_map<UniquePairAssociativeContainer>(c);
0458   }
0459
0460   template <typename UniquePairAssociativeContainer>
0461   class const_associative_property_map
0462     : public boost::put_get_helper<
0463        const typename UniquePairAssociativeContainer::value_type::second_type&,
0464        const_associative_property_map<UniquePairAssociativeContainer> >
0465   {
0466     typedef UniquePairAssociativeContainer C;
0467   public:
0468     typedef typename C::key_type key_type;
0469     typedef typename C::value_type::second_type value_type;
0470     typedef const value_type& reference;
0471     typedef lvalue_property_map_tag category;
0472     const_associative_property_map() : m_c(0) { }
0473     const_associative_property_map(const C& c) : m_c(&c) { }
0474     reference operator[](const key_type& k) const {
0475       return m_c->find(k)->second;
0476     }
0477   private:
0478     C const* m_c;
0479   };
0480
0481   template <class UniquePairAssociativeContainer>
0482   const_associative_property_map<UniquePairAssociativeContainer>
0483   make_assoc_property_map(const UniquePairAssociativeContainer& c)
0484   {
0485     return const_associative_property_map<UniquePairAssociativeContainer>(c);
0486   }
0487
0488   //=========================================================================
0489   // A property map that always returns the same object by value.
0490   //
0491   template <typename ValueType, typename KeyType = void>
0492   class static_property_map :
0493       public
0494   boost::put_get_helper<ValueType,static_property_map<ValueType> >
0495   {
0496     ValueType value;
0497   public:
0498     typedef KeyType key_type;
0499     typedef ValueType value_type;
0500     typedef ValueType reference;
0501     typedef readable_property_map_tag category;
0502     static_property_map(ValueType v) : value(v) {}
0503
0504     template<typename T>
0505     inline reference operator[](T) const { return value; }
0506   };
0507
0508   template <typename KeyType, typename ValueType>
0509   static_property_map<ValueType, KeyType>
0510   make_static_property_map(const ValueType& v) {
0511     return static_property_map<ValueType, KeyType>(v);
0512   }
0513
0514   //=========================================================================
0515   // A property map that always returns a reference to the same object.
0516   //
0517   template <typename KeyType, typename ValueType>
0518   class ref_property_map :
0519     public
0520       boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> >
0521   {
0522     ValueType* value;
0523   public:
0524     typedef KeyType key_type;
0525     typedef ValueType value_type;
0526     typedef ValueType& reference;
0527     typedef lvalue_property_map_tag category;
0528     ref_property_map(ValueType& v) : value(&v) {}
0529     ValueType& operator[](key_type const&) const { return *value; }
0530   };
0531
0532   //=========================================================================
0533   // A generalized identity property map
0534   template <typename T>
0535   struct typed_identity_property_map
0536     : public boost::put_get_helper<T, typed_identity_property_map<T> >
0537   {
0538     typedef T key_type;
0539     typedef T value_type;
0540     typedef T reference;
0541     typedef boost::readable_property_map_tag category;
0542
0543     inline value_type operator[](const key_type& v) const { return v; }
0544   };
0545
0546 //=========================================================================
0547   // A property map that applies the identity function to integers
0548   typedef typed_identity_property_map<std::size_t> identity_property_map;
0549
0550   //=========================================================================
0551   // A property map that does not do anything, for
0552   // when you have to supply a property map, but don't need it.
0553   namespace detail {
0554     struct dummy_pmap_reference {
0555       template <class T>
0556       dummy_pmap_reference& operator=(const T&) { return *this; }
0557       operator int() { return 0; }
0558     };
0559   }
0560   class dummy_property_map
0561     : public boost::put_get_helper<detail::dummy_pmap_reference,
0562         dummy_property_map  >
0563   {
0564   public:
0565     typedef void key_type;
0566     typedef int value_type;
0567     typedef detail::dummy_pmap_reference reference;
0568     typedef boost::read_write_property_map_tag category;
0569     inline dummy_property_map() : c(0) { }
0570     inline dummy_property_map(value_type cc) : c(cc) { }
0571     inline dummy_property_map(const dummy_property_map& x)
0572       : c(x.c) { }
0573     template <class Vertex>
0574     inline reference operator[](Vertex) const { return reference(); }
0575    protected:
0576     value_type c;
0577   };
0578
0579   // Convert a Readable property map into a function object
0580   template <typename PropMap>
0581   class property_map_function {
0582     PropMap pm;
0583     typedef typename property_traits<PropMap>::key_type param_type;
0584     public:
0585     explicit property_map_function(const PropMap& pm): pm(pm) {}
0586     typedef typename property_traits<PropMap>::value_type result_type;
0587     result_type operator()(const param_type& k) const {return get(pm, k);}
0588   };
0589
0590   template <typename PropMap>
0591   property_map_function<PropMap>
0592   make_property_map_function(const PropMap& pm) {
0593     return property_map_function<PropMap>(pm);
0594   }
0595
0596 } // namespace boost
0597
0598 #include <boost/property_map/vector_property_map.hpp>
0599
0600 #endif /* BOOST_PROPERTY_MAP_HPP */
0601