Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:38:38 

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2007-2014
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_AVL_SET_HPP
0013 #define BOOST_INTRUSIVE_AVL_SET_HPP
0014 
0015 #include <boost/intrusive/detail/config_begin.hpp>
0016 #include <boost/intrusive/intrusive_fwd.hpp>
0017 #include <boost/intrusive/avltree.hpp>
0018 #include <boost/intrusive/detail/mpl.hpp>
0019 #include <boost/move/utility_core.hpp>
0020 #include <boost/static_assert.hpp>
0021 
0022 #if defined(BOOST_HAS_PRAGMA_ONCE)
0023 #  pragma once
0024 #endif
0025 
0026 namespace boost {
0027 namespace intrusive {
0028 
0029 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0030 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
0031 class avl_multiset_impl;
0032 #endif
0033 
0034 //! The class template avl_set is an intrusive container, that mimics most of
0035 //! the interface of std::set as described in the C++ standard.
0036 //!
0037 //! The template parameter \c T is the type to be managed by the container.
0038 //! The user can specify additional options and if no options are provided
0039 //! default options are used.
0040 //!
0041 //! The container supports the following options:
0042 //! \c base_hook<>/member_hook<>/value_traits<>,
0043 //! \c constant_time_size<>, \c size_type<> and
0044 //! \c compare<>.
0045 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0046 template<class T, class ...Options>
0047 #else
0048 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
0049 #endif
0050 class avl_set_impl
0051 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0052    : public bstree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder>
0053 #endif
0054 {
0055    /// @cond
0056    typedef bstree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder> tree_type;
0057    BOOST_MOVABLE_BUT_NOT_COPYABLE(avl_set_impl)
0058 
0059    typedef tree_type implementation_defined;
0060    /// @endcond
0061 
0062    public:
0063    typedef typename implementation_defined::value_type               value_type;
0064    typedef typename implementation_defined::key_type                 key_type;
0065    typedef typename implementation_defined::key_of_value             key_of_value;
0066    typedef typename implementation_defined::value_traits             value_traits;
0067    typedef typename implementation_defined::pointer                  pointer;
0068    typedef typename implementation_defined::const_pointer            const_pointer;
0069    typedef typename implementation_defined::reference                reference;
0070    typedef typename implementation_defined::const_reference          const_reference;
0071    typedef typename implementation_defined::difference_type          difference_type;
0072    typedef typename implementation_defined::size_type                size_type;
0073    typedef typename implementation_defined::value_compare            value_compare;
0074    typedef typename implementation_defined::key_compare              key_compare;
0075    typedef typename implementation_defined::iterator                 iterator;
0076    typedef typename implementation_defined::const_iterator           const_iterator;
0077    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
0078    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
0079    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
0080    typedef typename implementation_defined::node_traits              node_traits;
0081    typedef typename implementation_defined::node                     node;
0082    typedef typename implementation_defined::node_ptr                 node_ptr;
0083    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
0084    typedef typename implementation_defined::node_algorithms          node_algorithms;
0085 
0086    static const bool constant_time_size = tree_type::constant_time_size;
0087 
0088    public:
0089 
0090    //! @copydoc ::boost::intrusive::avltree::avltree()
0091    avl_set_impl()
0092       :  tree_type()
0093    {}
0094 
0095    //! @copydoc ::boost::intrusive::avltree::avltree(const key_compare &,const value_traits &)
0096    explicit avl_set_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
0097       :  tree_type(cmp, v_traits)
0098    {}
0099 
0100    //! @copydoc ::boost::intrusive::avltree::avltree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
0101    template<class Iterator>
0102    avl_set_impl( Iterator b, Iterator e
0103            , const key_compare &cmp = key_compare()
0104            , const value_traits &v_traits = value_traits())
0105       : tree_type(true, b, e, cmp, v_traits)
0106    {}
0107 
0108    //! @copydoc ::boost::intrusive::avltree::avltree(avltree &&)
0109    avl_set_impl(BOOST_RV_REF(avl_set_impl) x)
0110       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
0111    {}
0112 
0113    //! @copydoc ::boost::intrusive::avltree::operator=(avltree &&)
0114    avl_set_impl& operator=(BOOST_RV_REF(avl_set_impl) x)
0115    {  return static_cast<avl_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
0116 
0117    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0118 
0119    //! @copydoc ::boost::intrusive::avltree::~avltree()
0120    ~avl_set_impl();
0121 
0122    //! @copydoc ::boost::intrusive::avltree::begin()
0123    iterator begin() BOOST_NOEXCEPT;
0124 
0125    //! @copydoc ::boost::intrusive::avltree::begin()const
0126    const_iterator begin() const BOOST_NOEXCEPT;
0127 
0128    //! @copydoc ::boost::intrusive::avltree::cbegin()const
0129    const_iterator cbegin() const BOOST_NOEXCEPT;
0130 
0131    //! @copydoc ::boost::intrusive::avltree::end()
0132    iterator end() BOOST_NOEXCEPT;
0133 
0134    //! @copydoc ::boost::intrusive::avltree::end()const
0135    const_iterator end() const BOOST_NOEXCEPT;
0136 
0137    //! @copydoc ::boost::intrusive::avltree::cend()const
0138    const_iterator cend() const BOOST_NOEXCEPT;
0139 
0140    //! @copydoc ::boost::intrusive::avltree::begin()
0141    reverse_iterator avlegin();
0142 
0143    //! @copydoc ::boost::intrusive::avltree::begin()const
0144    const_reverse_iterator avlegin() const;
0145 
0146    //! @copydoc ::boost::intrusive::avltree::crbegin()const
0147    const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
0148 
0149    //! @copydoc ::boost::intrusive::avltree::rend()
0150    reverse_iterator rend() BOOST_NOEXCEPT;
0151 
0152    //! @copydoc ::boost::intrusive::avltree::rend()const
0153    const_reverse_iterator rend() const BOOST_NOEXCEPT;
0154 
0155    //! @copydoc ::boost::intrusive::avltree::crend()const
0156    const_reverse_iterator crend() const BOOST_NOEXCEPT;
0157 
0158    //! @copydoc ::boost::intrusive::avltree::root()
0159    iterator root() BOOST_NOEXCEPT;
0160 
0161    //! @copydoc ::boost::intrusive::avltree::root()const
0162    const_iterator root() const BOOST_NOEXCEPT;
0163 
0164    //! @copydoc ::boost::intrusive::avltree::croot()const
0165    const_iterator croot() const BOOST_NOEXCEPT;
0166 
0167    //! @copydoc ::boost::intrusive::avltree::container_from_end_iterator(iterator)
0168    static avl_set_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
0169 
0170    //! @copydoc ::boost::intrusive::avltree::container_from_end_iterator(const_iterator)
0171    static const avl_set_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
0172 
0173    //! @copydoc ::boost::intrusive::avltree::container_from_iterator(iterator)
0174    static avl_set_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
0175 
0176    //! @copydoc ::boost::intrusive::avltree::container_from_iterator(const_iterator)
0177    static const avl_set_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
0178 
0179    //! @copydoc ::boost::intrusive::avltree::key_comp()const
0180    key_compare key_comp() const;
0181 
0182    //! @copydoc ::boost::intrusive::avltree::value_comp()const
0183    value_compare value_comp() const;
0184 
0185    //! @copydoc ::boost::intrusive::avltree::empty()const
0186    bool empty() const BOOST_NOEXCEPT;
0187 
0188    //! @copydoc ::boost::intrusive::avltree::size()const
0189    size_type size() const BOOST_NOEXCEPT;
0190 
0191    //! @copydoc ::boost::intrusive::avltree::swap
0192    void swap(avl_set_impl& other);
0193 
0194    //! @copydoc ::boost::intrusive::avltree::clone_from(const avltree&,Cloner,Disposer)
0195    template <class Cloner, class Disposer>
0196    void clone_from(const avl_set_impl &src, Cloner cloner, Disposer disposer);
0197 
0198    #else
0199 
0200    using tree_type::clone_from;
0201 
0202    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0203 
0204    //! @copydoc ::boost::intrusive::avltree::clone_from(avltree&&,Cloner,Disposer)
0205    template <class Cloner, class Disposer>
0206    void clone_from(BOOST_RV_REF(avl_set_impl) src, Cloner cloner, Disposer disposer)
0207    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
0208 
0209    //! @copydoc ::boost::intrusive::avltree::insert_unique(reference)
0210    std::pair<iterator, bool> insert(reference value)
0211    {  return tree_type::insert_unique(value);  }
0212 
0213    //! @copydoc ::boost::intrusive::avltree::insert_unique(const_iterator,reference)
0214    iterator insert(const_iterator hint, reference value)
0215    {  return tree_type::insert_unique(hint, value);  }
0216 
0217    //! @copydoc ::boost::intrusive::avltree::insert_unique_check(const key_type&,insert_commit_data&)
0218    std::pair<iterator, bool> insert_check
0219       (const key_type &key, insert_commit_data &commit_data)
0220    {  return tree_type::insert_unique_check(key, commit_data); }
0221 
0222    //! @copydoc ::boost::intrusive::avltree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
0223    std::pair<iterator, bool> insert_check
0224       (const_iterator hint, const key_type &key
0225       ,insert_commit_data &commit_data)
0226    {  return tree_type::insert_unique_check(hint, key, commit_data); }
0227 
0228    //! @copydoc ::boost::intrusive::avltree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
0229    template<class KeyType, class KeyTypeKeyCompare>
0230    std::pair<iterator, bool> insert_check
0231       (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data)
0232    {  return tree_type::insert_unique_check(key, comp, commit_data); }
0233 
0234    //! @copydoc ::boost::intrusive::avltree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
0235    template<class KeyType, class KeyTypeKeyCompare>
0236    std::pair<iterator, bool> insert_check
0237       (const_iterator hint, const KeyType &key
0238       ,KeyTypeKeyCompare comp, insert_commit_data &commit_data)
0239    {  return tree_type::insert_unique_check(hint, key, comp, commit_data); }
0240 
0241    //! @copydoc ::boost::intrusive::avltree::insert_unique(Iterator,Iterator)
0242    template<class Iterator>
0243    void insert(Iterator b, Iterator e)
0244    {  tree_type::insert_unique(b, e);  }
0245 
0246    //! @copydoc ::boost::intrusive::avltree::insert_unique_commit
0247    iterator insert_commit(reference value, const insert_commit_data &commit_data) BOOST_NOEXCEPT
0248    {  return tree_type::insert_unique_commit(value, commit_data);  }
0249 
0250    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0251    //! @copydoc ::boost::intrusive::avltree::insert_before
0252    iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
0253 
0254    //! @copydoc ::boost::intrusive::avltree::push_back
0255    void push_back(reference value) BOOST_NOEXCEPT;
0256 
0257    //! @copydoc ::boost::intrusive::avltree::push_front
0258    void push_front(reference value) BOOST_NOEXCEPT;
0259 
0260    //! @copydoc ::boost::intrusive::avltree::erase(const_iterator)
0261    iterator erase(const_iterator i) BOOST_NOEXCEPT;
0262 
0263    //! @copydoc ::boost::intrusive::avltree::erase(const_iterator,const_iterator)
0264    iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
0265 
0266    //! @copydoc ::boost::intrusive::avltree::erase(const key_type &key)
0267    size_type erase(const key_type &key);
0268 
0269    //! @copydoc ::boost::intrusive::avltree::erase(const KeyType&,KeyTypeKeyCompare)
0270    template<class KeyType, class KeyTypeKeyCompare>
0271    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
0272 
0273    //! @copydoc ::boost::intrusive::avltree::erase_and_dispose(const_iterator,Disposer)
0274    template<class Disposer>
0275    iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
0276 
0277    //! @copydoc ::boost::intrusive::avltree::erase_and_dispose(const_iterator,const_iterator,Disposer)
0278    template<class Disposer>
0279    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
0280 
0281    //! @copydoc ::boost::intrusive::avltree::erase_and_dispose(const key_type &, Disposer)
0282    template<class Disposer>
0283    size_type erase_and_dispose(const key_type &key, Disposer disposer);
0284 
0285    //! @copydoc ::boost::intrusive::avltree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
0286    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
0287    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
0288 
0289    //! @copydoc ::boost::intrusive::avltree::clear
0290    void clear() BOOST_NOEXCEPT;
0291 
0292    //! @copydoc ::boost::intrusive::avltree::clear_and_dispose
0293    template<class Disposer>
0294    void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
0295 
0296    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0297 
0298    //! @copydoc ::boost::intrusive::avltree::count(const key_type &)const
0299    size_type count(const key_type &key) const
0300    {  return static_cast<size_type>(this->tree_type::find(key) != this->tree_type::cend()); }
0301 
0302    //! @copydoc ::boost::intrusive::avltree::count(const KeyType&,KeyTypeKeyCompare)const
0303    template<class KeyType, class KeyTypeKeyCompare>
0304    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const
0305    {  return static_cast<size_type>(this->tree_type::find(key, comp) != this->tree_type::cend()); }
0306 
0307    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0308 
0309    //! @copydoc ::boost::intrusive::avltree::lower_bound(const key_type &)
0310    iterator lower_bound(const key_type &key);
0311 
0312    //! @copydoc ::boost::intrusive::avltree::lower_bound(const KeyType&,KeyTypeKeyCompare)
0313    template<class KeyType, class KeyTypeKeyCompare>
0314    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
0315 
0316    //! @copydoc ::boost::intrusive::avltree::lower_bound(const key_type &)const
0317    const_iterator lower_bound(const key_type &key) const;
0318 
0319    //! @copydoc ::boost::intrusive::avltree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
0320    template<class KeyType, class KeyTypeKeyCompare>
0321    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0322 
0323    //! @copydoc ::boost::intrusive::avltree::upper_bound(const key_type &)
0324    iterator upper_bound(const key_type &key);
0325 
0326    //! @copydoc ::boost::intrusive::avltree::upper_bound(const KeyType&,KeyTypeKeyCompare)
0327    template<class KeyType, class KeyTypeKeyCompare>
0328    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
0329 
0330    //! @copydoc ::boost::intrusive::avltree::upper_bound(const key_type &)const
0331    const_iterator upper_bound(const key_type &key) const;
0332 
0333    //! @copydoc ::boost::intrusive::avltree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
0334    template<class KeyType, class KeyTypeKeyCompare>
0335    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0336 
0337    //! @copydoc ::boost::intrusive::avltree::find(const key_type &)
0338    iterator find(const key_type &key);
0339 
0340    //! @copydoc ::boost::intrusive::avltree::find(const KeyType&,KeyTypeKeyCompare)
0341    template<class KeyType, class KeyTypeKeyCompare>
0342    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
0343 
0344    //! @copydoc ::boost::intrusive::avltree::find(const key_type &)const
0345    const_iterator find(const key_type &key) const;
0346 
0347    //! @copydoc ::boost::intrusive::avltree::find(const KeyType&,KeyTypeKeyCompare)const
0348    template<class KeyType, class KeyTypeKeyCompare>
0349    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
0350 
0351    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0352 
0353    //! @copydoc ::boost::intrusive::avltree::equal_range(const key_type &)
0354    std::pair<iterator,iterator> equal_range(const key_type &key)
0355    {  return this->tree_type::lower_bound_range(key); }
0356 
0357    //! @copydoc ::boost::intrusive::avltree::equal_range(const KeyType&,KeyTypeKeyCompare)
0358    template<class KeyType, class KeyTypeKeyCompare>
0359    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp)
0360    {  return this->tree_type::equal_range(key, comp); }
0361 
0362    //! @copydoc ::boost::intrusive::avltree::equal_range(const key_type &)const
0363    std::pair<const_iterator, const_iterator>
0364       equal_range(const key_type &key) const
0365    {  return this->tree_type::lower_bound_range(key); }
0366 
0367    //! @copydoc ::boost::intrusive::avltree::equal_range(const KeyType&,KeyTypeKeyCompare)const
0368    template<class KeyType, class KeyTypeKeyCompare>
0369    std::pair<const_iterator, const_iterator>
0370       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const
0371    {  return this->tree_type::equal_range(key, comp); }
0372 
0373    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0374 
0375    //! @copydoc ::boost::intrusive::avltree::bounded_range(const key_type &,const key_type &,bool,bool)
0376    std::pair<iterator,iterator> bounded_range
0377       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
0378 
0379    //! @copydoc ::boost::intrusive::avltree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
0380    template<class KeyType, class KeyTypeKeyCompare>
0381    std::pair<iterator,iterator> bounded_range
0382       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
0383 
0384    //! @copydoc ::boost::intrusive::avltree::bounded_range(const key_type &,const key_type &,bool,bool)const
0385    std::pair<const_iterator, const_iterator>
0386       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
0387 
0388    //! @copydoc ::boost::intrusive::avltree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
0389    template<class KeyType, class KeyTypeKeyCompare>
0390    std::pair<const_iterator, const_iterator> bounded_range
0391          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
0392 
0393    //! @copydoc ::boost::intrusive::avltree::s_iterator_to(reference)
0394    static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
0395 
0396    //! @copydoc ::boost::intrusive::avltree::s_iterator_to(const_reference)
0397    static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
0398 
0399    //! @copydoc ::boost::intrusive::avltree::iterator_to(reference)
0400    iterator iterator_to(reference value) BOOST_NOEXCEPT;
0401 
0402    //! @copydoc ::boost::intrusive::avltree::iterator_to(const_reference)const
0403    const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
0404 
0405    //! @copydoc ::boost::intrusive::avltree::init_node(reference)
0406    static void init_node(reference value) BOOST_NOEXCEPT;
0407 
0408    //! @copydoc ::boost::intrusive::avltree::unlink_leftmost_without_rebalance
0409    pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
0410 
0411    //! @copydoc ::boost::intrusive::avltree::replace_node
0412    void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
0413 
0414    //! @copydoc ::boost::intrusive::avltree::remove_node
0415    void remove_node(reference value) BOOST_NOEXCEPT;
0416 
0417    //! @copydoc ::boost::intrusive::avltree::merge_unique
0418    template<class ...Options2>
0419    void merge(avl_set<T, Options2...> &source);
0420 
0421    //! @copydoc ::boost::intrusive::avltree::merge_unique
0422    template<class ...Options2>
0423    void merge(avl_multiset<T, Options2...> &source);
0424 
0425    #else
0426 
0427    template<class Compare2>
0428    void merge(avl_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
0429    {  return tree_type::merge_unique(source);  }
0430 
0431 
0432    template<class Compare2>
0433    void merge(avl_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
0434    {  return tree_type::merge_unique(source);  }
0435 
0436    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0437 };
0438 
0439 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0440 
0441 template<class T, class ...Options>
0442 bool operator!= (const avl_set_impl<T, Options...> &x, const avl_set_impl<T, Options...> &y);
0443 
0444 template<class T, class ...Options>
0445 bool operator>(const avl_set_impl<T, Options...> &x, const avl_set_impl<T, Options...> &y);
0446 
0447 template<class T, class ...Options>
0448 bool operator<=(const avl_set_impl<T, Options...> &x, const avl_set_impl<T, Options...> &y);
0449 
0450 template<class T, class ...Options>
0451 bool operator>=(const avl_set_impl<T, Options...> &x, const avl_set_impl<T, Options...> &y);
0452 
0453 template<class T, class ...Options>
0454 void swap(avl_set_impl<T, Options...> &x, avl_set_impl<T, Options...> &y);
0455 
0456 #endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0457 
0458 //! Helper metafunction to define a \c set that yields to the same type when the
0459 //! same options (either explicitly or implicitly) are used.
0460 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0461 template<class T, class ...Options>
0462 #else
0463 template<class T, class O1 = void, class O2 = void
0464                 , class O3 = void, class O4 = void
0465                 , class O5 = void, class O6 = void>
0466 #endif
0467 struct make_avl_set
0468 {
0469    /// @cond
0470    typedef typename pack_options
0471       < avltree_defaults,
0472       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0473       O1, O2, O3, O4, O5, O6
0474       #else
0475       Options...
0476       #endif
0477       >::type packed_options;
0478 
0479    typedef typename detail::get_value_traits
0480       <T, typename packed_options::proto_value_traits>::type value_traits;
0481 
0482    typedef avl_set_impl
0483          < value_traits
0484          , typename packed_options::key_of_value
0485          , typename packed_options::compare
0486          , typename packed_options::size_type
0487          , packed_options::constant_time_size
0488          , typename packed_options::header_holder_type
0489          > implementation_defined;
0490    /// @endcond
0491    typedef implementation_defined type;
0492 };
0493 
0494 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0495 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0496 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
0497 #else
0498 template<class T, class ...Options>
0499 #endif
0500 class avl_set
0501    :  public make_avl_set<T,
0502    #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0503    O1, O2, O3, O4, O5, O6
0504    #else
0505    Options...
0506    #endif
0507    >::type
0508 {
0509    typedef typename make_avl_set
0510       <T,
0511       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0512       O1, O2, O3, O4, O5, O6
0513       #else
0514       Options...
0515       #endif
0516       >::type   Base;
0517 
0518    BOOST_MOVABLE_BUT_NOT_COPYABLE(avl_set)
0519    public:
0520    typedef typename Base::key_compare        key_compare;
0521    typedef typename Base::value_traits       value_traits;
0522    typedef typename Base::iterator           iterator;
0523    typedef typename Base::const_iterator     const_iterator;
0524 
0525    //Assert if passed value traits are compatible with the type
0526    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
0527 
0528    BOOST_INTRUSIVE_FORCEINLINE avl_set()
0529       :  Base()
0530    {}
0531 
0532    BOOST_INTRUSIVE_FORCEINLINE explicit avl_set( const key_compare &cmp, const value_traits &v_traits = value_traits())
0533       :  Base(cmp, v_traits)
0534    {}
0535 
0536    template<class Iterator>
0537    BOOST_INTRUSIVE_FORCEINLINE avl_set( Iterator b, Iterator e
0538       , const key_compare &cmp = key_compare()
0539       , const value_traits &v_traits = value_traits())
0540       :  Base(b, e, cmp, v_traits)
0541    {}
0542 
0543    BOOST_INTRUSIVE_FORCEINLINE avl_set(BOOST_RV_REF(avl_set) x)
0544       :  Base(BOOST_MOVE_BASE(Base, x))
0545    {}
0546 
0547    BOOST_INTRUSIVE_FORCEINLINE avl_set& operator=(BOOST_RV_REF(avl_set) x)
0548    {  return static_cast<avl_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
0549 
0550    template <class Cloner, class Disposer>
0551    BOOST_INTRUSIVE_FORCEINLINE void clone_from(const avl_set &src, Cloner cloner, Disposer disposer)
0552    {  Base::clone_from(src, cloner, disposer);  }
0553 
0554    template <class Cloner, class Disposer>
0555    BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(avl_set) src, Cloner cloner, Disposer disposer)
0556    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
0557 
0558    BOOST_INTRUSIVE_FORCEINLINE static avl_set &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
0559    {  return static_cast<avl_set &>(Base::container_from_end_iterator(end_iterator));   }
0560 
0561    BOOST_INTRUSIVE_FORCEINLINE static const avl_set &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
0562    {  return static_cast<const avl_set &>(Base::container_from_end_iterator(end_iterator));   }
0563 
0564    BOOST_INTRUSIVE_FORCEINLINE static avl_set &container_from_iterator(iterator it) BOOST_NOEXCEPT
0565    {  return static_cast<avl_set &>(Base::container_from_iterator(it));   }
0566 
0567    BOOST_INTRUSIVE_FORCEINLINE static const avl_set &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
0568    {  return static_cast<const avl_set &>(Base::container_from_iterator(it));   }
0569 };
0570 
0571 #endif
0572 
0573 //! The class template avl_multiset is an intrusive container, that mimics most of
0574 //! the interface of std::_multiset as described in the C++ standard.
0575 //!
0576 //! The template parameter \c T is the type to be managed by the container.
0577 //! The user can specify additional options and if no options are provided
0578 //! default options are used.
0579 //!
0580 //! The container supports the following options:
0581 //! \c base_hook<>/member_hook<>/value_traits<>,
0582 //! \c constant_time_size<>, \c size_type<> and
0583 //! \c compare<>.
0584 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0585 template<class T, class ...Options>
0586 #else
0587 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
0588 #endif
0589 class avl_multiset_impl
0590 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0591    : public bstree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder>
0592 #endif
0593 {
0594    /// @cond
0595    typedef bstree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder> tree_type;
0596 
0597    BOOST_MOVABLE_BUT_NOT_COPYABLE(avl_multiset_impl)
0598    typedef tree_type implementation_defined;
0599    /// @endcond
0600 
0601    public:
0602    typedef typename implementation_defined::value_type               value_type;
0603    typedef typename implementation_defined::key_type                 key_type;
0604    typedef typename implementation_defined::key_of_value             key_of_value;
0605    typedef typename implementation_defined::value_traits             value_traits;
0606    typedef typename implementation_defined::pointer                  pointer;
0607    typedef typename implementation_defined::const_pointer            const_pointer;
0608    typedef typename implementation_defined::reference                reference;
0609    typedef typename implementation_defined::const_reference          const_reference;
0610    typedef typename implementation_defined::difference_type          difference_type;
0611    typedef typename implementation_defined::size_type                size_type;
0612    typedef typename implementation_defined::value_compare            value_compare;
0613    typedef typename implementation_defined::key_compare              key_compare;
0614    typedef typename implementation_defined::iterator                 iterator;
0615    typedef typename implementation_defined::const_iterator           const_iterator;
0616    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
0617    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
0618    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
0619    typedef typename implementation_defined::node_traits              node_traits;
0620    typedef typename implementation_defined::node                     node;
0621    typedef typename implementation_defined::node_ptr                 node_ptr;
0622    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
0623    typedef typename implementation_defined::node_algorithms          node_algorithms;
0624 
0625    static const bool constant_time_size = tree_type::constant_time_size;
0626 
0627    public:
0628    //! @copydoc ::boost::intrusive::avltree::avltree()
0629    avl_multiset_impl()
0630       :  tree_type()
0631    {}
0632 
0633    //! @copydoc ::boost::intrusive::avltree::avltree(const key_compare &,const value_traits &)
0634    explicit avl_multiset_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
0635       :  tree_type(cmp, v_traits)
0636    {}
0637 
0638    //! @copydoc ::boost::intrusive::avltree::avltree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
0639    template<class Iterator>
0640    avl_multiset_impl( Iterator b, Iterator e
0641                 , const key_compare &cmp = key_compare()
0642                 , const value_traits &v_traits = value_traits())
0643       : tree_type(false, b, e, cmp, v_traits)
0644    {}
0645 
0646    //! @copydoc ::boost::intrusive::avltree::avltree(avltree &&)
0647    avl_multiset_impl(BOOST_RV_REF(avl_multiset_impl) x)
0648       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
0649    {}
0650 
0651    //! @copydoc ::boost::intrusive::avltree::operator=(avltree &&)
0652    avl_multiset_impl& operator=(BOOST_RV_REF(avl_multiset_impl) x)
0653    {  return static_cast<avl_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
0654 
0655    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0656    //! @copydoc ::boost::intrusive::avltree::~avltree()
0657    ~avl_multiset_impl();
0658 
0659    //! @copydoc ::boost::intrusive::avltree::begin()
0660    iterator begin() BOOST_NOEXCEPT;
0661 
0662    //! @copydoc ::boost::intrusive::avltree::begin()const
0663    const_iterator begin() const BOOST_NOEXCEPT;
0664 
0665    //! @copydoc ::boost::intrusive::avltree::cbegin()const
0666    const_iterator cbegin() const BOOST_NOEXCEPT;
0667 
0668    //! @copydoc ::boost::intrusive::avltree::end()
0669    iterator end() BOOST_NOEXCEPT;
0670 
0671    //! @copydoc ::boost::intrusive::avltree::end()const
0672    const_iterator end() const BOOST_NOEXCEPT;
0673 
0674    //! @copydoc ::boost::intrusive::avltree::cend()const
0675    const_iterator cend() const BOOST_NOEXCEPT;
0676 
0677    //! @copydoc ::boost::intrusive::avltree::rbegin()
0678    reverse_iterator rbegin() BOOST_NOEXCEPT;
0679 
0680    //! @copydoc ::boost::intrusive::avltree::rbegin()const
0681    const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
0682 
0683    //! @copydoc ::boost::intrusive::avltree::crbegin()const
0684    const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
0685 
0686    //! @copydoc ::boost::intrusive::avltree::rend()
0687    reverse_iterator rend() BOOST_NOEXCEPT;
0688 
0689    //! @copydoc ::boost::intrusive::avltree::rend()const
0690    const_reverse_iterator rend() const BOOST_NOEXCEPT;
0691 
0692    //! @copydoc ::boost::intrusive::avltree::crend()const
0693    const_reverse_iterator crend() const BOOST_NOEXCEPT;
0694 
0695    //! @copydoc ::boost::intrusive::avltree::root()
0696    iterator root() BOOST_NOEXCEPT;
0697 
0698    //! @copydoc ::boost::intrusive::avltree::root()const
0699    const_iterator root() const BOOST_NOEXCEPT;
0700 
0701    //! @copydoc ::boost::intrusive::avltree::croot()const
0702    const_iterator croot() const BOOST_NOEXCEPT;
0703 
0704    //! @copydoc ::boost::intrusive::avltree::container_from_end_iterator(iterator)
0705    static avl_multiset_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
0706 
0707    //! @copydoc ::boost::intrusive::avltree::container_from_end_iterator(const_iterator)
0708    static const avl_multiset_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
0709 
0710    //! @copydoc ::boost::intrusive::avltree::container_from_iterator(iterator)
0711    static avl_multiset_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
0712 
0713    //! @copydoc ::boost::intrusive::avltree::container_from_iterator(const_iterator)
0714    static const avl_multiset_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
0715 
0716    //! @copydoc ::boost::intrusive::avltree::key_comp()const
0717    key_compare key_comp() const;
0718 
0719    //! @copydoc ::boost::intrusive::avltree::value_comp()const
0720    value_compare value_comp() const;
0721 
0722    //! @copydoc ::boost::intrusive::avltree::empty()const
0723    bool empty() const BOOST_NOEXCEPT;
0724 
0725    //! @copydoc ::boost::intrusive::avltree::size()const
0726    size_type size() const BOOST_NOEXCEPT;
0727 
0728    //! @copydoc ::boost::intrusive::avltree::swap
0729    void swap(avl_multiset_impl& other);
0730 
0731    //! @copydoc ::boost::intrusive::avltree::clone_from(const avltree&,Cloner,Disposer)
0732    template <class Cloner, class Disposer>
0733    void clone_from(const avl_multiset_impl &src, Cloner cloner, Disposer disposer);
0734 
0735    #else
0736 
0737    using tree_type::clone_from;
0738 
0739    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0740 
0741    //! @copydoc ::boost::intrusive::avltree::clone_from(avltree&&,Cloner,Disposer)
0742    template <class Cloner, class Disposer>
0743    void clone_from(BOOST_RV_REF(avl_multiset_impl) src, Cloner cloner, Disposer disposer)
0744    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
0745 
0746    //! @copydoc ::boost::intrusive::avltree::insert_equal(reference)
0747    iterator insert(reference value)
0748    {  return tree_type::insert_equal(value);  }
0749 
0750    //! @copydoc ::boost::intrusive::avltree::insert_equal(const_iterator,reference)
0751    iterator insert(const_iterator hint, reference value)
0752    {  return tree_type::insert_equal(hint, value);  }
0753 
0754    //! @copydoc ::boost::intrusive::avltree::insert_equal(Iterator,Iterator)
0755    template<class Iterator>
0756    void insert(Iterator b, Iterator e)
0757    {  tree_type::insert_equal(b, e);  }
0758 
0759    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0760    //! @copydoc ::boost::intrusive::avltree::insert_before
0761    iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
0762 
0763    //! @copydoc ::boost::intrusive::avltree::push_back
0764    void push_back(reference value) BOOST_NOEXCEPT;
0765 
0766    //! @copydoc ::boost::intrusive::avltree::push_front
0767    void push_front(reference value) BOOST_NOEXCEPT;
0768 
0769    //! @copydoc ::boost::intrusive::avltree::erase(const_iterator)
0770    iterator erase(const_iterator i) BOOST_NOEXCEPT;
0771 
0772    //! @copydoc ::boost::intrusive::avltree::erase(const_iterator,const_iterator)
0773    iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
0774 
0775    //! @copydoc ::boost::intrusive::avltree::erase(const key_type &)
0776    size_type erase(const key_type &key);
0777 
0778    //! @copydoc ::boost::intrusive::avltree::erase(const KeyType&,KeyTypeKeyCompare)
0779    template<class KeyType, class KeyTypeKeyCompare>
0780    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
0781 
0782    //! @copydoc ::boost::intrusive::avltree::erase_and_dispose(const_iterator,Disposer)
0783    template<class Disposer>
0784    iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
0785 
0786    //! @copydoc ::boost::intrusive::avltree::erase_and_dispose(const_iterator,const_iterator,Disposer)
0787    template<class Disposer>
0788    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
0789 
0790    //! @copydoc ::boost::intrusive::avltree::erase_and_dispose(const key_type &, Disposer)
0791    template<class Disposer>
0792    size_type erase_and_dispose(const key_type &key, Disposer disposer);
0793 
0794    //! @copydoc ::boost::intrusive::avltree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
0795    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
0796    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
0797 
0798    //! @copydoc ::boost::intrusive::avltree::clear
0799    void clear() BOOST_NOEXCEPT;
0800 
0801    //! @copydoc ::boost::intrusive::avltree::clear_and_dispose
0802    template<class Disposer>
0803    void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
0804 
0805    //! @copydoc ::boost::intrusive::avltree::count(const key_type &)const
0806    size_type count(const key_type &key) const;
0807 
0808    //! @copydoc ::boost::intrusive::avltree::count(const KeyType&,KeyTypeKeyCompare)const
0809    template<class KeyType, class KeyTypeKeyCompare>
0810    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
0811 
0812    //! @copydoc ::boost::intrusive::avltree::lower_bound(const key_type &)
0813    iterator lower_bound(const key_type &key);
0814 
0815    //! @copydoc ::boost::intrusive::avltree::lower_bound(const KeyType&,KeyTypeKeyCompare)
0816    template<class KeyType, class KeyTypeKeyCompare>
0817    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
0818 
0819    //! @copydoc ::boost::intrusive::avltree::lower_bound(const key_type &)const
0820    const_iterator lower_bound(const key_type &key) const;
0821 
0822    //! @copydoc ::boost::intrusive::avltree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
0823    template<class KeyType, class KeyTypeKeyCompare>
0824    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0825 
0826    //! @copydoc ::boost::intrusive::avltree::upper_bound(const key_type &)
0827    iterator upper_bound(const key_type &key);
0828 
0829    //! @copydoc ::boost::intrusive::avltree::upper_bound(const KeyType&,KeyTypeKeyCompare)
0830    template<class KeyType, class KeyTypeKeyCompare>
0831    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
0832 
0833    //! @copydoc ::boost::intrusive::avltree::upper_bound(const key_type &)const
0834    const_iterator upper_bound(const key_type &key) const;
0835 
0836    //! @copydoc ::boost::intrusive::avltree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
0837    template<class KeyType, class KeyTypeKeyCompare>
0838    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0839 
0840    //! @copydoc ::boost::intrusive::avltree::find(const key_type &)
0841    iterator find(const key_type &key);
0842 
0843    //! @copydoc ::boost::intrusive::avltree::find(const KeyType&,KeyTypeKeyCompare)
0844    template<class KeyType, class KeyTypeKeyCompare>
0845    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
0846 
0847    //! @copydoc ::boost::intrusive::avltree::find(const key_type &)const
0848    const_iterator find(const key_type &key) const;
0849 
0850    //! @copydoc ::boost::intrusive::avltree::find(const KeyType&,KeyTypeKeyCompare)const
0851    template<class KeyType, class KeyTypeKeyCompare>
0852    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
0853 
0854    //! @copydoc ::boost::intrusive::avltree::equal_range(const key_type &)
0855    std::pair<iterator,iterator> equal_range(const key_type &key);
0856 
0857    //! @copydoc ::boost::intrusive::avltree::equal_range(const KeyType&,KeyTypeKeyCompare)
0858    template<class KeyType, class KeyTypeKeyCompare>
0859    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
0860 
0861    //! @copydoc ::boost::intrusive::avltree::equal_range(const key_type &)const
0862    std::pair<const_iterator, const_iterator>
0863       equal_range(const key_type &key) const;
0864 
0865    //! @copydoc ::boost::intrusive::avltree::equal_range(const KeyType&,KeyTypeKeyCompare)const
0866    template<class KeyType, class KeyTypeKeyCompare>
0867    std::pair<const_iterator, const_iterator>
0868       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
0869 
0870    //! @copydoc ::boost::intrusive::avltree::bounded_range(const key_type &,const key_type &,bool,bool)
0871    std::pair<iterator,iterator> bounded_range
0872       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
0873 
0874    //! @copydoc ::boost::intrusive::avltree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
0875    template<class KeyType, class KeyTypeKeyCompare>
0876    std::pair<iterator,iterator> bounded_range
0877       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
0878 
0879    //! @copydoc ::boost::intrusive::avltree::bounded_range(const key_type &,const key_type &,bool,bool)const
0880    std::pair<const_iterator, const_iterator>
0881       bounded_range(const key_type &lower_key, const key_type &key upper_key, bool left_closed, bool right_closed) const;
0882 
0883    //! @copydoc ::boost::intrusive::avltree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
0884    template<class KeyType, class KeyTypeKeyCompare>
0885    std::pair<const_iterator, const_iterator> bounded_range
0886          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
0887 
0888    //! @copydoc ::boost::intrusive::avltree::s_iterator_to(reference)
0889    static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
0890 
0891    //! @copydoc ::boost::intrusive::avltree::s_iterator_to(const_reference)
0892    static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
0893 
0894    //! @copydoc ::boost::intrusive::avltree::iterator_to(reference)
0895    iterator iterator_to(reference value) BOOST_NOEXCEPT;
0896 
0897    //! @copydoc ::boost::intrusive::avltree::iterator_to(const_reference)const
0898    const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
0899 
0900    //! @copydoc ::boost::intrusive::avltree::init_node(reference)
0901    static void init_node(reference value) BOOST_NOEXCEPT;
0902 
0903    //! @copydoc ::boost::intrusive::avltree::unlink_leftmost_without_rebalance
0904    pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
0905 
0906    //! @copydoc ::boost::intrusive::avltree::replace_node
0907    void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
0908 
0909    //! @copydoc ::boost::intrusive::avltree::remove_node
0910    void remove_node(reference value) BOOST_NOEXCEPT;
0911 
0912    //! @copydoc ::boost::intrusive::avltree::merge_equal
0913    template<class ...Options2>
0914    void merge(avl_multiset<T, Options2...> &source);
0915 
0916    //! @copydoc ::boost::intrusive::avltree::merge_equal
0917    template<class ...Options2>
0918    void merge(avl_set<T, Options2...> &source);
0919 
0920    #else
0921 
0922    template<class Compare2>
0923    void merge(avl_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
0924    {  return tree_type::merge_equal(source);  }
0925 
0926    template<class Compare2>
0927    void merge(avl_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
0928    {  return tree_type::merge_equal(source);  }
0929 
0930    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0931 };
0932 
0933 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0934 
0935 template<class T, class ...Options>
0936 bool operator!= (const avl_multiset_impl<T, Options...> &x, const avl_multiset_impl<T, Options...> &y);
0937 
0938 template<class T, class ...Options>
0939 bool operator>(const avl_multiset_impl<T, Options...> &x, const avl_multiset_impl<T, Options...> &y);
0940 
0941 template<class T, class ...Options>
0942 bool operator<=(const avl_multiset_impl<T, Options...> &x, const avl_multiset_impl<T, Options...> &y);
0943 
0944 template<class T, class ...Options>
0945 bool operator>=(const avl_multiset_impl<T, Options...> &x, const avl_multiset_impl<T, Options...> &y);
0946 
0947 template<class T, class ...Options>
0948 void swap(avl_multiset_impl<T, Options...> &x, avl_multiset_impl<T, Options...> &y);
0949 
0950 #endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0951 
0952 //! Helper metafunction to define a \c avl_multiset that yields to the same type when the
0953 //! same options (either explicitly or implicitly) are used.
0954 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0955 template<class T, class ...Options>
0956 #else
0957 template<class T, class O1 = void, class O2 = void
0958                 , class O3 = void, class O4 = void
0959                 , class O5 = void, class O6 = void>
0960 #endif
0961 struct make_avl_multiset
0962 {
0963    /// @cond
0964    typedef typename pack_options
0965       < avltree_defaults,
0966       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0967       O1, O2, O3, O4, O5, O6
0968       #else
0969       Options...
0970       #endif
0971       >::type packed_options;
0972 
0973    typedef typename detail::get_value_traits
0974       <T, typename packed_options::proto_value_traits>::type value_traits;
0975 
0976    typedef avl_multiset_impl
0977          < value_traits
0978          , typename packed_options::key_of_value
0979          , typename packed_options::compare
0980          , typename packed_options::size_type
0981          , packed_options::constant_time_size
0982          , typename packed_options::header_holder_type
0983          > implementation_defined;
0984    /// @endcond
0985    typedef implementation_defined type;
0986 };
0987 
0988 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0989 
0990 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0991 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
0992 #else
0993 template<class T, class ...Options>
0994 #endif
0995 class avl_multiset
0996    :  public make_avl_multiset<T,
0997       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0998       O1, O2, O3, O4, O5, O6
0999       #else
1000       Options...
1001       #endif
1002       >::type
1003 {
1004    typedef typename make_avl_multiset<T,
1005       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1006       O1, O2, O3, O4, O5, O6
1007       #else
1008       Options...
1009       #endif
1010       >::type   Base;
1011 
1012    BOOST_MOVABLE_BUT_NOT_COPYABLE(avl_multiset)
1013 
1014    public:
1015    typedef typename Base::key_compare        key_compare;
1016    typedef typename Base::value_traits       value_traits;
1017    typedef typename Base::iterator           iterator;
1018    typedef typename Base::const_iterator     const_iterator;
1019 
1020    //Assert if passed value traits are compatible with the type
1021    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1022 
1023    BOOST_INTRUSIVE_FORCEINLINE avl_multiset()
1024       :  Base()
1025    {}
1026 
1027    BOOST_INTRUSIVE_FORCEINLINE explicit avl_multiset( const key_compare &cmp, const value_traits &v_traits = value_traits())
1028       :  Base(cmp, v_traits)
1029    {}
1030 
1031    template<class Iterator>
1032    BOOST_INTRUSIVE_FORCEINLINE avl_multiset( Iterator b, Iterator e
1033            , const key_compare &cmp = key_compare()
1034            , const value_traits &v_traits = value_traits())
1035       :  Base(b, e, cmp, v_traits)
1036    {}
1037 
1038    BOOST_INTRUSIVE_FORCEINLINE avl_multiset(BOOST_RV_REF(avl_multiset) x)
1039       :  Base(BOOST_MOVE_BASE(Base, x))
1040    {}
1041 
1042    BOOST_INTRUSIVE_FORCEINLINE avl_multiset& operator=(BOOST_RV_REF(avl_multiset) x)
1043    {  return static_cast<avl_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
1044 
1045    template <class Cloner, class Disposer>
1046    BOOST_INTRUSIVE_FORCEINLINE void clone_from(const avl_multiset &src, Cloner cloner, Disposer disposer)
1047    {  Base::clone_from(src, cloner, disposer);  }
1048 
1049    template <class Cloner, class Disposer>
1050    BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(avl_multiset) src, Cloner cloner, Disposer disposer)
1051    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
1052 
1053    BOOST_INTRUSIVE_FORCEINLINE static avl_multiset &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
1054    {  return static_cast<avl_multiset &>(Base::container_from_end_iterator(end_iterator));   }
1055 
1056    BOOST_INTRUSIVE_FORCEINLINE static const avl_multiset &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
1057    {  return static_cast<const avl_multiset &>(Base::container_from_end_iterator(end_iterator));   }
1058 
1059    BOOST_INTRUSIVE_FORCEINLINE static avl_multiset &container_from_iterator(iterator it) BOOST_NOEXCEPT
1060    {  return static_cast<avl_multiset &>(Base::container_from_iterator(it));   }
1061 
1062    BOOST_INTRUSIVE_FORCEINLINE static const avl_multiset &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
1063    {  return static_cast<const avl_multiset &>(Base::container_from_iterator(it));   }
1064 };
1065 
1066 #endif
1067 
1068 } //namespace intrusive
1069 } //namespace boost
1070 
1071 #include <boost/intrusive/detail/config_end.hpp>
1072 
1073 #endif //BOOST_INTRUSIVE_AVL_SET_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!