1 /////////////////////////////////////////////////////////////////////////////
\r
3 // (C) Copyright Olaf Krzikalla 2004-2006.
\r
4 // (C) Copyright Ion GaztaƱaga 2006-2007.
\r
6 // Distributed under the Boost Software License, Version 1.0.
\r
7 // (See accompanying file LICENSE_1_0.txt or copy at
\r
8 // http://www.boost.org/LICENSE_1_0.txt)
\r
10 // See http://www.boost.org/libs/intrusive for documentation.
\r
12 /////////////////////////////////////////////////////////////////////////////
\r
13 // The internal implementation of red-black trees is based on that of SGI STL
\r
14 // stl_tree.h file:
\r
16 // Copyright (c) 1996,1997
\r
17 // Silicon Graphics Computer Systems, Inc.
\r
19 // Permission to use, copy, modify, distribute and sell this software
\r
20 // and its documentation for any purpose is hereby granted without fee,
\r
21 // provided that the above copyright notice appear in all copies and
\r
22 // that both that copyright notice and this permission notice appear
\r
23 // in supporting documentation. Silicon Graphics makes no
\r
24 // representations about the suitability of this software for any
\r
25 // purpose. It is provided "as is" without express or implied warranty.
\r
28 // Copyright (c) 1994
\r
29 // Hewlett-Packard Company
\r
31 // Permission to use, copy, modify, distribute and sell this software
\r
32 // and its documentation for any purpose is hereby granted without fee,
\r
33 // provided that the above copyright notice appear in all copies and
\r
34 // that both that copyright notice and this permission notice appear
\r
35 // in supporting documentation. Hewlett-Packard Company makes no
\r
36 // representations about the suitability of this software for any
\r
37 // purpose. It is provided "as is" without express or implied warranty.
\r
39 #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
\r
40 #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
\r
42 #include <boost/intrusive/detail/config_begin.hpp>
\r
44 #include <boost/assert.hpp>
\r
45 #include <boost/intrusive/detail/pointer_type.hpp>
\r
46 #include <boost/intrusive/detail/pointer_to_other.hpp>
\r
47 #include <boost/get_pointer.hpp>
\r
48 #include <boost/type_traits/alignment_of.hpp>
\r
50 #include <boost/detail/no_exceptions_support.hpp>
\r
54 namespace intrusive {
\r
56 //! rbtree_algorithms provides basic algorithms to manipulate
\r
57 //! nodes forming a red-black tree. The insertion and deletion algorithms are
58 //! based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms
59 //! (MIT Press, 1990), except that
61 //! (1) the header node is maintained with links not only to the root
62 //! but also to the leftmost node of the tree, to enable constant time
63 //! begin(), and to the rightmost node of the tree, to enable linear time
64 //! performance when used with the generic set algorithms (set_union,
67 //! (2) when a node being deleted has two children its successor node is
68 //! relinked into its place, rather than copied, so that the only
69 //! iterators invalidated are those referring to the deleted node.
\r
71 //! rbtree_algorithms is configured with a NodeTraits class, which capsulates the
\r
72 //! information about the node to be manipulated. NodeTraits must support the
\r
73 //! following interface:
\r
75 //! <b>Typedefs</b>:
\r
77 //! <tt>node</tt>: The type of the node that forms the circular list
\r
79 //! <tt>node_ptr</tt>: A pointer to a node
\r
81 //! <tt>const_node_ptr</tt>: A pointer to a const node
\r
83 //! <tt>color</tt>: The type that can store the color of a node
\r
85 //! <b>Static functions</b>:
\r
87 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
\r
89 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
\r
91 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
\r
93 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
\r
95 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
\r
97 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
\r
99 //! <tt>static color get_color(const_node_ptr n);</tt>
\r
101 //! <tt>static void set_color(node_ptr n, color c);</tt>
\r
103 //! <tt>static color black();</tt>
\r
105 //! <tt>static color red();</tt>
\r
106 template<class NodeTraits>
\r
107 class rbtree_algorithms
\r
110 typedef typename NodeTraits::node node;
\r
113 typedef typename NodeTraits::node_ptr node_ptr;
\r
114 typedef typename NodeTraits::const_node_ptr const_node_ptr;
\r
115 typedef typename NodeTraits::color color;
\r
117 //! This type is the information that will be filled by insert_unique_check
\r
118 struct insert_commit_data
\r
120 insert_commit_data()
\r
128 //! <b>Requires</b>: header1 and header2 must be the header nodes
\r
131 //! <b>Effects</b>: Swaps two trees. After the function header1 will contain
\r
132 //! links to the second tree and header2 will have links to the first tree.
\r
134 //! <b>Complexity</b>: Constant.
\r
136 //! <b>Throws</b>: Nothing.
\r
137 static void swap_tree(node_ptr header1, node_ptr header2)
\r
139 if(header1 == header2)
\r
145 tmp = NodeTraits::get_parent(header1);
\r
146 NodeTraits::set_parent(header1, NodeTraits::get_parent(header2));
\r
147 NodeTraits::set_parent(header2, tmp);
\r
149 tmp = NodeTraits::get_left(header1);
\r
150 NodeTraits::set_left(header1, NodeTraits::get_left(header2));
\r
151 NodeTraits::set_left(header2, tmp);
\r
153 tmp = NodeTraits::get_right(header1);
\r
154 NodeTraits::set_right(header1, NodeTraits::get_right(header2));
\r
155 NodeTraits::set_right(header2, tmp);
\r
158 node_ptr h1_parent(NodeTraits::get_parent(header1));
\r
160 NodeTraits::set_parent(h1_parent, header1);
\r
163 NodeTraits::set_left(header1, header1);
\r
164 NodeTraits::set_right(header1, header1);
\r
167 node_ptr h2_parent(NodeTraits::get_parent(header2));
\r
168 if(NodeTraits::get_parent(header2)){
\r
169 NodeTraits::set_parent(h2_parent, header2);
\r
172 NodeTraits::set_left(header2, header2);
\r
173 NodeTraits::set_right(header2, header2);
\r
177 //! <b>Requires</b>: node is a tree node but not the header.
\r
179 //! <b>Effects</b>: Unlinks the node and rebalances the tree.
\r
181 //! <b>Complexity</b>: Average complexity is constant time.
\r
183 //! <b>Throws</b>: Nothing.
\r
184 static void unlink_and_rebalance(node_ptr node)
\r
186 if(NodeTraits::get_parent(node)){
\r
187 node_ptr x = NodeTraits::get_parent(node);
\r
188 while(!is_header(x))
\r
189 x = NodeTraits::get_parent(x);
\r
194 //! <b>Requires</b>: header is the header of a tree.
\r
196 //! <b>Effects</b>: Unlinks the leftmost node from the tree, and
\r
197 //! updates the header link to the new leftmost node.
\r
199 //! <b>Complexity</b>: Average complexity is constant time.
\r
201 //! <b>Throws</b>: Nothing.
\r
203 //! <b>Notes</b>: This function breaks the tree and the tree can
\r
204 //! only be used for more unlink_leftmost_without_rebalance calls.
\r
205 //! This function is normally used to achieve a step by step
\r
206 //! controlled destruction of the tree.
\r
207 static node_ptr unlink_leftmost_without_rebalance(node_ptr header)
\r
209 node_ptr leftmost = NodeTraits::get_left(header);
\r
210 if (leftmost == header)
\r
212 node_ptr leftmost_parent(NodeTraits::get_parent(leftmost));
\r
213 node_ptr leftmost_right (NodeTraits::get_right(leftmost));
\r
214 bool is_root = leftmost_parent == header;
\r
216 if (leftmost_right){
\r
217 NodeTraits::set_parent(leftmost_right, leftmost_parent);
\r
218 NodeTraits::set_left(header, minimum(leftmost_right));
\r
221 NodeTraits::set_parent(header, leftmost_right);
\r
223 NodeTraits::set_left(NodeTraits::get_parent(header), leftmost_right);
\r
226 NodeTraits::set_parent(header, 0);
\r
227 NodeTraits::set_left(header, header);
\r
228 NodeTraits::set_right(header, header);
\r
231 NodeTraits::set_left(leftmost_parent, 0);
\r
232 NodeTraits::set_left(header, leftmost_parent);
\r
237 //! <b>Requires</b>: node is a node of the tree or an node initialized
\r
240 //! <b>Effects</b>: Returns true if the node is initialized by init().
\r
242 //! <b>Complexity</b>: Constant time.
\r
244 //! <b>Throws</b>: Nothing.
\r
245 static bool unique(const_node_ptr node)
\r
246 { return NodeTraits::get_parent(node) == 0; }
\r
248 //! <b>Requires</b>: node is a node of the tree but it's not the header.
\r
250 //! <b>Effects</b>: Returns the number of nodes of the subtree.
\r
252 //! <b>Complexity</b>: Constant time.
\r
254 //! <b>Throws</b>: Nothing.
\r
255 static std::size_t count(const_node_ptr node)
\r
257 std::size_t result = 1;
\r
258 if(NodeTraits::get_left(node))
\r
259 result += count(NodeTraits::get_left(node));
\r
260 if(NodeTraits::get_right(node))
\r
261 result += count(NodeTraits::get_right(node));
\r
265 //! <b>Requires</b>: p is a node from the tree except the header.
\r
267 //! <b>Effects</b>: Returns the next node of the tree.
\r
269 //! <b>Complexity</b>: Average constant time.
\r
271 //! <b>Throws</b>: Nothing.
\r
272 static node_ptr next_node(node_ptr p)
\r
274 node_ptr p_right(NodeTraits::get_right(p));
\r
276 return minimum(p_right);
\r
279 node_ptr x = NodeTraits::get_parent(p);
\r
280 while(p == NodeTraits::get_right(x)){
\r
282 x = NodeTraits::get_parent(x);
\r
284 return NodeTraits::get_right(p) != x ? x : uncast(p);
\r
288 //! <b>Requires</b>: p is a node from the tree except the leftmost node.
\r
290 //! <b>Effects</b>: Returns the previous node of the tree.
\r
292 //! <b>Complexity</b>: Average constant time.
\r
294 //! <b>Throws</b>: Nothing.
\r
295 static node_ptr prev_node(node_ptr p)
\r
298 return NodeTraits::get_right(p); // p is header, return rightmost
\r
300 else if(NodeTraits::get_left(p)){
\r
301 return maximum(NodeTraits::get_left(p));
\r
304 node_ptr x = NodeTraits::get_parent(p);
\r
305 while(p == NodeTraits::get_left(x)){
\r
307 x = NodeTraits::get_parent(x);
\r
313 //! <b>Requires</b>: node must not be part of any tree.
\r
315 //! <b>Effects</b>: After the function unique(node) == true.
\r
317 //! <b>Complexity</b>: Constant.
\r
319 //! <b>Throws</b>: Nothing.
\r
321 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
\r
322 static void init(node_ptr node)
\r
324 NodeTraits::set_parent(node, 0);
\r
325 NodeTraits::set_left(node, 0);
\r
326 NodeTraits::set_right(node, 0);
\r
327 NodeTraits::set_color(node, NodeTraits::black());
\r
330 //! <b>Requires</b>: node must not be part of any tree.
\r
332 //! <b>Effects</b>: Initializes the header to represent an empty tree.
\r
333 //! unique(header) == true.
\r
335 //! <b>Complexity</b>: Constant.
\r
337 //! <b>Throws</b>: Nothing.
\r
339 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
\r
340 static void init_header(node_ptr header)
\r
342 NodeTraits::set_parent(header, 0);
\r
343 NodeTraits::set_left(header, header);
\r
344 NodeTraits::set_right(header, header);
\r
345 NodeTraits::set_color(header, NodeTraits::red());
\r
348 //! <b>Requires</b>: header must be the header of a tree, z a node
\r
349 //! of that tree and z != header.
\r
351 //! <b>Effects</b>: Erases node "z" from the tree with header "header".
\r
353 //! <b>Complexity</b>: Amortized constant time.
\r
355 //! <b>Throws</b>: Nothing.
\r
356 static node_ptr erase(node_ptr header, node_ptr z)
\r
360 node_ptr x_parent(0);
\r
361 node_ptr y_left(NodeTraits::get_left(y));
\r
362 node_ptr y_right(NodeTraits::get_right(y));
\r
364 x = y_right; // x might be null.
\r
366 else if(!y_right){ // z has exactly one non-null child. y == z.
\r
367 x = y_left; // x is not null.
\r
370 y = minimum (y_right);
\r
371 x = NodeTraits::get_right(y); // x might be null.
\r
375 // relink y in place of z. y is z's successor
\r
376 NodeTraits::set_parent(NodeTraits::get_left(z), y);
\r
377 NodeTraits::set_left(y, NodeTraits::get_left(z));
\r
378 if(y != NodeTraits::get_right(z)){
\r
379 x_parent = NodeTraits::get_parent(y);
\r
381 NodeTraits::set_parent(x, NodeTraits::get_parent(y));
\r
382 NodeTraits::set_left(NodeTraits::get_parent(y), x); // y must be a child of left_
\r
383 NodeTraits::set_right(y, NodeTraits::get_right(z));
\r
384 NodeTraits::set_parent(NodeTraits::get_right(z), y);
\r
388 replace_own (z, y, header);
\r
389 NodeTraits::set_parent(y, NodeTraits::get_parent(z));
\r
390 color tmp(NodeTraits::get_color(y));
\r
391 tmp = NodeTraits::get_color(y);
\r
392 NodeTraits::set_color(y, NodeTraits::get_color(z));
\r
393 NodeTraits::set_color(z, tmp);
\r
394 // std::swap(NodeTraits::get_color(y), NodeTraits::get_color(z));
\r
396 // y now points to node to be actually deleted
\r
399 x_parent = NodeTraits::get_parent(y);
\r
401 NodeTraits::set_parent(x, NodeTraits::get_parent(y));
\r
402 replace_own (z, x, header);
\r
403 if(NodeTraits::get_left(header) == z){
\r
404 NodeTraits::set_left(header, NodeTraits::get_right(z) == 0 ? // z->get_left() must be null also
\r
405 NodeTraits::get_parent(z) : // makes leftmost == header if z == root
\r
408 if(NodeTraits::get_right(header) == z){
\r
409 NodeTraits::set_right(header, NodeTraits::get_left(z) == 0 ? // z->get_right() must be null also
\r
410 NodeTraits::get_parent(z) : // makes rightmost == header if z == root
\r
414 if(NodeTraits::get_color(y) != NodeTraits::red()){
\r
415 while(x != NodeTraits::get_parent(header) && (x == 0 || NodeTraits::get_color(x) == NodeTraits::black())){
\r
416 if(x == NodeTraits::get_left(x_parent)){
\r
417 node_ptr w = NodeTraits::get_right(x_parent);
\r
418 if(NodeTraits::get_color(w) == NodeTraits::red()){
\r
419 NodeTraits::set_color(w, NodeTraits::black());
\r
420 NodeTraits::set_color(x_parent, NodeTraits::red());
\r
421 rotate_left(x_parent, header);
\r
422 w = NodeTraits::get_right(x_parent);
\r
424 if((NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()) &&
\r
425 (NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black())){
\r
426 NodeTraits::set_color(w, NodeTraits::red());
\r
428 x_parent = NodeTraits::get_parent(x_parent);
\r
431 if(NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()){
\r
432 NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());
\r
433 NodeTraits::set_color(w, NodeTraits::red());
\r
434 rotate_right(w, header);
\r
435 w = NodeTraits::get_right(x_parent);
\r
437 NodeTraits::set_color(w, NodeTraits::get_color(x_parent));
\r
438 NodeTraits::set_color(x_parent, NodeTraits::black());
\r
439 if(NodeTraits::get_right(w))
\r
440 NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());
\r
441 rotate_left(x_parent, header);
\r
446 // same as above, with right_ <-> left_.
\r
447 node_ptr w = NodeTraits::get_left(x_parent);
\r
448 if(NodeTraits::get_color(w) == NodeTraits::red()){
\r
449 NodeTraits::set_color(w, NodeTraits::black());
\r
450 NodeTraits::set_color(x_parent, NodeTraits::red());
\r
451 rotate_right(x_parent, header);
\r
452 w = NodeTraits::get_left(x_parent);
\r
454 if((NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()) &&
\r
455 (NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black())){
\r
456 NodeTraits::set_color(w, NodeTraits::red());
\r
458 x_parent = NodeTraits::get_parent(x_parent);
\r
461 if(NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()){
\r
462 NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());
\r
463 NodeTraits::set_color(w, NodeTraits::red());
\r
464 rotate_left(w, header);
\r
465 w = NodeTraits::get_left(x_parent);
\r
467 NodeTraits::set_color(w, NodeTraits::get_color(x_parent));
\r
468 NodeTraits::set_color(x_parent, NodeTraits::black());
\r
469 if(NodeTraits::get_left(w))
\r
470 NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());
\r
471 rotate_right(x_parent, header);
\r
477 NodeTraits::set_color(x, NodeTraits::black());
\r
482 //! <b>Requires</b>: "cloner" must be a function
\r
483 //! object taking a node_ptr and returning a new cloned node of it. "destroyer" must
\r
484 //! take a node_ptr and shouldn't throw.
\r
486 //! <b>Effects</b>: First empties target tree calling
\r
487 //! <tt>void destroyer::operator()(node_ptr)</tt> for every node of the tree
\r
488 //! except the header.
\r
490 //! Then, duplicates the entire tree pointed by "source_header" cloning each
\r
491 //! source node with <tt>node_ptr Cloner::operator()(node_ptr)</tt> to obtain
\r
492 //! the nodes of the target tree. If "cloner" throws, the cloned target nodes
\r
493 //! are destroyed using <tt>void destroyer(node_ptr)</tt>.
\r
495 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
\r
496 //! number of elements of tree target tree when calling this function.
\r
498 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are destroyed.
\r
499 template <class Cloner, class Destroyer>
\r
500 static void clone_tree
\r
501 (const_node_ptr source_header, node_ptr target_header, Cloner cloner, Destroyer destroyer)
\r
503 if(!unique(target_header)){
\r
505 while((p = unlink_leftmost_without_rebalance(target_header))){
\r
510 node_ptr source_root = NodeTraits::get_parent(source_header);
\r
514 NodeTraits::set_parent
\r
516 , deep_clone_node(source_root, target_header, cloner, destroyer));
\r
517 NodeTraits::set_left(target_header, minimum(NodeTraits::get_parent(target_header)));
\r
518 NodeTraits::set_right(target_header, maximum(NodeTraits::get_parent(target_header)));
\r
521 //! <b>Requires</b>: "header" must be the header node of a tree.
\r
522 //! KeyNodePtrCompare is a function object that induces a strict weak
\r
523 //! ordering compatible with the strict weak ordering used to create the
\r
524 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
\r
526 //! <b>Effects</b>: Returns an node_ptr to the first element that is
\r
527 //! not less than "key" according to "comp" or "header" if that element does
\r
530 //! <b>Complexity</b>: Logarithmic.
\r
532 //! <b>Throws</b>: If "comp" throws.
\r
533 template<class KeyType, class KeyNodePtrCompare>
\r
534 static node_ptr lower_bound
\r
535 (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)
\r
537 node_ptr y = uncast(header);
\r
538 node_ptr x = NodeTraits::get_parent(header);
\r
541 x = NodeTraits::get_right(x);
\r
545 x = NodeTraits::get_left(x);
\r
551 //! <b>Requires</b>: "header" must be the header node of a tree.
\r
552 //! KeyNodePtrCompare is a function object that induces a strict weak
\r
553 //! ordering compatible with the strict weak ordering used to create the
\r
554 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
\r
556 //! <b>Effects</b>: Returns an node_ptr to the first element that is greater
\r
557 //! than "key" according to "comp" or "header" if that element does not exist.
\r
559 //! <b>Complexity</b>: Logarithmic.
\r
561 //! <b>Throws</b>: If "comp" throws.
\r
562 template<class KeyType, class KeyNodePtrCompare>
\r
563 static node_ptr upper_bound
\r
564 (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)
\r
566 node_ptr y = uncast(header);
\r
567 node_ptr x = NodeTraits::get_parent(header);
\r
571 x = NodeTraits::get_left(x);
\r
574 x = NodeTraits::get_right(x);
\r
580 //! <b>Requires</b>: "header" must be the header node of a tree.
\r
581 //! KeyNodePtrCompare is a function object that induces a strict weak
\r
582 //! ordering compatible with the strict weak ordering used to create the
\r
583 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
\r
585 //! <b>Effects</b>: Returns an node_ptr to the element that is equivalent to
\r
586 //! "key" according to "comp" or "header" if that element does not exist.
\r
588 //! <b>Complexity</b>: Logarithmic.
\r
590 //! <b>Throws</b>: If "comp" throws.
\r
591 template<class KeyType, class KeyNodePtrCompare>
\r
592 static node_ptr find
\r
593 (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)
\r
595 node_ptr end = uncast(header);
\r
596 node_ptr y = lower_bound(header, key, comp);
\r
597 return (y == end || comp(key, y)) ? end : y;
\r
600 //! <b>Requires</b>: "header" must be the header node of a tree.
\r
601 //! KeyNodePtrCompare is a function object that induces a strict weak
\r
602 //! ordering compatible with the strict weak ordering used to create the
\r
603 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
\r
605 //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
\r
606 //! all elements that are equivalent to "key" according to "comp" or an
\r
607 //! empty range that indicates the position where those elements would be
\r
608 //! if they there are no equivalent elements.
\r
610 //! <b>Complexity</b>: Logarithmic.
\r
612 //! <b>Throws</b>: If "comp" throws.
\r
613 template<class KeyType, class KeyNodePtrCompare>
\r
614 static std::pair<node_ptr, node_ptr> equal_range
\r
615 (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)
\r
617 node_ptr y = uncast(header);
\r
618 node_ptr x = NodeTraits::get_parent(header);
\r
622 x = NodeTraits::get_right(x);
\r
624 else if(comp(key, x)){
\r
626 x = NodeTraits::get_left(x);
\r
629 node_ptr xu(x), yu(y);
\r
630 y = x, x = NodeTraits::get_left(x);
\r
631 xu = NodeTraits::get_right(xu);
\r
635 x = NodeTraits::get_right(x);
\r
639 x = NodeTraits::get_left(x);
\r
646 xu = NodeTraits::get_left(xu);
\r
649 xu = NodeTraits::get_right(xu);
\r
652 return std::pair<node_ptr,node_ptr>(y, yu);
\r
655 return std::pair<node_ptr,node_ptr>(y, y);
\r
658 //! <b>Requires</b>: "h" must be the header node of a tree.
\r
659 //! NodePtrCompare is a function object that induces a strict weak
\r
660 //! ordering compatible with the strict weak ordering used to create the
\r
661 //! the tree. NodePtrCompare compares two node_ptrs.
\r
663 //! <b>Effects</b>: Inserts new_node into the tree before the upper bound
\r
664 //! according to "comp".
\r
666 //! <b>Complexity</b>: Average complexity for insert element is at
\r
667 //! most logarithmic.
\r
669 //! <b>Throws</b>: If "comp" throws.
\r
670 template<class NodePtrCompare>
\r
671 static node_ptr insert_equal_upper_bound
\r
672 (node_ptr h, node_ptr new_node, NodePtrCompare comp)
\r
675 node_ptr x(NodeTraits::get_parent(y));
\r
679 x = comp(new_node, x) ?
\r
680 NodeTraits::get_left(x) : NodeTraits::get_right(x);
\r
683 bool link_left = (y == h) ||
\r
685 link_and_balance(new_node, y, link_left, h);
\r
689 //! <b>Requires</b>: "h" must be the header node of a tree.
\r
690 //! NodePtrCompare is a function object that induces a strict weak
\r
691 //! ordering compatible with the strict weak ordering used to create the
\r
692 //! the tree. NodePtrCompare compares two node_ptrs.
\r
694 //! <b>Effects</b>: Inserts new_node into the tree before the lower bound
\r
695 //! according to "comp".
\r
697 //! <b>Complexity</b>: Average complexity for insert element is at
\r
698 //! most logarithmic.
\r
700 //! <b>Throws</b>: If "comp" throws.
\r
701 template<class NodePtrCompare>
\r
702 static node_ptr insert_equal_lower_bound
\r
703 (node_ptr h, node_ptr new_node, NodePtrCompare comp)
\r
706 node_ptr x(NodeTraits::get_parent(y));
\r
710 x = !comp(x, new_node) ?
\r
711 NodeTraits::get_left(x) : NodeTraits::get_right(x);
\r
714 bool link_left = (y == h) ||
\r
715 !comp(y, new_node);
\r
716 link_and_balance(new_node, y, link_left, h);
\r
720 //! <b>Requires</b>: "header" must be the header node of a tree.
\r
721 //! NodePtrCompare is a function object that induces a strict weak
\r
722 //! ordering compatible with the strict weak ordering used to create the
\r
723 //! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from
\r
724 //! the "header"'s tree.
\r
726 //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to
\r
727 //! where it will be inserted. If "hint" is the upper_bound
\r
728 //! the insertion takes constant time (two comparisons in the worst case).
\r
730 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
\r
731 //! constant time if new_node is inserted immediately before "hint".
\r
733 //! <b>Throws</b>: If "comp" throws.
\r
734 template<class NodePtrCompare>
\r
735 static node_ptr insert_equal
\r
736 (node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp)
\r
738 if(hint == header || !comp(hint, new_node)){
\r
739 node_ptr prev(hint);
\r
740 if(hint == NodeTraits::get_left(header) ||
\r
741 !comp(new_node, (prev = prev_node(hint)))){
\r
742 bool link_left = unique(header) || !NodeTraits::get_left(hint);
\r
743 link_and_balance(new_node, link_left ? hint : prev, link_left, header);
\r
747 return insert_equal_upper_bound(header, new_node, comp);
\r
751 return insert_equal_lower_bound(header, new_node, comp);
\r
755 //! <b>Requires</b>: "header" must be the header node of a tree.
\r
756 //! KeyNodePtrCompare is a function object that induces a strict weak
\r
757 //! ordering compatible with the strict weak ordering used to create the
\r
758 //! the tree. NodePtrCompare compares KeyType with a node_ptr.
\r
760 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
\r
761 //! tree according to "comp" and obtains the needed information to realize
\r
762 //! a constant-time node insertion if there is no equivalent node.
\r
764 //! <b>Returns</b>: If an equivalent node is already present
\r
765 //! returns a pair containing a node_ptr to the already present node
\r
766 //! and false. If there is not equivalent key can be inserted returns true
\r
767 //! in the returned pair's boolean and fills "commit_data" that is meant to
\r
768 //! be used with the "insert_commit" function to achieve a constant-time
\r
769 //! insertion function.
\r
771 //! <b>Complexity</b>: Average complexity is at most logarithmic.
\r
773 //! <b>Throws</b>: If "comp" throws.
\r
775 //! <b>Notes</b>: This function is used to improve performance when constructing
\r
776 //! a node is expensive and the user does not want to have two equivalent nodes
\r
777 //! in the tree: if an equivalent node is already present
\r
778 //! the constructed object must be discarded. Many times, the part of the
\r
779 //! node that is used to impose the order is much cheaper to construct
\r
780 //! than the node and this function offers the possibility to use that part
\r
781 //! to check if the insertion will be successful.
\r
783 //! If the check is successful, the user can construct the node and use
\r
784 //! "insert_commit" to insert the node in constant-time. This gives a total
\r
785 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
\r
787 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only
\r
788 //! if no more objects are inserted or erased from the set.
\r
789 template<class KeyType, class KeyNodePtrCompare>
\r
790 static std::pair<node_ptr, bool> insert_unique_check
\r
791 (const_node_ptr header, const KeyType &key
\r
792 ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
\r
794 node_ptr h(uncast(header));
\r
796 node_ptr x(NodeTraits::get_parent(y));
\r
799 //Find the upper bound, cache the previous value and if we should
\r
800 //store it in the left or right node
\r
801 bool left_child = true;
\r
804 x = (left_child = comp(key, x)) ?
\r
805 NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x));
\r
808 //Since we've found the upper bound there is no other value with the same key if:
\r
809 // - There is no previous node
\r
810 // - The previous node is less than the key
\r
811 if(!prev || comp(prev, key)){
\r
812 commit_data.link_left = left_child;
\r
813 commit_data.node = y;
\r
814 return std::pair<node_ptr, bool>(node_ptr(), true);
\r
816 //If the previous value was not less than key, it means that it's equal
\r
817 //(because we've checked the upper bound)
\r
819 return std::pair<node_ptr, bool>(prev, false);
\r
823 //! <b>Requires</b>: "header" must be the header node of a tree.
\r
824 //! KeyNodePtrCompare is a function object that induces a strict weak
\r
825 //! ordering compatible with the strict weak ordering used to create the
\r
826 //! the tree. NodePtrCompare compares KeyType with a node_ptr.
\r
827 //! "hint" is node from the "header"'s tree.
\r
829 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
\r
830 //! tree according to "comp" using "hint" as a hint to where it should be
\r
831 //! inserted and obtains the needed information to realize
\r
832 //! a constant-time node insertion if there is no equivalent node.
\r
833 //! If "hint" is the upper_bound the function has constant time
\r
834 //! complexity (two comparisons in the worst case).
\r
836 //! <b>Returns</b>: If an equivalent node is already present
\r
837 //! returns a pair containing a node_ptr to the already present node
\r
838 //! and false. If there is not equivalent key can be inserted returns true
\r
839 //! in the returned pair's boolean and fills "commit_data" that is meant to
\r
840 //! be used with the "insert_commit" function to achieve a constant-time
\r
841 //! insertion function.
\r
843 //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is
\r
844 //! amortized constant time if new_node should be inserted immediately before "hint".
\r
846 //! <b>Throws</b>: If "comp" throws.
\r
848 //! <b>Notes</b>: This function is used to improve performance when constructing
\r
849 //! a node is expensive and the user does not want to have two equivalent nodes
\r
850 //! in the tree: if an equivalent node is already present
\r
851 //! the constructed object must be discarded. Many times, the part of the
\r
852 //! node that is used to impose the order is much cheaper to construct
\r
853 //! than the node and this function offers the possibility to use that part
\r
854 //! to check if the insertion will be successful.
\r
856 //! If the check is successful, the user can construct the node and use
\r
857 //! "insert_commit" to insert the node in constant-time. This gives a total
\r
858 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
\r
860 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only
\r
861 //! if no more objects are inserted or erased from the set.
\r
862 template<class KeyType, class KeyNodePtrCompare>
\r
863 static std::pair<node_ptr, bool> insert_unique_check
\r
864 (const_node_ptr header, node_ptr hint, const KeyType &key
\r
865 ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
\r
867 //hint must be bigger than the key
\r
868 if(hint == header || comp(key, hint)){
\r
869 node_ptr prev = hint;
\r
870 //The previous value should be less than the key
\r
871 if(prev == NodeTraits::get_left(header) || comp((prev = prev_node(hint)), key)){
\r
872 commit_data.link_left = unique(header) || !NodeTraits::get_left(hint);
\r
873 commit_data.node = commit_data.link_left ? hint : prev;
\r
874 return std::pair<node_ptr, bool>(node_ptr(), true);
\r
877 return insert_unique_check(header, key, comp, commit_data);
\r
878 //return std::pair<node_ptr, bool>(prev, false);
\r
881 //The hint was wrong, use hintless insert
\r
883 return insert_unique_check(header, key, comp, commit_data);
\r
887 //! <b>Requires</b>: "header" must be the header node of a tree.
\r
888 //! "commit_data" must have been obtained from a previous call to
\r
889 //! "insert_unique_check". No objects should have been inserted or erased
\r
890 //! from the set between the "insert_unique_check" that filled "commit_data"
\r
891 //! and the call to "insert_commit".
\r
894 //! <b>Effects</b>: Inserts new_node in the set using the information obtained
\r
895 //! from the "commit_data" that a previous "insert_check" filled.
\r
897 //! <b>Complexity</b>: Constant time.
\r
899 //! <b>Throws</b>: Nothing.
\r
901 //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been
\r
902 //! previously executed to fill "commit_data". No value should be inserted or
\r
903 //! erased between the "insert_check" and "insert_commit" calls.
\r
904 static void insert_unique_commit
\r
905 (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data)
\r
907 //Check if commit_data has not been initialized by a insert_unique_check call.
\r
908 BOOST_ASSERT(commit_data.node != 0);
\r
909 link_and_balance(new_value, commit_data.node, commit_data.link_left, header);
\r
914 static node_ptr uncast(const_node_ptr ptr)
\r
916 using boost::get_pointer;
\r
917 return node_ptr(const_cast<node*>(get_pointer(ptr)));
\r
920 //! <b>Requires</b>: z is the node to be inserted, par is its parent,
\r
921 //! left, indicates if z should be a left node of par and header is the header
\r
924 //! <b>Effects</b>: If left is true links z as a left child of par or as a right
\r
925 //! child otherwise. After that rebalances the tree.
\r
927 //! <b>Complexity</b>: Average constant time.???
\r
929 //! <b>Throws</b>: Nothing.
\r
930 static void link_and_balance (node_ptr z, node_ptr par, bool left, node_ptr header)
\r
933 NodeTraits::set_parent(header, z);
\r
934 NodeTraits::set_right(header, z);
\r
935 NodeTraits::set_left(header, z);
\r
938 NodeTraits::set_left(par, z);
\r
939 if(par == NodeTraits::get_left(header))
\r
940 NodeTraits::set_left(header, z);
\r
943 NodeTraits::set_right(par, z);
\r
944 if(par == NodeTraits::get_right(header))
\r
945 NodeTraits::set_right(header, z);
\r
947 NodeTraits::set_parent(z, par);
\r
948 NodeTraits::set_right(z, 0);
\r
949 NodeTraits::set_left(z, 0);
\r
950 rebalance(z, header);
\r
953 //! <b>Requires</b>: p is a node of a tree but not the header.
\r
955 //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
\r
957 //! <b>Complexity</b>: Logarithmic to the size of the subtree.
\r
959 //! <b>Throws</b>: Nothing.
\r
960 static node_ptr minimum (node_ptr p)
\r
962 for(node_ptr p_left = NodeTraits::get_left(p)
\r
964 ;p_left = NodeTraits::get_left(p)){
\r
970 //! <b>Requires</b>: p is a node of a tree but not the header.
\r
972 //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
\r
974 //! <b>Complexity</b>: Logarithmic to the size of the subtree.
\r
976 //! <b>Throws</b>: Nothing.
\r
977 static node_ptr maximum(node_ptr p)
\r
979 for(node_ptr p_right = NodeTraits::get_right(p)
\r
981 ;p_right = NodeTraits::get_right(p)){
\r
987 //! <b>Requires</b>: p is a node of a tree.
\r
989 //! <b>Effects</b>: Returns true if p is the header of the tree.
\r
991 //! <b>Complexity</b>: Constant.
\r
993 //! <b>Throws</b>: Nothing.
\r
994 static bool is_header(const_node_ptr p)
\r
996 return NodeTraits::get_color(p) == NodeTraits::red() &&
\r
997 NodeTraits::get_parent(NodeTraits::get_parent(p)) == p;
\r
1000 //! <b>Requires</b>: p is a node of a tree.
\r
1002 //! <b>Effects</b>: Returns true if p is a left child.
\r
1004 //! <b>Complexity</b>: Constant.
\r
1006 //! <b>Throws</b>: Nothing.
\r
1007 static bool is_left_child(node_ptr p)
\r
1008 { return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; }
\r
1010 //! <b>Requires</b>: p is a node of a tree.
\r
1012 //! <b>Effects</b>: Returns true if p is a right child.
\r
1014 //! <b>Complexity</b>: Constant.
\r
1016 //! <b>Throws</b>: Nothing.
\r
1017 static bool is_right_child (node_ptr p)
\r
1018 { return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; }
\r
1020 static void replace_own (node_ptr own, node_ptr x, node_ptr header)
\r
1022 if(NodeTraits::get_parent(header) == own)
\r
1023 NodeTraits::set_parent(header, x);
\r
1024 else if(is_left_child(own))
\r
1025 NodeTraits::set_left(NodeTraits::get_parent(own), x);
\r
1027 NodeTraits::set_right(NodeTraits::get_parent(own), x);
\r
1030 static void rotate_left(node_ptr p, node_ptr header)
\r
1032 node_ptr x = NodeTraits::get_right(p);
\r
1033 NodeTraits::set_right(p, NodeTraits::get_left(x));
\r
1034 if(NodeTraits::get_left(x) != 0)
\r
1035 NodeTraits::set_parent(NodeTraits::get_left(x), p);
\r
1036 NodeTraits::set_parent(x, NodeTraits::get_parent(p));
\r
1037 replace_own (p, x, header);
\r
1038 NodeTraits::set_left(x, p);
\r
1039 NodeTraits::set_parent(p, x);
\r
1042 static void rotate_right(node_ptr p, node_ptr header)
\r
1044 node_ptr x(NodeTraits::get_left(p));
\r
1045 node_ptr x_right(NodeTraits::get_right(x));
\r
1046 NodeTraits::set_left(p, x_right);
\r
1048 NodeTraits::set_parent(x_right, p);
\r
1049 NodeTraits::set_parent(x, NodeTraits::get_parent(p));
\r
1050 replace_own (p, x, header);
\r
1051 NodeTraits::set_right(x, p);
\r
1052 NodeTraits::set_parent(p, x);
\r
1055 static void rebalance(node_ptr p, node_ptr header)
\r
1057 NodeTraits::set_color(p, NodeTraits::red());
\r
1058 while(p != NodeTraits::get_parent(header) && NodeTraits::get_color(NodeTraits::get_parent(p)) == NodeTraits::red()){
\r
1059 node_ptr p_parent(NodeTraits::get_parent(p));
\r
1060 node_ptr p_parent_parent(NodeTraits::get_parent(p_parent));
\r
1061 if(is_left_child(p_parent)){
\r
1062 node_ptr x = NodeTraits::get_right(p_parent_parent);
\r
1063 if(x && NodeTraits::get_color(x) == NodeTraits::red()){
\r
1064 NodeTraits::set_color(p_parent, NodeTraits::black());
\r
1065 NodeTraits::set_color(p_parent_parent, NodeTraits::red());
\r
1066 NodeTraits::set_color(x, NodeTraits::black());
\r
1067 p = p_parent_parent;
\r
1070 if(!is_left_child(p)){
\r
1072 rotate_left(p, header);
\r
1074 node_ptr new_p_parent(NodeTraits::get_parent(p));
\r
1075 node_ptr new_p_parent_parent(NodeTraits::get_parent(new_p_parent));
\r
1076 NodeTraits::set_color(new_p_parent, NodeTraits::black());
\r
1077 NodeTraits::set_color(new_p_parent_parent, NodeTraits::red());
\r
1078 rotate_right(new_p_parent_parent, header);
\r
1082 node_ptr x = NodeTraits::get_left(p_parent_parent);
\r
1083 if(x && NodeTraits::get_color(x) == NodeTraits::red()){
\r
1084 NodeTraits::set_color(p_parent, NodeTraits::black());
\r
1085 NodeTraits::set_color(p_parent_parent, NodeTraits::red());
\r
1086 NodeTraits::set_color(x, NodeTraits::black());
\r
1087 p = p_parent_parent;
\r
1090 if(is_left_child(p)){
\r
1092 rotate_right(p, header);
\r
1094 node_ptr new_p_parent(NodeTraits::get_parent(p));
\r
1095 node_ptr new_p_parent_parent(NodeTraits::get_parent(new_p_parent));
\r
1096 NodeTraits::set_color(new_p_parent, NodeTraits::black());
\r
1097 NodeTraits::set_color(new_p_parent_parent, NodeTraits::red());
\r
1098 rotate_left(new_p_parent_parent, header);
\r
1102 NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black());
\r
1105 template <class Cloner, class Destroyer>
\r
1106 static node_ptr deep_clone_node
\r
1107 (node_ptr source_root, node_ptr new_parent, Cloner cloner, Destroyer destroyer)
\r
1109 // structural copy. source_root and new_parent must be non-null.
\r
1110 node_ptr top = cloner(source_root);
\r
1111 NodeTraits::set_parent(top, new_parent);
\r
1114 if(NodeTraits::get_right(source_root)){
\r
1115 NodeTraits::set_right
\r
1116 (top, deep_clone_node(NodeTraits::get_right(source_root), top
\r
1117 ,cloner, destroyer));
\r
1120 source_root = NodeTraits::get_left(source_root);
\r
1122 while(source_root){
\r
1123 node_ptr y = cloner(source_root);
\r
1124 NodeTraits::set_left(new_parent, y);
\r
1125 NodeTraits::set_parent(y, new_parent);
\r
1127 if(NodeTraits::get_right(source_root)){
\r
1128 NodeTraits::set_right(y, deep_clone_node(NodeTraits::get_right(source_root), y
\r
1129 ,cloner, destroyer));
\r
1132 source_root = NodeTraits::get_left(source_root);
\r
1136 deep_destroy_node(top, destroyer);
\r
1143 template<class Destroyer>
\r
1144 static void deep_destroy_node(node_ptr x, Destroyer destroyer)
\r
1146 // erase without rebalancing
\r
1148 deep_destroy_node(NodeTraits::get_right(x), destroyer);
\r
1149 node_ptr y = NodeTraits::get_left(x);
\r
1156 } //namespace intrusive
\r
1157 } //namespace boost
\r
1159 #include <boost/intrusive/detail/config_end.hpp>
\r
1161 #endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
\r