1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2007-2012
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)
9 // See http://www.boost.org/libs/intrusive for documentation.
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).
15 // The code has been modified and (supposely) improved by Ion Gaztanaga.
16 // Here is the header of the file used as base code:
18 // splay_tree.h -- implementation of a STL compatible splay tree.
20 // Copyright (c) 2004 Ralf Mattethat
22 // Permission to copy, use, modify, sell and distribute this software
23 // is granted provided this copyright notice appears in all copies.
24 // This software is provided "as is" without express or implied
25 // warranty, and with no claim as to its suitability for any purpose.
27 // Please send questions, comments, complaints, performance data, etc to
28 // ralf.mattethat@teknologisk.dk
30 // Requirements for element type
31 // * must be copy-constructible
32 // * destructor must not throw exception
34 // Methods marked with note A only throws an exception if the evaluation of the
35 // predicate throws an exception. If an exception is thrown the call has no
36 // effect on the containers state
38 // Methods marked with note B only throws an exception if the coppy constructor
39 // or assignment operator of the predicate throws an exception. If an exception
40 // is thrown the call has no effect on the containers state
42 // iterators are only invalidated, if the element pointed to by the iterator
43 // is deleted. The same goes for element references
46 #ifndef BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP
47 #define BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP
49 #include <boost/intrusive/detail/config_begin.hpp>
50 #include <boost/intrusive/detail/assert.hpp>
51 #include <boost/intrusive/intrusive_fwd.hpp>
52 #include <boost/intrusive/pointer_traits.hpp>
54 #include <boost/intrusive/detail/utilities.hpp>
55 #include <boost/intrusive/detail/tree_algorithms.hpp>
63 template<class NodeTraits>
64 struct splaydown_rollback
66 typedef typename NodeTraits::node_ptr node_ptr;
67 splaydown_rollback( const node_ptr *pcur_subtree, const node_ptr & header
68 , const node_ptr & leftmost , const node_ptr & rightmost)
69 : pcur_subtree_(pcur_subtree) , header_(header)
70 , leftmost_(leftmost) , rightmost_(rightmost)
74 { pcur_subtree_ = 0; }
79 //Exception can only be thrown by comp, but
80 //tree invariants still hold. *pcur_subtree is the current root
81 //so link it to the header.
82 NodeTraits::set_parent(*pcur_subtree_, header_);
83 NodeTraits::set_parent(header_, *pcur_subtree_);
84 //Recover leftmost/rightmost pointers
85 NodeTraits::set_left (header_, leftmost_);
86 NodeTraits::set_right(header_, rightmost_);
89 const node_ptr *pcur_subtree_;
90 node_ptr header_, leftmost_, rightmost_;
93 } //namespace detail {
96 //! A splay tree is an implementation of a binary search tree. The tree is
97 //! self balancing using the splay algorithm as described in
99 //! "Self-Adjusting Binary Search Trees
100 //! by Daniel Dominic Sleator and Robert Endre Tarjan
101 //! AT&T Bell Laboratories, Murray Hill, NJ
102 //! Journal of the ACM, Vol 32, no 3, July 1985, pp 652-686
104 //! splaytree_algorithms is configured with a NodeTraits class, which encapsulates the
105 //! information about the node to be manipulated. NodeTraits must support the
106 //! following interface:
110 //! <tt>node</tt>: The type of the node that forms the circular list
112 //! <tt>node_ptr</tt>: A pointer to a node
114 //! <tt>const_node_ptr</tt>: A pointer to a const node
116 //! <b>Static functions</b>:
118 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
120 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
122 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
124 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
126 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
128 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
129 template<class NodeTraits>
130 class splaytree_algorithms
134 typedef detail::tree_algorithms<NodeTraits> tree_algorithms;
138 typedef typename NodeTraits::node node;
139 typedef NodeTraits node_traits;
140 typedef typename NodeTraits::node_ptr node_ptr;
141 typedef typename NodeTraits::const_node_ptr const_node_ptr;
143 //! This type is the information that will be
144 //! filled by insert_unique_check
145 typedef typename tree_algorithms::insert_commit_data insert_commit_data;
149 static node_ptr uncast(const const_node_ptr & ptr)
150 { return pointer_traits<node_ptr>::const_cast_from(ptr); }
154 static node_ptr begin_node(const const_node_ptr & header)
155 { return tree_algorithms::begin_node(header); }
157 static node_ptr end_node(const const_node_ptr & header)
158 { return tree_algorithms::end_node(header); }
160 //! <b>Requires</b>: node is a node of the tree or an node initialized
163 //! <b>Effects</b>: Returns true if the node is initialized by init().
165 //! <b>Complexity</b>: Constant time.
167 //! <b>Throws</b>: Nothing.
168 static bool unique(const const_node_ptr & node)
169 { return tree_algorithms::unique(node); }
171 static void unlink(const node_ptr & node)
172 { tree_algorithms::unlink(node); }
174 //! <b>Requires</b>: node1 and node2 can't be header nodes
177 //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
178 //! in the position node2 before the function. node2 will be inserted in the
179 //! position node1 had before the function.
181 //! <b>Complexity</b>: Logarithmic.
183 //! <b>Throws</b>: Nothing.
185 //! <b>Note</b>: This function will break container ordering invariants if
186 //! node1 and node2 are not equivalent according to the ordering rules.
188 //!Experimental function
189 static void swap_nodes(const node_ptr & node1, const node_ptr & node2)
194 node_ptr header1(tree_algorithms::get_header(node1)), header2(tree_algorithms::get_header(node2));
195 swap_nodes(node1, header1, node2, header2);
198 //! <b>Requires</b>: node1 and node2 can't be header nodes
199 //! of two trees with header header1 and header2.
201 //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
202 //! in the position node2 before the function. node2 will be inserted in the
203 //! position node1 had before the function.
205 //! <b>Complexity</b>: Constant.
207 //! <b>Throws</b>: Nothing.
209 //! <b>Note</b>: This function will break container ordering invariants if
210 //! node1 and node2 are not equivalent according to the ordering rules.
212 //!Experimental function
213 static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2)
214 { tree_algorithms::swap_nodes(node1, header1, node2, header2); }
216 //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
217 //! and new_node must not be inserted in a tree.
219 //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
220 //! tree with new_node. The tree does not need to be rebalanced
222 //! <b>Complexity</b>: Logarithmic.
224 //! <b>Throws</b>: Nothing.
226 //! <b>Note</b>: This function will break container ordering invariants if
227 //! new_node is not equivalent to node_to_be_replaced according to the
228 //! ordering rules. This function is faster than erasing and inserting
229 //! the node, since no rebalancing and comparison is needed.
231 //!Experimental function
232 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
234 if(node_to_be_replaced == new_node)
236 replace_node(node_to_be_replaced, tree_algorithms::get_header(node_to_be_replaced), new_node);
239 //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
240 //! with header "header" and new_node must not be inserted in a tree.
242 //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
243 //! tree with new_node. The tree does not need to be rebalanced
245 //! <b>Complexity</b>: Constant.
247 //! <b>Throws</b>: Nothing.
249 //! <b>Note</b>: This function will break container ordering invariants if
250 //! new_node is not equivalent to node_to_be_replaced according to the
251 //! ordering rules. This function is faster than erasing and inserting
252 //! the node, since no rebalancing or comparison is needed.
254 //!Experimental function
255 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
256 { tree_algorithms::replace_node(node_to_be_replaced, header, new_node); }
258 //! <b>Requires</b>: p is a node from the tree except the header.
260 //! <b>Effects</b>: Returns the next node of the tree.
262 //! <b>Complexity</b>: Average constant time.
264 //! <b>Throws</b>: Nothing.
265 static node_ptr next_node(const node_ptr & p)
266 { return tree_algorithms::next_node(p); }
268 //! <b>Requires</b>: p is a node from the tree except the leftmost node.
270 //! <b>Effects</b>: Returns the previous node of the tree.
272 //! <b>Complexity</b>: Average constant time.
274 //! <b>Throws</b>: Nothing.
275 static node_ptr prev_node(const node_ptr & p)
276 { return tree_algorithms::prev_node(p); }
278 //! <b>Requires</b>: node must not be part of any tree.
280 //! <b>Effects</b>: After the function unique(node) == true.
282 //! <b>Complexity</b>: Constant.
284 //! <b>Throws</b>: Nothing.
286 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
287 static void init(const node_ptr & node)
288 { tree_algorithms::init(node); }
290 //! <b>Requires</b>: node must not be part of any tree.
292 //! <b>Effects</b>: Initializes the header to represent an empty tree.
293 //! unique(header) == true.
295 //! <b>Complexity</b>: Constant.
297 //! <b>Throws</b>: Nothing.
299 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
300 static void init_header(const node_ptr & header)
301 { tree_algorithms::init_header(header); }
303 //! <b>Requires</b>: "disposer" must be an object function
304 //! taking a node_ptr parameter and shouldn't throw.
306 //! <b>Effects</b>: Empties the target tree calling
307 //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
308 //! except the header.
310 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
311 //! number of elements of tree target tree when calling this function.
313 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
314 template<class Disposer>
315 static void clear_and_dispose(const node_ptr & header, Disposer disposer)
316 { tree_algorithms::clear_and_dispose(header, disposer); }
318 //! <b>Requires</b>: node is a node of the tree but it's not the header.
320 //! <b>Effects</b>: Returns the number of nodes of the subtree.
322 //! <b>Complexity</b>: Linear time.
324 //! <b>Throws</b>: Nothing.
325 static std::size_t count(const const_node_ptr & node)
326 { return tree_algorithms::count(node); }
328 //! <b>Requires</b>: header is the header node of the tree.
330 //! <b>Effects</b>: Returns the number of nodes above the header.
332 //! <b>Complexity</b>: Linear time.
334 //! <b>Throws</b>: Nothing.
335 static std::size_t size(const const_node_ptr & header)
336 { return tree_algorithms::size(header); }
338 //! <b>Requires</b>: header1 and header2 must be the header nodes
341 //! <b>Effects</b>: Swaps two trees. After the function header1 will contain
342 //! links to the second tree and header2 will have links to the first tree.
344 //! <b>Complexity</b>: Constant.
346 //! <b>Throws</b>: Nothing.
347 static void swap_tree(const node_ptr & header1, const node_ptr & header2)
348 { return tree_algorithms::swap_tree(header1, header2); }
350 //! <b>Requires</b>: "header" must be the header node of a tree.
351 //! "commit_data" must have been obtained from a previous call to
352 //! "insert_unique_check". No objects should have been inserted or erased
353 //! from the set between the "insert_unique_check" that filled "commit_data"
354 //! and the call to "insert_commit".
357 //! <b>Effects</b>: Inserts new_node in the set using the information obtained
358 //! from the "commit_data" that a previous "insert_check" filled.
360 //! <b>Complexity</b>: Constant time.
362 //! <b>Throws</b>: Nothing.
364 //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been
365 //! previously executed to fill "commit_data". No value should be inserted or
366 //! erased between the "insert_check" and "insert_commit" calls.
367 static void insert_unique_commit
368 (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
369 { tree_algorithms::insert_unique_commit(header, new_value, commit_data); }
371 //! <b>Requires</b>: "header" must be the header node of a tree.
372 //! KeyNodePtrCompare is a function object that induces a strict weak
373 //! ordering compatible with the strict weak ordering used to create the
374 //! the tree. NodePtrCompare compares KeyType with a node_ptr.
376 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
377 //! tree according to "comp" and obtains the needed information to realize
378 //! a constant-time node insertion if there is no equivalent node.
380 //! <b>Returns</b>: If there is an equivalent value
381 //! returns a pair containing a node_ptr to the already present node
382 //! and false. If there is not equivalent key can be inserted returns true
383 //! in the returned pair's boolean and fills "commit_data" that is meant to
384 //! be used with the "insert_commit" function to achieve a constant-time
385 //! insertion function.
387 //! <b>Complexity</b>: Average complexity is at most logarithmic.
389 //! <b>Throws</b>: If "comp" throws.
391 //! <b>Notes</b>: This function is used to improve performance when constructing
392 //! a node is expensive and the user does not want to have two equivalent nodes
393 //! in the tree: if there is an equivalent value
394 //! the constructed object must be discarded. Many times, the part of the
395 //! node that is used to impose the order is much cheaper to construct
396 //! than the node and this function offers the possibility to use that part
397 //! to check if the insertion will be successful.
399 //! If the check is successful, the user can construct the node and use
400 //! "insert_commit" to insert the node in constant-time. This gives a total
401 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
403 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only
404 //! if no more objects are inserted or erased from the set.
405 template<class KeyType, class KeyNodePtrCompare>
406 static std::pair<node_ptr, bool> insert_unique_check
407 (const node_ptr & header, const KeyType &key
408 ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
410 splay_down(header, key, comp);
411 return tree_algorithms::insert_unique_check(header, key, comp, commit_data);
414 template<class KeyType, class KeyNodePtrCompare>
415 static std::pair<node_ptr, bool> insert_unique_check
416 (const node_ptr & header, const node_ptr &hint, const KeyType &key
417 ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
419 splay_down(header, key, comp);
420 return tree_algorithms::insert_unique_check(header, hint, key, comp, commit_data);
423 static bool is_header(const const_node_ptr & p)
424 { return tree_algorithms::is_header(p); }
426 //! <b>Requires</b>: "header" must be the header node of a tree.
427 //! KeyNodePtrCompare is a function object that induces a strict weak
428 //! ordering compatible with the strict weak ordering used to create the
429 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
431 //! <b>Effects</b>: Returns an node_ptr to the element that is equivalent to
432 //! "key" according to "comp" or "header" if that element does not exist.
434 //! <b>Complexity</b>: Logarithmic.
436 //! <b>Throws</b>: If "comp" throws.
437 template<class KeyType, class KeyNodePtrCompare>
439 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool splay = true)
442 splay_down(uncast(header), key, comp);
443 node_ptr end = uncast(header);
444 node_ptr y = lower_bound(header, key, comp, false);
445 node_ptr r = (y == end || comp(key, y)) ? end : y;
449 //! <b>Requires</b>: "header" must be the header node of a tree.
450 //! KeyNodePtrCompare is a function object that induces a strict weak
451 //! ordering compatible with the strict weak ordering used to create the
452 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
454 //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
455 //! all elements that are equivalent to "key" according to "comp" or an
456 //! empty range that indicates the position where those elements would be
457 //! if they there are no equivalent elements.
459 //! <b>Complexity</b>: Logarithmic.
461 //! <b>Throws</b>: If "comp" throws.
462 template<class KeyType, class KeyNodePtrCompare>
463 static std::pair<node_ptr, node_ptr> equal_range
464 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool splay = true)
467 //splay_down(uncast(header), key, comp);
468 std::pair<node_ptr, node_ptr> ret =
469 tree_algorithms::equal_range(header, key, comp);
472 splay_up(ret.first, uncast(header));
476 //! <b>Requires</b>: "header" must be the header node of a tree.
477 //! KeyNodePtrCompare is a function object that induces a strict weak
478 //! ordering compatible with the strict weak ordering used to create the
479 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
480 //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
481 //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
483 //! <b>Effects</b>: Returns an a pair with the following criteria:
485 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
487 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
489 //! <b>Complexity</b>: Logarithmic.
491 //! <b>Throws</b>: If "comp" throws.
493 //! <b>Note</b>: This function can be more efficient than calling upper_bound
494 //! and lower_bound for lower_key and upper_key.
495 template<class KeyType, class KeyNodePtrCompare>
496 static std::pair<node_ptr, node_ptr> bounded_range
497 (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
498 , bool left_closed, bool right_closed, bool splay = true)
500 std::pair<node_ptr, node_ptr> ret =
501 tree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed);
504 splay_up(ret.first, uncast(header));
508 //! <b>Requires</b>: "header" must be the header node of a tree.
509 //! KeyNodePtrCompare is a function object that induces a strict weak
510 //! ordering compatible with the strict weak ordering used to create the
511 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
513 //! <b>Effects</b>: Returns an node_ptr to the first element that is
514 //! not less than "key" according to "comp" or "header" if that element does
517 //! <b>Complexity</b>: Logarithmic.
519 //! <b>Throws</b>: If "comp" throws.
520 template<class KeyType, class KeyNodePtrCompare>
521 static node_ptr lower_bound
522 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool splay = true)
525 //splay_down(uncast(header), key, comp);
526 node_ptr y = tree_algorithms::lower_bound(header, key, comp);
528 splay_up(y, uncast(header));
532 //! <b>Requires</b>: "header" must be the header node of a tree.
533 //! KeyNodePtrCompare is a function object that induces a strict weak
534 //! ordering compatible with the strict weak ordering used to create the
535 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
537 //! <b>Effects</b>: Returns an node_ptr to the first element that is greater
538 //! than "key" according to "comp" or "header" if that element does not exist.
540 //! <b>Complexity</b>: Logarithmic.
542 //! <b>Throws</b>: If "comp" throws.
543 template<class KeyType, class KeyNodePtrCompare>
544 static node_ptr upper_bound
545 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool splay = true)
548 //splay_down(uncast(header), key, comp);
549 node_ptr y = tree_algorithms::upper_bound(header, key, comp);
551 splay_up(y, uncast(header));
555 //! <b>Requires</b>: "header" must be the header node of a tree.
556 //! NodePtrCompare is a function object that induces a strict weak
557 //! ordering compatible with the strict weak ordering used to create the
558 //! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from
559 //! the "header"'s tree.
561 //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to
562 //! where it will be inserted. If "hint" is the upper_bound
563 //! the insertion takes constant time (two comparisons in the worst case).
565 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
566 //! constant time if new_node is inserted immediately before "hint".
568 //! <b>Throws</b>: If "comp" throws.
569 template<class NodePtrCompare>
570 static node_ptr insert_equal
571 (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp)
573 splay_down(header, new_node, comp);
574 return tree_algorithms::insert_equal(header, hint, new_node, comp);
578 //! <b>Requires</b>: "header" must be the header node of a tree.
579 //! "pos" must be a valid iterator or header (end) node.
580 //! "pos" must be an iterator pointing to the successor to "new_node"
581 //! once inserted according to the order of already inserted nodes. This function does not
582 //! check "pos" and this precondition must be guaranteed by the caller.
584 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
586 //! <b>Complexity</b>: Constant-time.
588 //! <b>Throws</b>: Nothing.
590 //! <b>Note</b>: If "pos" is not the successor of the newly inserted "new_node"
591 //! tree invariants might be broken.
592 static node_ptr insert_before
593 (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node)
595 tree_algorithms::insert_before(header, pos, new_node);
596 splay_up(new_node, header);
600 //! <b>Requires</b>: "header" must be the header node of a tree.
601 //! "new_node" must be, according to the used ordering no less than the
602 //! greatest inserted key.
604 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
606 //! <b>Complexity</b>: Constant-time.
608 //! <b>Throws</b>: Nothing.
610 //! <b>Note</b>: If "new_node" is less than the greatest inserted key
611 //! tree invariants are broken. This function is slightly faster than
612 //! using "insert_before".
613 static void push_back(const node_ptr & header, const node_ptr & new_node)
615 tree_algorithms::push_back(header, new_node);
616 splay_up(new_node, header);
619 //! <b>Requires</b>: "header" must be the header node of a tree.
620 //! "new_node" must be, according to the used ordering, no greater than the
621 //! lowest inserted key.
623 //! <b>Effects</b>: Inserts new_node into the tree before "pos".
625 //! <b>Complexity</b>: Constant-time.
627 //! <b>Throws</b>: Nothing.
629 //! <b>Note</b>: If "new_node" is greater than the lowest inserted key
630 //! tree invariants are broken. This function is slightly faster than
631 //! using "insert_before".
632 static void push_front(const node_ptr & header, const node_ptr & new_node)
634 tree_algorithms::push_front(header, new_node);
635 splay_up(new_node, header);
638 //! <b>Requires</b>: "header" must be the header node of a tree.
639 //! NodePtrCompare is a function object that induces a strict weak
640 //! ordering compatible with the strict weak ordering used to create the
641 //! the tree. NodePtrCompare compares two node_ptrs.
643 //! <b>Effects</b>: Inserts new_node into the tree before the upper bound
644 //! according to "comp".
646 //! <b>Complexity</b>: Average complexity for insert element is at
647 //! most logarithmic.
649 //! <b>Throws</b>: If "comp" throws.
650 template<class NodePtrCompare>
651 static node_ptr insert_equal_upper_bound
652 (const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp)
654 splay_down(header, new_node, comp);
655 return tree_algorithms::insert_equal_upper_bound(header, new_node, comp);
658 //! <b>Requires</b>: "header" must be the header node of a tree.
659 //! NodePtrCompare is a function object that induces a strict weak
660 //! ordering compatible with the strict weak ordering used to create the
661 //! the tree. NodePtrCompare compares two node_ptrs.
663 //! <b>Effects</b>: Inserts new_node into the tree before the lower bound
664 //! according to "comp".
666 //! <b>Complexity</b>: Average complexity for insert element is at
667 //! most logarithmic.
669 //! <b>Throws</b>: If "comp" throws.
670 template<class NodePtrCompare>
671 static node_ptr insert_equal_lower_bound
672 (const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp)
674 splay_down(header, new_node, comp);
675 return tree_algorithms::insert_equal_lower_bound(header, new_node, comp);
678 //! <b>Requires</b>: "cloner" must be a function
679 //! object taking a node_ptr and returning a new cloned node of it. "disposer" must
680 //! take a node_ptr and shouldn't throw.
682 //! <b>Effects</b>: First empties target tree calling
683 //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
684 //! except the header.
686 //! Then, duplicates the entire tree pointed by "source_header" cloning each
687 //! source node with <tt>node_ptr Cloner::operator()(const node_ptr &)</tt> to obtain
688 //! the nodes of the target tree. If "cloner" throws, the cloned target nodes
689 //! are disposed using <tt>void disposer(const node_ptr &)</tt>.
691 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
692 //! number of elements of tree target tree when calling this function.
694 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
695 template <class Cloner, class Disposer>
697 (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
698 { tree_algorithms::clone(source_header, target_header, cloner, disposer); }
700 // delete node | complexity : constant | exception : nothrow
701 static void erase(const node_ptr & header, const node_ptr & z, bool splay = true)
703 // node_base* n = t->right;
704 // if( t->left != node_ptr() ){
705 // node_base* l = t->previous();
706 // splay_up( l , t );
708 // n->right = t->right;
709 // if( n->right != node_ptr() )
710 // n->right->parent = n;
713 // if( n != node_ptr() )
714 // n->parent = t->parent;
716 // if( t->parent->left == t )
717 // t->parent->left = n;
718 // else // must be ( t->parent->right == t )
719 // t->parent->right = n;
721 // if( data_->parent == t )
722 // data_->parent = find_leftmost();
724 if(splay && NodeTraits::get_left(z)){
725 splay_up(prev_node(z), header);
729 if(splay && NodeTraits::get_left(z) != node_ptr() ){
730 node_ptr l = NodeTraits::get_left(z);
733 if(splay && NodeTraits::get_left(z) != node_ptr() ){
734 node_ptr l = prev_node(z);
744 //splay_up(z, header);
745 tree_algorithms::erase(header, z);
748 // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow
749 static void splay_up(const node_ptr & node, const node_ptr & header)
751 // If (node == header) do a splay for the right most node instead
752 // this is to boost performance of equal_range/count on equivalent containers in the case
753 // where there are many equal elements at the end
754 node_ptr n((node == header) ? NodeTraits::get_right(header) : node);
760 node_ptr p(NodeTraits::get_parent(n));
761 node_ptr g(NodeTraits::get_parent(p));
769 else if ((NodeTraits::get_left(p) == n && NodeTraits::get_left(g) == p) ||
770 (NodeTraits::get_right(p) == n && NodeTraits::get_right(g) == p) ){
783 // top-down splay | complexity : logarithmic | exception : strong, note A
784 template<class KeyType, class KeyNodePtrCompare>
785 static node_ptr splay_down(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
787 if(!NodeTraits::get_parent(header))
789 //Most splay tree implementations use a dummy/null node to implement.
790 //this function. This has some problems for a generic library like Intrusive:
792 // * The node might not have a default constructor.
793 // * The default constructor could throw.
795 //We already have a header node. Leftmost and rightmost nodes of the tree
796 //are not changed when splaying (because the invariants of the tree don't
797 //change) We can back up them, use the header as the null node and
798 //reassign old values after the function has been completed.
799 node_ptr t = NodeTraits::get_parent(header);
800 //Check if tree has a single node
801 if(!NodeTraits::get_left(t) && !NodeTraits::get_right(t))
803 //Backup leftmost/rightmost
804 node_ptr leftmost (NodeTraits::get_left(header));
805 node_ptr rightmost(NodeTraits::get_right(header));
807 //Anti-exception rollback, recovers the original header node if an exception is thrown.
808 detail::splaydown_rollback<NodeTraits> rollback(&t, header, leftmost, rightmost);
809 node_ptr null_node = header;
810 node_ptr l = null_node;
811 node_ptr r = null_node;
815 if(NodeTraits::get_left(t) == node_ptr() )
817 if(comp(key, NodeTraits::get_left(t))){
818 t = tree_algorithms::rotate_right(t);
820 if(NodeTraits::get_left(t) == node_ptr())
824 else if(comp(NodeTraits::get_left(t), key)){
827 if(NodeTraits::get_right(t) == node_ptr() )
835 else if(comp(t, key)){
836 if(NodeTraits::get_right(t) == node_ptr() )
839 if(comp(NodeTraits::get_right(t), key)){
840 t = tree_algorithms::rotate_left( t );
842 if(NodeTraits::get_right(t) == node_ptr() )
846 else if(comp(key, NodeTraits::get_right(t))){
849 if(NodeTraits::get_left(t) == node_ptr())
863 assemble(t, l, r, null_node);
867 //Now recover the original header except for the
869 //t is the current root
870 NodeTraits::set_parent(header, t);
871 NodeTraits::set_parent(t, header);
872 //Recover leftmost/rightmost pointers
873 NodeTraits::set_left (header, leftmost);
874 NodeTraits::set_right(header, rightmost);
878 //! <b>Requires</b>: header must be the header of a tree.
880 //! <b>Effects</b>: Rebalances the tree.
882 //! <b>Throws</b>: Nothing.
884 //! <b>Complexity</b>: Linear.
885 static void rebalance(const node_ptr & header)
886 { tree_algorithms::rebalance(header); }
888 //! <b>Requires</b>: old_root is a node of a tree.
890 //! <b>Effects</b>: Rebalances the subtree rooted at old_root.
892 //! <b>Returns</b>: The new root of the subtree.
894 //! <b>Throws</b>: Nothing.
896 //! <b>Complexity</b>: Linear.
897 static node_ptr rebalance_subtree(const node_ptr & old_root)
898 { return tree_algorithms::rebalance_subtree(old_root); }
901 //! <b>Requires</b>: "n" must be a node inserted in a tree.
903 //! <b>Effects</b>: Returns a pointer to the header node of the tree.
905 //! <b>Complexity</b>: Logarithmic.
907 //! <b>Throws</b>: Nothing.
908 static node_ptr get_header(const node_ptr & n)
909 { return tree_algorithms::get_header(n); }
915 // assemble the three sub-trees into new tree pointed to by t | complexity : constant | exception : nothrow
916 static void assemble(const node_ptr &t, const node_ptr & l, const node_ptr & r, const const_node_ptr & null_node )
918 NodeTraits::set_right(l, NodeTraits::get_left(t));
919 NodeTraits::set_left(r, NodeTraits::get_right(t));
921 if(NodeTraits::get_right(l) != node_ptr()){
922 NodeTraits::set_parent(NodeTraits::get_right(l), l);
925 if(NodeTraits::get_left(r) != node_ptr()){
926 NodeTraits::set_parent(NodeTraits::get_left(r), r);
929 NodeTraits::set_left (t, NodeTraits::get_right(null_node));
930 NodeTraits::set_right(t, NodeTraits::get_left(null_node));
932 if( NodeTraits::get_left(t) != node_ptr() ){
933 NodeTraits::set_parent(NodeTraits::get_left(t), t);
936 if( NodeTraits::get_right(t) ){
937 NodeTraits::set_parent(NodeTraits::get_right(t), t);
941 // break link to left child node and attach it to left tree pointed to by l | complexity : constant | exception : nothrow
942 static void link_left(node_ptr & t, node_ptr & l)
944 NodeTraits::set_right(l, t);
945 NodeTraits::set_parent(t, l);
947 t = NodeTraits::get_right(t);
950 // break link to right child node and attach it to right tree pointed to by r | complexity : constant | exception : nothrow
951 static void link_right(node_ptr & t, node_ptr & r)
953 NodeTraits::set_left(r, t);
954 NodeTraits::set_parent(t, r);
956 t = NodeTraits::get_left(t);
959 // rotate n with its parent | complexity : constant | exception : nothrow
960 static void rotate(const node_ptr & n)
962 node_ptr p = NodeTraits::get_parent(n);
963 node_ptr g = NodeTraits::get_parent(p);
964 //Test if g is header before breaking tree
965 //invariants that would make is_header invalid
966 bool g_is_header = is_header(g);
968 if(NodeTraits::get_left(p) == n){
969 NodeTraits::set_left(p, NodeTraits::get_right(n));
970 if(NodeTraits::get_left(p) != node_ptr())
971 NodeTraits::set_parent(NodeTraits::get_left(p), p);
972 NodeTraits::set_right(n, p);
974 else{ // must be ( p->right == n )
975 NodeTraits::set_right(p, NodeTraits::get_left(n));
976 if(NodeTraits::get_right(p) != node_ptr())
977 NodeTraits::set_parent(NodeTraits::get_right(p), p);
978 NodeTraits::set_left(n, p);
981 NodeTraits::set_parent(p, n);
982 NodeTraits::set_parent(n, g);
985 if(NodeTraits::get_parent(g) == p)
986 NodeTraits::set_parent(g, n);
987 else{//must be ( g->right == p )
988 BOOST_INTRUSIVE_INVARIANT_ASSERT(false);
989 NodeTraits::set_right(g, n);
993 if(NodeTraits::get_left(g) == p)
994 NodeTraits::set_left(g, n);
995 else //must be ( g->right == p )
996 NodeTraits::set_right(g, n);
1003 } //namespace intrusive
1006 #include <boost/intrusive/detail/config_end.hpp>
1008 #endif //BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP