1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2014-2014 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 13 #ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP 14 #define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP 15 16 #ifndef BOOST_CONFIG_HPP 17 # include <boost/config.hpp> 18 #endif 19 20 #if defined(BOOST_HAS_PRAGMA_ONCE) 21 # pragma once 22 #endif 23 24 #include <boost/intrusive/detail/uncast.hpp> 25 26 namespace boost { 27 namespace intrusive { 28 29 template<class NodeTraits> 30 class bstree_algorithms_base 31 { 32 public: 33 typedef typename NodeTraits::node node; 34 typedef NodeTraits node_traits; 35 typedef typename NodeTraits::node_ptr node_ptr; 36 typedef typename NodeTraits::const_node_ptr const_node_ptr; 37 38 //! <b>Requires</b>: 'node' is a node from the tree except the header. 39 //! 40 //! <b>Effects</b>: Returns the next node of the tree. 41 //! 42 //! <b>Complexity</b>: Average constant time. 43 //! 44 //! <b>Throws</b>: Nothing. next_node(const node_ptr & node)45 static node_ptr next_node(const node_ptr & node) 46 { 47 node_ptr const n_right(NodeTraits::get_right(node)); 48 if(n_right){ 49 return minimum(n_right); 50 } 51 else { 52 node_ptr n(node); 53 node_ptr p(NodeTraits::get_parent(n)); 54 while(n == NodeTraits::get_right(p)){ 55 n = p; 56 p = NodeTraits::get_parent(p); 57 } 58 return NodeTraits::get_right(n) != p ? p : n; 59 } 60 } 61 62 //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node. 63 //! 64 //! <b>Effects</b>: Returns the previous node of the tree. 65 //! 66 //! <b>Complexity</b>: Average constant time. 67 //! 68 //! <b>Throws</b>: Nothing. prev_node(const node_ptr & node)69 static node_ptr prev_node(const node_ptr & node) 70 { 71 if(is_header(node)){ 72 //return NodeTraits::get_right(node); 73 return maximum(NodeTraits::get_parent(node)); 74 } 75 else if(NodeTraits::get_left(node)){ 76 return maximum(NodeTraits::get_left(node)); 77 } 78 else { 79 node_ptr p(node); 80 node_ptr x = NodeTraits::get_parent(p); 81 while(p == NodeTraits::get_left(x)){ 82 p = x; 83 x = NodeTraits::get_parent(x); 84 } 85 return x; 86 } 87 } 88 89 //! <b>Requires</b>: 'node' is a node of a tree but not the header. 90 //! 91 //! <b>Effects</b>: Returns the minimum node of the subtree starting at p. 92 //! 93 //! <b>Complexity</b>: Logarithmic to the size of the subtree. 94 //! 95 //! <b>Throws</b>: Nothing. minimum(node_ptr node)96 static node_ptr minimum(node_ptr node) 97 { 98 for(node_ptr p_left = NodeTraits::get_left(node) 99 ;p_left 100 ;p_left = NodeTraits::get_left(node)){ 101 node = p_left; 102 } 103 return node; 104 } 105 106 //! <b>Requires</b>: 'node' is a node of a tree but not the header. 107 //! 108 //! <b>Effects</b>: Returns the maximum node of the subtree starting at p. 109 //! 110 //! <b>Complexity</b>: Logarithmic to the size of the subtree. 111 //! 112 //! <b>Throws</b>: Nothing. maximum(node_ptr node)113 static node_ptr maximum(node_ptr node) 114 { 115 for(node_ptr p_right = NodeTraits::get_right(node) 116 ;p_right 117 ;p_right = NodeTraits::get_right(node)){ 118 node = p_right; 119 } 120 return node; 121 } 122 123 //! <b>Requires</b>: p is a node of a tree. 124 //! 125 //! <b>Effects</b>: Returns true if p is the header of the tree. 126 //! 127 //! <b>Complexity</b>: Constant. 128 //! 129 //! <b>Throws</b>: Nothing. is_header(const const_node_ptr & p)130 static bool is_header(const const_node_ptr & p) 131 { 132 node_ptr p_left (NodeTraits::get_left(p)); 133 node_ptr p_right(NodeTraits::get_right(p)); 134 if(!NodeTraits::get_parent(p) || //Header condition when empty tree 135 (p_left && p_right && //Header always has leftmost and rightmost 136 (p_left == p_right || //Header condition when only node 137 (NodeTraits::get_parent(p_left) != p || 138 NodeTraits::get_parent(p_right) != p )) 139 //When tree size > 1 headers can't be leftmost's 140 //and rightmost's parent 141 )){ 142 return true; 143 } 144 return false; 145 } 146 147 //! <b>Requires</b>: 'node' is a node of the tree or a header node. 148 //! 149 //! <b>Effects</b>: Returns the header of the tree. 150 //! 151 //! <b>Complexity</b>: Logarithmic. 152 //! 153 //! <b>Throws</b>: Nothing. get_header(const const_node_ptr & node)154 static node_ptr get_header(const const_node_ptr & node) 155 { 156 node_ptr n(detail::uncast(node)); 157 node_ptr p(NodeTraits::get_parent(node)); 158 //If p is null, then n is the header of an empty tree 159 if(p){ 160 //Non-empty tree, check if n is neither root nor header 161 node_ptr pp(NodeTraits::get_parent(p)); 162 //If granparent is not equal to n, then n is neither root nor header, 163 //the try the fast path 164 if(n != pp){ 165 do{ 166 n = p; 167 p = pp; 168 pp = NodeTraits::get_parent(pp); 169 }while(n != pp); 170 n = p; 171 } 172 //Check if n is root or header when size() > 0 173 else if(!bstree_algorithms_base::is_header(n)){ 174 n = p; 175 } 176 } 177 return n; 178 } 179 }; 180 181 } //namespace intrusive 182 } //namespace boost 183 184 #endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP 185