]>
Commit | Line | Data |
---|---|---|
1 | ///////////////////////////////////////////////////////////////////////////// | |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2007-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 | // Scapegoat tree algorithms are taken from the paper titled: | |
14 | // "Scapegoat Trees" by Igal Galperin Ronald L. Rivest. | |
15 | // | |
16 | ///////////////////////////////////////////////////////////////////////////// | |
17 | #ifndef BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP | |
18 | #define BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP | |
19 | ||
20 | #include <boost/intrusive/detail/config_begin.hpp> | |
21 | #include <boost/intrusive/intrusive_fwd.hpp> | |
22 | ||
23 | #include <cstddef> | |
24 | #include <boost/intrusive/detail/algo_type.hpp> | |
25 | #include <boost/intrusive/bstree_algorithms.hpp> | |
26 | ||
27 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
28 | # pragma once | |
29 | #endif | |
30 | ||
31 | namespace boost { | |
32 | namespace intrusive { | |
33 | ||
34 | //! sgtree_algorithms is configured with a NodeTraits class, which encapsulates the | |
35 | //! information about the node to be manipulated. NodeTraits must support the | |
36 | //! following interface: | |
37 | //! | |
38 | //! <b>Typedefs</b>: | |
39 | //! | |
40 | //! <tt>node</tt>: The type of the node that forms the binary search tree | |
41 | //! | |
42 | //! <tt>node_ptr</tt>: A pointer to a node | |
43 | //! | |
44 | //! <tt>const_node_ptr</tt>: A pointer to a const node | |
45 | //! | |
46 | //! <b>Static functions</b>: | |
47 | //! | |
48 | //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> | |
49 | //! | |
50 | //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> | |
51 | //! | |
52 | //! <tt>static node_ptr get_left(const_node_ptr n);</tt> | |
53 | //! | |
54 | //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> | |
55 | //! | |
56 | //! <tt>static node_ptr get_right(const_node_ptr n);</tt> | |
57 | //! | |
58 | //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> | |
59 | template<class NodeTraits> | |
60 | class sgtree_algorithms | |
61 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
62 | : public bstree_algorithms<NodeTraits> | |
63 | #endif | |
64 | { | |
65 | public: | |
66 | typedef typename NodeTraits::node node; | |
67 | typedef NodeTraits node_traits; | |
68 | typedef typename NodeTraits::node_ptr node_ptr; | |
69 | typedef typename NodeTraits::const_node_ptr const_node_ptr; | |
70 | ||
71 | /// @cond | |
72 | private: | |
73 | ||
74 | typedef bstree_algorithms<NodeTraits> bstree_algo; | |
75 | ||
76 | /// @endcond | |
77 | ||
78 | public: | |
79 | //! This type is the information that will be | |
80 | //! filled by insert_unique_check | |
81 | struct insert_commit_data | |
82 | : bstree_algo::insert_commit_data | |
83 | { | |
84 | std::size_t depth; | |
85 | }; | |
86 | ||
87 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
88 | //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) | |
89 | static node_ptr get_header(const const_node_ptr & n); | |
90 | ||
91 | //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node | |
92 | static node_ptr begin_node(const const_node_ptr & header); | |
93 | ||
94 | //! @copydoc ::boost::intrusive::bstree_algorithms::end_node | |
95 | static node_ptr end_node(const const_node_ptr & header); | |
96 | ||
97 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree | |
98 | static void swap_tree(const node_ptr & header1, const node_ptr & header2); | |
99 | ||
100 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) | |
101 | static void swap_nodes(const node_ptr & node1, const node_ptr & node2); | |
102 | ||
103 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&) | |
104 | static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2); | |
105 | ||
106 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) | |
107 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node); | |
108 | ||
109 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) | |
110 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node); | |
111 | ||
112 | //Unlink is not possible since tree metadata is needed to update the tree | |
113 | //!static void unlink(const node_ptr & node); | |
114 | ||
115 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance | |
116 | static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); | |
117 | ||
118 | //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) | |
119 | static bool unique(const const_node_ptr & node); | |
120 | ||
121 | //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) | |
122 | static std::size_t size(const const_node_ptr & header); | |
123 | ||
124 | //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) | |
125 | static node_ptr next_node(const node_ptr & node); | |
126 | ||
127 | //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) | |
128 | static node_ptr prev_node(const node_ptr & node); | |
129 | ||
130 | //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) | |
131 | static void init(const node_ptr & node); | |
132 | ||
133 | //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&) | |
134 | static void init_header(const node_ptr & header); | |
135 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
136 | ||
137 | //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) | |
138 | template<class AlphaByMaxSize> | |
139 | static node_ptr erase(const node_ptr & header, const node_ptr & z, std::size_t tree_size, std::size_t &max_tree_size, AlphaByMaxSize alpha_by_maxsize) | |
140 | { | |
141 | bstree_algo::erase(header, z); | |
142 | --tree_size; | |
143 | if (tree_size > 0 && | |
144 | tree_size < alpha_by_maxsize(max_tree_size)){ | |
145 | bstree_algo::rebalance(header); | |
146 | max_tree_size = tree_size; | |
147 | } | |
148 | return z; | |
149 | } | |
150 | ||
151 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
152 | //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) | |
153 | template <class Cloner, class Disposer> | |
154 | static void clone | |
155 | (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer); | |
156 | ||
157 | //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) | |
158 | template<class Disposer> | |
159 | static void clear_and_dispose(const node_ptr & header, Disposer disposer); | |
160 | ||
161 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
162 | template<class KeyType, class KeyNodePtrCompare> | |
163 | static node_ptr lower_bound | |
164 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
165 | ||
166 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
167 | template<class KeyType, class KeyNodePtrCompare> | |
168 | static node_ptr upper_bound | |
169 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
170 | ||
171 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) | |
172 | template<class KeyType, class KeyNodePtrCompare> | |
173 | static node_ptr find | |
174 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
175 | ||
176 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
177 | template<class KeyType, class KeyNodePtrCompare> | |
178 | static std::pair<node_ptr, node_ptr> equal_range | |
179 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
180 | ||
181 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) | |
182 | template<class KeyType, class KeyNodePtrCompare> | |
183 | static std::pair<node_ptr, node_ptr> bounded_range | |
184 | (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp | |
185 | , bool left_closed, bool right_closed); | |
186 | ||
187 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
188 | template<class KeyType, class KeyNodePtrCompare> | |
189 | static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
190 | ||
191 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
192 | ||
193 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) | |
194 | template<class NodePtrCompare, class H_Alpha> | |
195 | static node_ptr insert_equal_upper_bound | |
196 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp | |
197 | ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
198 | { | |
199 | std::size_t depth; | |
200 | bstree_algo::insert_equal_upper_bound(h, new_node, comp, &depth); | |
201 | rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); | |
202 | return new_node; | |
203 | } | |
204 | ||
205 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) | |
206 | template<class NodePtrCompare, class H_Alpha> | |
207 | static node_ptr insert_equal_lower_bound | |
208 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp | |
209 | ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
210 | { | |
211 | std::size_t depth; | |
212 | bstree_algo::insert_equal_lower_bound(h, new_node, comp, &depth); | |
213 | rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); | |
214 | return new_node; | |
215 | } | |
216 | ||
217 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) | |
218 | template<class NodePtrCompare, class H_Alpha> | |
219 | static node_ptr insert_equal | |
220 | (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp | |
221 | ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
222 | { | |
223 | std::size_t depth; | |
224 | bstree_algo::insert_equal(header, hint, new_node, comp, &depth); | |
225 | rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); | |
226 | return new_node; | |
227 | } | |
228 | ||
229 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) | |
230 | template<class H_Alpha> | |
231 | static node_ptr insert_before | |
232 | (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node | |
233 | ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
234 | { | |
235 | std::size_t depth; | |
236 | bstree_algo::insert_before(header, pos, new_node, &depth); | |
237 | rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); | |
238 | return new_node; | |
239 | } | |
240 | ||
241 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) | |
242 | template<class H_Alpha> | |
243 | static void push_back(const node_ptr & header, const node_ptr & new_node | |
244 | ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
245 | { | |
246 | std::size_t depth; | |
247 | bstree_algo::push_back(header, new_node, &depth); | |
248 | rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); | |
249 | } | |
250 | ||
251 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) | |
252 | template<class H_Alpha> | |
253 | static void push_front(const node_ptr & header, const node_ptr & new_node | |
254 | ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
255 | { | |
256 | std::size_t depth; | |
257 | bstree_algo::push_front(header, new_node, &depth); | |
258 | rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); | |
259 | } | |
260 | ||
261 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) | |
262 | template<class KeyType, class KeyNodePtrCompare> | |
263 | static std::pair<node_ptr, bool> insert_unique_check | |
264 | (const const_node_ptr & header, const KeyType &key | |
265 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data) | |
266 | { | |
267 | std::size_t depth; | |
268 | std::pair<node_ptr, bool> ret = | |
269 | bstree_algo::insert_unique_check(header, key, comp, commit_data, &depth); | |
270 | commit_data.depth = depth; | |
271 | return ret; | |
272 | } | |
273 | ||
274 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) | |
275 | template<class KeyType, class KeyNodePtrCompare> | |
276 | static std::pair<node_ptr, bool> insert_unique_check | |
277 | (const const_node_ptr & header, const node_ptr &hint, const KeyType &key | |
278 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data) | |
279 | { | |
280 | std::size_t depth; | |
281 | std::pair<node_ptr, bool> ret = | |
282 | bstree_algo::insert_unique_check | |
283 | (header, hint, key, comp, commit_data, &depth); | |
284 | commit_data.depth = depth; | |
285 | return ret; | |
286 | } | |
287 | ||
288 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) | |
289 | template<class H_Alpha> | |
290 | BOOST_INTRUSIVE_FORCEINLINE static void insert_unique_commit | |
291 | (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data | |
292 | ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
293 | { return insert_commit(header, new_value, commit_data, tree_size, h_alpha, max_tree_size); } | |
294 | ||
295 | //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique | |
296 | template<class NodePtrCompare, class H_Alpha, class AlphaByMaxSize> | |
297 | static bool transfer_unique | |
298 | ( const node_ptr & header1, NodePtrCompare comp, std::size_t tree1_size, std::size_t &max_tree1_size | |
299 | , const node_ptr &header2, const node_ptr & z, std::size_t tree2_size, std::size_t &max_tree2_size | |
300 | ,H_Alpha h_alpha, AlphaByMaxSize alpha_by_maxsize) | |
301 | { | |
302 | insert_commit_data commit_data; | |
303 | bool const transferable = insert_unique_check(header1, z, comp, commit_data).second; | |
304 | if(transferable){ | |
305 | erase(header2, z, tree2_size, max_tree2_size, alpha_by_maxsize); | |
306 | insert_commit(header1, z, commit_data, tree1_size, h_alpha, max_tree1_size); | |
307 | } | |
308 | return transferable; | |
309 | } | |
310 | ||
311 | //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal | |
312 | template<class NodePtrCompare, class H_Alpha, class AlphaByMaxSize> | |
313 | static void transfer_equal | |
314 | ( const node_ptr & header1, NodePtrCompare comp, std::size_t tree1_size, std::size_t &max_tree1_size | |
315 | , const node_ptr &header2, const node_ptr & z, std::size_t tree2_size, std::size_t &max_tree2_size | |
316 | ,H_Alpha h_alpha, AlphaByMaxSize alpha_by_maxsize) | |
317 | { | |
318 | insert_commit_data commit_data; | |
319 | insert_equal_upper_bound_check(header1, z, comp, commit_data); | |
320 | erase(header2, z, tree2_size, max_tree2_size, alpha_by_maxsize); | |
321 | insert_commit(header1, z, commit_data, tree1_size, h_alpha, max_tree1_size); | |
322 | } | |
323 | ||
324 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
325 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header | |
326 | static bool is_header(const const_node_ptr & p); | |
327 | ||
328 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header | |
329 | static void rebalance(const node_ptr & header); | |
330 | ||
331 | //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance_subtree | |
332 | static node_ptr rebalance_subtree(const node_ptr & old_root) | |
333 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
334 | ||
335 | /// @cond | |
336 | private: | |
337 | ||
338 | template<class KeyType, class KeyNodePtrCompare> | |
339 | static void insert_equal_upper_bound_check | |
340 | (const node_ptr & header, const KeyType &key | |
341 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data) | |
342 | { | |
343 | std::size_t depth; | |
344 | bstree_algo::insert_equal_upper_bound_check(header, key, comp, commit_data, &depth); | |
345 | commit_data.depth = depth; | |
346 | } | |
347 | ||
348 | template<class H_Alpha> | |
349 | static void insert_commit | |
350 | (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data | |
351 | ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
352 | { | |
353 | bstree_algo::insert_unique_commit(header, new_value, commit_data); | |
354 | rebalance_after_insertion(new_value, commit_data.depth, tree_size+1, h_alpha, max_tree_size); | |
355 | } | |
356 | ||
357 | template<class H_Alpha> | |
358 | static void rebalance_after_insertion | |
359 | (const node_ptr &x, std::size_t depth | |
360 | , std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) | |
361 | { | |
362 | if(tree_size > max_tree_size) | |
363 | max_tree_size = tree_size; | |
364 | ||
365 | if(tree_size > 2 && //Nothing to do with only the root | |
366 | //Check if the root node is unbalanced | |
367 | //Scapegoat paper depth counts root depth as zero and "depth" counts root as 1, | |
368 | //but since "depth" is the depth of the ancestor of x, i == depth | |
369 | depth > h_alpha(tree_size)){ | |
370 | ||
371 | //Find the first non height-balanced node | |
372 | //as described in the section 4.2 of the paper. | |
373 | //This method is the alternative method described | |
374 | //in the paper. Authors claim that this method | |
375 | //may tend to yield more balanced trees on the average | |
376 | //than the weight balanced method. | |
377 | node_ptr s = x; | |
378 | std::size_t size = 1; | |
379 | for(std::size_t ancestor = 1; ancestor != depth; ++ancestor){ | |
380 | const node_ptr s_parent = NodeTraits::get_parent(s); | |
381 | const node_ptr s_parent_left = NodeTraits::get_left(s_parent); | |
382 | //Obtain parent's size (previous size + parent + sibling tree) | |
383 | const node_ptr s_sibling = s_parent_left == s ? NodeTraits::get_right(s_parent) : s_parent_left; | |
384 | size += 1 + bstree_algo::subtree_size(s_sibling); | |
385 | s = s_parent; | |
386 | if(ancestor > h_alpha(size)){ //is 's' scapegoat? | |
387 | bstree_algo::rebalance_subtree(s); | |
388 | return; | |
389 | } | |
390 | } | |
391 | //The whole tree must be rebuilt | |
392 | max_tree_size = tree_size; | |
393 | bstree_algo::rebalance_subtree(NodeTraits::get_parent(s)); | |
394 | } | |
395 | } | |
396 | /// @endcond | |
397 | }; | |
398 | ||
399 | /// @cond | |
400 | ||
401 | template<class NodeTraits> | |
402 | struct get_algo<SgTreeAlgorithms, NodeTraits> | |
403 | { | |
404 | typedef sgtree_algorithms<NodeTraits> type; | |
405 | }; | |
406 | ||
407 | template <class ValueTraits, class NodePtrCompare, class ExtraChecker> | |
408 | struct get_node_checker<SgTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> | |
409 | { | |
410 | typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; | |
411 | }; | |
412 | ||
413 | /// @endcond | |
414 | ||
415 | } //namespace intrusive | |
416 | } //namespace boost | |
417 | ||
418 | #include <boost/intrusive/detail/config_end.hpp> | |
419 | ||
420 | #endif //BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP |