]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 extra_checker) | |
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 header1(bstree_algo::get_header(node1)), header2(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 & header1, const node_ptr & node2, const node_ptr & header2) | |
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 & header, 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(x)) | |
226 | x = NodeTraits::get_parent(x); | |
227 | erase(x, 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 init_header(const node_ptr & header) | |
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 & header, const node_ptr & z) | |
269 | { | |
270 | typename bstree_algo::data_for_rebalance info; | |
271 | bstree_algo::erase(header, z, info); | |
272 | rebalance_after_erasure(header, z, info); | |
273 | return z; | |
274 | } | |
275 | ||
276 | //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique | |
277 | template<class NodePtrCompare> | |
278 | static bool transfer_unique | |
279 | (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z) | |
280 | { | |
281 | typename bstree_algo::data_for_rebalance info; | |
282 | bool const transferred = bstree_algo::transfer_unique(header1, comp, header2, z, info); | |
283 | if(transferred){ | |
284 | rebalance_after_erasure(header2, z, info); | |
285 | rebalance_after_insertion(header1, z); | |
286 | } | |
287 | return transferred; | |
288 | } | |
289 | ||
290 | //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal | |
291 | template<class NodePtrCompare> | |
292 | static void transfer_equal | |
293 | (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z) | |
294 | { | |
295 | typename bstree_algo::data_for_rebalance info; | |
296 | bstree_algo::transfer_equal(header1, comp, header2, z, info); | |
297 | rebalance_after_erasure(header2, z, info); | |
298 | rebalance_after_insertion(header1, z); | |
299 | } | |
300 | ||
301 | //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) | |
302 | template <class Cloner, class Disposer> | |
303 | static void clone | |
304 | (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer) | |
305 | { | |
306 | avltree_node_cloner<NodeTraits, Cloner> new_cloner(cloner); | |
307 | bstree_algo::clone(source_header, target_header, new_cloner, disposer); | |
308 | } | |
309 | ||
310 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
311 | //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) | |
312 | template<class Disposer> | |
313 | static void clear_and_dispose(const node_ptr & header, Disposer disposer); | |
314 | ||
315 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
316 | template<class KeyType, class KeyNodePtrCompare> | |
317 | static node_ptr lower_bound | |
318 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
319 | ||
320 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
321 | template<class KeyType, class KeyNodePtrCompare> | |
322 | static node_ptr upper_bound | |
323 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
324 | ||
325 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
326 | template<class KeyType, class KeyNodePtrCompare> | |
327 | static node_ptr find | |
328 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
329 | ||
330 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
331 | template<class KeyType, class KeyNodePtrCompare> | |
332 | static std::pair<node_ptr, node_ptr> equal_range | |
333 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
334 | ||
335 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) | |
336 | template<class KeyType, class KeyNodePtrCompare> | |
337 | static std::pair<node_ptr, node_ptr> bounded_range | |
338 | (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp | |
339 | , bool left_closed, bool right_closed); | |
340 | ||
341 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
342 | template<class KeyType, class KeyNodePtrCompare> | |
343 | static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
344 | ||
345 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
346 | ||
347 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) | |
348 | template<class NodePtrCompare> | |
349 | static node_ptr insert_equal_upper_bound | |
350 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) | |
351 | { | |
352 | bstree_algo::insert_equal_upper_bound(h, new_node, comp); | |
353 | rebalance_after_insertion(h, new_node); | |
354 | return new_node; | |
355 | } | |
356 | ||
357 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) | |
358 | template<class NodePtrCompare> | |
359 | static node_ptr insert_equal_lower_bound | |
360 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) | |
361 | { | |
362 | bstree_algo::insert_equal_lower_bound(h, new_node, comp); | |
363 | rebalance_after_insertion(h, new_node); | |
364 | return new_node; | |
365 | } | |
366 | ||
367 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) | |
368 | template<class NodePtrCompare> | |
369 | static node_ptr insert_equal | |
370 | (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) | |
371 | { | |
372 | bstree_algo::insert_equal(header, hint, new_node, comp); | |
373 | rebalance_after_insertion(header, new_node); | |
374 | return new_node; | |
375 | } | |
376 | ||
377 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) | |
378 | static node_ptr insert_before | |
379 | (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node) | |
380 | { | |
381 | bstree_algo::insert_before(header, pos, new_node); | |
382 | rebalance_after_insertion(header, new_node); | |
383 | return new_node; | |
384 | } | |
385 | ||
386 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) | |
387 | static void push_back(const node_ptr & header, const node_ptr & new_node) | |
388 | { | |
389 | bstree_algo::push_back(header, new_node); | |
390 | rebalance_after_insertion(header, new_node); | |
391 | } | |
392 | ||
393 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) | |
394 | static void push_front(const node_ptr & header, const node_ptr & new_node) | |
395 | { | |
396 | bstree_algo::push_front(header, new_node); | |
397 | rebalance_after_insertion(header, new_node); | |
398 | } | |
399 | ||
400 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
401 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) | |
402 | template<class KeyType, class KeyNodePtrCompare> | |
403 | static std::pair<node_ptr, bool> insert_unique_check | |
404 | (const const_node_ptr & header, const KeyType &key | |
405 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data); | |
406 | ||
407 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) | |
408 | template<class KeyType, class KeyNodePtrCompare> | |
409 | static std::pair<node_ptr, bool> insert_unique_check | |
410 | (const const_node_ptr & header, const node_ptr &hint, const KeyType &key | |
411 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data); | |
412 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
413 | ||
414 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data &) | |
415 | static void insert_unique_commit | |
416 | (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data) | |
417 | { | |
418 | bstree_algo::insert_unique_commit(header, new_value, commit_data); | |
419 | rebalance_after_insertion(header, new_value); | |
420 | } | |
421 | ||
422 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header | |
423 | static bool is_header(const const_node_ptr & p) | |
424 | { return NodeTraits::get_balance(p) == NodeTraits::zero() && bstree_algo::is_header(p); } | |
425 | ||
426 | ||
427 | /// @cond | |
428 | static bool verify(const node_ptr &header) | |
429 | { | |
430 | std::size_t height; | |
431 | std::size_t count; | |
432 | return verify_recursion(NodeTraits::get_parent(header), count, height); | |
433 | } | |
434 | ||
435 | private: | |
436 | ||
437 | static bool verify_recursion(node_ptr n, std::size_t &count, std::size_t &height) | |
438 | { | |
439 | if (!n){ | |
440 | count = 0; | |
441 | height = 0; | |
442 | return true; | |
443 | } | |
444 | std::size_t leftcount, rightcount; | |
445 | std::size_t leftheight, rightheight; | |
446 | if(!verify_recursion(NodeTraits::get_left (n), leftcount, leftheight) || | |
447 | !verify_recursion(NodeTraits::get_right(n), rightcount, rightheight) ){ | |
448 | return false; | |
449 | } | |
450 | count = 1u + leftcount + rightcount; | |
451 | height = 1u + (leftheight > rightheight ? leftheight : rightheight); | |
452 | ||
453 | //If equal height, balance must be zero | |
454 | if(rightheight == leftheight){ | |
455 | if(NodeTraits::get_balance(n) != NodeTraits::zero()){ | |
456 | BOOST_ASSERT(0); | |
457 | return false; | |
458 | } | |
459 | } | |
460 | //If right is taller than left, then the difference must be at least 1 and the balance positive | |
461 | else if(rightheight > leftheight){ | |
462 | if(rightheight - leftheight > 1 ){ | |
463 | BOOST_ASSERT(0); | |
464 | return false; | |
465 | } | |
466 | else if(NodeTraits::get_balance(n) != NodeTraits::positive()){ | |
467 | BOOST_ASSERT(0); | |
468 | return false; | |
469 | } | |
470 | } | |
471 | //If left is taller than right, then the difference must be at least 1 and the balance negative | |
472 | else{ | |
473 | if(leftheight - rightheight > 1 ){ | |
474 | BOOST_ASSERT(0); | |
475 | return false; | |
476 | } | |
477 | else if(NodeTraits::get_balance(n) != NodeTraits::negative()){ | |
478 | BOOST_ASSERT(0); | |
479 | return false; | |
480 | } | |
481 | } | |
482 | return true; | |
483 | } | |
484 | ||
485 | static void rebalance_after_erasure | |
486 | ( const node_ptr & header, const node_ptr &z, const typename bstree_algo::data_for_rebalance &info) | |
487 | { | |
488 | if(info.y != z){ | |
489 | NodeTraits::set_balance(info.y, NodeTraits::get_balance(z)); | |
490 | } | |
491 | //Rebalance avltree | |
492 | rebalance_after_erasure_restore_invariants(header, info.x, info.x_parent); | |
493 | } | |
494 | ||
495 | static void rebalance_after_erasure_restore_invariants(const node_ptr & header, node_ptr x, node_ptr x_parent) | |
496 | { | |
497 | for ( node_ptr root = NodeTraits::get_parent(header) | |
498 | ; x != root | |
499 | ; root = NodeTraits::get_parent(header), x_parent = NodeTraits::get_parent(x)) { | |
500 | const balance x_parent_balance = NodeTraits::get_balance(x_parent); | |
501 | //Don't cache x_is_leftchild or similar because x can be null and | |
502 | //equal to both x_parent_left and x_parent_right | |
503 | const node_ptr x_parent_left (NodeTraits::get_left(x_parent)); | |
504 | const node_ptr x_parent_right(NodeTraits::get_right(x_parent)); | |
505 | ||
506 | if(x_parent_balance == NodeTraits::zero()){ | |
507 | NodeTraits::set_balance( x_parent, x == x_parent_right ? NodeTraits::negative() : NodeTraits::positive() ); | |
508 | break; // the height didn't change, let's stop here | |
509 | } | |
510 | else if(x_parent_balance == NodeTraits::negative()){ | |
511 | if (x == x_parent_left) { ////x is left child or x and sibling are null | |
512 | NodeTraits::set_balance(x_parent, NodeTraits::zero()); // balanced | |
513 | x = x_parent; | |
514 | } | |
515 | else { | |
516 | // x is right child (x_parent_left is the left child) | |
517 | BOOST_INTRUSIVE_INVARIANT_ASSERT(x_parent_left); | |
518 | if (NodeTraits::get_balance(x_parent_left) == NodeTraits::positive()) { | |
519 | // x_parent_left MUST have a right child | |
520 | BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(x_parent_left)); | |
521 | x = avl_rotate_left_right(x_parent, x_parent_left, header); | |
522 | } | |
523 | else { | |
524 | avl_rotate_right(x_parent, x_parent_left, header); | |
525 | x = x_parent_left; | |
526 | } | |
527 | ||
528 | // if changed from negative to NodeTraits::positive(), no need to check above | |
529 | if (NodeTraits::get_balance(x) == NodeTraits::positive()){ | |
530 | break; | |
531 | } | |
532 | } | |
533 | } | |
534 | else if(x_parent_balance == NodeTraits::positive()){ | |
535 | if (x == x_parent_right) { //x is right child or x and sibling are null | |
536 | NodeTraits::set_balance(x_parent, NodeTraits::zero()); // balanced | |
537 | x = x_parent; | |
538 | } | |
539 | else { | |
540 | // x is left child (x_parent_right is the right child) | |
541 | BOOST_INTRUSIVE_INVARIANT_ASSERT(x_parent_right); | |
542 | if (NodeTraits::get_balance(x_parent_right) == NodeTraits::negative()) { | |
543 | // x_parent_right MUST have then a left child | |
544 | BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(x_parent_right)); | |
545 | x = avl_rotate_right_left(x_parent, x_parent_right, header); | |
546 | } | |
547 | else { | |
548 | avl_rotate_left(x_parent, x_parent_right, header); | |
549 | x = x_parent_right; | |
550 | } | |
551 | // if changed from NodeTraits::positive() to negative, no need to check above | |
552 | if (NodeTraits::get_balance(x) == NodeTraits::negative()){ | |
553 | break; | |
554 | } | |
555 | } | |
556 | } | |
557 | else{ | |
558 | BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached | |
559 | } | |
560 | } | |
561 | } | |
562 | ||
563 | static void rebalance_after_insertion(const node_ptr & header, node_ptr x) | |
564 | { | |
565 | NodeTraits::set_balance(x, NodeTraits::zero()); | |
566 | // Rebalance. | |
567 | for(node_ptr root = NodeTraits::get_parent(header); x != root; root = NodeTraits::get_parent(header)){ | |
568 | node_ptr const x_parent(NodeTraits::get_parent(x)); | |
569 | node_ptr const x_parent_left(NodeTraits::get_left(x_parent)); | |
570 | const balance x_parent_balance = NodeTraits::get_balance(x_parent); | |
571 | const bool x_is_leftchild(x == x_parent_left); | |
572 | if(x_parent_balance == NodeTraits::zero()){ | |
573 | // if x is left, parent will have parent->bal_factor = negative | |
574 | // else, parent->bal_factor = NodeTraits::positive() | |
575 | NodeTraits::set_balance( x_parent, x_is_leftchild ? NodeTraits::negative() : NodeTraits::positive() ); | |
576 | x = x_parent; | |
577 | } | |
578 | else if(x_parent_balance == NodeTraits::positive()){ | |
579 | // if x is a left child, parent->bal_factor = zero | |
580 | if (x_is_leftchild) | |
581 | NodeTraits::set_balance(x_parent, NodeTraits::zero()); | |
582 | else{ // x is a right child, needs rebalancing | |
583 | if (NodeTraits::get_balance(x) == NodeTraits::negative()) | |
584 | avl_rotate_right_left(x_parent, x, header); | |
585 | else | |
586 | avl_rotate_left(x_parent, x, header); | |
587 | } | |
588 | break; | |
589 | } | |
590 | else if(x_parent_balance == NodeTraits::negative()){ | |
591 | // if x is a left child, needs rebalancing | |
592 | if (x_is_leftchild) { | |
593 | if (NodeTraits::get_balance(x) == NodeTraits::positive()) | |
594 | avl_rotate_left_right(x_parent, x, header); | |
595 | else | |
596 | avl_rotate_right(x_parent, x, header); | |
597 | } | |
598 | else | |
599 | NodeTraits::set_balance(x_parent, NodeTraits::zero()); | |
600 | break; | |
601 | } | |
602 | else{ | |
603 | BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached | |
604 | } | |
605 | } | |
606 | } | |
607 | ||
608 | static void left_right_balancing(const node_ptr & a, const node_ptr & b, const node_ptr & c) | |
609 | { | |
610 | // balancing... | |
611 | const balance c_balance = NodeTraits::get_balance(c); | |
612 | const balance zero_balance = NodeTraits::zero(); | |
613 | const balance posi_balance = NodeTraits::positive(); | |
614 | const balance nega_balance = NodeTraits::negative(); | |
615 | NodeTraits::set_balance(c, zero_balance); | |
616 | if(c_balance == nega_balance){ | |
617 | NodeTraits::set_balance(a, posi_balance); | |
618 | NodeTraits::set_balance(b, zero_balance); | |
619 | } | |
620 | else if(c_balance == zero_balance){ | |
621 | NodeTraits::set_balance(a, zero_balance); | |
622 | NodeTraits::set_balance(b, zero_balance); | |
623 | } | |
624 | else if(c_balance == posi_balance){ | |
625 | NodeTraits::set_balance(a, zero_balance); | |
626 | NodeTraits::set_balance(b, nega_balance); | |
627 | } | |
628 | else{ | |
629 | BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached | |
630 | } | |
631 | } | |
632 | ||
633 | static node_ptr avl_rotate_left_right(const node_ptr a, const node_ptr a_oldleft, const node_ptr & hdr) | |
634 | { // [note: 'a_oldleft' is 'b'] | |
635 | // | | // | |
636 | // a(-2) c // | |
637 | // / \ / \ // | |
638 | // / \ ==> / \ // | |
639 | // (pos)b [g] b a // | |
640 | // / \ / \ / \ // | |
641 | // [d] c [d] e f [g] // | |
642 | // / \ // | |
643 | // e f // | |
644 | const node_ptr c = NodeTraits::get_right(a_oldleft); | |
645 | bstree_algo::rotate_left_no_parent_fix(a_oldleft, c); | |
646 | //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_left(a, c)] | |
647 | //as c is not root and another rotation is coming | |
648 | bstree_algo::rotate_right(a, c, NodeTraits::get_parent(a), hdr); | |
649 | left_right_balancing(a, a_oldleft, c); | |
650 | return c; | |
651 | } | |
652 | ||
653 | static node_ptr avl_rotate_right_left(const node_ptr a, const node_ptr a_oldright, const node_ptr & hdr) | |
654 | { // [note: 'a_oldright' is 'b'] | |
655 | // | | // | |
656 | // a(pos) c // | |
657 | // / \ / \ // | |
658 | // / \ / \ // | |
659 | // [d] b(neg) ==> a b // | |
660 | // / \ / \ / \ // | |
661 | // c [g] [d] e f [g] // | |
662 | // / \ // | |
663 | // e f // | |
664 | const node_ptr c (NodeTraits::get_left(a_oldright)); | |
665 | bstree_algo::rotate_right_no_parent_fix(a_oldright, c); | |
666 | //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_right(a, c)] | |
667 | //as c is not root and another rotation is coming. | |
668 | bstree_algo::rotate_left(a, c, NodeTraits::get_parent(a), hdr); | |
669 | left_right_balancing(a_oldright, a, c); | |
670 | return c; | |
671 | } | |
672 | ||
673 | static void avl_rotate_left(const node_ptr &x, const node_ptr &x_oldright, const node_ptr & hdr) | |
674 | { | |
675 | bstree_algo::rotate_left(x, x_oldright, NodeTraits::get_parent(x), hdr); | |
676 | ||
677 | // reset the balancing factor | |
678 | if (NodeTraits::get_balance(x_oldright) == NodeTraits::positive()) { | |
679 | NodeTraits::set_balance(x, NodeTraits::zero()); | |
680 | NodeTraits::set_balance(x_oldright, NodeTraits::zero()); | |
681 | } | |
682 | else { // this doesn't happen during insertions | |
683 | NodeTraits::set_balance(x, NodeTraits::positive()); | |
684 | NodeTraits::set_balance(x_oldright, NodeTraits::negative()); | |
685 | } | |
686 | } | |
687 | ||
688 | static void avl_rotate_right(const node_ptr &x, const node_ptr &x_oldleft, const node_ptr & hdr) | |
689 | { | |
690 | bstree_algo::rotate_right(x, x_oldleft, NodeTraits::get_parent(x), hdr); | |
691 | ||
692 | // reset the balancing factor | |
693 | if (NodeTraits::get_balance(x_oldleft) == NodeTraits::negative()) { | |
694 | NodeTraits::set_balance(x, NodeTraits::zero()); | |
695 | NodeTraits::set_balance(x_oldleft, NodeTraits::zero()); | |
696 | } | |
697 | else { // this doesn't happen during insertions | |
698 | NodeTraits::set_balance(x, NodeTraits::negative()); | |
699 | NodeTraits::set_balance(x_oldleft, NodeTraits::positive()); | |
700 | } | |
701 | } | |
702 | ||
703 | /// @endcond | |
704 | }; | |
705 | ||
706 | /// @cond | |
707 | ||
708 | template<class NodeTraits> | |
709 | struct get_algo<AvlTreeAlgorithms, NodeTraits> | |
710 | { | |
711 | typedef avltree_algorithms<NodeTraits> type; | |
712 | }; | |
713 | ||
714 | template <class ValueTraits, class NodePtrCompare, class ExtraChecker> | |
715 | struct get_node_checker<AvlTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> | |
716 | { | |
717 | typedef detail::avltree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; | |
718 | }; | |
719 | ||
720 | /// @endcond | |
721 | ||
722 | } //namespace intrusive | |
723 | } //namespace boost | |
724 | ||
725 | #include <boost/intrusive/detail/config_end.hpp> | |
726 | ||
727 | #endif //BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP |