Chris@102: /////////////////////////////////////////////////////////////////////////////
Chris@102: //
Chris@102: // (C) Copyright Ion Gaztanaga  2014-2014
Chris@102: //
Chris@102: // Distributed under the Boost Software License, Version 1.0.
Chris@102: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@102: //          http://www.boost.org/LICENSE_1_0.txt)
Chris@102: //
Chris@102: // See http://www.boost.org/libs/intrusive for documentation.
Chris@102: //
Chris@102: /////////////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: #ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP
Chris@102: #define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP
Chris@102: 
Chris@102: #ifndef BOOST_CONFIG_HPP
Chris@102: #  include <boost/config.hpp>
Chris@102: #endif
Chris@102: 
Chris@102: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@102: #  pragma once
Chris@102: #endif
Chris@102: 
Chris@102: #include <boost/intrusive/detail/uncast.hpp>
Chris@102: 
Chris@102: namespace boost {
Chris@102: namespace intrusive {
Chris@102: 
Chris@102: template<class NodeTraits>
Chris@102: class bstree_algorithms_base
Chris@102: {
Chris@102:    public:
Chris@102:    typedef typename NodeTraits::node            node;
Chris@102:    typedef NodeTraits                           node_traits;
Chris@102:    typedef typename NodeTraits::node_ptr        node_ptr;
Chris@102:    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
Chris@102: 
Chris@102:    //! <b>Requires</b>: 'node' is a node from the tree except the header.
Chris@102:    //!
Chris@102:    //! <b>Effects</b>: Returns the next node of the tree.
Chris@102:    //!
Chris@102:    //! <b>Complexity</b>: Average constant time.
Chris@102:    //!
Chris@102:    //! <b>Throws</b>: Nothing.
Chris@102:    static node_ptr next_node(const node_ptr & node)
Chris@102:    {
Chris@102:       node_ptr const n_right(NodeTraits::get_right(node));
Chris@102:       if(n_right){
Chris@102:          return minimum(n_right);
Chris@102:       }
Chris@102:       else {
Chris@102:          node_ptr n(node);
Chris@102:          node_ptr p(NodeTraits::get_parent(n));
Chris@102:          while(n == NodeTraits::get_right(p)){
Chris@102:             n = p;
Chris@102:             p = NodeTraits::get_parent(p);
Chris@102:          }
Chris@102:          return NodeTraits::get_right(n) != p ? p : n;
Chris@102:       }
Chris@102:    }
Chris@102: 
Chris@102:    //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node.
Chris@102:    //!
Chris@102:    //! <b>Effects</b>: Returns the previous node of the tree.
Chris@102:    //!
Chris@102:    //! <b>Complexity</b>: Average constant time.
Chris@102:    //!
Chris@102:    //! <b>Throws</b>: Nothing.
Chris@102:    static node_ptr prev_node(const node_ptr & node)
Chris@102:    {
Chris@102:       if(is_header(node)){
Chris@102:          return NodeTraits::get_right(node);
Chris@102:          //return maximum(NodeTraits::get_parent(node));
Chris@102:       }
Chris@102:       else if(NodeTraits::get_left(node)){
Chris@102:          return maximum(NodeTraits::get_left(node));
Chris@102:       }
Chris@102:       else {
Chris@102:          node_ptr p(node);
Chris@102:          node_ptr x = NodeTraits::get_parent(p);
Chris@102:          while(p == NodeTraits::get_left(x)){
Chris@102:             p = x;
Chris@102:             x = NodeTraits::get_parent(x);
Chris@102:          }
Chris@102:          return x;
Chris@102:       }
Chris@102:    }
Chris@102: 
Chris@102:    //! <b>Requires</b>: 'node' is a node of a tree but not the header.
Chris@102:    //!
Chris@102:    //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
Chris@102:    //!
Chris@102:    //! <b>Complexity</b>: Logarithmic to the size of the subtree.
Chris@102:    //!
Chris@102:    //! <b>Throws</b>: Nothing.
Chris@102:    static node_ptr minimum(node_ptr node)
Chris@102:    {
Chris@102:       for(node_ptr p_left = NodeTraits::get_left(node)
Chris@102:          ;p_left
Chris@102:          ;p_left = NodeTraits::get_left(node)){
Chris@102:          node = p_left;
Chris@102:       }
Chris@102:       return node;
Chris@102:    }
Chris@102: 
Chris@102:    //! <b>Requires</b>: 'node' is a node of a tree but not the header.
Chris@102:    //!
Chris@102:    //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
Chris@102:    //!
Chris@102:    //! <b>Complexity</b>: Logarithmic to the size of the subtree.
Chris@102:    //!
Chris@102:    //! <b>Throws</b>: Nothing.
Chris@102:    static node_ptr maximum(node_ptr node)
Chris@102:    {
Chris@102:       for(node_ptr p_right = NodeTraits::get_right(node)
Chris@102:          ;p_right
Chris@102:          ;p_right = NodeTraits::get_right(node)){
Chris@102:          node = p_right;
Chris@102:       }
Chris@102:       return node;
Chris@102:    }
Chris@102: 
Chris@102:    //! <b>Requires</b>: p is a node of a tree.
Chris@102:    //!
Chris@102:    //! <b>Effects</b>: Returns true if p is the header of the tree.
Chris@102:    //!
Chris@102:    //! <b>Complexity</b>: Constant.
Chris@102:    //!
Chris@102:    //! <b>Throws</b>: Nothing.
Chris@102:    static bool is_header(const const_node_ptr & p)
Chris@102:    {
Chris@102:       node_ptr p_left (NodeTraits::get_left(p));
Chris@102:       node_ptr p_right(NodeTraits::get_right(p));
Chris@102:       if(!NodeTraits::get_parent(p) || //Header condition when empty tree
Chris@102:          (p_left && p_right &&         //Header always has leftmost and rightmost
Chris@102:             (p_left == p_right ||      //Header condition when only node
Chris@102:                (NodeTraits::get_parent(p_left)  != p ||
Chris@102:                 NodeTraits::get_parent(p_right) != p ))
Chris@102:                //When tree size > 1 headers can't be leftmost's
Chris@102:                //and rightmost's parent
Chris@102:           )){
Chris@102:          return true;
Chris@102:       }
Chris@102:       return false;
Chris@102:    }
Chris@102: 
Chris@102:    //! <b>Requires</b>: 'node' is a node of the tree or a header node.
Chris@102:    //!
Chris@102:    //! <b>Effects</b>: Returns the header of the tree.
Chris@102:    //!
Chris@102:    //! <b>Complexity</b>: Logarithmic.
Chris@102:    //!
Chris@102:    //! <b>Throws</b>: Nothing.
Chris@102:    static node_ptr get_header(const const_node_ptr & node)
Chris@102:    {
Chris@102:       node_ptr n(detail::uncast(node));
Chris@102:       node_ptr p(NodeTraits::get_parent(node));
Chris@102:       //If p is null, then n is the header of an empty tree
Chris@102:       if(p){
Chris@102:          //Non-empty tree, check if n is neither root nor header
Chris@102:          node_ptr pp(NodeTraits::get_parent(p));
Chris@102:          //If granparent is not equal to n, then n is neither root nor header,
Chris@102:          //the try the fast path
Chris@102:          if(n != pp){
Chris@102:             do{
Chris@102:                n = p;
Chris@102:                p = pp;
Chris@102:                pp = NodeTraits::get_parent(pp);
Chris@102:             }while(n != pp);
Chris@102:             n = p;
Chris@102:          }
Chris@102:          //Check if n is root or header when size() > 0
Chris@102:          else if(!bstree_algorithms_base::is_header(n)){
Chris@102:             n = p;
Chris@102:          }
Chris@102:       }
Chris@102:       return n;
Chris@102:    }
Chris@102: };
Chris@102: 
Chris@102: }  //namespace intrusive
Chris@102: }  //namespace boost
Chris@102: 
Chris@102: #endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP