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 treap_node_extra_checkerboost::intrusive::detail::treap_node_extra_checker48 treap_node_extra_checker(const NodePtrPrioCompare& prio_comp, ExtraChecker extra_checker) 49 : base_checker_t(extra_checker), prio_comp_(prio_comp) 50 {} 51 operator ()boost::intrusive::detail::treap_node_extra_checker52 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 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: rerotate_on_destroy(node_ptr header,node_ptr p,std::size_t & n)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 ~rerotate_on_destroy()132 ~rerotate_on_destroy() 133 { 134 if(remove_it_){ 135 rotate_up_n(header_, p_, n_); 136 } 137 } 138 release()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 rotate_up_n(const node_ptr header,const node_ptr p,std::size_t n)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 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> unlink(node_ptr node,NodePtrPriorityCompare pcomp)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 const_node_ptr&) 223 static bool unique(const_node_ptr node) BOOST_NOEXCEPT; 224 225 //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) 226 static std::size_t size(const_node_ptr header) BOOST_NOEXCEPT; 227 228 //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) 229 static node_ptr next_node(node_ptr node) BOOST_NOEXCEPT; 230 231 //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const 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> erase(node_ptr header,node_ptr z,NodePtrPriorityCompare pcomp)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 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(const 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 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 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 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 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 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 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> insert_equal_upper_bound(node_ptr h,node_ptr new_node,NodePtrCompare comp,NodePtrPriorityCompare pcomp)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> insert_equal_lower_bound(node_ptr h,node_ptr new_node,NodePtrCompare comp,NodePtrPriorityCompare pcomp)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> insert_equal(node_ptr h,node_ptr hint,node_ptr new_node,NodePtrCompare comp,NodePtrPriorityCompare pcomp)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> insert_before(node_ptr header,node_ptr pos,node_ptr new_node,NodePtrPriorityCompare pcomp)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> push_back(node_ptr header,node_ptr new_node,NodePtrPriorityCompare pcomp)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> push_front(node_ptr header,node_ptr new_node,NodePtrPriorityCompare pcomp)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> insert_unique_check(const_node_ptr header,const KeyType & key,KeyNodePtrCompare comp,const PrioType & prio,PrioNodePtrPrioCompare pcomp,insert_commit_data & commit_data)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> insert_unique_check(const_node_ptr header,node_ptr hint,const KeyType & key,KeyNodePtrCompare comp,const PrioType & prio,PrioNodePtrPrioCompare pcomp,insert_commit_data & commit_data)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. insert_unique_commit(node_ptr header,node_ptr new_node,const insert_commit_data & commit_data)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> transfer_unique(node_ptr header1,NodePtrCompare comp,PrioNodePtrPrioCompare pcomp,node_ptr header2,node_ptr z)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> transfer_equal(node_ptr header1,NodePtrCompare comp,PrioNodePtrPrioCompare pcomp,node_ptr header2,node_ptr z)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> rebalance_for_erasure(node_ptr header,node_ptr z,NodePtrPriorityCompare pcomp)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> rebalance_check_and_commit(node_ptr h,node_ptr new_node,NodePtrPriorityCompare pcomp,insert_commit_data & commit_data)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> rebalance_after_insertion_check(const_node_ptr header,const_node_ptr up,const Key & k,KeyNodePriorityCompare pcomp,std::size_t & num_rotations)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> check_invariant(const_node_ptr header,NodePtrPriorityCompare pcomp)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 701