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