tree_algorithms.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 1,626 行 · 第 1/4 页

         rightmost_out  = rightmost;
      }
      return target_sub_root;
   }

   template<class Disposer>
   static void dispose_subtree(node_ptr x, Disposer disposer)
   {
      node_ptr save;
      while (x){
         save = NodeTraits::get_left(x);
         if (save) {
            // Right rotation
            NodeTraits::set_left(x, NodeTraits::get_right(save));
            NodeTraits::set_right(save, x);
         }
         else {
            save = NodeTraits::get_right(x);
            init(x);
            disposer(x);
         }
         x = save;
      }
   }

   //! <b>Requires</b>: p is a node of a tree.
   //! 
   //! <b>Effects</b>: Returns true if p is a left child.
   //! 
   //! <b>Complexity</b>: Constant.
   //! 
   //! <b>Throws</b>: Nothing.
   static bool is_left_child(node_ptr p)
   {  return NodeTraits::get_left(NodeTraits::get_parent(p)) == p;  }

   //! <b>Requires</b>: p is a node of a tree.
   //! 
   //! <b>Effects</b>: Returns true if p is a right child.
   //! 
   //! <b>Complexity</b>: Constant.
   //! 
   //! <b>Throws</b>: Nothing.
   static bool is_right_child (node_ptr p)
   {  return NodeTraits::get_right(NodeTraits::get_parent(p)) == p;  }

   static void replace_own (node_ptr own, node_ptr x, node_ptr header)
   {
      if(NodeTraits::get_parent(header) == own)
         NodeTraits::set_parent(header, x);
      else if(is_left_child(own))
         NodeTraits::set_left(NodeTraits::get_parent(own), x);
      else
         NodeTraits::set_right(NodeTraits::get_parent(own), x);
   }

   static void rotate_left(node_ptr p, node_ptr header)
   {
      node_ptr x = NodeTraits::get_right(p);
      NodeTraits::set_right(p, NodeTraits::get_left(x));
      if(NodeTraits::get_left(x) != 0)
         NodeTraits::set_parent(NodeTraits::get_left(x), p);
      NodeTraits::set_parent(x, NodeTraits::get_parent(p));
      replace_own (p, x, header);
      NodeTraits::set_left(x, p);
      NodeTraits::set_parent(p, x);
   }

   static void rotate_right(node_ptr p, node_ptr header)
   {
      node_ptr x(NodeTraits::get_left(p));
      node_ptr x_right(NodeTraits::get_right(x));
      NodeTraits::set_left(p, x_right);
      if(x_right)
         NodeTraits::set_parent(x_right, p);
      NodeTraits::set_parent(x, NodeTraits::get_parent(p));
      replace_own (p, x, header);
      NodeTraits::set_right(x, p);
      NodeTraits::set_parent(p, x);
   }

   // rotate node t with left child            | complexity : constant        | exception : nothrow
   static node_ptr rotate_left(node_ptr t)
   {
      node_ptr x = NodeTraits::get_right(t);
      NodeTraits::set_right(t, NodeTraits::get_left(x));

      if( NodeTraits::get_right(t) != 0 ){
         NodeTraits::set_parent(NodeTraits::get_right(t), t );
      }
      NodeTraits::set_left(x, t);
      NodeTraits::set_parent(t, x);
      return x;
   }

   // rotate node t with right child            | complexity : constant        | exception : nothrow
   static node_ptr rotate_right(node_ptr t)
   {
      node_ptr x = NodeTraits::get_left(t);
      NodeTraits::set_left(t, NodeTraits::get_right(x));
      if( NodeTraits::get_left(t) != 0 ){
         NodeTraits::set_parent(NodeTraits::get_left(t), t);
      }
      NodeTraits::set_right(x, t);
      NodeTraits::set_parent(t, x);
      return x;
   }

   static void link(node_ptr header, node_ptr z, node_ptr par, bool left)
   {
      if(par == header){
         NodeTraits::set_parent(header, z);
         NodeTraits::set_right(header, z);
         NodeTraits::set_left(header, z);
      }
      else if(left){
         NodeTraits::set_left(par, z);
         if(par == NodeTraits::get_left(header))
             NodeTraits::set_left(header, z);
      }
      else{
         NodeTraits::set_right(par, z);
         if(par == NodeTraits::get_right(header))
             NodeTraits::set_right(header, z);
      }
      NodeTraits::set_parent(z, par);
      NodeTraits::set_right(z, node_ptr(0));
      NodeTraits::set_left(z, node_ptr(0));
   }

   static void erase(node_ptr header, node_ptr z)
   {
      data_for_rebalance ignored;
      erase(header, z, nop_erase_fixup(), ignored);
   }

   struct data_for_rebalance
   {
      node_ptr x;
      node_ptr x_parent;
      node_ptr y;
   };

   template<class F>
   static void erase(node_ptr header, node_ptr z, F z_and_successor_fixup, data_for_rebalance &info)
   {
      erase_impl(header, z, info);
      if(info.y != z){
         z_and_successor_fixup(z, info.y);
      }
   }

   static void unlink(node_ptr node)
   {
      node_ptr x = NodeTraits::get_parent(node);
      if(x){
         while(!is_header(x))
            x = NodeTraits::get_parent(x);
         erase(x, node);
      }
   }

   static void tree_to_vine(node_ptr header)
   {  subtree_to_vine(NodeTraits::get_parent(header)); }

   static void vine_to_tree(node_ptr header, std::size_t count)
   {  vine_to_subtree(NodeTraits::get_parent(header), count);  }

   static void rebalance(node_ptr header)
   {
      //Taken from:
      //"Tree rebalancing in optimal time and space"
      //Quentin F. Stout and Bette L. Warren
      std::size_t len = 0;
      subtree_to_vine(NodeTraits::get_parent(header), &len);
      vine_to_subtree(NodeTraits::get_parent(header), len);
   }

   static node_ptr rebalance_subtree(node_ptr old_root)
   {
      std::size_t len = 0;
      node_ptr new_root = subtree_to_vine(old_root, &len);
      return vine_to_subtree(new_root, len);
   }

   static node_ptr subtree_to_vine(node_ptr old_root, std::size_t *plen = 0)
   {
      std::size_t len;
      len = 0;
      if(!old_root)   return node_ptr(0);

      //To avoid irregularities in the algorithm (old_root can be a
      //left or right child or even the root of the tree) just put the 
      //root as the right child of its parent. Before doing this backup
      //information to restore the original relationship after
      //the algorithm is applied.
      node_ptr super_root = NodeTraits::get_parent(old_root);
      BOOST_INTRUSIVE_INVARIANT_ASSERT(super_root);

      //Get info
      node_ptr super_root_right_backup = NodeTraits::get_right(super_root);
      bool super_root_is_header   = is_header(super_root);
      bool old_root_is_right  = is_right_child(old_root);

      node_ptr x(old_root);
      node_ptr new_root(x);
      node_ptr save;
      bool moved_to_right = false;
      for( ; x; x = save){
         save = NodeTraits::get_left(x);
         if(save){
            // Right rotation
            node_ptr save_right = NodeTraits::get_right(save);
            node_ptr x_parent   = NodeTraits::get_parent(x);
            NodeTraits::set_parent(save, x_parent);
            NodeTraits::set_right (x_parent, save);
            NodeTraits::set_parent(x, save);
            NodeTraits::set_right (save, x);
            NodeTraits::set_left(x, save_right);
            if(save_right)
               NodeTraits::set_parent(save_right, x);
            if(!moved_to_right)
               new_root = save;
         }
         else{
            moved_to_right = true;
            save = NodeTraits::get_right(x);
            ++len;
         }
      }

      if(super_root_is_header){
         NodeTraits::set_right(super_root, super_root_right_backup);
         NodeTraits::set_parent(super_root, new_root);
      }
      else if(old_root_is_right){
         NodeTraits::set_right(super_root, new_root);
      }
      else{
         NodeTraits::set_right(super_root, super_root_right_backup);
         NodeTraits::set_left(super_root, new_root);
      }
      if(plen) *plen = len;
      return new_root;
   }

   static node_ptr vine_to_subtree(node_ptr old_root, std::size_t count)
   {
      std::size_t leaf_nodes = count + 1 - ((size_t) 1 << floor_log2 (count + 1));
      std::size_t vine_nodes = count - leaf_nodes;

      node_ptr new_root = compress_subtree(old_root, leaf_nodes);
      while(vine_nodes > 1){
         vine_nodes /= 2;
         new_root = compress_subtree(new_root, vine_nodes);
      }
      return new_root;
   }

   static node_ptr compress_subtree(node_ptr old_root, std::size_t count)
   {
      if(!old_root)   return old_root;

      //To avoid irregularities in the algorithm (old_root can be
      //left or right child or even the root of the tree) just put the 
      //root as the right child of its parent. First obtain
      //information to restore the original relationship after
      //the algorithm is applied.
      node_ptr super_root = NodeTraits::get_parent(old_root);
      BOOST_INTRUSIVE_INVARIANT_ASSERT(super_root);

      //Get info
      node_ptr super_root_right_backup = NodeTraits::get_right(super_root);
      bool super_root_is_header   = is_header(super_root);
      bool old_root_is_right  = is_right_child(old_root);

      //Put old_root as right child
      NodeTraits::set_right(super_root, old_root);

      //Start the compression algorithm            
      node_ptr even_parent = super_root;
      node_ptr new_root = old_root;

      while(count--){
         node_ptr even = NodeTraits::get_right(even_parent);
         node_ptr odd = NodeTraits::get_right(even);

         if(new_root == old_root)
            new_root = odd;

         node_ptr even_right = NodeTraits::get_left(odd);
         NodeTraits::set_right(even, even_right);
         if (even_right)
            NodeTraits::set_parent(even_right, even);

         NodeTraits::set_right(even_parent, odd);
         NodeTraits::set_parent(odd, even_parent);
         NodeTraits::set_left(odd, even);
         NodeTraits::set_parent(even, odd);
         even_parent = odd;
      }

      if(super_root_is_header){
         NodeTraits::set_parent(super_root, new_root);
         NodeTraits::set_right(super_root, super_root_right_backup);
      }
      else if(old_root_is_right){
         NodeTraits::set_right(super_root, new_root);
      }
      else{
         NodeTraits::set_left(super_root, new_root);
         NodeTraits::set_right(super_root, super_root_right_backup);
      }
      return new_root;
   }

   //! <b>Requires</b>: "n" must be a node inserted in a tree.
   //!
   //! <b>Effects</b>: Returns a pointer to the header node of the tree.
   //!
   //! <b>Complexity</b>: Logarithmic.
   //! 
   //! <b>Throws</b>: Nothing.
   static node_ptr get_root(node_ptr node)
   {
      BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node)));
      node_ptr x = NodeTraits::get_parent(node);
      if(x){
         while(!is_header(x)){
            x = NodeTraits::get_parent(x);
         }
         return x;
      }
      else{
         return node;
      }
   }

   private:
   static void erase_impl(node_ptr header, node_ptr z, data_for_rebalance &info)
   {
      node_ptr y(z);
      node_ptr x;
      node_ptr x_parent(0);
      node_ptr z_left(NodeTraits::get_left(z));
      node_ptr z_right(NodeTraits::get_right(z));
      if(!z_left){
         x = z_right;    // x might be null.
      }
      else if(!z_right){ // z has exactly one non-null child. y == z.
         x = z_left;       // x is not null.
      }
      else{
         // find z's successor
         y = tree_algorithms::minimum (z_right);
         x = NodeTraits::get_right(y);     // x might be null.
      }

      if(y != z){
         // relink y in place of z.  y is z's successor
         NodeTraits::set_parent(NodeTraits::get_left(z), y);
         NodeTraits::set_left(y, NodeTraits::get_left(z));
         if(y != NodeTraits::get_right(z)){
            x_parent = NodeTraits::get_parent(y);
            if(x)
               NodeTraits::set_parent(x, x_parent);
            NodeTraits::set_left(x_parent, x);   // y must be a child of left_
            NodeTraits::set_right(y, NodeTraits::get_right(z));
            NodeTraits::set_parent(NodeTraits::get_right(z), y);
         }
         else
            x_parent = y;
         tree_algorithms::replace_own (z, y, header);
         NodeTraits::set_parent(y, NodeTraits::get_parent(z));
      }
      else {   // y == z --> z has only one child, or none
         x_parent = NodeTraits::get_parent(z);
         if(x)
            NodeTraits::set_parent(x, x_parent);
         tree_algorithms::replace_own (z, x, header);
         if(NodeTraits::get_left(header) == z){
            NodeTraits::set_left(header, NodeTraits::get_right(z) == 0 ?        // z->get_left() must be null also
               NodeTraits::get_parent(z) :  // makes leftmost == header if z == root
               tree_algorithms::minimum (x));
         }
         if(NodeTraits::get_right(header) == z){
            NodeTraits::set_right(header, NodeTraits::get_left(z) == 0 ?        // z->get_right() must be null also
                              NodeTraits::get_parent(z) :  // makes rightmost == header if z == root
                              tree_algorithms::maximum(x));
         }
      }

      info.x = x;
      info.x_parent = x_parent;
      info.y = y;
   }
};

}  //namespace detail {
}  //namespace intrusive 
}  //namespace boost 

#include <boost/intrusive/detail/config_end.hpp>

#endif //BOOST_INTRUSIVE_TREE_ALGORITHMS_HPP