view release on metacpan or  search on metacpan

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

            NodeTraits::set_right(header1, node2);
         }
         else if(node2 == NodeTraits::get_right(header2)){
            NodeTraits::set_right(header2, node1);
         }

         if(node1 == NodeTraits::get_parent(header1)){
            NodeTraits::set_parent(header1, node2);
         }
         else if(node2 == NodeTraits::get_parent(header2)){
            NodeTraits::set_parent(header2, node1);
         }

         //Adjust data in nodes to be swapped
         //so that final link swap works as expected
         if(node1 == NodeTraits::get_parent(node2)){
            NodeTraits::set_parent(node2, node2);

            if(node2 == NodeTraits::get_right(node1)){
               NodeTraits::set_right(node1, node1);
            }
            else{
               NodeTraits::set_left(node1, node1);
            }
         }
         else if(node2 == NodeTraits::get_parent(node1)){
            NodeTraits::set_parent(node1, node1);

            if(node1 == NodeTraits::get_right(node2)){
               NodeTraits::set_right(node2, node2);
            }
            else{
               NodeTraits::set_left(node2, node2);
            }
         }
      }

      //Now swap all the links
      node_ptr temp;
      //swap left link
      temp = NodeTraits::get_left(node1);
      NodeTraits::set_left(node1, NodeTraits::get_left(node2));
      NodeTraits::set_left(node2, temp);
      //swap right link
      temp = NodeTraits::get_right(node1);
      NodeTraits::set_right(node1, NodeTraits::get_right(node2));
      NodeTraits::set_right(node2, temp);
      //swap parent link
      temp = NodeTraits::get_parent(node1);
      NodeTraits::set_parent(node1, NodeTraits::get_parent(node2));
      NodeTraits::set_parent(node2, temp);

      //Now adjust adjacent nodes for newly inserted node 1
      if((temp = NodeTraits::get_left(node1))){
         NodeTraits::set_parent(temp, node1);
      }
      if((temp = NodeTraits::get_right(node1))){
         NodeTraits::set_parent(temp, node1);
      }
      if((temp = NodeTraits::get_parent(node1)) &&
         //The header has been already updated so avoid it
         temp != header2){
         if(NodeTraits::get_left(temp) == node2){
            NodeTraits::set_left(temp, node1);
         }
         if(NodeTraits::get_right(temp) == node2){
            NodeTraits::set_right(temp, node1);
         }
      }
      //Now adjust adjacent nodes for newly inserted node 2
      if((temp = NodeTraits::get_left(node2))){
         NodeTraits::set_parent(temp, node2);
      }
      if((temp = NodeTraits::get_right(node2))){
         NodeTraits::set_parent(temp, node2);
      }
      if((temp = NodeTraits::get_parent(node2)) &&
         //The header has been already updated so avoid it
         temp != header1){
         if(NodeTraits::get_left(temp) == node1){
            NodeTraits::set_left(temp, node2);
         }
         if(NodeTraits::get_right(temp) == node1){
            NodeTraits::set_right(temp, node2);
         }
      }
   }

   //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
   //!   and new_node must not be inserted in a tree.
   //!
   //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
   //!   tree with new_node. The tree does not need to be rebalanced
   //!
   //! <b>Complexity</b>: Logarithmic.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Note</b>: This function will break container ordering invariants if
   //!   new_node is not equivalent to node_to_be_replaced according to the
   //!   ordering rules. This function is faster than erasing and inserting
   //!   the node, since no rebalancing and comparison is needed. Experimental function
   BOOST_INTRUSIVE_FORCEINLINE static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
   {
      if(node_to_be_replaced == new_node)
         return;
      replace_node(node_to_be_replaced, base_type::get_header(node_to_be_replaced), new_node);
   }

   //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
   //!   with header "header" and new_node must not be inserted in a tree.
   //!
   //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the
   //!   tree with new_node. The tree does not need to be rebalanced
   //!
   //! <b>Complexity</b>: Constant.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Note</b>: This function will break container ordering invariants if
   //!   new_node is not equivalent to node_to_be_replaced according to the
   //!   ordering rules. This function is faster than erasing and inserting
   //!   the node, since no rebalancing or comparison is needed. Experimental function
   static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
   {
      if(node_to_be_replaced == new_node)
         return;

      //Update header if necessary
      if(node_to_be_replaced == NodeTraits::get_left(header)){
         NodeTraits::set_left(header, new_node);
      }

      if(node_to_be_replaced == NodeTraits::get_right(header)){
         NodeTraits::set_right(header, new_node);
      }

      if(node_to_be_replaced == NodeTraits::get_parent(header)){
         NodeTraits::set_parent(header, new_node);
      }

      //Now set data from the original node
      node_ptr temp;
      NodeTraits::set_left(new_node, NodeTraits::get_left(node_to_be_replaced));
      NodeTraits::set_right(new_node, NodeTraits::get_right(node_to_be_replaced));
      NodeTraits::set_parent(new_node, NodeTraits::get_parent(node_to_be_replaced));

      //Now adjust adjacent nodes for newly inserted node
      if((temp = NodeTraits::get_left(new_node))){
         NodeTraits::set_parent(temp, new_node);
      }
      if((temp = NodeTraits::get_right(new_node))){
         NodeTraits::set_parent(temp, new_node);
      }
      if((temp = NodeTraits::get_parent(new_node)) &&
         //The header has been already updated so avoid it
         temp != header){
         if(NodeTraits::get_left(temp) == node_to_be_replaced){
            NodeTraits::set_left(temp, new_node);
         }
         if(NodeTraits::get_right(temp) == node_to_be_replaced){
            NodeTraits::set_right(temp, new_node);
         }
      }
   }

   #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
   //! <b>Requires</b>: 'node' is a node from the tree except the header.
   //!
   //! <b>Effects</b>: Returns the next node of the tree.
   //!
   //! <b>Complexity</b>: Average constant time.
   //!
   //! <b>Throws</b>: Nothing.
   static node_ptr next_node(const node_ptr & node);

   //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node.
   //!
   //! <b>Effects</b>: Returns the previous node of the tree.
   //!
   //! <b>Complexity</b>: Average constant time.
   //!
   //! <b>Throws</b>: Nothing.
   static node_ptr prev_node(const node_ptr & node);

   //! <b>Requires</b>: 'node' is a node of a tree but not the header.
   //!
   //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
   //!
   //! <b>Complexity</b>: Logarithmic to the size of the subtree.
   //!
   //! <b>Throws</b>: Nothing.
   static node_ptr minimum(node_ptr node);

   //! <b>Requires</b>: 'node' is a node of a tree but not the header.
   //!
   //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
   //!
   //! <b>Complexity</b>: Logarithmic to the size of the subtree.
   //!
   //! <b>Throws</b>: Nothing.
   static node_ptr maximum(node_ptr node);
   #endif

   //! <b>Requires</b>: 'node' must not be part of any tree.
   //!
   //! <b>Effects</b>: After the function unique(node) == true.
   //!
   //! <b>Complexity</b>: Constant.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
   BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & node)
   {
      NodeTraits::set_parent(node, node_ptr());

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

   //Fix header and own's parent data when replacing x with own, providing own's old data with parent
   static void set_child(const node_ptr & header, const node_ptr & new_child, const node_ptr & new_parent, const bool link_left)
   {
      if(new_parent == header)
         NodeTraits::set_parent(header, new_child);
      else if(link_left)
         NodeTraits::set_left(new_parent, new_child);
      else
         NodeTraits::set_right(new_parent, new_child);
   }

   // rotate p to left (no header and p's parent fixup)
   static void rotate_left_no_parent_fix(const node_ptr & p, const node_ptr &p_right)
   {
      node_ptr p_right_left(NodeTraits::get_left(p_right));
      NodeTraits::set_right(p, p_right_left);
      if(p_right_left){
         NodeTraits::set_parent(p_right_left, p);
      }
      NodeTraits::set_left(p_right, p);
      NodeTraits::set_parent(p, p_right);
   }

   // rotate p to left (with header and p's parent fixup)
   static void rotate_left(const node_ptr & p, const node_ptr & p_right, const node_ptr & p_parent, const node_ptr & header)
   {
      const bool p_was_left(NodeTraits::get_left(p_parent) == p);
      rotate_left_no_parent_fix(p, p_right);
      NodeTraits::set_parent(p_right, p_parent);
      set_child(header, p_right, p_parent, p_was_left);
   }

   // rotate p to right (no header and p's parent fixup)
   static void rotate_right_no_parent_fix(const node_ptr & p, const node_ptr &p_left)
   {
      node_ptr p_left_right(NodeTraits::get_right(p_left));
      NodeTraits::set_left(p, p_left_right);
      if(p_left_right){
         NodeTraits::set_parent(p_left_right, p);
      }
      NodeTraits::set_right(p_left, p);
      NodeTraits::set_parent(p, p_left);
   }

   // rotate p to right (with header and p's parent fixup)
   static void rotate_right(const node_ptr & p, const node_ptr & p_left, const node_ptr & p_parent, const node_ptr & header)
   {
      const bool p_was_left(NodeTraits::get_left(p_parent) == p);
      rotate_right_no_parent_fix(p, p_left);
      NodeTraits::set_parent(p_left, p_parent);
      set_child(header, p_left, p_parent, p_was_left);
   }

   private:

   static void subtree_to_vine(node_ptr vine_tail, std::size_t &size)
   {
      //Inspired by LibAVL:
      //It uses a clever optimization for trees with parent pointers.
      //No parent pointer is updated when transforming a tree to a vine as
      //most of them will be overriten during compression rotations.
      //A final pass must be made after the rebalancing to updated those
      //pointers not updated by tree_to_vine + compression calls
      std::size_t len = 0;
      node_ptr remainder = NodeTraits::get_right(vine_tail);
      while(remainder){
         node_ptr tempptr = NodeTraits::get_left(remainder);
         if(!tempptr){   //move vine-tail down one
            vine_tail = remainder;
            remainder = NodeTraits::get_right(remainder);
            ++len;
         }
         else{ //rotate
            NodeTraits::set_left(remainder, NodeTraits::get_right(tempptr));
            NodeTraits::set_right(tempptr, remainder);
            remainder = tempptr;
            NodeTraits::set_right(vine_tail, tempptr);
         }
      }
      size = len;
   }

   static void compress_subtree(node_ptr scanner, std::size_t count)
   {
      while(count--){   //compress "count" spine nodes in the tree with pseudo-root scanner
         node_ptr child = NodeTraits::get_right(scanner);
         node_ptr child_right = NodeTraits::get_right(child);
         NodeTraits::set_right(scanner, child_right);
         //Avoid setting the parent of child_right
         scanner = child_right;
         node_ptr scanner_left = NodeTraits::get_left(scanner);
         NodeTraits::set_right(child, scanner_left);
         if(scanner_left)
            NodeTraits::set_parent(scanner_left, child);
         NodeTraits::set_left(scanner, child);
         NodeTraits::set_parent(child, scanner);
      }
   }

   static void vine_to_subtree(const node_ptr & super_root, std::size_t count)
   {
      const std::size_t one_szt = 1u;
      std::size_t leaf_nodes = count + one_szt - std::size_t(one_szt << detail::floor_log2(count + one_szt));
      compress_subtree(super_root, leaf_nodes);  //create deepest leaves
      std::size_t vine_nodes = count - leaf_nodes;
      while(vine_nodes > 1){
         vine_nodes /= 2;
         compress_subtree(super_root, vine_nodes);
      }

      //Update parents of nodes still in the in the original vine line
      //as those have not been updated by subtree_to_vine or compress_subtree
      for ( node_ptr q = super_root, p = NodeTraits::get_right(super_root)
          ; p
          ; q = p, p = NodeTraits::get_right(p)){
         NodeTraits::set_parent(p, q);
      }
   }

   //! <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(const node_ptr & node)
   {
      BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node)));
      node_ptr x = NodeTraits::get_parent(node);
      if(x){
         while(!base_type::is_header(x)){
            x = NodeTraits::get_parent(x);
         }
         return x;
      }
      else{
         return node;
      }
   }

   template <class Cloner, class Disposer>
   static node_ptr clone_subtree
      (const const_node_ptr &source_parent, const node_ptr &target_parent
      , Cloner cloner, Disposer disposer
      , node_ptr &leftmost_out, node_ptr &rightmost_out
      )
   {
      node_ptr target_sub_root = target_parent;
      node_ptr source_root = NodeTraits::get_parent(source_parent);
      if(!source_root){
         leftmost_out = rightmost_out = source_root;
      }
      else{
         //We'll calculate leftmost and rightmost nodes while iterating
         node_ptr current = source_root;
         node_ptr insertion_point = target_sub_root = cloner(current);

         //We'll calculate leftmost and rightmost nodes while iterating
         node_ptr leftmost  = target_sub_root;
         node_ptr rightmost = target_sub_root;

         //First set the subroot
         NodeTraits::set_left(target_sub_root, node_ptr());
         NodeTraits::set_right(target_sub_root, node_ptr());
         NodeTraits::set_parent(target_sub_root, target_parent);

         dispose_subtree_disposer<Disposer> rollback(disposer, target_sub_root);
         while(true) {
            //First clone left nodes
            if( NodeTraits::get_left(current) &&
               !NodeTraits::get_left(insertion_point)) {