comparison DEPENDENCIES/generic/include/boost/intrusive/sgtree.hpp @ 101:c530137014c0

Update Boost headers (1.58.0)

 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2007-2013
+// (C) Copyright Ion Gaztanaga 2007-2014
 //
 // Distributed under the Boost Software License, Version 1.0.
 //    (See accompanying file LICENSE_1_0.txt or copy at
 //          http://www.boost.org/LICENSE_1_0.txt)
 //

 
 #ifndef BOOST_INTRUSIVE_SGTREE_HPP
 #define BOOST_INTRUSIVE_SGTREE_HPP
 
 #include <boost/intrusive/detail/config_begin.hpp>
-#include <algorithm>
-#include <cstddef>
-#include <functional>
-#include <iterator>
-#include <utility>
-#include <cmath>
-#include <cstddef>
+#include <boost/intrusive/intrusive_fwd.hpp>
 #include <boost/intrusive/detail/assert.hpp>
 #include <boost/static_assert.hpp>
-#include <boost/intrusive/intrusive_fwd.hpp>
 #include <boost/intrusive/bs_set_hook.hpp>
 #include <boost/intrusive/bstree.hpp>
 #include <boost/intrusive/detail/tree_node.hpp>
-#include <boost/intrusive/detail/ebo_functor_holder.hpp>
 #include <boost/intrusive/pointer_traits.hpp>
 #include <boost/intrusive/detail/mpl.hpp>
-#include <boost/intrusive/detail/utilities.hpp>
-#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/detail/math.hpp>
+#include <boost/intrusive/detail/get_value_traits.hpp>
 #include <boost/intrusive/sgtree_algorithms.hpp>
+#include <boost/intrusive/detail/key_nodeptr_comp.hpp>
 #include <boost/intrusive/link_mode.hpp>
-#include <boost/move/move.hpp>
+
+#include <boost/move/utility_core.hpp>
+#include <boost/move/adl_move_swap.hpp>
+
+#include <cstddef>
+#include <boost/intrusive/detail/minimal_less_equal_header.hpp>
+#include <boost/intrusive/detail/minimal_pair_header.hpp>   //std::pair
+#include <cmath>
+#include <cstddef>
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#  pragma once
+#endif
 
 namespace boost {
 namespace intrusive {
 
 /// @cond
 
 namespace detail{
+
+/////////////////////////////////////////////////////////////
+//
+//       Halpha for fixed floating_point<false> option
+//
+/////////////////////////////////////////////////////////////
 
 //! Returns floor(log2(n)/log2(sqrt(2))) -> floor(2*log2(n))
 //! Undefined if N is 0.
 //!
 //! This function does not use float point operations.
 inline std::size_t calculate_h_sqrt2 (std::size_t n)
 {
    std::size_t f_log2 = detail::floor_log2(n);
-   return (2*f_log2) + (n >= detail::sqrt2_pow_2xplus1 (f_log2));
+   return (2*f_log2) + static_cast<std::size_t>(n >= detail::sqrt2_pow_2xplus1(f_log2));
 }
 
 struct h_alpha_sqrt2_t
 {
    h_alpha_sqrt2_t(void){}

       const std::size_t max_tree_size_limit = ((~std::size_t(0))/std::size_t(3));
       return max_tree_size > max_tree_size_limit ? max_tree_size/4*3 : max_tree_size*3/4;
    }
 };
 
+/////////////////////////////////////////////////////////////
+//
+//       Halpha for fixed floating_point<true> option
+//
+/////////////////////////////////////////////////////////////
+
 struct h_alpha_t
 {
    explicit h_alpha_t(float inv_minus_logalpha)
       :  inv_minus_logalpha_(inv_minus_logalpha)
    {}
 
    std::size_t operator()(std::size_t n) const
    {
-      //Returns floor(log2(1/alpha(n))) ->
-      // floor(log2(n)/log(1/alpha)) ->
-      // floor(log2(n)/(-log2(alpha)))
-      //return static_cast<std::size_t>(std::log(float(n))*inv_minus_logalpha_);
+      ////////////////////////////////////////////////////////////
+      // This function must return "floor(log2(1/alpha(n)))" ->
+      //    floor(log2(n)/log(1/alpha)) ->
+      //    floor(log2(n)/-log2(alpha))
+      //    floor(log2(n)*(1/-log2(alpha)))
+      ////////////////////////////////////////////////////////////
       return static_cast<std::size_t>(detail::fast_log2(float(n))*inv_minus_logalpha_);
    }
 
    private:
    //Since the function will be repeatedly called

 struct alpha_holder
 {
    typedef boost::intrusive::detail::h_alpha_t           h_alpha_t;
    typedef boost::intrusive::detail::alpha_by_max_size_t multiply_by_alpha_t;
 
-   alpha_holder() : max_tree_size_(0)
-   {  set_alpha(0.7f);   }
+   alpha_holder()
+      : max_tree_size_()
+   {  set_alpha(0.70711f);   } // ~1/sqrt(2)
 
    float get_alpha() const
    {  return alpha_;  }
 
    void set_alpha(float alpha)

       alpha_ = alpha;
       inv_minus_logalpha_ = 1/(-detail::fast_log2(alpha));
    }
 
    h_alpha_t get_h_alpha_t() const
-   {  return h_alpha_t(/*alpha_, */inv_minus_logalpha_);  }
+   {  return h_alpha_t(inv_minus_logalpha_);  }
 
    multiply_by_alpha_t get_multiply_by_alpha_t() const
    {  return multiply_by_alpha_t(alpha_);  }
 
    protected:

    //without using floating point operations
    //Downside: alpha CAN't be changed.
    typedef boost::intrusive::detail::h_alpha_sqrt2_t           h_alpha_t;
    typedef boost::intrusive::detail::alpha_0_75_by_max_size_t  multiply_by_alpha_t;
 
+   alpha_holder()
+      : max_tree_size_()
+   {}
+
    float get_alpha() const
    {  return 0.70710677f;  }
 
    void set_alpha(float)
    {  //alpha CAN't be changed.

 
 }  //namespace detail{
 
 struct sgtree_defaults
 {
-   typedef detail::default_bstree_hook proto_value_traits;
+   typedef default_bstree_hook_applier proto_value_traits;
    static const bool constant_time_size = true;
    typedef std::size_t size_type;
    typedef void compare;
    static const bool floating_point = true;
+   typedef void header_holder_type;
 };
 
 /// @endcond
 
 //! The class template sgtree is an intrusive scapegoat tree container, that

 //! \c floating_point<>, \c size_type<> and
 //! \c compare<>.
 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 template<class T, class ...Options>
 #else
-template<class ValueTraits, class VoidOrKeyComp, class SizeType, bool FloatingPoint>
+template<class ValueTraits, class VoidOrKeyComp, class SizeType, bool FloatingPoint, typename HeaderHolder>
 #endif
 class sgtree_impl
    /// @cond
-   :  public bstree_impl<ValueTraits, VoidOrKeyComp, SizeType, true, SgTreeAlgorithms>
+   :  public bstree_impl<ValueTraits, VoidOrKeyComp, SizeType, true, SgTreeAlgorithms, HeaderHolder>
    ,  public detail::alpha_holder<FloatingPoint, SizeType>
    /// @endcond
 {
    public:
    typedef ValueTraits                                               value_traits;
    /// @cond
    typedef bstree_impl< ValueTraits, VoidOrKeyComp, SizeType
-                      , true, SgTreeAlgorithms>                      tree_type;
+                      , true, SgTreeAlgorithms, HeaderHolder>        tree_type;
    typedef tree_type                                                 implementation_defined;
-   typedef typename tree_type::real_value_traits                     real_value_traits;
 
    /// @endcond
 
    typedef typename implementation_defined::pointer                  pointer;
    typedef typename implementation_defined::const_pointer            const_pointer;

    typedef detail::alpha_holder<FloatingPoint, SizeType>    alpha_traits;
    typedef typename alpha_traits::h_alpha_t                 h_alpha_t;
    typedef typename alpha_traits::multiply_by_alpha_t       multiply_by_alpha_t;
 
    BOOST_MOVABLE_BUT_NOT_COPYABLE(sgtree_impl)
-   BOOST_STATIC_ASSERT(((int)real_value_traits::link_mode != (int)auto_unlink));
+   BOOST_STATIC_ASSERT(((int)value_traits::link_mode != (int)auto_unlink));
 
    enum { safemode_or_autounlink  =
-            (int)real_value_traits::link_mode == (int)auto_unlink   ||
-            (int)real_value_traits::link_mode == (int)safe_link     };
+            (int)value_traits::link_mode == (int)auto_unlink   ||
+            (int)value_traits::link_mode == (int)safe_link     };
 
    /// @endcond
 
    public:
 

          this->insert_equal(b, e);
    }
 
    //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
    sgtree_impl(BOOST_RV_REF(sgtree_impl) x)
-      :  tree_type(::boost::move(static_cast<tree_type&>(x))), alpha_traits(x.get_alpha_traits())
-   {  std::swap(this->get_alpha_traits(), x.get_alpha_traits());   }
+      :  tree_type(BOOST_MOVE_BASE(tree_type, x)), alpha_traits(x.get_alpha_traits())
+   {  ::boost::adl_move_swap(this->get_alpha_traits(), x.get_alpha_traits());   }
 
    //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
    sgtree_impl& operator=(BOOST_RV_REF(sgtree_impl) x)
    {
       this->get_alpha_traits() = x.get_alpha_traits();
-      return static_cast<sgtree_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x))));
+      return static_cast<sgtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));
    }
 
    /// @cond
    private:
 

 
    //! @copydoc ::boost::intrusive::bstree::swap
    void swap(sgtree_impl& other)
    {
       //This can throw
-      using std::swap;
       this->tree_type::swap(static_cast<tree_type&>(other));
-      swap(this->get_alpha_traits(), other.get_alpha_traits());
+      ::boost::adl_move_swap(this->get_alpha_traits(), other.get_alpha_traits());
    }
 
    //! @copydoc ::boost::intrusive::bstree::clone_from
    //! Additional notes: it also copies the alpha factor from the source container.
    template <class Cloner, class Disposer>

    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
    iterator insert_equal(reference value)
    {
-      detail::key_nodeptr_comp<value_compare, real_value_traits>
-         key_node_comp(this->value_comp(), &this->get_real_value_traits());
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      detail::key_nodeptr_comp<value_compare, value_traits>
+         key_node_comp(this->value_comp(), &this->get_value_traits());
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
       node_ptr p = node_algorithms::insert_equal_upper_bound
          (this->tree_type::header_ptr(), to_insert, key_node_comp
          , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
       this->tree_type::sz_traits().increment();
       this->max_tree_size_ = (size_type)max_tree_size;
-      return iterator(p, this->real_value_traits_ptr());
+      return iterator(p, this->priv_value_traits_ptr());
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
    iterator insert_equal(const_iterator hint, reference value)
    {
-      detail::key_nodeptr_comp<value_compare, real_value_traits>
-         key_node_comp(this->value_comp(), &this->get_real_value_traits());
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      detail::key_nodeptr_comp<value_compare, value_traits>
+         key_node_comp(this->value_comp(), &this->get_value_traits());
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
       node_ptr p = node_algorithms::insert_equal
          (this->tree_type::header_ptr(), hint.pointed_node(), to_insert, key_node_comp
          , (std::size_t)this->size(), this->get_h_alpha_func(), max_tree_size);
       this->tree_type::sz_traits().increment();
       this->max_tree_size_ = (size_type)max_tree_size;
-      return iterator(p, this->real_value_traits_ptr());
+      return iterator(p, this->priv_value_traits_ptr());
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
    template<class Iterator>
    void insert_equal(Iterator b, Iterator e)

    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyValueCompare,insert_commit_data&)
    template<class KeyType, class KeyValueCompare>
    std::pair<iterator, bool> insert_unique_check
       (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
    {
-      detail::key_nodeptr_comp<KeyValueCompare, real_value_traits>
-         comp(key_value_comp, &this->get_real_value_traits());
+      detail::key_nodeptr_comp<KeyValueCompare, value_traits>
+         comp(key_value_comp, &this->get_value_traits());
       std::pair<node_ptr, bool> ret =
          (node_algorithms::insert_unique_check
             (this->tree_type::header_ptr(), key, comp, commit_data));
-      return std::pair<iterator, bool>(iterator(ret.first, this->real_value_traits_ptr()), ret.second);
+      return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyValueCompare,insert_commit_data&)
    template<class KeyType, class KeyValueCompare>
    std::pair<iterator, bool> insert_unique_check
       (const_iterator hint, const KeyType &key
       ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
    {
-      detail::key_nodeptr_comp<KeyValueCompare, real_value_traits>
-         comp(key_value_comp, &this->get_real_value_traits());
+      detail::key_nodeptr_comp<KeyValueCompare, value_traits>
+         comp(key_value_comp, &this->get_value_traits());
       std::pair<node_ptr, bool> ret =
          (node_algorithms::insert_unique_check
             (this->tree_type::header_ptr(), hint.pointed_node(), key, comp, commit_data));
-      return std::pair<iterator, bool>(iterator(ret.first, this->real_value_traits_ptr()), ret.second);
+      return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
    iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
    {
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
       node_algorithms::insert_unique_commit
          ( this->tree_type::header_ptr(), to_insert, commit_data
          , (std::size_t)this->size(), this->get_h_alpha_func(), max_tree_size);
       this->tree_type::sz_traits().increment();
       this->max_tree_size_ = (size_type)max_tree_size;
-      return iterator(to_insert, this->real_value_traits_ptr());
+      return iterator(to_insert, this->priv_value_traits_ptr());
    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
    template<class Iterator>
    void insert_unique(Iterator b, Iterator e)

    }
 
    //! @copydoc ::boost::intrusive::bstree::insert_before
    iterator insert_before(const_iterator pos, reference value)
    {
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
       node_ptr p = node_algorithms::insert_before
          ( this->tree_type::header_ptr(), pos.pointed_node(), to_insert
          , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
       this->tree_type::sz_traits().increment();
       this->max_tree_size_ = (size_type)max_tree_size;
-      return iterator(p, this->real_value_traits_ptr());
+      return iterator(p, this->priv_value_traits_ptr());
    }
 
    //! @copydoc ::boost::intrusive::bstree::push_back
    void push_back(reference value)
    {
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
       node_algorithms::push_back
          ( this->tree_type::header_ptr(), to_insert

    }
 
    //! @copydoc ::boost::intrusive::bstree::push_front
    void push_front(reference value)
    {
-      node_ptr to_insert(this->get_real_value_traits().to_node_ptr(value));
+      node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
       if(safemode_or_autounlink)
          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
       std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
       node_algorithms::push_front
          ( this->tree_type::header_ptr(), to_insert

    template<class Disposer>
    iterator erase_and_dispose(const_iterator i, Disposer disposer)
    {
       node_ptr to_erase(i.pointed_node());
       iterator ret(this->erase(i));
-      disposer(this->get_real_value_traits().to_value_ptr(to_erase));
+      disposer(this->get_value_traits().to_value_ptr(to_erase));
       return ret;
    }
 
    #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
    template<class Disposer>

    size_type count(const_reference value) const;
 
    //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyValueCompare)const
    template<class KeyType, class KeyValueCompare>
    size_type count(const KeyType& key, KeyValueCompare comp) const;
-   
+
    //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference)
    iterator lower_bound(const_reference value);
-   
+
    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare)
    template<class KeyType, class KeyValueCompare>
    iterator lower_bound(const KeyType& key, KeyValueCompare comp);
 
    //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference)const

 //! same options (either explicitly or implicitly) are used.
 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 template<class T, class ...Options>
 #else
 template<class T, class O1 = void, class O2 = void
-                , class O3 = void, class O4 = void>
+                , class O3 = void, class O4 = void
+                , class O5 = void>
 #endif
 struct make_sgtree
 {
    /// @cond
    typedef typename pack_options
       < sgtree_defaults,
       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-      O1, O2, O3, O4
+      O1, O2, O3, O4, O5
       #else
       Options...
       #endif
       >::type packed_options;
 

    typedef sgtree_impl
          < value_traits
          , typename packed_options::compare
          , typename packed_options::size_type
          , packed_options::floating_point
+         , typename packed_options::header_holder_type
          > implementation_defined;
    /// @endcond
    typedef implementation_defined type;
 };
 
 
 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 
 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-template<class T, class O1, class O2, class O3, class O4>
+template<class T, class O1, class O2, class O3, class O4, class O5>
 #else
 template<class T, class ...Options>
 #endif
 class sgtree
    :  public make_sgtree<T,
       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-      O1, O2, O3, O4
+      O1, O2, O3, O4, O5
       #else
       Options...
       #endif
       >::type
 {
    typedef typename make_sgtree
       <T,
       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
-      O1, O2, O3, O4
+      O1, O2, O3, O4, O5
       #else
       Options...
       #endif
       >::type   Base;
    BOOST_MOVABLE_BUT_NOT_COPYABLE(sgtree)
 
    public:
    typedef typename Base::value_compare      value_compare;
    typedef typename Base::value_traits       value_traits;
-   typedef typename Base::real_value_traits  real_value_traits;
    typedef typename Base::iterator           iterator;
    typedef typename Base::const_iterator     const_iterator;
    typedef typename Base::reverse_iterator           reverse_iterator;
    typedef typename Base::const_reverse_iterator     const_reverse_iterator;
 
    //Assert if passed value traits are compatible with the type
-   BOOST_STATIC_ASSERT((detail::is_same<typename real_value_traits::value_type, T>::value));
+   BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 
    explicit sgtree( const value_compare &cmp = value_compare()
                   , const value_traits &v_traits = value_traits())
       :  Base(cmp, v_traits)
    {}

          , const value_traits &v_traits = value_traits())
       :  Base(unique, b, e, cmp, v_traits)
    {}
 
    sgtree(BOOST_RV_REF(sgtree) x)
-      :  Base(::boost::move(static_cast<Base&>(x)))
+      :  Base(BOOST_MOVE_BASE(Base, x))
    {}
 
    sgtree& operator=(BOOST_RV_REF(sgtree) x)
-   {  return static_cast<sgtree &>(this->Base::operator=(::boost::move(static_cast<Base&>(x))));  }
+   {  return static_cast<sgtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
 
    static sgtree &container_from_end_iterator(iterator end_iterator)
    {  return static_cast<sgtree &>(Base::container_from_end_iterator(end_iterator));   }
 
    static const sgtree &container_from_end_iterator(const_iterator end_iterator)