Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-07-11 08:14:08 

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