1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Ion Gaztanaga 2006-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_TREAP_ALGORITHMS_HPP |
14 | #define BOOST_INTRUSIVE_TREAP_ALGORITHMS_HPP |
15 | |
16 | #include <boost/intrusive/detail/config_begin.hpp> |
17 | #include <boost/intrusive/intrusive_fwd.hpp> |
18 | |
19 | #include <cstddef> |
20 | |
21 | #include <boost/intrusive/detail/assert.hpp> |
22 | #include <boost/intrusive/detail/algo_type.hpp> |
23 | #include <boost/intrusive/bstree_algorithms.hpp> |
24 | |
25 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
26 | # pragma once |
27 | #endif |
28 | |
29 | namespace boost { |
30 | namespace intrusive { |
31 | |
32 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
33 | |
34 | namespace detail |
35 | { |
36 | |
37 | template<class ValueTraits, class NodePtrPrioCompare, class ExtraChecker> |
38 | struct |
39 | : public ExtraChecker |
40 | { |
41 | typedef ExtraChecker ; |
42 | typedef ValueTraits ; |
43 | typedef typename value_traits::node_traits ; |
44 | typedef typename node_traits::const_node_ptr ; |
45 | |
46 | typedef typename base_checker_t::return_type ; |
47 | |
48 | (const NodePtrPrioCompare& prio_comp, ExtraChecker ) |
49 | : base_checker_t(extra_checker), prio_comp_(prio_comp) |
50 | {} |
51 | |
52 | void (const const_node_ptr& p, |
53 | const return_type& check_return_left, const return_type& check_return_right, |
54 | return_type& check_return) |
55 | { |
56 | if (node_traits::get_left(p)) |
57 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!prio_comp_(node_traits::get_left(p), p)); |
58 | if (node_traits::get_right(p)) |
59 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!prio_comp_(node_traits::get_right(p), p)); |
60 | base_checker_t::operator()(p, check_return_left, check_return_right, check_return); |
61 | } |
62 | |
63 | const NodePtrPrioCompare ; |
64 | }; |
65 | |
66 | } // namespace detail |
67 | |
68 | #endif //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
69 | |
70 | //! treap_algorithms provides basic algorithms to manipulate |
71 | //! nodes forming a treap. |
72 | //! |
73 | //! (1) the header node is maintained with links not only to the root |
74 | //! but also to the leftmost node of the tree, to enable constant time |
75 | //! begin(), and to the rightmost node of the tree, to enable linear time |
76 | //! performance when used with the generic set algorithms (set_union, |
77 | //! etc.); |
78 | //! |
79 | //! (2) when a node being deleted has two children its successor node is |
80 | //! relinked into its place, rather than copied, so that the only |
81 | //! pointers invalidated are those referring to the deleted node. |
82 | //! |
83 | //! treap_algorithms is configured with a NodeTraits class, which encapsulates the |
84 | //! information about the node to be manipulated. NodeTraits must support the |
85 | //! following interface: |
86 | //! |
87 | //! <b>Typedefs</b>: |
88 | //! |
89 | //! <tt>node</tt>: The type of the node that forms the treap |
90 | //! |
91 | //! <tt>node_ptr</tt>: A pointer to a node |
92 | //! |
93 | //! <tt>const_node_ptr</tt>: A pointer to a const node |
94 | //! |
95 | //! <b>Static functions</b>: |
96 | //! |
97 | //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> |
98 | //! |
99 | //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> |
100 | //! |
101 | //! <tt>static node_ptr get_left(const_node_ptr n);</tt> |
102 | //! |
103 | //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> |
104 | //! |
105 | //! <tt>static node_ptr get_right(const_node_ptr n);</tt> |
106 | //! |
107 | //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> |
108 | template<class NodeTraits> |
109 | class treap_algorithms |
110 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
111 | : public bstree_algorithms<NodeTraits> |
112 | #endif |
113 | { |
114 | public: |
115 | typedef NodeTraits node_traits; |
116 | typedef typename NodeTraits::node node; |
117 | typedef typename NodeTraits::node_ptr node_ptr; |
118 | typedef typename NodeTraits::const_node_ptr const_node_ptr; |
119 | |
120 | /// @cond |
121 | private: |
122 | |
123 | typedef bstree_algorithms<NodeTraits> bstree_algo; |
124 | |
125 | class rerotate_on_destroy |
126 | { |
127 | rerotate_on_destroy& operator=(const rerotate_on_destroy&); |
128 | |
129 | public: |
130 | rerotate_on_destroy(const node_ptr & , const node_ptr & p, std::size_t &n) |
131 | : header_(header), p_(p), n_(n), remove_it_(true) |
132 | {} |
133 | |
134 | ~rerotate_on_destroy() |
135 | { |
136 | if(remove_it_){ |
137 | rotate_up_n(header: header_, p: p_, n: n_); |
138 | } |
139 | } |
140 | |
141 | void release() |
142 | { remove_it_ = false; } |
143 | |
144 | const node_ptr ; |
145 | const node_ptr p_; |
146 | std::size_t &n_; |
147 | bool remove_it_; |
148 | }; |
149 | |
150 | static void rotate_up_n(const node_ptr , const node_ptr p, std::size_t n) |
151 | { |
152 | node_ptr p_parent(NodeTraits::get_parent(p)); |
153 | node_ptr p_grandparent(NodeTraits::get_parent(p_parent)); |
154 | while(n--){ |
155 | if(p == NodeTraits::get_left(p_parent)){ //p is left child |
156 | bstree_algo::rotate_right(p_parent, p, p_grandparent, header); |
157 | } |
158 | else{ //p is right child |
159 | bstree_algo::rotate_left(p_parent, p, p_grandparent, header); |
160 | } |
161 | p_parent = p_grandparent; |
162 | p_grandparent = NodeTraits::get_parent(p_parent); |
163 | } |
164 | } |
165 | |
166 | /// @endcond |
167 | |
168 | public: |
169 | //! This type is the information that will be |
170 | //! filled by insert_unique_check |
171 | struct insert_commit_data |
172 | /// @cond |
173 | : public bstree_algo::insert_commit_data |
174 | /// @endcond |
175 | { |
176 | /// @cond |
177 | std::size_t rotations; |
178 | /// @endcond |
179 | }; |
180 | |
181 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
182 | |
183 | //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) |
184 | static node_ptr get_header(const const_node_ptr & n); |
185 | |
186 | //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node |
187 | static node_ptr begin_node(const const_node_ptr & header); |
188 | |
189 | //! @copydoc ::boost::intrusive::bstree_algorithms::end_node |
190 | static node_ptr end_node(const const_node_ptr & header); |
191 | |
192 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree |
193 | static void swap_tree(const node_ptr & header1, const node_ptr & header2); |
194 | |
195 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) |
196 | static void swap_nodes(const node_ptr & node1, const node_ptr & node2); |
197 | |
198 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&) |
199 | static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2); |
200 | |
201 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) |
202 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node); |
203 | |
204 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) |
205 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node); |
206 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
207 | |
208 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&) |
209 | template<class NodePtrPriorityCompare> |
210 | static void unlink(const node_ptr & node, NodePtrPriorityCompare pcomp) |
211 | { |
212 | node_ptr x = NodeTraits::get_parent(node); |
213 | if(x){ |
214 | while(!bstree_algo::is_header(x)) |
215 | x = NodeTraits::get_parent(x); |
216 | erase(x, node, pcomp); |
217 | } |
218 | } |
219 | |
220 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
221 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance |
222 | static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); |
223 | |
224 | //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) |
225 | static bool unique(const const_node_ptr & node); |
226 | |
227 | //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) |
228 | static std::size_t size(const const_node_ptr & header); |
229 | |
230 | //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) |
231 | static node_ptr next_node(const node_ptr & node); |
232 | |
233 | //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) |
234 | static node_ptr prev_node(const node_ptr & node); |
235 | |
236 | //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) |
237 | static void init(const node_ptr & node); |
238 | |
239 | //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&) |
240 | static void init_header(const node_ptr & header); |
241 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
242 | |
243 | //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) |
244 | template<class NodePtrPriorityCompare> |
245 | static node_ptr erase(const node_ptr & , const node_ptr & z, NodePtrPriorityCompare pcomp) |
246 | { |
247 | rebalance_for_erasure(header, z, pcomp); |
248 | bstree_algo::erase(header, z); |
249 | return z; |
250 | } |
251 | |
252 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
253 | //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) |
254 | template <class Cloner, class Disposer> |
255 | static void clone |
256 | (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer); |
257 | |
258 | //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) |
259 | template<class Disposer> |
260 | static void clear_and_dispose(const node_ptr & header, Disposer disposer); |
261 | |
262 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
263 | template<class KeyType, class KeyNodePtrCompare> |
264 | static node_ptr lower_bound |
265 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
266 | |
267 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
268 | template<class KeyType, class KeyNodePtrCompare> |
269 | static node_ptr upper_bound |
270 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
271 | |
272 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) |
273 | template<class KeyType, class KeyNodePtrCompare> |
274 | static node_ptr find |
275 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
276 | |
277 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
278 | template<class KeyType, class KeyNodePtrCompare> |
279 | static std::pair<node_ptr, node_ptr> equal_range |
280 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
281 | |
282 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) |
283 | template<class KeyType, class KeyNodePtrCompare> |
284 | static std::pair<node_ptr, node_ptr> bounded_range |
285 | (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp |
286 | , bool left_closed, bool right_closed); |
287 | |
288 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
289 | template<class KeyType, class KeyNodePtrCompare> |
290 | static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
291 | |
292 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
293 | |
294 | //! <b>Requires</b>: "h" must be the header node of a tree. |
295 | //! NodePtrCompare is a function object that induces a strict weak |
296 | //! ordering compatible with the strict weak ordering used to create the |
297 | //! the tree. NodePtrCompare compares two node_ptrs. |
298 | //! NodePtrPriorityCompare is a priority function object that induces a strict weak |
299 | //! ordering compatible with the one used to create the |
300 | //! the tree. NodePtrPriorityCompare compares two node_ptrs. |
301 | //! |
302 | //! <b>Effects</b>: Inserts new_node into the tree before the upper bound |
303 | //! according to "comp" and rotates the tree according to "pcomp". |
304 | //! |
305 | //! <b>Complexity</b>: Average complexity for insert element is at |
306 | //! most logarithmic. |
307 | //! |
308 | //! <b>Throws</b>: If "comp" throw or "pcomp" throw. |
309 | template<class NodePtrCompare, class NodePtrPriorityCompare> |
310 | static node_ptr insert_equal_upper_bound |
311 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp) |
312 | { |
313 | insert_commit_data commit_data; |
314 | bstree_algo::insert_equal_upper_bound_check(h, new_node, comp, commit_data); |
315 | rebalance_check_and_commit(h, new_node, pcomp, commit_data); |
316 | return new_node; |
317 | } |
318 | |
319 | //! <b>Requires</b>: "h" must be the header node of a tree. |
320 | //! NodePtrCompare is a function object that induces a strict weak |
321 | //! ordering compatible with the strict weak ordering used to create the |
322 | //! the tree. NodePtrCompare compares two node_ptrs. |
323 | //! NodePtrPriorityCompare is a priority function object that induces a strict weak |
324 | //! ordering compatible with the one used to create the |
325 | //! the tree. NodePtrPriorityCompare compares two node_ptrs. |
326 | //! |
327 | //! <b>Effects</b>: Inserts new_node into the tree before the upper bound |
328 | //! according to "comp" and rotates the tree according to "pcomp". |
329 | //! |
330 | //! <b>Complexity</b>: Average complexity for insert element is at |
331 | //! most logarithmic. |
332 | //! |
333 | //! <b>Throws</b>: If "comp" throws. |
334 | template<class NodePtrCompare, class NodePtrPriorityCompare> |
335 | static node_ptr insert_equal_lower_bound |
336 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp) |
337 | { |
338 | insert_commit_data commit_data; |
339 | bstree_algo::insert_equal_lower_bound_check(h, new_node, comp, commit_data); |
340 | rebalance_check_and_commit(h, new_node, pcomp, commit_data); |
341 | return new_node; |
342 | } |
343 | |
344 | //! <b>Requires</b>: "header" must be the header node of a tree. |
345 | //! NodePtrCompare is a function object that induces a strict weak |
346 | //! ordering compatible with the strict weak ordering used to create the |
347 | //! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from |
348 | //! the "header"'s tree. |
349 | //! NodePtrPriorityCompare is a priority function object that induces a strict weak |
350 | //! ordering compatible with the one used to create the |
351 | //! the tree. NodePtrPriorityCompare compares two node_ptrs. |
352 | //! |
353 | //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to |
354 | //! where it will be inserted. If "hint" is the upper_bound |
355 | //! the insertion takes constant time (two comparisons in the worst case). |
356 | //! Rotates the tree according to "pcomp". |
357 | //! |
358 | //! <b>Complexity</b>: Logarithmic in general, but it is amortized |
359 | //! constant time if new_node is inserted immediately before "hint". |
360 | //! |
361 | //! <b>Throws</b>: If "comp" throw or "pcomp" throw. |
362 | template<class NodePtrCompare, class NodePtrPriorityCompare> |
363 | static node_ptr insert_equal |
364 | (const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp) |
365 | { |
366 | insert_commit_data commit_data; |
367 | bstree_algo::insert_equal_check(h, hint, new_node, comp, commit_data); |
368 | rebalance_check_and_commit(h, new_node, pcomp, commit_data); |
369 | return new_node; |
370 | } |
371 | |
372 | //! <b>Requires</b>: "header" must be the header node of a tree. |
373 | //! "pos" must be a valid node of the tree (including header end) node. |
374 | //! "pos" must be a node pointing to the successor to "new_node" |
375 | //! once inserted according to the order of already inserted nodes. This function does not |
376 | //! check "pos" and this precondition must be guaranteed by the caller. |
377 | //! NodePtrPriorityCompare is a priority function object that induces a strict weak |
378 | //! ordering compatible with the one used to create the |
379 | //! the tree. NodePtrPriorityCompare compares two node_ptrs. |
380 | //! |
381 | //! <b>Effects</b>: Inserts new_node into the tree before "pos" |
382 | //! and rotates the tree according to "pcomp". |
383 | //! |
384 | //! <b>Complexity</b>: Constant-time. |
385 | //! |
386 | //! <b>Throws</b>: If "pcomp" throws, strong guarantee. |
387 | //! |
388 | //! <b>Note</b>: If "pos" is not the successor of the newly inserted "new_node" |
389 | //! tree invariants might be broken. |
390 | template<class NodePtrPriorityCompare> |
391 | static node_ptr insert_before |
392 | (const node_ptr & , const node_ptr & pos, const node_ptr & new_node, NodePtrPriorityCompare pcomp) |
393 | { |
394 | insert_commit_data commit_data; |
395 | bstree_algo::insert_before_check(header, pos, commit_data); |
396 | rebalance_check_and_commit(header, new_node, pcomp, commit_data); |
397 | return new_node; |
398 | } |
399 | |
400 | //! <b>Requires</b>: "header" must be the header node of a tree. |
401 | //! "new_node" must be, according to the used ordering no less than the |
402 | //! greatest inserted key. |
403 | //! NodePtrPriorityCompare is a priority function object that induces a strict weak |
404 | //! ordering compatible with the one used to create the |
405 | //! the tree. NodePtrPriorityCompare compares two node_ptrs. |
406 | //! |
407 | //! <b>Effects</b>: Inserts x into the tree in the last position |
408 | //! and rotates the tree according to "pcomp". |
409 | //! |
410 | //! <b>Complexity</b>: Constant-time. |
411 | //! |
412 | //! <b>Throws</b>: If "pcomp" throws, strong guarantee. |
413 | //! |
414 | //! <b>Note</b>: If "new_node" is less than the greatest inserted key |
415 | //! tree invariants are broken. This function is slightly faster than |
416 | //! using "insert_before". |
417 | template<class NodePtrPriorityCompare> |
418 | static void push_back(const node_ptr & , const node_ptr & new_node, NodePtrPriorityCompare pcomp) |
419 | { |
420 | insert_commit_data commit_data; |
421 | bstree_algo::push_back_check(header, commit_data); |
422 | rebalance_check_and_commit(header, new_node, pcomp, commit_data); |
423 | } |
424 | |
425 | //! <b>Requires</b>: "header" must be the header node of a tree. |
426 | //! "new_node" must be, according to the used ordering, no greater than the |
427 | //! lowest inserted key. |
428 | //! NodePtrPriorityCompare is a priority function object that induces a strict weak |
429 | //! ordering compatible with the one used to create the |
430 | //! the tree. NodePtrPriorityCompare compares two node_ptrs. |
431 | //! |
432 | //! <b>Effects</b>: Inserts x into the tree in the first position |
433 | //! and rotates the tree according to "pcomp". |
434 | //! |
435 | //! <b>Complexity</b>: Constant-time. |
436 | //! |
437 | //! <b>Throws</b>: If "pcomp" throws, strong guarantee. |
438 | //! |
439 | //! <b>Note</b>: If "new_node" is greater than the lowest inserted key |
440 | //! tree invariants are broken. This function is slightly faster than |
441 | //! using "insert_before". |
442 | template<class NodePtrPriorityCompare> |
443 | static void push_front(const node_ptr & , const node_ptr & new_node, NodePtrPriorityCompare pcomp) |
444 | { |
445 | insert_commit_data commit_data; |
446 | bstree_algo::push_front_check(header, commit_data); |
447 | rebalance_check_and_commit(header, new_node, pcomp, commit_data); |
448 | } |
449 | |
450 | //! <b>Requires</b>: "header" must be the header node of a tree. |
451 | //! KeyNodePtrCompare is a function object that induces a strict weak |
452 | //! ordering compatible with the strict weak ordering used to create the |
453 | //! the tree. NodePtrCompare compares KeyType with a node_ptr. |
454 | //! |
455 | //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the |
456 | //! tree according to "comp" and obtains the needed information to realize |
457 | //! a constant-time node insertion if there is no equivalent node. |
458 | //! |
459 | //! <b>Returns</b>: If there is an equivalent value |
460 | //! returns a pair containing a node_ptr to the already present node |
461 | //! and false. If there is not equivalent key can be inserted returns true |
462 | //! in the returned pair's boolean and fills "commit_data" that is meant to |
463 | //! be used with the "insert_commit" function to achieve a constant-time |
464 | //! insertion function. |
465 | //! |
466 | //! <b>Complexity</b>: Average complexity is at most logarithmic. |
467 | //! |
468 | //! <b>Throws</b>: If "comp" throws. |
469 | //! |
470 | //! <b>Notes</b>: This function is used to improve performance when constructing |
471 | //! a node is expensive and the user does not want to have two equivalent nodes |
472 | //! in the tree: if there is an equivalent value |
473 | //! the constructed object must be discarded. Many times, the part of the |
474 | //! node that is used to impose the order is much cheaper to construct |
475 | //! than the node and this function offers the possibility to use that part |
476 | //! to check if the insertion will be successful. |
477 | //! |
478 | //! If the check is successful, the user can construct the node and use |
479 | //! "insert_commit" to insert the node in constant-time. This gives a total |
480 | //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). |
481 | //! |
482 | //! "commit_data" remains valid for a subsequent "insert_unique_commit" only |
483 | //! if no more objects are inserted or erased from the set. |
484 | template<class KeyType, class KeyNodePtrCompare, class KeyNodePtrPrioCompare> |
485 | static std::pair<node_ptr, bool> insert_unique_check |
486 | (const const_node_ptr & , const KeyType &key |
487 | ,KeyNodePtrCompare comp, KeyNodePtrPrioCompare pcomp |
488 | ,insert_commit_data &commit_data) |
489 | { |
490 | std::pair<node_ptr, bool> ret = |
491 | bstree_algo::insert_unique_check(header, key, comp, commit_data); |
492 | if(ret.second) |
493 | rebalance_after_insertion_check(header, commit_data.node, key, pcomp, commit_data.rotations); |
494 | return ret; |
495 | } |
496 | |
497 | //! <b>Requires</b>: "header" must be the header node of a tree. |
498 | //! KeyNodePtrCompare is a function object that induces a strict weak |
499 | //! ordering compatible with the strict weak ordering used to create the |
500 | //! the tree. NodePtrCompare compares KeyType with a node_ptr. |
501 | //! "hint" is node from the "header"'s tree. |
502 | //! |
503 | //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the |
504 | //! tree according to "comp" using "hint" as a hint to where it should be |
505 | //! inserted and obtains the needed information to realize |
506 | //! a constant-time node insertion if there is no equivalent node. |
507 | //! If "hint" is the upper_bound the function has constant time |
508 | //! complexity (two comparisons in the worst case). |
509 | //! |
510 | //! <b>Returns</b>: If there is an equivalent value |
511 | //! returns a pair containing a node_ptr to the already present node |
512 | //! and false. If there is not equivalent key can be inserted returns true |
513 | //! in the returned pair's boolean and fills "commit_data" that is meant to |
514 | //! be used with the "insert_commit" function to achieve a constant-time |
515 | //! insertion function. |
516 | //! |
517 | //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is |
518 | //! amortized constant time if new_node should be inserted immediately before "hint". |
519 | //! |
520 | //! <b>Throws</b>: If "comp" throws. |
521 | //! |
522 | //! <b>Notes</b>: This function is used to improve performance when constructing |
523 | //! a node is expensive and the user does not want to have two equivalent nodes |
524 | //! in the tree: if there is an equivalent value |
525 | //! the constructed object must be discarded. Many times, the part of the |
526 | //! node that is used to impose the order is much cheaper to construct |
527 | //! than the node and this function offers the possibility to use that part |
528 | //! to check if the insertion will be successful. |
529 | //! |
530 | //! If the check is successful, the user can construct the node and use |
531 | //! "insert_commit" to insert the node in constant-time. This gives a total |
532 | //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). |
533 | //! |
534 | //! "commit_data" remains valid for a subsequent "insert_unique_commit" only |
535 | //! if no more objects are inserted or erased from the set. |
536 | template<class KeyType, class KeyNodePtrCompare, class KeyNodePtrPrioCompare> |
537 | static std::pair<node_ptr, bool> insert_unique_check |
538 | (const const_node_ptr & , const node_ptr & hint, const KeyType &key |
539 | ,KeyNodePtrCompare comp, KeyNodePtrPrioCompare pcomp, insert_commit_data &commit_data) |
540 | { |
541 | std::pair<node_ptr, bool> ret = |
542 | bstree_algo::insert_unique_check(header, hint, key, comp, commit_data); |
543 | if(ret.second) |
544 | rebalance_after_insertion_check(header, commit_data.node, key, pcomp, commit_data.rotations); |
545 | return ret; |
546 | } |
547 | |
548 | //! <b>Requires</b>: "header" must be the header node of a tree. |
549 | //! "commit_data" must have been obtained from a previous call to |
550 | //! "insert_unique_check". No objects should have been inserted or erased |
551 | //! from the set between the "insert_unique_check" that filled "commit_data" |
552 | //! and the call to "insert_commit". |
553 | //! |
554 | //! |
555 | //! <b>Effects</b>: Inserts new_node in the set using the information obtained |
556 | //! from the "commit_data" that a previous "insert_check" filled. |
557 | //! |
558 | //! <b>Complexity</b>: Constant time. |
559 | //! |
560 | //! <b>Throws</b>: Nothing. |
561 | //! |
562 | //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been |
563 | //! previously executed to fill "commit_data". No value should be inserted or |
564 | //! erased between the "insert_check" and "insert_commit" calls. |
565 | static void insert_unique_commit |
566 | (const node_ptr & , const node_ptr & new_node, const insert_commit_data &commit_data) |
567 | { |
568 | bstree_algo::insert_unique_commit(header, new_node, commit_data); |
569 | rotate_up_n(header, p: new_node, n: commit_data.rotations); |
570 | } |
571 | |
572 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
573 | |
574 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header |
575 | static bool is_header(const const_node_ptr & p); |
576 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
577 | |
578 | /// @cond |
579 | private: |
580 | |
581 | template<class NodePtrPriorityCompare> |
582 | static void rebalance_for_erasure(const node_ptr & , const node_ptr & z, NodePtrPriorityCompare pcomp) |
583 | { |
584 | std::size_t n = 0; |
585 | rerotate_on_destroy rb(header, z, n); |
586 | |
587 | node_ptr z_left = NodeTraits::get_left(z); |
588 | node_ptr z_right = NodeTraits::get_right(z); |
589 | while(z_left || z_right){ |
590 | const node_ptr z_parent(NodeTraits::get_parent(z)); |
591 | if(!z_right || (z_left && pcomp(z_left, z_right))){ |
592 | bstree_algo::rotate_right(z, z_left, z_parent, header); |
593 | } |
594 | else{ |
595 | bstree_algo::rotate_left(z, z_right, z_parent, header); |
596 | } |
597 | ++n; |
598 | z_left = NodeTraits::get_left(z); |
599 | z_right = NodeTraits::get_right(z); |
600 | } |
601 | rb.release(); |
602 | } |
603 | |
604 | template<class NodePtrPriorityCompare> |
605 | static void rebalance_check_and_commit |
606 | (const node_ptr & h, const node_ptr & new_node, NodePtrPriorityCompare pcomp, insert_commit_data &commit_data) |
607 | { |
608 | rebalance_after_insertion_check(h, commit_data.node, new_node, pcomp, commit_data.rotations); |
609 | //No-throw |
610 | bstree_algo::insert_unique_commit(h, new_node, commit_data); |
611 | rotate_up_n(header: h, p: new_node, n: commit_data.rotations); |
612 | } |
613 | |
614 | template<class Key, class KeyNodePriorityCompare> |
615 | static void rebalance_after_insertion_check |
616 | (const const_node_ptr &, const const_node_ptr & up, const Key &k |
617 | , KeyNodePriorityCompare pcomp, std::size_t &num_rotations) |
618 | { |
619 | const_node_ptr upnode(up); |
620 | //First check rotations since pcomp can throw |
621 | num_rotations = 0; |
622 | std::size_t n = 0; |
623 | while(upnode != header && pcomp(k, upnode)){ |
624 | ++n; |
625 | upnode = NodeTraits::get_parent(upnode); |
626 | } |
627 | num_rotations = n; |
628 | } |
629 | |
630 | template<class NodePtrPriorityCompare> |
631 | static bool check_invariant(const const_node_ptr & , NodePtrPriorityCompare pcomp) |
632 | { |
633 | node_ptr beg = begin_node(header); |
634 | node_ptr end = end_node(header); |
635 | |
636 | while(beg != end){ |
637 | node_ptr p = NodeTraits::get_parent(beg); |
638 | if(p != header){ |
639 | if(pcomp(beg, p)) |
640 | return false; |
641 | } |
642 | beg = next_node(beg); |
643 | } |
644 | return true; |
645 | } |
646 | |
647 | /// @endcond |
648 | }; |
649 | |
650 | /// @cond |
651 | |
652 | template<class NodeTraits> |
653 | struct get_algo<TreapAlgorithms, NodeTraits> |
654 | { |
655 | typedef treap_algorithms<NodeTraits> type; |
656 | }; |
657 | |
658 | template <class ValueTraits, class NodePtrCompare, class ExtraChecker> |
659 | struct get_node_checker<TreapAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> |
660 | { |
661 | typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; |
662 | }; |
663 | |
664 | /// @endcond |
665 | |
666 | } //namespace intrusive |
667 | } //namespace boost |
668 | |
669 | #include <boost/intrusive/detail/config_end.hpp> |
670 | |
671 | #endif //BOOST_INTRUSIVE_TREAP_ALGORITHMS_HPP |
672 | |