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
26namespace boost {
27namespace intrusive {
28
29template<class NodeTraits>
30class 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>: 'n' 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.
45 static node_ptr next_node(node_ptr n) BOOST_NOEXCEPT
46 {
47 node_ptr const n_right(NodeTraits::get_right(n));
48 if(n_right){
49 return minimum(n: n_right);
50 }
51 else {
52 node_ptr p(NodeTraits::get_parent(n));
53 while(n == NodeTraits::get_right(p)){
54 n = p;
55 p = NodeTraits::get_parent(p);
56 }
57 return NodeTraits::get_right(n) != p ? p : n;
58 }
59 }
60
61 //! <b>Requires</b>: 'n' is a node from the tree except the leftmost node.
62 //!
63 //! <b>Effects</b>: Returns the previous node of the tree.
64 //!
65 //! <b>Complexity</b>: Average constant time.
66 //!
67 //! <b>Throws</b>: Nothing.
68 static node_ptr prev_node(node_ptr n) BOOST_NOEXCEPT
69 {
70 if(is_header(p: n)){
71 return NodeTraits::get_right(n);
72 }
73 else if(NodeTraits::get_left(n)){
74 return maximum(n: NodeTraits::get_left(n));
75 }
76 else {
77 node_ptr p(n);
78 node_ptr x = NodeTraits::get_parent(p);
79 while(p == NodeTraits::get_left(x)){
80 p = x;
81 x = NodeTraits::get_parent(x);
82 }
83 return x;
84 }
85 }
86
87 //! <b>Requires</b>: 'n' is a node of a tree but not the header.
88 //!
89 //! <b>Effects</b>: Returns the minimum node of the subtree starting at p.
90 //!
91 //! <b>Complexity</b>: Logarithmic to the size of the subtree.
92 //!
93 //! <b>Throws</b>: Nothing.
94 static node_ptr minimum(node_ptr n)
95 {
96 for(node_ptr p_left = NodeTraits::get_left(n)
97 ;p_left
98 ;p_left = NodeTraits::get_left(n)){
99 n = p_left;
100 }
101 return n;
102 }
103
104 //! <b>Requires</b>: 'n' is a node of a tree but not the header.
105 //!
106 //! <b>Effects</b>: Returns the maximum node of the subtree starting at p.
107 //!
108 //! <b>Complexity</b>: Logarithmic to the size of the subtree.
109 //!
110 //! <b>Throws</b>: Nothing.
111 static node_ptr maximum(node_ptr n)
112 {
113 for(node_ptr p_right = NodeTraits::get_right(n)
114 ;p_right
115 ;p_right = NodeTraits::get_right(n)){
116 n = p_right;
117 }
118 return n;
119 }
120
121 //! <b>Requires</b>: p is a node of a tree.
122 //!
123 //! <b>Effects</b>: Returns true if p is the header of the tree.
124 //!
125 //! <b>Complexity</b>: Constant.
126 //!
127 //! <b>Throws</b>: Nothing.
128 static bool is_header(const_node_ptr p) BOOST_NOEXCEPT
129 {
130 node_ptr p_left (NodeTraits::get_left(p));
131 node_ptr p_right(NodeTraits::get_right(p));
132 if(!NodeTraits::get_parent(p) || //Header condition when empty tree
133 (p_left && p_right && //Header always has leftmost and rightmost
134 (p_left == p_right || //Header condition when only node
135 (NodeTraits::get_parent(p_left) != p ||
136 NodeTraits::get_parent(p_right) != p ))
137 //When tree size > 1 headers can't be leftmost's
138 //and rightmost's parent
139 )){
140 return true;
141 }
142 return false;
143 }
144
145 //! <b>Requires</b>: 'n' is a node of the tree or a header node.
146 //!
147 //! <b>Effects</b>: Returns the header of the tree.
148 //!
149 //! <b>Complexity</b>: Logarithmic.
150 //!
151 //! <b>Throws</b>: Nothing.
152 static node_ptr get_header(const_node_ptr n)
153 {
154 node_ptr nn(detail::uncast(n));
155 node_ptr p(NodeTraits::get_parent(n));
156 //If p is null, then nn is the header of an empty tree
157 if(p){
158 //Non-empty tree, check if nn is neither root nor header
159 node_ptr pp(NodeTraits::get_parent(p));
160 //If granparent is not equal to nn, then nn is neither root nor header,
161 //the try the fast path
162 if(nn != pp){
163 do{
164 nn = p;
165 p = pp;
166 pp = NodeTraits::get_parent(pp);
167 }while(nn != pp);
168 nn = p;
169 }
170 //Check if nn is root or header when size() > 0
171 else if(!bstree_algorithms_base::is_header(p: nn)){
172 nn = p;
173 }
174 }
175 return nn;
176 }
177};
178
179} //namespace intrusive
180} //namespace boost
181
182#endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP
183

source code of boost/libs/intrusive/include/boost/intrusive/detail/bstree_algorithms_base.hpp