boost/intrusive/sgtree_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2007-2012
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 //
  13 // Scapegoat tree algorithms are taken from the paper titled:
  14 // "Scapegoat Trees" by Igal Galperin Ronald L. Rivest.
  15 //
  16 /////////////////////////////////////////////////////////////////////////////
  17 #ifndef BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP
  18 #define BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP
  19
  20 #include <boost/intrusive/detail/config_begin.hpp>
  21
  22 #include <cstddef>
  23 #include <boost/intrusive/intrusive_fwd.hpp>
  24 #include <boost/intrusive/detail/assert.hpp>
  25 #include <boost/intrusive/detail/utilities.hpp>
  26 #include <boost/intrusive/detail/tree_algorithms.hpp>
  27 #include <boost/intrusive/pointer_traits.hpp>
  28
  29
  30 namespace boost {
  31 namespace intrusive {
  32
  33 //! sgtree_algorithms is configured with a NodeTraits class, which encapsulates the
  34 //! information about the node to be manipulated. NodeTraits must support the
  35 //! following interface:
  36 //!
  37 //! <b>Typedefs</b>:
  38 //!
  39 //! <tt>node</tt>: The type of the node that forms the circular list
  40 //!
  41 //! <tt>node_ptr</tt>: A pointer to a node
  42 //!
  43 //! <tt>const_node_ptr</tt>: A pointer to a const node
  44 //!
  45 //! <b>Static functions</b>:
  46 //!
  47 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
  48 //!
  49 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
  50 //!
  51 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
  52 //!
  53 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
  54 //!
  55 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
  56 //!
  57 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
  58 template<class NodeTraits>
  59 class sgtree_algorithms
  60 {
  61    public:
  62    typedef typename NodeTraits::node            node;
  63    typedef NodeTraits                           node_traits;
  64    typedef typename NodeTraits::node_ptr        node_ptr;
  65    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
  66
  67    /// @cond
  68    private:
  69
  70    typedef detail::tree_algorithms<NodeTraits>  tree_algorithms;
  71
  72    static node_ptr uncast(const const_node_ptr & ptr)
  73    {  return pointer_traits<node_ptr>::const_cast_from(ptr);  }
  74    /// @endcond
  75
  76    public:
  77    static node_ptr begin_node(const const_node_ptr & header)
  78    {  return tree_algorithms::begin_node(header);   }
  79
  80    static node_ptr end_node(const const_node_ptr & header)
  81    {  return tree_algorithms::end_node(header);   }
  82
  83    //! This type is the information that will be
  84    //! filled by insert_unique_check
  85    struct insert_commit_data
  86       :  tree_algorithms::insert_commit_data
  87    {
  88       std::size_t depth;
  89    };
  90
  91    //! <b>Requires</b>: header1 and header2 must be the header nodes
  92    //!  of two trees.
  93    //!
  94    //! <b>Effects</b>: Swaps two trees. After the function header1 will contain
  95    //!   links to the second tree and header2 will have links to the first tree.
  96    //!
  97    //! <b>Complexity</b>: Constant.
  98    //!
  99    //! <b>Throws</b>: Nothing.
 100    static void swap_tree(const node_ptr & header1, const node_ptr & header2)
 101    {  return tree_algorithms::swap_tree(header1, header2);  }
 102
 103    //! <b>Requires</b>: node1 and node2 can't be header nodes
 104    //!  of two trees.
 105    //!
 106    //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
 107    //!   in the position node2 before the function. node2 will be inserted in the
 108    //!   position node1 had before the function.
 109    //!
 110    //! <b>Complexity</b>: Logarithmic.
 111    //!
 112    //! <b>Throws</b>: Nothing.
 113    //!
 114    //! <b>Note</b>: This function will break container ordering invariants if
 115    //!   node1 and node2 are not equivalent according to the ordering rules.
 116    //!
 117    //!Experimental function
 118    static void swap_nodes(const node_ptr & node1, const node_ptr & node2)
 119    {
 120       if(node1 == node2)
 121          return;
 122
 123       node_ptr header1(tree_algorithms::get_header(node1)), header2(tree_algorithms::get_header(node2));
 124       swap_nodes(node1, header1, node2, header2);
 125    }
 126
 127    //! <b>Requires</b>: node1 and node2 can't be header nodes
 128    //!  of two trees with header header1 and header2.
 129    //!
 130    //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted
 131    //!   in the position node2 before the function. node2 will be inserted in the
 132    //!   position node1 had before the function.
 133    //!
 134    //! <b>Complexity</b>: Constant.
 135    //!
 136    //! <b>Throws</b>: Nothing.
 137    //!
 138    //! <b>Note</b>: This function will break container ordering invariants if
 139    //!   node1 and node2 are not equivalent according to the ordering rules.
 140    //!
 141    //!Experimental function
 142    static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2)
 143    {  tree_algorithms::swap_nodes(node1, header1, node2, header2);  }
 144
 145    //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
 146    //!   and new_node must not be inserted in a tree.
 147    //!
 148    //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
 149    //!   tree with new_node. The tree does not need to be rebalanced
 150    //!
 151    //! <b>Complexity</b>: Logarithmic.
 152    //!
 153    //! <b>Throws</b>: Nothing.
 154    //!
 155    //! <b>Note</b>: This function will break container ordering invariants if
 156    //!   new_node is not equivalent to node_to_be_replaced according to the
 157    //!   ordering rules. This function is faster than erasing and inserting
 158    //!   the node, since no rebalancing and comparison is needed.
 159    //!
 160    //!Experimental function
 161    static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
 162    {
 163       if(node_to_be_replaced == new_node)
 164          return;
 165       replace_node(node_to_be_replaced, tree_algorithms::get_header(node_to_be_replaced), new_node);
 166    }
 167
 168    //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
 169    //!   with header "header" and new_node must not be inserted in a tree.
 170    //!
 171    //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
 172    //!   tree with new_node. The tree does not need to be rebalanced
 173    //!
 174    //! <b>Complexity</b>: Constant.
 175    //!
 176    //! <b>Throws</b>: Nothing.
 177    //!
 178    //! <b>Note</b>: This function will break container ordering invariants if
 179    //!   new_node is not equivalent to node_to_be_replaced according to the
 180    //!   ordering rules. This function is faster than erasing and inserting
 181    //!   the node, since no rebalancing or comparison is needed.
 182    //!
 183    //!Experimental function
 184    static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
 185    {  tree_algorithms::replace_node(node_to_be_replaced, header, new_node);  }
 186
 187    //! <b>Requires</b>: node is a tree node but not the header.
 188    //!
 189    //! <b>Effects</b>: Unlinks the node and rebalances the tree.
 190    //!
 191    //! <b>Complexity</b>: Average complexity is constant time.
 192    //!
 193    //! <b>Throws</b>: Nothing.
 194    static void unlink(const node_ptr & node)
 195    {
 196       node_ptr x = NodeTraits::get_parent(node);
 197       if(x){
 198          while(!is_header(x))
 199             x = NodeTraits::get_parent(x);
 200          tree_algorithms::erase(x, node);
 201       }
 202    }
 203
 204    //! <b>Requires</b>: header is the header of a tree.
 205    //!
 206    //! <b>Effects</b>: Unlinks the leftmost node from the tree, and
 207    //!   updates the header link to the new leftmost node.
 208    //!
 209    //! <b>Complexity</b>: Average complexity is constant time.
 210    //!
 211    //! <b>Throws</b>: Nothing.
 212    //!
 213    //! <b>Notes</b>: This function breaks the tree and the tree can
 214    //!   only be used for more unlink_leftmost_without_rebalance calls.
 215    //!   This function is normally used to achieve a step by step
 216    //!   controlled destruction of the tree.
 217    static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header)
 218    {  return tree_algorithms::unlink_leftmost_without_rebalance(header);   }
 219
 220    //! <b>Requires</b>: node is a node of the tree or an node initialized
 221    //!   by init(...).
 222    //!
 223    //! <b>Effects</b>: Returns true if the node is initialized by init().
 224    //!
 225    //! <b>Complexity</b>: Constant time.
 226    //!
 227    //! <b>Throws</b>: Nothing.
 228    static bool unique(const const_node_ptr & node)
 229    {  return tree_algorithms::unique(node);  }
 230
 231    //! <b>Requires</b>: node is a node of the tree but it's not the header.
 232    //!
 233    //! <b>Effects</b>: Returns the number of nodes of the subtree.
 234    //!
 235    //! <b>Complexity</b>: Linear time.
 236    //!
 237    //! <b>Throws</b>: Nothing.
 238    static std::size_t count(const const_node_ptr & node)
 239    {  return tree_algorithms::count(node);   }
 240
 241    //! <b>Requires</b>: header is the header node of the tree.
 242    //!
 243    //! <b>Effects</b>: Returns the number of nodes above the header.
 244    //!
 245    //! <b>Complexity</b>: Linear time.
 246    //!
 247    //! <b>Throws</b>: Nothing.
 248    static std::size_t size(const const_node_ptr & header)
 249    {  return tree_algorithms::size(header);   }
 250
 251    //! <b>Requires</b>: p is a node from the tree except the header.
 252    //!
 253    //! <b>Effects</b>: Returns the next node of the tree.
 254    //!
 255    //! <b>Complexity</b>: Average constant time.
 256    //!
 257    //! <b>Throws</b>: Nothing.
 258    static node_ptr next_node(const node_ptr & p)
 259    {  return tree_algorithms::next_node(p); }
 260
 261    //! <b>Requires</b>: p is a node from the tree except the leftmost node.
 262    //!
 263    //! <b>Effects</b>: Returns the previous node of the tree.
 264    //!
 265    //! <b>Complexity</b>: Average constant time.
 266    //!
 267    //! <b>Throws</b>: Nothing.
 268    static node_ptr prev_node(const node_ptr & p)
 269    {  return tree_algorithms::prev_node(p); }
 270
 271    //! <b>Requires</b>: node must not be part of any tree.
 272    //!
 273    //! <b>Effects</b>: After the function unique(node) == true.
 274    //!
 275    //! <b>Complexity</b>: Constant.
 276    //!
 277    //! <b>Throws</b>: Nothing.
 278    //!
 279    //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
 280    static void init(const node_ptr & node)
 281    {  tree_algorithms::init(node);  }
 282
 283    //! <b>Requires</b>: node must not be part of any tree.
 284    //!
 285    //! <b>Effects</b>: Initializes the header to represent an empty tree.
 286    //!   unique(header) == true.
 287    //!
 288    //! <b>Complexity</b>: Constant.
 289    //!
 290    //! <b>Throws</b>: Nothing.
 291    //!
 292    //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
 293    static void init_header(const node_ptr & header)
 294    {  tree_algorithms::init_header(header);  }
 295
 296    //! <b>Requires</b>: header must be the header of a tree, z a node
 297    //!    of that tree and z != header.
 298    //!
 299    //! <b>Effects</b>: Erases node "z" from the tree with header "header".
 300    //!
 301    //! <b>Complexity</b>: Amortized constant time.
 302    //!
 303    //! <b>Throws</b>: Nothing.
 304    template<class AlphaByMaxSize>
 305    static node_ptr erase(const node_ptr & header, const node_ptr & z, std::size_t tree_size, std::size_t &max_tree_size, AlphaByMaxSize alpha_by_maxsize)
 306    {
 307       //typename tree_algorithms::data_for_rebalance info;
 308       tree_algorithms::erase(header, z);
 309       --tree_size;
 310       if (tree_size > 0 &&
 311           tree_size < alpha_by_maxsize(max_tree_size)){
 312          tree_algorithms::rebalance(header);
 313          max_tree_size = tree_size;
 314       }
 315       return z;
 316    }
 317
 318    //! <b>Requires</b>: "cloner" must be a function
 319    //!   object taking a node_ptr and returning a new cloned node of it. "disposer" must
 320    //!   take a node_ptr and shouldn't throw.
 321    //!
 322    //! <b>Effects</b>: First empties target tree calling
 323    //!   <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
 324    //!    except the header.
 325    //!
 326    //!   Then, duplicates the entire tree pointed by "source_header" cloning each
 327    //!   source node with <tt>node_ptr Cloner::operator()(const node_ptr &)</tt> to obtain
 328    //!   the nodes of the target tree. If "cloner" throws, the cloned target nodes
 329    //!   are disposed using <tt>void disposer(const node_ptr &)</tt>.
 330    //!
 331    //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
 332    //!   number of elements of tree target tree when calling this function.
 333    //!
 334    //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
 335    template <class Cloner, class Disposer>
 336    static void clone
 337       (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
 338    {
 339       tree_algorithms::clone(source_header, target_header, cloner, disposer);
 340    }
 341
 342    //! <b>Requires</b>: "disposer" must be an object function
 343    //!   taking a node_ptr parameter and shouldn't throw.
 344    //!
 345    //! <b>Effects</b>: Empties the target tree calling
 346    //!   <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree
 347    //!    except the header.
 348    //!
 349    //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
 350    //!   number of elements of tree target tree when calling this function.
 351    //!
 352    //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
 353    template<class Disposer>
 354    static void clear_and_dispose(const node_ptr & header, Disposer disposer)
 355    {  tree_algorithms::clear_and_dispose(header, disposer); }
 356
 357    //! <b>Requires</b>: "header" must be the header node of a tree.
 358    //!   KeyNodePtrCompare is a function object that induces a strict weak
 359    //!   ordering compatible with the strict weak ordering used to create the
 360    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
 361    //!
 362    //! <b>Effects</b>: Returns an node_ptr to the first element that is
 363    //!   not less than "key" according to "comp" or "header" if that element does
 364    //!   not exist.
 365    //!
 366    //! <b>Complexity</b>: Logarithmic.
 367    //!
 368    //! <b>Throws</b>: If "comp" throws.
 369    template<class KeyType, class KeyNodePtrCompare>
 370    static node_ptr lower_bound
 371       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 372    {  return tree_algorithms::lower_bound(header, key, comp);  }
 373
 374    //! <b>Requires</b>: "header" must be the header node of a tree.
 375    //!   KeyNodePtrCompare is a function object that induces a strict weak
 376    //!   ordering compatible with the strict weak ordering used to create the
 377    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
 378    //!
 379    //! <b>Effects</b>: Returns an node_ptr to the first element that is greater
 380    //!   than "key" according to "comp" or "header" if that element does not exist.
 381    //!
 382    //! <b>Complexity</b>: Logarithmic.
 383    //!
 384    //! <b>Throws</b>: If "comp" throws.
 385    template<class KeyType, class KeyNodePtrCompare>
 386    static node_ptr upper_bound
 387       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 388    {  return tree_algorithms::upper_bound(header, key, comp);  }
 389
 390    //! <b>Requires</b>: "header" must be the header node of a tree.
 391    //!   KeyNodePtrCompare is a function object that induces a strict weak
 392    //!   ordering compatible with the strict weak ordering used to create the
 393    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
 394    //!
 395    //! <b>Effects</b>: Returns an node_ptr to the element that is equivalent to
 396    //!   "key" according to "comp" or "header" if that element does not exist.
 397    //!
 398    //! <b>Complexity</b>: Logarithmic.
 399    //!
 400    //! <b>Throws</b>: If "comp" throws.
 401    template<class KeyType, class KeyNodePtrCompare>
 402    static node_ptr find
 403       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 404    {  return tree_algorithms::find(header, key, comp);  }
 405
 406    //! <b>Requires</b>: "header" must be the header node of a tree.
 407    //!   KeyNodePtrCompare is a function object that induces a strict weak
 408    //!   ordering compatible with the strict weak ordering used to create the
 409    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
 410    //!
 411    //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing
 412    //!   all elements that are equivalent to "key" according to "comp" or an
 413    //!   empty range that indicates the position where those elements would be
 414    //!   if they there are no equivalent elements.
 415    //!
 416    //! <b>Complexity</b>: Logarithmic.
 417    //!
 418    //! <b>Throws</b>: If "comp" throws.
 419    template<class KeyType, class KeyNodePtrCompare>
 420    static std::pair<node_ptr, node_ptr> equal_range
 421       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 422    {  return tree_algorithms::equal_range(header, key, comp);  }
 423
 424    //! <b>Requires</b>: "header" must be the header node of a tree.
 425    //!   KeyNodePtrCompare is a function object that induces a strict weak
 426    //!   ordering compatible with the strict weak ordering used to create the
 427    //!   the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
 428    //!   'lower_key' must not be greater than 'upper_key' according to 'comp'. If
 429    //!   'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
 430    //!
 431    //! <b>Effects</b>: Returns an a pair with the following criteria:
 432    //!
 433    //!   first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
 434    //!
 435    //!   second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
 436    //!
 437    //! <b>Complexity</b>: Logarithmic.
 438    //!
 439    //! <b>Throws</b>: If "comp" throws.
 440    //!
 441    //! <b>Note</b>: This function can be more efficient than calling upper_bound
 442    //!   and lower_bound for lower_key and upper_key.
 443    template<class KeyType, class KeyNodePtrCompare>
 444    static std::pair<node_ptr, node_ptr> bounded_range
 445       (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
 446       , bool left_closed, bool right_closed)
 447    {  return tree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed);  }
 448
 449    //! <b>Requires</b>: "h" must be the header node of a tree.
 450    //!   NodePtrCompare is a function object that induces a strict weak
 451    //!   ordering compatible with the strict weak ordering used to create the
 452    //!   the tree. NodePtrCompare compares two node_ptrs.
 453    //!
 454    //! <b>Effects</b>: Inserts new_node into the tree before the upper bound
 455    //!   according to "comp".
 456    //!
 457    //! <b>Complexity</b>: Average complexity for insert element is at
 458    //!   most logarithmic.
 459    //!
 460    //! <b>Throws</b>: If "comp" throws.
 461    template<class NodePtrCompare, class H_Alpha>
 462    static node_ptr insert_equal_upper_bound
 463       (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
 464       ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
 465    {
 466       std::size_t depth;
 467       tree_algorithms::insert_equal_upper_bound(h, new_node, comp, &depth);
 468       rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
 469       return new_node;
 470    }
 471
 472    //! <b>Requires</b>: "h" must be the header node of a tree.
 473    //!   NodePtrCompare is a function object that induces a strict weak
 474    //!   ordering compatible with the strict weak ordering used to create the
 475    //!   the tree. NodePtrCompare compares two node_ptrs.
 476    //!
 477    //! <b>Effects</b>: Inserts new_node into the tree before the lower bound
 478    //!   according to "comp".
 479    //!
 480    //! <b>Complexity</b>: Average complexity for insert element is at
 481    //!   most logarithmic.
 482    //!
 483    //! <b>Throws</b>: If "comp" throws.
 484    template<class NodePtrCompare, class H_Alpha>
 485    static node_ptr insert_equal_lower_bound
 486       (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
 487       ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
 488    {
 489       std::size_t depth;
 490       tree_algorithms::insert_equal_lower_bound(h, new_node, comp, &depth);
 491       rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
 492       return new_node;
 493    }
 494
 495    //! <b>Requires</b>: "header" must be the header node of a tree.
 496    //!   NodePtrCompare is a function object that induces a strict weak
 497    //!   ordering compatible with the strict weak ordering used to create the
 498    //!   the tree. NodePtrCompare compares two node_ptrs. "hint" is node from
 499    //!   the "header"'s tree.
 500    //!
 501    //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to
 502    //!   where it will be inserted. If "hint" is the upper_bound
 503    //!   the insertion takes constant time (two comparisons in the worst case).
 504    //!
 505    //! <b>Complexity</b>: Logarithmic in general, but it is amortized
 506    //!   constant time if new_node is inserted immediately before "hint".
 507    //!
 508    //! <b>Throws</b>: If "comp" throws.
 509    template<class NodePtrCompare, class H_Alpha>
 510    static node_ptr insert_equal
 511       (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp
 512       ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
 513    {
 514       std::size_t depth;
 515       tree_algorithms::insert_equal(header, hint, new_node, comp, &depth);
 516       rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
 517       return new_node;
 518    }
 519
 520    //! <b>Requires</b>: "header" must be the header node of a tree.
 521    //!   KeyNodePtrCompare is a function object that induces a strict weak
 522    //!   ordering compatible with the strict weak ordering used to create the
 523    //!   the tree. NodePtrCompare compares KeyType with a node_ptr.
 524    //!
 525    //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
 526    //!   tree according to "comp" and obtains the needed information to realize
 527    //!   a constant-time node insertion if there is no equivalent node.
 528    //!
 529    //! <b>Returns</b>: If there is an equivalent value
 530    //!   returns a pair containing a node_ptr to the already present node
 531    //!   and false. If there is not equivalent key can be inserted returns true
 532    //!   in the returned pair's boolean and fills "commit_data" that is meant to
 533    //!   be used with the "insert_commit" function to achieve a constant-time
 534    //!   insertion function.
 535    //!
 536    //! <b>Complexity</b>: Average complexity is at most logarithmic.
 537    //!
 538    //! <b>Throws</b>: If "comp" throws.
 539    //!
 540    //! <b>Notes</b>: This function is used to improve performance when constructing
 541    //!   a node is expensive and the user does not want to have two equivalent nodes
 542    //!   in the tree: if there is an equivalent value
 543    //!   the constructed object must be discarded. Many times, the part of the
 544    //!   node that is used to impose the order is much cheaper to construct
 545    //!   than the node and this function offers the possibility to use that part
 546    //!   to check if the insertion will be successful.
 547    //!
 548    //!   If the check is successful, the user can construct the node and use
 549    //!   "insert_commit" to insert the node in constant-time. This gives a total
 550    //!   logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
 551    //!
 552    //!   "commit_data" remains valid for a subsequent "insert_unique_commit" only
 553    //!   if no more objects are inserted or erased from the set.
 554    template<class KeyType, class KeyNodePtrCompare>
 555    static std::pair<node_ptr, bool> insert_unique_check
 556       (const const_node_ptr & header,  const KeyType &key
 557       ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
 558    {
 559       std::size_t depth;
 560       std::pair<node_ptr, bool> ret =
 561          tree_algorithms::insert_unique_check(header, key, comp, commit_data, &depth);
 562       commit_data.depth = depth;
 563       return ret;
 564    }
 565
 566
 567    //! <b>Requires</b>: "header" must be the header node of a tree.
 568    //!   "pos" must be a valid iterator or header (end) node.
 569    //!   "pos" must be an iterator pointing to the successor to "new_node"
 570    //!   once inserted according to the order of already inserted nodes. This function does not
 571    //!   check "pos" and this precondition must be guaranteed by the caller.
 572    //!
 573    //! <b>Effects</b>: Inserts new_node into the tree before "pos".
 574    //!
 575    //! <b>Complexity</b>: Constant-time.
 576    //!
 577    //! <b>Throws</b>: Nothing.
 578    //!
 579    //! <b>Note</b>: If "pos" is not the successor of the newly inserted "new_node"
 580    //! tree invariants might be broken.
 581    template<class H_Alpha>
 582    static node_ptr insert_before
 583       (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node
 584       ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
 585    {
 586       std::size_t depth;
 587       tree_algorithms::insert_before(header, pos, new_node, &depth);
 588       rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
 589       return new_node;
 590    }
 591
 592    //! <b>Requires</b>: "header" must be the header node of a tree.
 593    //!   "new_node" must be, according to the used ordering no less than the
 594    //!   greatest inserted key.
 595    //!
 596    //! <b>Effects</b>: Inserts new_node into the tree before "pos".
 597    //!
 598    //! <b>Complexity</b>: Constant-time.
 599    //!
 600    //! <b>Throws</b>: Nothing.
 601    //!
 602    //! <b>Note</b>: If "new_node" is less than the greatest inserted key
 603    //! tree invariants are broken. This function is slightly faster than
 604    //! using "insert_before".
 605    template<class H_Alpha>
 606    static void push_back(const node_ptr & header, const node_ptr & new_node
 607          ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
 608    {
 609       std::size_t depth;
 610       tree_algorithms::push_back(header, new_node, &depth);
 611       rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
 612    }
 613
 614    //! <b>Requires</b>: "header" must be the header node of a tree.
 615    //!   "new_node" must be, according to the used ordering, no greater than the
 616    //!   lowest inserted key.
 617    //!
 618    //! <b>Effects</b>: Inserts new_node into the tree before "pos".
 619    //!
 620    //! <b>Complexity</b>: Constant-time.
 621    //!
 622    //! <b>Throws</b>: Nothing.
 623    //!
 624    //! <b>Note</b>: If "new_node" is greater than the lowest inserted key
 625    //! tree invariants are broken. This function is slightly faster than
 626    //! using "insert_before".
 627    template<class H_Alpha>
 628    static void push_front(const node_ptr & header, const node_ptr & new_node
 629          ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
 630    {
 631       std::size_t depth;
 632       tree_algorithms::push_front(header, new_node, &depth);
 633       rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
 634    }
 635
 636    //! <b>Requires</b>: "header" must be the header node of a tree.
 637    //!   KeyNodePtrCompare is a function object that induces a strict weak
 638    //!   ordering compatible with the strict weak ordering used to create the
 639    //!   the tree. NodePtrCompare compares KeyType with a node_ptr.
 640    //!   "hint" is node from the "header"'s tree.
 641    //!
 642    //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the
 643    //!   tree according to "comp" using "hint" as a hint to where it should be
 644    //!   inserted and obtains the needed information to realize
 645    //!   a constant-time node insertion if there is no equivalent node.
 646    //!   If "hint" is the upper_bound the function has constant time
 647    //!   complexity (two comparisons in the worst case).
 648    //!
 649    //! <b>Returns</b>: If there is an equivalent value
 650    //!   returns a pair containing a node_ptr to the already present node
 651    //!   and false. If there is not equivalent key can be inserted returns true
 652    //!   in the returned pair's boolean and fills "commit_data" that is meant to
 653    //!   be used with the "insert_commit" function to achieve a constant-time
 654    //!   insertion function.
 655    //!
 656    //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is
 657    //!   amortized constant time if new_node should be inserted immediately before "hint".
 658    //!
 659    //! <b>Throws</b>: If "comp" throws.
 660    //!
 661    //! <b>Notes</b>: This function is used to improve performance when constructing
 662    //!   a node is expensive and the user does not want to have two equivalent nodes
 663    //!   in the tree: if there is an equivalent value
 664    //!   the constructed object must be discarded. Many times, the part of the
 665    //!   node that is used to impose the order is much cheaper to construct
 666    //!   than the node and this function offers the possibility to use that part
 667    //!   to check if the insertion will be successful.
 668    //!
 669    //!   If the check is successful, the user can construct the node and use
 670    //!   "insert_commit" to insert the node in constant-time. This gives a total
 671    //!   logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
 672    //!
 673    //!   "commit_data" remains valid for a subsequent "insert_unique_commit" only
 674    //!   if no more objects are inserted or erased from the set.
 675    template<class KeyType, class KeyNodePtrCompare>
 676    static std::pair<node_ptr, bool> insert_unique_check
 677       (const const_node_ptr & header, const node_ptr &hint, const KeyType &key
 678       ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
 679    {
 680       std::size_t depth;
 681       std::pair<node_ptr, bool> ret =
 682          tree_algorithms::insert_unique_check
 683             (header, hint, key, comp, commit_data, &depth);
 684       commit_data.depth = depth;
 685       return ret;
 686    }
 687
 688    //! <b>Requires</b>: "header" must be the header node of a tree.
 689    //!   "commit_data" must have been obtained from a previous call to
 690    //!   "insert_unique_check". No objects should have been inserted or erased
 691    //!   from the set between the "insert_unique_check" that filled "commit_data"
 692    //!   and the call to "insert_commit".
 693    //!
 694    //!
 695    //! <b>Effects</b>: Inserts new_node in the set using the information obtained
 696    //!   from the "commit_data" that a previous "insert_check" filled.
 697    //!
 698    //! <b>Complexity</b>: Constant time.
 699    //!
 700    //! <b>Throws</b>: Nothing.
 701    //!
 702    //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been
 703    //!   previously executed to fill "commit_data". No value should be inserted or
 704    //!   erased between the "insert_check" and "insert_commit" calls.
 705    template<class H_Alpha>
 706    static void insert_unique_commit
 707       (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data
 708       ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
 709    {
 710       tree_algorithms::insert_unique_commit(header, new_value, commit_data);
 711       rebalance_after_insertion(new_value, commit_data.depth, tree_size+1, h_alpha, max_tree_size);
 712    }
 713
 714    //! <b>Requires</b>: header must be the header of a tree.
 715    //!
 716    //! <b>Effects</b>: Rebalances the tree.
 717    //!
 718    //! <b>Throws</b>: Nothing.
 719    //!
 720    //! <b>Complexity</b>: Linear.
 721    static void rebalance(const node_ptr & header)
 722    {  tree_algorithms::rebalance(header); }
 723
 724    //! <b>Requires</b>: old_root is a node of a tree.
 725    //!
 726    //! <b>Effects</b>: Rebalances the subtree rooted at old_root.
 727    //!
 728    //! <b>Returns</b>: The new root of the subtree.
 729    //!
 730    //! <b>Throws</b>: Nothing.
 731    //!
 732    //! <b>Complexity</b>: Linear.
 733    static node_ptr rebalance_subtree(const node_ptr & old_root)
 734    {  return tree_algorithms::rebalance_subtree(old_root); }
 735
 736    //! <b>Requires</b>: "n" must be a node inserted in a tree.
 737    //!
 738    //! <b>Effects</b>: Returns a pointer to the header node of the tree.
 739    //!
 740    //! <b>Complexity</b>: Logarithmic.
 741    //!
 742    //! <b>Throws</b>: Nothing.
 743    static node_ptr get_header(const node_ptr & n)
 744    {  return tree_algorithms::get_header(n);   }
 745
 746    /// @cond
 747    private:
 748
 749    //! <b>Requires</b>: p is a node of a tree.
 750    //!
 751    //! <b>Effects</b>: Returns true if p is the header of the tree.
 752    //!
 753    //! <b>Complexity</b>: Constant.
 754    //!
 755    //! <b>Throws</b>: Nothing.
 756    static bool is_header(const const_node_ptr & p)
 757    {  return tree_algorithms::is_header(p);  }
 758
 759    template<class H_Alpha>
 760    static void rebalance_after_insertion
 761       (const node_ptr &x, std::size_t depth
 762       , std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
 763    {
 764       if(tree_size > max_tree_size)
 765          max_tree_size = tree_size;
 766
 767       if(tree_size != 1 && depth > h_alpha(tree_size)){
 768          //Find the first non height-balanced node
 769          //as described in the section 4.2 of the paper.
 770          //This method is the alternative method described
 771          //in the paper. Authors claim that this method
 772          //may tend to yield more balanced trees on the average
 773          //than the weight balanced method.
 774          node_ptr s = x;
 775          std::size_t size = 1;
 776
 777          for(std::size_t i = 1; true; ++i){
 778             bool rebalance = false;
 779             if(i == depth){
 780                BOOST_INTRUSIVE_INVARIANT_ASSERT(tree_size == count(s));
 781                rebalance = true;
 782             }
 783             else if(i > h_alpha(size)){
 784                node_ptr s_parent = NodeTraits::get_parent(s);
 785                node_ptr s_parent_left = NodeTraits::get_left(s_parent);
 786                size += 1 + tree_algorithms::count
 787                   ( s_parent_left == s ? NodeTraits::get_right(s_parent) : s_parent_left );
 788                s = s_parent;
 789                rebalance = true;
 790             }
 791             if(rebalance){
 792                rebalance_subtree(s);
 793                break;
 794             }
 795          }
 796       }
 797    }
 798
 799    /// @endcond
 800 };
 801
 802 } //namespace intrusive
 803 } //namespace boost
 804
 805 #include <boost/intrusive/detail/config_end.hpp>
 806
 807 #endif //BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP