ceph/src/boost/boost/property_map/property_map.hpp

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