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
17 #include <boost/intrusive/detail/config_begin.hpp>
18 #include <boost/intrusive/intrusive_fwd.hpp>
19 #include <boost/intrusive/detail/bstree_algorithms_base.hpp>
20 #include <boost/intrusive/detail/assert.hpp>
21 #include <boost/intrusive/detail/uncast.hpp>
22 #include <boost/intrusive/detail/math.hpp>
23 #include <boost/intrusive/detail/algo_type.hpp>
25 #include <boost/intrusive/detail/minimal_pair_header.hpp>
27 #if defined(BOOST_HAS_PRAGMA_ONCE)
36 //! This type is the information that will be filled by insert_unique_check
37 template <class NodePtr>
38 struct insert_commit_data_t
40 BOOST_INTRUSIVE_FORCEINLINE insert_commit_data_t()
41 : link_left(false), node()
47 template <class NodePtr>
48 struct data_for_rebalance_t
57 template<class ValueTraits, class NodePtrCompare, class ExtraChecker>
58 struct bstree_node_checker
61 typedef ExtraChecker base_checker_t;
62 typedef ValueTraits value_traits;
63 typedef typename value_traits::node_traits node_traits;
64 typedef typename node_traits::const_node_ptr const_node_ptr;
67 : public base_checker_t::return_type
69 BOOST_INTRUSIVE_FORCEINLINE return_type()
70 : min_key_node_ptr(const_node_ptr()), max_key_node_ptr(const_node_ptr()), node_count(0)
73 const_node_ptr min_key_node_ptr;
74 const_node_ptr max_key_node_ptr;
78 BOOST_INTRUSIVE_FORCEINLINE bstree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
79 : base_checker_t(extra_checker), comp_(comp)
82 void operator () (const const_node_ptr& p,
83 const return_type& check_return_left, const return_type& check_return_right,
84 return_type& check_return)
86 if (check_return_left.max_key_node_ptr)
87 BOOST_INTRUSIVE_INVARIANT_ASSERT(!comp_(p, check_return_left.max_key_node_ptr));
88 if (check_return_right.min_key_node_ptr)
89 BOOST_INTRUSIVE_INVARIANT_ASSERT(!comp_(check_return_right.min_key_node_ptr, p));
90 check_return.min_key_node_ptr = node_traits::get_left(p)? check_return_left.min_key_node_ptr : p;
91 check_return.max_key_node_ptr = node_traits::get_right(p)? check_return_right.max_key_node_ptr : p;
92 check_return.node_count = check_return_left.node_count + check_return_right.node_count + 1;
93 base_checker_t::operator()(p, check_return_left, check_return_right, check_return);
96 const NodePtrCompare comp_;
105 //! This is an implementation of a binary search tree.
106 //! A node in the search tree has references to its children and its parent. This
107 //! is to allow traversal of the whole tree from a given node making the
108 //! implementation of iterator a pointer to a node.
109 //! At the top of the tree a node is used specially. This node's parent pointer
110 //! is pointing to the root of the tree. Its left pointer points to the
111 //! leftmost node in the tree and the right pointer to the rightmost one.
112 //! This node is used to represent the end-iterator.
115 //! header------------------------------>| |
117 //! +----------(left)--------| |--------(right)---------+
124 //! root of tree ..|......................> | | |
127 //! | +-------+---------+-------+ |
133 //! | +---------+ +---------+ |
137 //! | +--+---------+--+ +--+---------+--+ |
141 //! | +---+-----+ +-----+---+ +---+-----+ +-----+---+ |
142 //! +-->| | | | | | | |<--+
143 //! | A | | C | | E | | G |
145 //! +---------+ +---------+ +---------+ +---------+
147 //! bstree_algorithms is configured with a NodeTraits class, which encapsulates the
148 //! information about the node to be manipulated. NodeTraits must support the
149 //! following interface:
153 //! <tt>node</tt>: The type of the node that forms the binary search tree
155 //! <tt>node_ptr</tt>: A pointer to a node
157 //! <tt>const_node_ptr</tt>: A pointer to a const node
159 //! <b>Static functions</b>:
161 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
163 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
165 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
167 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
169 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
171 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
172 template<class NodeTraits>
173 class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
176 typedef typename NodeTraits::node node;
177 typedef NodeTraits node_traits;
178 typedef typename NodeTraits::node_ptr node_ptr;
179 typedef typename NodeTraits::const_node_ptr const_node_ptr;
180 typedef insert_commit_data_t<node_ptr> insert_commit_data;
181 typedef data_for_rebalance_t<node_ptr> data_for_rebalance;
184 typedef bstree_algorithms<NodeTraits> this_type;
185 typedef bstree_algorithms_base<NodeTraits> base_type;
187 template<class Disposer>
188 struct dispose_subtree_disposer
190 BOOST_INTRUSIVE_FORCEINLINE dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree)
191 : disposer_(&disp), subtree_(subtree)
194 BOOST_INTRUSIVE_FORCEINLINE void release()
197 BOOST_INTRUSIVE_FORCEINLINE ~dispose_subtree_disposer()
200 dispose_subtree(subtree_, *disposer_);
204 const node_ptr subtree_;
210 //! <b>Requires</b>: 'header' is the header node of a tree.
212 //! <b>Effects</b>: Returns the first node of the tree, the header if the tree is empty.
214 //! <b>Complexity</b>: Constant time.
216 //! <b>Throws</b>: Nothing.
217 BOOST_INTRUSIVE_FORCEINLINE static node_ptr begin_node(const const_node_ptr & header)
218 { return node_traits::get_left(header); }
220 //! <b>Requires</b>: 'header' is the header node of a tree.
222 //! <b>Effects</b>: Returns the header of the tree.
224 //! <b>Complexity</b>: Constant time.
226 //! <b>Throws</b>: Nothing.
227 BOOST_INTRUSIVE_FORCEINLINE static node_ptr end_node(const const_node_ptr & header)
228 { return detail::uncast(header); }
230 //! <b>Requires</b>: 'header' is the header node of a tree.
232 //! <b>Effects</b>: Returns the root of the tree if any, header otherwise
234 //! <b>Complexity</b>: Constant time.
236 //! <b>Throws</b>: Nothing.
237 BOOST_INTRUSIVE_FORCEINLINE static node_ptr root_node(const const_node_ptr & header)
239 node_ptr p = node_traits::get_parent(header);
240 return p ? p : detail::uncast(header);
243 //! <b>Requires</b>: 'node' is a node of the tree or a node initialized
244 //! by init(...) or init_node.
246 //! <b>Effects</b>: Returns true if the node is initialized by init() or init_node().
248 //! <b>Complexity</b>: Constant time.
250 //! <b>Throws</b>: Nothing.
251 BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & node)
252 { return !NodeTraits::get_parent(node); }
254 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
255 //! <b>Requires</b>: 'node' is a node of the tree or a header node.
257 //! <b>Effects</b>: Returns the header of the tree.
259 //! <b>Complexity</b>: Logarithmic.
261 //! <b>Throws</b>: Nothing.
262 static node_ptr get_header(const const_node_ptr & node);
265 //! <b>Requires</b>: node1 and node2 can't be header nodes
268 //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
269 //! in the position node2 before the function. node2 will be inserted in the
270 //! position node1 had before the function.
272 //! <b>Complexity</b>: Logarithmic.
274 //! <b>Throws</b>: Nothing.
276 //! <b>Note</b>: This function will break container ordering invariants if
277 //! node1 and node2 are not equivalent according to the ordering rules.
279 //!Experimental function
280 static void swap_nodes(const node_ptr & node1, const node_ptr & node2)
285 node_ptr header1(base_type::get_header(node1)), header2(base_type::get_header(node2));
286 swap_nodes(node1, header1, node2, header2);
289 //! <b>Requires</b>: node1 and node2 can't be header nodes
290 //! of two trees with header header1 and header2.
292 //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
293 //! in the position node2 before the function. node2 will be inserted in the
294 //! position node1 had before the function.
296 //! <b>Complexity</b>: Constant.
298 //! <b>Throws</b>: Nothing.
300 //! <b>Note</b>: This function will break container ordering invariants if
301 //! node1 and node2 are not equivalent according to the ordering rules.
303 //!Experimental function
304 static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2)
309 //node1 and node2 must not be header nodes
310 //BOOST_INTRUSIVE_INVARIANT_ASSERT((header1 != node1 && header2 != node2));
311 if(header1 != header2){
312 //Update header1 if necessary
313 if(node1 == NodeTraits::get_left(header1)){
314 NodeTraits::set_left(header1, node2);
317 if(node1 == NodeTraits::get_right(header1)){
318 NodeTraits::set_right(header1, node2);
321 if(node1 == NodeTraits::get_parent(header1)){
322 NodeTraits::set_parent(header1, node2);
325 //Update header2 if necessary
326 if(node2 == NodeTraits::get_left(header2)){
327 NodeTraits::set_left(header2, node1);
330 if(node2 == NodeTraits::get_right(header2)){
331 NodeTraits::set_right(header2, node1);
334 if(node2 == NodeTraits::get_parent(header2)){
335 NodeTraits::set_parent(header2, node1);
339 //If both nodes are from the same tree
340 //Update header if necessary
341 if(node1 == NodeTraits::get_left(header1)){
342 NodeTraits::set_left(header1, node2);
344 else if(node2 == NodeTraits::get_left(header2)){
345 NodeTraits::set_left(header2, node1);
348 if(node1 == NodeTraits::get_right(header1)){
349 NodeTraits::set_right(header1, node2);
351 else if(node2 == NodeTraits::get_right(header2)){
352 NodeTraits::set_right(header2, node1);
355 if(node1 == NodeTraits::get_parent(header1)){
356 NodeTraits::set_parent(header1, node2);
358 else if(node2 == NodeTraits::get_parent(header2)){
359 NodeTraits::set_parent(header2, node1);
362 //Adjust data in nodes to be swapped
363 //so that final link swap works as expected
364 if(node1 == NodeTraits::get_parent(node2)){
365 NodeTraits::set_parent(node2, node2);
367 if(node2 == NodeTraits::get_right(node1)){
368 NodeTraits::set_right(node1, node1);
371 NodeTraits::set_left(node1, node1);
374 else if(node2 == NodeTraits::get_parent(node1)){
375 NodeTraits::set_parent(node1, node1);
377 if(node1 == NodeTraits::get_right(node2)){
378 NodeTraits::set_right(node2, node2);
381 NodeTraits::set_left(node2, node2);
386 //Now swap all the links
389 temp = NodeTraits::get_left(node1);
390 NodeTraits::set_left(node1, NodeTraits::get_left(node2));
391 NodeTraits::set_left(node2, temp);
393 temp = NodeTraits::get_right(node1);
394 NodeTraits::set_right(node1, NodeTraits::get_right(node2));
395 NodeTraits::set_right(node2, temp);
397 temp = NodeTraits::get_parent(node1);
398 NodeTraits::set_parent(node1, NodeTraits::get_parent(node2));
399 NodeTraits::set_parent(node2, temp);
401 //Now adjust adjacent nodes for newly inserted node 1
402 if((temp = NodeTraits::get_left(node1))){
403 NodeTraits::set_parent(temp, node1);
405 if((temp = NodeTraits::get_right(node1))){
406 NodeTraits::set_parent(temp, node1);
408 if((temp = NodeTraits::get_parent(node1)) &&
409 //The header has been already updated so avoid it
411 if(NodeTraits::get_left(temp) == node2){
412 NodeTraits::set_left(temp, node1);
414 if(NodeTraits::get_right(temp) == node2){
415 NodeTraits::set_right(temp, node1);
418 //Now adjust adjacent nodes for newly inserted node 2
419 if((temp = NodeTraits::get_left(node2))){
420 NodeTraits::set_parent(temp, node2);
422 if((temp = NodeTraits::get_right(node2))){
423 NodeTraits::set_parent(temp, node2);
425 if((temp = NodeTraits::get_parent(node2)) &&
426 //The header has been already updated so avoid it
428 if(NodeTraits::get_left(temp) == node1){
429 NodeTraits::set_left(temp, node2);
431 if(NodeTraits::get_right(temp) == node1){
432 NodeTraits::set_right(temp, node2);
437 //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
438 //! and new_node must not be inserted in a tree.
440 //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
441 //! tree with new_node. The tree does not need to be rebalanced
443 //! <b>Complexity</b>: Logarithmic.
445 //! <b>Throws</b>: Nothing.
447 //! <b>Note</b>: This function will break container ordering invariants if
448 //! new_node is not equivalent to node_to_be_replaced according to the
449 //! ordering rules. This function is faster than erasing and inserting
450 //! the node, since no rebalancing and comparison is needed. Experimental function
451 BOOST_INTRUSIVE_FORCEINLINE static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
453 if(node_to_be_replaced == new_node)
455 replace_node(node_to_be_replaced, base_type::get_header(node_to_be_replaced), new_node);
458 //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
459 //! with header "header" and new_node must not be inserted in a tree.
461 //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
462 //! tree with new_node. The tree does not need to be rebalanced
464 //! <b>Complexity</b>: Constant.
466 //! <b>Throws</b>: Nothing.
468 //! <b>Note</b>: This function will break container ordering invariants if
469 //! new_node is not equivalent to node_to_be_replaced according to the
470 //! ordering rules. This function is faster than erasing and inserting
471 //! the node, since no rebalancing or comparison is needed. Experimental function
472 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
474 if(node_to_be_replaced == new_node)
477 //Update header if necessary
478 if(node_to_be_replaced == NodeTraits::get_left(header)){
479 NodeTraits::set_left(header, new_node);
482 if(node_to_be_replaced == NodeTraits::get_right(header)){
483 NodeTraits::set_right(header, new_node);
486 if(node_to_be_replaced == NodeTraits::get_parent(header)){
487 NodeTraits::set_parent(header, new_node);
490 //Now set data from the original node
492 NodeTraits::set_left(new_node, NodeTraits::get_left(node_to_be_replaced));
493 NodeTraits::set_right(new_node, NodeTraits::get_right(node_to_be_replaced));
494 NodeTraits::set_parent(new_node, NodeTraits::get_parent(node_to_be_replaced));
496 //Now adjust adjacent nodes for newly inserted node
497 if((temp = NodeTraits::get_left(new_node))){
498 NodeTraits::set_parent(temp, new_node);
500 if((temp = NodeTraits::get_right(new_node))){
501 NodeTraits::set_parent(temp, new_node);
503 if((temp = NodeTraits::get_parent(new_node)) &&
504 //The header has been already updated so avoid it
506 if(NodeTraits::get_left(temp) == node_to_be_replaced){
507 NodeTraits::set_left(temp, new_node);
509 if(NodeTraits::get_right(temp) == node_to_be_replaced){
510 NodeTraits::set_right(temp, new_node);
515 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
516 //! <b>Requires</b>: 'node' is a node from the tree except the header.
518 //! <b>Effects</b>: Returns the next node of the tree.
520 //! <b>Complexity</b>: Average constant time.
522 //! <b>Throws</b>: Nothing.
523 static node_ptr next_node(const node_ptr & node);
525 //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node.
527 //! <b>Effects</b>: Returns the previous node of the tree.
529 //! <b>Complexity</b>: Average constant time.
531 //! <b>Throws</b>: Nothing.
532 static node_ptr prev_node(const node_ptr & node);
534 //! <b>Requires</b>: 'node' is a node of a tree but not the header.
536 //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
538 //! <b>Complexity</b>: Logarithmic to the size of the subtree.
540 //! <b>Throws</b>: Nothing.
541 static node_ptr minimum(node_ptr node);
543 //! <b>Requires</b>: 'node' is a node of a tree but not the header.
545 //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
547 //! <b>Complexity</b>: Logarithmic to the size of the subtree.
549 //! <b>Throws</b>: Nothing.
550 static node_ptr maximum(node_ptr node);
553 //! <b>Requires</b>: 'node' must not be part of any tree.
555 //! <b>Effects</b>: After the function unique(node) == true.
557 //! <b>Complexity</b>: Constant.
559 //! <b>Throws</b>: Nothing.
561 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
562 BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & node)
564 NodeTraits::set_parent(node, node_ptr());
565 NodeTraits::set_left(node, node_ptr());
566 NodeTraits::set_right(node, node_ptr());
569 //! <b>Effects</b>: Returns true if node is in the same state as if called init(node)
571 //! <b>Complexity</b>: Constant.
573 //! <b>Throws</b>: Nothing.
574 BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & node)
576 return !NodeTraits::get_parent(node) &&
577 !NodeTraits::get_left(node) &&
578 !NodeTraits::get_right(node) ;
581 //! <b>Requires</b>: node must not be part of any tree.
583 //! <b>Effects</b>: Initializes the header to represent an empty tree.
584 //! unique(header) == true.
586 //! <b>Complexity</b>: Constant.
588 //! <b>Throws</b>: Nothing.
590 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
591 BOOST_INTRUSIVE_FORCEINLINE static void init_header(const node_ptr & header)
593 NodeTraits::set_parent(header, node_ptr());
594 NodeTraits::set_left(header, header);
595 NodeTraits::set_right(header, header);
598 //! <b>Requires</b>: "disposer" must be an object function
599 //! taking a node_ptr parameter and shouldn't throw.
601 //! <b>Effects</b>: Empties the target tree calling
602 //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
603 //! except the header.
605 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
606 //! number of elements of tree target tree when calling this function.
608 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
609 template<class Disposer>
610 static void clear_and_dispose(const node_ptr & header, Disposer disposer)
612 node_ptr source_root = NodeTraits::get_parent(header);
615 dispose_subtree(source_root, disposer);
619 //! <b>Requires</b>: header is the header of a tree.
621 //! <b>Effects</b>: Unlinks the leftmost node from the tree, and
622 //! updates the header link to the new leftmost node.
624 //! <b>Complexity</b>: Average complexity is constant time.
626 //! <b>Throws</b>: Nothing.
628 //! <b>Notes</b>: This function breaks the tree and the tree can
629 //! only be used for more unlink_leftmost_without_rebalance calls.
630 //! This function is normally used to achieve a step by step
631 //! controlled destruction of the tree.
632 static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header)
634 node_ptr leftmost = NodeTraits::get_left(header);
635 if (leftmost == header)
637 node_ptr leftmost_parent(NodeTraits::get_parent(leftmost));
638 node_ptr leftmost_right (NodeTraits::get_right(leftmost));
639 bool is_root = leftmost_parent == header;
642 NodeTraits::set_parent(leftmost_right, leftmost_parent);
643 NodeTraits::set_left(header, base_type::minimum(leftmost_right));
646 NodeTraits::set_parent(header, leftmost_right);
648 NodeTraits::set_left(NodeTraits::get_parent(header), leftmost_right);
651 NodeTraits::set_parent(header, node_ptr());
652 NodeTraits::set_left(header, header);
653 NodeTraits::set_right(header, header);
656 NodeTraits::set_left(leftmost_parent, node_ptr());
657 NodeTraits::set_left(header, leftmost_parent);
662 //! <b>Requires</b>: node is a node of the tree but it's not the header.
664 //! <b>Effects</b>: Returns the number of nodes of the subtree.
666 //! <b>Complexity</b>: Linear time.
668 //! <b>Throws</b>: Nothing.
669 static std::size_t size(const const_node_ptr & header)
671 node_ptr beg(begin_node(header));
672 node_ptr end(end_node(header));
674 for(;beg != end; beg = base_type::next_node(beg)) ++i;
678 //! <b>Requires</b>: header1 and header2 must be the header nodes
681 //! <b>Effects</b>: Swaps two trees. After the function header1 will contain
682 //! links to the second tree and header2 will have links to the first tree.
684 //! <b>Complexity</b>: Constant.
686 //! <b>Throws</b>: Nothing.
687 static void swap_tree(const node_ptr & header1, const node_ptr & header2)
689 if(header1 == header2)
695 tmp = NodeTraits::get_parent(header1);
696 NodeTraits::set_parent(header1, NodeTraits::get_parent(header2));
697 NodeTraits::set_parent(header2, tmp);
699 tmp = NodeTraits::get_left(header1);
700 NodeTraits::set_left(header1, NodeTraits::get_left(header2));
701 NodeTraits::set_left(header2, tmp);
703 tmp = NodeTraits::get_right(header1);
704 NodeTraits::set_right(header1, NodeTraits::get_right(header2));
705 NodeTraits::set_right(header2, tmp);
708 node_ptr h1_parent(NodeTraits::get_parent(header1));
710 NodeTraits::set_parent(h1_parent, header1);
713 NodeTraits::set_left(header1, header1);
714 NodeTraits::set_right(header1, header1);
717 node_ptr h2_parent(NodeTraits::get_parent(header2));
719 NodeTraits::set_parent(h2_parent, header2);
722 NodeTraits::set_left(header2, header2);
723 NodeTraits::set_right(header2, header2);
727 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
728 //! <b>Requires</b>: p is a node of a tree.
730 //! <b>Effects</b>: Returns true if p is the header of the tree.
732 //! <b>Complexity</b>: Constant.
734 //! <b>Throws</b>: Nothing.
735 static bool is_header(const const_node_ptr & p);
738 //! <b>Requires</b>: "header" must be the header node of a tree.
739 //! KeyNodePtrCompare is a function object that induces a strict weak
740 //! ordering compatible with the strict weak ordering used to create the
741 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
743 //! <b>Effects</b>: Returns a node_ptr to the first element that is equivalent to
744 //! "key" according to "comp" or "header" if that element does not exist.
746 //! <b>Complexity</b>: Logarithmic.
748 //! <b>Throws</b>: If "comp" throws.
749 template<class KeyType, class KeyNodePtrCompare>
751 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
753 node_ptr end = detail::uncast(header);
754 node_ptr y = lower_bound(header, key, comp);
755 return (y == end || comp(key, y)) ? end : y;
758 //! <b>Requires</b>: "header" must be the header node of a tree.
759 //! KeyNodePtrCompare is a function object that induces a strict weak
760 //! ordering compatible with the strict weak ordering used to create the
761 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
762 //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
763 //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be true.
765 //! <b>Effects</b>: Returns an a pair with the following criteria:
767 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
769 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
771 //! <b>Complexity</b>: Logarithmic.
773 //! <b>Throws</b>: If "comp" throws.
775 //! <b>Note</b>: This function can be more efficient than calling upper_bound
776 //! and lower_bound for lower_key and upper_key.
778 //! <b>Note</b>: Experimental function, the interface might change.
779 template< class KeyType, class KeyNodePtrCompare>
780 static std::pair<node_ptr, node_ptr> bounded_range
781 ( const const_node_ptr & header
782 , const KeyType &lower_key
783 , const KeyType &upper_key
784 , KeyNodePtrCompare comp
788 node_ptr y = detail::uncast(header);
789 node_ptr x = NodeTraits::get_parent(header);
792 //If x is less than lower_key the target
793 //range is on the right part
794 if(comp(x, lower_key)){
795 //Check for invalid input range
796 BOOST_INTRUSIVE_INVARIANT_ASSERT(comp(x, upper_key));
797 x = NodeTraits::get_right(x);
799 //If the upper_key is less than x, the target
800 //range is on the left part
801 else if(comp(upper_key, x)){
803 x = NodeTraits::get_left(x);
806 //x is inside the bounded range(lower_key <= x <= upper_key),
807 //so we must split lower and upper searches
809 //Sanity check: if lower_key and upper_key are equal, then both left_closed and right_closed can't be false
810 BOOST_INTRUSIVE_INVARIANT_ASSERT(left_closed || right_closed || comp(lower_key, x) || comp(x, upper_key));
811 return std::pair<node_ptr,node_ptr>(
813 //If left_closed, then comp(x, lower_key) is already the lower_bound
814 //condition so we save one comparison and go to the next level
815 //following traditional lower_bound algo
816 ? lower_bound_loop(NodeTraits::get_left(x), x, lower_key, comp)
817 //If left-open, comp(x, lower_key) is not the upper_bound algo
818 //condition so we must recheck current 'x' node with upper_bound algo
819 : upper_bound_loop(x, y, lower_key, comp)
822 //If right_closed, then comp(upper_key, x) is already the upper_bound
823 //condition so we can save one comparison and go to the next level
824 //following lower_bound algo
825 ? upper_bound_loop(NodeTraits::get_right(x), y, upper_key, comp)
826 //If right-open, comp(upper_key, x) is not the lower_bound algo
827 //condition so we must recheck current 'x' node with lower_bound algo
828 : lower_bound_loop(x, y, upper_key, comp)
832 return std::pair<node_ptr,node_ptr> (y, y);
835 //! <b>Requires</b>: "header" must be the header node of a tree.
836 //! KeyNodePtrCompare is a function object that induces a strict weak
837 //! ordering compatible with the strict weak ordering used to create the
838 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
840 //! <b>Effects</b>: Returns the number of elements with a key equivalent to "key"
841 //! according to "comp".
843 //! <b>Complexity</b>: Logarithmic.
845 //! <b>Throws</b>: If "comp" throws.
846 template<class KeyType, class KeyNodePtrCompare>
847 static std::size_t count
848 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
850 std::pair<node_ptr, node_ptr> ret = equal_range(header, key, comp);
852 while(ret.first != ret.second){
854 ret.first = base_type::next_node(ret.first);
859 //! <b>Requires</b>: "header" must be the header node of a tree.
860 //! KeyNodePtrCompare is a function object that induces a strict weak
861 //! ordering compatible with the strict weak ordering used to create the
862 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
864 //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
865 //! all elements that are equivalent to "key" according to "comp" or an
866 //! empty range that indicates the position where those elements would be
867 //! if there are no equivalent elements.
869 //! <b>Complexity</b>: Logarithmic.
871 //! <b>Throws</b>: If "comp" throws.
872 template<class KeyType, class KeyNodePtrCompare>
873 BOOST_INTRUSIVE_FORCEINLINE static std::pair<node_ptr, node_ptr> equal_range
874 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
876 return bounded_range(header, key, key, comp, true, true);
879 //! <b>Requires</b>: "header" must be the header node of a tree.
880 //! KeyNodePtrCompare is a function object that induces a strict weak
881 //! ordering compatible with the strict weak ordering used to create the
882 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
884 //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
885 //! the first element that is equivalent to "key" according to "comp" or an
886 //! empty range that indicates the position where that element would be
887 //! if there are no equivalent elements.
889 //! <b>Complexity</b>: Logarithmic.
891 //! <b>Throws</b>: If "comp" throws.
892 template<class KeyType, class KeyNodePtrCompare>
893 static std::pair<node_ptr, node_ptr> lower_bound_range
894 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
896 node_ptr const lb(lower_bound(header, key, comp));
897 std::pair<node_ptr, node_ptr> ret_ii(lb, lb);
898 if(lb != header && !comp(key, lb)){
899 ret_ii.second = base_type::next_node(ret_ii.second);
904 //! <b>Requires</b>: "header" must be the header node of a tree.
905 //! KeyNodePtrCompare is a function object that induces a strict weak
906 //! ordering compatible with the strict weak ordering used to create the
907 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
909 //! <b>Effects</b>: Returns a node_ptr to the first element that is
910 //! not less than "key" according to "comp" or "header" if that element does
913 //! <b>Complexity</b>: Logarithmic.
915 //! <b>Throws</b>: If "comp" throws.
916 template<class KeyType, class KeyNodePtrCompare>
917 BOOST_INTRUSIVE_FORCEINLINE static node_ptr lower_bound
918 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
920 return lower_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp);
923 //! <b>Requires</b>: "header" must be the header node of a tree.
924 //! KeyNodePtrCompare is a function object that induces a strict weak
925 //! ordering compatible with the strict weak ordering used to create the
926 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
928 //! <b>Effects</b>: Returns a node_ptr to the first element that is greater
929 //! than "key" according to "comp" or "header" if that element does not exist.
931 //! <b>Complexity</b>: Logarithmic.
933 //! <b>Throws</b>: If "comp" throws.
934 template<class KeyType, class KeyNodePtrCompare>
935 BOOST_INTRUSIVE_FORCEINLINE static node_ptr upper_bound
936 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
938 return upper_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp);
941 //! <b>Requires</b>: "header" must be the header node of a tree.
942 //! "commit_data" must have been obtained from a previous call to
943 //! "insert_unique_check". No objects should have been inserted or erased
944 //! from the set between the "insert_unique_check" that filled "commit_data"
945 //! and the call to "insert_commit".
948 //! <b>Effects</b>: Inserts new_node in the set using the information obtained
949 //! from the "commit_data" that a previous "insert_check" filled.
951 //! <b>Complexity</b>: Constant time.
953 //! <b>Throws</b>: Nothing.
955 //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been
956 //! previously executed to fill "commit_data". No value should be inserted or
957 //! erased between the "insert_check" and "insert_commit" calls.
958 BOOST_INTRUSIVE_FORCEINLINE static void insert_unique_commit
959 (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
960 { return insert_commit(header, new_value, commit_data); }
962 //! <b>Requires</b>: "header" must be the header node of a tree.
963 //! KeyNodePtrCompare is a function object that induces a strict weak
964 //! ordering compatible with the strict weak ordering used to create the
965 //! the tree. NodePtrCompare compares KeyType with a node_ptr.
967 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
968 //! tree according to "comp" and obtains the needed information to realize
969 //! a constant-time node insertion if there is no equivalent node.
971 //! <b>Returns</b>: If there is an equivalent value
972 //! returns a pair containing a node_ptr to the already present node
973 //! and false. If there is not equivalent key can be inserted returns true
974 //! in the returned pair's boolean and fills "commit_data" that is meant to
975 //! be used with the "insert_commit" function to achieve a constant-time
976 //! insertion function.
978 //! <b>Complexity</b>: Average complexity is at most logarithmic.
980 //! <b>Throws</b>: If "comp" throws.
982 //! <b>Notes</b>: This function is used to improve performance when constructing
983 //! a node is expensive and the user does not want to have two equivalent nodes
984 //! in the tree: if there is an equivalent value
985 //! the constructed object must be discarded. Many times, the part of the
986 //! node that is used to impose the order is much cheaper to construct
987 //! than the node and this function offers the possibility to use that part
988 //! to check if the insertion will be successful.
990 //! If the check is successful, the user can construct the node and use
991 //! "insert_commit" to insert the node in constant-time. This gives a total
992 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
994 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only
995 //! if no more objects are inserted or erased from the set.
996 template<class KeyType, class KeyNodePtrCompare>
997 static std::pair<node_ptr, bool> insert_unique_check
998 (const const_node_ptr & header, const KeyType &key
999 ,KeyNodePtrCompare comp, insert_commit_data &commit_data
1000 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1001 , std::size_t *pdepth = 0
1005 std::size_t depth = 0;
1006 node_ptr h(detail::uncast(header));
1008 node_ptr x(NodeTraits::get_parent(y));
1009 node_ptr prev = node_ptr();
1011 //Find the upper bound, cache the previous value and if we should
1012 //store it in the left or right node
1013 bool left_child = true;
1017 x = (left_child = comp(key, x)) ?
1018 NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x));
1021 if(pdepth) *pdepth = depth;
1023 //Since we've found the upper bound there is no other value with the same key if:
1024 // - There is no previous node
1025 // - The previous node is less than the key
1026 const bool not_present = !prev || comp(prev, key);
1028 commit_data.link_left = left_child;
1029 commit_data.node = y;
1031 return std::pair<node_ptr, bool>(prev, not_present);
1034 //! <b>Requires</b>: "header" must be the header node of a tree.
1035 //! KeyNodePtrCompare is a function object that induces a strict weak
1036 //! ordering compatible with the strict weak ordering used to create the
1037 //! the tree. NodePtrCompare compares KeyType with a node_ptr.
1038 //! "hint" is node from the "header"'s tree.
1040 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
1041 //! tree according to "comp" using "hint" as a hint to where it should be
1042 //! inserted and obtains the needed information to realize
1043 //! a constant-time node insertion if there is no equivalent node.
1044 //! If "hint" is the upper_bound the function has constant time
1045 //! complexity (two comparisons in the worst case).
1047 //! <b>Returns</b>: If there is an equivalent value
1048 //! returns a pair containing a node_ptr to the already present node
1049 //! and false. If there is not equivalent key can be inserted returns true
1050 //! in the returned pair's boolean and fills "commit_data" that is meant to
1051 //! be used with the "insert_commit" function to achieve a constant-time
1052 //! insertion function.
1054 //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is
1055 //! amortized constant time if new_node should be inserted immediately before "hint".
1057 //! <b>Throws</b>: If "comp" throws.
1059 //! <b>Notes</b>: This function is used to improve performance when constructing
1060 //! a node is expensive and the user does not want to have two equivalent nodes
1061 //! in the tree: if there is an equivalent value
1062 //! the constructed object must be discarded. Many times, the part of the
1063 //! node that is used to impose the order is much cheaper to construct
1064 //! than the node and this function offers the possibility to use that part
1065 //! to check if the insertion will be successful.
1067 //! If the check is successful, the user can construct the node and use
1068 //! "insert_commit" to insert the node in constant-time. This gives a total
1069 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
1071 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only
1072 //! if no more objects are inserted or erased from the set.
1073 template<class KeyType, class KeyNodePtrCompare>
1074 static std::pair<node_ptr, bool> insert_unique_check
1075 (const const_node_ptr & header, const node_ptr &hint, const KeyType &key
1076 ,KeyNodePtrCompare comp, insert_commit_data &commit_data
1077 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1078 , std::size_t *pdepth = 0
1082 //hint must be bigger than the key
1083 if(hint == header || comp(key, hint)){
1084 node_ptr prev(hint);
1085 //Previous value should be less than the key
1086 if(hint == begin_node(header) || comp((prev = base_type::prev_node(hint)), key)){
1087 commit_data.link_left = unique(header) || !NodeTraits::get_left(hint);
1088 commit_data.node = commit_data.link_left ? hint : prev;
1090 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1;
1092 return std::pair<node_ptr, bool>(node_ptr(), true);
1095 //Hint was wrong, use hintless insertion
1096 return insert_unique_check(header, key, comp, commit_data, pdepth);
1099 //! <b>Requires</b>: "header" must be the header node of a tree.
1100 //! NodePtrCompare is a function object that induces a strict weak
1101 //! ordering compatible with the strict weak ordering used to create the
1102 //! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from
1103 //! the "header"'s tree.
1105 //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to
1106 //! where it will be inserted. If "hint" is the upper_bound
1107 //! the insertion takes constant time (two comparisons in the worst case).
1109 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
1110 //! constant time if new_node is inserted immediately before "hint".
1112 //! <b>Throws</b>: If "comp" throws.
1113 template<class NodePtrCompare>
1114 static node_ptr insert_equal
1115 (const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp
1116 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1117 , std::size_t *pdepth = 0
1121 insert_commit_data commit_data;
1122 insert_equal_check(h, hint, new_node, comp, commit_data, pdepth);
1123 insert_commit(h, new_node, commit_data);
1127 //! <b>Requires</b>: "h" must be the header node of a tree.
1128 //! NodePtrCompare is a function object that induces a strict weak
1129 //! ordering compatible with the strict weak ordering used to create the
1130 //! the tree. NodePtrCompare compares two node_ptrs.
1132 //! <b>Effects</b>: Inserts new_node into the tree before the upper bound
1133 //! according to "comp".
1135 //! <b>Complexity</b>: Average complexity for insert element is at
1136 //! most logarithmic.
1138 //! <b>Throws</b>: If "comp" throws.
1139 template<class NodePtrCompare>
1140 static node_ptr insert_equal_upper_bound
1141 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
1142 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1143 , std::size_t *pdepth = 0
1147 insert_commit_data commit_data;
1148 insert_equal_upper_bound_check(h, new_node, comp, commit_data, pdepth);
1149 insert_commit(h, new_node, commit_data);
1153 //! <b>Requires</b>: "h" must be the header node of a tree.
1154 //! NodePtrCompare is a function object that induces a strict weak
1155 //! ordering compatible with the strict weak ordering used to create the
1156 //! the tree. NodePtrCompare compares two node_ptrs.
1158 //! <b>Effects</b>: Inserts new_node into the tree before the lower bound
1159 //! according to "comp".
1161 //! <b>Complexity</b>: Average complexity for insert element is at
1162 //! most logarithmic.
1164 //! <b>Throws</b>: If "comp" throws.
1165 template<class NodePtrCompare>
1166 static node_ptr insert_equal_lower_bound
1167 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
1168 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1169 , std::size_t *pdepth = 0
1173 insert_commit_data commit_data;
1174 insert_equal_lower_bound_check(h, new_node, comp, commit_data, pdepth);
1175 insert_commit(h, new_node, commit_data);
1179 //! <b>Requires</b>: "header" must be the header node of a tree.
1180 //! "pos" must be a valid iterator or header (end) node.
1181 //! "pos" must be an iterator pointing to the successor to "new_node"
1182 //! once inserted according to the order of already inserted nodes. This function does not
1183 //! check "pos" and this precondition must be guaranteed by the caller.
1185 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
1187 //! <b>Complexity</b>: Constant-time.
1189 //! <b>Throws</b>: Nothing.
1191 //! <b>Note</b>: If "pos" is not the successor of the newly inserted "new_node"
1192 //! tree invariants might be broken.
1193 static node_ptr insert_before
1194 (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node
1195 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1196 , std::size_t *pdepth = 0
1200 insert_commit_data commit_data;
1201 insert_before_check(header, pos, commit_data, pdepth);
1202 insert_commit(header, new_node, commit_data);
1206 //! <b>Requires</b>: "header" must be the header node of a tree.
1207 //! "new_node" must be, according to the used ordering no less than the
1208 //! greatest inserted key.
1210 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
1212 //! <b>Complexity</b>: Constant-time.
1214 //! <b>Throws</b>: Nothing.
1216 //! <b>Note</b>: If "new_node" is less than the greatest inserted key
1217 //! tree invariants are broken. This function is slightly faster than
1218 //! using "insert_before".
1219 static void push_back
1220 (const node_ptr & header, const node_ptr & new_node
1221 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1222 , std::size_t *pdepth = 0
1226 insert_commit_data commit_data;
1227 push_back_check(header, commit_data, pdepth);
1228 insert_commit(header, new_node, commit_data);
1231 //! <b>Requires</b>: "header" must be the header node of a tree.
1232 //! "new_node" must be, according to the used ordering, no greater than the
1233 //! lowest inserted key.
1235 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
1237 //! <b>Complexity</b>: Constant-time.
1239 //! <b>Throws</b>: Nothing.
1241 //! <b>Note</b>: If "new_node" is greater than the lowest inserted key
1242 //! tree invariants are broken. This function is slightly faster than
1243 //! using "insert_before".
1244 static void push_front
1245 (const node_ptr & header, const node_ptr & new_node
1246 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1247 , std::size_t *pdepth = 0
1251 insert_commit_data commit_data;
1252 push_front_check(header, commit_data, pdepth);
1253 insert_commit(header, new_node, commit_data);
1256 //! <b>Requires</b>: 'node' can't be a header node.
1258 //! <b>Effects</b>: Calculates the depth of a node: the depth of a
1259 //! node is the length (number of edges) of the path from the root
1260 //! to that node. (The root node is at depth 0.)
1262 //! <b>Complexity</b>: Logarithmic to the number of nodes in the tree.
1264 //! <b>Throws</b>: Nothing.
1265 static std::size_t depth(const_node_ptr node)
1267 std::size_t depth = 0;
1269 while(node != NodeTraits::get_parent(p_parent = NodeTraits::get_parent(node))){
1276 //! <b>Requires</b>: "cloner" must be a function
1277 //! object taking a node_ptr and returning a new cloned node of it. "disposer" must
1278 //! take a node_ptr and shouldn't throw.
1280 //! <b>Effects</b>: First empties target tree calling
1281 //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
1282 //! except the header.
1284 //! Then, duplicates the entire tree pointed by "source_header" cloning each
1285 //! source node with <tt>node_ptr Cloner::operator()(const node_ptr &)</tt> to obtain
1286 //! the nodes of the target tree. If "cloner" throws, the cloned target nodes
1287 //! are disposed using <tt>void disposer(const node_ptr &)</tt>.
1289 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the
1290 //! number of elements of tree target tree when calling this function.
1292 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
1293 template <class Cloner, class Disposer>
1295 (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
1297 if(!unique(target_header)){
1298 clear_and_dispose(target_header, disposer);
1301 node_ptr leftmost, rightmost;
1302 node_ptr new_root = clone_subtree
1303 (source_header, target_header, cloner, disposer, leftmost, rightmost);
1305 //Now update header node
1306 NodeTraits::set_parent(target_header, new_root);
1307 NodeTraits::set_left (target_header, leftmost);
1308 NodeTraits::set_right (target_header, rightmost);
1311 //! <b>Requires</b>: header must be the header of a tree, z a node
1312 //! of that tree and z != header.
1314 //! <b>Effects</b>: Erases node "z" from the tree with header "header".
1316 //! <b>Complexity</b>: Amortized constant time.
1318 //! <b>Throws</b>: Nothing.
1319 BOOST_INTRUSIVE_FORCEINLINE static void erase(const node_ptr & header, const node_ptr & z)
1321 data_for_rebalance ignored;
1322 erase(header, z, ignored);
1325 //! <b>Requires</b>: header1 and header2 must be the headers of trees tree1 and tree2
1326 //! respectively, z a non-header node of tree1. NodePtrCompare is the comparison
1327 //! function of tree1..
1329 //! <b>Effects</b>: Transfers node "z" from tree1 to tree2 if tree1 does not contain
1330 //! a node that is equivalent to z.
1332 //! <b>Returns</b>: True if the node was trasferred, false otherwise.
1334 //! <b>Complexity</b>: Logarithmic.
1336 //! <b>Throws</b>: If the comparison throws.
1337 template<class NodePtrCompare>
1338 BOOST_INTRUSIVE_FORCEINLINE static bool transfer_unique
1339 (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
1341 data_for_rebalance ignored;
1342 return transfer_unique(header1, comp, header2, z, ignored);
1345 //! <b>Requires</b>: header1 and header2 must be the headers of trees tree1 and tree2
1346 //! respectively, z a non-header node of tree1. NodePtrCompare is the comparison
1347 //! function of tree1..
1349 //! <b>Effects</b>: Transfers node "z" from tree1 to tree2.
1351 //! <b>Complexity</b>: Logarithmic.
1353 //! <b>Throws</b>: If the comparison throws.
1354 template<class NodePtrCompare>
1355 BOOST_INTRUSIVE_FORCEINLINE static void transfer_equal
1356 (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
1358 data_for_rebalance ignored;
1359 transfer_equal(header1, comp, header2, z, ignored);
1362 //! <b>Requires</b>: node is a tree node but not the header.
1364 //! <b>Effects</b>: Unlinks the node and rebalances the tree.
1366 //! <b>Complexity</b>: Average complexity is constant time.
1368 //! <b>Throws</b>: Nothing.
1369 static void unlink(const node_ptr & node)
1371 node_ptr x = NodeTraits::get_parent(node);
1373 while(!base_type::is_header(x))
1374 x = NodeTraits::get_parent(x);
1379 //! <b>Requires</b>: header must be the header of a tree.
1381 //! <b>Effects</b>: Rebalances the tree.
1383 //! <b>Throws</b>: Nothing.
1385 //! <b>Complexity</b>: Linear.
1386 static void rebalance(const node_ptr & header)
1388 node_ptr root = NodeTraits::get_parent(header);
1390 rebalance_subtree(root);
1394 //! <b>Requires</b>: old_root is a node of a tree. It shall not be null.
1396 //! <b>Effects</b>: Rebalances the subtree rooted at old_root.
1398 //! <b>Returns</b>: The new root of the subtree.
1400 //! <b>Throws</b>: Nothing.
1402 //! <b>Complexity</b>: Linear.
1403 static node_ptr rebalance_subtree(const node_ptr & old_root)
1406 //"Tree rebalancing in optimal time and space"
1407 //Quentin F. Stout and Bette L. Warren
1409 //To avoid irregularities in the algorithm (old_root can be a
1410 //left or right child or even the root of the tree) just put the
1411 //root as the right child of its parent. Before doing this backup
1412 //information to restore the original relationship after
1413 //the algorithm is applied.
1414 node_ptr super_root = NodeTraits::get_parent(old_root);
1415 BOOST_INTRUSIVE_INVARIANT_ASSERT(super_root);
1418 node_ptr super_root_right_backup = NodeTraits::get_right(super_root);
1419 bool super_root_is_header = NodeTraits::get_parent(super_root) == old_root;
1420 bool old_root_is_right = is_right_child(old_root);
1421 NodeTraits::set_right(super_root, old_root);
1424 subtree_to_vine(super_root, size);
1425 vine_to_subtree(super_root, size);
1426 node_ptr new_root = NodeTraits::get_right(super_root);
1429 if(super_root_is_header){
1430 NodeTraits::set_right(super_root, super_root_right_backup);
1431 NodeTraits::set_parent(super_root, new_root);
1433 else if(old_root_is_right){
1434 NodeTraits::set_right(super_root, new_root);
1437 NodeTraits::set_right(super_root, super_root_right_backup);
1438 NodeTraits::set_left(super_root, new_root);
1443 //! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user.
1445 //! <b>Requires</b>: header must be the header of a tree.
1447 //! <b>Complexity</b>: Linear time.
1449 //! <b>Note</b>: The method might not have effect when asserts are turned off (e.g., with NDEBUG).
1450 //! Experimental function, interface might change in future versions.
1451 template<class Checker>
1452 static void check(const const_node_ptr& header, Checker checker, typename Checker::return_type& checker_return)
1454 const_node_ptr root_node_ptr = NodeTraits::get_parent(header);
1455 if (!root_node_ptr){
1456 // check left&right header pointers
1457 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header);
1458 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header);
1461 // check parent pointer of root node
1462 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header);
1463 // check subtree from root
1464 check_subtree(root_node_ptr, checker, checker_return);
1465 // check left&right header pointers
1466 const_node_ptr p = root_node_ptr;
1467 while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); }
1468 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p);
1470 while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); }
1471 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p);
1477 template<class NodePtrCompare>
1478 static bool transfer_unique
1479 (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z, data_for_rebalance &info)
1481 insert_commit_data commit_data;
1482 bool const transferable = insert_unique_check(header1, z, comp, commit_data).second;
1484 erase(header2, z, info);
1485 insert_commit(header1, z, commit_data);
1487 return transferable;
1490 template<class NodePtrCompare>
1491 static void transfer_equal
1492 (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z, data_for_rebalance &info)
1494 insert_commit_data commit_data;
1495 insert_equal_upper_bound_check(header1, z, comp, commit_data);
1496 erase(header2, z, info);
1497 insert_commit(header1, z, commit_data);
1500 static void erase(const node_ptr & header, const node_ptr & z, data_for_rebalance &info)
1504 const node_ptr z_left(NodeTraits::get_left(z));
1505 const node_ptr z_right(NodeTraits::get_right(z));
1508 x = z_right; // x might be null.
1510 else if(!z_right){ // z has exactly one non-null child. y == z.
1511 x = z_left; // x is not null.
1515 // y = find z's successor
1516 y = base_type::minimum(z_right);
1517 x = NodeTraits::get_right(y); // x might be null.
1521 const node_ptr z_parent(NodeTraits::get_parent(z));
1522 const bool z_is_leftchild(NodeTraits::get_left(z_parent) == z);
1524 if(y != z){ //has two children and y is the minimum of z
1525 //y is z's successor and it has a null left child.
1526 //x is the right child of y (it can be null)
1527 //Relink y in place of z and link x with y's old parent
1528 NodeTraits::set_parent(z_left, y);
1529 NodeTraits::set_left(y, z_left);
1531 //Link y with the right tree of z
1532 NodeTraits::set_right(y, z_right);
1533 NodeTraits::set_parent(z_right, y);
1534 //Link x with y's old parent (y must be a left child)
1535 x_parent = NodeTraits::get_parent(y);
1536 BOOST_ASSERT(NodeTraits::get_left(x_parent) == y);
1538 NodeTraits::set_parent(x, x_parent);
1539 //Since y was the successor and not the right child of z, it must be a left child
1540 NodeTraits::set_left(x_parent, x);
1542 else{ //y was the right child of y so no need to fix x's position
1545 NodeTraits::set_parent(y, z_parent);
1546 this_type::set_child(header, y, z_parent, z_is_leftchild);
1548 else { // z has zero or one child, x is one child (it can be null)
1549 //Just link x to z's parent
1550 x_parent = z_parent;
1552 NodeTraits::set_parent(x, z_parent);
1553 this_type::set_child(header, x, z_parent, z_is_leftchild);
1555 //Now update leftmost/rightmost in case z was one of them
1556 if(NodeTraits::get_left(header) == z){
1557 //z_left must be null because z is the leftmost
1558 BOOST_ASSERT(!z_left);
1559 NodeTraits::set_left(header, !z_right ?
1560 z_parent : // makes leftmost == header if z == root
1561 base_type::minimum(z_right));
1563 if(NodeTraits::get_right(header) == z){
1564 //z_right must be null because z is the rightmost
1565 BOOST_ASSERT(!z_right);
1566 NodeTraits::set_right(header, !z_left ?
1567 z_parent : // makes rightmost == header if z == root
1568 base_type::maximum(z_left));
1572 //If z had 0/1 child, y == z and one of its children (and maybe null)
1573 //If z had 2 children, y is the successor of z and x is the right child of y
1576 //If z had 0/1 child, x_parent is the new parent of the old right child of y (z's successor)
1577 //If z had 2 children, x_parent is the new parent of y (z_parent)
1578 BOOST_ASSERT(!x || NodeTraits::get_parent(x) == x_parent);
1579 info.x_parent = x_parent;
1582 //! <b>Requires</b>: node is a node of the tree but it's not the header.
1584 //! <b>Effects</b>: Returns the number of nodes of the subtree.
1586 //! <b>Complexity</b>: Linear time.
1588 //! <b>Throws</b>: Nothing.
1589 static std::size_t subtree_size(const const_node_ptr & subtree)
1591 std::size_t count = 0;
1593 node_ptr n = detail::uncast(subtree);
1594 node_ptr m = NodeTraits::get_left(n);
1597 m = NodeTraits::get_left(n);
1602 node_ptr n_right(NodeTraits::get_right(n));
1605 m = NodeTraits::get_left(n);
1608 m = NodeTraits::get_left(n);
1617 n = NodeTraits::get_parent(n);
1618 }while(NodeTraits::get_left(n) != m);
1625 //! <b>Requires</b>: p is a node of a tree.
1627 //! <b>Effects</b>: Returns true if p is a left child.
1629 //! <b>Complexity</b>: Constant.
1631 //! <b>Throws</b>: Nothing.
1632 BOOST_INTRUSIVE_FORCEINLINE static bool is_left_child(const node_ptr & p)
1633 { return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; }
1635 //! <b>Requires</b>: p is a node of a tree.
1637 //! <b>Effects</b>: Returns true if p is a right child.
1639 //! <b>Complexity</b>: Constant.
1641 //! <b>Throws</b>: Nothing.
1642 BOOST_INTRUSIVE_FORCEINLINE static bool is_right_child(const node_ptr & p)
1643 { return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; }
1645 static void insert_before_check
1646 (const node_ptr &header, const node_ptr & pos
1647 , insert_commit_data &commit_data
1648 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1649 , std::size_t *pdepth = 0
1654 if(pos != NodeTraits::get_left(header))
1655 prev = base_type::prev_node(pos);
1656 bool link_left = unique(header) || !NodeTraits::get_left(pos);
1657 commit_data.link_left = link_left;
1658 commit_data.node = link_left ? pos : prev;
1660 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1;
1664 static void push_back_check
1665 (const node_ptr & header, insert_commit_data &commit_data
1666 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1667 , std::size_t *pdepth = 0
1671 node_ptr prev(NodeTraits::get_right(header));
1673 *pdepth = prev == header ? 0 : depth(prev) + 1;
1675 commit_data.link_left = false;
1676 commit_data.node = prev;
1679 static void push_front_check
1680 (const node_ptr & header, insert_commit_data &commit_data
1681 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1682 , std::size_t *pdepth = 0
1686 node_ptr pos(NodeTraits::get_left(header));
1688 *pdepth = pos == header ? 0 : depth(pos) + 1;
1690 commit_data.link_left = true;
1691 commit_data.node = pos;
1694 template<class NodePtrCompare>
1695 static void insert_equal_check
1696 (const node_ptr &header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp
1697 , insert_commit_data &commit_data
1699 , std::size_t *pdepth = 0
1703 if(hint == header || !comp(hint, new_node)){
1704 node_ptr prev(hint);
1705 if(hint == NodeTraits::get_left(header) ||
1706 !comp(new_node, (prev = base_type::prev_node(hint)))){
1707 bool link_left = unique(header) || !NodeTraits::get_left(hint);
1708 commit_data.link_left = link_left;
1709 commit_data.node = link_left ? hint : prev;
1711 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1;
1715 insert_equal_upper_bound_check(header, new_node, comp, commit_data, pdepth);
1719 insert_equal_lower_bound_check(header, new_node, comp, commit_data, pdepth);
1723 template<class NodePtrCompare>
1724 static void insert_equal_upper_bound_check
1725 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
1727 std::size_t depth = 0;
1729 node_ptr x(NodeTraits::get_parent(y));
1734 x = comp(new_node, x) ?
1735 NodeTraits::get_left(x) : NodeTraits::get_right(x);
1737 if(pdepth) *pdepth = depth;
1738 commit_data.link_left = (y == h) || comp(new_node, y);
1739 commit_data.node = y;
1742 template<class NodePtrCompare>
1743 static void insert_equal_lower_bound_check
1744 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
1746 std::size_t depth = 0;
1748 node_ptr x(NodeTraits::get_parent(y));
1753 x = !comp(x, new_node) ?
1754 NodeTraits::get_left(x) : NodeTraits::get_right(x);
1756 if(pdepth) *pdepth = depth;
1757 commit_data.link_left = (y == h) || !comp(y, new_node);
1758 commit_data.node = y;
1761 static void insert_commit
1762 (const node_ptr & header, const node_ptr & new_node, const insert_commit_data &commit_data)
1764 //Check if commit_data has not been initialized by a insert_unique_check call.
1765 BOOST_INTRUSIVE_INVARIANT_ASSERT(commit_data.node != node_ptr());
1766 node_ptr parent_node(commit_data.node);
1767 if(parent_node == header){
1768 NodeTraits::set_parent(header, new_node);
1769 NodeTraits::set_right(header, new_node);
1770 NodeTraits::set_left(header, new_node);
1772 else if(commit_data.link_left){
1773 NodeTraits::set_left(parent_node, new_node);
1774 if(parent_node == NodeTraits::get_left(header))
1775 NodeTraits::set_left(header, new_node);
1778 NodeTraits::set_right(parent_node, new_node);
1779 if(parent_node == NodeTraits::get_right(header))
1780 NodeTraits::set_right(header, new_node);
1782 NodeTraits::set_parent(new_node, parent_node);
1783 NodeTraits::set_right(new_node, node_ptr());
1784 NodeTraits::set_left(new_node, node_ptr());
1787 //Fix header and own's parent data when replacing x with own, providing own's old data with parent
1788 static void set_child(const node_ptr & header, const node_ptr & new_child, const node_ptr & new_parent, const bool link_left)
1790 if(new_parent == header)
1791 NodeTraits::set_parent(header, new_child);
1793 NodeTraits::set_left(new_parent, new_child);
1795 NodeTraits::set_right(new_parent, new_child);
1798 // rotate p to left (no header and p's parent fixup)
1799 static void rotate_left_no_parent_fix(const node_ptr & p, const node_ptr &p_right)
1801 node_ptr p_right_left(NodeTraits::get_left(p_right));
1802 NodeTraits::set_right(p, p_right_left);
1804 NodeTraits::set_parent(p_right_left, p);
1806 NodeTraits::set_left(p_right, p);
1807 NodeTraits::set_parent(p, p_right);
1810 // rotate p to left (with header and p's parent fixup)
1811 static void rotate_left(const node_ptr & p, const node_ptr & p_right, const node_ptr & p_parent, const node_ptr & header)
1813 const bool p_was_left(NodeTraits::get_left(p_parent) == p);
1814 rotate_left_no_parent_fix(p, p_right);
1815 NodeTraits::set_parent(p_right, p_parent);
1816 set_child(header, p_right, p_parent, p_was_left);
1819 // rotate p to right (no header and p's parent fixup)
1820 static void rotate_right_no_parent_fix(const node_ptr & p, const node_ptr &p_left)
1822 node_ptr p_left_right(NodeTraits::get_right(p_left));
1823 NodeTraits::set_left(p, p_left_right);
1825 NodeTraits::set_parent(p_left_right, p);
1827 NodeTraits::set_right(p_left, p);
1828 NodeTraits::set_parent(p, p_left);
1831 // rotate p to right (with header and p's parent fixup)
1832 static void rotate_right(const node_ptr & p, const node_ptr & p_left, const node_ptr & p_parent, const node_ptr & header)
1834 const bool p_was_left(NodeTraits::get_left(p_parent) == p);
1835 rotate_right_no_parent_fix(p, p_left);
1836 NodeTraits::set_parent(p_left, p_parent);
1837 set_child(header, p_left, p_parent, p_was_left);
1842 static void subtree_to_vine(node_ptr vine_tail, std::size_t &size)
1844 //Inspired by LibAVL:
1845 //It uses a clever optimization for trees with parent pointers.
1846 //No parent pointer is updated when transforming a tree to a vine as
1847 //most of them will be overriten during compression rotations.
1848 //A final pass must be made after the rebalancing to updated those
1849 //pointers not updated by tree_to_vine + compression calls
1850 std::size_t len = 0;
1851 node_ptr remainder = NodeTraits::get_right(vine_tail);
1853 node_ptr tempptr = NodeTraits::get_left(remainder);
1854 if(!tempptr){ //move vine-tail down one
1855 vine_tail = remainder;
1856 remainder = NodeTraits::get_right(remainder);
1860 NodeTraits::set_left(remainder, NodeTraits::get_right(tempptr));
1861 NodeTraits::set_right(tempptr, remainder);
1862 remainder = tempptr;
1863 NodeTraits::set_right(vine_tail, tempptr);
1869 static void compress_subtree(node_ptr scanner, std::size_t count)
1871 while(count--){ //compress "count" spine nodes in the tree with pseudo-root scanner
1872 node_ptr child = NodeTraits::get_right(scanner);
1873 node_ptr child_right = NodeTraits::get_right(child);
1874 NodeTraits::set_right(scanner, child_right);
1875 //Avoid setting the parent of child_right
1876 scanner = child_right;
1877 node_ptr scanner_left = NodeTraits::get_left(scanner);
1878 NodeTraits::set_right(child, scanner_left);
1880 NodeTraits::set_parent(scanner_left, child);
1881 NodeTraits::set_left(scanner, child);
1882 NodeTraits::set_parent(child, scanner);
1886 static void vine_to_subtree(const node_ptr & super_root, std::size_t count)
1888 const std::size_t one_szt = 1u;
1889 std::size_t leaf_nodes = count + one_szt - std::size_t(one_szt << detail::floor_log2(count + one_szt));
1890 compress_subtree(super_root, leaf_nodes); //create deepest leaves
1891 std::size_t vine_nodes = count - leaf_nodes;
1892 while(vine_nodes > 1){
1894 compress_subtree(super_root, vine_nodes);
1897 //Update parents of nodes still in the in the original vine line
1898 //as those have not been updated by subtree_to_vine or compress_subtree
1899 for ( node_ptr q = super_root, p = NodeTraits::get_right(super_root)
1901 ; q = p, p = NodeTraits::get_right(p)){
1902 NodeTraits::set_parent(p, q);
1906 //! <b>Requires</b>: "n" must be a node inserted in a tree.
1908 //! <b>Effects</b>: Returns a pointer to the header node of the tree.
1910 //! <b>Complexity</b>: Logarithmic.
1912 //! <b>Throws</b>: Nothing.
1913 static node_ptr get_root(const node_ptr & node)
1915 BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node)));
1916 node_ptr x = NodeTraits::get_parent(node);
1918 while(!base_type::is_header(x)){
1919 x = NodeTraits::get_parent(x);
1928 template <class Cloner, class Disposer>
1929 static node_ptr clone_subtree
1930 (const const_node_ptr &source_parent, const node_ptr &target_parent
1931 , Cloner cloner, Disposer disposer
1932 , node_ptr &leftmost_out, node_ptr &rightmost_out
1935 node_ptr target_sub_root = target_parent;
1936 node_ptr source_root = NodeTraits::get_parent(source_parent);
1938 leftmost_out = rightmost_out = source_root;
1941 //We'll calculate leftmost and rightmost nodes while iterating
1942 node_ptr current = source_root;
1943 node_ptr insertion_point = target_sub_root = cloner(current);
1945 //We'll calculate leftmost and rightmost nodes while iterating
1946 node_ptr leftmost = target_sub_root;
1947 node_ptr rightmost = target_sub_root;
1949 //First set the subroot
1950 NodeTraits::set_left(target_sub_root, node_ptr());
1951 NodeTraits::set_right(target_sub_root, node_ptr());
1952 NodeTraits::set_parent(target_sub_root, target_parent);
1954 dispose_subtree_disposer<Disposer> rollback(disposer, target_sub_root);
1956 //First clone left nodes
1957 if( NodeTraits::get_left(current) &&
1958 !NodeTraits::get_left(insertion_point)) {
1959 current = NodeTraits::get_left(current);
1960 node_ptr temp = insertion_point;
1961 //Clone and mark as leaf
1962 insertion_point = cloner(current);
1963 NodeTraits::set_left (insertion_point, node_ptr());
1964 NodeTraits::set_right (insertion_point, node_ptr());
1966 NodeTraits::set_parent(insertion_point, temp);
1967 NodeTraits::set_left (temp, insertion_point);
1969 if(rightmost == target_sub_root)
1970 leftmost = insertion_point;
1972 //Then clone right nodes
1973 else if( NodeTraits::get_right(current) &&
1974 !NodeTraits::get_right(insertion_point)){
1975 current = NodeTraits::get_right(current);
1976 node_ptr temp = insertion_point;
1977 //Clone and mark as leaf
1978 insertion_point = cloner(current);
1979 NodeTraits::set_left (insertion_point, node_ptr());
1980 NodeTraits::set_right (insertion_point, node_ptr());
1982 NodeTraits::set_parent(insertion_point, temp);
1983 NodeTraits::set_right (temp, insertion_point);
1985 rightmost = insertion_point;
1988 else if(current == source_root){
1992 //Branch completed, go up searching more nodes to clone
1993 current = NodeTraits::get_parent(current);
1994 insertion_point = NodeTraits::get_parent(insertion_point);
1998 leftmost_out = leftmost;
1999 rightmost_out = rightmost;
2001 return target_sub_root;
2004 template<class Disposer>
2005 static void dispose_subtree(node_ptr x, Disposer disposer)
2008 node_ptr save(NodeTraits::get_left(x));
2011 NodeTraits::set_left(x, NodeTraits::get_right(save));
2012 NodeTraits::set_right(save, x);
2015 save = NodeTraits::get_right(x);
2023 template<class KeyType, class KeyNodePtrCompare>
2024 static node_ptr lower_bound_loop
2025 (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp)
2029 x = NodeTraits::get_right(x);
2033 x = NodeTraits::get_left(x);
2039 template<class KeyType, class KeyNodePtrCompare>
2040 static node_ptr upper_bound_loop
2041 (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp)
2046 x = NodeTraits::get_left(x);
2049 x = NodeTraits::get_right(x);
2055 template<class Checker>
2056 static void check_subtree(const const_node_ptr& node, Checker checker, typename Checker::return_type& check_return)
2058 const_node_ptr left = NodeTraits::get_left(node);
2059 const_node_ptr right = NodeTraits::get_right(node);
2060 typename Checker::return_type check_return_left;
2061 typename Checker::return_type check_return_right;
2064 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(left) == node);
2065 check_subtree(left, checker, check_return_left);
2069 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(right) == node);
2070 check_subtree(right, checker, check_return_right);
2072 checker(node, check_return_left, check_return_right, check_return);
2078 template<class NodeTraits>
2079 struct get_algo<BsTreeAlgorithms, NodeTraits>
2081 typedef bstree_algorithms<NodeTraits> type;
2084 template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
2085 struct get_node_checker<BsTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
2087 typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
2092 } //namespace intrusive
2095 #include <boost/intrusive/detail/config_end.hpp>
2097 #endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP