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
29namespace boost {
30namespace intrusive {
31
32#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
33
34namespace detail
35{
36
37template<class ValueTraits, class NodePtrPrioCompare, class ExtraChecker>
38struct 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>
108template<class NodeTraits>
109class 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: header_, p: p_, n: 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, p: new_node, n: commit_data.rotations);
570 }
571
572 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
573
574 //! @copydoc ::boost::intrusive::bstree_algorithms::is_header
575 static bool is_header(const const_node_ptr & p);
576 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
577
578 /// @cond
579 private:
580
581 template<class NodePtrPriorityCompare>
582 static void rebalance_for_erasure(const node_ptr & header, const node_ptr & z, NodePtrPriorityCompare pcomp)
583 {
584 std::size_t n = 0;
585 rerotate_on_destroy rb(header, z, n);
586
587 node_ptr z_left = NodeTraits::get_left(z);
588 node_ptr z_right = NodeTraits::get_right(z);
589 while(z_left || z_right){
590 const node_ptr z_parent(NodeTraits::get_parent(z));
591 if(!z_right || (z_left && pcomp(z_left, z_right))){
592 bstree_algo::rotate_right(z, z_left, z_parent, header);
593 }
594 else{
595 bstree_algo::rotate_left(z, z_right, z_parent, header);
596 }
597 ++n;
598 z_left = NodeTraits::get_left(z);
599 z_right = NodeTraits::get_right(z);
600 }
601 rb.release();
602 }
603
604 template<class NodePtrPriorityCompare>
605 static void rebalance_check_and_commit
606 (const node_ptr & h, const node_ptr & new_node, NodePtrPriorityCompare pcomp, insert_commit_data &commit_data)
607 {
608 rebalance_after_insertion_check(h, commit_data.node, new_node, pcomp, commit_data.rotations);
609 //No-throw
610 bstree_algo::insert_unique_commit(h, new_node, commit_data);
611 rotate_up_n(header: h, p: new_node, n: commit_data.rotations);
612 }
613
614 template<class Key, class KeyNodePriorityCompare>
615 static void rebalance_after_insertion_check
616 (const const_node_ptr &header, const const_node_ptr & up, const Key &k
617 , KeyNodePriorityCompare pcomp, std::size_t &num_rotations)
618 {
619 const_node_ptr upnode(up);
620 //First check rotations since pcomp can throw
621 num_rotations = 0;
622 std::size_t n = 0;
623 while(upnode != header && pcomp(k, upnode)){
624 ++n;
625 upnode = NodeTraits::get_parent(upnode);
626 }
627 num_rotations = n;
628 }
629
630 template<class NodePtrPriorityCompare>
631 static bool check_invariant(const const_node_ptr & header, NodePtrPriorityCompare pcomp)
632 {
633 node_ptr beg = begin_node(header);
634 node_ptr end = end_node(header);
635
636 while(beg != end){
637 node_ptr p = NodeTraits::get_parent(beg);
638 if(p != header){
639 if(pcomp(beg, p))
640 return false;
641 }
642 beg = next_node(beg);
643 }
644 return true;
645 }
646
647 /// @endcond
648};
649
650/// @cond
651
652template<class NodeTraits>
653struct get_algo<TreapAlgorithms, NodeTraits>
654{
655 typedef treap_algorithms<NodeTraits> type;
656};
657
658template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
659struct get_node_checker<TreapAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
660{
661 typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
662};
663
664/// @endcond
665
666} //namespace intrusive
667} //namespace boost
668
669#include <boost/intrusive/detail/config_end.hpp>
670
671#endif //BOOST_INTRUSIVE_TREAP_ALGORITHMS_HPP
672

source code of boost/boost/intrusive/treap_algorithms.hpp