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