1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2007-2014
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)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
13 #ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP
14 #define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP
21 #include <boost/intrusive/detail/config_begin.hpp>
22 #include <boost/intrusive/intrusive_fwd.hpp>
23 #include <boost/intrusive/detail/assert.hpp>
24 #include <boost/intrusive/detail/uncast.hpp>
25 #include <boost/intrusive/detail/math.hpp>
26 #include <boost/intrusive/detail/algo_type.hpp>
34 //! This type is the information that will be filled by insert_unique_check
35 template <class NodePtr>
36 struct insert_commit_data_t
38 insert_commit_data_t()
46 template <class NodePtr>
47 struct data_for_rebalance_t
56 template<class ValueTraits, class NodePtrCompare, class ExtraChecker>
57 struct bstree_node_checker
60 typedef ExtraChecker base_checker_t;
61 typedef ValueTraits value_traits;
62 typedef typename value_traits::node_traits node_traits;
63 typedef typename node_traits::const_node_ptr const_node_ptr;
66 : public base_checker_t::return_type
68 return_type() : min_key_node_ptr(const_node_ptr()), max_key_node_ptr(const_node_ptr()), node_count(0) {}
70 const_node_ptr min_key_node_ptr;
71 const_node_ptr max_key_node_ptr;
75 bstree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
76 : base_checker_t(extra_checker), comp_(comp)
79 void operator () (const const_node_ptr& p,
80 const return_type& check_return_left, const return_type& check_return_right,
81 return_type& check_return)
83 if (check_return_left.max_key_node_ptr)
84 BOOST_INTRUSIVE_INVARIANT_ASSERT(!comp_(p, check_return_left.max_key_node_ptr));
85 if (check_return_right.min_key_node_ptr)
86 BOOST_INTRUSIVE_INVARIANT_ASSERT(!comp_(check_return_right.min_key_node_ptr, p));
87 check_return.min_key_node_ptr = node_traits::get_left(p)? check_return_left.min_key_node_ptr : p;
88 check_return.max_key_node_ptr = node_traits::get_right(p)? check_return_right.max_key_node_ptr : p;
89 check_return.node_count = check_return_left.node_count + check_return_right.node_count + 1;
90 base_checker_t::operator()(p, check_return_left, check_return_right, check_return);
93 const NodePtrCompare comp_;
102 //! This is an implementation of a binary search tree.
103 //! A node in the search tree has references to its children and its parent. This
104 //! is to allow traversal of the whole tree from a given node making the
105 //! implementation of iterator a pointer to a node.
106 //! At the top of the tree a node is used specially. This node's parent pointer
107 //! is pointing to the root of the tree. Its left pointer points to the
108 //! leftmost node in the tree and the right pointer to the rightmost one.
109 //! This node is used to represent the end-iterator.
112 //! header------------------------------>| |
114 //! +----------(left)--------| |--------(right)---------+
121 //! root of tree ..|......................> | | |
124 //! | +-------+---------+-------+ |
130 //! | +---------+ +---------+ |
134 //! | +--+---------+--+ +--+---------+--+ |
138 //! | +---+-----+ +-----+---+ +---+-----+ +-----+---+ |
139 //! +-->| | | | | | | |<--+
140 //! | A | | C | | E | | G |
142 //! +---------+ +---------+ +---------+ +---------+
144 //! bstree_algorithms is configured with a NodeTraits class, which encapsulates the
145 //! information about the node to be manipulated. NodeTraits must support the
146 //! following interface:
150 //! <tt>node</tt>: The type of the node that forms the binary search tree
152 //! <tt>node_ptr</tt>: A pointer to a node
154 //! <tt>const_node_ptr</tt>: A pointer to a const node
156 //! <b>Static functions</b>:
158 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
160 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
162 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
164 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
166 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
168 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
169 template<class NodeTraits>
170 class bstree_algorithms
173 typedef typename NodeTraits::node node;
174 typedef NodeTraits node_traits;
175 typedef typename NodeTraits::node_ptr node_ptr;
176 typedef typename NodeTraits::const_node_ptr const_node_ptr;
177 typedef insert_commit_data_t<node_ptr> insert_commit_data;
178 typedef data_for_rebalance_t<node_ptr> data_for_rebalance;
183 template<class Disposer>
184 struct dispose_subtree_disposer
186 dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree)
187 : disposer_(&disp), subtree_(subtree)
193 ~dispose_subtree_disposer()
196 dispose_subtree(subtree_, *disposer_);
200 const node_ptr subtree_;
206 //! <b>Requires</b>: 'header' is the header node of a tree.
208 //! <b>Effects</b>: Returns the first node of the tree, the header if the tree is empty.
210 //! <b>Complexity</b>: Constant time.
212 //! <b>Throws</b>: Nothing.
213 static node_ptr begin_node(const const_node_ptr & header)
214 { return node_traits::get_left(header); }
216 //! <b>Requires</b>: 'header' is the header node of a tree.
218 //! <b>Effects</b>: Returns the header of the tree.
220 //! <b>Complexity</b>: Constant time.
222 //! <b>Throws</b>: Nothing.
223 static node_ptr end_node(const const_node_ptr & header)
224 { return detail::uncast(header); }
226 //! <b>Requires</b>: 'header' is the header node of a tree.
228 //! <b>Effects</b>: Returns the root of the tree if any, header otherwise
230 //! <b>Complexity</b>: Constant time.
232 //! <b>Throws</b>: Nothing.
233 static node_ptr root_node(const const_node_ptr & header)
235 node_ptr p = node_traits::get_parent(header);
236 return p ? p : detail::uncast(header);
239 //! <b>Requires</b>: 'node' is a node of the tree or a node initialized
240 //! by init(...) or init_node.
242 //! <b>Effects</b>: Returns true if the node is initialized by init() or init_node().
244 //! <b>Complexity</b>: Constant time.
246 //! <b>Throws</b>: Nothing.
247 static bool unique(const const_node_ptr & node)
248 { return !NodeTraits::get_parent(node); }
250 //! <b>Requires</b>: 'node' is a node of the tree or a header node.
252 //! <b>Effects</b>: Returns the header of the tree.
254 //! <b>Complexity</b>: Logarithmic.
256 //! <b>Throws</b>: Nothing.
257 static node_ptr get_header(const const_node_ptr & node)
259 node_ptr n(detail::uncast(node));
260 node_ptr p(NodeTraits::get_parent(node));
261 //If p is null, then n is the header of an empty tree
263 //Non-empty tree, check if n is neither root nor header
264 node_ptr pp(NodeTraits::get_parent(p));
265 //If granparent is not equal to n, then n is neither root nor header,
266 //the try the fast path
271 pp = NodeTraits::get_parent(pp);
275 //Check if n is root or header when size() > 0
276 else if(!is_header(n)){
282 node_ptr h = detail::uncast(node);
283 node_ptr p = NodeTraits::get_parent(node);
286 p = NodeTraits::get_parent(p);
294 //! <b>Requires</b>: node1 and node2 can't be header nodes
297 //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
298 //! in the position node2 before the function. node2 will be inserted in the
299 //! position node1 had before the function.
301 //! <b>Complexity</b>: Logarithmic.
303 //! <b>Throws</b>: Nothing.
305 //! <b>Note</b>: This function will break container ordering invariants if
306 //! node1 and node2 are not equivalent according to the ordering rules.
308 //!Experimental function
309 static void swap_nodes(const node_ptr & node1, const node_ptr & node2)
314 node_ptr header1(get_header(node1)), header2(get_header(node2));
315 swap_nodes(node1, header1, node2, header2);
318 //! <b>Requires</b>: node1 and node2 can't be header nodes
319 //! of two trees with header header1 and header2.
321 //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
322 //! in the position node2 before the function. node2 will be inserted in the
323 //! position node1 had before the function.
325 //! <b>Complexity</b>: Constant.
327 //! <b>Throws</b>: Nothing.
329 //! <b>Note</b>: This function will break container ordering invariants if
330 //! node1 and node2 are not equivalent according to the ordering rules.
332 //!Experimental function
333 static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2)
338 //node1 and node2 must not be header nodes
339 //BOOST_INTRUSIVE_INVARIANT_ASSERT((header1 != node1 && header2 != node2));
340 if(header1 != header2){
341 //Update header1 if necessary
342 if(node1 == NodeTraits::get_left(header1)){
343 NodeTraits::set_left(header1, node2);
346 if(node1 == NodeTraits::get_right(header1)){
347 NodeTraits::set_right(header1, node2);
350 if(node1 == NodeTraits::get_parent(header1)){
351 NodeTraits::set_parent(header1, node2);
354 //Update header2 if necessary
355 if(node2 == NodeTraits::get_left(header2)){
356 NodeTraits::set_left(header2, node1);
359 if(node2 == NodeTraits::get_right(header2)){
360 NodeTraits::set_right(header2, node1);
363 if(node2 == NodeTraits::get_parent(header2)){
364 NodeTraits::set_parent(header2, node1);
368 //If both nodes are from the same tree
369 //Update header if necessary
370 if(node1 == NodeTraits::get_left(header1)){
371 NodeTraits::set_left(header1, node2);
373 else if(node2 == NodeTraits::get_left(header2)){
374 NodeTraits::set_left(header2, node1);
377 if(node1 == NodeTraits::get_right(header1)){
378 NodeTraits::set_right(header1, node2);
380 else if(node2 == NodeTraits::get_right(header2)){
381 NodeTraits::set_right(header2, node1);
384 if(node1 == NodeTraits::get_parent(header1)){
385 NodeTraits::set_parent(header1, node2);
387 else if(node2 == NodeTraits::get_parent(header2)){
388 NodeTraits::set_parent(header2, node1);
391 //Adjust data in nodes to be swapped
392 //so that final link swap works as expected
393 if(node1 == NodeTraits::get_parent(node2)){
394 NodeTraits::set_parent(node2, node2);
396 if(node2 == NodeTraits::get_right(node1)){
397 NodeTraits::set_right(node1, node1);
400 NodeTraits::set_left(node1, node1);
403 else if(node2 == NodeTraits::get_parent(node1)){
404 NodeTraits::set_parent(node1, node1);
406 if(node1 == NodeTraits::get_right(node2)){
407 NodeTraits::set_right(node2, node2);
410 NodeTraits::set_left(node2, node2);
415 //Now swap all the links
418 temp = NodeTraits::get_left(node1);
419 NodeTraits::set_left(node1, NodeTraits::get_left(node2));
420 NodeTraits::set_left(node2, temp);
422 temp = NodeTraits::get_right(node1);
423 NodeTraits::set_right(node1, NodeTraits::get_right(node2));
424 NodeTraits::set_right(node2, temp);
426 temp = NodeTraits::get_parent(node1);
427 NodeTraits::set_parent(node1, NodeTraits::get_parent(node2));
428 NodeTraits::set_parent(node2, temp);
430 //Now adjust adjacent nodes for newly inserted node 1
431 if((temp = NodeTraits::get_left(node1))){
432 NodeTraits::set_parent(temp, node1);
434 if((temp = NodeTraits::get_right(node1))){
435 NodeTraits::set_parent(temp, node1);
437 if((temp = NodeTraits::get_parent(node1)) &&
438 //The header has been already updated so avoid it
440 if(NodeTraits::get_left(temp) == node2){
441 NodeTraits::set_left(temp, node1);
443 if(NodeTraits::get_right(temp) == node2){
444 NodeTraits::set_right(temp, node1);
447 //Now adjust adjacent nodes for newly inserted node 2
448 if((temp = NodeTraits::get_left(node2))){
449 NodeTraits::set_parent(temp, node2);
451 if((temp = NodeTraits::get_right(node2))){
452 NodeTraits::set_parent(temp, node2);
454 if((temp = NodeTraits::get_parent(node2)) &&
455 //The header has been already updated so avoid it
457 if(NodeTraits::get_left(temp) == node1){
458 NodeTraits::set_left(temp, node2);
460 if(NodeTraits::get_right(temp) == node1){
461 NodeTraits::set_right(temp, node2);
466 //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
467 //! and new_node must not be inserted in a tree.
469 //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
470 //! tree with new_node. The tree does not need to be rebalanced
472 //! <b>Complexity</b>: Logarithmic.
474 //! <b>Throws</b>: Nothing.
476 //! <b>Note</b>: This function will break container ordering invariants if
477 //! new_node is not equivalent to node_to_be_replaced according to the
478 //! ordering rules. This function is faster than erasing and inserting
479 //! the node, since no rebalancing and comparison is needed. Experimental function
480 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
482 if(node_to_be_replaced == new_node)
484 replace_node(node_to_be_replaced, get_header(node_to_be_replaced), new_node);
487 //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
488 //! with header "header" and new_node must not be inserted in a tree.
490 //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
491 //! tree with new_node. The tree does not need to be rebalanced
493 //! <b>Complexity</b>: Constant.
495 //! <b>Throws</b>: Nothing.
497 //! <b>Note</b>: This function will break container ordering invariants if
498 //! new_node is not equivalent to node_to_be_replaced according to the
499 //! ordering rules. This function is faster than erasing and inserting
500 //! the node, since no rebalancing or comparison is needed. Experimental function
501 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
503 if(node_to_be_replaced == new_node)
506 //Update header if necessary
507 if(node_to_be_replaced == NodeTraits::get_left(header)){
508 NodeTraits::set_left(header, new_node);
511 if(node_to_be_replaced == NodeTraits::get_right(header)){
512 NodeTraits::set_right(header, new_node);
515 if(node_to_be_replaced == NodeTraits::get_parent(header)){
516 NodeTraits::set_parent(header, new_node);
519 //Now set data from the original node
521 NodeTraits::set_left(new_node, NodeTraits::get_left(node_to_be_replaced));
522 NodeTraits::set_right(new_node, NodeTraits::get_right(node_to_be_replaced));
523 NodeTraits::set_parent(new_node, NodeTraits::get_parent(node_to_be_replaced));
525 //Now adjust adjacent nodes for newly inserted node
526 if((temp = NodeTraits::get_left(new_node))){
527 NodeTraits::set_parent(temp, new_node);
529 if((temp = NodeTraits::get_right(new_node))){
530 NodeTraits::set_parent(temp, new_node);
532 if((temp = NodeTraits::get_parent(new_node)) &&
533 //The header has been already updated so avoid it
535 if(NodeTraits::get_left(temp) == node_to_be_replaced){
536 NodeTraits::set_left(temp, new_node);
538 if(NodeTraits::get_right(temp) == node_to_be_replaced){
539 NodeTraits::set_right(temp, new_node);
544 //! <b>Requires</b>: 'node' is a node from the tree except the header.
546 //! <b>Effects</b>: Returns the next node of the tree.
548 //! <b>Complexity</b>: Average constant time.
550 //! <b>Throws</b>: Nothing.
551 static node_ptr next_node(const node_ptr & node)
553 node_ptr const n_right(NodeTraits::get_right(node));
555 return minimum(n_right);
559 node_ptr p(NodeTraits::get_parent(n));
560 while(n == NodeTraits::get_right(p)){
562 p = NodeTraits::get_parent(p);
564 return NodeTraits::get_right(n) != p ? p : n;
568 //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node.
570 //! <b>Effects</b>: Returns the previous node of the tree.
572 //! <b>Complexity</b>: Average constant time.
574 //! <b>Throws</b>: Nothing.
575 static node_ptr prev_node(const node_ptr & node)
578 return NodeTraits::get_right(node);
579 //return maximum(NodeTraits::get_parent(node));
581 else if(NodeTraits::get_left(node)){
582 return maximum(NodeTraits::get_left(node));
586 node_ptr x = NodeTraits::get_parent(p);
587 while(p == NodeTraits::get_left(x)){
589 x = NodeTraits::get_parent(x);
595 //! <b>Requires</b>: 'node' is a node of a tree but not the header.
597 //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
599 //! <b>Complexity</b>: Logarithmic to the size of the subtree.
601 //! <b>Throws</b>: Nothing.
602 static node_ptr minimum(node_ptr node)
604 for(node_ptr p_left = NodeTraits::get_left(node)
606 ;p_left = NodeTraits::get_left(node)){
612 //! <b>Requires</b>: 'node' is a node of a tree but not the header.
614 //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
616 //! <b>Complexity</b>: Logarithmic to the size of the subtree.
618 //! <b>Throws</b>: Nothing.
619 static node_ptr maximum(node_ptr node)
621 for(node_ptr p_right = NodeTraits::get_right(node)
623 ;p_right = NodeTraits::get_right(node)){
629 //! <b>Requires</b>: 'node' must not be part of any tree.
631 //! <b>Effects</b>: After the function unique(node) == true.
633 //! <b>Complexity</b>: Constant.
635 //! <b>Throws</b>: Nothing.
637 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
638 static void init(const node_ptr & node)
640 NodeTraits::set_parent(node, node_ptr());
641 NodeTraits::set_left(node, node_ptr());
642 NodeTraits::set_right(node, node_ptr());
645 //! <b>Effects</b>: Returns true if node is in the same state as if called init(node)
647 //! <b>Complexity</b>: Constant.
649 //! <b>Throws</b>: Nothing.
650 static bool inited(const const_node_ptr & node)
652 return !NodeTraits::get_parent(node) &&
653 !NodeTraits::get_left(node) &&
654 !NodeTraits::get_right(node) ;
657 //! <b>Requires</b>: node must not be part of any tree.
659 //! <b>Effects</b>: Initializes the header to represent an empty tree.
660 //! unique(header) == true.
662 //! <b>Complexity</b>: Constant.
664 //! <b>Throws</b>: Nothing.
666 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
667 static void init_header(const node_ptr & header)
669 NodeTraits::set_parent(header, node_ptr());
670 NodeTraits::set_left(header, header);
671 NodeTraits::set_right(header, header);
674 //! <b>Requires</b>: "disposer" must be an object function
675 //! taking a node_ptr parameter and shouldn't throw.
677 //! <b>Effects</b>: Empties the target tree calling
678 //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
679 //! except the header.
681 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
682 //! number of elements of tree target tree when calling this function.
684 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
685 template<class Disposer>
686 static void clear_and_dispose(const node_ptr & header, Disposer disposer)
688 node_ptr source_root = NodeTraits::get_parent(header);
691 dispose_subtree(source_root, disposer);
695 //! <b>Requires</b>: header is the header of a tree.
697 //! <b>Effects</b>: Unlinks the leftmost node from the tree, and
698 //! updates the header link to the new leftmost node.
700 //! <b>Complexity</b>: Average complexity is constant time.
702 //! <b>Throws</b>: Nothing.
704 //! <b>Notes</b>: This function breaks the tree and the tree can
705 //! only be used for more unlink_leftmost_without_rebalance calls.
706 //! This function is normally used to achieve a step by step
707 //! controlled destruction of the tree.
708 static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header)
710 node_ptr leftmost = NodeTraits::get_left(header);
711 if (leftmost == header)
713 node_ptr leftmost_parent(NodeTraits::get_parent(leftmost));
714 node_ptr leftmost_right (NodeTraits::get_right(leftmost));
715 bool is_root = leftmost_parent == header;
718 NodeTraits::set_parent(leftmost_right, leftmost_parent);
719 NodeTraits::set_left(header, bstree_algorithms::minimum(leftmost_right));
722 NodeTraits::set_parent(header, leftmost_right);
724 NodeTraits::set_left(NodeTraits::get_parent(header), leftmost_right);
727 NodeTraits::set_parent(header, node_ptr());
728 NodeTraits::set_left(header, header);
729 NodeTraits::set_right(header, header);
732 NodeTraits::set_left(leftmost_parent, node_ptr());
733 NodeTraits::set_left(header, leftmost_parent);
738 //! <b>Requires</b>: node is a node of the tree but it's not the header.
740 //! <b>Effects</b>: Returns the number of nodes of the subtree.
742 //! <b>Complexity</b>: Linear time.
744 //! <b>Throws</b>: Nothing.
745 static std::size_t size(const const_node_ptr & header)
747 node_ptr beg(begin_node(header));
748 node_ptr end(end_node(header));
750 for(;beg != end; beg = next_node(beg)) ++i;
754 //! <b>Requires</b>: header1 and header2 must be the header nodes
757 //! <b>Effects</b>: Swaps two trees. After the function header1 will contain
758 //! links to the second tree and header2 will have links to the first tree.
760 //! <b>Complexity</b>: Constant.
762 //! <b>Throws</b>: Nothing.
763 static void swap_tree(const node_ptr & header1, const node_ptr & header2)
765 if(header1 == header2)
771 tmp = NodeTraits::get_parent(header1);
772 NodeTraits::set_parent(header1, NodeTraits::get_parent(header2));
773 NodeTraits::set_parent(header2, tmp);
775 tmp = NodeTraits::get_left(header1);
776 NodeTraits::set_left(header1, NodeTraits::get_left(header2));
777 NodeTraits::set_left(header2, tmp);
779 tmp = NodeTraits::get_right(header1);
780 NodeTraits::set_right(header1, NodeTraits::get_right(header2));
781 NodeTraits::set_right(header2, tmp);
784 node_ptr h1_parent(NodeTraits::get_parent(header1));
786 NodeTraits::set_parent(h1_parent, header1);
789 NodeTraits::set_left(header1, header1);
790 NodeTraits::set_right(header1, header1);
793 node_ptr h2_parent(NodeTraits::get_parent(header2));
795 NodeTraits::set_parent(h2_parent, header2);
798 NodeTraits::set_left(header2, header2);
799 NodeTraits::set_right(header2, header2);
803 //! <b>Requires</b>: p is a node of a tree.
805 //! <b>Effects</b>: Returns true if p is the header of the tree.
807 //! <b>Complexity</b>: Constant.
809 //! <b>Throws</b>: Nothing.
810 static bool is_header(const const_node_ptr & p)
812 node_ptr p_left (NodeTraits::get_left(p));
813 node_ptr p_right(NodeTraits::get_right(p));
814 if(!NodeTraits::get_parent(p) || //Header condition when empty tree
815 (p_left && p_right && //Header always has leftmost and rightmost
816 (p_left == p_right || //Header condition when only node
817 (NodeTraits::get_parent(p_left) != p ||
818 NodeTraits::get_parent(p_right) != p ))
819 //When tree size > 1 headers can't be leftmost's
820 //and rightmost's parent
827 //! <b>Requires</b>: "header" must be the header node of a tree.
828 //! KeyNodePtrCompare is a function object that induces a strict weak
829 //! ordering compatible with the strict weak ordering used to create the
830 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
832 //! <b>Effects</b>: Returns a node_ptr to the first element that is equivalent to
833 //! "key" according to "comp" or "header" if that element does not exist.
835 //! <b>Complexity</b>: Logarithmic.
837 //! <b>Throws</b>: If "comp" throws.
838 template<class KeyType, class KeyNodePtrCompare>
840 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
842 node_ptr end = detail::uncast(header);
843 node_ptr y = lower_bound(header, key, comp);
844 return (y == end || comp(key, y)) ? end : y;
847 //! <b>Requires</b>: "header" must be the header node of a tree.
848 //! KeyNodePtrCompare is a function object that induces a strict weak
849 //! ordering compatible with the strict weak ordering used to create the
850 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
851 //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
852 //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
854 //! <b>Effects</b>: Returns an a pair with the following criteria:
856 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
858 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
860 //! <b>Complexity</b>: Logarithmic.
862 //! <b>Throws</b>: If "comp" throws.
864 //! <b>Note</b>: This function can be more efficient than calling upper_bound
865 //! and lower_bound for lower_key and upper_key.
867 //! <b>Note</b>: Experimental function, the interface might change.
868 template< class KeyType, class KeyNodePtrCompare>
869 static std::pair<node_ptr, node_ptr> bounded_range
870 ( const const_node_ptr & header
871 , const KeyType &lower_key
872 , const KeyType &upper_key
873 , KeyNodePtrCompare comp
877 node_ptr y = detail::uncast(header);
878 node_ptr x = NodeTraits::get_parent(header);
881 //If x is less than lower_key the target
882 //range is on the right part
883 if(comp(x, lower_key)){
884 //Check for invalid input range
885 BOOST_INTRUSIVE_INVARIANT_ASSERT(comp(x, upper_key));
886 x = NodeTraits::get_right(x);
888 //If the upper_key is less than x, the target
889 //range is on the left part
890 else if(comp(upper_key, x)){
892 x = NodeTraits::get_left(x);
895 //x is inside the bounded range( x >= lower_key && x <= upper_key),
896 //so we must split lower and upper searches
898 //Sanity check: if lower_key and upper_key are equal, then both left_closed and right_closed can't be false
899 BOOST_INTRUSIVE_INVARIANT_ASSERT(left_closed || right_closed || comp(lower_key, x) || comp(x, upper_key));
900 return std::pair<node_ptr,node_ptr>(
902 //If left_closed, then comp(x, lower_key) is already the lower_bound
903 //condition so we save one comparison and go to the next level
904 //following traditional lower_bound algo
905 ? lower_bound_loop(NodeTraits::get_left(x), x, lower_key, comp)
906 //If left-open, comp(x, lower_key) is not the upper_bound algo
907 //condition so we must recheck current 'x' node with upper_bound algo
908 : upper_bound_loop(x, y, lower_key, comp)
911 //If right_closed, then comp(upper_key, x) is already the upper_bound
912 //condition so we can save one comparison and go to the next level
913 //following lower_bound algo
914 ? upper_bound_loop(NodeTraits::get_right(x), y, upper_key, comp)
915 //If right-open, comp(upper_key, x) is not the lower_bound algo
916 //condition so we must recheck current 'x' node with lower_bound algo
917 : lower_bound_loop(x, y, upper_key, comp)
921 return std::pair<node_ptr,node_ptr> (y, y);
924 //! <b>Requires</b>: "header" must be the header node of a tree.
925 //! KeyNodePtrCompare is a function object that induces a strict weak
926 //! ordering compatible with the strict weak ordering used to create the
927 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
929 //! <b>Effects</b>: Returns the number of elements with a key equivalent to "key"
930 //! according to "comp".
932 //! <b>Complexity</b>: Logarithmic.
934 //! <b>Throws</b>: If "comp" throws.
935 template<class KeyType, class KeyNodePtrCompare>
936 static std::size_t count
937 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
939 std::pair<node_ptr, node_ptr> ret = equal_range(header, key, comp);
941 while(ret.first != ret.second){
943 ret.first = next_node(ret.first);
948 //! <b>Requires</b>: "header" must be the header node of a tree.
949 //! KeyNodePtrCompare is a function object that induces a strict weak
950 //! ordering compatible with the strict weak ordering used to create the
951 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
953 //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
954 //! all elements that are equivalent to "key" according to "comp" or an
955 //! empty range that indicates the position where those elements would be
956 //! if there are no equivalent elements.
958 //! <b>Complexity</b>: Logarithmic.
960 //! <b>Throws</b>: If "comp" throws.
961 template<class KeyType, class KeyNodePtrCompare>
962 static std::pair<node_ptr, node_ptr> equal_range
963 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
965 return bounded_range(header, key, key, comp, true, true);
968 //! <b>Requires</b>: "header" must be the header node of a tree.
969 //! KeyNodePtrCompare is a function object that induces a strict weak
970 //! ordering compatible with the strict weak ordering used to create the
971 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
973 //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
974 //! the first element that is equivalent to "key" according to "comp" or an
975 //! empty range that indicates the position where that element would be
976 //! if there are no equivalent elements.
978 //! <b>Complexity</b>: Logarithmic.
980 //! <b>Throws</b>: If "comp" throws.
981 template<class KeyType, class KeyNodePtrCompare>
982 static std::pair<node_ptr, node_ptr> lower_bound_range
983 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
985 node_ptr const lb(lower_bound(header, key, comp));
986 std::pair<node_ptr, node_ptr> ret_ii(lb, lb);
987 if(lb != header && !comp(key, lb)){
988 ret_ii.second = next_node(ret_ii.second);
993 //! <b>Requires</b>: "header" must be the header node of a tree.
994 //! KeyNodePtrCompare is a function object that induces a strict weak
995 //! ordering compatible with the strict weak ordering used to create the
996 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
998 //! <b>Effects</b>: Returns a node_ptr to the first element that is
999 //! not less than "key" according to "comp" or "header" if that element does
1002 //! <b>Complexity</b>: Logarithmic.
1004 //! <b>Throws</b>: If "comp" throws.
1005 template<class KeyType, class KeyNodePtrCompare>
1006 static node_ptr lower_bound
1007 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
1009 return lower_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp);
1012 //! <b>Requires</b>: "header" must be the header node of a tree.
1013 //! KeyNodePtrCompare is a function object that induces a strict weak
1014 //! ordering compatible with the strict weak ordering used to create the
1015 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
1017 //! <b>Effects</b>: Returns a node_ptr to the first element that is greater
1018 //! than "key" according to "comp" or "header" if that element does not exist.
1020 //! <b>Complexity</b>: Logarithmic.
1022 //! <b>Throws</b>: If "comp" throws.
1023 template<class KeyType, class KeyNodePtrCompare>
1024 static node_ptr upper_bound
1025 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
1027 return upper_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp);
1030 //! <b>Requires</b>: "header" must be the header node of a tree.
1031 //! "commit_data" must have been obtained from a previous call to
1032 //! "insert_unique_check". No objects should have been inserted or erased
1033 //! from the set between the "insert_unique_check" that filled "commit_data"
1034 //! and the call to "insert_commit".
1037 //! <b>Effects</b>: Inserts new_node in the set using the information obtained
1038 //! from the "commit_data" that a previous "insert_check" filled.
1040 //! <b>Complexity</b>: Constant time.
1042 //! <b>Throws</b>: Nothing.
1044 //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been
1045 //! previously executed to fill "commit_data". No value should be inserted or
1046 //! erased between the "insert_check" and "insert_commit" calls.
1047 static void insert_unique_commit
1048 (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
1049 { return insert_commit(header, new_value, commit_data); }
1051 //! <b>Requires</b>: "header" must be the header node of a tree.
1052 //! KeyNodePtrCompare is a function object that induces a strict weak
1053 //! ordering compatible with the strict weak ordering used to create the
1054 //! the tree. NodePtrCompare compares KeyType with a node_ptr.
1056 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
1057 //! tree according to "comp" and obtains the needed information to realize
1058 //! a constant-time node insertion if there is no equivalent node.
1060 //! <b>Returns</b>: If there is an equivalent value
1061 //! returns a pair containing a node_ptr to the already present node
1062 //! and false. If there is not equivalent key can be inserted returns true
1063 //! in the returned pair's boolean and fills "commit_data" that is meant to
1064 //! be used with the "insert_commit" function to achieve a constant-time
1065 //! insertion function.
1067 //! <b>Complexity</b>: Average complexity is at most logarithmic.
1069 //! <b>Throws</b>: If "comp" throws.
1071 //! <b>Notes</b>: This function is used to improve performance when constructing
1072 //! a node is expensive and the user does not want to have two equivalent nodes
1073 //! in the tree: if there is an equivalent value
1074 //! the constructed object must be discarded. Many times, the part of the
1075 //! node that is used to impose the order is much cheaper to construct
1076 //! than the node and this function offers the possibility to use that part
1077 //! to check if the insertion will be successful.
1079 //! If the check is successful, the user can construct the node and use
1080 //! "insert_commit" to insert the node in constant-time. This gives a total
1081 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
1083 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only
1084 //! if no more objects are inserted or erased from the set.
1085 template<class KeyType, class KeyNodePtrCompare>
1086 static std::pair<node_ptr, bool> insert_unique_check
1087 (const const_node_ptr & header, const KeyType &key
1088 ,KeyNodePtrCompare comp, insert_commit_data &commit_data
1089 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1090 , std::size_t *pdepth = 0
1094 std::size_t depth = 0;
1095 node_ptr h(detail::uncast(header));
1097 node_ptr x(NodeTraits::get_parent(y));
1098 node_ptr prev = node_ptr();
1100 //Find the upper bound, cache the previous value and if we should
1101 //store it in the left or right node
1102 bool left_child = true;
1106 x = (left_child = comp(key, x)) ?
1107 NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x));
1110 if(pdepth) *pdepth = depth;
1112 //Since we've found the upper bound there is no other value with the same key if:
1113 // - There is no previous node
1114 // - The previous node is less than the key
1115 const bool not_present = !prev || comp(prev, key);
1117 commit_data.link_left = left_child;
1118 commit_data.node = y;
1120 return std::pair<node_ptr, bool>(prev, not_present);
1123 //! <b>Requires</b>: "header" must be the header node of a tree.
1124 //! KeyNodePtrCompare is a function object that induces a strict weak
1125 //! ordering compatible with the strict weak ordering used to create the
1126 //! the tree. NodePtrCompare compares KeyType with a node_ptr.
1127 //! "hint" is node from the "header"'s tree.
1129 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
1130 //! tree according to "comp" using "hint" as a hint to where it should be
1131 //! inserted and obtains the needed information to realize
1132 //! a constant-time node insertion if there is no equivalent node.
1133 //! If "hint" is the upper_bound the function has constant time
1134 //! complexity (two comparisons in the worst case).
1136 //! <b>Returns</b>: If there is an equivalent value
1137 //! returns a pair containing a node_ptr to the already present node
1138 //! and false. If there is not equivalent key can be inserted returns true
1139 //! in the returned pair's boolean and fills "commit_data" that is meant to
1140 //! be used with the "insert_commit" function to achieve a constant-time
1141 //! insertion function.
1143 //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is
1144 //! amortized constant time if new_node should be inserted immediately before "hint".
1146 //! <b>Throws</b>: If "comp" throws.
1148 //! <b>Notes</b>: This function is used to improve performance when constructing
1149 //! a node is expensive and the user does not want to have two equivalent nodes
1150 //! in the tree: if there is an equivalent value
1151 //! the constructed object must be discarded. Many times, the part of the
1152 //! node that is used to impose the order is much cheaper to construct
1153 //! than the node and this function offers the possibility to use that part
1154 //! to check if the insertion will be successful.
1156 //! If the check is successful, the user can construct the node and use
1157 //! "insert_commit" to insert the node in constant-time. This gives a total
1158 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
1160 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only
1161 //! if no more objects are inserted or erased from the set.
1162 template<class KeyType, class KeyNodePtrCompare>
1163 static std::pair<node_ptr, bool> insert_unique_check
1164 (const const_node_ptr & header, const node_ptr &hint, const KeyType &key
1165 ,KeyNodePtrCompare comp, insert_commit_data &commit_data
1166 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1167 , std::size_t *pdepth = 0
1171 //hint must be bigger than the key
1172 if(hint == header || comp(key, hint)){
1173 node_ptr prev(hint);
1174 //Previous value should be less than the key
1175 if(hint == begin_node(header) || comp((prev = prev_node(hint)), key)){
1176 commit_data.link_left = unique(header) || !NodeTraits::get_left(hint);
1177 commit_data.node = commit_data.link_left ? hint : prev;
1179 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1;
1181 return std::pair<node_ptr, bool>(node_ptr(), true);
1184 //Hint was wrong, use hintless insertion
1185 return insert_unique_check(header, key, comp, commit_data, pdepth);
1188 //! <b>Requires</b>: "header" must be the header node of a tree.
1189 //! NodePtrCompare is a function object that induces a strict weak
1190 //! ordering compatible with the strict weak ordering used to create the
1191 //! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from
1192 //! the "header"'s tree.
1194 //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to
1195 //! where it will be inserted. If "hint" is the upper_bound
1196 //! the insertion takes constant time (two comparisons in the worst case).
1198 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
1199 //! constant time if new_node is inserted immediately before "hint".
1201 //! <b>Throws</b>: If "comp" throws.
1202 template<class NodePtrCompare>
1203 static node_ptr insert_equal
1204 (const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp
1205 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1206 , std::size_t *pdepth = 0
1210 insert_commit_data commit_data;
1211 insert_equal_check(h, hint, new_node, comp, commit_data, pdepth);
1212 insert_commit(h, new_node, commit_data);
1216 //! <b>Requires</b>: "h" must be the header node of a tree.
1217 //! NodePtrCompare is a function object that induces a strict weak
1218 //! ordering compatible with the strict weak ordering used to create the
1219 //! the tree. NodePtrCompare compares two node_ptrs.
1221 //! <b>Effects</b>: Inserts new_node into the tree before the upper bound
1222 //! according to "comp".
1224 //! <b>Complexity</b>: Average complexity for insert element is at
1225 //! most logarithmic.
1227 //! <b>Throws</b>: If "comp" throws.
1228 template<class NodePtrCompare>
1229 static node_ptr insert_equal_upper_bound
1230 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
1231 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1232 , std::size_t *pdepth = 0
1236 insert_commit_data commit_data;
1237 insert_equal_upper_bound_check(h, new_node, comp, commit_data, pdepth);
1238 insert_commit(h, new_node, commit_data);
1242 //! <b>Requires</b>: "h" must be the header node of a tree.
1243 //! NodePtrCompare is a function object that induces a strict weak
1244 //! ordering compatible with the strict weak ordering used to create the
1245 //! the tree. NodePtrCompare compares two node_ptrs.
1247 //! <b>Effects</b>: Inserts new_node into the tree before the lower bound
1248 //! according to "comp".
1250 //! <b>Complexity</b>: Average complexity for insert element is at
1251 //! most logarithmic.
1253 //! <b>Throws</b>: If "comp" throws.
1254 template<class NodePtrCompare>
1255 static node_ptr insert_equal_lower_bound
1256 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
1257 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1258 , std::size_t *pdepth = 0
1262 insert_commit_data commit_data;
1263 insert_equal_lower_bound_check(h, new_node, comp, commit_data, pdepth);
1264 insert_commit(h, new_node, commit_data);
1268 //! <b>Requires</b>: "header" must be the header node of a tree.
1269 //! "pos" must be a valid iterator or header (end) node.
1270 //! "pos" must be an iterator pointing to the successor to "new_node"
1271 //! once inserted according to the order of already inserted nodes. This function does not
1272 //! check "pos" and this precondition must be guaranteed by the caller.
1274 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
1276 //! <b>Complexity</b>: Constant-time.
1278 //! <b>Throws</b>: Nothing.
1280 //! <b>Note</b>: If "pos" is not the successor of the newly inserted "new_node"
1281 //! tree invariants might be broken.
1282 static node_ptr insert_before
1283 (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node
1284 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1285 , std::size_t *pdepth = 0
1289 insert_commit_data commit_data;
1290 insert_before_check(header, pos, commit_data, pdepth);
1291 insert_commit(header, new_node, commit_data);
1295 //! <b>Requires</b>: "header" must be the header node of a tree.
1296 //! "new_node" must be, according to the used ordering no less than the
1297 //! greatest inserted key.
1299 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
1301 //! <b>Complexity</b>: Constant-time.
1303 //! <b>Throws</b>: Nothing.
1305 //! <b>Note</b>: If "new_node" is less than the greatest inserted key
1306 //! tree invariants are broken. This function is slightly faster than
1307 //! using "insert_before".
1308 static void push_back
1309 (const node_ptr & header, const node_ptr & new_node
1310 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1311 , std::size_t *pdepth = 0
1315 insert_commit_data commit_data;
1316 push_back_check(header, commit_data, pdepth);
1317 insert_commit(header, new_node, commit_data);
1320 //! <b>Requires</b>: "header" must be the header node of a tree.
1321 //! "new_node" must be, according to the used ordering, no greater than the
1322 //! lowest inserted key.
1324 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
1326 //! <b>Complexity</b>: Constant-time.
1328 //! <b>Throws</b>: Nothing.
1330 //! <b>Note</b>: If "new_node" is greater than the lowest inserted key
1331 //! tree invariants are broken. This function is slightly faster than
1332 //! using "insert_before".
1333 static void push_front
1334 (const node_ptr & header, const node_ptr & new_node
1335 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1336 , std::size_t *pdepth = 0
1340 insert_commit_data commit_data;
1341 push_front_check(header, commit_data, pdepth);
1342 insert_commit(header, new_node, commit_data);
1345 //! <b>Requires</b>: 'node' can't be a header node.
1347 //! <b>Effects</b>: Calculates the depth of a node: the depth of a
1348 //! node is the length (number of edges) of the path from the root
1349 //! to that node. (The root node is at depth 0.)
1351 //! <b>Complexity</b>: Logarithmic to the number of nodes in the tree.
1353 //! <b>Throws</b>: Nothing.
1354 static std::size_t depth(const_node_ptr node)
1356 std::size_t depth = 0;
1358 while(node != NodeTraits::get_parent(p_parent = NodeTraits::get_parent(node))){
1365 //! <b>Requires</b>: "cloner" must be a function
1366 //! object taking a node_ptr and returning a new cloned node of it. "disposer" must
1367 //! take a node_ptr and shouldn't throw.
1369 //! <b>Effects</b>: First empties target tree calling
1370 //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
1371 //! except the header.
1373 //! Then, duplicates the entire tree pointed by "source_header" cloning each
1374 //! source node with <tt>node_ptr Cloner::operator()(const node_ptr &)</tt> to obtain
1375 //! the nodes of the target tree. If "cloner" throws, the cloned target nodes
1376 //! are disposed using <tt>void disposer(const node_ptr &)</tt>.
1378 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
1379 //! number of elements of tree target tree when calling this function.
1381 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
1382 template <class Cloner, class Disposer>
1384 (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
1386 if(!unique(target_header)){
1387 clear_and_dispose(target_header, disposer);
1390 node_ptr leftmost, rightmost;
1391 node_ptr new_root = clone_subtree
1392 (source_header, target_header, cloner, disposer, leftmost, rightmost);
1394 //Now update header node
1395 NodeTraits::set_parent(target_header, new_root);
1396 NodeTraits::set_left (target_header, leftmost);
1397 NodeTraits::set_right (target_header, rightmost);
1400 //! <b>Requires</b>: header must be the header of a tree, z a node
1401 //! of that tree and z != header.
1403 //! <b>Effects</b>: Erases node "z" from the tree with header "header".
1405 //! <b>Complexity</b>: Amortized constant time.
1407 //! <b>Throws</b>: Nothing.
1408 static void erase(const node_ptr & header, const node_ptr & z)
1410 data_for_rebalance ignored;
1411 erase(header, z, ignored);
1414 //! <b>Requires</b>: node is a tree node but not the header.
1416 //! <b>Effects</b>: Unlinks the node and rebalances the tree.
1418 //! <b>Complexity</b>: Average complexity is constant time.
1420 //! <b>Throws</b>: Nothing.
1421 static void unlink(const node_ptr & node)
1423 node_ptr x = NodeTraits::get_parent(node);
1425 while(!is_header(x))
1426 x = NodeTraits::get_parent(x);
1431 //! <b>Requires</b>: header must be the header of a tree.
1433 //! <b>Effects</b>: Rebalances the tree.
1435 //! <b>Throws</b>: Nothing.
1437 //! <b>Complexity</b>: Linear.
1438 static void rebalance(const node_ptr & header)
1440 node_ptr root = NodeTraits::get_parent(header);
1442 rebalance_subtree(root);
1446 //! <b>Requires</b>: old_root is a node of a tree. It shall not be null.
1448 //! <b>Effects</b>: Rebalances the subtree rooted at old_root.
1450 //! <b>Returns</b>: The new root of the subtree.
1452 //! <b>Throws</b>: Nothing.
1454 //! <b>Complexity</b>: Linear.
1455 static node_ptr rebalance_subtree(const node_ptr & old_root)
1458 //"Tree rebalancing in optimal time and space"
1459 //Quentin F. Stout and Bette L. Warren
1461 //To avoid irregularities in the algorithm (old_root can be a
1462 //left or right child or even the root of the tree) just put the
1463 //root as the right child of its parent. Before doing this backup
1464 //information to restore the original relationship after
1465 //the algorithm is applied.
1466 node_ptr super_root = NodeTraits::get_parent(old_root);
1467 BOOST_INTRUSIVE_INVARIANT_ASSERT(super_root);
1470 node_ptr super_root_right_backup = NodeTraits::get_right(super_root);
1471 bool super_root_is_header = NodeTraits::get_parent(super_root) == old_root;
1472 bool old_root_is_right = is_right_child(old_root);
1473 NodeTraits::set_right(super_root, old_root);
1476 subtree_to_vine(super_root, size);
1477 vine_to_subtree(super_root, size);
1478 node_ptr new_root = NodeTraits::get_right(super_root);
1481 if(super_root_is_header){
1482 NodeTraits::set_right(super_root, super_root_right_backup);
1483 NodeTraits::set_parent(super_root, new_root);
1485 else if(old_root_is_right){
1486 NodeTraits::set_right(super_root, new_root);
1489 NodeTraits::set_right(super_root, super_root_right_backup);
1490 NodeTraits::set_left(super_root, new_root);
1495 //! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user.
1497 //! <b>Requires</b>: header must be the header of a tree.
1499 //! <b>Complexity</b>: Linear time.
1501 //! <b>Note</b>: The method might not have effect when asserts are turned off (e.g., with NDEBUG).
1502 //! Experimental function, interface might change in future versions.
1503 template<class Checker>
1504 static void check(const const_node_ptr& header, Checker checker, typename Checker::return_type& checker_return)
1506 const_node_ptr root_node_ptr = NodeTraits::get_parent(header);
1509 // check left&right header pointers
1510 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header);
1511 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header);
1515 // check parent pointer of root node
1516 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header);
1517 // check subtree from root
1518 check_subtree(root_node_ptr, checker, checker_return);
1519 // check left&right header pointers
1520 const_node_ptr p = root_node_ptr;
1521 while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); }
1522 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p);
1524 while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); }
1525 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p);
1530 static void erase(const node_ptr & header, const node_ptr & z, data_for_rebalance &info)
1534 const node_ptr z_left(NodeTraits::get_left(z));
1535 const node_ptr z_right(NodeTraits::get_right(z));
1538 x = z_right; // x might be null.
1540 else if(!z_right){ // z has exactly one non-null child. y == z.
1541 x = z_left; // x is not null.
1545 // y = find z's successor
1546 y = bstree_algorithms::minimum(z_right);
1547 x = NodeTraits::get_right(y); // x might be null.
1551 const node_ptr z_parent(NodeTraits::get_parent(z));
1552 const bool z_is_leftchild(NodeTraits::get_left(z_parent) == z);
1554 if(y != z){ //has two children and y is the minimum of z
1555 //y is z's successor and it has a null left child.
1556 //x is the right child of y (it can be null)
1557 //Relink y in place of z and link x with y's old parent
1558 NodeTraits::set_parent(z_left, y);
1559 NodeTraits::set_left(y, z_left);
1561 //Link y with the right tree of z
1562 NodeTraits::set_right(y, z_right);
1563 NodeTraits::set_parent(z_right, y);
1564 //Link x with y's old parent (y must be a left child)
1565 x_parent = NodeTraits::get_parent(y);
1566 BOOST_ASSERT(NodeTraits::get_left(x_parent) == y);
1568 NodeTraits::set_parent(x, x_parent);
1569 //Since y was the successor and not the right child of z, it must be a left child
1570 NodeTraits::set_left(x_parent, x);
1572 else{ //y was the right child of y so no need to fix x's position
1575 NodeTraits::set_parent(y, z_parent);
1576 bstree_algorithms::set_child(header, y, z_parent, z_is_leftchild);
1578 else { // z has zero or one child, x is one child (it can be null)
1579 //Just link x to z's parent
1580 x_parent = z_parent;
1582 NodeTraits::set_parent(x, z_parent);
1583 bstree_algorithms::set_child(header, x, z_parent, z_is_leftchild);
1585 //Now update leftmost/rightmost in case z was one of them
1586 if(NodeTraits::get_left(header) == z){
1587 //z_left must be null because z is the leftmost
1588 BOOST_ASSERT(!z_left);
1589 NodeTraits::set_left(header, !z_right ?
1590 z_parent : // makes leftmost == header if z == root
1591 bstree_algorithms::minimum(z_right));
1593 if(NodeTraits::get_right(header) == z){
1594 //z_right must be null because z is the rightmost
1595 BOOST_ASSERT(!z_right);
1596 NodeTraits::set_right(header, !z_left ?
1597 z_parent : // makes rightmost == header if z == root
1598 bstree_algorithms::maximum(z_left));
1602 //If z had 0/1 child, y == z and one of its children (and maybe null)
1603 //If z had 2 children, y is the successor of z and x is the right child of y
1606 //If z had 0/1 child, x_parent is the new parent of the old right child of y (z's successor)
1607 //If z had 2 children, x_parent is the new parent of y (z_parent)
1608 BOOST_ASSERT(!x || NodeTraits::get_parent(x) == x_parent);
1609 info.x_parent = x_parent;
1612 //! <b>Requires</b>: node is a node of the tree but it's not the header.
1614 //! <b>Effects</b>: Returns the number of nodes of the subtree.
1616 //! <b>Complexity</b>: Linear time.
1618 //! <b>Throws</b>: Nothing.
1619 static std::size_t subtree_size(const const_node_ptr & subtree)
1621 std::size_t count = 0;
1623 node_ptr n = detail::uncast(subtree);
1624 node_ptr m = NodeTraits::get_left(n);
1627 m = NodeTraits::get_left(n);
1632 node_ptr n_right(NodeTraits::get_right(n));
1635 m = NodeTraits::get_left(n);
1638 m = NodeTraits::get_left(n);
1647 n = NodeTraits::get_parent(n);
1648 }while(NodeTraits::get_left(n) != m);
1655 //! <b>Requires</b>: p is a node of a tree.
1657 //! <b>Effects</b>: Returns true if p is a left child.
1659 //! <b>Complexity</b>: Constant.
1661 //! <b>Throws</b>: Nothing.
1662 static bool is_left_child(const node_ptr & p)
1663 { return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; }
1665 //! <b>Requires</b>: p is a node of a tree.
1667 //! <b>Effects</b>: Returns true if p is a right child.
1669 //! <b>Complexity</b>: Constant.
1671 //! <b>Throws</b>: Nothing.
1672 static bool is_right_child(const node_ptr & p)
1673 { return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; }
1675 static void insert_before_check
1676 (const node_ptr &header, const node_ptr & pos
1677 , insert_commit_data &commit_data
1678 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1679 , std::size_t *pdepth = 0
1684 if(pos != NodeTraits::get_left(header))
1685 prev = prev_node(pos);
1686 bool link_left = unique(header) || !NodeTraits::get_left(pos);
1687 commit_data.link_left = link_left;
1688 commit_data.node = link_left ? pos : prev;
1690 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1;
1694 static void push_back_check
1695 (const node_ptr & header, insert_commit_data &commit_data
1696 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1697 , std::size_t *pdepth = 0
1701 node_ptr prev(NodeTraits::get_right(header));
1703 *pdepth = prev == header ? 0 : depth(prev) + 1;
1705 commit_data.link_left = false;
1706 commit_data.node = prev;
1709 static void push_front_check
1710 (const node_ptr & header, insert_commit_data &commit_data
1711 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1712 , std::size_t *pdepth = 0
1716 node_ptr pos(NodeTraits::get_left(header));
1718 *pdepth = pos == header ? 0 : depth(pos) + 1;
1720 commit_data.link_left = true;
1721 commit_data.node = pos;
1724 template<class NodePtrCompare>
1725 static void insert_equal_check
1726 (const node_ptr &header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp
1727 , insert_commit_data &commit_data
1729 , std::size_t *pdepth = 0
1733 if(hint == header || !comp(hint, new_node)){
1734 node_ptr prev(hint);
1735 if(hint == NodeTraits::get_left(header) ||
1736 !comp(new_node, (prev = prev_node(hint)))){
1737 bool link_left = unique(header) || !NodeTraits::get_left(hint);
1738 commit_data.link_left = link_left;
1739 commit_data.node = link_left ? hint : prev;
1741 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1;
1745 insert_equal_upper_bound_check(header, new_node, comp, commit_data, pdepth);
1749 insert_equal_lower_bound_check(header, new_node, comp, commit_data, pdepth);
1753 template<class NodePtrCompare>
1754 static void insert_equal_upper_bound_check
1755 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
1757 std::size_t depth = 0;
1759 node_ptr x(NodeTraits::get_parent(y));
1764 x = comp(new_node, x) ?
1765 NodeTraits::get_left(x) : NodeTraits::get_right(x);
1767 if(pdepth) *pdepth = depth;
1768 commit_data.link_left = (y == h) || comp(new_node, y);
1769 commit_data.node = y;
1772 template<class NodePtrCompare>
1773 static void insert_equal_lower_bound_check
1774 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
1776 std::size_t depth = 0;
1778 node_ptr x(NodeTraits::get_parent(y));
1783 x = !comp(x, new_node) ?
1784 NodeTraits::get_left(x) : NodeTraits::get_right(x);
1786 if(pdepth) *pdepth = depth;
1787 commit_data.link_left = (y == h) || !comp(y, new_node);
1788 commit_data.node = y;
1791 static void insert_commit
1792 (const node_ptr & header, const node_ptr & new_node, const insert_commit_data &commit_data)
1794 //Check if commit_data has not been initialized by a insert_unique_check call.
1795 BOOST_INTRUSIVE_INVARIANT_ASSERT(commit_data.node != node_ptr());
1796 node_ptr parent_node(commit_data.node);
1797 if(parent_node == header){
1798 NodeTraits::set_parent(header, new_node);
1799 NodeTraits::set_right(header, new_node);
1800 NodeTraits::set_left(header, new_node);
1802 else if(commit_data.link_left){
1803 NodeTraits::set_left(parent_node, new_node);
1804 if(parent_node == NodeTraits::get_left(header))
1805 NodeTraits::set_left(header, new_node);
1808 NodeTraits::set_right(parent_node, new_node);
1809 if(parent_node == NodeTraits::get_right(header))
1810 NodeTraits::set_right(header, new_node);
1812 NodeTraits::set_parent(new_node, parent_node);
1813 NodeTraits::set_right(new_node, node_ptr());
1814 NodeTraits::set_left(new_node, node_ptr());
1817 //Fix header and own's parent data when replacing x with own, providing own's old data with parent
1818 static void set_child(const node_ptr & header, const node_ptr & new_child, const node_ptr & new_parent, const bool link_left)
1820 if(new_parent == header)
1821 NodeTraits::set_parent(header, new_child);
1823 NodeTraits::set_left(new_parent, new_child);
1825 NodeTraits::set_right(new_parent, new_child);
1828 // rotate p to left (no header and p's parent fixup)
1829 static void rotate_left_no_parent_fix(const node_ptr & p, const node_ptr &p_right)
1831 node_ptr p_right_left(NodeTraits::get_left(p_right));
1832 NodeTraits::set_right(p, p_right_left);
1834 NodeTraits::set_parent(p_right_left, p);
1836 NodeTraits::set_left(p_right, p);
1837 NodeTraits::set_parent(p, p_right);
1840 // rotate p to left (with header and p's parent fixup)
1841 static void rotate_left(const node_ptr & p, const node_ptr & p_right, const node_ptr & p_parent, const node_ptr & header)
1843 const bool p_was_left(NodeTraits::get_left(p_parent) == p);
1844 rotate_left_no_parent_fix(p, p_right);
1845 NodeTraits::set_parent(p_right, p_parent);
1846 set_child(header, p_right, p_parent, p_was_left);
1849 // rotate p to right (no header and p's parent fixup)
1850 static void rotate_right_no_parent_fix(const node_ptr & p, const node_ptr &p_left)
1852 node_ptr p_left_right(NodeTraits::get_right(p_left));
1853 NodeTraits::set_left(p, p_left_right);
1855 NodeTraits::set_parent(p_left_right, p);
1857 NodeTraits::set_right(p_left, p);
1858 NodeTraits::set_parent(p, p_left);
1861 // rotate p to right (with header and p's parent fixup)
1862 static void rotate_right(const node_ptr & p, const node_ptr & p_left, const node_ptr & p_parent, const node_ptr & header)
1864 const bool p_was_left(NodeTraits::get_left(p_parent) == p);
1865 rotate_right_no_parent_fix(p, p_left);
1866 NodeTraits::set_parent(p_left, p_parent);
1867 set_child(header, p_left, p_parent, p_was_left);
1872 static void subtree_to_vine(node_ptr vine_tail, std::size_t &size)
1874 //Inspired by LibAVL:
1875 //It uses a clever optimization for trees with parent pointers.
1876 //No parent pointer is updated when transforming a tree to a vine as
1877 //most of them will be overriten during compression rotations.
1878 //A final pass must be made after the rebalancing to updated those
1879 //pointers not updated by tree_to_vine + compression calls
1880 std::size_t len = 0;
1881 node_ptr remainder = NodeTraits::get_right(vine_tail);
1883 node_ptr tempptr = NodeTraits::get_left(remainder);
1884 if(!tempptr){ //move vine-tail down one
1885 vine_tail = remainder;
1886 remainder = NodeTraits::get_right(remainder);
1890 NodeTraits::set_left(remainder, NodeTraits::get_right(tempptr));
1891 NodeTraits::set_right(tempptr, remainder);
1892 remainder = tempptr;
1893 NodeTraits::set_right(vine_tail, tempptr);
1899 static void compress_subtree(node_ptr scanner, std::size_t count)
1901 while(count--){ //compress "count" spine nodes in the tree with pseudo-root scanner
1902 node_ptr child = NodeTraits::get_right(scanner);
1903 node_ptr child_right = NodeTraits::get_right(child);
1904 NodeTraits::set_right(scanner, child_right);
1905 //Avoid setting the parent of child_right
1906 scanner = child_right;
1907 node_ptr scanner_left = NodeTraits::get_left(scanner);
1908 NodeTraits::set_right(child, scanner_left);
1910 NodeTraits::set_parent(scanner_left, child);
1911 NodeTraits::set_left(scanner, child);
1912 NodeTraits::set_parent(child, scanner);
1916 static void vine_to_subtree(const node_ptr & super_root, std::size_t count)
1918 const std::size_t one_szt = 1u;
1919 std::size_t leaf_nodes = count + one_szt - std::size_t(one_szt << detail::floor_log2(count + one_szt));
1920 compress_subtree(super_root, leaf_nodes); //create deepest leaves
1921 std::size_t vine_nodes = count - leaf_nodes;
1922 while(vine_nodes > 1){
1924 compress_subtree(super_root, vine_nodes);
1927 //Update parents of nodes still in the in the original vine line
1928 //as those have not been updated by subtree_to_vine or compress_subtree
1929 for ( node_ptr q = super_root, p = NodeTraits::get_right(super_root)
1931 ; q = p, p = NodeTraits::get_right(p)){
1932 NodeTraits::set_parent(p, q);
1936 //! <b>Requires</b>: "n" must be a node inserted in a tree.
1938 //! <b>Effects</b>: Returns a pointer to the header node of the tree.
1940 //! <b>Complexity</b>: Logarithmic.
1942 //! <b>Throws</b>: Nothing.
1943 static node_ptr get_root(const node_ptr & node)
1945 BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node)));
1946 node_ptr x = NodeTraits::get_parent(node);
1948 while(!is_header(x)){
1949 x = NodeTraits::get_parent(x);
1958 template <class Cloner, class Disposer>
1959 static node_ptr clone_subtree
1960 (const const_node_ptr &source_parent, const node_ptr &target_parent
1961 , Cloner cloner, Disposer disposer
1962 , node_ptr &leftmost_out, node_ptr &rightmost_out
1965 node_ptr target_sub_root = target_parent;
1966 node_ptr source_root = NodeTraits::get_parent(source_parent);
1968 leftmost_out = rightmost_out = source_root;
1971 //We'll calculate leftmost and rightmost nodes while iterating
1972 node_ptr current = source_root;
1973 node_ptr insertion_point = target_sub_root = cloner(current);
1975 //We'll calculate leftmost and rightmost nodes while iterating
1976 node_ptr leftmost = target_sub_root;
1977 node_ptr rightmost = target_sub_root;
1979 //First set the subroot
1980 NodeTraits::set_left(target_sub_root, node_ptr());
1981 NodeTraits::set_right(target_sub_root, node_ptr());
1982 NodeTraits::set_parent(target_sub_root, target_parent);
1984 dispose_subtree_disposer<Disposer> rollback(disposer, target_sub_root);
1986 //First clone left nodes
1987 if( NodeTraits::get_left(current) &&
1988 !NodeTraits::get_left(insertion_point)) {
1989 current = NodeTraits::get_left(current);
1990 node_ptr temp = insertion_point;
1991 //Clone and mark as leaf
1992 insertion_point = cloner(current);
1993 NodeTraits::set_left (insertion_point, node_ptr());
1994 NodeTraits::set_right (insertion_point, node_ptr());
1996 NodeTraits::set_parent(insertion_point, temp);
1997 NodeTraits::set_left (temp, insertion_point);
1999 if(rightmost == target_sub_root)
2000 leftmost = insertion_point;
2002 //Then clone right nodes
2003 else if( NodeTraits::get_right(current) &&
2004 !NodeTraits::get_right(insertion_point)){
2005 current = NodeTraits::get_right(current);
2006 node_ptr temp = insertion_point;
2007 //Clone and mark as leaf
2008 insertion_point = cloner(current);
2009 NodeTraits::set_left (insertion_point, node_ptr());
2010 NodeTraits::set_right (insertion_point, node_ptr());
2012 NodeTraits::set_parent(insertion_point, temp);
2013 NodeTraits::set_right (temp, insertion_point);
2015 rightmost = insertion_point;
2018 else if(current == source_root){
2022 //Branch completed, go up searching more nodes to clone
2023 current = NodeTraits::get_parent(current);
2024 insertion_point = NodeTraits::get_parent(insertion_point);
2028 leftmost_out = leftmost;
2029 rightmost_out = rightmost;
2031 return target_sub_root;
2034 template<class Disposer>
2035 static void dispose_subtree(node_ptr x, Disposer disposer)
2038 node_ptr save(NodeTraits::get_left(x));
2041 NodeTraits::set_left(x, NodeTraits::get_right(save));
2042 NodeTraits::set_right(save, x);
2045 save = NodeTraits::get_right(x);
2053 template<class KeyType, class KeyNodePtrCompare>
2054 static node_ptr lower_bound_loop
2055 (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp)
2059 x = NodeTraits::get_right(x);
2063 x = NodeTraits::get_left(x);
2069 template<class KeyType, class KeyNodePtrCompare>
2070 static node_ptr upper_bound_loop
2071 (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp)
2076 x = NodeTraits::get_left(x);
2079 x = NodeTraits::get_right(x);
2085 template<class Checker>
2086 static void check_subtree(const const_node_ptr& node, Checker checker, typename Checker::return_type& check_return)
2088 const_node_ptr left = NodeTraits::get_left(node);
2089 const_node_ptr right = NodeTraits::get_right(node);
2090 typename Checker::return_type check_return_left;
2091 typename Checker::return_type check_return_right;
2094 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(left) == node);
2095 check_subtree(left, checker, check_return_left);
2099 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(right) == node);
2100 check_subtree(right, checker, check_return_right);
2102 checker(node, check_return_left, check_return_right, check_return);
2108 template<class NodeTraits>
2109 struct get_algo<BsTreeAlgorithms, NodeTraits>
2111 typedef bstree_algorithms<NodeTraits> type;
2114 template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
2115 struct get_node_checker<BsTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
2117 typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
2122 } //namespace intrusive
2125 #include <boost/intrusive/detail/config_end.hpp>
2127 #endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP