view release on metacpan or  search on metacpan

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

   //! <b>Complexity</b>: Logarithmic.
   //!
   //! <b>Throws</b>: If the comparison throws.
   template<class NodePtrCompare>
   BOOST_INTRUSIVE_FORCEINLINE static void transfer_equal
      (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
   {
      data_for_rebalance ignored;
      transfer_equal(header1, comp, header2, z, ignored);
   }

   //! <b>Requires</b>: node is a tree node but not the header.
   //!
   //! <b>Effects</b>: Unlinks the node and rebalances the tree.
   //!
   //! <b>Complexity</b>: Average complexity is constant time.
   //!
   //! <b>Throws</b>: Nothing.
   static void unlink(const node_ptr & node)
   {
      node_ptr x = NodeTraits::get_parent(node);
      if(x){
         while(!base_type::is_header(x))
            x = NodeTraits::get_parent(x);
         erase(x, node);
      }
   }

   //! <b>Requires</b>: header must be the header of a tree.
   //!
   //! <b>Effects</b>: Rebalances the tree.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Linear.
   static void rebalance(const node_ptr & header)
   {
      node_ptr root = NodeTraits::get_parent(header);
      if(root){
         rebalance_subtree(root);
      }
   }

   //! <b>Requires</b>: old_root is a node of a tree. It shall not be null.
   //!
   //! <b>Effects</b>: Rebalances the subtree rooted at old_root.
   //!
   //! <b>Returns</b>: The new root of the subtree.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Linear.
   static node_ptr rebalance_subtree(const node_ptr & old_root)
   {
      //Taken from:
      //"Tree rebalancing in optimal time and space"
      //Quentin F. Stout and Bette L. Warren

      //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 root info
      node_ptr super_root_right_backup = NodeTraits::get_right(super_root);
      bool super_root_is_header = NodeTraits::get_parent(super_root) == old_root;
      bool old_root_is_right  = is_right_child(old_root);
      NodeTraits::set_right(super_root, old_root);

      std::size_t size;
      subtree_to_vine(super_root, size);
      vine_to_subtree(super_root, size);
      node_ptr new_root = NodeTraits::get_right(super_root);

      //Recover root
      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);
      }
      return new_root;
   }

   //! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user.
   //!
   //! <b>Requires</b>: header must be the header of a tree.
   //!
   //! <b>Complexity</b>: Linear time.
   //!
   //! <b>Note</b>: The method might not have effect when asserts are turned off (e.g., with NDEBUG).
   //!   Experimental function, interface might change in future versions.
   template<class Checker>
   static void check(const const_node_ptr& header, Checker checker, typename Checker::return_type& checker_return)
   {
      const_node_ptr root_node_ptr = NodeTraits::get_parent(header);
      if (!root_node_ptr){
         // check left&right header pointers
         BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header);
         BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header);
      }
      else{
         // check parent pointer of root node
         BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header);
         // check subtree from root
         check_subtree(root_node_ptr, checker, checker_return);
         // check left&right header pointers
         const_node_ptr p = root_node_ptr;
         while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); }
         BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p);
         p = root_node_ptr;
         while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); }
         BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p);
      }
   }

   protected:

   template<class NodePtrCompare>
   static bool transfer_unique
      (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z, data_for_rebalance &info)
   {
      insert_commit_data commit_data;
      bool const transferable = insert_unique_check(header1, z, comp, commit_data).second;
      if(transferable){
         erase(header2, z, info);
         insert_commit(header1, z, commit_data);
      }
      return transferable;
   }

   template<class NodePtrCompare>
   static void transfer_equal
      (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z, data_for_rebalance &info)
   {
      insert_commit_data commit_data;
      insert_equal_upper_bound_check(header1, z, comp, commit_data);
      erase(header2, z, info);
      insert_commit(header1, z, commit_data);