boost/intrusive/avltree.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2007-2013
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/intrusive for documentation.
0010 //
0011 /////////////////////////////////////////////////////////////////////////////
0012 #ifndef BOOST_INTRUSIVE_AVLTREE_HPP
0013 #define BOOST_INTRUSIVE_AVLTREE_HPP
0014
0015 #include <boost/intrusive/detail/config_begin.hpp>
0016 #include <boost/intrusive/intrusive_fwd.hpp>
0017 #include <cstddef>
0018 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>
0019 #include <boost/intrusive/detail/minimal_pair_header.hpp>
0020
0021 #include <boost/intrusive/avl_set_hook.hpp>
0022 #include <boost/intrusive/detail/avltree_node.hpp>
0023 #include <boost/intrusive/bstree.hpp>
0024 #include <boost/intrusive/detail/tree_node.hpp>
0025 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
0026 #include <boost/intrusive/detail/mpl.hpp>
0027 #include <boost/intrusive/pointer_traits.hpp>
0028 #include <boost/intrusive/detail/get_value_traits.hpp>
0029 #include <boost/intrusive/avltree_algorithms.hpp>
0030 #include <boost/intrusive/link_mode.hpp>
0031 #include <boost/move/utility_core.hpp>
0032
0033 #if defined(BOOST_HAS_PRAGMA_ONCE)
0034 #  pragma once
0035 #endif
0036
0037 namespace boost {
0038 namespace intrusive {
0039
0040 /// @cond
0041
0042 struct default_avltree_hook_applier
0043 {  template <class T> struct apply{ typedef typename T::default_avltree_hook type;  };  };
0044
0045 template<>
0046 struct is_default_hook_tag<default_avltree_hook_applier>
0047 {  static const bool value = true;  };
0048
0049 struct avltree_defaults
0050    : bstree_defaults
0051 {
0052    typedef default_avltree_hook_applier proto_value_traits;
0053 };
0054
0055 /// @endcond
0056
0057 //! The class template avltree is an intrusive AVL tree container, that
0058 //! is used to construct intrusive avl_set and avl_multiset containers.
0059 //! The no-throw guarantee holds only, if the key_compare object
0060 //! doesn't throw.
0061 //!
0062 //! The template parameter \c T is the type to be managed by the container.
0063 //! The user can specify additional options and if no options are provided
0064 //! default options are used.
0065 //!
0066 //! The container supports the following options:
0067 //! \c base_hook<>/member_hook<>/value_traits<>,
0068 //! \c constant_time_size<>, \c size_type<> and
0069 //! \c compare<>.
0070 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0071 template<class T, class ...Options>
0072 #else
0073 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
0074 #endif
0075 class avltree_impl
0076    /// @cond
0077    :  public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder>
0078    /// @endcond
0079 {
0080    public:
0081    typedef ValueTraits value_traits;
0082    /// @cond
0083    typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
0084                       , ConstantTimeSize, AvlTreeAlgorithms
0085                       , HeaderHolder>                                tree_type;
0086    typedef tree_type                                                 implementation_defined;
0087    /// @endcond
0088
0089    typedef typename implementation_defined::pointer                  pointer;
0090    typedef typename implementation_defined::const_pointer            const_pointer;
0091    typedef typename implementation_defined::value_type               value_type;
0092    typedef typename implementation_defined::key_type                 key_type;
0093    typedef typename implementation_defined::key_of_value             key_of_value;
0094    typedef typename implementation_defined::reference                reference;
0095    typedef typename implementation_defined::const_reference          const_reference;
0096    typedef typename implementation_defined::difference_type          difference_type;
0097    typedef typename implementation_defined::size_type                size_type;
0098    typedef typename implementation_defined::value_compare            value_compare;
0099    typedef typename implementation_defined::key_compare              key_compare;
0100    typedef typename implementation_defined::iterator                 iterator;
0101    typedef typename implementation_defined::const_iterator           const_iterator;
0102    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
0103    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
0104    typedef typename implementation_defined::node_traits              node_traits;
0105    typedef typename implementation_defined::node                     node;
0106    typedef typename implementation_defined::node_ptr                 node_ptr;
0107    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
0108    typedef typename implementation_defined::node_algorithms          node_algorithms;
0109
0110    static const bool constant_time_size = implementation_defined::constant_time_size;
0111    /// @cond
0112    private:
0113
0114    //noncopyable
0115    BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree_impl)
0116
0117    /// @endcond
0118
0119    public:
0120
0121    typedef typename implementation_defined::insert_commit_data insert_commit_data;
0122
0123    //! @copydoc ::boost::intrusive::bstree::bstree()
0124    avltree_impl()
0125       :  tree_type()
0126    {}
0127
0128    //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &)
0129    explicit avltree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
0130       :  tree_type(cmp, v_traits)
0131    {}
0132
0133    //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
0134    template<class Iterator>
0135    avltree_impl( bool unique, Iterator b, Iterator e
0136               , const key_compare &cmp     = key_compare()
0137               , const value_traits &v_traits = value_traits())
0138       : tree_type(unique, b, e, cmp, v_traits)
0139    {}
0140
0141    //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
0142    avltree_impl(BOOST_RV_REF(avltree_impl) x)
0143       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
0144    {}
0145
0146    //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
0147    avltree_impl& operator=(BOOST_RV_REF(avltree_impl) x)
0148    {  return static_cast<avltree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
0149
0150    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0151
0152    //! @copydoc ::boost::intrusive::bstree::~bstree()
0153    ~avltree_impl();
0154
0155    //! @copydoc ::boost::intrusive::bstree::begin()
0156    iterator begin() BOOST_NOEXCEPT;
0157
0158    //! @copydoc ::boost::intrusive::bstree::begin()const
0159    const_iterator begin() const BOOST_NOEXCEPT;
0160
0161    //! @copydoc ::boost::intrusive::bstree::cbegin()const
0162    const_iterator cbegin() const BOOST_NOEXCEPT;
0163
0164    //! @copydoc ::boost::intrusive::bstree::end()
0165    iterator end() BOOST_NOEXCEPT;
0166
0167    //! @copydoc ::boost::intrusive::bstree::end()const
0168    const_iterator end() const BOOST_NOEXCEPT;
0169
0170    //! @copydoc ::boost::intrusive::bstree::cend()const
0171    const_iterator cend() const BOOST_NOEXCEPT;
0172
0173    //! @copydoc ::boost::intrusive::bstree::rbegin()
0174    reverse_iterator rbegin() BOOST_NOEXCEPT;
0175
0176    //! @copydoc ::boost::intrusive::bstree::rbegin()const
0177    const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
0178
0179    //! @copydoc ::boost::intrusive::bstree::crbegin()const
0180    const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
0181
0182    //! @copydoc ::boost::intrusive::bstree::rend()
0183    reverse_iterator rend() BOOST_NOEXCEPT;
0184
0185    //! @copydoc ::boost::intrusive::bstree::rend()const
0186    const_reverse_iterator rend() const BOOST_NOEXCEPT;
0187
0188    //! @copydoc ::boost::intrusive::bstree::crend()const
0189    const_reverse_iterator crend() const BOOST_NOEXCEPT;
0190
0191    //! @copydoc ::boost::intrusive::bstree::root()
0192    iterator root() BOOST_NOEXCEPT;
0193
0194    //! @copydoc ::boost::intrusive::bstree::root()const
0195    const_iterator root() const BOOST_NOEXCEPT;
0196
0197    //! @copydoc ::boost::intrusive::bstree::croot()const
0198    const_iterator croot() const BOOST_NOEXCEPT;
0199
0200    //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
0201    static avltree_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
0202
0203    //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
0204    static const avltree_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
0205
0206    //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
0207    static avltree_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
0208
0209    //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
0210    static const avltree_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
0211
0212    //! @copydoc ::boost::intrusive::bstree::key_comp()const
0213    key_compare key_comp() const;
0214
0215    //! @copydoc ::boost::intrusive::bstree::value_comp()const
0216    value_compare value_comp() const;
0217
0218    //! @copydoc ::boost::intrusive::bstree::empty()const
0219    bool empty() const BOOST_NOEXCEPT;
0220
0221    //! @copydoc ::boost::intrusive::bstree::size()const
0222    size_type size() const BOOST_NOEXCEPT;
0223
0224    //! @copydoc ::boost::intrusive::bstree::swap
0225    void swap(avltree_impl& other);
0226
0227    //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer)
0228    template <class Cloner, class Disposer>
0229    void clone_from(const avltree_impl &src, Cloner cloner, Disposer disposer);
0230
0231    #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED
0232
0233    using tree_type::clone_from;
0234
0235    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0236
0237    //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer)
0238    template <class Cloner, class Disposer>
0239    void clone_from(BOOST_RV_REF(avltree_impl) src, Cloner cloner, Disposer disposer)
0240    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
0241
0242    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0243
0244    //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
0245    iterator insert_equal(reference value);
0246
0247    //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
0248    iterator insert_equal(const_iterator hint, reference value);
0249
0250    //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
0251    template<class Iterator>
0252    void insert_equal(Iterator b, Iterator e);
0253
0254    //! @copydoc ::boost::intrusive::bstree::insert_unique(reference)
0255    std::pair<iterator, bool> insert_unique(reference value);
0256
0257    //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference)
0258    iterator insert_unique(const_iterator hint, reference value);
0259
0260    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
0261    template<class KeyType, class KeyTypeKeyCompare>
0262    std::pair<iterator, bool> insert_unique_check
0263       (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data);
0264
0265    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
0266    template<class KeyType, class KeyTypeKeyCompare>
0267    std::pair<iterator, bool> insert_unique_check
0268       (const_iterator hint, const KeyType &key
0269       ,KeyTypeKeyCompare comp, insert_commit_data &commit_data);
0270
0271    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&)
0272    std::pair<iterator, bool> insert_unique_check
0273       (const key_type &key, insert_commit_data &commit_data);
0274
0275    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
0276    std::pair<iterator, bool> insert_unique_check
0277       (const_iterator hint, const key_type &key, insert_commit_data &commit_data);
0278
0279    //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
0280    iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) BOOST_NOEXCEPT;
0281
0282    //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
0283    template<class Iterator>
0284    void insert_unique(Iterator b, Iterator e);
0285
0286    //! @copydoc ::boost::intrusive::bstree::insert_before
0287    iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
0288
0289    //! @copydoc ::boost::intrusive::bstree::push_back
0290    void push_back(reference value) BOOST_NOEXCEPT;
0291
0292    //! @copydoc ::boost::intrusive::bstree::push_front
0293    void push_front(reference value) BOOST_NOEXCEPT;
0294
0295    //! @copydoc ::boost::intrusive::bstree::erase(const_iterator)
0296    iterator erase(const_iterator i) BOOST_NOEXCEPT;
0297
0298    //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator)
0299    iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
0300
0301    //! @copydoc ::boost::intrusive::bstree::erase(const key_type &)
0302    size_type erase(const key_type &key);
0303
0304    //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare)
0305    template<class KeyType, class KeyTypeKeyCompare>
0306    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
0307
0308    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer)
0309    template<class Disposer>
0310    iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
0311
0312    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer)
0313    template<class Disposer>
0314    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
0315
0316    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer)
0317    template<class Disposer>
0318    size_type erase_and_dispose(const key_type &key, Disposer disposer);
0319
0320    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
0321    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
0322    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
0323
0324    //! @copydoc ::boost::intrusive::bstree::clear
0325    void clear() BOOST_NOEXCEPT;
0326
0327    //! @copydoc ::boost::intrusive::bstree::clear_and_dispose
0328    template<class Disposer>
0329    void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
0330
0331    //! @copydoc ::boost::intrusive::bstree::count(const key_type &ke)const
0332    size_type count(const key_type &key) const;
0333
0334    //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
0335    template<class KeyType, class KeyTypeKeyCompare>
0336    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
0337
0338    //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
0339    iterator lower_bound(const key_type &key);
0340
0341    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)
0342    template<class KeyType, class KeyTypeKeyCompare>
0343    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
0344
0345    //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
0346    const_iterator lower_bound(const key_type &key) const;
0347
0348    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
0349    template<class KeyType, class KeyTypeKeyCompare>
0350    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0351
0352    //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &key)
0353    iterator upper_bound(const key_type &key);
0354
0355    //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)
0356    template<class KeyType, class KeyTypeKeyCompare>
0357    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
0358
0359    //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
0360    const_iterator upper_bound(const key_type &key) const;
0361
0362    //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
0363    template<class KeyType, class KeyTypeKeyCompare>
0364    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0365
0366    //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
0367    iterator find(const key_type &key);
0368
0369    //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
0370    template<class KeyType, class KeyTypeKeyCompare>
0371    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
0372
0373    //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
0374    const_iterator find(const key_type &key) const;
0375
0376    //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const
0377    template<class KeyType, class KeyTypeKeyCompare>
0378    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
0379
0380    //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
0381    std::pair<iterator,iterator> equal_range(const key_type &key);
0382
0383    //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)
0384    template<class KeyType, class KeyTypeKeyCompare>
0385    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
0386
0387    //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const
0388    std::pair<const_iterator, const_iterator>
0389       equal_range(const key_type &key) const;
0390
0391    //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const
0392    template<class KeyType, class KeyTypeKeyCompare>
0393    std::pair<const_iterator, const_iterator>
0394       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
0395
0396    //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)
0397    std::pair<iterator,iterator> bounded_range
0398       (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed);
0399
0400    //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
0401    template<class KeyType, class KeyTypeKeyCompare>
0402    std::pair<iterator,iterator> bounded_range
0403       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
0404
0405    //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const
0406    std::pair<const_iterator, const_iterator>
0407       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
0408
0409    //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
0410    template<class KeyType, class KeyTypeKeyCompare>
0411    std::pair<const_iterator, const_iterator> bounded_range
0412          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
0413
0414    //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
0415    static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
0416
0417    //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
0418    static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
0419
0420    //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
0421    iterator iterator_to(reference value) BOOST_NOEXCEPT;
0422
0423    //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
0424    const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
0425
0426    //! @copydoc ::boost::intrusive::bstree::init_node(reference)
0427    static void init_node(reference value) BOOST_NOEXCEPT;
0428
0429    //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
0430    pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
0431
0432    //! @copydoc ::boost::intrusive::bstree::replace_node
0433    void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
0434
0435    //! @copydoc ::boost::intrusive::bstree::remove_node
0436    void remove_node(reference value) BOOST_NOEXCEPT;
0437
0438    //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&)
0439    template<class T, class ...Options2>
0440    void merge_unique(avltree<T, Options2...> &);
0441
0442    //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&)
0443    template<class T, class ...Options2>
0444    void merge_equal(avltree<T, Options2...> &);
0445
0446    friend bool operator< (const avltree_impl &x, const avltree_impl &y);
0447
0448    friend bool operator==(const avltree_impl &x, const avltree_impl &y);
0449
0450    friend bool operator!= (const avltree_impl &x, const avltree_impl &y);
0451
0452    friend bool operator>(const avltree_impl &x, const avltree_impl &y);
0453
0454    friend bool operator<=(const avltree_impl &x, const avltree_impl &y);
0455
0456    friend bool operator>=(const avltree_impl &x, const avltree_impl &y);
0457
0458    friend void swap(avltree_impl &x, avltree_impl &y);
0459    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0460 };
0461
0462
0463 //! Helper metafunction to define a \c avltree that yields to the same type when the
0464 //! same options (either explicitly or implicitly) are used.
0465 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0466 template<class T, class ...Options>
0467 #else
0468 template<class T, class O1 = void, class O2 = void
0469                 , class O3 = void, class O4 = void
0470                 , class O5 = void, class O6 = void>
0471 #endif
0472 struct make_avltree
0473 {
0474    /// @cond
0475    typedef typename pack_options
0476       < avltree_defaults,
0477       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0478       O1, O2, O3, O4, O5, O6
0479       #else
0480       Options...
0481       #endif
0482       >::type packed_options;
0483
0484    typedef typename detail::get_value_traits
0485       <T, typename packed_options::proto_value_traits>::type value_traits;
0486
0487    typedef avltree_impl
0488          < value_traits
0489          , typename packed_options::key_of_value
0490          , typename packed_options::compare
0491          , typename packed_options::size_type
0492          , packed_options::constant_time_size
0493          , typename packed_options::header_holder_type
0494          > implementation_defined;
0495    /// @endcond
0496    typedef implementation_defined type;
0497 };
0498
0499
0500 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0501
0502 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0503 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
0504 #else
0505 template<class T, class ...Options>
0506 #endif
0507 class avltree
0508    :  public make_avltree<T,
0509       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0510       O1, O2, O3, O4, O5, O6
0511       #else
0512       Options...
0513       #endif
0514       >::type
0515 {
0516    typedef typename make_avltree
0517       <T,
0518       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0519       O1, O2, O3, O4, O5, O6
0520       #else
0521       Options...
0522       #endif
0523       >::type   Base;
0524    BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree)
0525
0526    public:
0527    typedef typename Base::key_compare        key_compare;
0528    typedef typename Base::value_traits       value_traits;
0529    typedef typename Base::iterator           iterator;
0530    typedef typename Base::const_iterator     const_iterator;
0531    typedef typename Base::reverse_iterator           reverse_iterator;
0532    typedef typename Base::const_reverse_iterator     const_reverse_iterator;
0533
0534    //Assert if passed value traits are compatible with the type
0535    BOOST_INTRUSIVE_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
0536
0537    inline avltree()
0538       :  Base()
0539    {}
0540
0541    inline explicit avltree( const key_compare &cmp, const value_traits &v_traits = value_traits())
0542       :  Base(cmp, v_traits)
0543    {}
0544
0545    template<class Iterator>
0546    inline avltree( bool unique, Iterator b, Iterator e
0547          , const key_compare &cmp = key_compare()
0548          , const value_traits &v_traits = value_traits())
0549       :  Base(unique, b, e, cmp, v_traits)
0550    {}
0551
0552    inline avltree(BOOST_RV_REF(avltree) x)
0553       :  Base(BOOST_MOVE_BASE(Base, x))
0554    {}
0555
0556    inline avltree& operator=(BOOST_RV_REF(avltree) x)
0557    {  return static_cast<avltree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
0558
0559    template <class Cloner, class Disposer>
0560    inline void clone_from(const avltree &src, Cloner cloner, Disposer disposer)
0561    {  Base::clone_from(src, cloner, disposer);  }
0562
0563    template <class Cloner, class Disposer>
0564    inline void clone_from(BOOST_RV_REF(avltree) src, Cloner cloner, Disposer disposer)
0565    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
0566
0567    inline static avltree &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
0568    {  return static_cast<avltree &>(Base::container_from_end_iterator(end_iterator));   }
0569
0570    inline static const avltree &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
0571    {  return static_cast<const avltree &>(Base::container_from_end_iterator(end_iterator));   }
0572
0573    inline static avltree &container_from_iterator(iterator it) BOOST_NOEXCEPT
0574    {  return static_cast<avltree &>(Base::container_from_iterator(it));   }
0575
0576    inline static const avltree &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
0577    {  return static_cast<const avltree &>(Base::container_from_iterator(it));   }
0578 };
0579
0580 #endif
0581
0582 } //namespace intrusive
0583 } //namespace boost
0584
0585 #include <boost/intrusive/detail/config_end.hpp>
0586
0587 #endif //BOOST_INTRUSIVE_AVLTREE_HPP