ceph/src/boost/boost/intrusive/treap_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-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 #ifndef BOOST_INTRUSIVE_TREAP_ALGORITHMS_HPP
  14 #define BOOST_INTRUSIVE_TREAP_ALGORITHMS_HPP
  15
  16 #include <boost/intrusive/detail/config_begin.hpp>
  17 #include <boost/intrusive/intrusive_fwd.hpp>
  18
  19 #include <cstddef>
  20
  21 #include <boost/intrusive/detail/assert.hpp>
  22 #include <boost/intrusive/detail/algo_type.hpp>
  23 #include <boost/intrusive/bstree_algorithms.hpp>
  24
  25 #if defined(BOOST_HAS_PRAGMA_ONCE)
  26 #  pragma once
  27 #endif
  28
  29 namespace boost {
  30 namespace intrusive {
  31
  32 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
  33
  34 namespace detail
  35 {
  36
  37 template<class ValueTraits, class NodePtrPrioCompare, class ExtraChecker>
  38 struct treap_node_extra_checker
  39       : public ExtraChecker
  40 {
  41    typedef ExtraChecker                            base_checker_t;
  42    typedef ValueTraits                             value_traits;
  43    typedef typename value_traits::node_traits      node_traits;
  44    typedef typename node_traits::const_node_ptr const_node_ptr;
  45
  46    typedef typename base_checker_t::return_type    return_type;
  47
  48    treap_node_extra_checker(const NodePtrPrioCompare& prio_comp, ExtraChecker extra_checker)
  49       : base_checker_t(extra_checker), prio_comp_(prio_comp)
  50    {}
  51
  52    void operator () (const_node_ptr p,
  53                      const return_type& check_return_left, const return_type& check_return_right,
  54                      return_type& check_return)
  55    {
  56       BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_traits::get_left(p) || !prio_comp_(node_traits::get_left(p), p));
  57       BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_traits::get_right(p) || !prio_comp_(node_traits::get_right(p), p));
  58       base_checker_t::operator()(p, check_return_left, check_return_right, check_return);
  59    }
  60
  61    const NodePtrPrioCompare prio_comp_;
  62 };
  63
  64 } // namespace detail
  65
  66 #endif   //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
  67
  68 //! treap_algorithms provides basic algorithms to manipulate
  69 //! nodes forming a treap.
  70 //!
  71 //! (1) the header node is maintained with links not only to the root
  72 //! but also to the leftmost node of the tree, to enable constant time
  73 //! begin(), and to the rightmost node of the tree, to enable linear time
  74 //! performance when used with the generic set algorithms (set_union,
  75 //! etc.);
  76 //!
  77 //! (2) when a node being deleted has two children its successor node is
  78 //! relinked into its place, rather than copied, so that the only
  79 //! pointers invalidated are those referring to the deleted node.
  80 //!
  81 //! treap_algorithms is configured with a NodeTraits class, which encapsulates the
  82 //! information about the node to be manipulated. NodeTraits must support the
  83 //! following interface:
  84 //!
  85 //! <b>Typedefs</b>:
  86 //!
  87 //! <tt>node</tt>: The type of the node that forms the treap
  88 //!
  89 //! <tt>node_ptr</tt>: A pointer to a node
  90 //!
  91 //! <tt>const_node_ptr</tt>: A pointer to a const node
  92 //!
  93 //! <b>Static functions</b>:
  94 //!
  95 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
  96 //!
  97 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
  98 //!
  99 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
 100 //!
 101 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
 102 //!
 103 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
 104 //!
 105 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
 106 template<class NodeTraits>
 107 class treap_algorithms
 108    #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 109    : public bstree_algorithms<NodeTraits>
 110    #endif
 111 {
 112    public:
 113    typedef NodeTraits                           node_traits;
 114    typedef typename NodeTraits::node            node;
 115    typedef typename NodeTraits::node_ptr       node_ptr;
 116    typedef typename NodeTraits::const_node_ptr const_node_ptr;
 117
 118    /// @cond
 119    private:
 120
 121    typedef bstree_algorithms<NodeTraits>  bstree_algo;
 122
 123    class rerotate_on_destroy
 124    {
 125       rerotate_on_destroy& operator=(const rerotate_on_destroy&);
 126
 127       public:
 128       rerotate_on_destroy(node_ptr header, node_ptr p, std::size_t &n)
 129          :  header_(header), p_(p), n_(n), remove_it_(true)
 130       {}
 131
 132       ~rerotate_on_destroy()
 133       {
 134          if(remove_it_){
 135             rotate_up_n(header_, p_, n_);
 136          }
 137       }
 138
 139       void release()
 140       {  remove_it_ = false;  }
 141
 142       const node_ptr header_;
 143       const node_ptr p_;
 144       std::size_t &n_;
 145       bool remove_it_;
 146    };
 147
 148    static void rotate_up_n(const node_ptr header, const node_ptr p, std::size_t n)
 149    {
 150       node_ptr p_parent(NodeTraits::get_parent(p));
 151       node_ptr p_grandparent(NodeTraits::get_parent(p_parent));
 152       while(n--){
 153          if(p == NodeTraits::get_left(p_parent)){  //p is left child
 154             bstree_algo::rotate_right(p_parent, p, p_grandparent, header);
 155          }
 156          else{ //p is right child
 157             bstree_algo::rotate_left(p_parent, p, p_grandparent, header);
 158          }
 159          p_parent      = p_grandparent;
 160          p_grandparent = NodeTraits::get_parent(p_parent);
 161       }
 162    }
 163
 164    /// @endcond
 165
 166    public:
 167    //! This type is the information that will be
 168    //! filled by insert_unique_check
 169    struct insert_commit_data
 170       /// @cond
 171       :  public bstree_algo::insert_commit_data
 172       /// @endcond
 173    {
 174       /// @cond
 175       std::size_t rotations;
 176       /// @endcond
 177    };
 178
 179    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 180
 181    //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const_node_ptr)
 182    static node_ptr get_header(const_node_ptr n) BOOST_NOEXCEPT;
 183
 184    //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node
 185    static node_ptr begin_node(const_node_ptr header) BOOST_NOEXCEPT;
 186
 187    //! @copydoc ::boost::intrusive::bstree_algorithms::end_node
 188    static node_ptr end_node(const_node_ptr header) BOOST_NOEXCEPT;
 189
 190    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree
 191    static void swap_tree(node_ptr header1, node_ptr header2) BOOST_NOEXCEPT;
 192
 193    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr)
 194    static void swap_nodes(node_ptr node1, node_ptr node2) BOOST_NOEXCEPT;
 195
 196    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr,node_ptr,node_ptr)
 197    static void swap_nodes(node_ptr node1, node_ptr header1, node_ptr node2, node_ptr header2) BOOST_NOEXCEPT;
 198
 199    //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(node_ptr,node_ptr)
 200    static void replace_node(node_ptr node_to_be_replaced, node_ptr new_node) BOOST_NOEXCEPT;
 201
 202    //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(node_ptr,node_ptr,node_ptr)
 203    static void replace_node(node_ptr node_to_be_replaced, node_ptr header, node_ptr new_node) BOOST_NOEXCEPT;
 204    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 205
 206    //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(node_ptr)
 207    template<class NodePtrPriorityCompare>
 208    static void unlink(node_ptr node, NodePtrPriorityCompare pcomp)
 209    {
 210       node_ptr x = NodeTraits::get_parent(node);
 211       if(x){
 212          while(!bstree_algo::is_header(x))
 213             x = NodeTraits::get_parent(x);
 214          erase(x, node, pcomp);
 215       }
 216    }
 217
 218    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 219    //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance
 220    static node_ptr unlink_leftmost_without_rebalance(node_ptr header) BOOST_NOEXCEPT;
 221
 222    //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const_node_ptr)
 223    static bool unique(const_node_ptr node) BOOST_NOEXCEPT;
 224
 225    //! @copydoc ::boost::intrusive::bstree_algorithms::size(const_node_ptr)
 226    static std::size_t size(const_node_ptr header) BOOST_NOEXCEPT;
 227
 228    //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(node_ptr)
 229    static node_ptr next_node(node_ptr node) BOOST_NOEXCEPT;
 230
 231    //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(node_ptr)
 232    static node_ptr prev_node(node_ptr node) BOOST_NOEXCEPT;
 233
 234    //! @copydoc ::boost::intrusive::bstree_algorithms::init(node_ptr)
 235    static void init(node_ptr node) BOOST_NOEXCEPT;
 236
 237    //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(node_ptr)
 238    static void init_header(node_ptr header) BOOST_NOEXCEPT;
 239    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 240
 241    //! @copydoc ::boost::intrusive::bstree_algorithms::erase(node_ptr,node_ptr)
 242    template<class NodePtrPriorityCompare>
 243    static node_ptr erase(node_ptr header, node_ptr z, NodePtrPriorityCompare pcomp)
 244    {
 245       rebalance_for_erasure(header, z, pcomp);
 246       bstree_algo::erase(header, z);
 247       return z;
 248    }
 249
 250    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 251    //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const_node_ptr,node_ptr,Cloner,Disposer)
 252    template <class Cloner, class Disposer>
 253    static void clone
 254       (const_node_ptr source_header, node_ptr target_header, Cloner cloner, Disposer disposer);
 255
 256    //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(node_ptr,Disposer)
 257    template<class Disposer>
 258    static void clear_and_dispose(node_ptr header, Disposer disposer) BOOST_NOEXCEPT;
 259
 260    //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const_node_ptr,const KeyType&,KeyNodePtrCompare)
 261    template<class KeyType, class KeyNodePtrCompare>
 262    static node_ptr lower_bound
 263       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
 264
 265    //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const_node_ptr,const KeyType&,KeyNodePtrCompare)
 266    template<class KeyType, class KeyNodePtrCompare>
 267    static node_ptr upper_bound
 268       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
 269
 270    //! @copydoc ::boost::intrusive::bstree_algorithms::find(const_node_ptr, const KeyType&,KeyNodePtrCompare)
 271    template<class KeyType, class KeyNodePtrCompare>
 272    static node_ptr find
 273       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
 274
 275    //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const_node_ptr,const KeyType&,KeyNodePtrCompare)
 276    template<class KeyType, class KeyNodePtrCompare>
 277    static std::pair<node_ptr, node_ptr> equal_range
 278       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
 279
 280    //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const_node_ptr,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool)
 281    template<class KeyType, class KeyNodePtrCompare>
 282    static std::pair<node_ptr, node_ptr> bounded_range
 283       (const_node_ptr header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
 284       , bool left_closed, bool right_closed);
 285
 286    //! @copydoc ::boost::intrusive::bstree_algorithms::count(const_node_ptr,const KeyType&,KeyNodePtrCompare)
 287    template<class KeyType, class KeyNodePtrCompare>
 288    static std::size_t count(const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
 289
 290    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 291
 292    //! <b>Requires</b>: "h" must be the header node of a tree.
 293    //!   NodePtrCompare is a function object that induces a strict weak
 294    //!   ordering compatible with the strict weak ordering used to create the
 295    //!   the tree. NodePtrCompare compares two node_ptrs.
 296    //!   NodePtrPriorityCompare is a priority function object that induces a strict weak
 297    //!   ordering compatible with the one used to create the
 298    //!   the tree. NodePtrPriorityCompare compares two node_ptrs.
 299    //!
 300    //! <b>Effects</b>: Inserts new_node into the tree before the upper bound
 301    //!   according to "comp" and rotates the tree according to "pcomp".
 302    //!
 303    //! <b>Complexity</b>: Average complexity for insert element is at
 304    //!   most logarithmic.
 305    //!
 306    //! <b>Throws</b>: If "comp" throw or "pcomp" throw.
 307    template<class NodePtrCompare, class NodePtrPriorityCompare>
 308    static node_ptr insert_equal_upper_bound
 309       (node_ptr h, node_ptr new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp)
 310    {
 311       insert_commit_data commit_data;
 312       bstree_algo::insert_equal_upper_bound_check(h, new_node, comp, commit_data);
 313       rebalance_check_and_commit(h, new_node, pcomp, commit_data);
 314       return new_node;
 315    }
 316
 317    //! <b>Requires</b>: "h" must be the header node of a tree.
 318    //!   NodePtrCompare is a function object that induces a strict weak
 319    //!   ordering compatible with the strict weak ordering used to create the
 320    //!   the tree. NodePtrCompare compares two node_ptrs.
 321    //!   NodePtrPriorityCompare is a priority function object that induces a strict weak
 322    //!   ordering compatible with the one used to create the
 323    //!   the tree. NodePtrPriorityCompare compares two node_ptrs.
 324    //!
 325    //! <b>Effects</b>: Inserts new_node into the tree before the upper bound
 326    //!   according to "comp" and rotates the tree according to "pcomp".
 327    //!
 328    //! <b>Complexity</b>: Average complexity for insert element is at
 329    //!   most logarithmic.
 330    //!
 331    //! <b>Throws</b>: If "comp" throws.
 332    template<class NodePtrCompare, class NodePtrPriorityCompare>
 333    static node_ptr insert_equal_lower_bound
 334       (node_ptr h, node_ptr new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp)
 335    {
 336       insert_commit_data commit_data;
 337       bstree_algo::insert_equal_lower_bound_check(h, new_node, comp, commit_data);
 338       rebalance_check_and_commit(h, new_node, pcomp, commit_data);
 339       return new_node;
 340    }
 341
 342    //! <b>Requires</b>: "header" must be the header node of a tree.
 343    //!   NodePtrCompare is a function object that induces a strict weak
 344    //!   ordering compatible with the strict weak ordering used to create the
 345    //!   the tree. NodePtrCompare compares two node_ptrs. "hint" is node from
 346    //!   the "header"'s tree.
 347    //!   NodePtrPriorityCompare is a priority function object that induces a strict weak
 348    //!   ordering compatible with the one used to create the
 349    //!   the tree. NodePtrPriorityCompare compares two node_ptrs.
 350    //!
 351    //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to
 352    //!   where it will be inserted. If "hint" is the upper_bound
 353    //!   the insertion takes constant time (two comparisons in the worst case).
 354    //!   Rotates the tree according to "pcomp".
 355    //!
 356    //! <b>Complexity</b>: Logarithmic in general, but it is amortized
 357    //!   constant time if new_node is inserted immediately before "hint".
 358    //!
 359    //! <b>Throws</b>: If "comp" throw or "pcomp" throw.
 360    template<class NodePtrCompare, class NodePtrPriorityCompare>
 361    static node_ptr insert_equal
 362       (node_ptr h, node_ptr hint, node_ptr new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp)
 363    {
 364       insert_commit_data commit_data;
 365       bstree_algo::insert_equal_check(h, hint, new_node, comp, commit_data);
 366       rebalance_check_and_commit(h, new_node, pcomp, commit_data);
 367       return new_node;
 368    }
 369
 370    //! <b>Requires</b>: "header" must be the header node of a tree.
 371    //!   "pos" must be a valid node of the tree (including header end) node.
 372    //!   "pos" must be a node pointing to the successor to "new_node"
 373    //!   once inserted according to the order of already inserted nodes. This function does not
 374    //!   check "pos" and this precondition must be guaranteed by the caller.
 375    //!   NodePtrPriorityCompare is a priority function object that induces a strict weak
 376    //!   ordering compatible with the one used to create the
 377    //!   the tree. NodePtrPriorityCompare compares two node_ptrs.
 378    //!
 379    //! <b>Effects</b>: Inserts new_node into the tree before "pos"
 380    //!   and rotates the tree according to "pcomp".
 381    //!
 382    //! <b>Complexity</b>: Constant-time.
 383    //!
 384    //! <b>Throws</b>: If "pcomp" throws, strong guarantee.
 385    //!
 386    //! <b>Note</b>: If "pos" is not the successor of the newly inserted "new_node"
 387    //! tree invariants might be broken.
 388    template<class NodePtrPriorityCompare>
 389    static node_ptr insert_before
 390       (node_ptr header, node_ptr pos, node_ptr new_node, NodePtrPriorityCompare pcomp)
 391    {
 392       insert_commit_data commit_data;
 393       bstree_algo::insert_before_check(header, pos, commit_data);
 394       rebalance_check_and_commit(header, new_node, pcomp, commit_data);
 395       return new_node;
 396    }
 397
 398    //! <b>Requires</b>: "header" must be the header node of a tree.
 399    //!   "new_node" must be, according to the used ordering no less than the
 400    //!   greatest inserted key.
 401    //!   NodePtrPriorityCompare is a priority function object that induces a strict weak
 402    //!   ordering compatible with the one used to create the
 403    //!   the tree. NodePtrPriorityCompare compares two node_ptrs.
 404    //!
 405    //! <b>Effects</b>: Inserts x into the tree in the last position
 406    //!   and rotates the tree according to "pcomp".
 407    //!
 408    //! <b>Complexity</b>: Constant-time.
 409    //!
 410    //! <b>Throws</b>: If "pcomp" throws, strong guarantee.
 411    //!
 412    //! <b>Note</b>: If "new_node" is less than the greatest inserted key
 413    //! tree invariants are broken. This function is slightly faster than
 414    //! using "insert_before".
 415    template<class NodePtrPriorityCompare>
 416    static void push_back(node_ptr header, node_ptr new_node, NodePtrPriorityCompare pcomp)
 417    {
 418       insert_commit_data commit_data;
 419       bstree_algo::push_back_check(header, commit_data);
 420       rebalance_check_and_commit(header, new_node, pcomp, commit_data);
 421    }
 422
 423    //! <b>Requires</b>: "header" must be the header node of a tree.
 424    //!   "new_node" must be, according to the used ordering, no greater than the
 425    //!   lowest inserted key.
 426    //!   NodePtrPriorityCompare is a priority function object that induces a strict weak
 427    //!   ordering compatible with the one used to create the
 428    //!   the tree. NodePtrPriorityCompare compares two node_ptrs.
 429    //!
 430    //! <b>Effects</b>: Inserts x into the tree in the first position
 431    //!   and rotates the tree according to "pcomp".
 432    //!
 433    //! <b>Complexity</b>: Constant-time.
 434    //!
 435    //! <b>Throws</b>: If "pcomp" throws, strong guarantee.
 436    //!
 437    //! <b>Note</b>: If "new_node" is greater than the lowest inserted key
 438    //! tree invariants are broken. This function is slightly faster than
 439    //! using "insert_before".
 440    template<class NodePtrPriorityCompare>
 441    static void push_front(node_ptr header, node_ptr new_node, NodePtrPriorityCompare pcomp)
 442    {
 443       insert_commit_data commit_data;
 444       bstree_algo::push_front_check(header, commit_data);
 445       rebalance_check_and_commit(header, new_node, pcomp, commit_data);
 446    }
 447
 448    //! <b>Requires</b>: "header" must be the header node of a tree.
 449    //!   KeyNodePtrCompare is a function object that induces a strict weak
 450    //!   ordering compatible with the strict weak ordering used to create the
 451    //!   the tree. NodePtrCompare compares KeyType with a node_ptr.
 452    //!
 453    //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
 454    //!   tree according to "comp" and obtains the needed information to realize
 455    //!   a constant-time node insertion if there is no equivalent node.
 456    //!
 457    //! <b>Returns</b>: If there is an equivalent value
 458    //!   returns a pair containing a node_ptr to the already present node
 459    //!   and false. If there is not equivalent key can be inserted returns true
 460    //!   in the returned pair's boolean and fills "commit_data" that is meant to
 461    //!   be used with the "insert_commit" function to achieve a constant-time
 462    //!   insertion function.
 463    //!
 464    //! <b>Complexity</b>: Average complexity is at most logarithmic.
 465    //!
 466    //! <b>Throws</b>: If "comp" throws.
 467    //!
 468    //! <b>Notes</b>: This function is used to improve performance when constructing
 469    //!   a node is expensive and the user does not want to have two equivalent nodes
 470    //!   in the tree: if there is an equivalent value
 471    //!   the constructed object must be discarded. Many times, the part of the
 472    //!   node that is used to impose the order is much cheaper to construct
 473    //!   than the node and this function offers the possibility to use that part
 474    //!   to check if the insertion will be successful.
 475    //!
 476    //!   If the check is successful, the user can construct the node and use
 477    //!   "insert_commit" to insert the node in constant-time. This gives a total
 478    //!   logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
 479    //!
 480    //!   "commit_data" remains valid for a subsequent "insert_unique_commit" only
 481    //!   if no more objects are inserted or erased from the set.
 482    template<class KeyType, class KeyNodePtrCompare, class PrioType, class PrioNodePtrPrioCompare>
 483    static std::pair<node_ptr, bool> insert_unique_check
 484       ( const_node_ptr header
 485       , const KeyType &key, KeyNodePtrCompare comp
 486       , const PrioType &prio, PrioNodePtrPrioCompare pcomp
 487       , insert_commit_data &commit_data)
 488    {
 489       std::pair<node_ptr, bool> ret =
 490          bstree_algo::insert_unique_check(header, key, comp, commit_data);
 491       if(ret.second)
 492          rebalance_after_insertion_check(header, commit_data.node, prio, pcomp, commit_data.rotations);
 493       return ret;
 494    }
 495
 496    //! <b>Requires</b>: "header" must be the header node of a tree.
 497    //!   KeyNodePtrCompare is a function object that induces a strict weak
 498    //!   ordering compatible with the strict weak ordering used to create the
 499    //!   the tree. NodePtrCompare compares KeyType with a node_ptr.
 500    //!   "hint" is node from the "header"'s tree.
 501    //!
 502    //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
 503    //!   tree according to "comp" using "hint" as a hint to where it should be
 504    //!   inserted and obtains the needed information to realize
 505    //!   a constant-time node insertion if there is no equivalent node.
 506    //!   If "hint" is the upper_bound the function has constant time
 507    //!   complexity (two comparisons in the worst case).
 508    //!
 509    //! <b>Returns</b>: If there is an equivalent value
 510    //!   returns a pair containing a node_ptr to the already present node
 511    //!   and false. If there is not equivalent key can be inserted returns true
 512    //!   in the returned pair's boolean and fills "commit_data" that is meant to
 513    //!   be used with the "insert_commit" function to achieve a constant-time
 514    //!   insertion function.
 515    //!
 516    //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is
 517    //!   amortized constant time if new_node should be inserted immediately before "hint".
 518    //!
 519    //! <b>Throws</b>: If "comp" throws.
 520    //!
 521    //! <b>Notes</b>: This function is used to improve performance when constructing
 522    //!   a node is expensive and the user does not want to have two equivalent nodes
 523    //!   in the tree: if there is an equivalent value
 524    //!   the constructed object must be discarded. Many times, the part of the
 525    //!   node that is used to impose the order is much cheaper to construct
 526    //!   than the node and this function offers the possibility to use that part
 527    //!   to check if the insertion will be successful.
 528    //!
 529    //!   If the check is successful, the user can construct the node and use
 530    //!   "insert_commit" to insert the node in constant-time. This gives a total
 531    //!   logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
 532    //!
 533    //!   "commit_data" remains valid for a subsequent "insert_unique_commit" only
 534    //!   if no more objects are inserted or erased from the set.
 535    template<class KeyType, class KeyNodePtrCompare, class PrioType, class PrioNodePtrPrioCompare>
 536    static std::pair<node_ptr, bool> insert_unique_check
 537       ( const_node_ptr header, node_ptr hint
 538       , const KeyType &key, KeyNodePtrCompare comp
 539       , const PrioType &prio, PrioNodePtrPrioCompare pcomp
 540       , insert_commit_data &commit_data)
 541    {
 542       std::pair<node_ptr, bool> ret =
 543          bstree_algo::insert_unique_check(header, hint, key, comp, commit_data);
 544       if(ret.second)
 545          rebalance_after_insertion_check(header, commit_data.node, prio, pcomp, commit_data.rotations);
 546       return ret;
 547    }
 548
 549    //! <b>Requires</b>: "header" must be the header node of a tree.
 550    //!   "commit_data" must have been obtained from a previous call to
 551    //!   "insert_unique_check". No objects should have been inserted or erased
 552    //!   from the set between the "insert_unique_check" that filled "commit_data"
 553    //!   and the call to "insert_commit".
 554    //!
 555    //!
 556    //! <b>Effects</b>: Inserts new_node in the set using the information obtained
 557    //!   from the "commit_data" that a previous "insert_check" filled.
 558    //!
 559    //! <b>Complexity</b>: Constant time.
 560    //!
 561    //! <b>Throws</b>: Nothing.
 562    //!
 563    //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been
 564    //!   previously executed to fill "commit_data". No value should be inserted or
 565    //!   erased between the "insert_check" and "insert_commit" calls.
 566    static void insert_unique_commit
 567       (node_ptr header, node_ptr new_node, const insert_commit_data &commit_data) BOOST_NOEXCEPT
 568    {
 569       bstree_algo::insert_unique_commit(header, new_node, commit_data);
 570       rotate_up_n(header, new_node, commit_data.rotations);
 571    }
 572
 573    //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
 574    template<class NodePtrCompare, class PrioNodePtrPrioCompare>
 575    static bool transfer_unique
 576       (node_ptr header1, NodePtrCompare comp, PrioNodePtrPrioCompare pcomp, node_ptr header2, node_ptr z)
 577    {
 578       insert_commit_data commit_data;
 579       bool const transferable = insert_unique_check(header1, z, comp, z, pcomp, commit_data).second;
 580       if(transferable){
 581          erase(header2, z, pcomp);
 582          insert_unique_commit(header1, z, commit_data);
 583       }
 584       return transferable;
 585    }
 586
 587    //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
 588    template<class NodePtrCompare, class PrioNodePtrPrioCompare>
 589    static void transfer_equal
 590       (node_ptr header1, NodePtrCompare comp, PrioNodePtrPrioCompare pcomp, node_ptr header2, node_ptr z)
 591    {
 592       insert_commit_data commit_data;
 593       bstree_algo::insert_equal_upper_bound_check(header1, z, comp, commit_data);
 594       rebalance_after_insertion_check(header1, commit_data.node, z, pcomp, commit_data.rotations);
 595       rebalance_for_erasure(header2, z, pcomp);
 596       bstree_algo::erase(header2, z);
 597       bstree_algo::insert_unique_commit(header1, z, commit_data);
 598       rotate_up_n(header1, z, commit_data.rotations);
 599    }
 600
 601    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 602
 603    //! @copydoc ::boost::intrusive::bstree_algorithms::is_header
 604    static bool is_header(const_node_ptr p) BOOST_NOEXCEPT;
 605    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 606
 607    /// @cond
 608    private:
 609
 610    template<class NodePtrPriorityCompare>
 611    static void rebalance_for_erasure(node_ptr header, node_ptr z, NodePtrPriorityCompare pcomp)
 612    {
 613       std::size_t n = 0;
 614       rerotate_on_destroy rb(header, z, n);
 615
 616       node_ptr z_left  = NodeTraits::get_left(z);
 617       node_ptr z_right = NodeTraits::get_right(z);
 618       while(z_left || z_right){
 619          const node_ptr z_parent(NodeTraits::get_parent(z));
 620          if(!z_right || (z_left && pcomp(z_left, z_right))){
 621             bstree_algo::rotate_right(z, z_left, z_parent, header);
 622          }
 623          else{
 624             bstree_algo::rotate_left(z, z_right, z_parent, header);
 625          }
 626          ++n;
 627          z_left  = NodeTraits::get_left(z);
 628          z_right = NodeTraits::get_right(z);
 629       }
 630       rb.release();
 631    }
 632
 633    template<class NodePtrPriorityCompare>
 634    static void rebalance_check_and_commit
 635       (node_ptr h, node_ptr new_node, NodePtrPriorityCompare pcomp, insert_commit_data &commit_data)
 636    {
 637       rebalance_after_insertion_check(h, commit_data.node, new_node, pcomp, commit_data.rotations);
 638       //No-throw
 639       bstree_algo::insert_unique_commit(h, new_node, commit_data);
 640       rotate_up_n(h, new_node, commit_data.rotations);
 641    }
 642
 643    template<class Key, class KeyNodePriorityCompare>
 644    static void rebalance_after_insertion_check
 645       (const_node_ptr header, const_node_ptr up, const Key &k
 646       , KeyNodePriorityCompare pcomp, std::size_t &num_rotations)
 647    {
 648       const_node_ptr upnode(up);
 649       //First check rotations since pcomp can throw
 650       num_rotations = 0;
 651       std::size_t n = 0;
 652       while(upnode != header && pcomp(k, upnode)){
 653          ++n;
 654          upnode = NodeTraits::get_parent(upnode);
 655       }
 656       num_rotations = n;
 657    }
 658
 659    template<class NodePtrPriorityCompare>
 660    static bool check_invariant(const_node_ptr header, NodePtrPriorityCompare pcomp)
 661    {
 662       node_ptr beg = begin_node(header);
 663       node_ptr end = end_node(header);
 664
 665       while(beg != end){
 666          node_ptr p = NodeTraits::get_parent(beg);
 667          if(p != header){
 668             if(pcomp(beg, p))
 669                return false;
 670          }
 671          beg = next_node(beg);
 672       }
 673       return true;
 674    }
 675
 676    /// @endcond
 677 };
 678
 679 /// @cond
 680
 681 template<class NodeTraits>
 682 struct get_algo<TreapAlgorithms, NodeTraits>
 683 {
 684    typedef treap_algorithms<NodeTraits> type;
 685 };
 686
 687 template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
 688 struct get_node_checker<TreapAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
 689 {
 690    typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
 691 };
 692
 693 /// @endcond
 694
 695 } //namespace intrusive
 696 } //namespace boost
 697
 698 #include <boost/intrusive/detail/config_end.hpp>
 699
 700 #endif //BOOST_INTRUSIVE_TREAP_ALGORITHMS_HPP