]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 & header, 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 & header, const node_ptr & z) | |
231 | { | |
232 | //posibility 1 | |
233 | if(NodeTraits::get_left(z)){ | |
234 | splay_up(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 | //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique | |
255 | template<class NodePtrCompare> | |
256 | static bool transfer_unique | |
257 | (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z) | |
258 | { | |
259 | typename bstree_algo::insert_commit_data commit_data; | |
260 | bool const transferable = bstree_algo::insert_unique_check(header1, z, comp, commit_data).second; | |
261 | if(transferable){ | |
262 | erase(header2, z); | |
263 | bstree_algo::insert_commit(header1, z, commit_data); | |
264 | splay_up(z, header1); | |
265 | } | |
266 | return transferable; | |
267 | } | |
268 | ||
269 | //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal | |
270 | template<class NodePtrCompare> | |
271 | static void transfer_equal | |
272 | (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z) | |
273 | { | |
274 | insert_commit_data commit_data; | |
275 | splay_down(header1, z, comp); | |
276 | bstree_algo::insert_equal_upper_bound_check(header1, z, comp, commit_data); | |
277 | erase(header2, z); | |
278 | bstree_algo::insert_commit(header1, z, commit_data); | |
279 | } | |
280 | ||
281 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
282 | //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) | |
283 | template <class Cloner, class Disposer> | |
284 | static void clone | |
285 | (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer); | |
286 | ||
287 | //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) | |
288 | template<class Disposer> | |
289 | static void clear_and_dispose(const node_ptr & header, Disposer disposer); | |
290 | ||
291 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
292 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
293 | //! Additional notes: an element with key `key` is splayed. | |
294 | template<class KeyType, class KeyNodePtrCompare> | |
295 | static std::size_t count | |
296 | (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
297 | { | |
298 | std::pair<node_ptr, node_ptr> ret = equal_range(header, key, comp); | |
299 | std::size_t n = 0; | |
300 | while(ret.first != ret.second){ | |
301 | ++n; | |
302 | ret.first = next_node(ret.first); | |
303 | } | |
304 | return n; | |
305 | } | |
306 | ||
307 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
308 | //! Additional note: no splaying is performed | |
309 | template<class KeyType, class KeyNodePtrCompare> | |
310 | static std::size_t count | |
311 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
312 | { return bstree_algo::count(header, key, comp); } | |
313 | ||
314 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
315 | //! Additional notes: the first node of the range is splayed. | |
316 | template<class KeyType, class KeyNodePtrCompare> | |
317 | static node_ptr lower_bound | |
318 | (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
319 | { | |
320 | splay_down(detail::uncast(header), key, comp); | |
321 | node_ptr y = bstree_algo::lower_bound(header, key, comp); | |
322 | //splay_up(y, detail::uncast(header)); | |
323 | return y; | |
324 | } | |
325 | ||
326 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
327 | //! Additional note: no splaying is performed | |
328 | template<class KeyType, class KeyNodePtrCompare> | |
329 | static node_ptr lower_bound | |
330 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
331 | { return bstree_algo::lower_bound(header, key, comp); } | |
332 | ||
333 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
334 | //! Additional notes: the first node of the range is splayed. | |
335 | template<class KeyType, class KeyNodePtrCompare> | |
336 | static node_ptr upper_bound | |
337 | (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
338 | { | |
339 | splay_down(detail::uncast(header), key, comp); | |
340 | node_ptr y = bstree_algo::upper_bound(header, key, comp); | |
341 | //splay_up(y, detail::uncast(header)); | |
342 | return y; | |
343 | } | |
344 | ||
345 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
346 | //! Additional note: no splaying is performed | |
347 | template<class KeyType, class KeyNodePtrCompare> | |
348 | static node_ptr upper_bound | |
349 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
350 | { return bstree_algo::upper_bound(header, key, comp); } | |
351 | ||
352 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) | |
353 | //! Additional notes: the found node of the lower bound is splayed. | |
354 | template<class KeyType, class KeyNodePtrCompare> | |
355 | static node_ptr find | |
356 | (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
357 | { | |
358 | splay_down(detail::uncast(header), key, comp); | |
359 | return bstree_algo::find(header, key, comp); | |
360 | } | |
361 | ||
362 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) | |
363 | //! Additional note: no splaying is performed | |
364 | template<class KeyType, class KeyNodePtrCompare> | |
365 | static node_ptr find | |
366 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
367 | { return bstree_algo::find(header, key, comp); } | |
368 | ||
369 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
370 | //! Additional notes: the first node of the range is splayed. | |
371 | template<class KeyType, class KeyNodePtrCompare> | |
372 | static std::pair<node_ptr, node_ptr> equal_range | |
373 | (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
374 | { | |
375 | splay_down(detail::uncast(header), key, comp); | |
376 | std::pair<node_ptr, node_ptr> ret = bstree_algo::equal_range(header, key, comp); | |
377 | //splay_up(ret.first, detail::uncast(header)); | |
378 | return ret; | |
379 | } | |
380 | ||
381 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
382 | //! Additional note: no splaying is performed | |
383 | template<class KeyType, class KeyNodePtrCompare> | |
384 | static std::pair<node_ptr, node_ptr> equal_range | |
385 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
386 | { return bstree_algo::equal_range(header, key, comp); } | |
387 | ||
388 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
389 | //! Additional notes: the first node of the range is splayed. | |
390 | template<class KeyType, class KeyNodePtrCompare> | |
391 | static std::pair<node_ptr, node_ptr> lower_bound_range | |
392 | (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
393 | { | |
394 | splay_down(detail::uncast(header), key, comp); | |
395 | std::pair<node_ptr, node_ptr> ret = bstree_algo::lower_bound_range(header, key, comp); | |
396 | //splay_up(ret.first, detail::uncast(header)); | |
397 | return ret; | |
398 | } | |
399 | ||
400 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
401 | //! Additional note: no splaying is performed | |
402 | template<class KeyType, class KeyNodePtrCompare> | |
403 | static std::pair<node_ptr, node_ptr> lower_bound_range | |
404 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) | |
405 | { return bstree_algo::lower_bound_range(header, key, comp); } | |
406 | ||
407 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) | |
408 | //! Additional notes: the first node of the range is splayed. | |
409 | template<class KeyType, class KeyNodePtrCompare> | |
410 | static std::pair<node_ptr, node_ptr> bounded_range | |
411 | (const node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp | |
412 | , bool left_closed, bool right_closed) | |
413 | { | |
414 | splay_down(detail::uncast(header), lower_key, comp); | |
415 | std::pair<node_ptr, node_ptr> ret = | |
416 | bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); | |
417 | //splay_up(ret.first, detail::uncast(header)); | |
418 | return ret; | |
419 | } | |
420 | ||
421 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) | |
422 | //! Additional note: no splaying is performed | |
423 | template<class KeyType, class KeyNodePtrCompare> | |
424 | static std::pair<node_ptr, node_ptr> bounded_range | |
425 | (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp | |
426 | , bool left_closed, bool right_closed) | |
427 | { return bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); } | |
428 | ||
429 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) | |
430 | //! Additional note: the inserted node is splayed | |
431 | template<class NodePtrCompare> | |
432 | static node_ptr insert_equal_upper_bound | |
433 | (const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp) | |
434 | { | |
435 | splay_down(header, new_node, comp); | |
436 | return bstree_algo::insert_equal_upper_bound(header, new_node, comp); | |
437 | } | |
438 | ||
439 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) | |
440 | //! Additional note: the inserted node is splayed | |
441 | template<class NodePtrCompare> | |
442 | static node_ptr insert_equal_lower_bound | |
443 | (const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp) | |
444 | { | |
445 | splay_down(header, new_node, comp); | |
446 | return bstree_algo::insert_equal_lower_bound(header, new_node, comp); | |
447 | } | |
448 | ||
449 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) | |
450 | //! Additional note: the inserted node is splayed | |
451 | template<class NodePtrCompare> | |
452 | static node_ptr insert_equal | |
453 | (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) | |
454 | { | |
455 | splay_down(header, new_node, comp); | |
456 | return bstree_algo::insert_equal(header, hint, new_node, comp); | |
457 | } | |
458 | ||
459 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) | |
460 | //! Additional note: the inserted node is splayed | |
461 | static node_ptr insert_before | |
462 | (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node) | |
463 | { | |
464 | bstree_algo::insert_before(header, pos, new_node); | |
465 | splay_up(new_node, header); | |
466 | return new_node; | |
467 | } | |
468 | ||
469 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) | |
470 | //! Additional note: the inserted node is splayed | |
471 | static void push_back(const node_ptr & header, const node_ptr & new_node) | |
472 | { | |
473 | bstree_algo::push_back(header, new_node); | |
474 | splay_up(new_node, header); | |
475 | } | |
476 | ||
477 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) | |
478 | //! Additional note: the inserted node is splayed | |
479 | static void push_front(const node_ptr & header, const node_ptr & new_node) | |
480 | { | |
481 | bstree_algo::push_front(header, new_node); | |
482 | splay_up(new_node, header); | |
483 | } | |
484 | ||
485 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) | |
486 | //! Additional note: nodes with the given key are splayed | |
487 | template<class KeyType, class KeyNodePtrCompare> | |
488 | static std::pair<node_ptr, bool> insert_unique_check | |
489 | (const node_ptr & header, const KeyType &key | |
490 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data) | |
491 | { | |
492 | splay_down(header, key, comp); | |
493 | return bstree_algo::insert_unique_check(header, key, comp, commit_data); | |
494 | } | |
495 | ||
496 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) | |
497 | //! Additional note: nodes with the given key are splayed | |
498 | template<class KeyType, class KeyNodePtrCompare> | |
499 | static std::pair<node_ptr, bool> insert_unique_check | |
500 | (const node_ptr & header, const node_ptr &hint, const KeyType &key | |
501 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data) | |
502 | { | |
503 | splay_down(header, key, comp); | |
504 | return bstree_algo::insert_unique_check(header, hint, key, comp, commit_data); | |
505 | } | |
506 | ||
507 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
508 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) | |
509 | static void insert_unique_commit | |
510 | (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data); | |
511 | ||
512 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header | |
513 | static bool is_header(const const_node_ptr & p); | |
514 | ||
515 | //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance | |
516 | static void rebalance(const node_ptr & header); | |
517 | ||
518 | //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance_subtree | |
519 | static node_ptr rebalance_subtree(const node_ptr & old_root); | |
520 | ||
521 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
522 | ||
523 | // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow | |
524 | static void splay_up(const node_ptr & node, const node_ptr & header) | |
525 | { priv_splay_up<true>(node, header); } | |
526 | ||
527 | // top-down splay | complexity : logarithmic | exception : strong, note A | |
528 | template<class KeyType, class KeyNodePtrCompare> | |
529 | static node_ptr splay_down(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool *pfound = 0) | |
530 | { return priv_splay_down<true>(header, key, comp, pfound); } | |
531 | ||
532 | private: | |
533 | ||
534 | /// @cond | |
535 | ||
536 | // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow | |
537 | template<bool SimpleSplay> | |
538 | static void priv_splay_up(const node_ptr & node, const node_ptr & header) | |
539 | { | |
540 | // If (node == header) do a splay for the right most node instead | |
541 | // this is to boost performance of equal_range/count on equivalent containers in the case | |
542 | // where there are many equal elements at the end | |
543 | node_ptr n((node == header) ? NodeTraits::get_right(header) : node); | |
544 | node_ptr t(header); | |
545 | ||
546 | if( n == t ) return; | |
547 | ||
548 | for( ;; ){ | |
549 | node_ptr p(NodeTraits::get_parent(n)); | |
550 | node_ptr g(NodeTraits::get_parent(p)); | |
551 | ||
552 | if( p == t ) break; | |
553 | ||
554 | if( g == t ){ | |
555 | // zig | |
556 | rotate(n); | |
557 | } | |
558 | else if ((NodeTraits::get_left(p) == n && NodeTraits::get_left(g) == p) || | |
559 | (NodeTraits::get_right(p) == n && NodeTraits::get_right(g) == p) ){ | |
560 | // zig-zig | |
561 | rotate(p); | |
562 | rotate(n); | |
563 | } | |
564 | else { | |
565 | // zig-zag | |
566 | rotate(n); | |
567 | if(!SimpleSplay){ | |
568 | rotate(n); | |
569 | } | |
570 | } | |
571 | } | |
572 | } | |
573 | ||
574 | template<bool SimpleSplay, class KeyType, class KeyNodePtrCompare> | |
575 | static node_ptr priv_splay_down(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool *pfound = 0) | |
576 | { | |
577 | //Most splay tree implementations use a dummy/null node to implement. | |
578 | //this function. This has some problems for a generic library like Intrusive: | |
579 | // | |
580 | // * The node might not have a default constructor. | |
581 | // * The default constructor could throw. | |
582 | // | |
583 | //We already have a header node. Leftmost and rightmost nodes of the tree | |
584 | //are not changed when splaying (because the invariants of the tree don't | |
585 | //change) We can back up them, use the header as the null node and | |
586 | //reassign old values after the function has been completed. | |
587 | node_ptr const old_root = NodeTraits::get_parent(header); | |
588 | node_ptr const leftmost = NodeTraits::get_left(header); | |
589 | node_ptr const rightmost = NodeTraits::get_right(header); | |
590 | if(leftmost == rightmost){ //Empty or unique node | |
591 | if(pfound){ | |
592 | *pfound = old_root && !comp(key, old_root) && !comp(old_root, key); | |
593 | } | |
594 | return old_root ? old_root : header; | |
595 | } | |
596 | else{ | |
597 | //Initialize "null node" (the header in our case) | |
598 | NodeTraits::set_left (header, node_ptr()); | |
599 | NodeTraits::set_right(header, node_ptr()); | |
600 | //Class that will backup leftmost/rightmost from header, commit the assemble(), | |
601 | //and will restore leftmost/rightmost to header even if "comp" throws | |
602 | detail::splaydown_assemble_and_fix_header<NodeTraits> commit(old_root, header, leftmost, rightmost); | |
603 | bool found = false; | |
604 | ||
605 | for( ;; ){ | |
606 | if(comp(key, commit.t_)){ | |
607 | node_ptr const t_left = NodeTraits::get_left(commit.t_); | |
608 | if(!t_left) | |
609 | break; | |
610 | if(comp(key, t_left)){ | |
611 | bstree_algo::rotate_right_no_parent_fix(commit.t_, t_left); | |
612 | commit.t_ = t_left; | |
613 | if( !NodeTraits::get_left(commit.t_) ) | |
614 | break; | |
615 | link_right(commit.t_, commit.r_); | |
616 | } | |
617 | else{ | |
618 | link_right(commit.t_, commit.r_); | |
619 | if(!SimpleSplay && comp(t_left, key)){ | |
620 | if( !NodeTraits::get_right(commit.t_) ) | |
621 | break; | |
622 | link_left(commit.t_, commit.l_); | |
623 | } | |
624 | } | |
625 | } | |
626 | else if(comp(commit.t_, key)){ | |
627 | node_ptr const t_right = NodeTraits::get_right(commit.t_); | |
628 | if(!t_right) | |
629 | break; | |
630 | ||
631 | if(comp(t_right, key)){ | |
632 | bstree_algo::rotate_left_no_parent_fix(commit.t_, t_right); | |
633 | commit.t_ = t_right; | |
634 | if( !NodeTraits::get_right(commit.t_) ) | |
635 | break; | |
636 | link_left(commit.t_, commit.l_); | |
637 | } | |
638 | else{ | |
639 | link_left(commit.t_, commit.l_); | |
640 | if(!SimpleSplay && comp(key, t_right)){ | |
641 | if( !NodeTraits::get_left(commit.t_) ) | |
642 | break; | |
643 | link_right(commit.t_, commit.r_); | |
644 | } | |
645 | } | |
646 | } | |
647 | else{ | |
648 | found = true; | |
649 | break; | |
650 | } | |
651 | } | |
652 | ||
653 | //commit.~splaydown_assemble_and_fix_header<NodeTraits>() will first | |
654 | //"assemble()" + link the new root & recover header's leftmost & rightmost | |
655 | if(pfound){ | |
656 | *pfound = found; | |
657 | } | |
658 | return commit.t_; | |
659 | } | |
660 | } | |
661 | ||
662 | // break link to left child node and attach it to left tree pointed to by l | complexity : constant | exception : nothrow | |
663 | static void link_left(node_ptr & t, node_ptr & l) | |
664 | { | |
665 | //procedure link_left; | |
666 | // t, l, right(l) := right(t), t, t | |
667 | //end link_left | |
668 | NodeTraits::set_right(l, t); | |
669 | NodeTraits::set_parent(t, l); | |
670 | l = t; | |
671 | t = NodeTraits::get_right(t); | |
672 | } | |
673 | ||
674 | // break link to right child node and attach it to right tree pointed to by r | complexity : constant | exception : nothrow | |
675 | static void link_right(node_ptr & t, node_ptr & r) | |
676 | { | |
677 | //procedure link_right; | |
678 | // t, r, left(r) := left(t), t, t | |
679 | //end link_right; | |
680 | NodeTraits::set_left(r, t); | |
681 | NodeTraits::set_parent(t, r); | |
682 | r = t; | |
683 | t = NodeTraits::get_left(t); | |
684 | } | |
685 | ||
686 | // rotate n with its parent | complexity : constant | exception : nothrow | |
687 | static void rotate(const node_ptr & n) | |
688 | { | |
689 | //procedure rotate_left; | |
690 | // t, right(t), left(right(t)) := right(t), left(right(t)), t | |
691 | //end rotate_left; | |
692 | node_ptr p = NodeTraits::get_parent(n); | |
693 | node_ptr g = NodeTraits::get_parent(p); | |
694 | //Test if g is header before breaking tree | |
695 | //invariants that would make is_header invalid | |
696 | bool g_is_header = bstree_algo::is_header(g); | |
697 | ||
698 | if(NodeTraits::get_left(p) == n){ | |
699 | NodeTraits::set_left(p, NodeTraits::get_right(n)); | |
700 | if(NodeTraits::get_left(p)) | |
701 | NodeTraits::set_parent(NodeTraits::get_left(p), p); | |
702 | NodeTraits::set_right(n, p); | |
703 | } | |
704 | else{ // must be ( p->right == n ) | |
705 | NodeTraits::set_right(p, NodeTraits::get_left(n)); | |
706 | if(NodeTraits::get_right(p)) | |
707 | NodeTraits::set_parent(NodeTraits::get_right(p), p); | |
708 | NodeTraits::set_left(n, p); | |
709 | } | |
710 | ||
711 | NodeTraits::set_parent(p, n); | |
712 | NodeTraits::set_parent(n, g); | |
713 | ||
714 | if(g_is_header){ | |
715 | if(NodeTraits::get_parent(g) == p) | |
716 | NodeTraits::set_parent(g, n); | |
717 | else{//must be ( g->right == p ) | |
718 | BOOST_INTRUSIVE_INVARIANT_ASSERT(false); | |
719 | NodeTraits::set_right(g, n); | |
720 | } | |
721 | } | |
722 | else{ | |
723 | if(NodeTraits::get_left(g) == p) | |
724 | NodeTraits::set_left(g, n); | |
725 | else //must be ( g->right == p ) | |
726 | NodeTraits::set_right(g, n); | |
727 | } | |
728 | } | |
729 | ||
730 | /// @endcond | |
731 | }; | |
732 | ||
733 | /// @cond | |
734 | ||
735 | template<class NodeTraits> | |
736 | struct get_algo<SplayTreeAlgorithms, NodeTraits> | |
737 | { | |
738 | typedef splaytree_algorithms<NodeTraits> type; | |
739 | }; | |
740 | ||
741 | template <class ValueTraits, class NodePtrCompare, class ExtraChecker> | |
742 | struct get_node_checker<SplayTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> | |
743 | { | |
744 | typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; | |
745 | }; | |
746 | ||
747 | /// @endcond | |
748 | ||
749 | } //namespace intrusive | |
750 | } //namespace boost | |
751 | ||
752 | #include <boost/intrusive/detail/config_end.hpp> | |
753 | ||
754 | #endif //BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP |