--- /dev/null
+/////////////////////////////////////////////////////////////////////////////\r
+//\r
+// (C) Copyright Olaf Krzikalla 2004-2006.\r
+// (C) Copyright Ion Gazta�aga 2006-2007.\r
+//\r
+// Distributed under the Boost Software License, Version 1.0.\r
+// (See accompanying file LICENSE_1_0.txt or copy at\r
+// http://www.boost.org/LICENSE_1_0.txt)\r
+//\r
+// See http://www.boost.org/libs/intrusive for documentation.\r
+//\r
+/////////////////////////////////////////////////////////////////////////////\r
+// The internal implementation of red-black trees is based on that of SGI STL\r
+// stl_tree.h file: \r
+//\r
+// Copyright (c) 1996,1997\r
+// Silicon Graphics Computer Systems, Inc.\r
+//\r
+// Permission to use, copy, modify, distribute and sell this software\r
+// and its documentation for any purpose is hereby granted without fee,\r
+// provided that the above copyright notice appear in all copies and\r
+// that both that copyright notice and this permission notice appear\r
+// in supporting documentation. Silicon Graphics makes no\r
+// representations about the suitability of this software for any\r
+// purpose. It is provided "as is" without express or implied warranty.\r
+//\r
+//\r
+// Copyright (c) 1994\r
+// Hewlett-Packard Company\r
+//\r
+// Permission to use, copy, modify, distribute and sell this software\r
+// and its documentation for any purpose is hereby granted without fee,\r
+// provided that the above copyright notice appear in all copies and\r
+// that both that copyright notice and this permission notice appear\r
+// in supporting documentation. Hewlett-Packard Company makes no\r
+// representations about the suitability of this software for any\r
+// purpose. It is provided "as is" without express or implied warranty.\r
+\r
+#ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP\r
+#define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP\r
+\r
+#include "detail/config_begin.hpp"\r
+#include <iterator>\r
+#include <boost/assert.hpp>\r
+#include "detail/pointer_type.hpp"\r
+#include "detail/pointer_to_other.hpp"\r
+#include <boost/get_pointer.hpp>\r
+#include <boost/type_traits/alignment_of.hpp>\r
+#include <cstddef>\r
+#include <boost/detail/no_exceptions_support.hpp>\r
+\r
+\r
+namespace boost {\r
+namespace intrusive {\r
+\r
+//! rbtree_algorithms provides basic algorithms to manipulate \r
+//! nodes forming a red-black tree. The insertion and deletion algorithms are
+//! based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms
+//! (MIT Press, 1990), except that
+//!
+//! (1) the header node is maintained with links not only to the root
+//! but also to the leftmost node of the tree, to enable constant time
+//! begin(), and to the rightmost node of the tree, to enable linear time
+//! performance when used with the generic set algorithms (set_union,
+//! etc.);
+//!
+//! (2) when a node being deleted has two children its successor node is
+//! relinked into its place, rather than copied, so that the only
+//! iterators invalidated are those referring to the deleted node.\r
+//!\r
+//! rbtree_algorithms is configured with a NodeTraits class, which capsulates the\r
+//! information about the node to be manipulated. NodeTraits must support the\r
+//! following interface:\r
+//!\r
+//! <b>Typedefs</b>:\r
+//!\r
+//! <tt>node</tt>: The type of the node that forms the circular list\r
+//!\r
+//! <tt>node_ptr</tt>: A pointer to a node\r
+//!\r
+//! <tt>const_node_ptr</tt>: A pointer to a const node\r
+//!\r
+//! <tt>color</tt>: The type that can store the color of a node\r
+//!\r
+//! <b>Static functions</b>:\r
+//!\r
+//! <tt>static node_ptr get_parent(const_node_ptr n);</tt>\r
+//! \r
+//! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>\r
+//!\r
+//! <tt>static node_ptr get_left(const_node_ptr n);</tt>\r
+//! \r
+//! <tt>static void set_left(node_ptr n, node_ptr left);</tt>\r
+//!\r
+//! <tt>static node_ptr get_right(const_node_ptr n);</tt>\r
+//! \r
+//! <tt>static void set_right(node_ptr n, node_ptr right);</tt>\r
+//! \r
+//! <tt>static color get_color(const_node_ptr n);</tt>\r
+//! \r
+//! <tt>static void set_color(node_ptr n, color c);</tt>\r
+//! \r
+//! <tt>static color black();</tt>\r
+//! \r
+//! <tt>static color red();</tt>\r
+template<class NodeTraits>\r
+class rbtree_algorithms\r
+{\r
+ private:\r
+ typedef typename NodeTraits::node node;\r
+\r
+ public:\r
+ typedef typename NodeTraits::node_ptr node_ptr;\r
+ typedef typename NodeTraits::const_node_ptr const_node_ptr;\r
+ typedef typename NodeTraits::color color;\r
+\r
+ //! This type is the information that will be filled by insert_unique_check\r
+ struct insert_commit_data\r
+ {\r
+ insert_commit_data()\r
+ : link_left(false)\r
+ , node(0)\r
+ {}\r
+ bool link_left;\r
+ node_ptr node;\r
+ };\r
+\r
+ //! <b>Requires</b>: header1 and header2 must be the header nodes\r
+ //! of two trees.\r
+ //! \r
+ //! <b>Effects</b>: Swaps two trees. After the function header1 will contain \r
+ //! links to the second tree and header2 will have links to the first tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void swap_tree(node_ptr header1, node_ptr header2)\r
+ {\r
+ if(header1 == header2)\r
+ return;\r
+ \r
+ node_ptr tmp;\r
+\r
+ //Parent swap\r
+ tmp = NodeTraits::get_parent(header1);\r
+ NodeTraits::set_parent(header1, NodeTraits::get_parent(header2));\r
+ NodeTraits::set_parent(header2, tmp);\r
+ //Left swap\r
+ tmp = NodeTraits::get_left(header1);\r
+ NodeTraits::set_left(header1, NodeTraits::get_left(header2));\r
+ NodeTraits::set_left(header2, tmp);\r
+ //Right swap\r
+ tmp = NodeTraits::get_right(header1);\r
+ NodeTraits::set_right(header1, NodeTraits::get_right(header2));\r
+ NodeTraits::set_right(header2, tmp);\r
+\r
+ //Now test parent\r
+ node_ptr h1_parent(NodeTraits::get_parent(header1));\r
+ if(h1_parent){\r
+ NodeTraits::set_parent(h1_parent, header1);\r
+ }\r
+ else{\r
+ NodeTraits::set_left(header1, header1);\r
+ NodeTraits::set_right(header1, header1);\r
+ }\r
+\r
+ node_ptr h2_parent(NodeTraits::get_parent(header2));\r
+ if(NodeTraits::get_parent(header2)){\r
+ NodeTraits::set_parent(h2_parent, header2);\r
+ }\r
+ else{\r
+ NodeTraits::set_left(header2, header2);\r
+ NodeTraits::set_right(header2, header2);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: node is a tree node but not the header.\r
+ //! \r
+ //! <b>Effects</b>: Unlinks the node and rebalances the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity is constant time.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void unlink_and_rebalance(node_ptr node)\r
+ {\r
+ if(NodeTraits::get_parent(node)){\r
+ node_ptr x = NodeTraits::get_parent(node);\r
+ while(!is_header(x))\r
+ x = NodeTraits::get_parent(x);\r
+ erase(x, node);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: header is the header of a tree.\r
+ //! \r
+ //! <b>Effects</b>: Unlinks the leftmost node from the tree, and\r
+ //! updates the header link to the new leftmost node.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity is constant time.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Notes</b>: This function breaks the tree and the tree can\r
+ //! only be used for more unlink_leftmost_without_rebalance calls.\r
+ //! This function is normally used to achieve a step by step\r
+ //! controlled destruction of the tree.\r
+ static node_ptr unlink_leftmost_without_rebalance(node_ptr header)\r
+ {\r
+ node_ptr leftmost = NodeTraits::get_left(header);\r
+ if (leftmost == header)\r
+ return 0;\r
+ node_ptr leftmost_parent(NodeTraits::get_parent(leftmost));\r
+ node_ptr leftmost_right (NodeTraits::get_right(leftmost));\r
+ bool is_root = leftmost_parent == header;\r
+\r
+ if (leftmost_right){\r
+ NodeTraits::set_parent(leftmost_right, leftmost_parent);\r
+ NodeTraits::set_left(header, minimum(leftmost_right));\r
+\r
+ if (is_root)\r
+ NodeTraits::set_parent(header, leftmost_right);\r
+ else\r
+ NodeTraits::set_left(NodeTraits::get_parent(header), leftmost_right);\r
+ }\r
+ else if (is_root){\r
+ NodeTraits::set_parent(header, 0);\r
+ NodeTraits::set_left(header, header);\r
+ NodeTraits::set_right(header, header);\r
+ }\r
+ else{\r
+ NodeTraits::set_left(leftmost_parent, 0);\r
+ NodeTraits::set_left(header, leftmost_parent);\r
+ }\r
+ return leftmost;\r
+ }\r
+\r
+ //! <b>Requires</b>: node is a node of the tree or an node initialized\r
+ //! by init(...).\r
+ //! \r
+ //! <b>Effects</b>: Returns true if the node is initialized by init().\r
+ //! \r
+ //! <b>Complexity</b>: Constant time.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static bool unique(const_node_ptr node)\r
+ { return NodeTraits::get_parent(node) == 0; }\r
+\r
+ //! <b>Requires</b>: node is a node of the tree but it's not the header.\r
+ //! \r
+ //! <b>Effects</b>: Returns the number of nodes of the subtree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant time.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static std::size_t count(const_node_ptr node)\r
+ {\r
+ std::size_t result = 1;\r
+ if(NodeTraits::get_left(node))\r
+ result += count(NodeTraits::get_left(node));\r
+ if(NodeTraits::get_right(node))\r
+ result += count(NodeTraits::get_right(node));\r
+ return result;\r
+ }\r
+\r
+ //! <b>Requires</b>: p is a node from the tree except the header.\r
+ //! \r
+ //! <b>Effects</b>: Returns the next node of the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Average constant time.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static node_ptr next_node(node_ptr p)\r
+ {\r
+ node_ptr p_right(NodeTraits::get_right(p));\r
+ if(p_right){\r
+ return minimum(p_right);\r
+ }\r
+ else {\r
+ node_ptr x = NodeTraits::get_parent(p);\r
+ while(p == NodeTraits::get_right(x)){\r
+ p = x;\r
+ x = NodeTraits::get_parent(x);\r
+ }\r
+ return NodeTraits::get_right(p) != x ? x : uncast(p);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: p is a node from the tree except the leftmost node.\r
+ //! \r
+ //! <b>Effects</b>: Returns the previous node of the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Average constant time.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static node_ptr prev_node(node_ptr p)\r
+ {\r
+ if(is_header(p)){\r
+ return NodeTraits::get_right(p); // p is header, return rightmost\r
+ }\r
+ else if(NodeTraits::get_left(p)){\r
+ return maximum(NodeTraits::get_left(p));\r
+ }\r
+ else {\r
+ node_ptr x = NodeTraits::get_parent(p);\r
+ while(p == NodeTraits::get_left(x)){\r
+ p = x;\r
+ x = NodeTraits::get_parent(x);\r
+ }\r
+ return x;\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: node must not be part of any tree.\r
+ //!\r
+ //! <b>Effects</b>: After the function unique(node) == true.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //!\r
+ //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.\r
+ static void init(node_ptr node)\r
+ {\r
+ NodeTraits::set_parent(node, 0);\r
+ NodeTraits::set_left(node, 0);\r
+ NodeTraits::set_right(node, 0); \r
+ NodeTraits::set_color(node, NodeTraits::black());\r
+ };\r
+\r
+ //! <b>Requires</b>: node must not be part of any tree.\r
+ //!\r
+ //! <b>Effects</b>: Initializes the header to represent an empty tree.\r
+ //! unique(header) == true.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //!\r
+ //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.\r
+ static void init_header(node_ptr header)\r
+ {\r
+ NodeTraits::set_parent(header, 0);\r
+ NodeTraits::set_left(header, header);\r
+ NodeTraits::set_right(header, header); \r
+ NodeTraits::set_color(header, NodeTraits::red()); \r
+ };\r
+\r
+ //! <b>Requires</b>: header must be the header of a tree, z a node\r
+ //! of that tree and z != header.\r
+ //!\r
+ //! <b>Effects</b>: Erases node "z" from the tree with header "header".\r
+ //! \r
+ //! <b>Complexity</b>: Amortized constant time.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static node_ptr erase(node_ptr header, node_ptr z)\r
+ {\r
+ node_ptr y(z);\r
+ node_ptr x(0);\r
+ node_ptr x_parent(0);\r
+ node_ptr y_left(NodeTraits::get_left(y));\r
+ node_ptr y_right(NodeTraits::get_right(y));\r
+ if(!y_left){\r
+ x = y_right; // x might be null.\r
+ }\r
+ else if(!y_right){ // z has exactly one non-null child. y == z.\r
+ x = y_left; // x is not null.\r
+ }\r
+ else{\r
+ y = minimum (y_right);\r
+ x = NodeTraits::get_right(y); // x might be null.\r
+ }\r
+\r
+ if(y != z){\r
+ // relink y in place of z. y is z's successor\r
+ NodeTraits::set_parent(NodeTraits::get_left(z), y);\r
+ NodeTraits::set_left(y, NodeTraits::get_left(z));\r
+ if(y != NodeTraits::get_right(z)){\r
+ x_parent = NodeTraits::get_parent(y);\r
+ if(x)\r
+ NodeTraits::set_parent(x, NodeTraits::get_parent(y));\r
+ NodeTraits::set_left(NodeTraits::get_parent(y), x); // y must be a child of left_\r
+ NodeTraits::set_right(y, NodeTraits::get_right(z));\r
+ NodeTraits::set_parent(NodeTraits::get_right(z), y);\r
+ }\r
+ else\r
+ x_parent = y;\r
+ replace_own (z, y, header);\r
+ NodeTraits::set_parent(y, NodeTraits::get_parent(z));\r
+ color tmp(NodeTraits::get_color(y));\r
+ tmp = NodeTraits::get_color(y);\r
+ NodeTraits::set_color(y, NodeTraits::get_color(z));\r
+ NodeTraits::set_color(z, tmp);\r
+// std::swap(NodeTraits::get_color(y), NodeTraits::get_color(z));\r
+ y = z;\r
+ // y now points to node to be actually deleted\r
+ }\r
+ else { // y == z\r
+ x_parent = NodeTraits::get_parent(y);\r
+ if(x)\r
+ NodeTraits::set_parent(x, NodeTraits::get_parent(y));\r
+ replace_own (z, x, header);\r
+ if(NodeTraits::get_left(header) == z){\r
+ NodeTraits::set_left(header, NodeTraits::get_right(z) == 0 ? // z->get_left() must be null also\r
+ NodeTraits::get_parent(z) : // makes leftmost == header if z == root\r
+ minimum (x));\r
+ }\r
+ if(NodeTraits::get_right(header) == z){\r
+ NodeTraits::set_right(header, NodeTraits::get_left(z) == 0 ? // z->get_right() must be null also\r
+ NodeTraits::get_parent(z) : // makes rightmost == header if z == root\r
+ maximum(x));\r
+ }\r
+ }\r
+ if(NodeTraits::get_color(y) != NodeTraits::red()){\r
+ while(x != NodeTraits::get_parent(header) && (x == 0 || NodeTraits::get_color(x) == NodeTraits::black())){\r
+ if(x == NodeTraits::get_left(x_parent)){\r
+ node_ptr w = NodeTraits::get_right(x_parent);\r
+ if(NodeTraits::get_color(w) == NodeTraits::red()){\r
+ NodeTraits::set_color(w, NodeTraits::black());\r
+ NodeTraits::set_color(x_parent, NodeTraits::red());\r
+ rotate_left(x_parent, header);\r
+ w = NodeTraits::get_right(x_parent);\r
+ }\r
+ if((NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()) &&\r
+ (NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black())){\r
+ NodeTraits::set_color(w, NodeTraits::red());\r
+ x = x_parent;\r
+ x_parent = NodeTraits::get_parent(x_parent);\r
+ } \r
+ else {\r
+ if(NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()){\r
+ NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());\r
+ NodeTraits::set_color(w, NodeTraits::red());\r
+ rotate_right(w, header);\r
+ w = NodeTraits::get_right(x_parent);\r
+ }\r
+ NodeTraits::set_color(w, NodeTraits::get_color(x_parent));\r
+ NodeTraits::set_color(x_parent, NodeTraits::black());\r
+ if(NodeTraits::get_right(w))\r
+ NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());\r
+ rotate_left(x_parent, header);\r
+ break;\r
+ }\r
+ }\r
+ else {\r
+ // same as above, with right_ <-> left_.\r
+ node_ptr w = NodeTraits::get_left(x_parent);\r
+ if(NodeTraits::get_color(w) == NodeTraits::red()){\r
+ NodeTraits::set_color(w, NodeTraits::black());\r
+ NodeTraits::set_color(x_parent, NodeTraits::red());\r
+ rotate_right(x_parent, header);\r
+ w = NodeTraits::get_left(x_parent);\r
+ }\r
+ if((NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()) &&\r
+ (NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black())){\r
+ NodeTraits::set_color(w, NodeTraits::red());\r
+ x = x_parent;\r
+ x_parent = NodeTraits::get_parent(x_parent);\r
+ }\r
+ else {\r
+ if(NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()){\r
+ NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());\r
+ NodeTraits::set_color(w, NodeTraits::red());\r
+ rotate_left(w, header);\r
+ w = NodeTraits::get_left(x_parent);\r
+ }\r
+ NodeTraits::set_color(w, NodeTraits::get_color(x_parent));\r
+ NodeTraits::set_color(x_parent, NodeTraits::black());\r
+ if(NodeTraits::get_left(w))\r
+ NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());\r
+ rotate_right(x_parent, header);\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ if(x)\r
+ NodeTraits::set_color(x, NodeTraits::black());\r
+ }\r
+ return y;\r
+ }\r
+\r
+ //! <b>Requires</b>: "cloner" must be a function\r
+ //! object taking a node_ptr and returning a new cloned node of it. "destroyer" must\r
+ //! take a node_ptr and shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: First empties target tree calling \r
+ //! <tt>void destroyer::operator()(node_ptr)</tt> for every node of the tree\r
+ //! except the header.\r
+ //! \r
+ //! Then, duplicates the entire tree pointed by "source_header" cloning each\r
+ //! source node with <tt>node_ptr Cloner::operator()(node_ptr)</tt> to obtain \r
+ //! the nodes of the target tree. If "cloner" throws, the cloned target nodes\r
+ //! are destroyed using <tt>void destroyer(node_ptr)</tt>.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.\r
+ //! number of elements of tree target tree when calling this function.\r
+ //! \r
+ //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are destroyed.\r
+ template <class Cloner, class Destroyer>\r
+ static void clone_tree\r
+ (const_node_ptr source_header, node_ptr target_header, Cloner cloner, Destroyer destroyer)\r
+ {\r
+ if(!unique(target_header)){\r
+ node_ptr p;\r
+ while((p = unlink_leftmost_without_rebalance(target_header))){\r
+ destroyer(p);\r
+ }\r
+ }\r
+\r
+ node_ptr source_root = NodeTraits::get_parent(source_header);\r
+ if(!source_root)\r
+ return;\r
+\r
+ NodeTraits::set_parent\r
+ ( target_header\r
+ , deep_clone_node(source_root, target_header, cloner, destroyer));\r
+ NodeTraits::set_left(target_header, minimum(NodeTraits::get_parent(target_header)));\r
+ NodeTraits::set_right(target_header, maximum(NodeTraits::get_parent(target_header)));\r
+ }\r
+\r
+ //! <b>Requires</b>: "header" must be the header node of a tree.\r
+ //! KeyNodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.\r
+ //!\r
+ //! <b>Effects</b>: Returns an node_ptr to the first element that is\r
+ //! not less than "key" according to "comp" or "header" if that element does\r
+ //! not exist.\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: If "comp" throws.\r
+ template<class KeyType, class KeyNodePtrCompare>\r
+ static node_ptr lower_bound\r
+ (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)\r
+ {\r
+ node_ptr y = uncast(header);\r
+ node_ptr x = NodeTraits::get_parent(header);\r
+ while(x){\r
+ if(comp(x, key)){\r
+ x = NodeTraits::get_right(x);\r
+ }\r
+ else {\r
+ y = x;\r
+ x = NodeTraits::get_left(x);\r
+ }\r
+ }\r
+ return y;\r
+ }\r
+\r
+ //! <b>Requires</b>: "header" must be the header node of a tree.\r
+ //! KeyNodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.\r
+ //!\r
+ //! <b>Effects</b>: Returns an node_ptr to the first element that is greater\r
+ //! than "key" according to "comp" or "header" if that element does not exist.\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: If "comp" throws.\r
+ template<class KeyType, class KeyNodePtrCompare>\r
+ static node_ptr upper_bound\r
+ (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)\r
+ {\r
+ node_ptr y = uncast(header);\r
+ node_ptr x = NodeTraits::get_parent(header);\r
+ while(x){\r
+ if(comp(key, x)){\r
+ y = x;\r
+ x = NodeTraits::get_left(x);\r
+ }\r
+ else {\r
+ x = NodeTraits::get_right(x);\r
+ }\r
+ }\r
+ return y;\r
+ }\r
+\r
+ //! <b>Requires</b>: "header" must be the header node of a tree.\r
+ //! KeyNodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.\r
+ //!\r
+ //! <b>Effects</b>: Returns an node_ptr to the element that is equivalent to\r
+ //! "key" according to "comp" or "header" if that element does not exist.\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: If "comp" throws.\r
+ template<class KeyType, class KeyNodePtrCompare>\r
+ static node_ptr find\r
+ (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)\r
+ {\r
+ node_ptr end = uncast(header);\r
+ node_ptr y = lower_bound(header, key, comp);\r
+ return (y == end || comp(key, y)) ? end : y;\r
+ }\r
+\r
+ //! <b>Requires</b>: "header" must be the header node of a tree.\r
+ //! KeyNodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.\r
+ //!\r
+ //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing\r
+ //! all elements that are equivalent to "key" according to "comp" or an\r
+ //! empty range that indicates the position where those elements would be\r
+ //! if they there are no equivalent elements.\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: If "comp" throws.\r
+ template<class KeyType, class KeyNodePtrCompare>\r
+ static std::pair<node_ptr, node_ptr> equal_range\r
+ (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)\r
+ {\r
+ node_ptr y = uncast(header);\r
+ node_ptr x = NodeTraits::get_parent(header);\r
+\r
+ while(x){\r
+ if(comp(x, key)){\r
+ x = NodeTraits::get_right(x);\r
+ }\r
+ else if(comp(key, x)){\r
+ y = x;\r
+ x = NodeTraits::get_left(x);\r
+ }\r
+ else{\r
+ node_ptr xu(x), yu(y);\r
+ y = x, x = NodeTraits::get_left(x);\r
+ xu = NodeTraits::get_right(xu);\r
+\r
+ while(x){\r
+ if(comp(x, key)){\r
+ x = NodeTraits::get_right(x);\r
+ }\r
+ else {\r
+ y = x;\r
+ x = NodeTraits::get_left(x);\r
+ }\r
+ }\r
+\r
+ while(xu){\r
+ if(comp(key, xu)){\r
+ yu = xu;\r
+ xu = NodeTraits::get_left(xu);\r
+ }\r
+ else {\r
+ xu = NodeTraits::get_right(xu);\r
+ }\r
+ }\r
+ return std::pair<node_ptr,node_ptr>(y, yu);\r
+ }\r
+ }\r
+ return std::pair<node_ptr,node_ptr>(y, y);\r
+ }\r
+\r
+ //! <b>Requires</b>: "h" must be the header node of a tree.\r
+ //! NodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. NodePtrCompare compares two node_ptrs.\r
+ //!\r
+ //! <b>Effects</b>: Inserts new_node into the tree before the upper bound\r
+ //! according to "comp".\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for insert element is at\r
+ //! most logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: If "comp" throws.\r
+ template<class NodePtrCompare>\r
+ static node_ptr insert_equal_upper_bound\r
+ (node_ptr h, node_ptr new_node, NodePtrCompare comp)\r
+ {\r
+ node_ptr y(h);\r
+ node_ptr x(NodeTraits::get_parent(y));\r
+\r
+ while(x){\r
+ y = x;\r
+ x = comp(new_node, x) ? \r
+ NodeTraits::get_left(x) : NodeTraits::get_right(x);\r
+ }\r
+\r
+ bool link_left = (y == h) || \r
+ comp(new_node, y);\r
+ link_and_balance(new_node, y, link_left, h);\r
+ return new_node;\r
+ }\r
+\r
+ //! <b>Requires</b>: "h" must be the header node of a tree.\r
+ //! NodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. NodePtrCompare compares two node_ptrs.\r
+ //!\r
+ //! <b>Effects</b>: Inserts new_node into the tree before the lower bound\r
+ //! according to "comp".\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for insert element is at\r
+ //! most logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: If "comp" throws.\r
+ template<class NodePtrCompare>\r
+ static node_ptr insert_equal_lower_bound\r
+ (node_ptr h, node_ptr new_node, NodePtrCompare comp)\r
+ {\r
+ node_ptr y(h);\r
+ node_ptr x(NodeTraits::get_parent(y));\r
+\r
+ while(x){\r
+ y = x;\r
+ x = !comp(x, new_node) ? \r
+ NodeTraits::get_left(x) : NodeTraits::get_right(x);\r
+ }\r
+\r
+ bool link_left = (y == h) || \r
+ !comp(y, new_node);\r
+ link_and_balance(new_node, y, link_left, h);\r
+ return new_node;\r
+ }\r
+\r
+ //! <b>Requires</b>: "header" must be the header node of a tree.\r
+ //! NodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from\r
+ //! the "header"'s tree.\r
+ //! \r
+ //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to\r
+ //! where it will be inserted. If "hint" is the upper_bound\r
+ //! the insertion takes constant time (two comparisons in the worst case).\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic in general, but it is amortized\r
+ //! constant time if new_node is inserted immediately before "hint".\r
+ //! \r
+ //! <b>Throws</b>: If "comp" throws.\r
+ template<class NodePtrCompare>\r
+ static node_ptr insert_equal\r
+ (node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp)\r
+ {\r
+ if(hint == header || !comp(hint, new_node)){\r
+ node_ptr prev(hint);\r
+ if(hint == NodeTraits::get_left(header) || \r
+ !comp(new_node, (prev = prev_node(hint)))){\r
+ bool link_left = unique(header) || !NodeTraits::get_left(hint);\r
+ link_and_balance(new_node, link_left ? hint : prev, link_left, header);\r
+ return new_node;\r
+ }\r
+ else{\r
+ return insert_equal_upper_bound(header, new_node, comp);\r
+ }\r
+ }\r
+ else{\r
+ return insert_equal_lower_bound(header, new_node, comp);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: "header" must be the header node of a tree.\r
+ //! KeyNodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. NodePtrCompare compares KeyType with a node_ptr.\r
+ //! \r
+ //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the\r
+ //! tree according to "comp" and obtains the needed information to realize\r
+ //! a constant-time node insertion if there is no equivalent node.\r
+ //!\r
+ //! <b>Returns</b>: If an equivalent node is already present\r
+ //! returns a pair containing a node_ptr to the already present node\r
+ //! and false. If there is not equivalent key can be inserted returns true\r
+ //! in the returned pair's boolean and fills "commit_data" that is meant to\r
+ //! be used with the "insert_commit" function to achieve a constant-time\r
+ //! insertion function.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity is at most logarithmic.\r
+ //!\r
+ //! <b>Throws</b>: If "comp" throws.\r
+ //! \r
+ //! <b>Notes</b>: This function is used to improve performance when constructing\r
+ //! a node is expensive and the user does not want to have two equivalent nodes\r
+ //! in the tree: if an equivalent node is already present\r
+ //! the constructed object must be discarded. Many times, the part of the\r
+ //! node that is used to impose the order is much cheaper to construct\r
+ //! than the node and this function offers the possibility to use that part\r
+ //! to check if the insertion will be successful.\r
+ //!\r
+ //! If the check is successful, the user can construct the node and use\r
+ //! "insert_commit" to insert the node in constant-time. This gives a total\r
+ //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).\r
+ //!\r
+ //! "commit_data" remains valid for a subsequent "insert_unique_commit" only\r
+ //! if no more objects are inserted or erased from the set.\r
+ template<class KeyType, class KeyNodePtrCompare>\r
+ static std::pair<node_ptr, bool> insert_unique_check\r
+ (const_node_ptr header, const KeyType &key\r
+ ,KeyNodePtrCompare comp, insert_commit_data &commit_data)\r
+ {\r
+ node_ptr h(uncast(header));\r
+ node_ptr y(h);\r
+ node_ptr x(NodeTraits::get_parent(y));\r
+ node_ptr prev(0);\r
+\r
+ //Find the upper bound, cache the previous value and if we should\r
+ //store it in the left or right node\r
+ bool left_child = true;\r
+ while(x){\r
+ y = x;\r
+ x = (left_child = comp(key, x)) ? \r
+ NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x));\r
+ }\r
+\r
+ //Since we've found the upper bound there is no other value with the same key if:\r
+ // - There is no previous node\r
+ // - The previous node is less than the key\r
+ if(!prev || comp(prev, key)){\r
+ commit_data.link_left = left_child;\r
+ commit_data.node = y;\r
+ return std::pair<node_ptr, bool>(node_ptr(), true);\r
+ }\r
+ //If the previous value was not less than key, it means that it's equal\r
+ //(because we've checked the upper bound)\r
+ else{\r
+ return std::pair<node_ptr, bool>(prev, false);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: "header" must be the header node of a tree.\r
+ //! KeyNodePtrCompare is a function object that induces a strict weak\r
+ //! ordering compatible with the strict weak ordering used to create the\r
+ //! the tree. NodePtrCompare compares KeyType with a node_ptr.\r
+ //! "hint" is node from the "header"'s tree.\r
+ //! \r
+ //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the\r
+ //! tree according to "comp" using "hint" as a hint to where it should be\r
+ //! inserted and obtains the needed information to realize\r
+ //! a constant-time node insertion if there is no equivalent node. \r
+ //! If "hint" is the upper_bound the function has constant time \r
+ //! complexity (two comparisons in the worst case).\r
+ //!\r
+ //! <b>Returns</b>: If an equivalent node is already present\r
+ //! returns a pair containing a node_ptr to the already present node\r
+ //! and false. If there is not equivalent key can be inserted returns true\r
+ //! in the returned pair's boolean and fills "commit_data" that is meant to\r
+ //! be used with the "insert_commit" function to achieve a constant-time\r
+ //! insertion function.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is\r
+ //! amortized constant time if new_node should be inserted immediately before "hint".\r
+ //!\r
+ //! <b>Throws</b>: If "comp" throws.\r
+ //! \r
+ //! <b>Notes</b>: This function is used to improve performance when constructing\r
+ //! a node is expensive and the user does not want to have two equivalent nodes\r
+ //! in the tree: if an equivalent node is already present\r
+ //! the constructed object must be discarded. Many times, the part of the\r
+ //! node that is used to impose the order is much cheaper to construct\r
+ //! than the node and this function offers the possibility to use that part\r
+ //! to check if the insertion will be successful.\r
+ //!\r
+ //! If the check is successful, the user can construct the node and use\r
+ //! "insert_commit" to insert the node in constant-time. This gives a total\r
+ //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).\r
+ //!\r
+ //! "commit_data" remains valid for a subsequent "insert_unique_commit" only\r
+ //! if no more objects are inserted or erased from the set.\r
+ template<class KeyType, class KeyNodePtrCompare>\r
+ static std::pair<node_ptr, bool> insert_unique_check\r
+ (const_node_ptr header, node_ptr hint, const KeyType &key\r
+ ,KeyNodePtrCompare comp, insert_commit_data &commit_data)\r
+ {\r
+ //hint must be bigger than the key\r
+ if(hint == header || comp(key, hint)){\r
+ node_ptr prev = hint;\r
+ //The previous value should be less than the key\r
+ if(prev == NodeTraits::get_left(header) || comp((prev = prev_node(hint)), key)){\r
+ commit_data.link_left = unique(header) || !NodeTraits::get_left(hint);\r
+ commit_data.node = commit_data.link_left ? hint : prev;\r
+ return std::pair<node_ptr, bool>(node_ptr(), true);\r
+ }\r
+ else{\r
+ return insert_unique_check(header, key, comp, commit_data);\r
+ //return std::pair<node_ptr, bool>(prev, false);\r
+ }\r
+ }\r
+ //The hint was wrong, use hintless insert\r
+ else{\r
+ return insert_unique_check(header, key, comp, commit_data);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: "header" must be the header node of a tree.\r
+ //! "commit_data" must have been obtained from a previous call to\r
+ //! "insert_unique_check". No objects should have been inserted or erased\r
+ //! from the set between the "insert_unique_check" that filled "commit_data"\r
+ //! and the call to "insert_commit". \r
+ //! \r
+ //! \r
+ //! <b>Effects</b>: Inserts new_node in the set using the information obtained\r
+ //! from the "commit_data" that a previous "insert_check" filled.\r
+ //!\r
+ //! <b>Complexity</b>: Constant time.\r
+ //!\r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been\r
+ //! previously executed to fill "commit_data". No value should be inserted or\r
+ //! erased between the "insert_check" and "insert_commit" calls.\r
+ static void insert_unique_commit\r
+ (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data)\r
+ {\r
+ //Check if commit_data has not been initialized by a insert_unique_check call.\r
+ BOOST_ASSERT(commit_data.node != 0);\r
+ link_and_balance(new_value, commit_data.node, commit_data.link_left, header);\r
+ }\r
+\r
+ private:\r
+\r
+ static node_ptr uncast(const_node_ptr ptr)\r
+ {\r
+ using boost::get_pointer;\r
+ return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
+ }\r
+\r
+ //! <b>Requires</b>: z is the node to be inserted, par is its parent,\r
+ //! left, indicates if z should be a left node of par and header is the header\r
+ //! of the tree.\r
+ //! \r
+ //! <b>Effects</b>: If left is true links z as a left child of par or as a right\r
+ //! child otherwise. After that rebalances the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Average constant time.???\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void link_and_balance (node_ptr z, node_ptr par, bool left, node_ptr header)\r
+ {\r
+ if(par == header){\r
+ NodeTraits::set_parent(header, z);\r
+ NodeTraits::set_right(header, z);\r
+ NodeTraits::set_left(header, z);\r
+ }\r
+ else if(left){\r
+ NodeTraits::set_left(par, z);\r
+ if(par == NodeTraits::get_left(header))\r
+ NodeTraits::set_left(header, z);\r
+ }\r
+ else{\r
+ NodeTraits::set_right(par, z);\r
+ if(par == NodeTraits::get_right(header))\r
+ NodeTraits::set_right(header, z);\r
+ }\r
+ NodeTraits::set_parent(z, par);\r
+ NodeTraits::set_right(z, 0);\r
+ NodeTraits::set_left(z, 0);\r
+ rebalance(z, header);\r
+ }\r
+\r
+ //! <b>Requires</b>: p is a node of a tree but not the header.\r
+ //! \r
+ //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic to the size of the subtree.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static node_ptr minimum (node_ptr p)\r
+ {\r
+ for(node_ptr p_left = NodeTraits::get_left(p)\r
+ ;p_left\r
+ ;p_left = NodeTraits::get_left(p)){\r
+ p = p_left;\r
+ }\r
+ return p;\r
+ }\r
+\r
+ //! <b>Requires</b>: p is a node of a tree but not the header.\r
+ //! \r
+ //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic to the size of the subtree.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static node_ptr maximum(node_ptr p)\r
+ {\r
+ for(node_ptr p_right = NodeTraits::get_right(p)\r
+ ;p_right\r
+ ;p_right = NodeTraits::get_right(p)){\r
+ p = p_right;\r
+ }\r
+ return p;\r
+ }\r
+\r
+ //! <b>Requires</b>: p is a node of a tree.\r
+ //! \r
+ //! <b>Effects</b>: Returns true if p is the header of the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static bool is_header(const_node_ptr p)\r
+ {\r
+ return NodeTraits::get_color(p) == NodeTraits::red() && \r
+ NodeTraits::get_parent(NodeTraits::get_parent(p)) == p;\r
+ }\r
+\r
+ //! <b>Requires</b>: p is a node of a tree.\r
+ //! \r
+ //! <b>Effects</b>: Returns true if p is a left child.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static bool is_left_child(node_ptr p)\r
+ { return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; }\r
+\r
+ //! <b>Requires</b>: p is a node of a tree.\r
+ //! \r
+ //! <b>Effects</b>: Returns true if p is a right child.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static bool is_right_child (node_ptr p)\r
+ { return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; }\r
+\r
+ static void replace_own (node_ptr own, node_ptr x, node_ptr header)\r
+ {\r
+ if(NodeTraits::get_parent(header) == own)\r
+ NodeTraits::set_parent(header, x);\r
+ else if(is_left_child(own))\r
+ NodeTraits::set_left(NodeTraits::get_parent(own), x);\r
+ else\r
+ NodeTraits::set_right(NodeTraits::get_parent(own), x);\r
+ }\r
+\r
+ static void rotate_left(node_ptr p, node_ptr header)\r
+ {\r
+ node_ptr x = NodeTraits::get_right(p);\r
+ NodeTraits::set_right(p, NodeTraits::get_left(x));\r
+ if(NodeTraits::get_left(x) != 0)\r
+ NodeTraits::set_parent(NodeTraits::get_left(x), p);\r
+ NodeTraits::set_parent(x, NodeTraits::get_parent(p));\r
+ replace_own (p, x, header);\r
+ NodeTraits::set_left(x, p);\r
+ NodeTraits::set_parent(p, x);\r
+ }\r
+\r
+ static void rotate_right(node_ptr p, node_ptr header)\r
+ {\r
+ node_ptr x(NodeTraits::get_left(p));\r
+ node_ptr x_right(NodeTraits::get_right(x));\r
+ NodeTraits::set_left(p, x_right);\r
+ if(x_right)\r
+ NodeTraits::set_parent(x_right, p);\r
+ NodeTraits::set_parent(x, NodeTraits::get_parent(p));\r
+ replace_own (p, x, header);\r
+ NodeTraits::set_right(x, p);\r
+ NodeTraits::set_parent(p, x);\r
+ }\r
+\r
+ static void rebalance(node_ptr p, node_ptr header)\r
+ {\r
+ NodeTraits::set_color(p, NodeTraits::red());\r
+ while(p != NodeTraits::get_parent(header) && NodeTraits::get_color(NodeTraits::get_parent(p)) == NodeTraits::red()){\r
+ node_ptr p_parent(NodeTraits::get_parent(p));\r
+ node_ptr p_parent_parent(NodeTraits::get_parent(p_parent));\r
+ if(is_left_child(p_parent)){\r
+ node_ptr x = NodeTraits::get_right(p_parent_parent);\r
+ if(x && NodeTraits::get_color(x) == NodeTraits::red()){\r
+ NodeTraits::set_color(p_parent, NodeTraits::black());\r
+ NodeTraits::set_color(p_parent_parent, NodeTraits::red());\r
+ NodeTraits::set_color(x, NodeTraits::black());\r
+ p = p_parent_parent;\r
+ }\r
+ else {\r
+ if(!is_left_child(p)){\r
+ p = p_parent;\r
+ rotate_left(p, header);\r
+ }\r
+ node_ptr new_p_parent(NodeTraits::get_parent(p));\r
+ node_ptr new_p_parent_parent(NodeTraits::get_parent(new_p_parent));\r
+ NodeTraits::set_color(new_p_parent, NodeTraits::black());\r
+ NodeTraits::set_color(new_p_parent_parent, NodeTraits::red());\r
+ rotate_right(new_p_parent_parent, header);\r
+ }\r
+ }\r
+ else{\r
+ node_ptr x = NodeTraits::get_left(p_parent_parent);\r
+ if(x && NodeTraits::get_color(x) == NodeTraits::red()){\r
+ NodeTraits::set_color(p_parent, NodeTraits::black());\r
+ NodeTraits::set_color(p_parent_parent, NodeTraits::red());\r
+ NodeTraits::set_color(x, NodeTraits::black());\r
+ p = p_parent_parent;\r
+ }\r
+ else{\r
+ if(is_left_child(p)){\r
+ p = p_parent;\r
+ rotate_right(p, header);\r
+ }\r
+ node_ptr new_p_parent(NodeTraits::get_parent(p));\r
+ node_ptr new_p_parent_parent(NodeTraits::get_parent(new_p_parent));\r
+ NodeTraits::set_color(new_p_parent, NodeTraits::black());\r
+ NodeTraits::set_color(new_p_parent_parent, NodeTraits::red());\r
+ rotate_left(new_p_parent_parent, header);\r
+ }\r
+ }\r
+ }\r
+ NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black());\r
+ }\r
+\r
+ template <class Cloner, class Destroyer>\r
+ static node_ptr deep_clone_node\r
+ (node_ptr source_root, node_ptr new_parent, Cloner cloner, Destroyer destroyer)\r
+ {\r
+ // structural copy. source_root and new_parent must be non-null.\r
+ node_ptr top = cloner(source_root);\r
+ NodeTraits::set_parent(top, new_parent);\r
+ \r
+ BOOST_TRY {\r
+ if(NodeTraits::get_right(source_root)){\r
+ NodeTraits::set_right\r
+ (top, deep_clone_node(NodeTraits::get_right(source_root), top\r
+ ,cloner, destroyer));\r
+ }\r
+ new_parent = top;\r
+ source_root = NodeTraits::get_left(source_root);\r
+\r
+ while(source_root){\r
+ node_ptr y = cloner(source_root);\r
+ NodeTraits::set_left(new_parent, y);\r
+ NodeTraits::set_parent(y, new_parent);\r
+\r
+ if(NodeTraits::get_right(source_root)){\r
+ NodeTraits::set_right(y, deep_clone_node(NodeTraits::get_right(source_root), y\r
+ ,cloner, destroyer));\r
+ }\r
+ new_parent = y;\r
+ source_root = NodeTraits::get_left(source_root);\r
+ }\r
+ }\r
+ BOOST_CATCH(...){\r
+ deep_destroy_node(top, destroyer);\r
+ BOOST_RETHROW;\r
+ }\r
+ BOOST_CATCH_END\r
+ return top;\r
+ }\r
+\r
+ template<class Destroyer>\r
+ static void deep_destroy_node(node_ptr x, Destroyer destroyer)\r
+ {\r
+ // erase without rebalancing\r
+ while(x){\r
+ deep_destroy_node(NodeTraits::get_right(x), destroyer);\r
+ node_ptr y = NodeTraits::get_left(x);\r
+ destroyer(x);\r
+ x = y;\r
+ }\r
+ }\r
+};\r
+\r
+} //namespace intrusive \r
+} //namespace boost \r
+\r
+#include "detail/config_end.hpp"\r
+\r
+#endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP\r
projects / senf.git / blobdiff