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