1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Ion Gaztanaga 2007-2014 |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. |
6 | // (See accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | // |
9 | // See http://www.boost.org/libs/intrusive for documentation. |
10 | // |
11 | ///////////////////////////////////////////////////////////////////////////// |
12 | // The implementation of splay trees is based on the article and code published |
13 | // in C++ Users Journal "Implementing Splay Trees in C++" (September 1, 2005). |
14 | // |
15 | // The splay code has been modified and (supposedly) improved by Ion Gaztanaga. |
16 | // |
17 | // Here is the copyright notice of the original file containing the splay code: |
18 | // |
19 | // splay_tree.h -- implementation of a STL compatible splay tree. |
20 | // |
21 | // Copyright (c) 2004 Ralf Mattethat |
22 | // |
23 | // Permission to copy, use, modify, sell and distribute this software |
24 | // is granted provided this copyright notice appears in all copies. |
25 | // This software is provided "as is" without express or implied |
26 | // warranty, and with no claim as to its suitability for any purpose. |
27 | // |
28 | ///////////////////////////////////////////////////////////////////////////// |
29 | |
30 | #ifndef BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP |
31 | #define BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP |
32 | |
33 | #include <boost/intrusive/detail/config_begin.hpp> |
34 | #include <boost/intrusive/intrusive_fwd.hpp> |
35 | #include <boost/intrusive/detail/assert.hpp> |
36 | #include <boost/intrusive/detail/algo_type.hpp> |
37 | #include <boost/intrusive/detail/uncast.hpp> |
38 | #include <boost/intrusive/bstree_algorithms.hpp> |
39 | |
40 | #include <cstddef> |
41 | |
42 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
43 | # pragma once |
44 | #endif |
45 | |
46 | namespace boost { |
47 | namespace intrusive { |
48 | |
49 | /// @cond |
50 | namespace detail { |
51 | |
52 | template<class NodeTraits> |
53 | struct splaydown_assemble_and_fix_header |
54 | { |
55 | typedef typename NodeTraits::node_ptr node_ptr; |
56 | |
57 | splaydown_assemble_and_fix_header(const node_ptr & t, const node_ptr & , const node_ptr &leftmost, const node_ptr &rightmost) |
58 | : t_(t) |
59 | , null_node_(header) |
60 | , l_(null_node_) |
61 | , r_(null_node_) |
62 | , leftmost_(leftmost) |
63 | , rightmost_(rightmost) |
64 | {} |
65 | |
66 | ~splaydown_assemble_and_fix_header() |
67 | { |
68 | this->assemble(); |
69 | |
70 | //Now recover the original header except for the |
71 | //splayed root node. |
72 | //"t_" is the current root and "null_node_" is the header node |
73 | NodeTraits::set_parent(null_node_, t_); |
74 | NodeTraits::set_parent(t_, null_node_); |
75 | //Recover leftmost/rightmost pointers |
76 | NodeTraits::set_left (null_node_, leftmost_); |
77 | NodeTraits::set_right(null_node_, rightmost_); |
78 | } |
79 | |
80 | private: |
81 | |
82 | void assemble() |
83 | { |
84 | //procedure assemble; |
85 | // left(r), right(l) := right(t), left(t); |
86 | // left(t), right(t) := right(null), left(null); |
87 | //end assemble; |
88 | { // left(r), right(l) := right(t), left(t); |
89 | |
90 | node_ptr const old_t_left = NodeTraits::get_left(t_); |
91 | node_ptr const old_t_right = NodeTraits::get_right(t_); |
92 | NodeTraits::set_right(l_, old_t_left); |
93 | NodeTraits::set_left (r_, old_t_right); |
94 | if(old_t_left){ |
95 | NodeTraits::set_parent(old_t_left, l_); |
96 | } |
97 | if(old_t_right){ |
98 | NodeTraits::set_parent(old_t_right, r_); |
99 | } |
100 | } |
101 | { // left(t), right(t) := right(null), left(null); |
102 | node_ptr const null_right = NodeTraits::get_right(null_node_); |
103 | node_ptr const null_left = NodeTraits::get_left(null_node_); |
104 | NodeTraits::set_left (t_, null_right); |
105 | NodeTraits::set_right(t_, null_left); |
106 | if(null_right){ |
107 | NodeTraits::set_parent(null_right, t_); |
108 | } |
109 | if(null_left){ |
110 | NodeTraits::set_parent(null_left, t_); |
111 | } |
112 | } |
113 | } |
114 | |
115 | public: |
116 | node_ptr t_, null_node_, l_, r_, leftmost_, rightmost_; |
117 | }; |
118 | |
119 | } //namespace detail { |
120 | /// @endcond |
121 | |
122 | //! A splay tree is an implementation of a binary search tree. The tree is |
123 | //! self balancing using the splay algorithm as described in |
124 | //! |
125 | //! "Self-Adjusting Binary Search Trees |
126 | //! by Daniel Dominic Sleator and Robert Endre Tarjan |
127 | //! AT&T Bell Laboratories, Murray Hill, NJ |
128 | //! Journal of the ACM, Vol 32, no 3, July 1985, pp 652-686 |
129 | //! |
130 | //! splaytree_algorithms is configured with a NodeTraits class, which encapsulates the |
131 | //! information about the node to be manipulated. NodeTraits must support the |
132 | //! following interface: |
133 | //! |
134 | //! <b>Typedefs</b>: |
135 | //! |
136 | //! <tt>node</tt>: The type of the node that forms the binary search tree |
137 | //! |
138 | //! <tt>node_ptr</tt>: A pointer to a node |
139 | //! |
140 | //! <tt>const_node_ptr</tt>: A pointer to a const node |
141 | //! |
142 | //! <b>Static functions</b>: |
143 | //! |
144 | //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> |
145 | //! |
146 | //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> |
147 | //! |
148 | //! <tt>static node_ptr get_left(const_node_ptr n);</tt> |
149 | //! |
150 | //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> |
151 | //! |
152 | //! <tt>static node_ptr get_right(const_node_ptr n);</tt> |
153 | //! |
154 | //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> |
155 | template<class NodeTraits> |
156 | class splaytree_algorithms |
157 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
158 | : public bstree_algorithms<NodeTraits> |
159 | #endif |
160 | { |
161 | /// @cond |
162 | private: |
163 | typedef bstree_algorithms<NodeTraits> bstree_algo; |
164 | /// @endcond |
165 | |
166 | public: |
167 | typedef typename NodeTraits::node node; |
168 | typedef NodeTraits node_traits; |
169 | typedef typename NodeTraits::node_ptr node_ptr; |
170 | typedef typename NodeTraits::const_node_ptr const_node_ptr; |
171 | |
172 | //! This type is the information that will be |
173 | //! filled by insert_unique_check |
174 | typedef typename bstree_algo::insert_commit_data insert_commit_data; |
175 | |
176 | public: |
177 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
178 | //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) |
179 | static node_ptr get_header(const const_node_ptr & n); |
180 | |
181 | //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node |
182 | static node_ptr begin_node(const const_node_ptr & header); |
183 | |
184 | //! @copydoc ::boost::intrusive::bstree_algorithms::end_node |
185 | static node_ptr end_node(const const_node_ptr & header); |
186 | |
187 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree |
188 | static void swap_tree(const node_ptr & header1, const node_ptr & header2); |
189 | |
190 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) |
191 | static void swap_nodes(const node_ptr & node1, const node_ptr & node2); |
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 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) |
197 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node); |
198 | |
199 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) |
200 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node); |
201 | |
202 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&) |
203 | static void unlink(const node_ptr & node); |
204 | |
205 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance |
206 | static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); |
207 | |
208 | //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) |
209 | static bool unique(const const_node_ptr & node); |
210 | |
211 | //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) |
212 | static std::size_t size(const const_node_ptr & header); |
213 | |
214 | //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) |
215 | static node_ptr next_node(const node_ptr & node); |
216 | |
217 | //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) |
218 | static node_ptr prev_node(const node_ptr & node); |
219 | |
220 | //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) |
221 | static void init(const node_ptr & node); |
222 | |
223 | //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&) |
224 | static void init_header(const node_ptr & header); |
225 | |
226 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
227 | |
228 | //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) |
229 | //! Additional notes: the previous node of z is splayed to speed up range deletions. |
230 | static void erase(const node_ptr & , const node_ptr & z) |
231 | { |
232 | //posibility 1 |
233 | if(NodeTraits::get_left(z)){ |
234 | splay_up(node: bstree_algo::prev_node(z), header); |
235 | } |
236 | |
237 | //possibility 2 |
238 | //if(NodeTraits::get_left(z)){ |
239 | // node_ptr l = NodeTraits::get_left(z); |
240 | // splay_up(l, header); |
241 | //} |
242 | |
243 | //if(NodeTraits::get_left(z)){ |
244 | // node_ptr l = bstree_algo::prev_node(z); |
245 | // splay_up_impl(l, z); |
246 | //} |
247 | |
248 | //possibility 4 |
249 | //splay_up(z, header); |
250 | |
251 | bstree_algo::erase(header, z); |
252 | } |
253 | |
254 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
255 | //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) |
256 | template <class Cloner, class Disposer> |
257 | static void clone |
258 | (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer); |
259 | |
260 | //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) |
261 | template<class Disposer> |
262 | static void clear_and_dispose(const node_ptr & header, Disposer disposer); |
263 | |
264 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
265 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
266 | //! Additional notes: an element with key `key` is splayed. |
267 | template<class KeyType, class KeyNodePtrCompare> |
268 | static std::size_t count |
269 | (const node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
270 | { |
271 | std::pair<node_ptr, node_ptr> ret = equal_range(header, key, comp); |
272 | std::size_t n = 0; |
273 | while(ret.first != ret.second){ |
274 | ++n; |
275 | ret.first = next_node(ret.first); |
276 | } |
277 | return n; |
278 | } |
279 | |
280 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
281 | //! Additional note: no splaying is performed |
282 | template<class KeyType, class KeyNodePtrCompare> |
283 | static std::size_t count |
284 | (const const_node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
285 | { return bstree_algo::count(header, key, comp); } |
286 | |
287 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
288 | //! Additional notes: the first node of the range is splayed. |
289 | template<class KeyType, class KeyNodePtrCompare> |
290 | static node_ptr lower_bound |
291 | (const node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
292 | { |
293 | splay_down(detail::uncast(header), key, comp); |
294 | node_ptr y = bstree_algo::lower_bound(header, key, comp); |
295 | //splay_up(y, detail::uncast(header)); |
296 | return y; |
297 | } |
298 | |
299 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
300 | //! Additional note: no splaying is performed |
301 | template<class KeyType, class KeyNodePtrCompare> |
302 | static node_ptr lower_bound |
303 | (const const_node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
304 | { return bstree_algo::lower_bound(header, key, comp); } |
305 | |
306 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
307 | //! Additional notes: the first node of the range is splayed. |
308 | template<class KeyType, class KeyNodePtrCompare> |
309 | static node_ptr upper_bound |
310 | (const node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
311 | { |
312 | splay_down(detail::uncast(header), key, comp); |
313 | node_ptr y = bstree_algo::upper_bound(header, key, comp); |
314 | //splay_up(y, detail::uncast(header)); |
315 | return y; |
316 | } |
317 | |
318 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
319 | //! Additional note: no splaying is performed |
320 | template<class KeyType, class KeyNodePtrCompare> |
321 | static node_ptr upper_bound |
322 | (const const_node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
323 | { return bstree_algo::upper_bound(header, key, comp); } |
324 | |
325 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) |
326 | //! Additional notes: the found node of the lower bound is splayed. |
327 | template<class KeyType, class KeyNodePtrCompare> |
328 | static node_ptr find |
329 | (const node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
330 | { |
331 | splay_down(detail::uncast(header), key, comp); |
332 | return bstree_algo::find(header, key, comp); |
333 | } |
334 | |
335 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) |
336 | //! Additional note: no splaying is performed |
337 | template<class KeyType, class KeyNodePtrCompare> |
338 | static node_ptr find |
339 | (const const_node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
340 | { return bstree_algo::find(header, key, comp); } |
341 | |
342 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
343 | //! Additional notes: the first node of the range is splayed. |
344 | template<class KeyType, class KeyNodePtrCompare> |
345 | static std::pair<node_ptr, node_ptr> equal_range |
346 | (const node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
347 | { |
348 | splay_down(detail::uncast(header), key, comp); |
349 | std::pair<node_ptr, node_ptr> ret = bstree_algo::equal_range(header, key, comp); |
350 | //splay_up(ret.first, detail::uncast(header)); |
351 | return ret; |
352 | } |
353 | |
354 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
355 | //! Additional note: no splaying is performed |
356 | template<class KeyType, class KeyNodePtrCompare> |
357 | static std::pair<node_ptr, node_ptr> equal_range |
358 | (const const_node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
359 | { return bstree_algo::equal_range(header, key, comp); } |
360 | |
361 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
362 | //! Additional notes: the first node of the range is splayed. |
363 | template<class KeyType, class KeyNodePtrCompare> |
364 | static std::pair<node_ptr, node_ptr> lower_bound_range |
365 | (const node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
366 | { |
367 | splay_down(detail::uncast(header), key, comp); |
368 | std::pair<node_ptr, node_ptr> ret = bstree_algo::lower_bound_range(header, key, comp); |
369 | //splay_up(ret.first, detail::uncast(header)); |
370 | return ret; |
371 | } |
372 | |
373 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
374 | //! Additional note: no splaying is performed |
375 | template<class KeyType, class KeyNodePtrCompare> |
376 | static std::pair<node_ptr, node_ptr> lower_bound_range |
377 | (const const_node_ptr & , const KeyType &key, KeyNodePtrCompare comp) |
378 | { return bstree_algo::lower_bound_range(header, key, comp); } |
379 | |
380 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) |
381 | //! Additional notes: the first node of the range is splayed. |
382 | template<class KeyType, class KeyNodePtrCompare> |
383 | static std::pair<node_ptr, node_ptr> bounded_range |
384 | (const node_ptr & , const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp |
385 | , bool left_closed, bool right_closed) |
386 | { |
387 | splay_down(detail::uncast(header), lower_key, comp); |
388 | std::pair<node_ptr, node_ptr> ret = |
389 | bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); |
390 | //splay_up(ret.first, detail::uncast(header)); |
391 | return ret; |
392 | } |
393 | |
394 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) |
395 | //! Additional note: no splaying is performed |
396 | template<class KeyType, class KeyNodePtrCompare> |
397 | static std::pair<node_ptr, node_ptr> bounded_range |
398 | (const const_node_ptr & , const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp |
399 | , bool left_closed, bool right_closed) |
400 | { return bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); } |
401 | |
402 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) |
403 | //! Additional note: the inserted node is splayed |
404 | template<class NodePtrCompare> |
405 | static node_ptr insert_equal_upper_bound |
406 | (const node_ptr & , const node_ptr & new_node, NodePtrCompare comp) |
407 | { |
408 | splay_down(header, new_node, comp); |
409 | return bstree_algo::insert_equal_upper_bound(header, new_node, comp); |
410 | } |
411 | |
412 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) |
413 | //! Additional note: the inserted node is splayed |
414 | template<class NodePtrCompare> |
415 | static node_ptr insert_equal_lower_bound |
416 | (const node_ptr & , const node_ptr & new_node, NodePtrCompare comp) |
417 | { |
418 | splay_down(header, new_node, comp); |
419 | return bstree_algo::insert_equal_lower_bound(header, new_node, comp); |
420 | } |
421 | |
422 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) |
423 | //! Additional note: the inserted node is splayed |
424 | template<class NodePtrCompare> |
425 | static node_ptr insert_equal |
426 | (const node_ptr & , const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) |
427 | { |
428 | splay_down(header, new_node, comp); |
429 | return bstree_algo::insert_equal(header, hint, new_node, comp); |
430 | } |
431 | |
432 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) |
433 | //! Additional note: the inserted node is splayed |
434 | static node_ptr insert_before |
435 | (const node_ptr & , const node_ptr & pos, const node_ptr & new_node) |
436 | { |
437 | bstree_algo::insert_before(header, pos, new_node); |
438 | splay_up(node: new_node, header); |
439 | return new_node; |
440 | } |
441 | |
442 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) |
443 | //! Additional note: the inserted node is splayed |
444 | static void push_back(const node_ptr & , const node_ptr & new_node) |
445 | { |
446 | bstree_algo::push_back(header, new_node); |
447 | splay_up(node: new_node, header); |
448 | } |
449 | |
450 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) |
451 | //! Additional note: the inserted node is splayed |
452 | static void push_front(const node_ptr & , const node_ptr & new_node) |
453 | { |
454 | bstree_algo::push_front(header, new_node); |
455 | splay_up(node: new_node, header); |
456 | } |
457 | |
458 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) |
459 | //! Additional note: nodes with the given key are splayed |
460 | template<class KeyType, class KeyNodePtrCompare> |
461 | static std::pair<node_ptr, bool> insert_unique_check |
462 | (const node_ptr & , const KeyType &key |
463 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data) |
464 | { |
465 | splay_down(header, key, comp); |
466 | return bstree_algo::insert_unique_check(header, key, comp, commit_data); |
467 | } |
468 | |
469 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) |
470 | //! Additional note: nodes with the given key are splayed |
471 | template<class KeyType, class KeyNodePtrCompare> |
472 | static std::pair<node_ptr, bool> insert_unique_check |
473 | (const node_ptr & , const node_ptr &hint, const KeyType &key |
474 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data) |
475 | { |
476 | splay_down(header, key, comp); |
477 | return bstree_algo::insert_unique_check(header, hint, key, comp, commit_data); |
478 | } |
479 | |
480 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
481 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) |
482 | static void insert_unique_commit |
483 | (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data); |
484 | |
485 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header |
486 | static bool is_header(const const_node_ptr & p); |
487 | |
488 | //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance |
489 | static void rebalance(const node_ptr & header); |
490 | |
491 | //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance_subtree |
492 | static node_ptr rebalance_subtree(const node_ptr & old_root); |
493 | |
494 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
495 | |
496 | // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow |
497 | static void splay_up(const node_ptr & node, const node_ptr & ) |
498 | { priv_splay_up<true>(node, header); } |
499 | |
500 | // top-down splay | complexity : logarithmic | exception : strong, note A |
501 | template<class KeyType, class KeyNodePtrCompare> |
502 | static node_ptr splay_down(const node_ptr & , const KeyType &key, KeyNodePtrCompare comp, bool *pfound = 0) |
503 | { return priv_splay_down<true>(header, key, comp, pfound); } |
504 | |
505 | private: |
506 | |
507 | /// @cond |
508 | |
509 | // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow |
510 | template<bool SimpleSplay> |
511 | static void priv_splay_up(const node_ptr & node, const node_ptr & ) |
512 | { |
513 | // If (node == header) do a splay for the right most node instead |
514 | // this is to boost performance of equal_range/count on equivalent containers in the case |
515 | // where there are many equal elements at the end |
516 | node_ptr n((node == header) ? NodeTraits::get_right(header) : node); |
517 | node_ptr t(header); |
518 | |
519 | if( n == t ) return; |
520 | |
521 | for( ;; ){ |
522 | node_ptr p(NodeTraits::get_parent(n)); |
523 | node_ptr g(NodeTraits::get_parent(p)); |
524 | |
525 | if( p == t ) break; |
526 | |
527 | if( g == t ){ |
528 | // zig |
529 | rotate(n); |
530 | } |
531 | else if ((NodeTraits::get_left(p) == n && NodeTraits::get_left(g) == p) || |
532 | (NodeTraits::get_right(p) == n && NodeTraits::get_right(g) == p) ){ |
533 | // zig-zig |
534 | rotate(n: p); |
535 | rotate(n); |
536 | } |
537 | else { |
538 | // zig-zag |
539 | rotate(n); |
540 | if(!SimpleSplay){ |
541 | rotate(n); |
542 | } |
543 | } |
544 | } |
545 | } |
546 | |
547 | template<bool SimpleSplay, class KeyType, class KeyNodePtrCompare> |
548 | static node_ptr priv_splay_down(const node_ptr & , const KeyType &key, KeyNodePtrCompare comp, bool *pfound = 0) |
549 | { |
550 | //Most splay tree implementations use a dummy/null node to implement. |
551 | //this function. This has some problems for a generic library like Intrusive: |
552 | // |
553 | // * The node might not have a default constructor. |
554 | // * The default constructor could throw. |
555 | // |
556 | //We already have a header node. Leftmost and rightmost nodes of the tree |
557 | //are not changed when splaying (because the invariants of the tree don't |
558 | //change) We can back up them, use the header as the null node and |
559 | //reassign old values after the function has been completed. |
560 | node_ptr const old_root = NodeTraits::get_parent(header); |
561 | node_ptr const leftmost = NodeTraits::get_left(header); |
562 | node_ptr const rightmost = NodeTraits::get_right(header); |
563 | if(leftmost == rightmost){ //Empty or unique node |
564 | if(pfound){ |
565 | *pfound = old_root && !comp(key, old_root) && !comp(old_root, key); |
566 | } |
567 | return old_root ? old_root : header; |
568 | } |
569 | else{ |
570 | //Initialize "null node" (the header in our case) |
571 | NodeTraits::set_left (header, node_ptr()); |
572 | NodeTraits::set_right(header, node_ptr()); |
573 | //Class that will backup leftmost/rightmost from header, commit the assemble(), |
574 | //and will restore leftmost/rightmost to header even if "comp" throws |
575 | detail::splaydown_assemble_and_fix_header<NodeTraits> commit(old_root, header, leftmost, rightmost); |
576 | bool found = false; |
577 | |
578 | for( ;; ){ |
579 | if(comp(key, commit.t_)){ |
580 | node_ptr const t_left = NodeTraits::get_left(commit.t_); |
581 | if(!t_left) |
582 | break; |
583 | if(comp(key, t_left)){ |
584 | bstree_algo::rotate_right_no_parent_fix(commit.t_, t_left); |
585 | commit.t_ = t_left; |
586 | if( !NodeTraits::get_left(commit.t_) ) |
587 | break; |
588 | link_right(t&: commit.t_, r&: commit.r_); |
589 | } |
590 | else{ |
591 | link_right(t&: commit.t_, r&: commit.r_); |
592 | if(!SimpleSplay && comp(t_left, key)){ |
593 | if( !NodeTraits::get_right(commit.t_) ) |
594 | break; |
595 | link_left(t&: commit.t_, l&: commit.l_); |
596 | } |
597 | } |
598 | } |
599 | else if(comp(commit.t_, key)){ |
600 | node_ptr const t_right = NodeTraits::get_right(commit.t_); |
601 | if(!t_right) |
602 | break; |
603 | |
604 | if(comp(t_right, key)){ |
605 | bstree_algo::rotate_left_no_parent_fix(commit.t_, t_right); |
606 | commit.t_ = t_right; |
607 | if( !NodeTraits::get_right(commit.t_) ) |
608 | break; |
609 | link_left(t&: commit.t_, l&: commit.l_); |
610 | } |
611 | else{ |
612 | link_left(t&: commit.t_, l&: commit.l_); |
613 | if(!SimpleSplay && comp(key, t_right)){ |
614 | if( !NodeTraits::get_left(commit.t_) ) |
615 | break; |
616 | link_right(t&: commit.t_, r&: commit.r_); |
617 | } |
618 | } |
619 | } |
620 | else{ |
621 | found = true; |
622 | break; |
623 | } |
624 | } |
625 | |
626 | //commit.~splaydown_assemble_and_fix_header<NodeTraits>() will first |
627 | //"assemble()" + link the new root & recover header's leftmost & rightmost |
628 | if(pfound){ |
629 | *pfound = found; |
630 | } |
631 | return commit.t_; |
632 | } |
633 | } |
634 | |
635 | // break link to left child node and attach it to left tree pointed to by l | complexity : constant | exception : nothrow |
636 | static void link_left(node_ptr & t, node_ptr & l) |
637 | { |
638 | //procedure link_left; |
639 | // t, l, right(l) := right(t), t, t |
640 | //end link_left |
641 | NodeTraits::set_right(l, t); |
642 | NodeTraits::set_parent(t, l); |
643 | l = t; |
644 | t = NodeTraits::get_right(t); |
645 | } |
646 | |
647 | // break link to right child node and attach it to right tree pointed to by r | complexity : constant | exception : nothrow |
648 | static void link_right(node_ptr & t, node_ptr & r) |
649 | { |
650 | //procedure link_right; |
651 | // t, r, left(r) := left(t), t, t |
652 | //end link_right; |
653 | NodeTraits::set_left(r, t); |
654 | NodeTraits::set_parent(t, r); |
655 | r = t; |
656 | t = NodeTraits::get_left(t); |
657 | } |
658 | |
659 | // rotate n with its parent | complexity : constant | exception : nothrow |
660 | static void rotate(const node_ptr & n) |
661 | { |
662 | //procedure rotate_left; |
663 | // t, right(t), left(right(t)) := right(t), left(right(t)), t |
664 | //end rotate_left; |
665 | node_ptr p = NodeTraits::get_parent(n); |
666 | node_ptr g = NodeTraits::get_parent(p); |
667 | //Test if g is header before breaking tree |
668 | //invariants that would make is_header invalid |
669 | bool = bstree_algo::is_header(g); |
670 | |
671 | if(NodeTraits::get_left(p) == n){ |
672 | NodeTraits::set_left(p, NodeTraits::get_right(n)); |
673 | if(NodeTraits::get_left(p)) |
674 | NodeTraits::set_parent(NodeTraits::get_left(p), p); |
675 | NodeTraits::set_right(n, p); |
676 | } |
677 | else{ // must be ( p->right == n ) |
678 | NodeTraits::set_right(p, NodeTraits::get_left(n)); |
679 | if(NodeTraits::get_right(p)) |
680 | NodeTraits::set_parent(NodeTraits::get_right(p), p); |
681 | NodeTraits::set_left(n, p); |
682 | } |
683 | |
684 | NodeTraits::set_parent(p, n); |
685 | NodeTraits::set_parent(n, g); |
686 | |
687 | if(g_is_header){ |
688 | if(NodeTraits::get_parent(g) == p) |
689 | NodeTraits::set_parent(g, n); |
690 | else{//must be ( g->right == p ) |
691 | BOOST_INTRUSIVE_INVARIANT_ASSERT(false); |
692 | NodeTraits::set_right(g, n); |
693 | } |
694 | } |
695 | else{ |
696 | if(NodeTraits::get_left(g) == p) |
697 | NodeTraits::set_left(g, n); |
698 | else //must be ( g->right == p ) |
699 | NodeTraits::set_right(g, n); |
700 | } |
701 | } |
702 | |
703 | /// @endcond |
704 | }; |
705 | |
706 | /// @cond |
707 | |
708 | template<class NodeTraits> |
709 | struct get_algo<SplayTreeAlgorithms, NodeTraits> |
710 | { |
711 | typedef splaytree_algorithms<NodeTraits> type; |
712 | }; |
713 | |
714 | template <class ValueTraits, class NodePtrCompare, class ExtraChecker> |
715 | struct get_node_checker<SplayTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> |
716 | { |
717 | typedef detail::bstree_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_SPLAYTREE_ALGORITHMS_HPP |
728 | |