ceph/src/boost/libs/intrusive/include/boost/intrusive/treap_set.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2007-2014
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See 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/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 #ifndef BOOST_INTRUSIVE_TREAP_SET_HPP
  13 #define BOOST_INTRUSIVE_TREAP_SET_HPP
  14
  15 #include <boost/intrusive/detail/config_begin.hpp>
  16 #include <boost/intrusive/intrusive_fwd.hpp>
  17 #include <boost/intrusive/treap.hpp>
  18 #include <boost/intrusive/detail/mpl.hpp>
  19 #include <boost/move/utility_core.hpp>
  20 #include <boost/static_assert.hpp>
  21
  22 #if defined(BOOST_HAS_PRAGMA_ONCE)
  23 #  pragma once
  24 #endif
  25
  26 namespace boost {
  27 namespace intrusive {
  28
  29 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  30 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
  31 class treap_multiset_impl;
  32 #endif
  33
  34 //! The class template treap_set is an intrusive container, that mimics most of
  35 //! the interface of std::set as described in the C++ standard.
  36 //!
  37 //! The template parameter \c T is the type to be managed by the container.
  38 //! The user can specify additional options and if no options are provided
  39 //! default options are used.
  40 //!
  41 //! The container supports the following options:
  42 //! \c base_hook<>/member_hook<>/value_traits<>,
  43 //! \c constant_time_size<>, \c size_type<>,
  44 //! \c compare<> and \c priority_compare<>
  45 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  46 template<class T, class ...Options>
  47 #else
  48 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
  49 #endif
  50 class treap_set_impl
  51 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
  52    : public treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder>
  53 #endif
  54 {
  55    /// @cond
  56    public:
  57    typedef treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
  58    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_set_impl)
  59
  60    typedef tree_type implementation_defined;
  61    /// @endcond
  62
  63    public:
  64    typedef typename implementation_defined::value_type               value_type;
  65    typedef typename implementation_defined::value_traits             value_traits;
  66    typedef typename implementation_defined::key_type                 key_type;
  67    typedef typename implementation_defined::key_of_value             key_of_value;
  68    typedef typename implementation_defined::pointer                  pointer;
  69    typedef typename implementation_defined::const_pointer            const_pointer;
  70    typedef typename implementation_defined::reference                reference;
  71    typedef typename implementation_defined::const_reference          const_reference;
  72    typedef typename implementation_defined::difference_type          difference_type;
  73    typedef typename implementation_defined::size_type                size_type;
  74    typedef typename implementation_defined::value_compare            value_compare;
  75    typedef typename implementation_defined::key_compare              key_compare;
  76    typedef typename implementation_defined::priority_compare         priority_compare;
  77    typedef typename implementation_defined::iterator                 iterator;
  78    typedef typename implementation_defined::const_iterator           const_iterator;
  79    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
  80    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
  81    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
  82    typedef typename implementation_defined::node_traits              node_traits;
  83    typedef typename implementation_defined::node                     node;
  84    typedef typename implementation_defined::node_ptr                 node_ptr;
  85    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
  86    typedef typename implementation_defined::node_algorithms          node_algorithms;
  87
  88    static const bool constant_time_size = implementation_defined::constant_time_size;
  89
  90    public:
  91    //! @copydoc ::boost::intrusive::treap::treap()
  92    treap_set_impl()
  93       :  tree_type()
  94    {}
  95
  96    //! @copydoc ::boost::intrusive::treap::treap(const key_compare &,const priority_compare &,const value_traits &)
  97    explicit treap_set_impl( const key_compare &cmp
  98                           , const priority_compare &pcmp  = priority_compare()
  99                           , const value_traits &v_traits  = value_traits())
 100       :  tree_type(cmp, pcmp, v_traits)
 101    {}
 102
 103    //! @copydoc ::boost::intrusive::treap::treap(bool,Iterator,Iterator,const key_compare &,const priority_compare &,const value_traits &)
 104    template<class Iterator>
 105    treap_set_impl( Iterator b, Iterator e
 106            , const key_compare &cmp = key_compare()
 107            , const priority_compare &pcmp  = priority_compare()
 108            , const value_traits &v_traits = value_traits())
 109       : tree_type(true, b, e, cmp, pcmp, v_traits)
 110    {}
 111
 112    //! <b>Effects</b>: to-do
 113    //!
 114    treap_set_impl(BOOST_RV_REF(treap_set_impl) x)
 115       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
 116    {}
 117
 118    //! <b>Effects</b>: to-do
 119    //!
 120    treap_set_impl& operator=(BOOST_RV_REF(treap_set_impl) x)
 121    {  return static_cast<treap_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));  }
 122
 123    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 124    //! @copydoc ::boost::intrusive::treap::~treap()
 125    ~treap_set_impl();
 126
 127    //! @copydoc ::boost::intrusive::treap::begin()
 128    iterator begin();
 129
 130    //! @copydoc ::boost::intrusive::treap::begin()const
 131    const_iterator begin() const;
 132
 133    //! @copydoc ::boost::intrusive::treap::cbegin()const
 134    const_iterator cbegin() const;
 135
 136    //! @copydoc ::boost::intrusive::treap::end()
 137    iterator end();
 138
 139    //! @copydoc ::boost::intrusive::treap::end()const
 140    const_iterator end() const;
 141
 142    //! @copydoc ::boost::intrusive::treap::cend()const
 143    const_iterator cend() const;
 144
 145    //! @copydoc ::boost::intrusive::treap::rbegin()
 146    reverse_iterator rbegin();
 147
 148    //! @copydoc ::boost::intrusive::treap::rbegin()const
 149    const_reverse_iterator rbegin() const;
 150
 151    //! @copydoc ::boost::intrusive::treap::crbegin()const
 152    const_reverse_iterator crbegin() const;
 153
 154    //! @copydoc ::boost::intrusive::treap::rend()
 155    reverse_iterator rend();
 156
 157    //! @copydoc ::boost::intrusive::treap::rend()const
 158    const_reverse_iterator rend() const;
 159
 160    //! @copydoc ::boost::intrusive::treap::crend()const
 161    const_reverse_iterator crend() const;
 162
 163    //! @copydoc ::boost::intrusive::treap::root()
 164    iterator root();
 165
 166    //! @copydoc ::boost::intrusive::treap::root()const
 167    const_iterator root() const;
 168
 169    //! @copydoc ::boost::intrusive::treap::croot()const
 170    const_iterator croot() const;
 171
 172    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
 173    static treap_set_impl &container_from_end_iterator(iterator end_iterator);
 174
 175    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(const_iterator)
 176    static const treap_set_impl &container_from_end_iterator(const_iterator end_iterator);
 177
 178    //! @copydoc ::boost::intrusive::treap::container_from_iterator(iterator)
 179    static treap_set_impl &container_from_iterator(iterator it);
 180
 181    //! @copydoc ::boost::intrusive::treap::container_from_iterator(const_iterator)
 182    static const treap_set_impl &container_from_iterator(const_iterator it);
 183
 184    //! @copydoc ::boost::intrusive::treap::key_comp()const
 185    key_compare key_comp() const;
 186
 187    //! @copydoc ::boost::intrusive::treap::value_comp()const
 188    value_compare value_comp() const;
 189
 190    //! @copydoc ::boost::intrusive::treap::empty()const
 191    bool empty() const;
 192
 193    //! @copydoc ::boost::intrusive::treap::size()const
 194    size_type size() const;
 195
 196    //! @copydoc ::boost::intrusive::treap::swap
 197    void swap(treap_set_impl& other);
 198
 199    //! @copydoc ::boost::intrusive::treap::clone_from(const treap&,Cloner,Disposer)
 200    template <class Cloner, class Disposer>
 201    void clone_from(const treap_set_impl &src, Cloner cloner, Disposer disposer);
 202
 203    #else
 204
 205    using tree_type::clone_from;
 206
 207    #endif
 208
 209    //! @copydoc ::boost::intrusive::treap::clone_from(treap&&,Cloner,Disposer)
 210    template <class Cloner, class Disposer>
 211    void clone_from(BOOST_RV_REF(treap_set_impl) src, Cloner cloner, Disposer disposer)
 212    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
 213
 214    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 215
 216    //! @copydoc ::boost::intrusive::treap::top()
 217    iterator top();
 218
 219    //! @copydoc ::boost::intrusive::treap::top()const
 220    const_iterator top() const;
 221
 222    //! @copydoc ::boost::intrusive::treap::ctop()const
 223    const_iterator ctop() const;
 224
 225    //! @copydoc ::boost::intrusive::treap::rtop()
 226    reverse_iterator rtop();
 227
 228    //! @copydoc ::boost::intrusive::treap::rtop()const
 229    const_reverse_iterator rtop() const;
 230
 231    //! @copydoc ::boost::intrusive::treap::crtop()const
 232    const_reverse_iterator crtop() const;
 233
 234    //! @copydoc ::boost::intrusive::treap::crtop() const
 235    priority_compare priority_comp() const;
 236    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 237
 238    //! @copydoc ::boost::intrusive::treap::insert_unique(reference)
 239    std::pair<iterator, bool> insert(reference value)
 240    {  return tree_type::insert_unique(value);  }
 241
 242    //! @copydoc ::boost::intrusive::treap::insert_unique(const_iterator,reference)
 243    iterator insert(const_iterator hint, reference value)
 244    {  return tree_type::insert_unique(hint, value);  }
 245
 246    //! @copydoc ::boost::intrusive::treap::insert_unique_check(const key_type&,insert_commit_data&)
 247    std::pair<iterator, bool> insert_check( const key_type &key, insert_commit_data &commit_data)
 248    {  return tree_type::insert_unique_check(key, commit_data); }
 249
 250    //! @copydoc ::boost::intrusive::treap::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
 251    std::pair<iterator, bool> insert_check
 252       ( const_iterator hint, const key_type &key, insert_commit_data &commit_data)
 253    {  return tree_type::insert_unique_check(hint, key, commit_data); }
 254
 255    //! @copydoc ::boost::intrusive::treap::insert_unique_check(const KeyType&,KeyTypeKeyCompare,KeyValuePrioCompare,insert_commit_data&)
 256    template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare>
 257    std::pair<iterator, bool> insert_check
 258       ( const KeyType &key, KeyTypeKeyCompare comp, KeyValuePrioCompare key_value_pcomp
 259       , insert_commit_data &commit_data)
 260    {  return tree_type::insert_unique_check(key, comp, key_value_pcomp, commit_data); }
 261
 262    //! @copydoc ::boost::intrusive::treap::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,KeyValuePrioCompare,insert_commit_data&)
 263    template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare>
 264    std::pair<iterator, bool> insert_check
 265       ( const_iterator hint, const KeyType &key
 266       , KeyTypeKeyCompare comp, KeyValuePrioCompare key_value_pcomp
 267       , insert_commit_data &commit_data)
 268    {  return tree_type::insert_unique_check(hint, key, comp, key_value_pcomp, commit_data); }
 269
 270    //! @copydoc ::boost::intrusive::treap::insert_unique(Iterator,Iterator)
 271    template<class Iterator>
 272    void insert(Iterator b, Iterator e)
 273    {  tree_type::insert_unique(b, e);  }
 274
 275    //! @copydoc ::boost::intrusive::treap::insert_unique_commit
 276    iterator insert_commit(reference value, const insert_commit_data &commit_data)
 277    {  return tree_type::insert_unique_commit(value, commit_data);  }
 278
 279    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 280    //! @copydoc ::boost::intrusive::treap::insert_before
 281    iterator insert_before(const_iterator pos, reference value);
 282
 283    //! @copydoc ::boost::intrusive::treap::push_back
 284    void push_back(reference value);
 285
 286    //! @copydoc ::boost::intrusive::treap::push_front
 287    void push_front(reference value);
 288
 289    //! @copydoc ::boost::intrusive::treap::erase(const_iterator)
 290    iterator erase(const_iterator i);
 291
 292    //! @copydoc ::boost::intrusive::treap::erase(const_iterator,const_iterator)
 293    iterator erase(const_iterator b, const_iterator e);
 294
 295    //! @copydoc ::boost::intrusive::treap::erase(const key_type &)
 296    size_type erase(const key_type &key);
 297
 298    //! @copydoc ::boost::intrusive::treap::erase(const KeyType&,KeyTypeKeyCompare)
 299    template<class KeyType, class KeyTypeKeyCompare>
 300    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
 301
 302    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,Disposer)
 303    template<class Disposer>
 304    iterator erase_and_dispose(const_iterator i, Disposer disposer);
 305
 306    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,const_iterator,Disposer)
 307    template<class Disposer>
 308    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
 309
 310    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const key_type &, Disposer)
 311    template<class Disposer>
 312    size_type erase_and_dispose(const key_type &key, Disposer disposer);
 313
 314    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 315    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 316    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
 317
 318    //! @copydoc ::boost::intrusive::treap::clear
 319    void clear();
 320
 321    //! @copydoc ::boost::intrusive::treap::clear_and_dispose
 322    template<class Disposer>
 323    void clear_and_dispose(Disposer disposer);
 324
 325    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 326
 327    //! @copydoc ::boost::intrusive::treap::count(const key_type &)const
 328    size_type count(const key_type &key) const
 329    {  return static_cast<size_type>(this->tree_type::find(key) != this->tree_type::cend()); }
 330
 331    //! @copydoc ::boost::intrusive::treap::count(const KeyType&,KeyTypeKeyCompare)const
 332    template<class KeyType, class KeyTypeKeyCompare>
 333    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const
 334    {  return static_cast<size_type>(this->tree_type::find(key, comp) != this->tree_type::cend()); }
 335
 336    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 337
 338    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)
 339    iterator lower_bound(const key_type &key);
 340
 341    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)
 342    template<class KeyType, class KeyTypeKeyCompare>
 343    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 344
 345    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)const
 346    const_iterator lower_bound(const key_type &key) const;
 347
 348    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 349    template<class KeyType, class KeyTypeKeyCompare>
 350    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 351
 352    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)
 353    iterator upper_bound(const key_type &key);
 354
 355    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)
 356    template<class KeyType, class KeyTypeKeyCompare>
 357    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 358
 359    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)const
 360    const_iterator upper_bound(const key_type &key) const;
 361
 362    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 363    template<class KeyType, class KeyTypeKeyCompare>
 364    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 365
 366    //! @copydoc ::boost::intrusive::treap::find(const key_type &)
 367    iterator find(const key_type &key);
 368
 369    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)
 370    template<class KeyType, class KeyTypeKeyCompare>
 371    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 372
 373    //! @copydoc ::boost::intrusive::treap::find(const key_type &)const
 374    const_iterator find(const key_type &key) const;
 375
 376    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)const
 377    template<class KeyType, class KeyTypeKeyCompare>
 378    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 379
 380    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 381
 382    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)
 383    std::pair<iterator,iterator> equal_range(const key_type &key)
 384    {  return this->tree_type::lower_bound_range(key); }
 385
 386    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)
 387    template<class KeyType, class KeyTypeKeyCompare>
 388    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp)
 389    {  return this->tree_type::equal_range(key, comp); }
 390
 391    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)const
 392    std::pair<const_iterator, const_iterator>
 393       equal_range(const key_type &key) const
 394    {  return this->tree_type::lower_bound_range(key); }
 395
 396    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)const
 397    template<class KeyType, class KeyTypeKeyCompare>
 398    std::pair<const_iterator, const_iterator>
 399       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const
 400    {  return this->tree_type::equal_range(key, comp); }
 401
 402    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 403
 404    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)
 405    std::pair<iterator,iterator> bounded_range
 406       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
 407
 408    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 409    template<class KeyType, class KeyTypeKeyCompare>
 410    std::pair<iterator,iterator> bounded_range
 411       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 412
 413    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)const
 414    std::pair<const_iterator, const_iterator>
 415       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
 416
 417    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 418    template<class KeyType, class KeyTypeKeyCompare>
 419    std::pair<const_iterator, const_iterator> bounded_range
 420          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 421
 422    //! @copydoc ::boost::intrusive::treap::s_iterator_to(reference)
 423    static iterator s_iterator_to(reference value);
 424
 425    //! @copydoc ::boost::intrusive::treap::s_iterator_to(const_reference)
 426    static const_iterator s_iterator_to(const_reference value);
 427
 428    //! @copydoc ::boost::intrusive::treap::iterator_to(reference)
 429    iterator iterator_to(reference value);
 430
 431    //! @copydoc ::boost::intrusive::treap::iterator_to(const_reference)const
 432    const_iterator iterator_to(const_reference value) const;
 433
 434    //! @copydoc ::boost::intrusive::treap::init_node(reference)
 435    static void init_node(reference value);
 436
 437    //! @copydoc ::boost::intrusive::treap::unlink_leftmost_without_rebalance
 438    pointer unlink_leftmost_without_rebalance();
 439
 440    //! @copydoc ::boost::intrusive::treap::replace_node
 441    void replace_node(iterator replace_this, reference with_this);
 442
 443    //! @copydoc ::boost::intrusive::treap::remove_node
 444    void remove_node(reference value);
 445
 446
 447    //! @copydoc ::boost::intrusive::treap::merge_unique
 448    template<class ...Options2>
 449    void merge(treap_set<T, Options2...> &source);
 450
 451    //! @copydoc ::boost::intrusive::treap::merge_unique
 452    template<class ...Options2>
 453    void merge(treap_multiset<T, Options2...> &source);
 454
 455    #else
 456
 457    template<class Compare2>
 458    void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
 459    {  return tree_type::merge_unique(source);  }
 460
 461    template<class Compare2>
 462    void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
 463    {  return tree_type::merge_unique(source);  }
 464
 465    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 466 };
 467
 468
 469 //! Helper metafunction to define a \c treap_set that yields to the same type when the
 470 //! same options (either explicitly or implicitly) are used.
 471 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 472 template<class T, class ...Options>
 473 #else
 474 template<class T, class O1 = void, class O2 = void
 475                 , class O3 = void, class O4 = void
 476                 , class O5 = void, class O6 = void>
 477 #endif
 478 struct make_treap_set
 479 {
 480    typedef typename pack_options
 481       < treap_defaults,
 482       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 483       O1, O2, O3, O4, O5, O6
 484       #else
 485       Options...
 486       #endif
 487       >::type packed_options;
 488
 489    typedef typename detail::get_value_traits
 490       <T, typename packed_options::proto_value_traits>::type value_traits;
 491
 492    typedef treap_set_impl
 493          < value_traits
 494          , typename packed_options::key_of_value
 495          , typename packed_options::compare
 496          , typename packed_options::priority
 497          , typename packed_options::size_type
 498          , packed_options::constant_time_size
 499          , typename packed_options::header_holder_type
 500          > implementation_defined;
 501    /// @endcond
 502    typedef implementation_defined type;
 503 };
 504
 505 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 506
 507 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 508 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
 509 #else
 510 template<class T, class ...Options>
 511 #endif
 512 class treap_set
 513    :  public make_treap_set<T,
 514       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 515       O1, O2, O3, O4, O5, O6
 516       #else
 517       Options...
 518       #endif
 519       >::type
 520 {
 521    typedef typename make_treap_set
 522       <T,
 523       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 524       O1, O2, O3, O4, O5, O6
 525       #else
 526       Options...
 527       #endif
 528       >::type   Base;
 529    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_set)
 530
 531    public:
 532    typedef typename Base::key_compare        key_compare;
 533    typedef typename Base::priority_compare   priority_compare;
 534    typedef typename Base::value_traits       value_traits;
 535    typedef typename Base::iterator           iterator;
 536    typedef typename Base::const_iterator     const_iterator;
 537
 538    //Assert if passed value traits are compatible with the type
 539    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 540
 541    treap_set()
 542       :  Base()
 543    {}
 544
 545    explicit treap_set( const key_compare &cmp
 546                      , const priority_compare &pcmp = priority_compare()
 547                      , const value_traits &v_traits = value_traits())
 548       :  Base(cmp, pcmp, v_traits)
 549    {}
 550
 551    template<class Iterator>
 552    treap_set( Iterator b, Iterator e
 553       , const key_compare &cmp = key_compare()
 554       , const priority_compare &pcmp = priority_compare()
 555       , const value_traits &v_traits = value_traits())
 556       :  Base(b, e, cmp, pcmp, v_traits)
 557    {}
 558
 559    treap_set(BOOST_RV_REF(treap_set) x)
 560       :  Base(BOOST_MOVE_BASE(Base, x))
 561    {}
 562
 563    treap_set& operator=(BOOST_RV_REF(treap_set) x)
 564    {  return static_cast<treap_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
 565
 566    template <class Cloner, class Disposer>
 567    void clone_from(const treap_set &src, Cloner cloner, Disposer disposer)
 568    {  Base::clone_from(src, cloner, disposer);  }
 569
 570    template <class Cloner, class Disposer>
 571    void clone_from(BOOST_RV_REF(treap_set) src, Cloner cloner, Disposer disposer)
 572    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
 573
 574    static treap_set &container_from_end_iterator(iterator end_iterator)
 575    {  return static_cast<treap_set &>(Base::container_from_end_iterator(end_iterator));   }
 576
 577    static const treap_set &container_from_end_iterator(const_iterator end_iterator)
 578    {  return static_cast<const treap_set &>(Base::container_from_end_iterator(end_iterator));   }
 579
 580    static treap_set &container_from_iterator(iterator it)
 581    {  return static_cast<treap_set &>(Base::container_from_iterator(it));   }
 582
 583    static const treap_set &container_from_iterator(const_iterator it)
 584    {  return static_cast<const treap_set &>(Base::container_from_iterator(it));   }
 585 };
 586
 587 #endif
 588
 589 //! The class template treap_multiset is an intrusive container, that mimics most of
 590 //! the interface of std::treap_multiset as described in the C++ standard.
 591 //!
 592 //! The template parameter \c T is the type to be managed by the container.
 593 //! The user can specify additional options and if no options are provided
 594 //! default options are used.
 595 //!
 596 //! The container supports the following options:
 597 //! \c base_hook<>/member_hook<>/value_traits<>,
 598 //! \c constant_time_size<>, \c size_type<>,
 599 //! \c compare<> and \c priority_compare<>
 600 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 601 template<class T, class ...Options>
 602 #else
 603 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
 604 #endif
 605 class treap_multiset_impl
 606 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 607    : public treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder>
 608 #endif
 609 {
 610    /// @cond
 611    typedef treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
 612    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset_impl)
 613
 614    typedef tree_type implementation_defined;
 615    /// @endcond
 616
 617    public:
 618    typedef typename implementation_defined::value_type               value_type;
 619    typedef typename implementation_defined::value_traits             value_traits;
 620    typedef typename implementation_defined::key_type                 key_type;
 621    typedef typename implementation_defined::key_of_value             key_of_value;
 622    typedef typename implementation_defined::pointer                  pointer;
 623    typedef typename implementation_defined::const_pointer            const_pointer;
 624    typedef typename implementation_defined::reference                reference;
 625    typedef typename implementation_defined::const_reference          const_reference;
 626    typedef typename implementation_defined::difference_type          difference_type;
 627    typedef typename implementation_defined::size_type                size_type;
 628    typedef typename implementation_defined::value_compare            value_compare;
 629    typedef typename implementation_defined::key_compare              key_compare;
 630    typedef typename implementation_defined::priority_compare         priority_compare;
 631    typedef typename implementation_defined::iterator                 iterator;
 632    typedef typename implementation_defined::const_iterator           const_iterator;
 633    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
 634    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
 635    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
 636    typedef typename implementation_defined::node_traits              node_traits;
 637    typedef typename implementation_defined::node                     node;
 638    typedef typename implementation_defined::node_ptr                 node_ptr;
 639    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
 640    typedef typename implementation_defined::node_algorithms          node_algorithms;
 641
 642    static const bool constant_time_size = implementation_defined::constant_time_size;
 643
 644    public:
 645
 646    //! @copydoc ::boost::intrusive::treap::treap()
 647    treap_multiset_impl()
 648       :  tree_type()
 649    {}
 650
 651    //! @copydoc ::boost::intrusive::treap::treap(const key_compare &,const priority_compare &,const value_traits &)
 652    explicit treap_multiset_impl( const key_compare &cmp
 653                           , const priority_compare &pcmp  = priority_compare()
 654                           , const value_traits &v_traits  = value_traits())
 655       :  tree_type(cmp, pcmp, v_traits)
 656    {}
 657
 658    //! @copydoc ::boost::intrusive::treap::treap(bool,Iterator,Iterator,const key_compare &,const priority_compare &,const value_traits &)
 659    template<class Iterator>
 660    treap_multiset_impl( Iterator b, Iterator e
 661            , const key_compare &cmp = key_compare()
 662            , const priority_compare &pcmp  = priority_compare()
 663            , const value_traits &v_traits = value_traits())
 664       : tree_type(false, b, e, cmp, pcmp, v_traits)
 665    {}
 666
 667    //! <b>Effects</b>: to-do
 668    //!
 669    treap_multiset_impl(BOOST_RV_REF(treap_multiset_impl) x)
 670       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
 671    {}
 672
 673    //! <b>Effects</b>: to-do
 674    //!
 675    treap_multiset_impl& operator=(BOOST_RV_REF(treap_multiset_impl) x)
 676    {  return static_cast<treap_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));  }
 677
 678    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 679    //! @copydoc ::boost::intrusive::treap::~treap()
 680    ~treap_multiset_impl();
 681
 682    //! @copydoc ::boost::intrusive::treap::begin()
 683    iterator begin();
 684
 685    //! @copydoc ::boost::intrusive::treap::begin()const
 686    const_iterator begin() const;
 687
 688    //! @copydoc ::boost::intrusive::treap::cbegin()const
 689    const_iterator cbegin() const;
 690
 691    //! @copydoc ::boost::intrusive::treap::end()
 692    iterator end();
 693
 694    //! @copydoc ::boost::intrusive::treap::end()const
 695    const_iterator end() const;
 696
 697    //! @copydoc ::boost::intrusive::treap::cend()const
 698    const_iterator cend() const;
 699
 700    //! @copydoc ::boost::intrusive::treap::rbegin()
 701    reverse_iterator rbegin();
 702
 703    //! @copydoc ::boost::intrusive::treap::rbegin()const
 704    const_reverse_iterator rbegin() const;
 705
 706    //! @copydoc ::boost::intrusive::treap::crbegin()const
 707    const_reverse_iterator crbegin() const;
 708
 709    //! @copydoc ::boost::intrusive::treap::rend()
 710    reverse_iterator rend();
 711
 712    //! @copydoc ::boost::intrusive::treap::rend()const
 713    const_reverse_iterator rend() const;
 714
 715    //! @copydoc ::boost::intrusive::treap::crend()const
 716    const_reverse_iterator crend() const;
 717
 718    //! @copydoc ::boost::intrusive::treap::root()
 719    iterator root();
 720
 721    //! @copydoc ::boost::intrusive::treap::root()const
 722    const_iterator root() const;
 723
 724    //! @copydoc ::boost::intrusive::treap::croot()const
 725    const_iterator croot() const;
 726
 727    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
 728    static treap_multiset_impl &container_from_end_iterator(iterator end_iterator);
 729
 730    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(const_iterator)
 731    static const treap_multiset_impl &container_from_end_iterator(const_iterator end_iterator);
 732
 733    //! @copydoc ::boost::intrusive::treap::container_from_iterator(iterator)
 734    static treap_multiset_impl &container_from_iterator(iterator it);
 735
 736    //! @copydoc ::boost::intrusive::treap::container_from_iterator(const_iterator)
 737    static const treap_multiset_impl &container_from_iterator(const_iterator it);
 738
 739    //! @copydoc ::boost::intrusive::treap::key_comp()const
 740    key_compare key_comp() const;
 741
 742    //! @copydoc ::boost::intrusive::treap::value_comp()const
 743    value_compare value_comp() const;
 744
 745    //! @copydoc ::boost::intrusive::treap::empty()const
 746    bool empty() const;
 747
 748    //! @copydoc ::boost::intrusive::treap::size()const
 749    size_type size() const;
 750
 751    //! @copydoc ::boost::intrusive::treap::swap
 752    void swap(treap_multiset_impl& other);
 753
 754    //! @copydoc ::boost::intrusive::treap::clone_from(const treap&,Cloner,Disposer)
 755    template <class Cloner, class Disposer>
 756    void clone_from(const treap_multiset_impl &src, Cloner cloner, Disposer disposer);
 757
 758    #else
 759
 760    using tree_type::clone_from;
 761
 762    #endif
 763
 764    //! @copydoc ::boost::intrusive::treap::clone_from(treap&&,Cloner,Disposer)
 765    template <class Cloner, class Disposer>
 766    void clone_from(BOOST_RV_REF(treap_multiset_impl) src, Cloner cloner, Disposer disposer)
 767    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
 768
 769    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 770
 771    //! @copydoc ::boost::intrusive::treap::top()
 772    iterator top();
 773
 774    //! @copydoc ::boost::intrusive::treap::top()const
 775    const_iterator top() const;
 776
 777    //! @copydoc ::boost::intrusive::treap::ctop()const
 778    const_iterator ctop() const;
 779
 780    //! @copydoc ::boost::intrusive::treap::rtop()
 781    reverse_iterator rtop();
 782
 783    //! @copydoc ::boost::intrusive::treap::rtop()const
 784    const_reverse_iterator rtop() const;
 785
 786    //! @copydoc ::boost::intrusive::treap::crtop()const
 787    const_reverse_iterator crtop() const;
 788
 789    //! @copydoc ::boost::intrusive::treap::crtop() const
 790    priority_compare priority_comp() const;
 791    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 792
 793    //! @copydoc ::boost::intrusive::treap::insert_equal(reference)
 794    iterator insert(reference value)
 795    {  return tree_type::insert_equal(value);  }
 796
 797    //! @copydoc ::boost::intrusive::treap::insert_equal(const_iterator,reference)
 798    iterator insert(const_iterator hint, reference value)
 799    {  return tree_type::insert_equal(hint, value);  }
 800
 801    //! @copydoc ::boost::intrusive::treap::insert_equal(Iterator,Iterator)
 802    template<class Iterator>
 803    void insert(Iterator b, Iterator e)
 804    {  tree_type::insert_equal(b, e);  }
 805
 806    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 807    //! @copydoc ::boost::intrusive::treap::insert_before
 808    iterator insert_before(const_iterator pos, reference value);
 809
 810    //! @copydoc ::boost::intrusive::treap::push_back
 811    void push_back(reference value);
 812
 813    //! @copydoc ::boost::intrusive::treap::push_front
 814    void push_front(reference value);
 815
 816    //! @copydoc ::boost::intrusive::treap::erase(const_iterator)
 817    iterator erase(const_iterator i);
 818
 819    //! @copydoc ::boost::intrusive::treap::erase(const_iterator,const_iterator)
 820    iterator erase(const_iterator b, const_iterator e);
 821
 822    //! @copydoc ::boost::intrusive::treap::erase(const key_type &)
 823    size_type erase(const key_type &key);
 824
 825    //! @copydoc ::boost::intrusive::treap::erase(const KeyType&,KeyTypeKeyCompare)
 826    template<class KeyType, class KeyTypeKeyCompare>
 827    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
 828
 829    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,Disposer)
 830    template<class Disposer>
 831    iterator erase_and_dispose(const_iterator i, Disposer disposer);
 832
 833    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,const_iterator,Disposer)
 834    template<class Disposer>
 835    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
 836
 837    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const key_type &, Disposer)
 838    template<class Disposer>
 839    size_type erase_and_dispose(const key_type &key, Disposer disposer);
 840
 841    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 842    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 843    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
 844
 845    //! @copydoc ::boost::intrusive::treap::clear
 846    void clear();
 847
 848    //! @copydoc ::boost::intrusive::treap::clear_and_dispose
 849    template<class Disposer>
 850    void clear_and_dispose(Disposer disposer);
 851
 852    //! @copydoc ::boost::intrusive::treap::count(const key_type &)const
 853    size_type count(const key_type &key) const;
 854
 855    //! @copydoc ::boost::intrusive::treap::count(const KeyType&,KeyTypeKeyCompare)const
 856    template<class KeyType, class KeyTypeKeyCompare>
 857    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
 858
 859    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)
 860    iterator lower_bound(const key_type &key);
 861
 862    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)
 863    template<class KeyType, class KeyTypeKeyCompare>
 864    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 865
 866    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)const
 867    const_iterator lower_bound(const key_type &key) const;
 868
 869    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 870    template<class KeyType, class KeyTypeKeyCompare>
 871    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 872
 873    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)
 874    iterator upper_bound(const key_type &key);
 875
 876    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)
 877    template<class KeyType, class KeyTypeKeyCompare>
 878    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 879
 880    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)const
 881    const_iterator upper_bound(const key_type &key) const;
 882
 883    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 884    template<class KeyType, class KeyTypeKeyCompare>
 885    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 886
 887    //! @copydoc ::boost::intrusive::treap::find(const key_type &)
 888    iterator find(const key_type &key);
 889
 890    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)
 891    template<class KeyType, class KeyTypeKeyCompare>
 892    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 893
 894    //! @copydoc ::boost::intrusive::treap::find(const key_type &)const
 895    const_iterator find(const key_type &key) const;
 896
 897    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)const
 898    template<class KeyType, class KeyTypeKeyCompare>
 899    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 900
 901    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)
 902    std::pair<iterator,iterator> equal_range(const key_type &key);
 903
 904    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)
 905    template<class KeyType, class KeyTypeKeyCompare>
 906    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
 907
 908    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)const
 909    std::pair<const_iterator, const_iterator>
 910       equal_range(const key_type &key) const;
 911
 912    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)const
 913    template<class KeyType, class KeyTypeKeyCompare>
 914    std::pair<const_iterator, const_iterator>
 915       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
 916
 917    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)
 918    std::pair<iterator,iterator> bounded_range
 919       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
 920
 921    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 922    template<class KeyType, class KeyTypeKeyCompare>
 923    std::pair<iterator,iterator> bounded_range
 924       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 925
 926    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)const
 927    std::pair<const_iterator, const_iterator>
 928       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
 929
 930    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 931    template<class KeyType, class KeyTypeKeyCompare>
 932    std::pair<const_iterator, const_iterator> bounded_range
 933          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 934
 935    //! @copydoc ::boost::intrusive::treap::s_iterator_to(reference)
 936    static iterator s_iterator_to(reference value);
 937
 938    //! @copydoc ::boost::intrusive::treap::s_iterator_to(const_reference)
 939    static const_iterator s_iterator_to(const_reference value);
 940
 941    //! @copydoc ::boost::intrusive::treap::iterator_to(reference)
 942    iterator iterator_to(reference value);
 943
 944    //! @copydoc ::boost::intrusive::treap::iterator_to(const_reference)const
 945    const_iterator iterator_to(const_reference value) const;
 946
 947    //! @copydoc ::boost::intrusive::treap::init_node(reference)
 948    static void init_node(reference value);
 949
 950    //! @copydoc ::boost::intrusive::treap::unlink_leftmost_without_rebalance
 951    pointer unlink_leftmost_without_rebalance();
 952
 953    //! @copydoc ::boost::intrusive::treap::replace_node
 954    void replace_node(iterator replace_this, reference with_this);
 955
 956    //! @copydoc ::boost::intrusive::treap::remove_node
 957    void remove_node(reference value);
 958
 959    //! @copydoc ::boost::intrusive::treap::merge_unique
 960    template<class ...Options2>
 961    void merge(treap_multiset<T, Options2...> &source);
 962
 963    //! @copydoc ::boost::intrusive::treap::merge_unique
 964    template<class ...Options2>
 965    void merge(treap_set<T, Options2...> &source);
 966
 967    #else
 968
 969    template<class Compare2>
 970    void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
 971    {  return tree_type::merge_equal(source);  }
 972
 973    template<class Compare2>
 974    void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
 975    {  return tree_type::merge_equal(source);  }
 976
 977    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 978 };
 979
 980
 981 //! Helper metafunction to define a \c treap_multiset that yields to the same type when the
 982 //! same options (either explicitly or implicitly) are used.
 983 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 984 template<class T, class ...Options>
 985 #else
 986 template<class T, class O1 = void, class O2 = void
 987                 , class O3 = void, class O4 = void
 988                 , class O5 = void, class O6 = void>
 989 #endif
 990 struct make_treap_multiset
 991 {
 992    typedef typename pack_options
 993       < treap_defaults,
 994       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 995       O1, O2, O3, O4, O5, O6
 996       #else
 997       Options...
 998       #endif
 999       >::type packed_options;
1000
1001    typedef typename detail::get_value_traits
1002       <T, typename packed_options::proto_value_traits>::type value_traits;
1003
1004    typedef treap_multiset_impl
1005          < value_traits
1006          , typename packed_options::key_of_value
1007          , typename packed_options::compare
1008          , typename packed_options::priority
1009          , typename packed_options::size_type
1010          , packed_options::constant_time_size
1011          , typename packed_options::header_holder_type
1012          > implementation_defined;
1013    /// @endcond
1014    typedef implementation_defined type;
1015 };
1016
1017 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1018
1019 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1020 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
1021 #else
1022 template<class T, class ...Options>
1023 #endif
1024 class treap_multiset
1025    :  public make_treap_multiset<T,
1026       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1027       O1, O2, O3, O4, O5, O6
1028       #else
1029       Options...
1030       #endif
1031       >::type
1032 {
1033    typedef typename make_treap_multiset
1034       <T,
1035       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1036       O1, O2, O3, O4, O5, O6
1037       #else
1038       Options...
1039       #endif
1040       >::type   Base;
1041    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset)
1042
1043    public:
1044    typedef typename Base::key_compare        key_compare;
1045    typedef typename Base::priority_compare   priority_compare;
1046    typedef typename Base::value_traits       value_traits;
1047    typedef typename Base::iterator           iterator;
1048    typedef typename Base::const_iterator     const_iterator;
1049
1050    //Assert if passed value traits are compatible with the type
1051    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1052
1053    treap_multiset()
1054       :  Base()
1055    {}
1056
1057    explicit treap_multiset( const key_compare &cmp
1058                           , const priority_compare &pcmp = priority_compare()
1059                           , const value_traits &v_traits = value_traits())
1060       :  Base(cmp, pcmp, v_traits)
1061    {}
1062
1063    template<class Iterator>
1064    treap_multiset( Iterator b, Iterator e
1065       , const key_compare &cmp = key_compare()
1066       , const priority_compare &pcmp = priority_compare()
1067       , const value_traits &v_traits = value_traits())
1068       :  Base(b, e, cmp, pcmp, v_traits)
1069    {}
1070
1071    treap_multiset(BOOST_RV_REF(treap_multiset) x)
1072       :  Base(BOOST_MOVE_BASE(Base, x))
1073    {}
1074
1075    treap_multiset& operator=(BOOST_RV_REF(treap_multiset) x)
1076    {  return static_cast<treap_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
1077
1078    template <class Cloner, class Disposer>
1079    void clone_from(const treap_multiset &src, Cloner cloner, Disposer disposer)
1080    {  Base::clone_from(src, cloner, disposer);  }
1081
1082    template <class Cloner, class Disposer>
1083    void clone_from(BOOST_RV_REF(treap_multiset) src, Cloner cloner, Disposer disposer)
1084    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
1085
1086    static treap_multiset &container_from_end_iterator(iterator end_iterator)
1087    {  return static_cast<treap_multiset &>(Base::container_from_end_iterator(end_iterator));   }
1088
1089    static const treap_multiset &container_from_end_iterator(const_iterator end_iterator)
1090    {  return static_cast<const treap_multiset &>(Base::container_from_end_iterator(end_iterator));   }
1091
1092    static treap_multiset &container_from_iterator(iterator it)
1093    {  return static_cast<treap_multiset &>(Base::container_from_iterator(it));   }
1094
1095    static const treap_multiset &container_from_iterator(const_iterator it)
1096    {  return static_cast<const treap_multiset &>(Base::container_from_iterator(it));   }
1097 };
1098
1099 #endif
1100
1101 } //namespace intrusive
1102 } //namespace boost
1103
1104 #include <boost/intrusive/detail/config_end.hpp>
1105
1106 #endif //BOOST_INTRUSIVE_TREAP_SET_HPP