view release on metacpan or  search on metacpan

include/boost/intrusive/avltree_algorithms.hpp  view on Meta::CPAN

   template<class NodePtrCompare>
   static node_ptr insert_equal
      (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp)
   {
      bstree_algo::insert_equal(header, hint, new_node, comp);
      rebalance_after_insertion(header, new_node);
      return new_node;
   }

   //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&)
   static node_ptr insert_before
      (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node)
   {
      bstree_algo::insert_before(header, pos, new_node);
      rebalance_after_insertion(header, new_node);
      return new_node;
   }

   //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&)
   static void push_back(const node_ptr & header, const node_ptr & new_node)
   {
      bstree_algo::push_back(header, new_node);
      rebalance_after_insertion(header, new_node);
   }

   //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&)
   static void push_front(const node_ptr & header, const node_ptr & new_node)
   {
      bstree_algo::push_front(header, new_node);
      rebalance_after_insertion(header, new_node);
   }

   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
   //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
   template<class KeyType, class KeyNodePtrCompare>
   static std::pair<node_ptr, bool> insert_unique_check
      (const const_node_ptr & header,  const KeyType &key
      ,KeyNodePtrCompare comp, insert_commit_data &commit_data);

   //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
   template<class KeyType, class KeyNodePtrCompare>
   static std::pair<node_ptr, bool> insert_unique_check
      (const const_node_ptr & header, const node_ptr &hint, const KeyType &key
      ,KeyNodePtrCompare comp, insert_commit_data &commit_data);
   #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED

   //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data &)
   static void insert_unique_commit
      (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
   {
      bstree_algo::insert_unique_commit(header, new_value, commit_data);
      rebalance_after_insertion(header, new_value);
   }

   //! @copydoc ::boost::intrusive::bstree_algorithms::is_header
   static bool is_header(const const_node_ptr & p)
   {  return NodeTraits::get_balance(p) == NodeTraits::zero() && bstree_algo::is_header(p);  }


   /// @cond
   static bool verify(const node_ptr &header)
   {
      std::size_t height;
      std::size_t count;
      return verify_recursion(NodeTraits::get_parent(header), count, height);
   }

   private:

   static bool verify_recursion(node_ptr n, std::size_t &count, std::size_t &height)
   {
      if (!n){
         count = 0;
         height = 0;
         return true;
      }
      std::size_t leftcount, rightcount;
      std::size_t leftheight, rightheight;
      if(!verify_recursion(NodeTraits::get_left (n), leftcount,  leftheight) ||
         !verify_recursion(NodeTraits::get_right(n), rightcount, rightheight) ){
         return false;
      }
      count = 1u + leftcount + rightcount;
      height = 1u + (leftheight > rightheight ? leftheight : rightheight);

      //If equal height, balance must be zero
      if(rightheight == leftheight){
         if(NodeTraits::get_balance(n) != NodeTraits::zero()){
            BOOST_ASSERT(0);
            return false;
         }
      }
      //If right is taller than left, then the difference must be at least 1 and the balance positive
      else if(rightheight > leftheight){
         if(rightheight - leftheight > 1 ){
            BOOST_ASSERT(0);
            return false;
         }
         else if(NodeTraits::get_balance(n) != NodeTraits::positive()){
            BOOST_ASSERT(0);
            return false;
         }
      }
      //If left is taller than right, then the difference must be at least 1 and the balance negative
      else{
         if(leftheight - rightheight > 1 ){
            BOOST_ASSERT(0);
            return false;
         }
         else if(NodeTraits::get_balance(n) != NodeTraits::negative()){
            BOOST_ASSERT(0);
            return false;
         }
      }
      return true;
   }

   static void rebalance_after_erasure
      ( const node_ptr & header, const node_ptr &z, const typename bstree_algo::data_for_rebalance &info)
   {
      if(info.y != z){
         NodeTraits::set_balance(info.y, NodeTraits::get_balance(z));
      }
      //Rebalance avltree
      rebalance_after_erasure_restore_invariants(header, info.x, info.x_parent);
   }

   static void rebalance_after_erasure_restore_invariants(const node_ptr & header, node_ptr x, node_ptr x_parent)
   {
      for ( node_ptr root = NodeTraits::get_parent(header)
          ; x != root
          ; root = NodeTraits::get_parent(header), x_parent = NodeTraits::get_parent(x)) {
         const balance x_parent_balance = NodeTraits::get_balance(x_parent);
         //Don't cache x_is_leftchild or similar because x can be null and
         //equal to both x_parent_left and x_parent_right
         const node_ptr x_parent_left (NodeTraits::get_left(x_parent));
         const node_ptr x_parent_right(NodeTraits::get_right(x_parent));

         if(x_parent_balance == NodeTraits::zero()){
            NodeTraits::set_balance( x_parent, x == x_parent_right ? NodeTraits::negative() : NodeTraits::positive() );