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

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2007-2013
   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_AVLTREE_HPP
  13 #define BOOST_INTRUSIVE_AVLTREE_HPP
  14
  15 #include <boost/intrusive/detail/config_begin.hpp>
  16 #include <boost/intrusive/intrusive_fwd.hpp>
  17 #include <cstddef>
  18 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>
  19 #include <boost/intrusive/detail/minimal_pair_header.hpp>
  20
  21 #include <boost/static_assert.hpp>
  22 #include <boost/intrusive/avl_set_hook.hpp>
  23 #include <boost/intrusive/detail/avltree_node.hpp>
  24 #include <boost/intrusive/bstree.hpp>
  25 #include <boost/intrusive/detail/tree_node.hpp>
  26 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
  27 #include <boost/intrusive/detail/mpl.hpp>
  28 #include <boost/intrusive/pointer_traits.hpp>
  29 #include <boost/intrusive/detail/get_value_traits.hpp>
  30 #include <boost/intrusive/avltree_algorithms.hpp>
  31 #include <boost/intrusive/link_mode.hpp>
  32 #include <boost/move/utility_core.hpp>
  33
  34 #if defined(BOOST_HAS_PRAGMA_ONCE)
  35 #  pragma once
  36 #endif
  37
  38 namespace boost {
  39 namespace intrusive {
  40
  41 /// @cond
  42
  43 struct default_avltree_hook_applier
  44 {  template <class T> struct apply{ typedef typename T::default_avltree_hook type;  };  };
  45
  46 template<>
  47 struct is_default_hook_tag<default_avltree_hook_applier>
  48 {  static const bool value = true;  };
  49
  50 struct avltree_defaults
  51    : bstree_defaults
  52 {
  53    typedef default_avltree_hook_applier proto_value_traits;
  54 };
  55
  56 /// @endcond
  57
  58 //! The class template avltree is an intrusive AVL tree container, that
  59 //! is used to construct intrusive avl_set and avl_multiset containers.
  60 //! The no-throw guarantee holds only, if the key_compare object
  61 //! doesn't throw.
  62 //!
  63 //! The template parameter \c T is the type to be managed by the container.
  64 //! The user can specify additional options and if no options are provided
  65 //! default options are used.
  66 //!
  67 //! The container supports the following options:
  68 //! \c base_hook<>/member_hook<>/value_traits<>,
  69 //! \c constant_time_size<>, \c size_type<> and
  70 //! \c compare<>.
  71 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  72 template<class T, class ...Options>
  73 #else
  74 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
  75 #endif
  76 class avltree_impl
  77    /// @cond
  78    :  public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder>
  79    /// @endcond
  80 {
  81    public:
  82    typedef ValueTraits value_traits;
  83    /// @cond
  84    typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
  85                       , ConstantTimeSize, AvlTreeAlgorithms
  86                       , HeaderHolder>                                tree_type;
  87    typedef tree_type                                                 implementation_defined;
  88    /// @endcond
  89
  90    typedef typename implementation_defined::pointer                  pointer;
  91    typedef typename implementation_defined::const_pointer            const_pointer;
  92    typedef typename implementation_defined::value_type               value_type;
  93    typedef typename implementation_defined::key_type                 key_type;
  94    typedef typename implementation_defined::key_of_value             key_of_value;
  95    typedef typename implementation_defined::reference                reference;
  96    typedef typename implementation_defined::const_reference          const_reference;
  97    typedef typename implementation_defined::difference_type          difference_type;
  98    typedef typename implementation_defined::size_type                size_type;
  99    typedef typename implementation_defined::value_compare            value_compare;
 100    typedef typename implementation_defined::key_compare              key_compare;
 101    typedef typename implementation_defined::iterator                 iterator;
 102    typedef typename implementation_defined::const_iterator           const_iterator;
 103    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
 104    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
 105    typedef typename implementation_defined::node_traits              node_traits;
 106    typedef typename implementation_defined::node                     node;
 107    typedef typename implementation_defined::node_ptr                 node_ptr;
 108    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
 109    typedef typename implementation_defined::node_algorithms          node_algorithms;
 110
 111    static const bool constant_time_size = implementation_defined::constant_time_size;
 112    /// @cond
 113    private:
 114
 115    //noncopyable
 116    BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree_impl)
 117
 118    /// @endcond
 119
 120    public:
 121
 122    typedef typename implementation_defined::insert_commit_data insert_commit_data;
 123
 124    //! @copydoc ::boost::intrusive::bstree::bstree()
 125    avltree_impl()
 126       :  tree_type()
 127    {}
 128
 129    //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &)
 130    explicit avltree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
 131       :  tree_type(cmp, v_traits)
 132    {}
 133
 134    //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
 135    template<class Iterator>
 136    avltree_impl( bool unique, Iterator b, Iterator e
 137               , const key_compare &cmp     = key_compare()
 138               , const value_traits &v_traits = value_traits())
 139       : tree_type(unique, b, e, cmp, v_traits)
 140    {}
 141
 142    //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
 143    avltree_impl(BOOST_RV_REF(avltree_impl) x)
 144       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
 145    {}
 146
 147    //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
 148    avltree_impl& operator=(BOOST_RV_REF(avltree_impl) x)
 149    {  return static_cast<avltree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
 150
 151    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 152
 153    //! @copydoc ::boost::intrusive::bstree::~bstree()
 154    ~avltree_impl();
 155
 156    //! @copydoc ::boost::intrusive::bstree::begin()
 157    iterator begin();
 158
 159    //! @copydoc ::boost::intrusive::bstree::begin()const
 160    const_iterator begin() const;
 161
 162    //! @copydoc ::boost::intrusive::bstree::cbegin()const
 163    const_iterator cbegin() const;
 164
 165    //! @copydoc ::boost::intrusive::bstree::end()
 166    iterator end();
 167
 168    //! @copydoc ::boost::intrusive::bstree::end()const
 169    const_iterator end() const;
 170
 171    //! @copydoc ::boost::intrusive::bstree::cend()const
 172    const_iterator cend() const;
 173
 174    //! @copydoc ::boost::intrusive::bstree::rbegin()
 175    reverse_iterator rbegin();
 176
 177    //! @copydoc ::boost::intrusive::bstree::rbegin()const
 178    const_reverse_iterator rbegin() const;
 179
 180    //! @copydoc ::boost::intrusive::bstree::crbegin()const
 181    const_reverse_iterator crbegin() const;
 182
 183    //! @copydoc ::boost::intrusive::bstree::rend()
 184    reverse_iterator rend();
 185
 186    //! @copydoc ::boost::intrusive::bstree::rend()const
 187    const_reverse_iterator rend() const;
 188
 189    //! @copydoc ::boost::intrusive::bstree::crend()const
 190    const_reverse_iterator crend() const;
 191
 192    //! @copydoc ::boost::intrusive::bstree::root()
 193    iterator root();
 194
 195    //! @copydoc ::boost::intrusive::bstree::root()const
 196    const_iterator root() const;
 197
 198    //! @copydoc ::boost::intrusive::bstree::croot()const
 199    const_iterator croot() const;
 200
 201    //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
 202    static avltree_impl &container_from_end_iterator(iterator end_iterator);
 203
 204    //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
 205    static const avltree_impl &container_from_end_iterator(const_iterator end_iterator);
 206
 207    //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
 208    static avltree_impl &container_from_iterator(iterator it);
 209
 210    //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
 211    static const avltree_impl &container_from_iterator(const_iterator it);
 212
 213    //! @copydoc ::boost::intrusive::bstree::key_comp()const
 214    key_compare key_comp() const;
 215
 216    //! @copydoc ::boost::intrusive::bstree::value_comp()const
 217    value_compare value_comp() const;
 218
 219    //! @copydoc ::boost::intrusive::bstree::empty()const
 220    bool empty() const;
 221
 222    //! @copydoc ::boost::intrusive::bstree::size()const
 223    size_type size() const;
 224
 225    //! @copydoc ::boost::intrusive::bstree::swap
 226    void swap(avltree_impl& other);
 227
 228    //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer)
 229    template <class Cloner, class Disposer>
 230    void clone_from(const avltree_impl &src, Cloner cloner, Disposer disposer);
 231
 232    #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED
 233
 234    using tree_type::clone_from;
 235
 236    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 237
 238    //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer)
 239    template <class Cloner, class Disposer>
 240    void clone_from(BOOST_RV_REF(avltree_impl) src, Cloner cloner, Disposer disposer)
 241    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
 242
 243    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 244
 245    //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
 246    iterator insert_equal(reference value);
 247
 248    //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
 249    iterator insert_equal(const_iterator hint, reference value);
 250
 251    //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
 252    template<class Iterator>
 253    void insert_equal(Iterator b, Iterator e);
 254
 255    //! @copydoc ::boost::intrusive::bstree::insert_unique(reference)
 256    std::pair<iterator, bool> insert_unique(reference value);
 257
 258    //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference)
 259    iterator insert_unique(const_iterator hint, reference value);
 260
 261    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 262    template<class KeyType, class KeyTypeKeyCompare>
 263    std::pair<iterator, bool> insert_unique_check
 264       (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data);
 265
 266    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 267    template<class KeyType, class KeyTypeKeyCompare>
 268    std::pair<iterator, bool> insert_unique_check
 269       (const_iterator hint, const KeyType &key
 270       ,KeyTypeKeyCompare comp, insert_commit_data &commit_data);
 271
 272    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&)
 273    std::pair<iterator, bool> insert_unique_check
 274       (const key_type &key, insert_commit_data &commit_data);
 275
 276    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
 277    std::pair<iterator, bool> insert_unique_check
 278       (const_iterator hint, const key_type &key, insert_commit_data &commit_data);
 279
 280    //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
 281    iterator insert_unique_commit(reference value, const insert_commit_data &commit_data);
 282
 283    //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
 284    template<class Iterator>
 285    void insert_unique(Iterator b, Iterator e);
 286
 287    //! @copydoc ::boost::intrusive::bstree::insert_before
 288    iterator insert_before(const_iterator pos, reference value);
 289
 290    //! @copydoc ::boost::intrusive::bstree::push_back
 291    void push_back(reference value);
 292
 293    //! @copydoc ::boost::intrusive::bstree::push_front
 294    void push_front(reference value);
 295
 296    //! @copydoc ::boost::intrusive::bstree::erase(const_iterator)
 297    iterator erase(const_iterator i);
 298
 299    //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator)
 300    iterator erase(const_iterator b, const_iterator e);
 301
 302    //! @copydoc ::boost::intrusive::bstree::erase(const key_type &)
 303    size_type erase(const key_type &key);
 304
 305    //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare)
 306    template<class KeyType, class KeyTypeKeyCompare>
 307    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
 308
 309    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer)
 310    template<class Disposer>
 311    iterator erase_and_dispose(const_iterator i, Disposer disposer);
 312
 313    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer)
 314    template<class Disposer>
 315    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
 316
 317    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer)
 318    template<class Disposer>
 319    size_type erase_and_dispose(const key_type &key, Disposer disposer);
 320
 321    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 322    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 323    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
 324
 325    //! @copydoc ::boost::intrusive::bstree::clear
 326    void clear();
 327
 328    //! @copydoc ::boost::intrusive::bstree::clear_and_dispose
 329    template<class Disposer>
 330    void clear_and_dispose(Disposer disposer);
 331
 332    //! @copydoc ::boost::intrusive::bstree::count(const key_type &ke)const
 333    size_type count(const key_type &key) const;
 334
 335    //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
 336    template<class KeyType, class KeyTypeKeyCompare>
 337    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
 338
 339    //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
 340    iterator lower_bound(const key_type &key);
 341
 342    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)
 343    template<class KeyType, class KeyTypeKeyCompare>
 344    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 345
 346    //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
 347    const_iterator lower_bound(const key_type &key) const;
 348
 349    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 350    template<class KeyType, class KeyTypeKeyCompare>
 351    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 352
 353    //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &key)
 354    iterator upper_bound(const key_type &key);
 355
 356    //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)
 357    template<class KeyType, class KeyTypeKeyCompare>
 358    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 359
 360    //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
 361    const_iterator upper_bound(const key_type &key) const;
 362
 363    //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 364    template<class KeyType, class KeyTypeKeyCompare>
 365    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 366
 367    //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
 368    iterator find(const key_type &key);
 369
 370    //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
 371    template<class KeyType, class KeyTypeKeyCompare>
 372    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 373
 374    //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
 375    const_iterator find(const key_type &key) const;
 376
 377    //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const
 378    template<class KeyType, class KeyTypeKeyCompare>
 379    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 380
 381    //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
 382    std::pair<iterator,iterator> equal_range(const key_type &key);
 383
 384    //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)
 385    template<class KeyType, class KeyTypeKeyCompare>
 386    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
 387
 388    //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const
 389    std::pair<const_iterator, const_iterator>
 390       equal_range(const key_type &key) const;
 391
 392    //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const
 393    template<class KeyType, class KeyTypeKeyCompare>
 394    std::pair<const_iterator, const_iterator>
 395       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
 396
 397    //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)
 398    std::pair<iterator,iterator> bounded_range
 399       (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed);
 400
 401    //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 402    template<class KeyType, class KeyTypeKeyCompare>
 403    std::pair<iterator,iterator> bounded_range
 404       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 405
 406    //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const
 407    std::pair<const_iterator, const_iterator>
 408       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
 409
 410    //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 411    template<class KeyType, class KeyTypeKeyCompare>
 412    std::pair<const_iterator, const_iterator> bounded_range
 413          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 414
 415    //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
 416    static iterator s_iterator_to(reference value);
 417
 418    //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
 419    static const_iterator s_iterator_to(const_reference value);
 420
 421    //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
 422    iterator iterator_to(reference value);
 423
 424    //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
 425    const_iterator iterator_to(const_reference value) const;
 426
 427    //! @copydoc ::boost::intrusive::bstree::init_node(reference)
 428    static void init_node(reference value);
 429
 430    //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
 431    pointer unlink_leftmost_without_rebalance();
 432
 433    //! @copydoc ::boost::intrusive::bstree::replace_node
 434    void replace_node(iterator replace_this, reference with_this);
 435
 436    //! @copydoc ::boost::intrusive::bstree::remove_node
 437    void remove_node(reference value);
 438
 439    //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&)
 440    template<class T, class ...Options2>
 441    void merge_unique(avltree<T, Options2...> &);
 442
 443    //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&)
 444    template<class T, class ...Options2>
 445    void merge_equal(avltree<T, Options2...> &);
 446
 447    friend bool operator< (const avltree_impl &x, const avltree_impl &y);
 448
 449    friend bool operator==(const avltree_impl &x, const avltree_impl &y);
 450
 451    friend bool operator!= (const avltree_impl &x, const avltree_impl &y);
 452
 453    friend bool operator>(const avltree_impl &x, const avltree_impl &y);
 454
 455    friend bool operator<=(const avltree_impl &x, const avltree_impl &y);
 456
 457    friend bool operator>=(const avltree_impl &x, const avltree_impl &y);
 458
 459    friend void swap(avltree_impl &x, avltree_impl &y);
 460    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 461 };
 462
 463
 464 //! Helper metafunction to define a \c avltree that yields to the same type when the
 465 //! same options (either explicitly or implicitly) are used.
 466 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 467 template<class T, class ...Options>
 468 #else
 469 template<class T, class O1 = void, class O2 = void
 470                 , class O3 = void, class O4 = void
 471                 , class O5 = void, class O6 = void>
 472 #endif
 473 struct make_avltree
 474 {
 475    /// @cond
 476    typedef typename pack_options
 477       < avltree_defaults,
 478       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 479       O1, O2, O3, O4, O5, O6
 480       #else
 481       Options...
 482       #endif
 483       >::type packed_options;
 484
 485    typedef typename detail::get_value_traits
 486       <T, typename packed_options::proto_value_traits>::type value_traits;
 487
 488    typedef avltree_impl
 489          < value_traits
 490          , typename packed_options::key_of_value
 491          , typename packed_options::compare
 492          , typename packed_options::size_type
 493          , packed_options::constant_time_size
 494          , typename packed_options::header_holder_type
 495          > implementation_defined;
 496    /// @endcond
 497    typedef implementation_defined type;
 498 };
 499
 500
 501 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 502
 503 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 504 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
 505 #else
 506 template<class T, class ...Options>
 507 #endif
 508 class avltree
 509    :  public make_avltree<T,
 510       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 511       O1, O2, O3, O4, O5, O6
 512       #else
 513       Options...
 514       #endif
 515       >::type
 516 {
 517    typedef typename make_avltree
 518       <T,
 519       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 520       O1, O2, O3, O4, O5, O6
 521       #else
 522       Options...
 523       #endif
 524       >::type   Base;
 525    BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree)
 526
 527    public:
 528    typedef typename Base::key_compare        key_compare;
 529    typedef typename Base::value_traits       value_traits;
 530    typedef typename Base::iterator           iterator;
 531    typedef typename Base::const_iterator     const_iterator;
 532    typedef typename Base::reverse_iterator           reverse_iterator;
 533    typedef typename Base::const_reverse_iterator     const_reverse_iterator;
 534
 535    //Assert if passed value traits are compatible with the type
 536    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 537
 538    avltree()
 539       :  Base()
 540    {}
 541
 542    explicit avltree( const key_compare &cmp, const value_traits &v_traits = value_traits())
 543       :  Base(cmp, v_traits)
 544    {}
 545
 546    template<class Iterator>
 547    avltree( bool unique, Iterator b, Iterator e
 548          , const key_compare &cmp = key_compare()
 549          , const value_traits &v_traits = value_traits())
 550       :  Base(unique, b, e, cmp, v_traits)
 551    {}
 552
 553    avltree(BOOST_RV_REF(avltree) x)
 554       :  Base(BOOST_MOVE_BASE(Base, x))
 555    {}
 556
 557    avltree& operator=(BOOST_RV_REF(avltree) x)
 558    {  return static_cast<avltree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
 559
 560    template <class Cloner, class Disposer>
 561    void clone_from(const avltree &src, Cloner cloner, Disposer disposer)
 562    {  Base::clone_from(src, cloner, disposer);  }
 563
 564    template <class Cloner, class Disposer>
 565    void clone_from(BOOST_RV_REF(avltree) src, Cloner cloner, Disposer disposer)
 566    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
 567
 568    static avltree &container_from_end_iterator(iterator end_iterator)
 569    {  return static_cast<avltree &>(Base::container_from_end_iterator(end_iterator));   }
 570
 571    static const avltree &container_from_end_iterator(const_iterator end_iterator)
 572    {  return static_cast<const avltree &>(Base::container_from_end_iterator(end_iterator));   }
 573
 574    static avltree &container_from_iterator(iterator it)
 575    {  return static_cast<avltree &>(Base::container_from_iterator(it));   }
 576
 577    static const avltree &container_from_iterator(const_iterator it)
 578    {  return static_cast<const avltree &>(Base::container_from_iterator(it));   }
 579 };
 580
 581 #endif
 582
 583 } //namespace intrusive
 584 } //namespace boost
 585
 586 #include <boost/intrusive/detail/config_end.hpp>
 587
 588 #endif //BOOST_INTRUSIVE_AVLTREE_HPP