1	/////////////////////////////////////////////////////////////////////////////
2	//
3	// (C) Copyright Ion Gaztanaga 2007-2014
4	//
5	// Distributed under the Boost Software License, Version 1.0.
6	// (See accompanying file LICENSE_1_0.txt or copy at
7	// http://www.boost.org/LICENSE_1_0.txt)
8	//
9	// See http://www.boost.org/libs/intrusive for documentation.
10	//
11	/////////////////////////////////////////////////////////////////////////////
12
13	#ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP
14	#define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP
15
16	#include <cstddef>
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>
24
25	#include <boost/intrusive/detail/minimal_pair_header.hpp>
26
27	#if defined(BOOST_HAS_PRAGMA_ONCE)
28	# pragma once
29	#endif
30
31	namespace boost {
32	namespace intrusive {
33
34	/// @cond
35
36	//! This type is the information that will be filled by insert_unique_check
37	template <class NodePtr>
38	struct insert_commit_data_t
39	{
40	bool link_left;
41	NodePtr node;
42	};
43
44	template <class NodePtr>
45	struct data_for_rebalance_t
46	{
47	NodePtr x;
48	NodePtr x_parent;
49	NodePtr y;
50	};
51
52	namespace detail {
53
54	template<class ValueTraits, class NodePtrCompare, class ExtraChecker>
55	struct bstree_node_checker
56	: public ExtraChecker
57	{
58	typedef ExtraChecker base_checker_t;
59	typedef ValueTraits value_traits;
60	typedef typename value_traits::node_traits node_traits;
61	typedef typename node_traits::const_node_ptr const_node_ptr;
62
63	struct return_type
64	: public base_checker_t::return_type
65	{
66	return_type() : min_key_node_ptr(const_node_ptr()), max_key_node_ptr(const_node_ptr()), node_count(0) {}
67
68	const_node_ptr min_key_node_ptr;
69	const_node_ptr max_key_node_ptr;
70	size_t node_count;
71	};
72
73	bstree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
74	: base_checker_t(extra_checker), comp_(comp)
75	{}
76
77	void operator () (const const_node_ptr& p,
78	const return_type& check_return_left, const return_type& check_return_right,
79	return_type& check_return)
80	{
81	if (check_return_left.max_key_node_ptr)
82	BOOST_INTRUSIVE_INVARIANT_ASSERT(!comp_(p, check_return_left.max_key_node_ptr));
83	if (check_return_right.min_key_node_ptr)
84	BOOST_INTRUSIVE_INVARIANT_ASSERT(!comp_(check_return_right.min_key_node_ptr, p));
85	check_return.min_key_node_ptr = node_traits::get_left(p)? check_return_left.min_key_node_ptr : p;
86	check_return.max_key_node_ptr = node_traits::get_right(p)? check_return_right.max_key_node_ptr : p;
87	check_return.node_count = check_return_left.node_count + check_return_right.node_count + 1;
88	base_checker_t::operator()(p, check_return_left, check_return_right, check_return);
89	}
90
91	const NodePtrCompare comp_;
92	};
93
94	} // namespace detail
95
96	/// @endcond
97
98
99
100	//! This is an implementation of a binary search tree.
101	//! A node in the search tree has references to its children and its parent. This
102	//! is to allow traversal of the whole tree from a given node making the
103	//! implementation of iterator a pointer to a node.
104	//! At the top of the tree a node is used specially. This node's parent pointer
105	//! is pointing to the root of the tree. Its left pointer points to the
106	//! leftmost node in the tree and the right pointer to the rightmost one.
107	//! This node is used to represent the end-iterator.
108	//!
109	//! +---------+
110	//! header------------------------------>| |
111	//! | |
112	//! +----------(left)--------| |--------(right)---------+
113	//! | +---------+ |
114	//! | | |
115	//! | | (parent) |
116	//! | | |
117	//! | | |
118	//! | +---------+ |
119	//! root of tree ..|......................> | | |
120	//! | | D | |
121	//! | | | |
122	//! | +-------+---------+-------+ |
123	//! | | | |
124	//! | | | |
125	//! | | | |
126	//! | | | |
127	//! | | | |
128	//! | +---------+ +---------+ |
129	//! | | | | | |
130	//! | | B | | F | |
131	//! | | | | | |
132	//! | +--+---------+--+ +--+---------+--+ |
133	//! | | | | | |
134	//! | | | | | |
135	//! | | | | | |
136	//! | +---+-----+ +-----+---+ +---+-----+ +-----+---+ |
137	//! +-->| | | | | | | |<--+
138	//! | A | | C | | E | | G |
139	//! | | | | | | | |
140	//! +---------+ +---------+ +---------+ +---------+
141	//!
142	//! bstree_algorithms is configured with a NodeTraits class, which encapsulates the
143	//! information about the node to be manipulated. NodeTraits must support the
144	//! following interface:
145	//!
146	//! <b>Typedefs</b>:
147	//!
148	//! <tt>node</tt>: The type of the node that forms the binary search tree
149	//!
150	//! <tt>node_ptr</tt>: A pointer to a node
151	//!
152	//! <tt>const_node_ptr</tt>: A pointer to a const node
153	//!
154	//! <b>Static functions</b>:
155	//!
156	//! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
157	//!
158	//! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
159	//!
160	//! <tt>static node_ptr get_left(const_node_ptr n);</tt>
161	//!
162	//! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
163	//!
164	//! <tt>static node_ptr get_right(const_node_ptr n);</tt>
165	//!
166	//! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
167	template<class NodeTraits>
168	class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
169	{
170	public:
171	typedef typename NodeTraits::node node;
172	typedef NodeTraits node_traits;
173	typedef typename NodeTraits::node_ptr node_ptr;
174	typedef typename NodeTraits::const_node_ptr const_node_ptr;
175	typedef insert_commit_data_t<node_ptr> insert_commit_data;
176	typedef data_for_rebalance_t<node_ptr> data_for_rebalance;
177
178	/// @cond
179	typedef bstree_algorithms<NodeTraits> this_type;
180	typedef bstree_algorithms_base<NodeTraits> base_type;
181	private:
182	template<class Disposer>
183	struct dispose_subtree_disposer
184	{
185	dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree)
186	: disposer_(&disp), subtree_(subtree)
187	{}
188
189	void release()
190	{ disposer_ = 0; }
191
192	~dispose_subtree_disposer()
193	{
194	if(disposer_){
195	dispose_subtree(subtree_, *disposer_);
196	}
197	}
198	Disposer *disposer_;
199	const node_ptr subtree_;
200	};
201
202	/// @endcond
203
204	public:
205	//! <b>Requires</b>: 'header' is the header node of a tree.
206	//!
207	//! <b>Effects</b>: Returns the first node of the tree, the header if the tree is empty.
208	//!
209	//! <b>Complexity</b>: Constant time.
210	//!
211	//! <b>Throws</b>: Nothing.
212	static node_ptr begin_node(const const_node_ptr & header)
213	{ return node_traits::get_left(header); }
214
215	//! <b>Requires</b>: 'header' is the header node of a tree.
216	//!
217	//! <b>Effects</b>: Returns the header of the tree.
218	//!
219	//! <b>Complexity</b>: Constant time.
220	//!
221	//! <b>Throws</b>: Nothing.
222	static node_ptr end_node(const const_node_ptr & header)
223	{ return detail::uncast(header); }
224
225	//! <b>Requires</b>: 'header' is the header node of a tree.
226	//!
227	//! <b>Effects</b>: Returns the root of the tree if any, header otherwise
228	//!
229	//! <b>Complexity</b>: Constant time.
230	//!
231	//! <b>Throws</b>: Nothing.
232	static node_ptr root_node(const const_node_ptr & header)
233	{
234	node_ptr p = node_traits::get_parent(header);
235	return p ? p : detail::uncast(header);
236	}
237
238	//! <b>Requires</b>: 'node' is a node of the tree or a node initialized
239	//! by init(...) or init_node.
240	//!
241	//! <b>Effects</b>: Returns true if the node is initialized by init() or init_node().
242	//!
243	//! <b>Complexity</b>: Constant time.
244	//!
245	//! <b>Throws</b>: Nothing.
246	static bool unique(const const_node_ptr & node)
247	{ return !NodeTraits::get_parent(node); }
248
249	#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
250	//! <b>Requires</b>: 'node' is a node of the tree or a header node.
251	//!
252	//! <b>Effects</b>: Returns the header of the tree.
253	//!
254	//! <b>Complexity</b>: Logarithmic.
255	//!
256	//! <b>Throws</b>: Nothing.
257	static node_ptr get_header(const const_node_ptr & node);
258	#endif
259
260	//! <b>Requires</b>: node1 and node2 can't be header nodes
261	//! of two trees.
262	//!
263	//! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
264	//! in the position node2 before the function. node2 will be inserted in the
265	//! position node1 had before the function.
266	//!
267	//! <b>Complexity</b>: Logarithmic.
268	//!
269	//! <b>Throws</b>: Nothing.
270	//!
271	//! <b>Note</b>: This function will break container ordering invariants if
272	//! node1 and node2 are not equivalent according to the ordering rules.
273	//!
274	//!Experimental function
275	static void swap_nodes(const node_ptr & node1, const node_ptr & node2)
276	{
277	if(node1 == node2)
278	return;
279
280	node_ptr header1(base_type::get_header(node1)), header2(base_type::get_header(node2));
281	swap_nodes(node1, header1, node2, header2);
282	}
283
284	//! <b>Requires</b>: node1 and node2 can't be header nodes
285	//! of two trees with header header1 and header2.
286	//!
287	//! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
288	//! in the position node2 before the function. node2 will be inserted in the
289	//! position node1 had before the function.
290	//!
291	//! <b>Complexity</b>: Constant.
292	//!
293	//! <b>Throws</b>: Nothing.
294	//!
295	//! <b>Note</b>: This function will break container ordering invariants if
296	//! node1 and node2 are not equivalent according to the ordering rules.
297	//!
298	//!Experimental function
299	static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2)
300	{
301	if(node1 == node2)
302	return;
303
304	//node1 and node2 must not be header nodes
305	//BOOST_INTRUSIVE_INVARIANT_ASSERT((header1 != node1 && header2 != node2));
306	if(header1 != header2){
307	//Update header1 if necessary
308	if(node1 == NodeTraits::get_left(header1)){
309	NodeTraits::set_left(header1, node2);
310	}
311
312	if(node1 == NodeTraits::get_right(header1)){
313	NodeTraits::set_right(header1, node2);
314	}
315
316	if(node1 == NodeTraits::get_parent(header1)){
317	NodeTraits::set_parent(header1, node2);
318	}
319
320	//Update header2 if necessary
321	if(node2 == NodeTraits::get_left(header2)){
322	NodeTraits::set_left(header2, node1);
323	}
324
325	if(node2 == NodeTraits::get_right(header2)){
326	NodeTraits::set_right(header2, node1);
327	}
328
329	if(node2 == NodeTraits::get_parent(header2)){
330	NodeTraits::set_parent(header2, node1);
331	}
332	}
333	else{
334	//If both nodes are from the same tree
335	//Update header if necessary
336	if(node1 == NodeTraits::get_left(header1)){
337	NodeTraits::set_left(header1, node2);
338	}
339	else if(node2 == NodeTraits::get_left(header2)){
340	NodeTraits::set_left(header2, node1);
341	}
342
343	if(node1 == NodeTraits::get_right(header1)){
344	NodeTraits::set_right(header1, node2);
345	}
346	else if(node2 == NodeTraits::get_right(header2)){
347	NodeTraits::set_right(header2, node1);
348	}
349
350	if(node1 == NodeTraits::get_parent(header1)){
351	NodeTraits::set_parent(header1, node2);
352	}
353	else if(node2 == NodeTraits::get_parent(header2)){
354	NodeTraits::set_parent(header2, node1);
355	}
356
357	//Adjust data in nodes to be swapped
358	//so that final link swap works as expected
359	if(node1 == NodeTraits::get_parent(node2)){
360	NodeTraits::set_parent(node2, node2);
361
362	if(node2 == NodeTraits::get_right(node1)){
363	NodeTraits::set_right(node1, node1);
364	}
365	else{
366	NodeTraits::set_left(node1, node1);
367	}
368	}
369	else if(node2 == NodeTraits::get_parent(node1)){
370	NodeTraits::set_parent(node1, node1);
371
372	if(node1 == NodeTraits::get_right(node2)){
373	NodeTraits::set_right(node2, node2);
374	}
375	else{
376	NodeTraits::set_left(node2, node2);
377	}
378	}
379	}
380
381	//Now swap all the links
382	node_ptr temp;
383	//swap left link
384	temp = NodeTraits::get_left(node1);
385	NodeTraits::set_left(node1, NodeTraits::get_left(node2));
386	NodeTraits::set_left(node2, temp);
387	//swap right link
388	temp = NodeTraits::get_right(node1);
389	NodeTraits::set_right(node1, NodeTraits::get_right(node2));
390	NodeTraits::set_right(node2, temp);
391	//swap parent link
392	temp = NodeTraits::get_parent(node1);
393	NodeTraits::set_parent(node1, NodeTraits::get_parent(node2));
394	NodeTraits::set_parent(node2, temp);
395
396	//Now adjust adjacent nodes for newly inserted node 1
397	if((temp = NodeTraits::get_left(node1))){
398	NodeTraits::set_parent(temp, node1);
399	}
400	if((temp = NodeTraits::get_right(node1))){
401	NodeTraits::set_parent(temp, node1);
402	}
403	if((temp = NodeTraits::get_parent(node1)) &&
404	//The header has been already updated so avoid it
405	temp != header2){
406	if(NodeTraits::get_left(temp) == node2){
407	NodeTraits::set_left(temp, node1);
408	}
409	if(NodeTraits::get_right(temp) == node2){
410	NodeTraits::set_right(temp, node1);
411	}
412	}
413	//Now adjust adjacent nodes for newly inserted node 2
414	if((temp = NodeTraits::get_left(node2))){
415	NodeTraits::set_parent(temp, node2);
416	}
417	if((temp = NodeTraits::get_right(node2))){
418	NodeTraits::set_parent(temp, node2);
419	}
420	if((temp = NodeTraits::get_parent(node2)) &&
421	//The header has been already updated so avoid it
422	temp != header1){
423	if(NodeTraits::get_left(temp) == node1){
424	NodeTraits::set_left(temp, node2);
425	}
426	if(NodeTraits::get_right(temp) == node1){
427	NodeTraits::set_right(temp, node2);
428	}
429	}
430	}
431
432	//! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
433	//! and new_node must not be inserted in a tree.
434	//!
435	//! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
436	//! tree with new_node. The tree does not need to be rebalanced
437	//!
438	//! <b>Complexity</b>: Logarithmic.
439	//!
440	//! <b>Throws</b>: Nothing.
441	//!
442	//! <b>Note</b>: This function will break container ordering invariants if
443	//! new_node is not equivalent to node_to_be_replaced according to the
444	//! ordering rules. This function is faster than erasing and inserting
445	//! the node, since no rebalancing and comparison is needed. Experimental function
446	static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
447	{
448	if(node_to_be_replaced == new_node)
449	return;
450	replace_node(node_to_be_replaced, base_type::get_header(node_to_be_replaced), new_node);
451	}
452
453	//! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
454	//! with header "header" and new_node must not be inserted in a tree.
455	//!
456	//! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
457	//! tree with new_node. The tree does not need to be rebalanced
458	//!
459	//! <b>Complexity</b>: Constant.
460	//!
461	//! <b>Throws</b>: Nothing.
462	//!
463	//! <b>Note</b>: This function will break container ordering invariants if
464	//! new_node is not equivalent to node_to_be_replaced according to the
465	//! ordering rules. This function is faster than erasing and inserting
466	//! the node, since no rebalancing or comparison is needed. Experimental function
467	static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
468	{
469	if(node_to_be_replaced == new_node)
470	return;
471
472	//Update header if necessary
473	if(node_to_be_replaced == NodeTraits::get_left(header)){
474	NodeTraits::set_left(header, new_node);
475	}
476
477	if(node_to_be_replaced == NodeTraits::get_right(header)){
478	NodeTraits::set_right(header, new_node);
479	}
480
481	if(node_to_be_replaced == NodeTraits::get_parent(header)){
482	NodeTraits::set_parent(header, new_node);
483	}
484
485	//Now set data from the original node
486	node_ptr temp;
487	NodeTraits::set_left(new_node, NodeTraits::get_left(node_to_be_replaced));
488	NodeTraits::set_right(new_node, NodeTraits::get_right(node_to_be_replaced));
489	NodeTraits::set_parent(new_node, NodeTraits::get_parent(node_to_be_replaced));
490
491	//Now adjust adjacent nodes for newly inserted node
492	if((temp = NodeTraits::get_left(new_node))){
493	NodeTraits::set_parent(temp, new_node);
494	}
495	if((temp = NodeTraits::get_right(new_node))){
496	NodeTraits::set_parent(temp, new_node);
497	}
498	if((temp = NodeTraits::get_parent(new_node)) &&
499	//The header has been already updated so avoid it
500	temp != header){
501	if(NodeTraits::get_left(temp) == node_to_be_replaced){
502	NodeTraits::set_left(temp, new_node);
503	}
504	if(NodeTraits::get_right(temp) == node_to_be_replaced){
505	NodeTraits::set_right(temp, new_node);
506	}
507	}
508	}
509
510	#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
511	//! <b>Requires</b>: 'node' is a node from the tree except the header.
512	//!
513	//! <b>Effects</b>: Returns the next node of the tree.
514	//!
515	//! <b>Complexity</b>: Average constant time.
516	//!
517	//! <b>Throws</b>: Nothing.
518	static node_ptr next_node(const node_ptr & node);
519
520	//! <b>Requires</b>: 'node' is a node from the tree except the leftmost node.
521	//!
522	//! <b>Effects</b>: Returns the previous node of the tree.
523	//!
524	//! <b>Complexity</b>: Average constant time.
525	//!
526	//! <b>Throws</b>: Nothing.
527	static node_ptr prev_node(const node_ptr & node);
528
529	//! <b>Requires</b>: 'node' is a node of a tree but not the header.
530	//!
531	//! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
532	//!
533	//! <b>Complexity</b>: Logarithmic to the size of the subtree.
534	//!
535	//! <b>Throws</b>: Nothing.
536	static node_ptr minimum(node_ptr node);
537
538	//! <b>Requires</b>: 'node' is a node of a tree but not the header.
539	//!
540	//! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
541	//!
542	//! <b>Complexity</b>: Logarithmic to the size of the subtree.
543	//!
544	//! <b>Throws</b>: Nothing.
545	static node_ptr maximum(node_ptr node);
546	#endif
547
548	//! <b>Requires</b>: 'node' must not be part of any tree.
549	//!
550	//! <b>Effects</b>: After the function unique(node) == true.
551	//!
552	//! <b>Complexity</b>: Constant.
553	//!
554	//! <b>Throws</b>: Nothing.
555	//!
556	//! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
557	static void init(const node_ptr & node)
558	{
559	NodeTraits::set_parent(node, node_ptr());
560	NodeTraits::set_left(node, node_ptr());
561	NodeTraits::set_right(node, node_ptr());
562	};
563
564	//! <b>Effects</b>: Returns true if node is in the same state as if called init(node)
565	//!
566	//! <b>Complexity</b>: Constant.
567	//!
568	//! <b>Throws</b>: Nothing.
569	static bool inited(const const_node_ptr & node)
570	{
571	return !NodeTraits::get_parent(node) &&
572	!NodeTraits::get_left(node) &&
573	!NodeTraits::get_right(node) ;
574	};
575
576	//! <b>Requires</b>: node must not be part of any tree.
577	//!
578	//! <b>Effects</b>: Initializes the header to represent an empty tree.
579	//! unique(header) == true.
580	//!
581	//! <b>Complexity</b>: Constant.
582	//!
583	//! <b>Throws</b>: Nothing.
584	//!
585	//! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
586	static void init_header(const node_ptr & header)
587	{
588	NodeTraits::set_parent(header, node_ptr());
589	NodeTraits::set_left(header, header);
590	NodeTraits::set_right(header, header);
591	}
592
593	//! <b>Requires</b>: "disposer" must be an object function
594	//! taking a node_ptr parameter and shouldn't throw.
595	//!
596	//! <b>Effects</b>: Empties the target tree calling
597	//! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
598	//! except the header.
599	//!
600	//! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
601	//! number of elements of tree target tree when calling this function.
602	//!
603	//! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
604	template<class Disposer>
605	static void clear_and_dispose(const node_ptr & header, Disposer disposer)
606	{
607	node_ptr source_root = NodeTraits::get_parent(header);
608	if(!source_root)
609	return;
610	dispose_subtree(source_root, disposer);
611	init_header(header);
612	}
613
614	//! <b>Requires</b>: header is the header of a tree.
615	//!
616	//! <b>Effects</b>: Unlinks the leftmost node from the tree, and
617	//! updates the header link to the new leftmost node.
618	//!
619	//! <b>Complexity</b>: Average complexity is constant time.
620	//!
621	//! <b>Throws</b>: Nothing.
622	//!
623	//! <b>Notes</b>: This function breaks the tree and the tree can
624	//! only be used for more unlink_leftmost_without_rebalance calls.
625	//! This function is normally used to achieve a step by step
626	//! controlled destruction of the tree.
627	static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header)
628	{
629	node_ptr leftmost = NodeTraits::get_left(header);
630	if (leftmost == header)
631	return node_ptr();
632	node_ptr leftmost_parent(NodeTraits::get_parent(leftmost));
633	node_ptr leftmost_right (NodeTraits::get_right(leftmost));
634	bool is_root = leftmost_parent == header;
635
636	if (leftmost_right){
637	NodeTraits::set_parent(leftmost_right, leftmost_parent);
638	NodeTraits::set_left(header, base_type::minimum(leftmost_right));
639
640	if (is_root)
641	NodeTraits::set_parent(header, leftmost_right);
642	else
643	NodeTraits::set_left(NodeTraits::get_parent(header), leftmost_right);
644	}
645	else if (is_root){
646	NodeTraits::set_parent(header, node_ptr());
647	NodeTraits::set_left(header, header);
648	NodeTraits::set_right(header, header);
649	}
650	else{
651	NodeTraits::set_left(leftmost_parent, node_ptr());
652	NodeTraits::set_left(header, leftmost_parent);
653	}
654	return leftmost;
655	}
656
657	//! <b>Requires</b>: node is a node of the tree but it's not the header.
658	//!
659	//! <b>Effects</b>: Returns the number of nodes of the subtree.
660	//!
661	//! <b>Complexity</b>: Linear time.
662	//!
663	//! <b>Throws</b>: Nothing.
664	static std::size_t size(const const_node_ptr & header)
665	{
666	node_ptr beg(begin_node(header));
667	node_ptr end(end_node(header));
668	std::size_t i = 0;
669	for(;beg != end; beg = base_type::next_node(beg)) ++i;
670	return i;
671	}
672
673	//! <b>Requires</b>: header1 and header2 must be the header nodes
674	//! of two trees.
675	//!
676	//! <b>Effects</b>: Swaps two trees. After the function header1 will contain
677	//! links to the second tree and header2 will have links to the first tree.
678	//!
679	//! <b>Complexity</b>: Constant.
680	//!
681	//! <b>Throws</b>: Nothing.
682	static void swap_tree(const node_ptr & header1, const node_ptr & header2)
683	{
684	if(header1 == header2)
685	return;
686
687	node_ptr tmp;
688
689	//Parent swap
690	tmp = NodeTraits::get_parent(header1);
691	NodeTraits::set_parent(header1, NodeTraits::get_parent(header2));
692	NodeTraits::set_parent(header2, tmp);
693	//Left swap
694	tmp = NodeTraits::get_left(header1);
695	NodeTraits::set_left(header1, NodeTraits::get_left(header2));
696	NodeTraits::set_left(header2, tmp);
697	//Right swap
698	tmp = NodeTraits::get_right(header1);
699	NodeTraits::set_right(header1, NodeTraits::get_right(header2));
700	NodeTraits::set_right(header2, tmp);
701
702	//Now test parent
703	node_ptr h1_parent(NodeTraits::get_parent(header1));
704	if(h1_parent){
705	NodeTraits::set_parent(h1_parent, header1);
706	}
707	else{
708	NodeTraits::set_left(header1, header1);
709	NodeTraits::set_right(header1, header1);
710	}
711
712	node_ptr h2_parent(NodeTraits::get_parent(header2));
713	if(h2_parent){
714	NodeTraits::set_parent(h2_parent, header2);
715	}
716	else{
717	NodeTraits::set_left(header2, header2);
718	NodeTraits::set_right(header2, header2);
719	}
720	}
721
722	#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
723	//! <b>Requires</b>: p is a node of a tree.
724	//!
725	//! <b>Effects</b>: Returns true if p is the header of the tree.
726	//!
727	//! <b>Complexity</b>: Constant.
728	//!
729	//! <b>Throws</b>: Nothing.
730	static bool is_header(const const_node_ptr & p);
731	#endif
732
733	//! <b>Requires</b>: "header" must be the header node of a tree.
734	//! KeyNodePtrCompare is a function object that induces a strict weak
735	//! ordering compatible with the strict weak ordering used to create the
736	//! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
737	//!
738	//! <b>Effects</b>: Returns a node_ptr to the first element that is equivalent to
739	//! "key" according to "comp" or "header" if that element does not exist.
740	//!
741	//! <b>Complexity</b>: Logarithmic.
742	//!
743	//! <b>Throws</b>: If "comp" throws.
744	template<class KeyType, class KeyNodePtrCompare>
745	static node_ptr find
746	(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
747	{
748	node_ptr end = detail::uncast(header);
749	node_ptr y = lower_bound(header, key, comp);
750	return (y == end || comp(key, y)) ? end : y;
751	}
752
753	//! <b>Requires</b>: "header" must be the header node of a tree.
754	//! KeyNodePtrCompare is a function object that induces a strict weak
755	//! ordering compatible with the strict weak ordering used to create the
756	//! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
757	//! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
758	//! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be true.
759	//!
760	//! <b>Effects</b>: Returns an a pair with the following criteria:
761	//!
762	//! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
763	//!
764	//! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
765	//!
766	//! <b>Complexity</b>: Logarithmic.
767	//!
768	//! <b>Throws</b>: If "comp" throws.
769	//!
770	//! <b>Note</b>: This function can be more efficient than calling upper_bound
771	//! and lower_bound for lower_key and upper_key.
772	//!
773	//! <b>Note</b>: Experimental function, the interface might change.
774	template< class KeyType, class KeyNodePtrCompare>
775	static std::pair<node_ptr, node_ptr> bounded_range
776	( const const_node_ptr & header
777	, const KeyType &lower_key
778	, const KeyType &upper_key
779	, KeyNodePtrCompare comp
780	, bool left_closed
781	, bool right_closed)
782	{
783	node_ptr y = detail::uncast(header);
784	node_ptr x = NodeTraits::get_parent(header);
785
786	while(x){
787	//If x is less than lower_key the target
788	//range is on the right part
789	if(comp(x, lower_key)){
790	//Check for invalid input range
791	BOOST_INTRUSIVE_INVARIANT_ASSERT(comp(x, upper_key));
792	x = NodeTraits::get_right(x);
793	}
794	//If the upper_key is less than x, the target
795	//range is on the left part
796	else if(comp(upper_key, x)){
797	y = x;
798	x = NodeTraits::get_left(x);
799	}
800	else{
801	//x is inside the bounded range(lower_key <= x <= upper_key),
802	//so we must split lower and upper searches
803	//
804	//Sanity check: if lower_key and upper_key are equal, then both left_closed and right_closed can't be false
805	BOOST_INTRUSIVE_INVARIANT_ASSERT(left_closed || right_closed || comp(lower_key, x) || comp(x, upper_key));
806	return std::pair<node_ptr,node_ptr>(
807	left_closed
808	//If left_closed, then comp(x, lower_key) is already the lower_bound
809	//condition so we save one comparison and go to the next level
810	//following traditional lower_bound algo
811	? lower_bound_loop(NodeTraits::get_left(x), x, lower_key, comp)
812	//If left-open, comp(x, lower_key) is not the upper_bound algo
813	//condition so we must recheck current 'x' node with upper_bound algo
814	: upper_bound_loop(x, y, lower_key, comp)
815	,
816	right_closed
817	//If right_closed, then comp(upper_key, x) is already the upper_bound
818	//condition so we can save one comparison and go to the next level
819	//following lower_bound algo
820	? upper_bound_loop(NodeTraits::get_right(x), y, upper_key, comp)
821	//If right-open, comp(upper_key, x) is not the lower_bound algo
822	//condition so we must recheck current 'x' node with lower_bound algo
823	: lower_bound_loop(x, y, upper_key, comp)
824	);
825	}
826	}
827	return std::pair<node_ptr,node_ptr> (y, y);
828	}
829
830	//! <b>Requires</b>: "header" must be the header node of a tree.
831	//! KeyNodePtrCompare is a function object that induces a strict weak
832	//! ordering compatible with the strict weak ordering used to create the
833	//! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
834	//!
835	//! <b>Effects</b>: Returns the number of elements with a key equivalent to "key"
836	//! according to "comp".
837	//!
838	//! <b>Complexity</b>: Logarithmic.
839	//!
840	//! <b>Throws</b>: If "comp" throws.
841	template<class KeyType, class KeyNodePtrCompare>
842	static std::size_t count
843	(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
844	{
845	std::pair<node_ptr, node_ptr> ret = equal_range(header, key, comp);
846	std::size_t n = 0;
847	while(ret.first != ret.second){
848	++n;
849	ret.first = base_type::next_node(ret.first);
850	}
851	return n;
852	}
853
854	//! <b>Requires</b>: "header" must be the header node of a tree.
855	//! KeyNodePtrCompare is a function object that induces a strict weak
856	//! ordering compatible with the strict weak ordering used to create the
857	//! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
858	//!
859	//! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
860	//! all elements that are equivalent to "key" according to "comp" or an
861	//! empty range that indicates the position where those elements would be
862	//! if there are no equivalent elements.
863	//!
864	//! <b>Complexity</b>: Logarithmic.
865	//!
866	//! <b>Throws</b>: If "comp" throws.
867	template<class KeyType, class KeyNodePtrCompare>
868	static std::pair<node_ptr, node_ptr> equal_range
869	(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
870	{
871	return bounded_range(header, key, key, comp, true, true);
872	}
873
874	//! <b>Requires</b>: "header" must be the header node of a tree.
875	//! KeyNodePtrCompare is a function object that induces a strict weak
876	//! ordering compatible with the strict weak ordering used to create the
877	//! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
878	//!
879	//! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
880	//! the first element that is equivalent to "key" according to "comp" or an
881	//! empty range that indicates the position where that element would be
882	//! if there are no equivalent elements.
883	//!
884	//! <b>Complexity</b>: Logarithmic.
885	//!
886	//! <b>Throws</b>: If "comp" throws.
887	template<class KeyType, class KeyNodePtrCompare>
888	static std::pair<node_ptr, node_ptr> lower_bound_range
889	(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
890	{
891	node_ptr const lb(lower_bound(header, key, comp));
892	std::pair<node_ptr, node_ptr> ret_ii(lb, lb);
893	if(lb != header && !comp(key, lb)){
894	ret_ii.second = base_type::next_node(ret_ii.second);
895	}
896	return ret_ii;
897	}
898
899	//! <b>Requires</b>: "header" must be the header node of a tree.
900	//! KeyNodePtrCompare is a function object that induces a strict weak
901	//! ordering compatible with the strict weak ordering used to create the
902	//! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
903	//!
904	//! <b>Effects</b>: Returns a node_ptr to the first element that is
905	//! not less than "key" according to "comp" or "header" if that element does
906	//! not exist.
907	//!
908	//! <b>Complexity</b>: Logarithmic.
909	//!
910	//! <b>Throws</b>: If "comp" throws.
911	template<class KeyType, class KeyNodePtrCompare>
912	static node_ptr lower_bound
913	(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
914	{
915	return lower_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp);
916	}
917
918	//! <b>Requires</b>: "header" must be the header node of a tree.
919	//! KeyNodePtrCompare is a function object that induces a strict weak
920	//! ordering compatible with the strict weak ordering used to create the
921	//! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
922	//!
923	//! <b>Effects</b>: Returns a node_ptr to the first element that is greater
924	//! than "key" according to "comp" or "header" if that element does not exist.
925	//!
926	//! <b>Complexity</b>: Logarithmic.
927	//!
928	//! <b>Throws</b>: If "comp" throws.
929	template<class KeyType, class KeyNodePtrCompare>
930	static node_ptr upper_bound
931	(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
932	{
933	return upper_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp);
934	}
935
936	//! <b>Requires</b>: "header" must be the header node of a tree.
937	//! "commit_data" must have been obtained from a previous call to
938	//! "insert_unique_check". No objects should have been inserted or erased
939	//! from the set between the "insert_unique_check" that filled "commit_data"
940	//! and the call to "insert_commit".
941	//!
942	//!
943	//! <b>Effects</b>: Inserts new_node in the set using the information obtained
944	//! from the "commit_data" that a previous "insert_check" filled.
945	//!
946	//! <b>Complexity</b>: Constant time.
947	//!
948	//! <b>Throws</b>: Nothing.
949	//!
950	//! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been
951	//! previously executed to fill "commit_data". No value should be inserted or
952	//! erased between the "insert_check" and "insert_commit" calls.
953	static void insert_unique_commit
954	(const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
955	{ return insert_commit(header, new_node: new_value, commit_data); }
956
957	//! <b>Requires</b>: "header" must be the header node of a tree.
958	//! KeyNodePtrCompare is a function object that induces a strict weak
959	//! ordering compatible with the strict weak ordering used to create the
960	//! the tree. NodePtrCompare compares KeyType with a node_ptr.
961	//!
962	//! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
963	//! tree according to "comp" and obtains the needed information to realize
964	//! a constant-time node insertion if there is no equivalent node.
965	//!
966	//! <b>Returns</b>: If there is an equivalent value
967	//! returns a pair containing a node_ptr to the already present node
968	//! and false. If there is not equivalent key can be inserted returns true
969	//! in the returned pair's boolean and fills "commit_data" that is meant to
970	//! be used with the "insert_commit" function to achieve a constant-time
971	//! insertion function.
972	//!
973	//! <b>Complexity</b>: Average complexity is at most logarithmic.
974	//!
975	//! <b>Throws</b>: If "comp" throws.
976	//!
977	//! <b>Notes</b>: This function is used to improve performance when constructing
978	//! a node is expensive and the user does not want to have two equivalent nodes
979	//! in the tree: if there is an equivalent value
980	//! the constructed object must be discarded. Many times, the part of the
981	//! node that is used to impose the order is much cheaper to construct
982	//! than the node and this function offers the possibility to use that part
983	//! to check if the insertion will be successful.
984	//!
985	//! If the check is successful, the user can construct the node and use
986	//! "insert_commit" to insert the node in constant-time. This gives a total
987	//! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
988	//!
989	//! "commit_data" remains valid for a subsequent "insert_unique_commit" only
990	//! if no more objects are inserted or erased from the set.
991	template<class KeyType, class KeyNodePtrCompare>
992	static std::pair<node_ptr, bool> insert_unique_check
993	(const const_node_ptr & header, const KeyType &key
994	,KeyNodePtrCompare comp, insert_commit_data &commit_data
995	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
996	, std::size_t *pdepth = 0
997	#endif
998	)
999	{
1000	std::size_t depth = 0;
1001	node_ptr h(detail::uncast(header));
1002	node_ptr y(h);
1003	node_ptr x(NodeTraits::get_parent(y));
1004	node_ptr prev = node_ptr();
1005
1006	//Find the upper bound, cache the previous value and if we should
1007	//store it in the left or right node
1008	bool left_child = true;
1009	while(x){
1010	++depth;
1011	y = x;
1012	x = (left_child = comp(key, x)) ?
1013	NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x));
1014	}
1015
1016	if(pdepth) *pdepth = depth;
1017
1018	//Since we've found the upper bound there is no other value with the same key if:
1019	// - There is no previous node
1020	// - The previous node is less than the key
1021	const bool not_present = !prev || comp(prev, key);
1022	if(not_present){
1023	commit_data.link_left = left_child;
1024	commit_data.node = y;
1025	}
1026	return std::pair<node_ptr, bool>(prev, not_present);
1027	}
1028
1029	//! <b>Requires</b>: "header" must be the header node of a tree.
1030	//! KeyNodePtrCompare is a function object that induces a strict weak
1031	//! ordering compatible with the strict weak ordering used to create the
1032	//! the tree. NodePtrCompare compares KeyType with a node_ptr.
1033	//! "hint" is node from the "header"'s tree.
1034	//!
1035	//! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
1036	//! tree according to "comp" using "hint" as a hint to where it should be
1037	//! inserted and obtains the needed information to realize
1038	//! a constant-time node insertion if there is no equivalent node.
1039	//! If "hint" is the upper_bound the function has constant time
1040	//! complexity (two comparisons in the worst case).
1041	//!
1042	//! <b>Returns</b>: If there is an equivalent value
1043	//! returns a pair containing a node_ptr to the already present node
1044	//! and false. If there is not equivalent key can be inserted returns true
1045	//! in the returned pair's boolean and fills "commit_data" that is meant to
1046	//! be used with the "insert_commit" function to achieve a constant-time
1047	//! insertion function.
1048	//!
1049	//! <b>Complexity</b>: Average complexity is at most logarithmic, but it is
1050	//! amortized constant time if new_node should be inserted immediately before "hint".
1051	//!
1052	//! <b>Throws</b>: If "comp" throws.
1053	//!
1054	//! <b>Notes</b>: This function is used to improve performance when constructing
1055	//! a node is expensive and the user does not want to have two equivalent nodes
1056	//! in the tree: if there is an equivalent value
1057	//! the constructed object must be discarded. Many times, the part of the
1058	//! node that is used to impose the order is much cheaper to construct
1059	//! than the node and this function offers the possibility to use that part
1060	//! to check if the insertion will be successful.
1061	//!
1062	//! If the check is successful, the user can construct the node and use
1063	//! "insert_commit" to insert the node in constant-time. This gives a total
1064	//! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
1065	//!
1066	//! "commit_data" remains valid for a subsequent "insert_unique_commit" only
1067	//! if no more objects are inserted or erased from the set.
1068	template<class KeyType, class KeyNodePtrCompare>
1069	static std::pair<node_ptr, bool> insert_unique_check
1070	(const const_node_ptr & header, const node_ptr &hint, const KeyType &key
1071	,KeyNodePtrCompare comp, insert_commit_data &commit_data
1072	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1073	, std::size_t *pdepth = 0
1074	#endif
1075	)
1076	{
1077	//hint must be bigger than the key
1078	if(hint == header || comp(key, hint)){
1079	node_ptr prev(hint);
1080	//Previous value should be less than the key
1081	if(hint == begin_node(header) || comp((prev = base_type::prev_node(hint)), key)){
1082	commit_data.link_left = unique(node: header) || !NodeTraits::get_left(hint);
1083	commit_data.node = commit_data.link_left ? hint : prev;
1084	if(pdepth){
1085	*pdepth = commit_data.node == header ? 0 : depth(node: commit_data.node) + 1;
1086	}
1087	return std::pair<node_ptr, bool>(node_ptr(), true);
1088	}
1089	}
1090	//Hint was wrong, use hintless insertion
1091	return insert_unique_check(header, key, comp, commit_data, pdepth);
1092	}
1093
1094	//! <b>Requires</b>: "header" must be the header node of a tree.
1095	//! NodePtrCompare is a function object that induces a strict weak
1096	//! ordering compatible with the strict weak ordering used to create the
1097	//! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from
1098	//! the "header"'s tree.
1099	//!
1100	//! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to
1101	//! where it will be inserted. If "hint" is the upper_bound
1102	//! the insertion takes constant time (two comparisons in the worst case).
1103	//!
1104	//! <b>Complexity</b>: Logarithmic in general, but it is amortized
1105	//! constant time if new_node is inserted immediately before "hint".
1106	//!
1107	//! <b>Throws</b>: If "comp" throws.
1108	template<class NodePtrCompare>
1109	static node_ptr insert_equal
1110	(const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp
1111	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1112	, std::size_t *pdepth = 0
1113	#endif
1114	)
1115	{
1116	insert_commit_data commit_data;
1117	insert_equal_check(h, hint, new_node, comp, commit_data, pdepth);
1118	insert_commit(header: h, new_node, commit_data);
1119	return new_node;
1120	}
1121
1122	//! <b>Requires</b>: "h" must be the header node of a tree.
1123	//! NodePtrCompare is a function object that induces a strict weak
1124	//! ordering compatible with the strict weak ordering used to create the
1125	//! the tree. NodePtrCompare compares two node_ptrs.
1126	//!
1127	//! <b>Effects</b>: Inserts new_node into the tree before the upper bound
1128	//! according to "comp".
1129	//!
1130	//! <b>Complexity</b>: Average complexity for insert element is at
1131	//! most logarithmic.
1132	//!
1133	//! <b>Throws</b>: If "comp" throws.
1134	template<class NodePtrCompare>
1135	static node_ptr insert_equal_upper_bound
1136	(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
1137	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1138	, std::size_t *pdepth = 0
1139	#endif
1140	)
1141	{
1142	insert_commit_data commit_data;
1143	insert_equal_upper_bound_check(h, new_node, comp, commit_data, pdepth);
1144	insert_commit(header: h, new_node, commit_data);
1145	return new_node;
1146	}
1147
1148	//! <b>Requires</b>: "h" must be the header node of a tree.
1149	//! NodePtrCompare is a function object that induces a strict weak
1150	//! ordering compatible with the strict weak ordering used to create the
1151	//! the tree. NodePtrCompare compares two node_ptrs.
1152	//!
1153	//! <b>Effects</b>: Inserts new_node into the tree before the lower bound
1154	//! according to "comp".
1155	//!
1156	//! <b>Complexity</b>: Average complexity for insert element is at
1157	//! most logarithmic.
1158	//!
1159	//! <b>Throws</b>: If "comp" throws.
1160	template<class NodePtrCompare>
1161	static node_ptr insert_equal_lower_bound
1162	(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
1163	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1164	, std::size_t *pdepth = 0
1165	#endif
1166	)
1167	{
1168	insert_commit_data commit_data;
1169	insert_equal_lower_bound_check(h, new_node, comp, commit_data, pdepth);
1170	insert_commit(header: h, new_node, commit_data);
1171	return new_node;
1172	}
1173
1174	//! <b>Requires</b>: "header" must be the header node of a tree.
1175	//! "pos" must be a valid iterator or header (end) node.
1176	//! "pos" must be an iterator pointing to the successor to "new_node"
1177	//! once inserted according to the order of already inserted nodes. This function does not
1178	//! check "pos" and this precondition must be guaranteed by the caller.
1179	//!
1180	//! <b>Effects</b>: Inserts new_node into the tree before "pos".
1181	//!
1182	//! <b>Complexity</b>: Constant-time.
1183	//!
1184	//! <b>Throws</b>: Nothing.
1185	//!
1186	//! <b>Note</b>: If "pos" is not the successor of the newly inserted "new_node"
1187	//! tree invariants might be broken.
1188	static node_ptr insert_before
1189	(const node_ptr & header, const node_ptr & pos, const node_ptr & new_node
1190	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1191	, std::size_t *pdepth = 0
1192	#endif
1193	)
1194	{
1195	insert_commit_data commit_data;
1196	insert_before_check(header, pos, commit_data, pdepth);
1197	insert_commit(header, new_node, commit_data);
1198	return new_node;
1199	}
1200
1201	//! <b>Requires</b>: "header" must be the header node of a tree.
1202	//! "new_node" must be, according to the used ordering no less than the
1203	//! greatest inserted key.
1204	//!
1205	//! <b>Effects</b>: Inserts new_node into the tree before "pos".
1206	//!
1207	//! <b>Complexity</b>: Constant-time.
1208	//!
1209	//! <b>Throws</b>: Nothing.
1210	//!
1211	//! <b>Note</b>: If "new_node" is less than the greatest inserted key
1212	//! tree invariants are broken. This function is slightly faster than
1213	//! using "insert_before".
1214	static void push_back
1215	(const node_ptr & header, const node_ptr & new_node
1216	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1217	, std::size_t *pdepth = 0
1218	#endif
1219	)
1220	{
1221	insert_commit_data commit_data;
1222	push_back_check(header, commit_data, pdepth);
1223	insert_commit(header, new_node, commit_data);
1224	}
1225
1226	//! <b>Requires</b>: "header" must be the header node of a tree.
1227	//! "new_node" must be, according to the used ordering, no greater than the
1228	//! lowest inserted key.
1229	//!
1230	//! <b>Effects</b>: Inserts new_node into the tree before "pos".
1231	//!
1232	//! <b>Complexity</b>: Constant-time.
1233	//!
1234	//! <b>Throws</b>: Nothing.
1235	//!
1236	//! <b>Note</b>: If "new_node" is greater than the lowest inserted key
1237	//! tree invariants are broken. This function is slightly faster than
1238	//! using "insert_before".
1239	static void push_front
1240	(const node_ptr & header, const node_ptr & new_node
1241	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1242	, std::size_t *pdepth = 0
1243	#endif
1244	)
1245	{
1246	insert_commit_data commit_data;
1247	push_front_check(header, commit_data, pdepth);
1248	insert_commit(header, new_node, commit_data);
1249	}
1250
1251	//! <b>Requires</b>: 'node' can't be a header node.
1252	//!
1253	//! <b>Effects</b>: Calculates the depth of a node: the depth of a
1254	//! node is the length (number of edges) of the path from the root
1255	//! to that node. (The root node is at depth 0.)
1256	//!
1257	//! <b>Complexity</b>: Logarithmic to the number of nodes in the tree.
1258	//!
1259	//! <b>Throws</b>: Nothing.
1260	static std::size_t depth(const_node_ptr node)
1261	{
1262	std::size_t depth = 0;
1263	node_ptr p_parent;
1264	while(node != NodeTraits::get_parent(p_parent = NodeTraits::get_parent(node))){
1265	++depth;
1266	node = p_parent;
1267	}
1268	return depth;
1269	}
1270
1271	//! <b>Requires</b>: "cloner" must be a function
1272	//! object taking a node_ptr and returning a new cloned node of it. "disposer" must
1273	//! take a node_ptr and shouldn't throw.
1274	//!
1275	//! <b>Effects</b>: First empties target tree calling
1276	//! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
1277	//! except the header.
1278	//!
1279	//! Then, duplicates the entire tree pointed by "source_header" cloning each
1280	//! source node with <tt>node_ptr Cloner::operator()(const node_ptr &)</tt> to obtain
1281	//! the nodes of the target tree. If "cloner" throws, the cloned target nodes
1282	//! are disposed using <tt>void disposer(const node_ptr &)</tt>.
1283	//!
1284	//! <b>Complexity</b>: Linear to the number of element of the source tree plus the
1285	//! number of elements of tree target tree when calling this function.
1286	//!
1287	//! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
1288	template <class Cloner, class Disposer>
1289	static void clone
1290	(const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
1291	{
1292	if(!unique(node: target_header)){
1293	clear_and_dispose(target_header, disposer);
1294	}
1295
1296	node_ptr leftmost, rightmost;
1297	node_ptr new_root = clone_subtree
1298	(source_header, target_header, cloner, disposer, leftmost, rightmost);
1299
1300	//Now update header node
1301	NodeTraits::set_parent(target_header, new_root);
1302	NodeTraits::set_left (target_header, leftmost);
1303	NodeTraits::set_right (target_header, rightmost);
1304	}
1305
1306	//! <b>Requires</b>: header must be the header of a tree, z a node
1307	//! of that tree and z != header.
1308	//!
1309	//! <b>Effects</b>: Erases node "z" from the tree with header "header".
1310	//!
1311	//! <b>Complexity</b>: Amortized constant time.
1312	//!
1313	//! <b>Throws</b>: Nothing.
1314	static void erase(const node_ptr & header, const node_ptr & z)
1315	{
1316	data_for_rebalance ignored;
1317	erase(header, z, ignored);
1318	}
1319
1320	//! <b>Requires</b>: node is a tree node but not the header.
1321	//!
1322	//! <b>Effects</b>: Unlinks the node and rebalances the tree.
1323	//!
1324	//! <b>Complexity</b>: Average complexity is constant time.
1325	//!
1326	//! <b>Throws</b>: Nothing.
1327	static void unlink(const node_ptr & node)
1328	{
1329	node_ptr x = NodeTraits::get_parent(node);
1330	if(x){
1331	while(!base_type::is_header(x))
1332	x = NodeTraits::get_parent(x);
1333	erase(x, node);
1334	}
1335	}
1336
1337	//! <b>Requires</b>: header must be the header of a tree.
1338	//!
1339	//! <b>Effects</b>: Rebalances the tree.
1340	//!
1341	//! <b>Throws</b>: Nothing.
1342	//!
1343	//! <b>Complexity</b>: Linear.
1344	static void rebalance(const node_ptr & header)
1345	{
1346	node_ptr root = NodeTraits::get_parent(header);
1347	if(root){
1348	rebalance_subtree(old_root: root);
1349	}
1350	}
1351
1352	//! <b>Requires</b>: old_root is a node of a tree. It shall not be null.
1353	//!
1354	//! <b>Effects</b>: Rebalances the subtree rooted at old_root.
1355	//!
1356	//! <b>Returns</b>: The new root of the subtree.
1357	//!
1358	//! <b>Throws</b>: Nothing.
1359	//!
1360	//! <b>Complexity</b>: Linear.
1361	static node_ptr rebalance_subtree(const node_ptr & old_root)
1362	{
1363	//Taken from:
1364	//"Tree rebalancing in optimal time and space"
1365	//Quentin F. Stout and Bette L. Warren
1366
1367	//To avoid irregularities in the algorithm (old_root can be a
1368	//left or right child or even the root of the tree) just put the
1369	//root as the right child of its parent. Before doing this backup
1370	//information to restore the original relationship after
1371	//the algorithm is applied.
1372	node_ptr super_root = NodeTraits::get_parent(old_root);
1373	BOOST_INTRUSIVE_INVARIANT_ASSERT(super_root);
1374
1375	//Get root info
1376	node_ptr super_root_right_backup = NodeTraits::get_right(super_root);
1377	bool super_root_is_header = NodeTraits::get_parent(super_root) == old_root;
1378	bool old_root_is_right = is_right_child(p: old_root);
1379	NodeTraits::set_right(super_root, old_root);
1380
1381	std::size_t size;
1382	subtree_to_vine(vine_tail: super_root, size);
1383	vine_to_subtree(super_root, count: size);
1384	node_ptr new_root = NodeTraits::get_right(super_root);
1385
1386	//Recover root
1387	if(super_root_is_header){
1388	NodeTraits::set_right(super_root, super_root_right_backup);
1389	NodeTraits::set_parent(super_root, new_root);
1390	}
1391	else if(old_root_is_right){
1392	NodeTraits::set_right(super_root, new_root);
1393	}
1394	else{
1395	NodeTraits::set_right(super_root, super_root_right_backup);
1396	NodeTraits::set_left(super_root, new_root);
1397	}
1398	return new_root;
1399	}
1400
1401	//! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user.
1402	//!
1403	//! <b>Requires</b>: header must be the header of a tree.
1404	//!
1405	//! <b>Complexity</b>: Linear time.
1406	//!
1407	//! <b>Note</b>: The method might not have effect when asserts are turned off (e.g., with NDEBUG).
1408	//! Experimental function, interface might change in future versions.
1409	template<class Checker>
1410	static void check(const const_node_ptr& header, Checker checker, typename Checker::return_type& checker_return)
1411	{
1412	const_node_ptr root_node_ptr = NodeTraits::get_parent(header);
1413	if (!root_node_ptr){
1414	// check left&right header pointers
1415	BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header);
1416	BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header);
1417	}
1418	else{
1419	// check parent pointer of root node
1420	BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header);
1421	// check subtree from root
1422	check_subtree(root_node_ptr, checker, checker_return);
1423	// check left&right header pointers
1424	const_node_ptr p = root_node_ptr;
1425	while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); }
1426	BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p);
1427	p = root_node_ptr;
1428	while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); }
1429	BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p);
1430	}
1431	}
1432
1433	protected:
1434	static void erase(const node_ptr & header, const node_ptr & z, data_for_rebalance &info)
1435	{
1436	node_ptr y(z);
1437	node_ptr x;
1438	const node_ptr z_left(NodeTraits::get_left(z));
1439	const node_ptr z_right(NodeTraits::get_right(z));
1440
1441	if(!z_left){
1442	x = z_right; // x might be null.
1443	}
1444	else if(!z_right){ // z has exactly one non-null child. y == z.
1445	x = z_left; // x is not null.
1446	BOOST_ASSERT(x);
1447	}
1448	else{ //make y != z
1449	// y = find z's successor
1450	y = base_type::minimum(z_right);
1451	x = NodeTraits::get_right(y); // x might be null.
1452	}
1453
1454	node_ptr x_parent;
1455	const node_ptr z_parent(NodeTraits::get_parent(z));
1456	const bool z_is_leftchild(NodeTraits::get_left(z_parent) == z);
1457
1458	if(y != z){ //has two children and y is the minimum of z
1459	//y is z's successor and it has a null left child.
1460	//x is the right child of y (it can be null)
1461	//Relink y in place of z and link x with y's old parent
1462	NodeTraits::set_parent(z_left, y);
1463	NodeTraits::set_left(y, z_left);
1464	if(y != z_right){
1465	//Link y with the right tree of z
1466	NodeTraits::set_right(y, z_right);
1467	NodeTraits::set_parent(z_right, y);
1468	//Link x with y's old parent (y must be a left child)
1469	x_parent = NodeTraits::get_parent(y);
1470	BOOST_ASSERT(NodeTraits::get_left(x_parent) == y);
1471	if(x)
1472	NodeTraits::set_parent(x, x_parent);
1473	//Since y was the successor and not the right child of z, it must be a left child
1474	NodeTraits::set_left(x_parent, x);
1475	}
1476	else{ //y was the right child of y so no need to fix x's position
1477	x_parent = y;
1478	}
1479	NodeTraits::set_parent(y, z_parent);
1480	this_type::set_child(header, new_child: y, new_parent: z_parent, link_left: z_is_leftchild);
1481	}
1482	else { // z has zero or one child, x is one child (it can be null)
1483	//Just link x to z's parent
1484	x_parent = z_parent;
1485	if(x)
1486	NodeTraits::set_parent(x, z_parent);
1487	this_type::set_child(header, new_child: x, new_parent: z_parent, link_left: z_is_leftchild);
1488
1489	//Now update leftmost/rightmost in case z was one of them
1490	if(NodeTraits::get_left(header) == z){
1491	//z_left must be null because z is the leftmost
1492	BOOST_ASSERT(!z_left);
1493	NodeTraits::set_left(header, !z_right ?
1494	z_parent : // makes leftmost == header if z == root
1495	base_type::minimum(z_right));
1496	}
1497	if(NodeTraits::get_right(header) == z){
1498	//z_right must be null because z is the rightmost
1499	BOOST_ASSERT(!z_right);
1500	NodeTraits::set_right(header, !z_left ?
1501	z_parent : // makes rightmost == header if z == root
1502	base_type::maximum(z_left));
1503	}
1504	}
1505
1506	//If z had 0/1 child, y == z and one of its children (and maybe null)
1507	//If z had 2 children, y is the successor of z and x is the right child of y
1508	info.x = x;
1509	info.y = y;
1510	//If z had 0/1 child, x_parent is the new parent of the old right child of y (z's successor)
1511	//If z had 2 children, x_parent is the new parent of y (z_parent)
1512	BOOST_ASSERT(!x || NodeTraits::get_parent(x) == x_parent);
1513	info.x_parent = x_parent;
1514	}
1515
1516	//! <b>Requires</b>: node is a node of the tree but it's not the header.
1517	//!
1518	//! <b>Effects</b>: Returns the number of nodes of the subtree.
1519	//!
1520	//! <b>Complexity</b>: Linear time.
1521	//!
1522	//! <b>Throws</b>: Nothing.
1523	static std::size_t subtree_size(const const_node_ptr & subtree)
1524	{
1525	std::size_t count = 0;
1526	if (subtree){
1527	node_ptr n = detail::uncast(subtree);
1528	node_ptr m = NodeTraits::get_left(n);
1529	while(m){
1530	n = m;
1531	m = NodeTraits::get_left(n);
1532	}
1533
1534	while(1){
1535	++count;
1536	node_ptr n_right(NodeTraits::get_right(n));
1537	if(n_right){
1538	n = n_right;
1539	m = NodeTraits::get_left(n);
1540	while(m){
1541	n = m;
1542	m = NodeTraits::get_left(n);
1543	}
1544	}
1545	else {
1546	do{
1547	if (n == subtree){
1548	return count;
1549	}
1550	m = n;
1551	n = NodeTraits::get_parent(n);
1552	}while(NodeTraits::get_left(n) != m);
1553	}
1554	}
1555	}
1556	return count;
1557	}
1558
1559	//! <b>Requires</b>: p is a node of a tree.
1560	//!
1561	//! <b>Effects</b>: Returns true if p is a left child.
1562	//!
1563	//! <b>Complexity</b>: Constant.
1564	//!
1565	//! <b>Throws</b>: Nothing.
1566	static bool is_left_child(const node_ptr & p)
1567	{ return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; }
1568
1569	//! <b>Requires</b>: p is a node of a tree.
1570	//!
1571	//! <b>Effects</b>: Returns true if p is a right child.
1572	//!
1573	//! <b>Complexity</b>: Constant.
1574	//!
1575	//! <b>Throws</b>: Nothing.
1576	static bool is_right_child(const node_ptr & p)
1577	{ return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; }
1578
1579	static void insert_before_check
1580	(const node_ptr &header, const node_ptr & pos
1581	, insert_commit_data &commit_data
1582	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1583	, std::size_t *pdepth = 0
1584	#endif
1585	)
1586	{
1587	node_ptr prev(pos);
1588	if(pos != NodeTraits::get_left(header))
1589	prev = base_type::prev_node(pos);
1590	bool link_left = unique(node: header) || !NodeTraits::get_left(pos);
1591	commit_data.link_left = link_left;
1592	commit_data.node = link_left ? pos : prev;
1593	if(pdepth){
1594	*pdepth = commit_data.node == header ? 0 : depth(node: commit_data.node) + 1;
1595	}
1596	}
1597
1598	static void push_back_check
1599	(const node_ptr & header, insert_commit_data &commit_data
1600	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1601	, std::size_t *pdepth = 0
1602	#endif
1603	)
1604	{
1605	node_ptr prev(NodeTraits::get_right(header));
1606	if(pdepth){
1607	*pdepth = prev == header ? 0 : depth(node: prev) + 1;
1608	}
1609	commit_data.link_left = false;
1610	commit_data.node = prev;
1611	}
1612
1613	static void push_front_check
1614	(const node_ptr & header, insert_commit_data &commit_data
1615	#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1616	, std::size_t *pdepth = 0
1617	#endif
1618	)
1619	{
1620	node_ptr pos(NodeTraits::get_left(header));
1621	if(pdepth){
1622	*pdepth = pos == header ? 0 : depth(node: pos) + 1;
1623	}
1624	commit_data.link_left = true;
1625	commit_data.node = pos;
1626	}
1627
1628	template<class NodePtrCompare>
1629	static void insert_equal_check
1630	(const node_ptr &header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp
1631	, insert_commit_data &commit_data
1632	/// @cond
1633	, std::size_t *pdepth = 0
1634	/// @endcond
1635	)
1636	{
1637	if(hint == header || !comp(hint, new_node)){
1638	node_ptr prev(hint);
1639	if(hint == NodeTraits::get_left(header) ||
1640	!comp(new_node, (prev = base_type::prev_node(hint)))){
1641	bool link_left = unique(node: header) || !NodeTraits::get_left(hint);
1642	commit_data.link_left = link_left;
1643	commit_data.node = link_left ? hint : prev;
1644	if(pdepth){
1645	*pdepth = commit_data.node == header ? 0 : depth(node: commit_data.node) + 1;
1646	}
1647	}
1648	else{
1649	insert_equal_upper_bound_check(header, new_node, comp, commit_data, pdepth);
1650	}
1651	}
1652	else{
1653	insert_equal_lower_bound_check(header, new_node, comp, commit_data, pdepth);
1654	}
1655	}
1656
1657	template<class NodePtrCompare>
1658	static void insert_equal_upper_bound_check
1659	(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
1660	{
1661	std::size_t depth = 0;
1662	node_ptr y(h);
1663	node_ptr x(NodeTraits::get_parent(y));
1664
1665	while(x){
1666	++depth;
1667	y = x;
1668	x = comp(new_node, x) ?
1669	NodeTraits::get_left(x) : NodeTraits::get_right(x);
1670	}
1671	if(pdepth) *pdepth = depth;
1672	commit_data.link_left = (y == h) || comp(new_node, y);
1673	commit_data.node = y;
1674	}
1675
1676	template<class NodePtrCompare>
1677	static void insert_equal_lower_bound_check
1678	(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
1679	{
1680	std::size_t depth = 0;
1681	node_ptr y(h);
1682	node_ptr x(NodeTraits::get_parent(y));
1683
1684	while(x){
1685	++depth;
1686	y = x;
1687	x = !comp(x, new_node) ?
1688	NodeTraits::get_left(x) : NodeTraits::get_right(x);
1689	}
1690	if(pdepth) *pdepth = depth;
1691	commit_data.link_left = (y == h) || !comp(y, new_node);
1692	commit_data.node = y;
1693	}
1694
1695	static void insert_commit
1696	(const node_ptr & header, const node_ptr & new_node, const insert_commit_data &commit_data)
1697	{
1698	//Check if commit_data has not been initialized by a insert_unique_check call.
1699	BOOST_INTRUSIVE_INVARIANT_ASSERT(commit_data.node != node_ptr());
1700	node_ptr parent_node(commit_data.node);
1701	if(parent_node == header){
1702	NodeTraits::set_parent(header, new_node);
1703	NodeTraits::set_right(header, new_node);
1704	NodeTraits::set_left(header, new_node);
1705	}
1706	else if(commit_data.link_left){
1707	NodeTraits::set_left(parent_node, new_node);
1708	if(parent_node == NodeTraits::get_left(header))
1709	NodeTraits::set_left(header, new_node);
1710	}
1711	else{
1712	NodeTraits::set_right(parent_node, new_node);
1713	if(parent_node == NodeTraits::get_right(header))
1714	NodeTraits::set_right(header, new_node);
1715	}
1716	NodeTraits::set_parent(new_node, parent_node);
1717	NodeTraits::set_right(new_node, node_ptr());
1718	NodeTraits::set_left(new_node, node_ptr());
1719	}
1720
1721	//Fix header and own's parent data when replacing x with own, providing own's old data with parent
1722	static void set_child(const node_ptr & header, const node_ptr & new_child, const node_ptr & new_parent, const bool link_left)
1723	{
1724	if(new_parent == header)
1725	NodeTraits::set_parent(header, new_child);
1726	else if(link_left)
1727	NodeTraits::set_left(new_parent, new_child);
1728	else
1729	NodeTraits::set_right(new_parent, new_child);
1730	}
1731
1732	// rotate p to left (no header and p's parent fixup)
1733	static void rotate_left_no_parent_fix(const node_ptr & p, const node_ptr &p_right)
1734	{
1735	node_ptr p_right_left(NodeTraits::get_left(p_right));
1736	NodeTraits::set_right(p, p_right_left);
1737	if(p_right_left){
1738	NodeTraits::set_parent(p_right_left, p);
1739	}
1740	NodeTraits::set_left(p_right, p);
1741	NodeTraits::set_parent(p, p_right);
1742	}
1743
1744	// rotate p to left (with header and p's parent fixup)
1745	static void rotate_left(const node_ptr & p, const node_ptr & p_right, const node_ptr & p_parent, const node_ptr & header)
1746	{
1747	const bool p_was_left(NodeTraits::get_left(p_parent) == p);
1748	rotate_left_no_parent_fix(p, p_right);
1749	NodeTraits::set_parent(p_right, p_parent);
1750	set_child(header, new_child: p_right, new_parent: p_parent, link_left: p_was_left);
1751	}
1752
1753	// rotate p to right (no header and p's parent fixup)
1754	static void rotate_right_no_parent_fix(const node_ptr & p, const node_ptr &p_left)
1755	{
1756	node_ptr p_left_right(NodeTraits::get_right(p_left));
1757	NodeTraits::set_left(p, p_left_right);
1758	if(p_left_right){
1759	NodeTraits::set_parent(p_left_right, p);
1760	}
1761	NodeTraits::set_right(p_left, p);
1762	NodeTraits::set_parent(p, p_left);
1763	}
1764
1765	// rotate p to right (with header and p's parent fixup)
1766	static void rotate_right(const node_ptr & p, const node_ptr & p_left, const node_ptr & p_parent, const node_ptr & header)
1767	{
1768	const bool p_was_left(NodeTraits::get_left(p_parent) == p);
1769	rotate_right_no_parent_fix(p, p_left);
1770	NodeTraits::set_parent(p_left, p_parent);
1771	set_child(header, new_child: p_left, new_parent: p_parent, link_left: p_was_left);
1772	}
1773
1774	private:
1775
1776	static void subtree_to_vine(node_ptr vine_tail, std::size_t &size)
1777	{
1778	//Inspired by LibAVL:
1779	//It uses a clever optimization for trees with parent pointers.
1780	//No parent pointer is updated when transforming a tree to a vine as
1781	//most of them will be overriten during compression rotations.
1782	//A final pass must be made after the rebalancing to updated those
1783	//pointers not updated by tree_to_vine + compression calls
1784	std::size_t len = 0;
1785	node_ptr remainder = NodeTraits::get_right(vine_tail);
1786	while(remainder){
1787	node_ptr tempptr = NodeTraits::get_left(remainder);
1788	if(!tempptr){ //move vine-tail down one
1789	vine_tail = remainder;
1790	remainder = NodeTraits::get_right(remainder);
1791	++len;
1792	}
1793	else{ //rotate
1794	NodeTraits::set_left(remainder, NodeTraits::get_right(tempptr));
1795	NodeTraits::set_right(tempptr, remainder);
1796	remainder = tempptr;
1797	NodeTraits::set_right(vine_tail, tempptr);
1798	}
1799	}
1800	size = len;
1801	}
1802
1803	static void compress_subtree(node_ptr scanner, std::size_t count)
1804	{
1805	while(count--){ //compress "count" spine nodes in the tree with pseudo-root scanner
1806	node_ptr child = NodeTraits::get_right(scanner);
1807	node_ptr child_right = NodeTraits::get_right(child);
1808	NodeTraits::set_right(scanner, child_right);
1809	//Avoid setting the parent of child_right
1810	scanner = child_right;
1811	node_ptr scanner_left = NodeTraits::get_left(scanner);
1812	NodeTraits::set_right(child, scanner_left);
1813	if(scanner_left)
1814	NodeTraits::set_parent(scanner_left, child);
1815	NodeTraits::set_left(scanner, child);
1816	NodeTraits::set_parent(child, scanner);
1817	}
1818	}
1819
1820	static void vine_to_subtree(const node_ptr & super_root, std::size_t count)
1821	{
1822	const std::size_t one_szt = 1u;
1823	std::size_t leaf_nodes = count + one_szt - std::size_t(one_szt << detail::floor_log2(n: count + one_szt));
1824	compress_subtree(scanner: super_root, count: leaf_nodes); //create deepest leaves
1825	std::size_t vine_nodes = count - leaf_nodes;
1826	while(vine_nodes > 1){
1827	vine_nodes /= 2;
1828	compress_subtree(scanner: super_root, count: vine_nodes);
1829	}
1830
1831	//Update parents of nodes still in the in the original vine line
1832	//as those have not been updated by subtree_to_vine or compress_subtree
1833	for ( node_ptr q = super_root, p = NodeTraits::get_right(super_root)
1834	; p
1835	; q = p, p = NodeTraits::get_right(p)){
1836	NodeTraits::set_parent(p, q);
1837	}
1838	}
1839
1840	//! <b>Requires</b>: "n" must be a node inserted in a tree.
1841	//!
1842	//! <b>Effects</b>: Returns a pointer to the header node of the tree.
1843	//!
1844	//! <b>Complexity</b>: Logarithmic.
1845	//!
1846	//! <b>Throws</b>: Nothing.
1847	static node_ptr get_root(const node_ptr & node)
1848	{
1849	BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node)));
1850	node_ptr x = NodeTraits::get_parent(node);
1851	if(x){
1852	while(!base_type::is_header(x)){
1853	x = NodeTraits::get_parent(x);
1854	}
1855	return x;
1856	}
1857	else{
1858	return node;
1859	}
1860	}
1861
1862	template <class Cloner, class Disposer>
1863	static node_ptr clone_subtree
1864	(const const_node_ptr &source_parent, const node_ptr &target_parent
1865	, Cloner cloner, Disposer disposer
1866	, node_ptr &leftmost_out, node_ptr &rightmost_out
1867	)
1868	{
1869	node_ptr target_sub_root = target_parent;
1870	node_ptr source_root = NodeTraits::get_parent(source_parent);
1871	if(!source_root){
1872	leftmost_out = rightmost_out = source_root;
1873	}
1874	else{
1875	//We'll calculate leftmost and rightmost nodes while iterating
1876	node_ptr current = source_root;
1877	node_ptr insertion_point = target_sub_root = cloner(current);
1878
1879	//We'll calculate leftmost and rightmost nodes while iterating
1880	node_ptr leftmost = target_sub_root;
1881	node_ptr rightmost = target_sub_root;
1882
1883	//First set the subroot
1884	NodeTraits::set_left(target_sub_root, node_ptr());
1885	NodeTraits::set_right(target_sub_root, node_ptr());
1886	NodeTraits::set_parent(target_sub_root, target_parent);
1887
1888	dispose_subtree_disposer<Disposer> rollback(disposer, target_sub_root);
1889	while(true) {
1890	//First clone left nodes
1891	if( NodeTraits::get_left(current) &&
1892	!NodeTraits::get_left(insertion_point)) {
1893	current = NodeTraits::get_left(current);
1894	node_ptr temp = insertion_point;
1895	//Clone and mark as leaf
1896	insertion_point = cloner(current);
1897	NodeTraits::set_left (insertion_point, node_ptr());
1898	NodeTraits::set_right (insertion_point, node_ptr());
1899	//Insert left
1900	NodeTraits::set_parent(insertion_point, temp);
1901	NodeTraits::set_left (temp, insertion_point);
1902	//Update leftmost
1903	if(rightmost == target_sub_root)
1904	leftmost = insertion_point;
1905	}
1906	//Then clone right nodes
1907	else if( NodeTraits::get_right(current) &&
1908	!NodeTraits::get_right(insertion_point)){
1909	current = NodeTraits::get_right(current);
1910	node_ptr temp = insertion_point;
1911	//Clone and mark as leaf
1912	insertion_point = cloner(current);
1913	NodeTraits::set_left (insertion_point, node_ptr());
1914	NodeTraits::set_right (insertion_point, node_ptr());
1915	//Insert right
1916	NodeTraits::set_parent(insertion_point, temp);
1917	NodeTraits::set_right (temp, insertion_point);
1918	//Update rightmost
1919	rightmost = insertion_point;
1920	}
1921	//If not, go up
1922	else if(current == source_root){
1923	break;
1924	}
1925	else{
1926	//Branch completed, go up searching more nodes to clone
1927	current = NodeTraits::get_parent(current);
1928	insertion_point = NodeTraits::get_parent(insertion_point);
1929	}
1930	}
1931	rollback.release();
1932	leftmost_out = leftmost;
1933	rightmost_out = rightmost;
1934	}
1935	return target_sub_root;
1936	}
1937
1938	template<class Disposer>
1939	static void dispose_subtree(node_ptr x, Disposer disposer)
1940	{
1941	while (x){
1942	node_ptr save(NodeTraits::get_left(x));
1943	if (save) {
1944	// Right rotation
1945	NodeTraits::set_left(x, NodeTraits::get_right(save));
1946	NodeTraits::set_right(save, x);
1947	}
1948	else {
1949	save = NodeTraits::get_right(x);
1950	init(node: x);
1951	disposer(x);
1952	}
1953	x = save;
1954	}
1955	}
1956
1957	template<class KeyType, class KeyNodePtrCompare>
1958	static node_ptr lower_bound_loop
1959	(node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp)
1960	{
1961	while(x){
1962	if(comp(x, key)){
1963	x = NodeTraits::get_right(x);
1964	}
1965	else{
1966	y = x;
1967	x = NodeTraits::get_left(x);
1968	}
1969	}
1970	return y;
1971	}
1972
1973	template<class KeyType, class KeyNodePtrCompare>
1974	static node_ptr upper_bound_loop
1975	(node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp)
1976	{
1977	while(x){
1978	if(comp(key, x)){
1979	y = x;
1980	x = NodeTraits::get_left(x);
1981	}
1982	else{
1983	x = NodeTraits::get_right(x);
1984	}
1985	}
1986	return y;
1987	}
1988
1989	template<class Checker>
1990	static void check_subtree(const const_node_ptr& node, Checker checker, typename Checker::return_type& check_return)
1991	{
1992	const_node_ptr left = NodeTraits::get_left(node);
1993	const_node_ptr right = NodeTraits::get_right(node);
1994	typename Checker::return_type check_return_left;
1995	typename Checker::return_type check_return_right;
1996	if (left)
1997	{
1998	BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(left) == node);
1999	check_subtree(left, checker, check_return_left);
2000	}
2001	if (right)
2002	{
2003	BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(right) == node);
2004	check_subtree(right, checker, check_return_right);
2005	}
2006	checker(node, check_return_left, check_return_right, check_return);
2007	}
2008	};
2009
2010	/// @cond
2011
2012	template<class NodeTraits>
2013	struct get_algo<BsTreeAlgorithms, NodeTraits>
2014	{
2015	typedef bstree_algorithms<NodeTraits> type;
2016	};
2017
2018	template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
2019	struct get_node_checker<BsTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
2020	{
2021	typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
2022	};
2023
2024	/// @endcond
2025
2026	} //namespace intrusive
2027	} //namespace boost
2028
2029	#include <boost/intrusive/detail/config_end.hpp>
2030
2031	#endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP
2032