1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Daniel K. O. 2005. |
4 | // (C) Copyright Ion Gaztanaga 2007-2014 |
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_AVLTREE_ALGORITHMS_HPP |
15 | #define BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP |
16 | |
17 | #include <boost/intrusive/detail/config_begin.hpp> |
18 | #include <boost/intrusive/intrusive_fwd.hpp> |
19 | |
20 | #include <cstddef> |
21 | |
22 | #include <boost/intrusive/detail/assert.hpp> |
23 | #include <boost/intrusive/detail/algo_type.hpp> |
24 | #include <boost/intrusive/detail/ebo_functor_holder.hpp> |
25 | #include <boost/intrusive/bstree_algorithms.hpp> |
26 | |
27 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
28 | # pragma once |
29 | #endif |
30 | |
31 | |
32 | namespace boost { |
33 | namespace intrusive { |
34 | |
35 | /// @cond |
36 | |
37 | template<class NodeTraits, class F> |
38 | struct avltree_node_cloner |
39 | //Use public inheritance to avoid MSVC bugs with closures |
40 | : public detail::ebo_functor_holder<F> |
41 | { |
42 | typedef typename NodeTraits::node_ptr node_ptr; |
43 | typedef detail::ebo_functor_holder<F> base_t; |
44 | |
45 | avltree_node_cloner(F f) |
46 | : base_t(f) |
47 | {} |
48 | |
49 | node_ptr operator()(const node_ptr & p) |
50 | { |
51 | node_ptr n = base_t::get()(p); |
52 | NodeTraits::set_balance(n, NodeTraits::get_balance(p)); |
53 | return n; |
54 | } |
55 | |
56 | node_ptr operator()(const node_ptr & p) const |
57 | { |
58 | node_ptr n = base_t::get()(p); |
59 | NodeTraits::set_balance(n, NodeTraits::get_balance(p)); |
60 | return n; |
61 | } |
62 | }; |
63 | |
64 | namespace detail { |
65 | |
66 | template<class ValueTraits, class NodePtrCompare, class ExtraChecker> |
67 | struct avltree_node_checker |
68 | : public bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> |
69 | { |
70 | typedef bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> base_checker_t; |
71 | typedef ValueTraits value_traits; |
72 | typedef typename value_traits::node_traits node_traits; |
73 | typedef typename node_traits::const_node_ptr const_node_ptr; |
74 | |
75 | struct return_type |
76 | : public base_checker_t::return_type |
77 | { |
78 | return_type() : height(0) {} |
79 | int height; |
80 | }; |
81 | |
82 | avltree_node_checker(const NodePtrCompare& comp, ExtraChecker ) |
83 | : base_checker_t(comp, extra_checker) |
84 | {} |
85 | |
86 | void operator () (const const_node_ptr& p, |
87 | const return_type& check_return_left, const return_type& check_return_right, |
88 | return_type& check_return) |
89 | { |
90 | const int height_diff = check_return_right.height - check_return_left.height; (void)height_diff; |
91 | BOOST_INTRUSIVE_INVARIANT_ASSERT( |
92 | (height_diff == -1 && node_traits::get_balance(p) == node_traits::negative()) || |
93 | (height_diff == 0 && node_traits::get_balance(p) == node_traits::zero()) || |
94 | (height_diff == 1 && node_traits::get_balance(p) == node_traits::positive()) |
95 | ); |
96 | check_return.height = 1 + |
97 | (check_return_left.height > check_return_right.height ? check_return_left.height : check_return_right.height); |
98 | base_checker_t::operator()(p, check_return_left, check_return_right, check_return); |
99 | } |
100 | }; |
101 | |
102 | } // namespace detail |
103 | |
104 | /// @endcond |
105 | |
106 | //! avltree_algorithms is configured with a NodeTraits class, which encapsulates the |
107 | //! information about the node to be manipulated. NodeTraits must support the |
108 | //! following interface: |
109 | //! |
110 | //! <b>Typedefs</b>: |
111 | //! |
112 | //! <tt>node</tt>: The type of the node that forms the binary search tree |
113 | //! |
114 | //! <tt>node_ptr</tt>: A pointer to a node |
115 | //! |
116 | //! <tt>const_node_ptr</tt>: A pointer to a const node |
117 | //! |
118 | //! <tt>balance</tt>: The type of the balance factor |
119 | //! |
120 | //! <b>Static functions</b>: |
121 | //! |
122 | //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> |
123 | //! |
124 | //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> |
125 | //! |
126 | //! <tt>static node_ptr get_left(const_node_ptr n);</tt> |
127 | //! |
128 | //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> |
129 | //! |
130 | //! <tt>static node_ptr get_right(const_node_ptr n);</tt> |
131 | //! |
132 | //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> |
133 | //! |
134 | //! <tt>static balance get_balance(const_node_ptr n);</tt> |
135 | //! |
136 | //! <tt>static void set_balance(node_ptr n, balance b);</tt> |
137 | //! |
138 | //! <tt>static balance negative();</tt> |
139 | //! |
140 | //! <tt>static balance zero();</tt> |
141 | //! |
142 | //! <tt>static balance positive();</tt> |
143 | template<class NodeTraits> |
144 | class avltree_algorithms |
145 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
146 | : public bstree_algorithms<NodeTraits> |
147 | #endif |
148 | { |
149 | public: |
150 | typedef typename NodeTraits::node node; |
151 | typedef NodeTraits node_traits; |
152 | typedef typename NodeTraits::node_ptr node_ptr; |
153 | typedef typename NodeTraits::const_node_ptr const_node_ptr; |
154 | typedef typename NodeTraits::balance balance; |
155 | |
156 | /// @cond |
157 | private: |
158 | typedef bstree_algorithms<NodeTraits> bstree_algo; |
159 | |
160 | /// @endcond |
161 | |
162 | public: |
163 | //! This type is the information that will be |
164 | //! filled by insert_unique_check |
165 | typedef typename bstree_algo::insert_commit_data insert_commit_data; |
166 | |
167 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
168 | |
169 | //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) |
170 | static node_ptr get_header(const const_node_ptr & n); |
171 | |
172 | //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node |
173 | static node_ptr begin_node(const const_node_ptr & header); |
174 | |
175 | //! @copydoc ::boost::intrusive::bstree_algorithms::end_node |
176 | static node_ptr end_node(const const_node_ptr & header); |
177 | |
178 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree |
179 | static void swap_tree(const node_ptr & header1, const node_ptr & header2); |
180 | |
181 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
182 | |
183 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) |
184 | static void swap_nodes(const node_ptr & node1, const node_ptr & node2) |
185 | { |
186 | if(node1 == node2) |
187 | return; |
188 | |
189 | node_ptr (bstree_algo::get_header(node1)), (bstree_algo::get_header(node2)); |
190 | swap_nodes(node1, header1, node2, header2); |
191 | } |
192 | |
193 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&) |
194 | static void swap_nodes(const node_ptr & node1, const node_ptr & , const node_ptr & node2, const node_ptr & ) |
195 | { |
196 | if(node1 == node2) return; |
197 | |
198 | bstree_algo::swap_nodes(node1, header1, node2, header2); |
199 | //Swap balance |
200 | balance c = NodeTraits::get_balance(node1); |
201 | NodeTraits::set_balance(node1, NodeTraits::get_balance(node2)); |
202 | NodeTraits::set_balance(node2, c); |
203 | } |
204 | |
205 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) |
206 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node) |
207 | { |
208 | if(node_to_be_replaced == new_node) |
209 | return; |
210 | replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node); |
211 | } |
212 | |
213 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) |
214 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & , const node_ptr & new_node) |
215 | { |
216 | bstree_algo::replace_node(node_to_be_replaced, header, new_node); |
217 | NodeTraits::set_balance(new_node, NodeTraits::get_balance(node_to_be_replaced)); |
218 | } |
219 | |
220 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&) |
221 | static void unlink(const node_ptr & node) |
222 | { |
223 | node_ptr x = NodeTraits::get_parent(node); |
224 | if(x){ |
225 | while(!is_header(p: x)) |
226 | x = NodeTraits::get_parent(x); |
227 | erase(header: x, z: node); |
228 | } |
229 | } |
230 | |
231 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
232 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance |
233 | static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); |
234 | |
235 | //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) |
236 | static bool unique(const const_node_ptr & node); |
237 | |
238 | //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) |
239 | static std::size_t size(const const_node_ptr & header); |
240 | |
241 | //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) |
242 | static node_ptr next_node(const node_ptr & node); |
243 | |
244 | //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) |
245 | static node_ptr prev_node(const node_ptr & node); |
246 | |
247 | //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) |
248 | static void init(const node_ptr & node); |
249 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
250 | |
251 | //! <b>Requires</b>: node must not be part of any tree. |
252 | //! |
253 | //! <b>Effects</b>: Initializes the header to represent an empty tree. |
254 | //! unique(header) == true. |
255 | //! |
256 | //! <b>Complexity</b>: Constant. |
257 | //! |
258 | //! <b>Throws</b>: Nothing. |
259 | //! |
260 | //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. |
261 | static void (const node_ptr & ) |
262 | { |
263 | bstree_algo::init_header(header); |
264 | NodeTraits::set_balance(header, NodeTraits::zero()); |
265 | } |
266 | |
267 | //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) |
268 | static node_ptr erase(const node_ptr & , const node_ptr & z) |
269 | { |
270 | typename bstree_algo::data_for_rebalance info; |
271 | bstree_algo::erase(header, z, info); |
272 | if(info.y != z){ |
273 | NodeTraits::set_balance(info.y, NodeTraits::get_balance(z)); |
274 | } |
275 | //Rebalance avltree |
276 | rebalance_after_erasure(header, x: info.x, x_parent: info.x_parent); |
277 | return z; |
278 | } |
279 | |
280 | //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) |
281 | template <class Cloner, class Disposer> |
282 | static void clone |
283 | (const const_node_ptr & , const node_ptr & , Cloner cloner, Disposer disposer) |
284 | { |
285 | avltree_node_cloner<NodeTraits, Cloner> new_cloner(cloner); |
286 | bstree_algo::clone(source_header, target_header, new_cloner, disposer); |
287 | } |
288 | |
289 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
290 | //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) |
291 | template<class Disposer> |
292 | static void clear_and_dispose(const node_ptr & header, Disposer disposer); |
293 | |
294 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
295 | template<class KeyType, class KeyNodePtrCompare> |
296 | static node_ptr lower_bound |
297 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
298 | |
299 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
300 | template<class KeyType, class KeyNodePtrCompare> |
301 | static node_ptr upper_bound |
302 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
303 | |
304 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
305 | template<class KeyType, class KeyNodePtrCompare> |
306 | static node_ptr find |
307 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
308 | |
309 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
310 | template<class KeyType, class KeyNodePtrCompare> |
311 | static std::pair<node_ptr, node_ptr> equal_range |
312 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
313 | |
314 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) |
315 | template<class KeyType, class KeyNodePtrCompare> |
316 | static std::pair<node_ptr, node_ptr> bounded_range |
317 | (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp |
318 | , bool left_closed, bool right_closed); |
319 | |
320 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
321 | template<class KeyType, class KeyNodePtrCompare> |
322 | static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
323 | |
324 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
325 | |
326 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) |
327 | template<class NodePtrCompare> |
328 | static node_ptr insert_equal_upper_bound |
329 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) |
330 | { |
331 | bstree_algo::insert_equal_upper_bound(h, new_node, comp); |
332 | rebalance_after_insertion(header: h, x: new_node); |
333 | return new_node; |
334 | } |
335 | |
336 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) |
337 | template<class NodePtrCompare> |
338 | static node_ptr insert_equal_lower_bound |
339 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) |
340 | { |
341 | bstree_algo::insert_equal_lower_bound(h, new_node, comp); |
342 | rebalance_after_insertion(header: h, x: new_node); |
343 | return new_node; |
344 | } |
345 | |
346 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) |
347 | template<class NodePtrCompare> |
348 | static node_ptr insert_equal |
349 | (const node_ptr & , const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) |
350 | { |
351 | bstree_algo::insert_equal(header, hint, new_node, comp); |
352 | rebalance_after_insertion(header, x: new_node); |
353 | return new_node; |
354 | } |
355 | |
356 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) |
357 | static node_ptr insert_before |
358 | (const node_ptr & , const node_ptr & pos, const node_ptr & new_node) |
359 | { |
360 | bstree_algo::insert_before(header, pos, new_node); |
361 | rebalance_after_insertion(header, x: new_node); |
362 | return new_node; |
363 | } |
364 | |
365 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) |
366 | static void push_back(const node_ptr & , const node_ptr & new_node) |
367 | { |
368 | bstree_algo::push_back(header, new_node); |
369 | rebalance_after_insertion(header, x: new_node); |
370 | } |
371 | |
372 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) |
373 | static void push_front(const node_ptr & , const node_ptr & new_node) |
374 | { |
375 | bstree_algo::push_front(header, new_node); |
376 | rebalance_after_insertion(header, x: new_node); |
377 | } |
378 | |
379 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
380 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) |
381 | template<class KeyType, class KeyNodePtrCompare> |
382 | static std::pair<node_ptr, bool> insert_unique_check |
383 | (const const_node_ptr & header, const KeyType &key |
384 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data); |
385 | |
386 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) |
387 | template<class KeyType, class KeyNodePtrCompare> |
388 | static std::pair<node_ptr, bool> insert_unique_check |
389 | (const const_node_ptr & header, const node_ptr &hint, const KeyType &key |
390 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data); |
391 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
392 | |
393 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data &) |
394 | static void insert_unique_commit |
395 | (const node_ptr & , const node_ptr & new_value, const insert_commit_data &commit_data) |
396 | { |
397 | bstree_algo::insert_unique_commit(header, new_value, commit_data); |
398 | rebalance_after_insertion(header, x: new_value); |
399 | } |
400 | |
401 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header |
402 | static bool (const const_node_ptr & p) |
403 | { return NodeTraits::get_balance(p) == NodeTraits::zero() && bstree_algo::is_header(p); } |
404 | |
405 | |
406 | /// @cond |
407 | static bool verify(const node_ptr &) |
408 | { |
409 | std::size_t height; |
410 | std::size_t count; |
411 | return verify_recursion(n: NodeTraits::get_parent(header), count, height); |
412 | } |
413 | |
414 | private: |
415 | |
416 | static bool verify_recursion(node_ptr n, std::size_t &count, std::size_t &height) |
417 | { |
418 | if (!n){ |
419 | count = 0; |
420 | height = 0; |
421 | return true; |
422 | } |
423 | std::size_t leftcount, rightcount; |
424 | std::size_t leftheight, rightheight; |
425 | if(!verify_recursion(n: NodeTraits::get_left (n), count&: leftcount, height&: leftheight) || |
426 | !verify_recursion(n: NodeTraits::get_right(n), count&: rightcount, height&: rightheight) ){ |
427 | return false; |
428 | } |
429 | count = 1u + leftcount + rightcount; |
430 | height = 1u + (leftheight > rightheight ? leftheight : rightheight); |
431 | |
432 | //If equal height, balance must be zero |
433 | if(rightheight == leftheight){ |
434 | if(NodeTraits::get_balance(n) != NodeTraits::zero()){ |
435 | BOOST_ASSERT(0); |
436 | return false; |
437 | } |
438 | } |
439 | //If right is taller than left, then the difference must be at least 1 and the balance positive |
440 | else if(rightheight > leftheight){ |
441 | if(rightheight - leftheight > 1 ){ |
442 | BOOST_ASSERT(0); |
443 | return false; |
444 | } |
445 | else if(NodeTraits::get_balance(n) != NodeTraits::positive()){ |
446 | BOOST_ASSERT(0); |
447 | return false; |
448 | } |
449 | } |
450 | //If left is taller than right, then the difference must be at least 1 and the balance negative |
451 | else{ |
452 | if(leftheight - rightheight > 1 ){ |
453 | BOOST_ASSERT(0); |
454 | return false; |
455 | } |
456 | else if(NodeTraits::get_balance(n) != NodeTraits::negative()){ |
457 | BOOST_ASSERT(0); |
458 | return false; |
459 | } |
460 | } |
461 | return true; |
462 | } |
463 | |
464 | static void rebalance_after_erasure(const node_ptr & , node_ptr x, node_ptr x_parent) |
465 | { |
466 | for ( node_ptr root = NodeTraits::get_parent(header) |
467 | ; x != root |
468 | ; root = NodeTraits::get_parent(header), x_parent = NodeTraits::get_parent(x)) { |
469 | const balance x_parent_balance = NodeTraits::get_balance(x_parent); |
470 | //Don't cache x_is_leftchild or similar because x can be null and |
471 | //equal to both x_parent_left and x_parent_right |
472 | const node_ptr x_parent_left (NodeTraits::get_left(x_parent)); |
473 | const node_ptr x_parent_right(NodeTraits::get_right(x_parent)); |
474 | |
475 | if(x_parent_balance == NodeTraits::zero()){ |
476 | NodeTraits::set_balance( x_parent, x == x_parent_right ? NodeTraits::negative() : NodeTraits::positive() ); |
477 | break; // the height didn't change, let's stop here |
478 | } |
479 | else if(x_parent_balance == NodeTraits::negative()){ |
480 | if (x == x_parent_left) { ////x is left child or x and sibling are null |
481 | NodeTraits::set_balance(x_parent, NodeTraits::zero()); // balanced |
482 | x = x_parent; |
483 | } |
484 | else { |
485 | // x is right child (x_parent_left is the left child) |
486 | BOOST_INTRUSIVE_INVARIANT_ASSERT(x_parent_left); |
487 | if (NodeTraits::get_balance(x_parent_left) == NodeTraits::positive()) { |
488 | // x_parent_left MUST have a right child |
489 | BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(x_parent_left)); |
490 | x = avl_rotate_left_right(a: x_parent, a_oldleft: x_parent_left, hdr: header); |
491 | } |
492 | else { |
493 | avl_rotate_right(x: x_parent, x_oldleft: x_parent_left, hdr: header); |
494 | x = x_parent_left; |
495 | } |
496 | |
497 | // if changed from negative to NodeTraits::positive(), no need to check above |
498 | if (NodeTraits::get_balance(x) == NodeTraits::positive()){ |
499 | break; |
500 | } |
501 | } |
502 | } |
503 | else if(x_parent_balance == NodeTraits::positive()){ |
504 | if (x == x_parent_right) { //x is right child or x and sibling are null |
505 | NodeTraits::set_balance(x_parent, NodeTraits::zero()); // balanced |
506 | x = x_parent; |
507 | } |
508 | else { |
509 | // x is left child (x_parent_right is the right child) |
510 | BOOST_INTRUSIVE_INVARIANT_ASSERT(x_parent_right); |
511 | if (NodeTraits::get_balance(x_parent_right) == NodeTraits::negative()) { |
512 | // x_parent_right MUST have then a left child |
513 | BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(x_parent_right)); |
514 | x = avl_rotate_right_left(a: x_parent, a_oldright: x_parent_right, hdr: header); |
515 | } |
516 | else { |
517 | avl_rotate_left(x: x_parent, x_oldright: x_parent_right, hdr: header); |
518 | x = x_parent_right; |
519 | } |
520 | // if changed from NodeTraits::positive() to negative, no need to check above |
521 | if (NodeTraits::get_balance(x) == NodeTraits::negative()){ |
522 | break; |
523 | } |
524 | } |
525 | } |
526 | else{ |
527 | BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached |
528 | } |
529 | } |
530 | } |
531 | |
532 | static void rebalance_after_insertion(const node_ptr & , node_ptr x) |
533 | { |
534 | NodeTraits::set_balance(x, NodeTraits::zero()); |
535 | // Rebalance. |
536 | for(node_ptr root = NodeTraits::get_parent(header); x != root; root = NodeTraits::get_parent(header)){ |
537 | node_ptr const x_parent(NodeTraits::get_parent(x)); |
538 | node_ptr const x_parent_left(NodeTraits::get_left(x_parent)); |
539 | const balance x_parent_balance = NodeTraits::get_balance(x_parent); |
540 | const bool x_is_leftchild(x == x_parent_left); |
541 | if(x_parent_balance == NodeTraits::zero()){ |
542 | // if x is left, parent will have parent->bal_factor = negative |
543 | // else, parent->bal_factor = NodeTraits::positive() |
544 | NodeTraits::set_balance( x_parent, x_is_leftchild ? NodeTraits::negative() : NodeTraits::positive() ); |
545 | x = x_parent; |
546 | } |
547 | else if(x_parent_balance == NodeTraits::positive()){ |
548 | // if x is a left child, parent->bal_factor = zero |
549 | if (x_is_leftchild) |
550 | NodeTraits::set_balance(x_parent, NodeTraits::zero()); |
551 | else{ // x is a right child, needs rebalancing |
552 | if (NodeTraits::get_balance(x) == NodeTraits::negative()) |
553 | avl_rotate_right_left(a: x_parent, a_oldright: x, hdr: header); |
554 | else |
555 | avl_rotate_left(x: x_parent, x_oldright: x, hdr: header); |
556 | } |
557 | break; |
558 | } |
559 | else if(x_parent_balance == NodeTraits::negative()){ |
560 | // if x is a left child, needs rebalancing |
561 | if (x_is_leftchild) { |
562 | if (NodeTraits::get_balance(x) == NodeTraits::positive()) |
563 | avl_rotate_left_right(a: x_parent, a_oldleft: x, hdr: header); |
564 | else |
565 | avl_rotate_right(x: x_parent, x_oldleft: x, hdr: header); |
566 | } |
567 | else |
568 | NodeTraits::set_balance(x_parent, NodeTraits::zero()); |
569 | break; |
570 | } |
571 | else{ |
572 | BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached |
573 | } |
574 | } |
575 | } |
576 | |
577 | static void left_right_balancing(const node_ptr & a, const node_ptr & b, const node_ptr & c) |
578 | { |
579 | // balancing... |
580 | const balance c_balance = NodeTraits::get_balance(c); |
581 | const balance zero_balance = NodeTraits::zero(); |
582 | const balance posi_balance = NodeTraits::positive(); |
583 | const balance nega_balance = NodeTraits::negative(); |
584 | NodeTraits::set_balance(c, zero_balance); |
585 | if(c_balance == nega_balance){ |
586 | NodeTraits::set_balance(a, posi_balance); |
587 | NodeTraits::set_balance(b, zero_balance); |
588 | } |
589 | else if(c_balance == zero_balance){ |
590 | NodeTraits::set_balance(a, zero_balance); |
591 | NodeTraits::set_balance(b, zero_balance); |
592 | } |
593 | else if(c_balance == posi_balance){ |
594 | NodeTraits::set_balance(a, zero_balance); |
595 | NodeTraits::set_balance(b, nega_balance); |
596 | } |
597 | else{ |
598 | BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached |
599 | } |
600 | } |
601 | |
602 | static node_ptr avl_rotate_left_right(const node_ptr a, const node_ptr a_oldleft, const node_ptr & hdr) |
603 | { // [note: 'a_oldleft' is 'b'] |
604 | // | | // |
605 | // a(-2) c // |
606 | // / \ / \ // |
607 | // / \ ==> / \ // |
608 | // (pos)b [g] b a // |
609 | // / \ / \ / \ // |
610 | // [d] c [d] e f [g] // |
611 | // / \ // |
612 | // e f // |
613 | const node_ptr c = NodeTraits::get_right(a_oldleft); |
614 | bstree_algo::rotate_left_no_parent_fix(a_oldleft, c); |
615 | //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_left(a, c)] |
616 | //as c is not root and another rotation is coming |
617 | bstree_algo::rotate_right(a, c, NodeTraits::get_parent(a), hdr); |
618 | left_right_balancing(a, b: a_oldleft, c); |
619 | return c; |
620 | } |
621 | |
622 | static node_ptr avl_rotate_right_left(const node_ptr a, const node_ptr a_oldright, const node_ptr & hdr) |
623 | { // [note: 'a_oldright' is 'b'] |
624 | // | | // |
625 | // a(pos) c // |
626 | // / \ / \ // |
627 | // / \ / \ // |
628 | // [d] b(neg) ==> a b // |
629 | // / \ / \ / \ // |
630 | // c [g] [d] e f [g] // |
631 | // / \ // |
632 | // e f // |
633 | const node_ptr c (NodeTraits::get_left(a_oldright)); |
634 | bstree_algo::rotate_right_no_parent_fix(a_oldright, c); |
635 | //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_right(a, c)] |
636 | //as c is not root and another rotation is coming. |
637 | bstree_algo::rotate_left(a, c, NodeTraits::get_parent(a), hdr); |
638 | left_right_balancing(a: a_oldright, b: a, c); |
639 | return c; |
640 | } |
641 | |
642 | static void avl_rotate_left(const node_ptr &x, const node_ptr &x_oldright, const node_ptr & hdr) |
643 | { |
644 | bstree_algo::rotate_left(x, x_oldright, NodeTraits::get_parent(x), hdr); |
645 | |
646 | // reset the balancing factor |
647 | if (NodeTraits::get_balance(x_oldright) == NodeTraits::positive()) { |
648 | NodeTraits::set_balance(x, NodeTraits::zero()); |
649 | NodeTraits::set_balance(x_oldright, NodeTraits::zero()); |
650 | } |
651 | else { // this doesn't happen during insertions |
652 | NodeTraits::set_balance(x, NodeTraits::positive()); |
653 | NodeTraits::set_balance(x_oldright, NodeTraits::negative()); |
654 | } |
655 | } |
656 | |
657 | static void avl_rotate_right(const node_ptr &x, const node_ptr &x_oldleft, const node_ptr & hdr) |
658 | { |
659 | bstree_algo::rotate_right(x, x_oldleft, NodeTraits::get_parent(x), hdr); |
660 | |
661 | // reset the balancing factor |
662 | if (NodeTraits::get_balance(x_oldleft) == NodeTraits::negative()) { |
663 | NodeTraits::set_balance(x, NodeTraits::zero()); |
664 | NodeTraits::set_balance(x_oldleft, NodeTraits::zero()); |
665 | } |
666 | else { // this doesn't happen during insertions |
667 | NodeTraits::set_balance(x, NodeTraits::negative()); |
668 | NodeTraits::set_balance(x_oldleft, NodeTraits::positive()); |
669 | } |
670 | } |
671 | |
672 | /// @endcond |
673 | }; |
674 | |
675 | /// @cond |
676 | |
677 | template<class NodeTraits> |
678 | struct get_algo<AvlTreeAlgorithms, NodeTraits> |
679 | { |
680 | typedef avltree_algorithms<NodeTraits> type; |
681 | }; |
682 | |
683 | template <class ValueTraits, class NodePtrCompare, class ExtraChecker> |
684 | struct get_node_checker<AvlTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> |
685 | { |
686 | typedef detail::avltree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; |
687 | }; |
688 | |
689 | /// @endcond |
690 | |
691 | } //namespace intrusive |
692 | } //namespace boost |
693 | |
694 | #include <boost/intrusive/detail/config_end.hpp> |
695 | |
696 | #endif //BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP |
697 | |