]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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. | |
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. | |
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. | |
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. | |
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. | |
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. | |
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 |