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