Chris@16: ///////////////////////////////////////////////////////////////////////////// Chris@16: // Chris@16: // (C) Copyright Daniel K. O. 2005. Chris@101: // (C) Copyright Ion Gaztanaga 2007-2014 Chris@16: // Chris@16: // Distributed under the Boost Software License, Version 1.0. Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at Chris@16: // http://www.boost.org/LICENSE_1_0.txt) Chris@16: // Chris@16: // See http://www.boost.org/libs/intrusive for documentation. Chris@16: // Chris@16: ///////////////////////////////////////////////////////////////////////////// Chris@16: Chris@16: #ifndef BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP Chris@16: #define BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP Chris@16: Chris@16: #include Chris@101: #include Chris@16: Chris@16: #include Chris@16: Chris@16: #include Chris@101: #include Chris@101: #include Chris@16: #include Chris@101: Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE) Chris@101: # pragma once Chris@101: #endif Chris@16: Chris@16: Chris@16: namespace boost { Chris@16: namespace intrusive { Chris@16: Chris@16: /// @cond Chris@16: Chris@16: template Chris@16: struct avltree_node_cloner Chris@101: //Use public inheritance to avoid MSVC bugs with closures Chris@101: : public detail::ebo_functor_holder Chris@16: { Chris@16: typedef typename NodeTraits::node_ptr node_ptr; Chris@16: typedef detail::ebo_functor_holder base_t; Chris@16: Chris@16: avltree_node_cloner(F f) Chris@16: : base_t(f) Chris@16: {} Chris@16: Chris@16: node_ptr operator()(const node_ptr & p) Chris@16: { Chris@16: node_ptr n = base_t::get()(p); Chris@16: NodeTraits::set_balance(n, NodeTraits::get_balance(p)); Chris@16: return n; Chris@16: } Chris@101: Chris@101: node_ptr operator()(const node_ptr & p) const Chris@101: { Chris@101: node_ptr n = base_t::get()(p); Chris@101: NodeTraits::set_balance(n, NodeTraits::get_balance(p)); Chris@101: return n; Chris@101: } Chris@16: }; Chris@16: Chris@101: namespace detail { Chris@101: Chris@101: template Chris@101: struct avltree_node_checker Chris@101: : public bstree_node_checker Chris@16: { Chris@101: typedef bstree_node_checker base_checker_t; Chris@101: typedef ValueTraits value_traits; Chris@101: typedef typename value_traits::node_traits node_traits; Chris@101: typedef typename node_traits::const_node_ptr const_node_ptr; Chris@16: Chris@101: struct return_type Chris@101: : public base_checker_t::return_type Chris@101: { Chris@101: return_type() : height(0) {} Chris@101: int height; Chris@101: }; Chris@101: Chris@101: avltree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) Chris@101: : base_checker_t(comp, extra_checker) Chris@101: {} Chris@101: Chris@101: void operator () (const const_node_ptr& p, Chris@101: const return_type& check_return_left, const return_type& check_return_right, Chris@101: return_type& check_return) Chris@101: { Chris@101: const int height_diff = check_return_right.height - check_return_left.height; (void)height_diff; Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT( Chris@101: (height_diff == -1 && node_traits::get_balance(p) == node_traits::negative()) || Chris@101: (height_diff == 0 && node_traits::get_balance(p) == node_traits::zero()) || Chris@101: (height_diff == 1 && node_traits::get_balance(p) == node_traits::positive()) Chris@101: ); Chris@101: check_return.height = 1 + Chris@101: (check_return_left.height > check_return_right.height ? check_return_left.height : check_return_right.height); Chris@101: base_checker_t::operator()(p, check_return_left, check_return_right, check_return); Chris@101: } Chris@16: }; Chris@16: Chris@101: } // namespace detail Chris@101: Chris@16: /// @endcond Chris@16: Chris@16: //! avltree_algorithms is configured with a NodeTraits class, which encapsulates the Chris@16: //! information about the node to be manipulated. NodeTraits must support the Chris@16: //! following interface: Chris@16: //! Chris@16: //! Typedefs: Chris@16: //! Chris@16: //! node: The type of the node that forms the binary search tree Chris@16: //! Chris@16: //! node_ptr: A pointer to a node Chris@16: //! Chris@16: //! const_node_ptr: A pointer to a const node Chris@16: //! Chris@16: //! balance: The type of the balance factor Chris@16: //! Chris@16: //! Static functions: Chris@16: //! Chris@16: //! static node_ptr get_parent(const_node_ptr n); Chris@16: //! Chris@16: //! static void set_parent(node_ptr n, node_ptr parent); Chris@16: //! Chris@16: //! static node_ptr get_left(const_node_ptr n); Chris@16: //! Chris@16: //! static void set_left(node_ptr n, node_ptr left); Chris@16: //! Chris@16: //! static node_ptr get_right(const_node_ptr n); Chris@16: //! Chris@16: //! static void set_right(node_ptr n, node_ptr right); Chris@16: //! Chris@16: //! static balance get_balance(const_node_ptr n); Chris@16: //! Chris@16: //! static void set_balance(node_ptr n, balance b); Chris@16: //! Chris@16: //! static balance negative(); Chris@16: //! Chris@16: //! static balance zero(); Chris@16: //! Chris@16: //! static balance positive(); Chris@16: template Chris@16: class avltree_algorithms Chris@16: #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: : public bstree_algorithms Chris@16: #endif Chris@16: { Chris@16: public: Chris@16: typedef typename NodeTraits::node node; Chris@16: typedef NodeTraits node_traits; Chris@16: typedef typename NodeTraits::node_ptr node_ptr; Chris@16: typedef typename NodeTraits::const_node_ptr const_node_ptr; Chris@16: typedef typename NodeTraits::balance balance; Chris@16: Chris@16: /// @cond Chris@16: private: Chris@16: typedef bstree_algorithms bstree_algo; Chris@16: Chris@16: /// @endcond Chris@16: Chris@16: public: Chris@16: //! This type is the information that will be Chris@16: //! filled by insert_unique_check Chris@16: typedef typename bstree_algo::insert_commit_data insert_commit_data; Chris@16: Chris@16: #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) Chris@16: static node_ptr get_header(const const_node_ptr & n); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node Chris@16: static node_ptr begin_node(const const_node_ptr & header); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::end_node Chris@16: static node_ptr end_node(const const_node_ptr & header); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree Chris@16: static void swap_tree(const node_ptr & header1, const node_ptr & header2); Chris@101: Chris@16: #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) Chris@16: static void swap_nodes(const node_ptr & node1, const node_ptr & node2) Chris@16: { Chris@16: if(node1 == node2) Chris@16: return; Chris@16: Chris@16: node_ptr header1(bstree_algo::get_header(node1)), header2(bstree_algo::get_header(node2)); Chris@16: swap_nodes(node1, header1, node2, header2); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&) Chris@16: static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2) Chris@16: { Chris@16: if(node1 == node2) return; Chris@16: Chris@16: bstree_algo::swap_nodes(node1, header1, node2, header2); Chris@16: //Swap balance Chris@16: balance c = NodeTraits::get_balance(node1); Chris@16: NodeTraits::set_balance(node1, NodeTraits::get_balance(node2)); Chris@16: NodeTraits::set_balance(node2, c); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) Chris@16: static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node) Chris@16: { Chris@16: if(node_to_be_replaced == new_node) Chris@16: return; Chris@16: replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) Chris@16: static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node) Chris@16: { Chris@16: bstree_algo::replace_node(node_to_be_replaced, header, new_node); Chris@16: NodeTraits::set_balance(new_node, NodeTraits::get_balance(node_to_be_replaced)); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&) Chris@16: static void unlink(const node_ptr & node) Chris@16: { Chris@16: node_ptr x = NodeTraits::get_parent(node); Chris@16: if(x){ Chris@16: while(!is_header(x)) Chris@16: x = NodeTraits::get_parent(x); Chris@16: erase(x, node); Chris@16: } Chris@16: } Chris@16: Chris@16: #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance Chris@16: static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) Chris@16: static bool unique(const const_node_ptr & node); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) Chris@16: static std::size_t size(const const_node_ptr & header); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) Chris@16: static node_ptr next_node(const node_ptr & node); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) Chris@16: static node_ptr prev_node(const node_ptr & node); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) Chris@16: static void init(const node_ptr & node); Chris@16: #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! Requires: node must not be part of any tree. Chris@16: //! Chris@16: //! Effects: Initializes the header to represent an empty tree. Chris@16: //! unique(header) == true. Chris@16: //! Chris@16: //! Complexity: Constant. Chris@16: //! Chris@16: //! Throws: Nothing. Chris@16: //! Chris@16: //! Nodes: If node is inserted in a tree, this function corrupts the tree. Chris@16: static void init_header(const node_ptr & header) Chris@16: { Chris@16: bstree_algo::init_header(header); Chris@16: NodeTraits::set_balance(header, NodeTraits::zero()); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) Chris@16: static node_ptr erase(const node_ptr & header, const node_ptr & z) Chris@16: { Chris@16: typename bstree_algo::data_for_rebalance info; Chris@101: bstree_algo::erase(header, z, info); Chris@101: if(info.y != z){ Chris@101: NodeTraits::set_balance(info.y, NodeTraits::get_balance(z)); Chris@101: } Chris@16: //Rebalance avltree Chris@16: rebalance_after_erasure(header, info.x, info.x_parent); Chris@16: return z; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) Chris@16: template Chris@16: static void clone Chris@16: (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer) Chris@16: { Chris@16: avltree_node_cloner new_cloner(cloner); Chris@16: bstree_algo::clone(source_header, target_header, new_cloner, disposer); Chris@16: } Chris@16: Chris@16: #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) Chris@16: template Chris@16: static void clear_and_dispose(const node_ptr & header, Disposer disposer); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static node_ptr lower_bound Chris@16: (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static node_ptr upper_bound Chris@16: (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static node_ptr find Chris@16: (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static std::pair equal_range Chris@16: (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) Chris@16: template Chris@16: static std::pair bounded_range Chris@16: (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp Chris@16: , bool left_closed, bool right_closed); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@101: Chris@16: #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) Chris@16: template Chris@16: static node_ptr insert_equal_upper_bound Chris@16: (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) Chris@16: { Chris@16: bstree_algo::insert_equal_upper_bound(h, new_node, comp); Chris@16: rebalance_after_insertion(h, new_node); Chris@16: return new_node; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) Chris@16: template Chris@16: static node_ptr insert_equal_lower_bound Chris@16: (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) Chris@16: { Chris@16: bstree_algo::insert_equal_lower_bound(h, new_node, comp); Chris@16: rebalance_after_insertion(h, new_node); Chris@16: return new_node; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) Chris@16: template Chris@16: static node_ptr insert_equal Chris@16: (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) Chris@16: { Chris@16: bstree_algo::insert_equal(header, hint, new_node, comp); Chris@16: rebalance_after_insertion(header, new_node); Chris@16: return new_node; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) Chris@16: static node_ptr insert_before Chris@16: (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node) Chris@16: { Chris@16: bstree_algo::insert_before(header, pos, new_node); Chris@16: rebalance_after_insertion(header, new_node); Chris@16: return new_node; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) Chris@16: static void push_back(const node_ptr & header, const node_ptr & new_node) Chris@16: { Chris@16: bstree_algo::push_back(header, new_node); Chris@16: rebalance_after_insertion(header, new_node); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) Chris@16: static void push_front(const node_ptr & header, const node_ptr & new_node) Chris@16: { Chris@16: bstree_algo::push_front(header, new_node); Chris@16: rebalance_after_insertion(header, new_node); Chris@16: } Chris@16: Chris@16: #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) Chris@16: template Chris@16: static std::pair insert_unique_check Chris@16: (const const_node_ptr & header, const KeyType &key Chris@16: ,KeyNodePtrCompare comp, insert_commit_data &commit_data); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) Chris@16: template Chris@16: static std::pair insert_unique_check Chris@16: (const const_node_ptr & header, const node_ptr &hint, const KeyType &key Chris@16: ,KeyNodePtrCompare comp, insert_commit_data &commit_data); Chris@16: #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data &) Chris@16: static void insert_unique_commit Chris@16: (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data) Chris@16: { Chris@16: bstree_algo::insert_unique_commit(header, new_value, commit_data); Chris@16: rebalance_after_insertion(header, new_value); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::is_header Chris@16: static bool is_header(const const_node_ptr & p) Chris@16: { return NodeTraits::get_balance(p) == NodeTraits::zero() && bstree_algo::is_header(p); } Chris@16: Chris@16: Chris@16: /// @cond Chris@101: static bool verify(const node_ptr &header) Chris@101: { Chris@101: std::size_t height; Chris@101: std::size_t count; Chris@101: return verify_recursion(NodeTraits::get_parent(header), count, height); Chris@101: } Chris@101: Chris@16: private: Chris@16: Chris@101: static bool verify_recursion(node_ptr n, std::size_t &count, std::size_t &height) Chris@16: { Chris@101: if (!n){ Chris@101: count = 0; Chris@101: height = 0; Chris@101: return true; Chris@101: } Chris@101: std::size_t leftcount, rightcount; Chris@101: std::size_t leftheight, rightheight; Chris@101: if(!verify_recursion(NodeTraits::get_left (n), leftcount, leftheight) || Chris@101: !verify_recursion(NodeTraits::get_right(n), rightcount, rightheight) ){ Chris@101: return false; Chris@101: } Chris@101: count = 1u + leftcount + rightcount; Chris@101: height = 1u + (leftheight > rightheight ? leftheight : rightheight); Chris@101: Chris@101: //If equal height, balance must be zero Chris@101: if(rightheight == leftheight){ Chris@101: if(NodeTraits::get_balance(n) != NodeTraits::zero()){ Chris@101: BOOST_ASSERT(0); Chris@101: return false; Chris@101: } Chris@101: } Chris@101: //If right is taller than left, then the difference must be at least 1 and the balance positive Chris@101: else if(rightheight > leftheight){ Chris@101: if(rightheight - leftheight > 1 ){ Chris@101: BOOST_ASSERT(0); Chris@101: return false; Chris@101: } Chris@101: else if(NodeTraits::get_balance(n) != NodeTraits::positive()){ Chris@101: BOOST_ASSERT(0); Chris@101: return false; Chris@101: } Chris@101: } Chris@101: //If left is taller than right, then the difference must be at least 1 and the balance negative Chris@101: else{ Chris@101: if(leftheight - rightheight > 1 ){ Chris@101: BOOST_ASSERT(0); Chris@101: return false; Chris@101: } Chris@101: else if(NodeTraits::get_balance(n) != NodeTraits::negative()){ Chris@101: BOOST_ASSERT(0); Chris@101: return false; Chris@101: } Chris@101: } Chris@101: return true; Chris@101: } Chris@101: Chris@101: static void rebalance_after_erasure(const node_ptr & header, node_ptr x, node_ptr x_parent) Chris@101: { Chris@101: for ( node_ptr root = NodeTraits::get_parent(header) Chris@101: ; x != root Chris@101: ; root = NodeTraits::get_parent(header), x_parent = NodeTraits::get_parent(x)) { Chris@16: const balance x_parent_balance = NodeTraits::get_balance(x_parent); Chris@101: //Don't cache x_is_leftchild or similar because x can be null and Chris@101: //equal to both x_parent_left and x_parent_right Chris@101: const node_ptr x_parent_left (NodeTraits::get_left(x_parent)); Chris@101: const node_ptr x_parent_right(NodeTraits::get_right(x_parent)); Chris@101: Chris@16: if(x_parent_balance == NodeTraits::zero()){ Chris@101: NodeTraits::set_balance( x_parent, x == x_parent_right ? NodeTraits::negative() : NodeTraits::positive() ); Chris@16: break; // the height didn't change, let's stop here Chris@16: } Chris@16: else if(x_parent_balance == NodeTraits::negative()){ Chris@101: if (x == x_parent_left) { ////x is left child or x and sibling are null Chris@16: NodeTraits::set_balance(x_parent, NodeTraits::zero()); // balanced Chris@16: x = x_parent; Chris@16: } Chris@16: else { Chris@101: // x is right child (x_parent_left is the left child) Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(x_parent_left); Chris@101: if (NodeTraits::get_balance(x_parent_left) == NodeTraits::positive()) { Chris@101: // x_parent_left MUST have a right child Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(x_parent_left)); Chris@101: x = avl_rotate_left_right(x_parent, x_parent_left, header); Chris@16: } Chris@16: else { Chris@101: avl_rotate_right(x_parent, x_parent_left, header); Chris@101: x = x_parent_left; Chris@16: } Chris@16: Chris@16: // if changed from negative to NodeTraits::positive(), no need to check above Chris@16: if (NodeTraits::get_balance(x) == NodeTraits::positive()){ Chris@16: break; Chris@16: } Chris@16: } Chris@16: } Chris@16: else if(x_parent_balance == NodeTraits::positive()){ Chris@101: if (x == x_parent_right) { //x is right child or x and sibling are null Chris@16: NodeTraits::set_balance(x_parent, NodeTraits::zero()); // balanced Chris@16: x = x_parent; Chris@16: } Chris@16: else { Chris@101: // x is left child (x_parent_right is the right child) Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(x_parent_right); Chris@101: if (NodeTraits::get_balance(x_parent_right) == NodeTraits::negative()) { Chris@101: // x_parent_right MUST have then a left child Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(x_parent_right)); Chris@101: x = avl_rotate_right_left(x_parent, x_parent_right, header); Chris@16: } Chris@16: else { Chris@101: avl_rotate_left(x_parent, x_parent_right, header); Chris@101: x = x_parent_right; Chris@16: } Chris@16: // if changed from NodeTraits::positive() to negative, no need to check above Chris@16: if (NodeTraits::get_balance(x) == NodeTraits::negative()){ Chris@16: break; Chris@16: } Chris@16: } Chris@16: } Chris@16: else{ Chris@16: BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached Chris@16: } Chris@16: } Chris@16: } Chris@16: Chris@101: static void rebalance_after_insertion(const node_ptr & header, node_ptr x) Chris@16: { Chris@16: NodeTraits::set_balance(x, NodeTraits::zero()); Chris@16: // Rebalance. Chris@16: for(node_ptr root = NodeTraits::get_parent(header); x != root; root = NodeTraits::get_parent(header)){ Chris@101: node_ptr const x_parent(NodeTraits::get_parent(x)); Chris@101: node_ptr const x_parent_left(NodeTraits::get_left(x_parent)); Chris@101: const balance x_parent_balance = NodeTraits::get_balance(x_parent); Chris@101: const bool x_is_leftchild(x == x_parent_left); Chris@16: if(x_parent_balance == NodeTraits::zero()){ Chris@16: // if x is left, parent will have parent->bal_factor = negative Chris@16: // else, parent->bal_factor = NodeTraits::positive() Chris@101: NodeTraits::set_balance( x_parent, x_is_leftchild ? NodeTraits::negative() : NodeTraits::positive() ); Chris@101: x = x_parent; Chris@16: } Chris@16: else if(x_parent_balance == NodeTraits::positive()){ Chris@16: // if x is a left child, parent->bal_factor = zero Chris@101: if (x_is_leftchild) Chris@101: NodeTraits::set_balance(x_parent, NodeTraits::zero()); Chris@16: else{ // x is a right child, needs rebalancing Chris@16: if (NodeTraits::get_balance(x) == NodeTraits::negative()) Chris@101: avl_rotate_right_left(x_parent, x, header); Chris@16: else Chris@101: avl_rotate_left(x_parent, x, header); Chris@16: } Chris@16: break; Chris@16: } Chris@16: else if(x_parent_balance == NodeTraits::negative()){ Chris@16: // if x is a left child, needs rebalancing Chris@101: if (x_is_leftchild) { Chris@16: if (NodeTraits::get_balance(x) == NodeTraits::positive()) Chris@101: avl_rotate_left_right(x_parent, x, header); Chris@16: else Chris@101: avl_rotate_right(x_parent, x, header); Chris@16: } Chris@16: else Chris@101: NodeTraits::set_balance(x_parent, NodeTraits::zero()); Chris@16: break; Chris@16: } Chris@16: else{ Chris@16: BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached Chris@16: } Chris@16: } Chris@16: } Chris@16: Chris@16: static void left_right_balancing(const node_ptr & a, const node_ptr & b, const node_ptr & c) Chris@16: { Chris@16: // balancing... Chris@16: const balance c_balance = NodeTraits::get_balance(c); Chris@16: const balance zero_balance = NodeTraits::zero(); Chris@101: const balance posi_balance = NodeTraits::positive(); Chris@101: const balance nega_balance = NodeTraits::negative(); Chris@16: NodeTraits::set_balance(c, zero_balance); Chris@101: if(c_balance == nega_balance){ Chris@101: NodeTraits::set_balance(a, posi_balance); Chris@16: NodeTraits::set_balance(b, zero_balance); Chris@16: } Chris@16: else if(c_balance == zero_balance){ Chris@16: NodeTraits::set_balance(a, zero_balance); Chris@16: NodeTraits::set_balance(b, zero_balance); Chris@16: } Chris@101: else if(c_balance == posi_balance){ Chris@16: NodeTraits::set_balance(a, zero_balance); Chris@101: NodeTraits::set_balance(b, nega_balance); Chris@16: } Chris@16: else{ Chris@16: BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached Chris@16: } Chris@16: } Chris@16: Chris@101: static node_ptr avl_rotate_left_right(const node_ptr a, const node_ptr a_oldleft, const node_ptr & hdr) Chris@101: { // [note: 'a_oldleft' is 'b'] Chris@16: // | | // Chris@16: // a(-2) c // Chris@16: // / \ / \ // Chris@16: // / \ ==> / \ // Chris@16: // (pos)b [g] b a // Chris@16: // / \ / \ / \ // Chris@16: // [d] c [d] e f [g] // Chris@101: // / \ // Chris@101: // e f // Chris@101: const node_ptr c = NodeTraits::get_right(a_oldleft); Chris@101: bstree_algo::rotate_left_no_parent_fix(a_oldleft, c); Chris@101: //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_left(a, c)] Chris@101: //as c is not root and another rotation is coming Chris@101: bstree_algo::rotate_right(a, c, NodeTraits::get_parent(a), hdr); Chris@101: left_right_balancing(a, a_oldleft, c); Chris@101: return c; Chris@16: } Chris@16: Chris@101: static node_ptr avl_rotate_right_left(const node_ptr a, const node_ptr a_oldright, const node_ptr & hdr) Chris@101: { // [note: 'a_oldright' is 'b'] Chris@16: // | | // Chris@16: // a(pos) c // Chris@16: // / \ / \ // Chris@16: // / \ / \ // Chris@16: // [d] b(neg) ==> a b // Chris@16: // / \ / \ / \ // Chris@16: // c [g] [d] e f [g] // Chris@16: // / \ // Chris@16: // e f // Chris@101: const node_ptr c (NodeTraits::get_left(a_oldright)); Chris@101: bstree_algo::rotate_right_no_parent_fix(a_oldright, c); Chris@101: //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_right(a, c)] Chris@101: //as c is not root and another rotation is coming. Chris@101: bstree_algo::rotate_left(a, c, NodeTraits::get_parent(a), hdr); Chris@101: left_right_balancing(a_oldright, a, c); Chris@101: return c; Chris@16: } Chris@16: Chris@101: static void avl_rotate_left(const node_ptr &x, const node_ptr &x_oldright, const node_ptr & hdr) Chris@16: { Chris@101: bstree_algo::rotate_left(x, x_oldright, NodeTraits::get_parent(x), hdr); Chris@16: Chris@16: // reset the balancing factor Chris@101: if (NodeTraits::get_balance(x_oldright) == NodeTraits::positive()) { Chris@16: NodeTraits::set_balance(x, NodeTraits::zero()); Chris@101: NodeTraits::set_balance(x_oldright, NodeTraits::zero()); Chris@16: } Chris@16: else { // this doesn't happen during insertions Chris@16: NodeTraits::set_balance(x, NodeTraits::positive()); Chris@101: NodeTraits::set_balance(x_oldright, NodeTraits::negative()); Chris@16: } Chris@16: } Chris@16: Chris@101: static void avl_rotate_right(const node_ptr &x, const node_ptr &x_oldleft, const node_ptr & hdr) Chris@16: { Chris@101: bstree_algo::rotate_right(x, x_oldleft, NodeTraits::get_parent(x), hdr); Chris@16: Chris@16: // reset the balancing factor Chris@101: if (NodeTraits::get_balance(x_oldleft) == NodeTraits::negative()) { Chris@16: NodeTraits::set_balance(x, NodeTraits::zero()); Chris@101: NodeTraits::set_balance(x_oldleft, NodeTraits::zero()); Chris@16: } Chris@16: else { // this doesn't happen during insertions Chris@16: NodeTraits::set_balance(x, NodeTraits::negative()); Chris@101: NodeTraits::set_balance(x_oldleft, NodeTraits::positive()); Chris@16: } Chris@16: } Chris@16: Chris@16: /// @endcond Chris@16: }; Chris@16: Chris@16: /// @cond Chris@16: Chris@16: template Chris@16: struct get_algo Chris@16: { Chris@16: typedef avltree_algorithms type; Chris@16: }; Chris@16: Chris@101: template Chris@101: struct get_node_checker Chris@101: { Chris@101: typedef detail::avltree_node_checker type; Chris@101: }; Chris@101: Chris@16: /// @endcond Chris@16: Chris@16: } //namespace intrusive Chris@16: } //namespace boost Chris@16: Chris@16: #include Chris@16: Chris@16: #endif //BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP