Back to home page

EIC code displayed by LXR
 
 

    

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

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