ceph/src/boost/boost/intrusive/sgtree.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2007-2014
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 //
  13 // The option that yields to non-floating point 1/sqrt(2) alpha is taken
  14 // from the scapegoat tree implementation of the PSPP library.
  15 //
  16 /////////////////////////////////////////////////////////////////////////////
  17
  18 #ifndef BOOST_INTRUSIVE_SGTREE_HPP
  19 #define BOOST_INTRUSIVE_SGTREE_HPP
  20
  21 #include <boost/intrusive/detail/config_begin.hpp>
  22 #include <boost/intrusive/intrusive_fwd.hpp>
  23 #include <boost/intrusive/detail/assert.hpp>
  24 #include <boost/static_assert.hpp>
  25 #include <boost/intrusive/bs_set_hook.hpp>
  26 #include <boost/intrusive/bstree.hpp>
  27 #include <boost/intrusive/detail/tree_node.hpp>
  28 #include <boost/intrusive/pointer_traits.hpp>
  29 #include <boost/intrusive/detail/mpl.hpp>
  30 #include <boost/intrusive/detail/math.hpp>
  31 #include <boost/intrusive/detail/get_value_traits.hpp>
  32 #include <boost/intrusive/sgtree_algorithms.hpp>
  33 #include <boost/intrusive/detail/key_nodeptr_comp.hpp>
  34 #include <boost/intrusive/link_mode.hpp>
  35
  36 #include <boost/move/utility_core.hpp>
  37 #include <boost/move/adl_move_swap.hpp>
  38
  39 #include <cstddef>
  40 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>
  41 #include <boost/intrusive/detail/minimal_pair_header.hpp>   //std::pair
  42 #include <cmath>
  43 #include <cstddef>
  44
  45 #if defined(BOOST_HAS_PRAGMA_ONCE)
  46 #  pragma once
  47 #endif
  48
  49 namespace boost {
  50 namespace intrusive {
  51
  52 /// @cond
  53
  54 namespace detail{
  55
  56 /////////////////////////////////////////////////////////////
  57 //
  58 //       Halpha for fixed floating_point<false> option
  59 //
  60 /////////////////////////////////////////////////////////////
  61
  62 //! Returns floor(log2(n)/log2(sqrt(2))) -> floor(2*log2(n))
  63 //! Undefined if N is 0.
  64 //!
  65 //! This function does not use float point operations.
  66 inline std::size_t calculate_h_sqrt2 (std::size_t n)
  67 {
  68    std::size_t f_log2 = detail::floor_log2(n);
  69    return (2*f_log2) + static_cast<std::size_t>(n >= detail::sqrt2_pow_2xplus1(f_log2));
  70 }
  71
  72 struct h_alpha_sqrt2_t
  73 {
  74    h_alpha_sqrt2_t(void){}
  75    std::size_t operator()(std::size_t n) const
  76    {  return calculate_h_sqrt2(n);  }
  77 };
  78
  79 struct alpha_0_75_by_max_size_t
  80 {
  81    alpha_0_75_by_max_size_t(void){}
  82
  83    std::size_t operator()(std::size_t max_tree_size) const
  84    {
  85       const std::size_t max_tree_size_limit = ((~std::size_t(0))/std::size_t(3));
  86       return max_tree_size > max_tree_size_limit ? max_tree_size/4*3 : max_tree_size*3/4;
  87    }
  88 };
  89
  90 /////////////////////////////////////////////////////////////
  91 //
  92 //       Halpha for fixed floating_point<true> option
  93 //
  94 /////////////////////////////////////////////////////////////
  95
  96 struct h_alpha_t
  97 {
  98    explicit h_alpha_t(float inv_minus_logalpha)
  99       :  inv_minus_logalpha_(inv_minus_logalpha)
 100    {}
 101
 102    std::size_t operator()(std::size_t n) const
 103    {
 104       ////////////////////////////////////////////////////////////
 105       // This function must return "floor(log2(1/alpha(n)))" ->
 106       //    floor(log2(n)/log(1/alpha)) ->
 107       //    floor(log2(n)/-log2(alpha))
 108       //    floor(log2(n)*(1/-log2(alpha)))
 109       ////////////////////////////////////////////////////////////
 110       return static_cast<std::size_t>(detail::fast_log2(float(n))*inv_minus_logalpha_);
 111    }
 112
 113    private:
 114    //Since the function will be repeatedly called
 115    //precalculate constant data to avoid repeated
 116    //calls to log and division.
 117    //This will store 1/(-std::log2(alpha_))
 118    float inv_minus_logalpha_;
 119 };
 120
 121 struct alpha_by_max_size_t
 122 {
 123    explicit alpha_by_max_size_t(float alpha)
 124       :  alpha_(alpha)
 125    {}
 126
 127    float operator()(std::size_t max_tree_size) const
 128    {  return float(max_tree_size)*alpha_;   }
 129
 130    private:
 131    float alpha_;
 132 };
 133
 134 template<bool Activate, class SizeType>
 135 struct alpha_holder
 136 {
 137    typedef boost::intrusive::detail::h_alpha_t           h_alpha_t;
 138    typedef boost::intrusive::detail::alpha_by_max_size_t multiply_by_alpha_t;
 139
 140    alpha_holder()
 141       : max_tree_size_()
 142    {  set_alpha(0.70711f);   } // ~1/sqrt(2)
 143
 144    float get_alpha() const
 145    {  return alpha_;  }
 146
 147    void set_alpha(float alpha)
 148    {
 149       alpha_ = alpha;
 150       inv_minus_logalpha_ = 1/(-detail::fast_log2(alpha));
 151    }
 152
 153    h_alpha_t get_h_alpha_t() const
 154    {  return h_alpha_t(inv_minus_logalpha_);  }
 155
 156    multiply_by_alpha_t get_multiply_by_alpha_t() const
 157    {  return multiply_by_alpha_t(alpha_);  }
 158
 159    SizeType &get_max_tree_size()
 160    {  return max_tree_size_;  }
 161
 162    protected:
 163    float alpha_;
 164    float inv_minus_logalpha_;
 165    SizeType max_tree_size_;
 166 };
 167
 168 template<class SizeType>
 169 struct alpha_holder<false, SizeType>
 170 {
 171    //This specialization uses alpha = 1/sqrt(2)
 172    //without using floating point operations
 173    //Downside: alpha CAN't be changed.
 174    typedef boost::intrusive::detail::h_alpha_sqrt2_t           h_alpha_t;
 175    typedef boost::intrusive::detail::alpha_0_75_by_max_size_t  multiply_by_alpha_t;
 176
 177    alpha_holder()
 178       : max_tree_size_()
 179    {}
 180
 181    float get_alpha() const
 182    {  return 0.70710677f;  }
 183
 184    void set_alpha(float)
 185    {  //alpha CAN't be changed.
 186       BOOST_INTRUSIVE_INVARIANT_ASSERT(0);
 187    }
 188
 189    h_alpha_t get_h_alpha_t() const
 190    {  return h_alpha_t();  }
 191
 192    multiply_by_alpha_t get_multiply_by_alpha_t() const
 193    {  return multiply_by_alpha_t();  }
 194
 195    SizeType &get_max_tree_size()
 196    {  return max_tree_size_;  }
 197
 198    protected:
 199    SizeType max_tree_size_;
 200 };
 201
 202 }  //namespace detail{
 203
 204 struct sgtree_defaults
 205    : bstree_defaults
 206 {
 207    static const bool floating_point = true;
 208 };
 209
 210 /// @endcond
 211
 212 //! The class template sgtree is an intrusive scapegoat tree container, that
 213 //! is used to construct intrusive sg_set and sg_multiset containers.
 214 //! The no-throw guarantee holds only, if the value_compare object
 215 //! doesn't throw.
 216 //!
 217 //! The template parameter \c T is the type to be managed by the container.
 218 //! The user can specify additional options and if no options are provided
 219 //! default options are used.
 220 //!
 221 //! The container supports the following options:
 222 //! \c base_hook<>/member_hook<>/value_traits<>,
 223 //! \c floating_point<>, \c size_type<> and
 224 //! \c compare<>.
 225 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 226 template<class T, class ...Options>
 227 #else
 228 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool FloatingPoint, typename HeaderHolder>
 229 #endif
 230 class sgtree_impl
 231    /// @cond
 232    :  public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, true, SgTreeAlgorithms, HeaderHolder>
 233    ,  public detail::alpha_holder<FloatingPoint, SizeType>
 234    /// @endcond
 235 {
 236    public:
 237    typedef ValueTraits                                               value_traits;
 238    /// @cond
 239    typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
 240                       , true, SgTreeAlgorithms, HeaderHolder>        tree_type;
 241    typedef tree_type                                                 implementation_defined;
 242
 243    /// @endcond
 244
 245    typedef typename implementation_defined::pointer                  pointer;
 246    typedef typename implementation_defined::const_pointer            const_pointer;
 247    typedef typename implementation_defined::value_type               value_type;
 248    typedef typename implementation_defined::key_type                 key_type;
 249    typedef typename implementation_defined::key_of_value             key_of_value;
 250    typedef typename implementation_defined::reference                reference;
 251    typedef typename implementation_defined::const_reference          const_reference;
 252    typedef typename implementation_defined::difference_type          difference_type;
 253    typedef typename implementation_defined::size_type                size_type;
 254    typedef typename implementation_defined::value_compare            value_compare;
 255    typedef typename implementation_defined::key_compare              key_compare;
 256    typedef typename implementation_defined::iterator                 iterator;
 257    typedef typename implementation_defined::const_iterator           const_iterator;
 258    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
 259    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
 260    typedef typename implementation_defined::node_traits              node_traits;
 261    typedef typename implementation_defined::node                     node;
 262    typedef typename implementation_defined::node_ptr                 node_ptr;
 263    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
 264    typedef BOOST_INTRUSIVE_IMPDEF(sgtree_algorithms<node_traits>)    node_algorithms;
 265
 266    static const bool constant_time_size      = implementation_defined::constant_time_size;
 267    static const bool floating_point          = FloatingPoint;
 268    static const bool stateful_value_traits   = implementation_defined::stateful_value_traits;
 269
 270    /// @cond
 271    private:
 272
 273    //noncopyable
 274    typedef detail::alpha_holder<FloatingPoint, SizeType>    alpha_traits;
 275    typedef typename alpha_traits::h_alpha_t                 h_alpha_t;
 276    typedef typename alpha_traits::multiply_by_alpha_t       multiply_by_alpha_t;
 277
 278    BOOST_MOVABLE_BUT_NOT_COPYABLE(sgtree_impl)
 279    BOOST_STATIC_ASSERT(((int)value_traits::link_mode != (int)auto_unlink));
 280
 281    enum { safemode_or_autounlink  =
 282             (int)value_traits::link_mode == (int)auto_unlink   ||
 283             (int)value_traits::link_mode == (int)safe_link     };
 284
 285    /// @endcond
 286
 287    public:
 288
 289    typedef BOOST_INTRUSIVE_IMPDEF(typename node_algorithms::insert_commit_data) insert_commit_data;
 290
 291    //! @copydoc ::boost::intrusive::bstree::bstree()
 292    sgtree_impl()
 293       :  tree_type()
 294    {}
 295
 296    //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &)
 297    explicit sgtree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
 298       :  tree_type(cmp, v_traits)
 299    {}
 300
 301    //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
 302    template<class Iterator>
 303    sgtree_impl( bool unique, Iterator b, Iterator e
 304               , const key_compare &cmp     = key_compare()
 305               , const value_traits &v_traits = value_traits())
 306       : tree_type(cmp, v_traits)
 307    {
 308       if(unique)
 309          this->insert_unique(b, e);
 310       else
 311          this->insert_equal(b, e);
 312    }
 313
 314    //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
 315    sgtree_impl(BOOST_RV_REF(sgtree_impl) x)
 316       :  tree_type(BOOST_MOVE_BASE(tree_type, x)), alpha_traits(x.get_alpha_traits())
 317    {  ::boost::adl_move_swap(this->get_alpha_traits(), x.get_alpha_traits());   }
 318
 319    //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
 320    sgtree_impl& operator=(BOOST_RV_REF(sgtree_impl) x)
 321    {
 322       this->get_alpha_traits() = x.get_alpha_traits();
 323       return static_cast<sgtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));
 324    }
 325
 326    /// @cond
 327    private:
 328
 329    const alpha_traits &get_alpha_traits() const
 330    {  return *this;  }
 331
 332    alpha_traits &get_alpha_traits()
 333    {  return *this;  }
 334
 335    h_alpha_t get_h_alpha_func() const
 336    {  return this->get_alpha_traits().get_h_alpha_t();  }
 337
 338    multiply_by_alpha_t get_alpha_by_max_size_func() const
 339    {  return this->get_alpha_traits().get_multiply_by_alpha_t(); }
 340
 341    /// @endcond
 342
 343    public:
 344
 345    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 346    //! @copydoc ::boost::intrusive::bstree::~bstree()
 347    ~sgtree_impl();
 348
 349    //! @copydoc ::boost::intrusive::bstree::begin()
 350    iterator begin();
 351
 352    //! @copydoc ::boost::intrusive::bstree::begin()const
 353    const_iterator begin() const;
 354
 355    //! @copydoc ::boost::intrusive::bstree::cbegin()const
 356    const_iterator cbegin() const;
 357
 358    //! @copydoc ::boost::intrusive::bstree::end()
 359    iterator end();
 360
 361    //! @copydoc ::boost::intrusive::bstree::end()const
 362    const_iterator end() const;
 363
 364    //! @copydoc ::boost::intrusive::bstree::cend()const
 365    const_iterator cend() const;
 366
 367    //! @copydoc ::boost::intrusive::bstree::rbegin()
 368    reverse_iterator rbegin();
 369
 370    //! @copydoc ::boost::intrusive::bstree::rbegin()const
 371    const_reverse_iterator rbegin() const;
 372
 373    //! @copydoc ::boost::intrusive::bstree::crbegin()const
 374    const_reverse_iterator crbegin() const;
 375
 376    //! @copydoc ::boost::intrusive::bstree::rend()
 377    reverse_iterator rend();
 378
 379    //! @copydoc ::boost::intrusive::bstree::rend()const
 380    const_reverse_iterator rend() const;
 381
 382    //! @copydoc ::boost::intrusive::bstree::crend()const
 383    const_reverse_iterator crend() const;
 384
 385    //! @copydoc ::boost::intrusive::bstree::root()
 386    iterator root();
 387
 388    //! @copydoc ::boost::intrusive::bstree::root()const
 389    const_iterator root() const;
 390
 391    //! @copydoc ::boost::intrusive::bstree::croot()const
 392    const_iterator croot() const;
 393
 394    //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
 395    static sgtree_impl &container_from_end_iterator(iterator end_iterator);
 396
 397    //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
 398    static const sgtree_impl &container_from_end_iterator(const_iterator end_iterator);
 399
 400    //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
 401    static sgtree_impl &container_from_iterator(iterator it);
 402
 403    //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
 404    static const sgtree_impl &container_from_iterator(const_iterator it);
 405
 406    //! @copydoc ::boost::intrusive::bstree::key_comp()const
 407    key_compare key_comp() const;
 408
 409    //! @copydoc ::boost::intrusive::bstree::value_comp()const
 410    value_compare value_comp() const;
 411
 412    //! @copydoc ::boost::intrusive::bstree::empty()const
 413    bool empty() const;
 414
 415    //! @copydoc ::boost::intrusive::bstree::size()const
 416    size_type size() const;
 417
 418    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 419
 420    //! @copydoc ::boost::intrusive::bstree::swap
 421    void swap(sgtree_impl& other)
 422    {
 423       //This can throw
 424       this->tree_type::swap(static_cast<tree_type&>(other));
 425       ::boost::adl_move_swap(this->get_alpha_traits(), other.get_alpha_traits());
 426    }
 427
 428    //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer)
 429    //! Additional notes: it also copies the alpha factor from the source container.
 430    template <class Cloner, class Disposer>
 431    void clone_from(const sgtree_impl &src, Cloner cloner, Disposer disposer)
 432    {
 433       tree_type::clone_from(src, cloner, disposer);
 434       this->get_alpha_traits() = src.get_alpha_traits();
 435    }
 436
 437    //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer)
 438    //! Additional notes: it also copies the alpha factor from the source container.
 439    template <class Cloner, class Disposer>
 440    void clone_from(BOOST_RV_REF(sgtree_impl) src, Cloner cloner, Disposer disposer)
 441    {
 442       tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);
 443       this->get_alpha_traits() = ::boost::move(src.get_alpha_traits());
 444    }
 445
 446    //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
 447    iterator insert_equal(reference value)
 448    {
 449       node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
 450       if(safemode_or_autounlink)
 451          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
 452       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
 453       node_ptr p = node_algorithms::insert_equal_upper_bound
 454          (this->tree_type::header_ptr(), to_insert, this->key_node_comp(this->key_comp())
 455          , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
 456       this->tree_type::sz_traits().increment();
 457       this->max_tree_size_ = (size_type)max_tree_size;
 458       return iterator(p, this->priv_value_traits_ptr());
 459    }
 460
 461    //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
 462    iterator insert_equal(const_iterator hint, reference value)
 463    {
 464       node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
 465       if(safemode_or_autounlink)
 466          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
 467       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
 468       node_ptr p = node_algorithms::insert_equal
 469          ( this->tree_type::header_ptr(), hint.pointed_node(), to_insert, this->key_node_comp(this->key_comp())
 470          , (std::size_t)this->size(), this->get_h_alpha_func(), max_tree_size);
 471       this->tree_type::sz_traits().increment();
 472       this->max_tree_size_ = (size_type)max_tree_size;
 473       return iterator(p, this->priv_value_traits_ptr());
 474    }
 475
 476    //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
 477    template<class Iterator>
 478    void insert_equal(Iterator b, Iterator e)
 479    {
 480       iterator iend(this->end());
 481       for (; b != e; ++b)
 482          this->insert_equal(iend, *b);
 483    }
 484
 485    //! @copydoc ::boost::intrusive::bstree::insert_unique(reference)
 486    std::pair<iterator, bool> insert_unique(reference value)
 487    {
 488       insert_commit_data commit_data;
 489       std::pair<iterator, bool> ret = this->insert_unique_check
 490          (key_of_value()(value), this->key_comp(), commit_data);
 491       if(!ret.second)
 492          return ret;
 493       return std::pair<iterator, bool> (this->insert_unique_commit(value, commit_data), true);
 494    }
 495
 496    //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference)
 497    iterator insert_unique(const_iterator hint, reference value)
 498    {
 499       insert_commit_data commit_data;
 500       std::pair<iterator, bool> ret = this->insert_unique_check
 501          (hint, key_of_value()(value), this->key_comp(), commit_data);
 502       if(!ret.second)
 503          return ret.first;
 504       return this->insert_unique_commit(value, commit_data);
 505    }
 506
 507    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 508    template<class KeyType, class KeyTypeKeyCompare>
 509    BOOST_INTRUSIVE_DOC1ST(std::pair<iterator BOOST_INTRUSIVE_I bool>
 510       , typename detail::disable_if_convertible
 511          <KeyType BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I
 512          std::pair<iterator BOOST_INTRUSIVE_I bool> >::type)
 513       insert_unique_check
 514       (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data)
 515    {
 516       std::pair<node_ptr, bool> ret =
 517          node_algorithms::insert_unique_check
 518             (this->tree_type::header_ptr(), key, this->key_node_comp(comp), commit_data);
 519       return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
 520    }
 521
 522    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 523    template<class KeyType, class KeyTypeKeyCompare>
 524    std::pair<iterator, bool> insert_unique_check
 525       (const_iterator hint, const KeyType &key
 526       ,KeyTypeKeyCompare comp, insert_commit_data &commit_data)
 527    {
 528       std::pair<node_ptr, bool> ret =
 529          node_algorithms::insert_unique_check
 530             (this->tree_type::header_ptr(), hint.pointed_node(), key, this->key_node_comp(comp), commit_data);
 531       return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
 532    }
 533
 534    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&)
 535    std::pair<iterator, bool> insert_unique_check
 536       (const key_type &key, insert_commit_data &commit_data)
 537    {  return this->insert_unique_check(key, this->key_comp(), commit_data);   }
 538
 539    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
 540    std::pair<iterator, bool> insert_unique_check
 541       (const_iterator hint, const key_type &key, insert_commit_data &commit_data)
 542    {  return this->insert_unique_check(hint, key, this->key_comp(), commit_data);   }
 543
 544    //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
 545    iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
 546    {
 547       node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
 548       if(safemode_or_autounlink)
 549          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
 550       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
 551       node_algorithms::insert_unique_commit
 552          ( this->tree_type::header_ptr(), to_insert, commit_data
 553          , (std::size_t)this->size(), this->get_h_alpha_func(), max_tree_size);
 554       this->tree_type::sz_traits().increment();
 555       this->max_tree_size_ = (size_type)max_tree_size;
 556       return iterator(to_insert, this->priv_value_traits_ptr());
 557    }
 558
 559    //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
 560    template<class Iterator>
 561    void insert_unique(Iterator b, Iterator e)
 562    {
 563       if(this->empty()){
 564          iterator iend(this->end());
 565          for (; b != e; ++b)
 566             this->insert_unique(iend, *b);
 567       }
 568       else{
 569          for (; b != e; ++b)
 570             this->insert_unique(*b);
 571       }
 572    }
 573
 574    //! @copydoc ::boost::intrusive::bstree::insert_before
 575    iterator insert_before(const_iterator pos, reference value)
 576    {
 577       node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
 578       if(safemode_or_autounlink)
 579          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
 580       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
 581       node_ptr p = node_algorithms::insert_before
 582          ( this->tree_type::header_ptr(), pos.pointed_node(), to_insert
 583          , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
 584       this->tree_type::sz_traits().increment();
 585       this->max_tree_size_ = (size_type)max_tree_size;
 586       return iterator(p, this->priv_value_traits_ptr());
 587    }
 588
 589    //! @copydoc ::boost::intrusive::bstree::push_back
 590    void push_back(reference value)
 591    {
 592       node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
 593       if(safemode_or_autounlink)
 594          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
 595       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
 596       node_algorithms::push_back
 597          ( this->tree_type::header_ptr(), to_insert
 598          , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
 599       this->tree_type::sz_traits().increment();
 600       this->max_tree_size_ = (size_type)max_tree_size;
 601    }
 602
 603    //! @copydoc ::boost::intrusive::bstree::push_front
 604    void push_front(reference value)
 605    {
 606       node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
 607       if(safemode_or_autounlink)
 608          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
 609       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
 610       node_algorithms::push_front
 611          ( this->tree_type::header_ptr(), to_insert
 612          , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
 613       this->tree_type::sz_traits().increment();
 614       this->max_tree_size_ = (size_type)max_tree_size;
 615    }
 616
 617
 618    //! @copydoc ::boost::intrusive::bstree::erase(const_iterator)
 619    iterator erase(const_iterator i)
 620    {
 621       const_iterator ret(i);
 622       ++ret;
 623       node_ptr to_erase(i.pointed_node());
 624       if(safemode_or_autounlink)
 625          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!node_algorithms::unique(to_erase));
 626       std::size_t max_tree_size = this->max_tree_size_;
 627       node_algorithms::erase
 628          ( this->tree_type::header_ptr(), to_erase, (std::size_t)this->size()
 629          , max_tree_size, this->get_alpha_by_max_size_func());
 630       this->max_tree_size_ = (size_type)max_tree_size;
 631       this->tree_type::sz_traits().decrement();
 632       if(safemode_or_autounlink)
 633          node_algorithms::init(to_erase);
 634       return ret.unconst();
 635    }
 636
 637    //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator)
 638    iterator erase(const_iterator b, const_iterator e)
 639    {  size_type n;   return private_erase(b, e, n);   }
 640
 641    //! @copydoc ::boost::intrusive::bstree::erase(const key_type &)
 642    size_type erase(const key_type &key)
 643    {  return this->erase(key, this->key_comp());   }
 644
 645    //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare)
 646    template<class KeyType, class KeyTypeKeyCompare>
 647    BOOST_INTRUSIVE_DOC1ST(size_type
 648       , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)
 649       erase(const KeyType& key, KeyTypeKeyCompare comp)
 650    {
 651       std::pair<iterator,iterator> p = this->equal_range(key, comp);
 652       size_type n;
 653       private_erase(p.first, p.second, n);
 654       return n;
 655    }
 656
 657    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer)
 658    template<class Disposer>
 659    iterator erase_and_dispose(const_iterator i, Disposer disposer)
 660    {
 661       node_ptr to_erase(i.pointed_node());
 662       iterator ret(this->erase(i));
 663       disposer(this->get_value_traits().to_value_ptr(to_erase));
 664       return ret;
 665    }
 666
 667    #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 668    template<class Disposer>
 669    iterator erase_and_dispose(iterator i, Disposer disposer)
 670    {  return this->erase_and_dispose(const_iterator(i), disposer);   }
 671    #endif
 672
 673    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer)
 674    template<class Disposer>
 675    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
 676    {  size_type n;   return private_erase(b, e, n, disposer);   }
 677
 678    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer)
 679    template<class Disposer>
 680    size_type erase_and_dispose(const key_type &key, Disposer disposer)
 681    {
 682       std::pair<iterator,iterator> p = this->equal_range(key);
 683       size_type n;
 684       private_erase(p.first, p.second, n, disposer);
 685       return n;
 686    }
 687
 688    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 689    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 690    BOOST_INTRUSIVE_DOC1ST(size_type
 691       , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)
 692       erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer)
 693    {
 694       std::pair<iterator,iterator> p = this->equal_range(key, comp);
 695       size_type n;
 696       private_erase(p.first, p.second, n, disposer);
 697       return n;
 698    }
 699
 700    //! @copydoc ::boost::intrusive::bstree::clear
 701    void clear()
 702    {
 703       tree_type::clear();
 704       this->max_tree_size_ = 0;
 705    }
 706
 707    //! @copydoc ::boost::intrusive::bstree::clear_and_dispose
 708    template<class Disposer>
 709    void clear_and_dispose(Disposer disposer)
 710    {
 711       tree_type::clear_and_dispose(disposer);
 712       this->max_tree_size_ = 0;
 713    }
 714
 715    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 716    //! @copydoc ::boost::intrusive::bstree::merge_unique
 717    template<class T, class ...Options2> void merge_unique(sgtree<T, Options2...> &);
 718    #else
 719    template<class Compare2>
 720    void merge_unique(sgtree_impl
 721       <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source)
 722    #endif
 723    {
 724       node_ptr it   (node_algorithms::begin_node(source.header_ptr()))
 725              , itend(node_algorithms::end_node  (source.header_ptr()));
 726
 727       while(it != itend){
 728          node_ptr const p(it);
 729          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p));
 730          it = node_algorithms::next_node(it);
 731
 732          std::size_t max_tree1_size = this->max_tree_size_;
 733          std::size_t max_tree2_size = source.get_max_tree_size();
 734          if( node_algorithms::transfer_unique
 735                ( this->header_ptr(), this->key_node_comp(this->key_comp()), this->size(), max_tree1_size
 736                , source.header_ptr(), p, source.size(), max_tree2_size
 737                , this->get_h_alpha_func(), this->get_alpha_by_max_size_func()) ){
 738             this->max_tree_size_  = (size_type)max_tree1_size;
 739             this->sz_traits().increment();
 740             source.get_max_tree_size() = (size_type)max_tree2_size;
 741             source.sz_traits().decrement();
 742          }
 743       }
 744    }
 745
 746    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 747    //! @copydoc ::boost::intrusive::bstree::merge_equal
 748    template<class T, class ...Options2> void merge_equal(sgtree<T, Options2...> &);
 749    #else
 750    template<class Compare2>
 751    void merge_equal(sgtree_impl
 752       <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source)
 753    #endif
 754    {
 755       node_ptr it   (node_algorithms::begin_node(source.header_ptr()))
 756              , itend(node_algorithms::end_node  (source.header_ptr()));
 757
 758       while(it != itend){
 759          node_ptr const p(it);
 760          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p));
 761          it = node_algorithms::next_node(it);
 762          std::size_t max_tree1_size = this->max_tree_size_;
 763          std::size_t max_tree2_size = source.get_max_tree_size();
 764          node_algorithms::transfer_equal
 765             ( this->header_ptr(), this->key_node_comp(this->key_comp()), this->size(), max_tree1_size
 766             , source.header_ptr(), p, source.size(), max_tree2_size
 767             , this->get_h_alpha_func(), this->get_alpha_by_max_size_func());
 768          this->max_tree_size_  = (size_type)max_tree1_size;
 769          this->sz_traits().increment();
 770          source.get_max_tree_size() = (size_type)max_tree2_size;
 771          source.sz_traits().decrement();
 772       }
 773    }
 774
 775    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 776    //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const
 777    size_type count(const key_type &key) const;
 778
 779    //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
 780    template<class KeyType, class KeyTypeKeyCompare>
 781    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
 782
 783    //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
 784    iterator lower_bound(const key_type &key);
 785
 786    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)
 787    template<class KeyType, class KeyTypeKeyCompare>
 788    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 789
 790    //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
 791    const_iterator lower_bound(const key_type &key) const;
 792
 793    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 794    template<class KeyType, class KeyTypeKeyCompare>
 795    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 796
 797    //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)
 798    iterator upper_bound(const key_type &key);
 799
 800    //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)
 801    template<class KeyType, class KeyTypeKeyCompare>
 802    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 803
 804    //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
 805    const_iterator upper_bound(const key_type &key) const;
 806
 807    //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 808    template<class KeyType, class KeyTypeKeyCompare>
 809    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 810
 811    //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
 812    iterator find(const key_type &key);
 813
 814    //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
 815    template<class KeyType, class KeyTypeKeyCompare>
 816    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 817
 818    //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
 819    const_iterator find(const key_type &key) const;
 820
 821    //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const
 822    template<class KeyType, class KeyTypeKeyCompare>
 823    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 824
 825    //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
 826    std::pair<iterator,iterator> equal_range(const key_type &key);
 827
 828    //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)
 829    template<class KeyType, class KeyTypeKeyCompare>
 830    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
 831
 832    //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const
 833    std::pair<const_iterator, const_iterator>
 834       equal_range(const key_type &key) const;
 835
 836    //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const
 837    template<class KeyType, class KeyTypeKeyCompare>
 838    std::pair<const_iterator, const_iterator>
 839       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
 840
 841    //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)
 842    std::pair<iterator,iterator> bounded_range
 843       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
 844
 845    //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 846    template<class KeyType, class KeyTypeKeyCompare>
 847    std::pair<iterator,iterator> bounded_range
 848       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 849
 850    //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const
 851    std::pair<const_iterator, const_iterator>
 852       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
 853
 854    //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 855    template<class KeyType, class KeyTypeKeyCompare>
 856    std::pair<const_iterator, const_iterator> bounded_range
 857          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 858
 859    //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
 860    static iterator s_iterator_to(reference value);
 861
 862    //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
 863    static const_iterator s_iterator_to(const_reference value);
 864
 865    //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
 866    iterator iterator_to(reference value);
 867
 868    //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
 869    const_iterator iterator_to(const_reference value) const;
 870
 871    //! @copydoc ::boost::intrusive::bstree::init_node(reference)
 872    static void init_node(reference value);
 873
 874    //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
 875    pointer unlink_leftmost_without_rebalance();
 876
 877    //! @copydoc ::boost::intrusive::bstree::replace_node
 878    void replace_node(iterator replace_this, reference with_this);
 879
 880    //! @copydoc ::boost::intrusive::bstree::remove_node
 881    void remove_node(reference value);
 882
 883    //! @copydoc ::boost::intrusive::bstree::rebalance
 884    void rebalance();
 885
 886    //! @copydoc ::boost::intrusive::bstree::rebalance_subtree
 887    iterator rebalance_subtree(iterator root);
 888
 889    friend bool operator< (const sgtree_impl &x, const sgtree_impl &y);
 890
 891    friend bool operator==(const sgtree_impl &x, const sgtree_impl &y);
 892
 893    friend bool operator!= (const sgtree_impl &x, const sgtree_impl &y);
 894
 895    friend bool operator>(const sgtree_impl &x, const sgtree_impl &y);
 896
 897    friend bool operator<=(const sgtree_impl &x, const sgtree_impl &y);
 898
 899    friend bool operator>=(const sgtree_impl &x, const sgtree_impl &y);
 900
 901    friend void swap(sgtree_impl &x, sgtree_impl &y);
 902
 903    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 904
 905    //! <b>Returns</b>: The balance factor (alpha) used in this tree
 906    //!
 907    //! <b>Throws</b>: Nothing.
 908    //!
 909    //! <b>Complexity</b>: Constant.
 910    float balance_factor() const
 911    {  return this->get_alpha_traits().get_alpha(); }
 912
 913    //! <b>Requires</b>: new_alpha must be a value between 0.5 and 1.0
 914    //!
 915    //! <b>Effects</b>: Establishes a new balance factor (alpha) and rebalances
 916    //!   the tree if the new balance factor is stricter (less) than the old factor.
 917    //!
 918    //! <b>Throws</b>: Nothing.
 919    //!
 920    //! <b>Complexity</b>: Linear to the elements in the subtree.
 921    void balance_factor(float new_alpha)
 922    {
 923       //The alpha factor CAN't be changed if the fixed, floating operation-less
 924       //1/sqrt(2) alpha factor option is activated
 925       BOOST_STATIC_ASSERT((floating_point));
 926       BOOST_INTRUSIVE_INVARIANT_ASSERT((new_alpha > 0.5f && new_alpha < 1.0f));
 927       if(new_alpha >= 0.5f && new_alpha < 1.0f){
 928          float old_alpha = this->get_alpha_traits().get_alpha();
 929          this->get_alpha_traits().set_alpha(new_alpha);
 930          if(new_alpha < old_alpha){
 931             this->max_tree_size_ = this->size();
 932             this->rebalance();
 933          }
 934       }
 935    }
 936
 937    /// @cond
 938    private:
 939    template<class Disposer>
 940    iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer)
 941    {
 942       for(n = 0; b != e; ++n)
 943         this->erase_and_dispose(b++, disposer);
 944       return b.unconst();
 945    }
 946
 947    iterator private_erase(const_iterator b, const_iterator e, size_type &n)
 948    {
 949       for(n = 0; b != e; ++n)
 950         this->erase(b++);
 951       return b.unconst();
 952    }
 953    /// @endcond
 954 };
 955
 956
 957 //! Helper metafunction to define a \c sgtree that yields to the same type when the
 958 //! same options (either explicitly or implicitly) are used.
 959 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 960 template<class T, class ...Options>
 961 #else
 962 template<class T, class O1 = void, class O2 = void
 963                 , class O3 = void, class O4 = void
 964                 , class O5 = void, class O6 = void>
 965 #endif
 966 struct make_sgtree
 967 {
 968    /// @cond
 969    typedef typename pack_options
 970       < sgtree_defaults,
 971       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 972       O1, O2, O3, O4, O5, O6
 973       #else
 974       Options...
 975       #endif
 976       >::type packed_options;
 977
 978    typedef typename detail::get_value_traits
 979       <T, typename packed_options::proto_value_traits>::type value_traits;
 980
 981    typedef sgtree_impl
 982          < value_traits
 983          , typename packed_options::key_of_value
 984          , typename packed_options::compare
 985          , typename packed_options::size_type
 986          , packed_options::floating_point
 987          , typename packed_options::header_holder_type
 988          > implementation_defined;
 989    /// @endcond
 990    typedef implementation_defined type;
 991 };
 992
 993
 994 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 995
 996 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 997 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
 998 #else
 999 template<class T, class ...Options>
1000 #endif
1001 class sgtree
1002    :  public make_sgtree<T,
1003       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1004       O1, O2, O3, O4, O5, O6
1005       #else
1006       Options...
1007       #endif
1008       >::type
1009 {
1010    typedef typename make_sgtree
1011       <T,
1012       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1013       O1, O2, O3, O4, O5, O6
1014       #else
1015       Options...
1016       #endif
1017       >::type   Base;
1018    BOOST_MOVABLE_BUT_NOT_COPYABLE(sgtree)
1019
1020    public:
1021    typedef typename Base::key_compare        key_compare;
1022    typedef typename Base::value_traits       value_traits;
1023    typedef typename Base::iterator           iterator;
1024    typedef typename Base::const_iterator     const_iterator;
1025    typedef typename Base::reverse_iterator           reverse_iterator;
1026    typedef typename Base::const_reverse_iterator     const_reverse_iterator;
1027
1028    //Assert if passed value traits are compatible with the type
1029    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1030
1031    sgtree()
1032       :  Base()
1033    {}
1034
1035    explicit sgtree(const key_compare &cmp, const value_traits &v_traits = value_traits())
1036       :  Base(cmp, v_traits)
1037    {}
1038
1039    template<class Iterator>
1040    sgtree( bool unique, Iterator b, Iterator e
1041          , const key_compare &cmp = key_compare()
1042          , const value_traits &v_traits = value_traits())
1043       :  Base(unique, b, e, cmp, v_traits)
1044    {}
1045
1046    sgtree(BOOST_RV_REF(sgtree) x)
1047       :  Base(BOOST_MOVE_BASE(Base, x))
1048    {}
1049
1050    sgtree& operator=(BOOST_RV_REF(sgtree) x)
1051    {  return static_cast<sgtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
1052
1053    template <class Cloner, class Disposer>
1054    void clone_from(const sgtree &src, Cloner cloner, Disposer disposer)
1055    {  Base::clone_from(src, cloner, disposer);  }
1056
1057    template <class Cloner, class Disposer>
1058    void clone_from(BOOST_RV_REF(sgtree) src, Cloner cloner, Disposer disposer)
1059    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
1060
1061    static sgtree &container_from_end_iterator(iterator end_iterator)
1062    {  return static_cast<sgtree &>(Base::container_from_end_iterator(end_iterator));   }
1063
1064    static const sgtree &container_from_end_iterator(const_iterator end_iterator)
1065    {  return static_cast<const sgtree &>(Base::container_from_end_iterator(end_iterator));   }
1066
1067    static sgtree &container_from_iterator(iterator it)
1068    {  return static_cast<sgtree &>(Base::container_from_iterator(it));   }
1069
1070    static const sgtree &container_from_iterator(const_iterator it)
1071    {  return static_cast<const sgtree &>(Base::container_from_iterator(it));   }
1072 };
1073
1074 #endif
1075
1076 } //namespace intrusive
1077 } //namespace boost
1078
1079 #include <boost/intrusive/detail/config_end.hpp>
1080
1081 #endif //BOOST_INTRUSIVE_SGTREE_HPP