boost/intrusive/rbtree_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////\r
   2 //\r
   3 // (C) Copyright Olaf Krzikalla 2004-2006.\r
   4 // (C) Copyright Ion Gaztañaga  2006-2007.\r
   5 //\r
   6 // Distributed under the Boost Software License, Version 1.0.\r
   7 //    (See accompanying file LICENSE_1_0.txt or copy at\r
   8 //          http://www.boost.org/LICENSE_1_0.txt)\r
   9 //\r
  10 // See http://www.boost.org/libs/intrusive for documentation.\r
  11 //\r
  12 /////////////////////////////////////////////////////////////////////////////\r
  13 // The internal implementation of red-black trees is based on that of SGI STL\r
  14 // stl_tree.h file: \r
  15 //\r
  16 // Copyright (c) 1996,1997\r
  17 // Silicon Graphics Computer Systems, Inc.\r
  18 //\r
  19 // Permission to use, copy, modify, distribute and sell this software\r
  20 // and its documentation for any purpose is hereby granted without fee,\r
  21 // provided that the above copyright notice appear in all copies and\r
  22 // that both that copyright notice and this permission notice appear\r
  23 // in supporting documentation.  Silicon Graphics makes no\r
  24 // representations about the suitability of this software for any\r
  25 // purpose.  It is provided "as is" without express or implied warranty.\r
  26 //\r
  27 //\r
  28 // Copyright (c) 1994\r
  29 // Hewlett-Packard Company\r
  30 //\r
  31 // Permission to use, copy, modify, distribute and sell this software\r
  32 // and its documentation for any purpose is hereby granted without fee,\r
  33 // provided that the above copyright notice appear in all copies and\r
  34 // that both that copyright notice and this permission notice appear\r
  35 // in supporting documentation.  Hewlett-Packard Company makes no\r
  36 // representations about the suitability of this software for any\r
  37 // purpose.  It is provided "as is" without express or implied warranty.\r
  38 \r
  39 #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP\r
  40 #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP\r
  41 \r
  42 #include "detail/config_begin.hpp"\r
  43 #include <iterator>\r
  44 #include <boost/assert.hpp>\r
  45 #include "detail/pointer_type.hpp"\r
  46 #include "detail/pointer_to_other.hpp"\r
  47 #include <boost/get_pointer.hpp>\r
  48 #include <boost/type_traits/alignment_of.hpp>\r
  49 #include <cstddef>\r
  50 #include <boost/detail/no_exceptions_support.hpp>\r
  51 \r
  52 \r
  53 namespace boost {\r
  54 namespace intrusive {\r
  55 \r
  56 //! rbtree_algorithms provides basic algorithms to manipulate \r
  57 //! nodes forming a red-black tree. The insertion and deletion algorithms are
  58 //! based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms
  59 //! (MIT Press, 1990), except that
  60 //!
  61 //! (1) the header node is maintained with links not only to the root
  62 //! but also to the leftmost node of the tree, to enable constant time
  63 //! begin(), and to the rightmost node of the tree, to enable linear time
  64 //! performance when used with the generic set algorithms (set_union,
  65 //! etc.);
  66 //!
  67 //! (2) when a node being deleted has two children its successor node is
  68 //! relinked into its place, rather than copied, so that the only
  69 //! iterators invalidated are those referring to the deleted node.\r
  70 //!\r
  71 //! rbtree_algorithms is configured with a NodeTraits class, which capsulates the\r
  72 //! information about the node to be manipulated. NodeTraits must support the\r
  73 //! following interface:\r
  74 //!\r
  75 //! <b>Typedefs</b>:\r
  76 //!\r
  77 //! <tt>node</tt>: The type of the node that forms the circular list\r
  78 //!\r
  79 //! <tt>node_ptr</tt>: A pointer to a node\r
  80 //!\r
  81 //! <tt>const_node_ptr</tt>: A pointer to a const node\r
  82 //!\r
  83 //! <tt>color</tt>: The type that can store the color of a node\r
  84 //!\r
  85 //! <b>Static functions</b>:\r
  86 //!\r
  87 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>\r
  88 //! \r
  89 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>\r
  90 //!\r
  91 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>\r
  92 //! \r
  93 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>\r
  94 //!\r
  95 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>\r
  96 //! \r
  97 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>\r
  98 //! \r
  99 //! <tt>static color get_color(const_node_ptr n);</tt>\r
 100 //! \r
 101 //! <tt>static void set_color(node_ptr n, color c);</tt>\r
 102 //! \r
 103 //! <tt>static color black();</tt>\r
 104 //! \r
 105 //! <tt>static color red();</tt>\r
 106 template<class NodeTraits>\r
 107 class rbtree_algorithms\r
 108 {\r
 109    private:\r
 110    typedef typename NodeTraits::node            node;\r
 111 \r
 112    public:\r
 113    typedef typename NodeTraits::node_ptr        node_ptr;\r
 114    typedef typename NodeTraits::const_node_ptr  const_node_ptr;\r
 115    typedef typename NodeTraits::color           color;\r
 116 \r
 117    //! This type is the information that will be filled by insert_unique_check\r
 118    struct insert_commit_data\r
 119    {\r
 120       insert_commit_data()\r
 121          :  link_left(false)\r
 122          ,  node(0)\r
 123       {}\r
 124       bool     link_left;\r
 125       node_ptr node;\r
 126    };\r
 127 \r
 128    //! <b>Requires</b>: header1 and header2 must be the header nodes\r
 129    //!  of two trees.\r
 130    //! \r
 131    //! <b>Effects</b>: Swaps two trees. After the function header1 will contain \r
 132    //!   links to the second tree and header2 will have links to the first tree.\r
 133    //! \r
 134    //! <b>Complexity</b>: Constant. \r
 135    //! \r
 136    //! <b>Throws</b>: Nothing.\r
 137    static void swap_tree(node_ptr header1, node_ptr header2)\r
 138    {\r
 139       if(header1 == header2)\r
 140          return;\r
 141    \r
 142       node_ptr tmp;\r
 143 \r
 144       //Parent swap\r
 145       tmp = NodeTraits::get_parent(header1);\r
 146       NodeTraits::set_parent(header1, NodeTraits::get_parent(header2));\r
 147       NodeTraits::set_parent(header2, tmp);\r
 148       //Left swap\r
 149       tmp = NodeTraits::get_left(header1);\r
 150       NodeTraits::set_left(header1, NodeTraits::get_left(header2));\r
 151       NodeTraits::set_left(header2, tmp);\r
 152       //Right swap\r
 153       tmp = NodeTraits::get_right(header1);\r
 154       NodeTraits::set_right(header1, NodeTraits::get_right(header2));\r
 155       NodeTraits::set_right(header2, tmp);\r
 156 \r
 157       //Now test parent\r
 158       node_ptr h1_parent(NodeTraits::get_parent(header1));\r
 159       if(h1_parent){\r
 160          NodeTraits::set_parent(h1_parent, header1);\r
 161       }\r
 162       else{\r
 163          NodeTraits::set_left(header1, header1);\r
 164          NodeTraits::set_right(header1, header1);\r
 165       }\r
 166 \r
 167       node_ptr h2_parent(NodeTraits::get_parent(header2));\r
 168       if(NodeTraits::get_parent(header2)){\r
 169          NodeTraits::set_parent(h2_parent, header2);\r
 170       }\r
 171       else{\r
 172          NodeTraits::set_left(header2, header2);\r
 173          NodeTraits::set_right(header2, header2);\r
 174       }\r
 175    }\r
 176 \r
 177    //! <b>Requires</b>: node is a tree node but not the header.\r
 178    //! \r
 179    //! <b>Effects</b>: Unlinks the node and rebalances the tree.\r
 180    //! \r
 181    //! <b>Complexity</b>: Average complexity is constant time.\r
 182    //! \r
 183    //! <b>Throws</b>: Nothing.\r
 184    static void unlink_and_rebalance(node_ptr node)\r
 185    {\r
 186       if(NodeTraits::get_parent(node)){\r
 187          node_ptr x = NodeTraits::get_parent(node);\r
 188          while(!is_header(x))\r
 189             x = NodeTraits::get_parent(x);\r
 190          erase(x, node);\r
 191       }\r
 192    }\r
 193 \r
 194    //! <b>Requires</b>: header is the header of a tree.\r
 195    //! \r
 196    //! <b>Effects</b>: Unlinks the leftmost node from the tree, and\r
 197    //!   updates the header link to the new leftmost node.\r
 198    //! \r
 199    //! <b>Complexity</b>: Average complexity is constant time.\r
 200    //! \r
 201    //! <b>Throws</b>: Nothing.\r
 202    //! \r
 203    //! <b>Notes</b>: This function breaks the tree and the tree can\r
 204    //!   only be used for more unlink_leftmost_without_rebalance calls.\r
 205    //!   This function is normally used to achieve a step by step\r
 206    //!   controlled destruction of the tree.\r
 207    static node_ptr unlink_leftmost_without_rebalance(node_ptr header)\r
 208    {\r
 209       node_ptr leftmost = NodeTraits::get_left(header);\r
 210       if (leftmost == header)\r
 211          return 0;\r
 212       node_ptr leftmost_parent(NodeTraits::get_parent(leftmost));\r
 213       node_ptr leftmost_right (NodeTraits::get_right(leftmost));\r
 214       bool is_root = leftmost_parent == header;\r
 215 \r
 216       if (leftmost_right){\r
 217          NodeTraits::set_parent(leftmost_right, leftmost_parent);\r
 218          NodeTraits::set_left(header, minimum(leftmost_right));\r
 219 \r
 220          if (is_root)\r
 221             NodeTraits::set_parent(header, leftmost_right);\r
 222          else\r
 223             NodeTraits::set_left(NodeTraits::get_parent(header), leftmost_right);\r
 224       }\r
 225       else if (is_root){\r
 226          NodeTraits::set_parent(header, 0);\r
 227          NodeTraits::set_left(header,  header);\r
 228          NodeTraits::set_right(header, header);\r
 229       }\r
 230       else{\r
 231          NodeTraits::set_left(leftmost_parent, 0);\r
 232          NodeTraits::set_left(header, leftmost_parent);\r
 233       }\r
 234       return leftmost;\r
 235    }\r
 236 \r
 237    //! <b>Requires</b>: node is a node of the tree or an node initialized\r
 238    //!   by init(...).\r
 239    //! \r
 240    //! <b>Effects</b>: Returns true if the node is initialized by init().\r
 241    //! \r
 242    //! <b>Complexity</b>: Constant time.\r
 243    //! \r
 244    //! <b>Throws</b>: Nothing.\r
 245    static bool unique(const_node_ptr node)\r
 246    { return NodeTraits::get_parent(node) == 0; }\r
 247 \r
 248    //! <b>Requires</b>: node is a node of the tree but it's not the header.\r
 249    //! \r
 250    //! <b>Effects</b>: Returns the number of nodes of the subtree.\r
 251    //! \r
 252    //! <b>Complexity</b>: Constant time.\r
 253    //! \r
 254    //! <b>Throws</b>: Nothing.\r
 255    static std::size_t count(const_node_ptr node)\r
 256    {\r
 257       std::size_t result = 1;\r
 258       if(NodeTraits::get_left(node))\r
 259          result += count(NodeTraits::get_left(node));\r
 260       if(NodeTraits::get_right(node))\r
 261          result += count(NodeTraits::get_right(node));\r
 262       return result;\r
 263    }\r
 264 \r
 265    //! <b>Requires</b>: p is a node from the tree except the header.\r
 266    //! \r
 267    //! <b>Effects</b>: Returns the next node of the tree.\r
 268    //! \r
 269    //! <b>Complexity</b>: Average constant time.\r
 270    //! \r
 271    //! <b>Throws</b>: Nothing.\r
 272    static node_ptr next_node(node_ptr p)\r
 273    {\r
 274       node_ptr p_right(NodeTraits::get_right(p));\r
 275       if(p_right){\r
 276          return minimum(p_right);\r
 277       }\r
 278       else {\r
 279          node_ptr x = NodeTraits::get_parent(p);\r
 280          while(p == NodeTraits::get_right(x)){\r
 281             p = x;\r
 282             x = NodeTraits::get_parent(x);\r
 283          }\r
 284          return NodeTraits::get_right(p) != x ? x : uncast(p);\r
 285       }\r
 286    }\r
 287 \r
 288    //! <b>Requires</b>: p is a node from the tree except the leftmost node.\r
 289    //! \r
 290    //! <b>Effects</b>: Returns the previous node of the tree.\r
 291    //! \r
 292    //! <b>Complexity</b>: Average constant time.\r
 293    //! \r
 294    //! <b>Throws</b>: Nothing.\r
 295    static node_ptr prev_node(node_ptr p)\r
 296    {\r
 297       if(is_header(p)){\r
 298          return NodeTraits::get_right(p); // p is header, return rightmost\r
 299       }\r
 300       else if(NodeTraits::get_left(p)){\r
 301          return maximum(NodeTraits::get_left(p));\r
 302       }\r
 303       else {\r
 304          node_ptr x = NodeTraits::get_parent(p);\r
 305          while(p == NodeTraits::get_left(x)){\r
 306             p = x;\r
 307             x = NodeTraits::get_parent(x);\r
 308          }\r
 309          return x;\r
 310       }\r
 311    }\r
 312 \r
 313    //! <b>Requires</b>: node must not be part of any tree.\r
 314    //!\r
 315    //! <b>Effects</b>: After the function unique(node) == true.\r
 316    //! \r
 317    //! <b>Complexity</b>: Constant.\r
 318    //! \r
 319    //! <b>Throws</b>: Nothing.\r
 320    //!\r
 321    //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.\r
 322    static void init(node_ptr node)\r
 323    {\r
 324       NodeTraits::set_parent(node, 0);\r
 325       NodeTraits::set_left(node, 0);\r
 326       NodeTraits::set_right(node, 0); \r
 327       NodeTraits::set_color(node, NodeTraits::black());\r
 328    };\r
 329 \r
 330    //! <b>Requires</b>: node must not be part of any tree.\r
 331    //!\r
 332    //! <b>Effects</b>: Initializes the header to represent an empty tree.\r
 333    //!   unique(header) == true.\r
 334    //! \r
 335    //! <b>Complexity</b>: Constant.\r
 336    //! \r
 337    //! <b>Throws</b>: Nothing.\r
 338    //!\r
 339    //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.\r
 340    static void init_header(node_ptr header)\r
 341    {\r
 342       NodeTraits::set_parent(header, 0);\r
 343       NodeTraits::set_left(header, header);\r
 344       NodeTraits::set_right(header, header); \r
 345       NodeTraits::set_color(header, NodeTraits::red()); \r
 346    };\r
 347 \r
 348    //! <b>Requires</b>: header must be the header of a tree, z a node\r
 349    //!    of that tree and z != header.\r
 350    //!\r
 351    //! <b>Effects</b>: Erases node "z" from the tree with header "header".\r
 352    //! \r
 353    //! <b>Complexity</b>: Amortized constant time.\r
 354    //! \r
 355    //! <b>Throws</b>: Nothing.\r
 356    static node_ptr erase(node_ptr header, node_ptr z)\r
 357    {\r
 358       node_ptr y(z);\r
 359       node_ptr x(0);\r
 360       node_ptr x_parent(0);\r
 361       node_ptr y_left(NodeTraits::get_left(y));\r
 362       node_ptr y_right(NodeTraits::get_right(y));\r
 363       if(!y_left){\r
 364          x = y_right;    // x might be null.\r
 365       }\r
 366       else if(!y_right){ // z has exactly one non-null child. y == z.\r
 367          x = y_left;            // x is not null.\r
 368       }\r
 369       else{\r
 370          y = minimum (y_right);\r
 371          x = NodeTraits::get_right(y);          // x might be null.\r
 372       }\r
 373 \r
 374       if(y != z){\r
 375          // relink y in place of z.  y is z's successor\r
 376          NodeTraits::set_parent(NodeTraits::get_left(z), y);\r
 377          NodeTraits::set_left(y, NodeTraits::get_left(z));\r
 378          if(y != NodeTraits::get_right(z)){\r
 379             x_parent = NodeTraits::get_parent(y);\r
 380             if(x)\r
 381                NodeTraits::set_parent(x, NodeTraits::get_parent(y));\r
 382             NodeTraits::set_left(NodeTraits::get_parent(y), x);   // y must be a child of left_\r
 383             NodeTraits::set_right(y, NodeTraits::get_right(z));\r
 384             NodeTraits::set_parent(NodeTraits::get_right(z), y);\r
 385          }\r
 386          else\r
 387             x_parent = y;\r
 388          replace_own (z, y, header);\r
 389          NodeTraits::set_parent(y, NodeTraits::get_parent(z));\r
 390          color tmp(NodeTraits::get_color(y));\r
 391          tmp = NodeTraits::get_color(y);\r
 392          NodeTraits::set_color(y, NodeTraits::get_color(z));\r
 393          NodeTraits::set_color(z, tmp);\r
 394 //         std::swap(NodeTraits::get_color(y), NodeTraits::get_color(z));\r
 395          y = z;\r
 396          // y now points to node to be actually deleted\r
 397       }\r
 398       else {                        // y == z\r
 399          x_parent = NodeTraits::get_parent(y);\r
 400          if(x)\r
 401             NodeTraits::set_parent(x, NodeTraits::get_parent(y));\r
 402          replace_own (z, x, header);\r
 403          if(NodeTraits::get_left(header) == z){\r
 404             NodeTraits::set_left(header, NodeTraits::get_right(z) == 0 ?        // z->get_left() must be null also\r
 405                NodeTraits::get_parent(z) :  // makes leftmost == header if z == root\r
 406                minimum (x));\r
 407          }\r
 408          if(NodeTraits::get_right(header) == z){\r
 409             NodeTraits::set_right(header, NodeTraits::get_left(z) == 0 ?        // z->get_right() must be null also\r
 410                               NodeTraits::get_parent(z) :  // makes rightmost == header if z == root\r
 411                               maximum(x));\r
 412          }\r
 413       }\r
 414       if(NodeTraits::get_color(y) != NodeTraits::red()){\r
 415          while(x != NodeTraits::get_parent(header) && (x == 0 || NodeTraits::get_color(x) == NodeTraits::black())){\r
 416             if(x == NodeTraits::get_left(x_parent)){\r
 417                node_ptr w = NodeTraits::get_right(x_parent);\r
 418                if(NodeTraits::get_color(w) == NodeTraits::red()){\r
 419                   NodeTraits::set_color(w, NodeTraits::black());\r
 420                   NodeTraits::set_color(x_parent, NodeTraits::red());\r
 421                   rotate_left(x_parent, header);\r
 422                   w = NodeTraits::get_right(x_parent);\r
 423                }\r
 424                if((NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w))  == NodeTraits::black()) &&\r
 425                   (NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black())){\r
 426                   NodeTraits::set_color(w, NodeTraits::red());\r
 427                   x = x_parent;\r
 428                   x_parent = NodeTraits::get_parent(x_parent);\r
 429                } \r
 430                else {\r
 431                   if(NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()){\r
 432                      NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());\r
 433                      NodeTraits::set_color(w, NodeTraits::red());\r
 434                      rotate_right(w, header);\r
 435                      w = NodeTraits::get_right(x_parent);\r
 436                   }\r
 437                   NodeTraits::set_color(w, NodeTraits::get_color(x_parent));\r
 438                   NodeTraits::set_color(x_parent, NodeTraits::black());\r
 439                   if(NodeTraits::get_right(w))\r
 440                      NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());\r
 441                   rotate_left(x_parent, header);\r
 442                   break;\r
 443                }\r
 444             }\r
 445             else {\r
 446                // same as above, with right_ <-> left_.\r
 447                node_ptr w = NodeTraits::get_left(x_parent);\r
 448                if(NodeTraits::get_color(w) == NodeTraits::red()){\r
 449                   NodeTraits::set_color(w, NodeTraits::black());\r
 450                   NodeTraits::set_color(x_parent, NodeTraits::red());\r
 451                   rotate_right(x_parent, header);\r
 452                   w = NodeTraits::get_left(x_parent);\r
 453                }\r
 454                if((NodeTraits::get_right(w) == 0 || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()) &&\r
 455                   (NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black())){\r
 456                   NodeTraits::set_color(w, NodeTraits::red());\r
 457                   x = x_parent;\r
 458                   x_parent = NodeTraits::get_parent(x_parent);\r
 459                }\r
 460                else {\r
 461                   if(NodeTraits::get_left(w) == 0 || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()){\r
 462                      NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());\r
 463                      NodeTraits::set_color(w, NodeTraits::red());\r
 464                      rotate_left(w, header);\r
 465                      w = NodeTraits::get_left(x_parent);\r
 466                   }\r
 467                   NodeTraits::set_color(w, NodeTraits::get_color(x_parent));\r
 468                   NodeTraits::set_color(x_parent, NodeTraits::black());\r
 469                   if(NodeTraits::get_left(w))\r
 470                      NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());\r
 471                   rotate_right(x_parent, header);\r
 472                   break;\r
 473                }\r
 474             }\r
 475          }\r
 476          if(x)\r
 477             NodeTraits::set_color(x, NodeTraits::black());\r
 478       }\r
 479       return y;\r
 480    }\r
 481 \r
 482    //! <b>Requires</b>: "cloner" must be a function\r
 483    //!   object taking a node_ptr and returning a new cloned node of it. "destroyer" must\r
 484    //!   take a node_ptr and shouldn't throw.\r
 485    //!\r
 486    //! <b>Effects</b>: First empties target tree calling \r
 487    //!   <tt>void destroyer::operator()(node_ptr)</tt> for every node of the tree\r
 488    //!    except the header.\r
 489    //!    \r
 490    //!   Then, duplicates the entire tree pointed by "source_header" cloning each\r
 491    //!   source node with <tt>node_ptr Cloner::operator()(node_ptr)</tt> to obtain \r
 492    //!   the nodes of the target tree. If "cloner" throws, the cloned target nodes\r
 493    //!   are destroyed using <tt>void destroyer(node_ptr)</tt>.\r
 494    //! \r
 495    //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.\r
 496    //!   number of elements of tree target tree when calling this function.\r
 497    //! \r
 498    //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are destroyed.\r
 499    template <class Cloner, class Destroyer>\r
 500    static void clone_tree\r
 501       (const_node_ptr source_header, node_ptr target_header, Cloner cloner, Destroyer destroyer)\r
 502    {\r
 503       if(!unique(target_header)){\r
 504          node_ptr p;\r
 505          while((p = unlink_leftmost_without_rebalance(target_header))){\r
 506             destroyer(p);\r
 507          }\r
 508       }\r
 509 \r
 510       node_ptr source_root = NodeTraits::get_parent(source_header);\r
 511       if(!source_root)\r
 512          return;\r
 513 \r
 514       NodeTraits::set_parent\r
 515          ( target_header\r
 516          , deep_clone_node(source_root, target_header, cloner, destroyer));\r
 517       NodeTraits::set_left(target_header, minimum(NodeTraits::get_parent(target_header)));\r
 518       NodeTraits::set_right(target_header, maximum(NodeTraits::get_parent(target_header)));\r
 519    }\r
 520 \r
 521    //! <b>Requires</b>: "header" must be the header node of a tree.\r
 522    //!   KeyNodePtrCompare is a function object that induces a strict weak\r
 523    //!   ordering compatible with the strict weak ordering used to create the\r
 524    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.\r
 525    //!\r
 526    //! <b>Effects</b>: Returns an node_ptr to the first element that is\r
 527    //!   not less than "key" according to "comp" or "header" if that element does\r
 528    //!   not exist.\r
 529    //!\r
 530    //! <b>Complexity</b>: Logarithmic.\r
 531    //! \r
 532    //! <b>Throws</b>: If "comp" throws.\r
 533    template<class KeyType, class KeyNodePtrCompare>\r
 534    static node_ptr lower_bound\r
 535       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)\r
 536    {\r
 537       node_ptr y = uncast(header);\r
 538       node_ptr x = NodeTraits::get_parent(header);\r
 539       while(x){\r
 540          if(comp(x, key)){\r
 541             x = NodeTraits::get_right(x);\r
 542          }\r
 543          else {\r
 544             y = x;\r
 545             x = NodeTraits::get_left(x);\r
 546          }\r
 547       }\r
 548       return y;\r
 549    }\r
 550 \r
 551    //! <b>Requires</b>: "header" must be the header node of a tree.\r
 552    //!   KeyNodePtrCompare is a function object that induces a strict weak\r
 553    //!   ordering compatible with the strict weak ordering used to create the\r
 554    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.\r
 555    //!\r
 556    //! <b>Effects</b>: Returns an node_ptr to the first element that is greater\r
 557    //!   than "key" according to "comp" or "header" if that element does not exist.\r
 558    //!\r
 559    //! <b>Complexity</b>: Logarithmic.\r
 560    //! \r
 561    //! <b>Throws</b>: If "comp" throws.\r
 562    template<class KeyType, class KeyNodePtrCompare>\r
 563    static node_ptr upper_bound\r
 564       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)\r
 565    {\r
 566       node_ptr y = uncast(header);\r
 567       node_ptr x = NodeTraits::get_parent(header);\r
 568       while(x){\r
 569          if(comp(key, x)){\r
 570             y = x;\r
 571             x = NodeTraits::get_left(x);\r
 572          }\r
 573          else {\r
 574             x = NodeTraits::get_right(x);\r
 575          }\r
 576       }\r
 577       return y;\r
 578    }\r
 579 \r
 580    //! <b>Requires</b>: "header" must be the header node of a tree.\r
 581    //!   KeyNodePtrCompare is a function object that induces a strict weak\r
 582    //!   ordering compatible with the strict weak ordering used to create the\r
 583    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.\r
 584    //!\r
 585    //! <b>Effects</b>: Returns an node_ptr to the element that is equivalent to\r
 586    //!   "key" according to "comp" or "header" if that element does not exist.\r
 587    //!\r
 588    //! <b>Complexity</b>: Logarithmic.\r
 589    //! \r
 590    //! <b>Throws</b>: If "comp" throws.\r
 591    template<class KeyType, class KeyNodePtrCompare>\r
 592    static node_ptr find\r
 593       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)\r
 594    {\r
 595       node_ptr end = uncast(header);\r
 596       node_ptr y = lower_bound(header, key, comp);\r
 597       return (y == end || comp(key, y)) ? end : y;\r
 598    }\r
 599 \r
 600    //! <b>Requires</b>: "header" must be the header node of a tree.\r
 601    //!   KeyNodePtrCompare is a function object that induces a strict weak\r
 602    //!   ordering compatible with the strict weak ordering used to create the\r
 603    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.\r
 604    //!\r
 605    //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing\r
 606    //!   all elements that are equivalent to "key" according to "comp" or an\r
 607    //!   empty range that indicates the position where those elements would be\r
 608    //!   if they there are no equivalent elements.\r
 609    //!\r
 610    //! <b>Complexity</b>: Logarithmic.\r
 611    //! \r
 612    //! <b>Throws</b>: If "comp" throws.\r
 613    template<class KeyType, class KeyNodePtrCompare>\r
 614    static std::pair<node_ptr, node_ptr> equal_range\r
 615       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp)\r
 616    {\r
 617       node_ptr y = uncast(header);\r
 618       node_ptr x = NodeTraits::get_parent(header);\r
 619 \r
 620       while(x){\r
 621          if(comp(x, key)){\r
 622             x = NodeTraits::get_right(x);\r
 623          }\r
 624          else if(comp(key, x)){\r
 625             y = x;\r
 626             x = NodeTraits::get_left(x);\r
 627          }\r
 628          else{\r
 629             node_ptr xu(x), yu(y);\r
 630             y = x, x = NodeTraits::get_left(x);\r
 631             xu = NodeTraits::get_right(xu);\r
 632 \r
 633             while(x){\r
 634                if(comp(x, key)){\r
 635                   x = NodeTraits::get_right(x);\r
 636                }\r
 637                else {\r
 638                   y = x;\r
 639                   x = NodeTraits::get_left(x);\r
 640                }\r
 641             }\r
 642 \r
 643             while(xu){\r
 644                if(comp(key, xu)){\r
 645                   yu = xu;\r
 646                   xu = NodeTraits::get_left(xu);\r
 647                }\r
 648                else {\r
 649                   xu = NodeTraits::get_right(xu);\r
 650                }\r
 651             }\r
 652             return std::pair<node_ptr,node_ptr>(y, yu);\r
 653          }\r
 654       }\r
 655       return std::pair<node_ptr,node_ptr>(y, y);\r
 656    }\r
 657 \r
 658    //! <b>Requires</b>: "h" must be the header node of a tree.\r
 659    //!   NodePtrCompare is a function object that induces a strict weak\r
 660    //!   ordering compatible with the strict weak ordering used to create the\r
 661    //!   the tree. NodePtrCompare compares two node_ptrs.\r
 662    //!\r
 663    //! <b>Effects</b>: Inserts new_node into the tree before the upper bound\r
 664    //!   according to "comp".\r
 665    //! \r
 666    //! <b>Complexity</b>: Average complexity for insert element is at\r
 667    //!   most logarithmic.\r
 668    //! \r
 669    //! <b>Throws</b>: If "comp" throws.\r
 670    template<class NodePtrCompare>\r
 671    static node_ptr insert_equal_upper_bound\r
 672       (node_ptr h, node_ptr new_node, NodePtrCompare comp)\r
 673    {\r
 674       node_ptr y(h);\r
 675       node_ptr x(NodeTraits::get_parent(y));\r
 676 \r
 677       while(x){\r
 678          y = x;\r
 679          x = comp(new_node, x) ? \r
 680                NodeTraits::get_left(x) : NodeTraits::get_right(x);\r
 681       }\r
 682 \r
 683       bool link_left = (y == h) || \r
 684                         comp(new_node, y);\r
 685       link_and_balance(new_node, y, link_left, h);\r
 686       return new_node;\r
 687    }\r
 688 \r
 689    //! <b>Requires</b>: "h" must be the header node of a tree.\r
 690    //!   NodePtrCompare is a function object that induces a strict weak\r
 691    //!   ordering compatible with the strict weak ordering used to create the\r
 692    //!   the tree. NodePtrCompare compares two node_ptrs.\r
 693    //!\r
 694    //! <b>Effects</b>: Inserts new_node into the tree before the lower bound\r
 695    //!   according to "comp".\r
 696    //! \r
 697    //! <b>Complexity</b>: Average complexity for insert element is at\r
 698    //!   most logarithmic.\r
 699    //! \r
 700    //! <b>Throws</b>: If "comp" throws.\r
 701    template<class NodePtrCompare>\r
 702    static node_ptr insert_equal_lower_bound\r
 703       (node_ptr h, node_ptr new_node, NodePtrCompare comp)\r
 704    {\r
 705       node_ptr y(h);\r
 706       node_ptr x(NodeTraits::get_parent(y));\r
 707 \r
 708       while(x){\r
 709          y = x;\r
 710          x = !comp(x, new_node) ? \r
 711                NodeTraits::get_left(x) : NodeTraits::get_right(x);\r
 712       }\r
 713 \r
 714       bool link_left = (y == h) || \r
 715                         !comp(y, new_node);\r
 716       link_and_balance(new_node, y, link_left, h);\r
 717       return new_node;\r
 718    }\r
 719 \r
 720    //! <b>Requires</b>: "header" must be the header node of a tree.\r
 721    //!   NodePtrCompare is a function object that induces a strict weak\r
 722    //!   ordering compatible with the strict weak ordering used to create the\r
 723    //!   the tree. NodePtrCompare compares two node_ptrs. "hint" is node from\r
 724    //!   the "header"'s tree.\r
 725    //!   \r
 726    //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to\r
 727    //!   where it will be inserted. If "hint" is the upper_bound\r
 728    //!   the insertion takes constant time (two comparisons in the worst case).\r
 729    //!\r
 730    //! <b>Complexity</b>: Logarithmic in general, but it is amortized\r
 731    //!   constant time if new_node is inserted immediately before "hint".\r
 732    //! \r
 733    //! <b>Throws</b>: If "comp" throws.\r
 734    template<class NodePtrCompare>\r
 735    static node_ptr insert_equal\r
 736       (node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp)\r
 737    {\r
 738       if(hint == header || !comp(hint, new_node)){\r
 739          node_ptr prev(hint);\r
 740          if(hint == NodeTraits::get_left(header) || \r
 741             !comp(new_node, (prev = prev_node(hint)))){\r
 742             bool link_left = unique(header) || !NodeTraits::get_left(hint);\r
 743             link_and_balance(new_node, link_left ? hint : prev, link_left, header);\r
 744             return new_node;\r
 745          }\r
 746          else{\r
 747             return insert_equal_upper_bound(header, new_node, comp);\r
 748          }\r
 749       }\r
 750       else{\r
 751          return insert_equal_lower_bound(header, new_node, comp);\r
 752       }\r
 753    }\r
 754 \r
 755    //! <b>Requires</b>: "header" must be the header node of a tree.\r
 756    //!   KeyNodePtrCompare is a function object that induces a strict weak\r
 757    //!   ordering compatible with the strict weak ordering used to create the\r
 758    //!   the tree. NodePtrCompare compares KeyType with a node_ptr.\r
 759    //! \r
 760    //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the\r
 761    //!   tree according to "comp" and obtains the needed information to realize\r
 762    //!   a constant-time node insertion if there is no equivalent node.\r
 763    //!\r
 764    //! <b>Returns</b>: If an equivalent node is already present\r
 765    //!   returns a pair containing a node_ptr to the already present node\r
 766    //!   and false. If there is not equivalent key can be inserted returns true\r
 767    //!   in the returned pair's boolean and fills "commit_data" that is meant to\r
 768    //!   be used with the "insert_commit" function to achieve a constant-time\r
 769    //!   insertion function.\r
 770    //! \r
 771    //! <b>Complexity</b>: Average complexity is at most logarithmic.\r
 772    //!\r
 773    //! <b>Throws</b>: If "comp" throws.\r
 774    //! \r
 775    //! <b>Notes</b>: This function is used to improve performance when constructing\r
 776    //!   a node is expensive and the user does not want to have two equivalent nodes\r
 777    //!   in the tree: if an equivalent node is already present\r
 778    //!   the constructed object must be discarded. Many times, the part of the\r
 779    //!   node that is used to impose the order is much cheaper to construct\r
 780    //!   than the node and this function offers the possibility to use that part\r
 781    //!   to check if the insertion will be successful.\r
 782    //!\r
 783    //!   If the check is successful, the user can construct the node and use\r
 784    //!   "insert_commit" to insert the node in constant-time. This gives a total\r
 785    //!   logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).\r
 786    //!\r
 787    //!   "commit_data" remains valid for a subsequent "insert_unique_commit" only\r
 788    //!   if no more objects are inserted or erased from the set.\r
 789    template<class KeyType, class KeyNodePtrCompare>\r
 790    static std::pair<node_ptr, bool> insert_unique_check\r
 791       (const_node_ptr header,  const KeyType &key\r
 792       ,KeyNodePtrCompare comp, insert_commit_data &commit_data)\r
 793    {\r
 794       node_ptr h(uncast(header));\r
 795       node_ptr y(h);\r
 796       node_ptr x(NodeTraits::get_parent(y));\r
 797       node_ptr prev(0);\r
 798 \r
 799       //Find the upper bound, cache the previous value and if we should\r
 800       //store it in the left or right node\r
 801       bool left_child = true;\r
 802       while(x){\r
 803          y = x;\r
 804          x = (left_child = comp(key, x)) ? \r
 805                NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x));\r
 806       }\r
 807 \r
 808       //Since we've found the upper bound there is no other value with the same key if:\r
 809       //    - There is no previous node\r
 810       //    - The previous node is less than the key\r
 811            if(!prev || comp(prev, key)){\r
 812          commit_data.link_left = left_child;\r
 813          commit_data.node      = y;\r
 814          return std::pair<node_ptr, bool>(node_ptr(), true);\r
 815            }\r
 816       //If the previous value was not less than key, it means that it's equal\r
 817       //(because we've checked the upper bound)\r
 818       else{\r
 819          return std::pair<node_ptr, bool>(prev, false);\r
 820       }\r
 821    }\r
 822 \r
 823    //! <b>Requires</b>: "header" must be the header node of a tree.\r
 824    //!   KeyNodePtrCompare is a function object that induces a strict weak\r
 825    //!   ordering compatible with the strict weak ordering used to create the\r
 826    //!   the tree. NodePtrCompare compares KeyType with a node_ptr.\r
 827    //!   "hint" is node from the "header"'s tree.\r
 828    //! \r
 829    //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the\r
 830    //!   tree according to "comp" using "hint" as a hint to where it should be\r
 831    //!   inserted and obtains the needed information to realize\r
 832    //!   a constant-time node insertion if there is no equivalent node. \r
 833    //!   If "hint" is the upper_bound the function has constant time \r
 834    //!   complexity (two comparisons in the worst case).\r
 835    //!\r
 836    //! <b>Returns</b>: If an equivalent node is already present\r
 837    //!   returns a pair containing a node_ptr to the already present node\r
 838    //!   and false. If there is not equivalent key can be inserted returns true\r
 839    //!   in the returned pair's boolean and fills "commit_data" that is meant to\r
 840    //!   be used with the "insert_commit" function to achieve a constant-time\r
 841    //!   insertion function.\r
 842    //! \r
 843    //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is\r
 844    //!   amortized constant time if new_node should be inserted immediately before "hint".\r
 845    //!\r
 846    //! <b>Throws</b>: If "comp" throws.\r
 847    //! \r
 848    //! <b>Notes</b>: This function is used to improve performance when constructing\r
 849    //!   a node is expensive and the user does not want to have two equivalent nodes\r
 850    //!   in the tree: if an equivalent node is already present\r
 851    //!   the constructed object must be discarded. Many times, the part of the\r
 852    //!   node that is used to impose the order is much cheaper to construct\r
 853    //!   than the node and this function offers the possibility to use that part\r
 854    //!   to check if the insertion will be successful.\r
 855    //!\r
 856    //!   If the check is successful, the user can construct the node and use\r
 857    //!   "insert_commit" to insert the node in constant-time. This gives a total\r
 858    //!   logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).\r
 859    //!\r
 860    //!   "commit_data" remains valid for a subsequent "insert_unique_commit" only\r
 861    //!   if no more objects are inserted or erased from the set.\r
 862    template<class KeyType, class KeyNodePtrCompare>\r
 863    static std::pair<node_ptr, bool> insert_unique_check\r
 864       (const_node_ptr header,  node_ptr hint, const KeyType &key\r
 865       ,KeyNodePtrCompare comp, insert_commit_data &commit_data)\r
 866    {\r
 867       //hint must be bigger than the key\r
 868            if(hint == header || comp(key, hint)){\r
 869          node_ptr prev = hint;\r
 870          //The previous value should be less than the key\r
 871                    if(prev == NodeTraits::get_left(header) || comp((prev = prev_node(hint)), key)){\r
 872             commit_data.link_left = unique(header) || !NodeTraits::get_left(hint);\r
 873             commit_data.node      = commit_data.link_left ? hint : prev;\r
 874             return std::pair<node_ptr, bool>(node_ptr(), true);\r
 875                    }\r
 876          else{\r
 877             return insert_unique_check(header, key, comp, commit_data);\r
 878             //return std::pair<node_ptr, bool>(prev, false);\r
 879          }\r
 880            }\r
 881       //The hint was wrong, use hintless insert\r
 882       else{\r
 883          return insert_unique_check(header, key, comp, commit_data);\r
 884       }\r
 885    }\r
 886 \r
 887    //! <b>Requires</b>: "header" must be the header node of a tree.\r
 888    //!   "commit_data" must have been obtained from a previous call to\r
 889    //!   "insert_unique_check". No objects should have been inserted or erased\r
 890    //!   from the set between the "insert_unique_check" that filled "commit_data"\r
 891    //!   and the call to "insert_commit". \r
 892    //! \r
 893    //! \r
 894    //! <b>Effects</b>: Inserts new_node in the set using the information obtained\r
 895    //!   from the "commit_data" that a previous "insert_check" filled.\r
 896    //!\r
 897    //! <b>Complexity</b>: Constant time.\r
 898    //!\r
 899    //! <b>Throws</b>: Nothing.\r
 900    //! \r
 901    //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been\r
 902    //!   previously executed to fill "commit_data". No value should be inserted or\r
 903    //!   erased between the "insert_check" and "insert_commit" calls.\r
 904    static void insert_unique_commit\r
 905       (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data)\r
 906    {\r
 907       //Check if commit_data has not been initialized by a insert_unique_check call.\r
 908       BOOST_ASSERT(commit_data.node != 0);\r
 909       link_and_balance(new_value, commit_data.node, commit_data.link_left, header);\r
 910    }\r
 911 \r
 912    private:\r
 913 \r
 914    static node_ptr uncast(const_node_ptr ptr)\r
 915    {\r
 916       using boost::get_pointer;\r
 917       return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
 918    }\r
 919 \r
 920    //! <b>Requires</b>: z is the node to be inserted, par is its parent,\r
 921    //!   left, indicates if z should be a left node of par and header is the header\r
 922    //!   of the tree.\r
 923    //! \r
 924    //! <b>Effects</b>: If left is true links z as a left child of par or as a right\r
 925    //!    child otherwise. After that rebalances the tree.\r
 926    //! \r
 927    //! <b>Complexity</b>: Average constant time.???\r
 928    //! \r
 929    //! <b>Throws</b>: Nothing.\r
 930    static void link_and_balance (node_ptr z, node_ptr par, bool left, node_ptr header)\r
 931    {\r
 932       if(par == header){\r
 933          NodeTraits::set_parent(header, z);\r
 934          NodeTraits::set_right(header, z);\r
 935          NodeTraits::set_left(header, z);\r
 936       }\r
 937       else if(left){\r
 938          NodeTraits::set_left(par, z);\r
 939          if(par == NodeTraits::get_left(header))\r
 940              NodeTraits::set_left(header, z);\r
 941       }\r
 942       else{\r
 943          NodeTraits::set_right(par, z);\r
 944          if(par == NodeTraits::get_right(header))\r
 945              NodeTraits::set_right(header, z);\r
 946       }\r
 947       NodeTraits::set_parent(z, par);\r
 948       NodeTraits::set_right(z, 0);\r
 949       NodeTraits::set_left(z, 0);\r
 950       rebalance(z, header);\r
 951    }\r
 952 \r
 953    //! <b>Requires</b>: p is a node of a tree but not the header.\r
 954    //! \r
 955    //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.\r
 956    //! \r
 957    //! <b>Complexity</b>: Logarithmic to the size of the subtree.\r
 958    //! \r
 959    //! <b>Throws</b>: Nothing.\r
 960    static node_ptr minimum (node_ptr p)\r
 961    {\r
 962       for(node_ptr p_left = NodeTraits::get_left(p)\r
 963          ;p_left\r
 964          ;p_left = NodeTraits::get_left(p)){\r
 965          p = p_left;\r
 966       }\r
 967       return p;\r
 968    }\r
 969 \r
 970    //! <b>Requires</b>: p is a node of a tree but not the header.\r
 971    //! \r
 972    //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.\r
 973    //! \r
 974    //! <b>Complexity</b>: Logarithmic to the size of the subtree.\r
 975    //! \r
 976    //! <b>Throws</b>: Nothing.\r
 977    static node_ptr maximum(node_ptr p)\r
 978    {\r
 979       for(node_ptr p_right = NodeTraits::get_right(p)\r
 980          ;p_right\r
 981          ;p_right = NodeTraits::get_right(p)){\r
 982          p = p_right;\r
 983       }\r
 984       return p;\r
 985    }\r
 986 \r
 987    //! <b>Requires</b>: p is a node of a tree.\r
 988    //! \r
 989    //! <b>Effects</b>: Returns true if p is the header of the tree.\r
 990    //! \r
 991    //! <b>Complexity</b>: Constant.\r
 992    //! \r
 993    //! <b>Throws</b>: Nothing.\r
 994    static bool is_header(const_node_ptr p)\r
 995    {\r
 996       return NodeTraits::get_color(p) == NodeTraits::red() && \r
 997              NodeTraits::get_parent(NodeTraits::get_parent(p)) == p;\r
 998    }\r
 999 \r
1000    //! <b>Requires</b>: p is a node of a tree.\r
1001    //! \r
1002    //! <b>Effects</b>: Returns true if p is a left child.\r
1003    //! \r
1004    //! <b>Complexity</b>: Constant.\r
1005    //! \r
1006    //! <b>Throws</b>: Nothing.\r
1007    static bool is_left_child(node_ptr p)\r
1008    {  return NodeTraits::get_left(NodeTraits::get_parent(p)) == p;  }\r
1009 \r
1010    //! <b>Requires</b>: p is a node of a tree.\r
1011    //! \r
1012    //! <b>Effects</b>: Returns true if p is a right child.\r
1013    //! \r
1014    //! <b>Complexity</b>: Constant.\r
1015    //! \r
1016    //! <b>Throws</b>: Nothing.\r
1017    static bool is_right_child (node_ptr p)\r
1018    {  return NodeTraits::get_right(NodeTraits::get_parent(p)) == p;  }\r
1019 \r
1020    static void replace_own (node_ptr own, node_ptr x, node_ptr header)\r
1021    {\r
1022       if(NodeTraits::get_parent(header) == own)\r
1023          NodeTraits::set_parent(header, x);\r
1024       else if(is_left_child(own))\r
1025          NodeTraits::set_left(NodeTraits::get_parent(own), x);\r
1026       else\r
1027          NodeTraits::set_right(NodeTraits::get_parent(own), x);\r
1028    }\r
1029 \r
1030    static void rotate_left(node_ptr p, node_ptr header)\r
1031    {\r
1032       node_ptr x = NodeTraits::get_right(p);\r
1033       NodeTraits::set_right(p, NodeTraits::get_left(x));\r
1034       if(NodeTraits::get_left(x) != 0)\r
1035          NodeTraits::set_parent(NodeTraits::get_left(x), p);\r
1036       NodeTraits::set_parent(x, NodeTraits::get_parent(p));\r
1037       replace_own (p, x, header);\r
1038       NodeTraits::set_left(x, p);\r
1039       NodeTraits::set_parent(p, x);\r
1040    }\r
1041 \r
1042    static void rotate_right(node_ptr p, node_ptr header)\r
1043    {\r
1044       node_ptr x(NodeTraits::get_left(p));\r
1045       node_ptr x_right(NodeTraits::get_right(x));\r
1046       NodeTraits::set_left(p, x_right);\r
1047       if(x_right)\r
1048          NodeTraits::set_parent(x_right, p);\r
1049       NodeTraits::set_parent(x, NodeTraits::get_parent(p));\r
1050       replace_own (p, x, header);\r
1051       NodeTraits::set_right(x, p);\r
1052       NodeTraits::set_parent(p, x);\r
1053    }\r
1054 \r
1055    static void rebalance(node_ptr p, node_ptr header)\r
1056    {\r
1057       NodeTraits::set_color(p, NodeTraits::red());\r
1058       while(p != NodeTraits::get_parent(header) && NodeTraits::get_color(NodeTraits::get_parent(p)) == NodeTraits::red()){\r
1059          node_ptr p_parent(NodeTraits::get_parent(p));\r
1060          node_ptr p_parent_parent(NodeTraits::get_parent(p_parent));\r
1061          if(is_left_child(p_parent)){\r
1062             node_ptr x = NodeTraits::get_right(p_parent_parent);\r
1063             if(x && NodeTraits::get_color(x) == NodeTraits::red()){\r
1064                NodeTraits::set_color(p_parent, NodeTraits::black());\r
1065                NodeTraits::set_color(p_parent_parent, NodeTraits::red());\r
1066                NodeTraits::set_color(x, NodeTraits::black());\r
1067                p = p_parent_parent;\r
1068             }\r
1069             else {\r
1070                if(!is_left_child(p)){\r
1071                   p = p_parent;\r
1072                   rotate_left(p, header);\r
1073                }\r
1074                node_ptr new_p_parent(NodeTraits::get_parent(p));\r
1075                node_ptr new_p_parent_parent(NodeTraits::get_parent(new_p_parent));\r
1076                NodeTraits::set_color(new_p_parent, NodeTraits::black());\r
1077                NodeTraits::set_color(new_p_parent_parent, NodeTraits::red());\r
1078                rotate_right(new_p_parent_parent, header);\r
1079             }\r
1080          }\r
1081          else{\r
1082             node_ptr x = NodeTraits::get_left(p_parent_parent);\r
1083             if(x && NodeTraits::get_color(x) == NodeTraits::red()){\r
1084                NodeTraits::set_color(p_parent, NodeTraits::black());\r
1085                NodeTraits::set_color(p_parent_parent, NodeTraits::red());\r
1086                NodeTraits::set_color(x, NodeTraits::black());\r
1087                p = p_parent_parent;\r
1088             }\r
1089             else{\r
1090                if(is_left_child(p)){\r
1091                   p = p_parent;\r
1092                   rotate_right(p, header);\r
1093                }\r
1094                node_ptr new_p_parent(NodeTraits::get_parent(p));\r
1095                node_ptr new_p_parent_parent(NodeTraits::get_parent(new_p_parent));\r
1096                NodeTraits::set_color(new_p_parent, NodeTraits::black());\r
1097                NodeTraits::set_color(new_p_parent_parent, NodeTraits::red());\r
1098                rotate_left(new_p_parent_parent, header);\r
1099             }\r
1100          }\r
1101       }\r
1102       NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black());\r
1103    }\r
1104 \r
1105    template <class Cloner, class Destroyer>\r
1106    static node_ptr deep_clone_node\r
1107       (node_ptr source_root, node_ptr new_parent, Cloner cloner, Destroyer destroyer)\r
1108    {\r
1109       // structural copy.  source_root and new_parent must be non-null.\r
1110       node_ptr top = cloner(source_root);\r
1111       NodeTraits::set_parent(top, new_parent);\r
1112        \r
1113       BOOST_TRY {\r
1114          if(NodeTraits::get_right(source_root)){\r
1115             NodeTraits::set_right\r
1116                (top, deep_clone_node(NodeTraits::get_right(source_root), top\r
1117                                     ,cloner, destroyer));\r
1118          }\r
1119          new_parent = top;\r
1120          source_root = NodeTraits::get_left(source_root);\r
1121 \r
1122          while(source_root){\r
1123             node_ptr y = cloner(source_root);\r
1124             NodeTraits::set_left(new_parent, y);\r
1125             NodeTraits::set_parent(y, new_parent);\r
1126 \r
1127             if(NodeTraits::get_right(source_root)){\r
1128                NodeTraits::set_right(y, deep_clone_node(NodeTraits::get_right(source_root), y\r
1129                                                     ,cloner, destroyer));\r
1130             }\r
1131             new_parent = y;\r
1132             source_root = NodeTraits::get_left(source_root);\r
1133          }\r
1134       }\r
1135       BOOST_CATCH(...){\r
1136          deep_destroy_node(top, destroyer);\r
1137          BOOST_RETHROW;\r
1138       }\r
1139       BOOST_CATCH_END\r
1140       return top;\r
1141    }\r
1142 \r
1143    template<class Destroyer>\r
1144    static void deep_destroy_node(node_ptr x, Destroyer destroyer)\r
1145    {\r
1146       // erase without rebalancing\r
1147       while(x){\r
1148          deep_destroy_node(NodeTraits::get_right(x), destroyer);\r
1149          node_ptr y = NodeTraits::get_left(x);\r
1150          destroyer(x);\r
1151          x = y;\r
1152       }\r
1153    }\r
1154 };\r
1155 \r
1156 } //namespace intrusive \r
1157 } //namespace boost \r
1158 \r
1159 #include "detail/config_end.hpp"\r
1160 \r
1161 #endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP\r