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 | #ifndef BOOST_INTRUSIVE_SPLAYTREE_HPP |
13 | #define BOOST_INTRUSIVE_SPLAYTREE_HPP |
14 | |
15 | #include <boost/intrusive/detail/config_begin.hpp> |
16 | #include <boost/intrusive/intrusive_fwd.hpp> |
17 | #include <cstddef> |
18 | #include <boost/intrusive/detail/minimal_less_equal_header.hpp> |
19 | #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair |
20 | |
21 | #include <boost/static_assert.hpp> |
22 | #include <boost/intrusive/bstree.hpp> |
23 | #include <boost/intrusive/detail/tree_node.hpp> |
24 | #include <boost/intrusive/detail/mpl.hpp> |
25 | #include <boost/intrusive/pointer_traits.hpp> |
26 | #include <boost/intrusive/detail/function_detector.hpp> |
27 | #include <boost/intrusive/detail/get_value_traits.hpp> |
28 | #include <boost/intrusive/splaytree_algorithms.hpp> |
29 | #include <boost/intrusive/link_mode.hpp> |
30 | #include <boost/intrusive/detail/key_nodeptr_comp.hpp> |
31 | #include <boost/move/utility_core.hpp> |
32 | |
33 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
34 | # pragma once |
35 | #endif |
36 | |
37 | namespace boost { |
38 | namespace intrusive { |
39 | |
40 | /// @cond |
41 | |
42 | struct splaytree_defaults |
43 | : bstree_defaults |
44 | {}; |
45 | |
46 | /// @endcond |
47 | |
48 | //! The class template splaytree is an intrusive splay tree container that |
49 | //! is used to construct intrusive splay_set and splay_multiset containers. The no-throw |
50 | //! guarantee holds only, if the key_compare object |
51 | //! doesn't throw. |
52 | //! |
53 | //! The template parameter \c T is the type to be managed by the container. |
54 | //! The user can specify additional options and if no options are provided |
55 | //! default options are used. |
56 | //! |
57 | //! The container supports the following options: |
58 | //! \c base_hook<>/member_hook<>/value_traits<>, |
59 | //! \c constant_time_size<>, \c size_type<> and |
60 | //! \c compare<>. |
61 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
62 | template<class T, class ...Options> |
63 | #else |
64 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder> |
65 | #endif |
66 | class splaytree_impl |
67 | /// @cond |
68 | : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, SplayTreeAlgorithms, HeaderHolder> |
69 | /// @endcond |
70 | { |
71 | public: |
72 | typedef ValueTraits value_traits; |
73 | /// @cond |
74 | typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType |
75 | , ConstantTimeSize, SplayTreeAlgorithms |
76 | , HeaderHolder> tree_type; |
77 | typedef tree_type implementation_defined; |
78 | /// @endcond |
79 | |
80 | typedef typename implementation_defined::pointer pointer; |
81 | typedef typename implementation_defined::const_pointer const_pointer; |
82 | typedef typename implementation_defined::value_type value_type; |
83 | typedef typename implementation_defined::key_type key_type; |
84 | typedef typename implementation_defined::key_of_value key_of_value; |
85 | typedef typename implementation_defined::reference reference; |
86 | typedef typename implementation_defined::const_reference const_reference; |
87 | typedef typename implementation_defined::difference_type difference_type; |
88 | typedef typename implementation_defined::size_type size_type; |
89 | typedef typename implementation_defined::value_compare value_compare; |
90 | typedef typename implementation_defined::key_compare key_compare; |
91 | typedef typename implementation_defined::iterator iterator; |
92 | typedef typename implementation_defined::const_iterator const_iterator; |
93 | typedef typename implementation_defined::reverse_iterator reverse_iterator; |
94 | typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; |
95 | typedef typename implementation_defined::node_traits node_traits; |
96 | typedef typename implementation_defined::node node; |
97 | typedef typename implementation_defined::node_ptr node_ptr; |
98 | typedef typename implementation_defined::const_node_ptr const_node_ptr; |
99 | typedef typename implementation_defined::node_algorithms node_algorithms; |
100 | |
101 | static const bool constant_time_size = implementation_defined::constant_time_size; |
102 | /// @cond |
103 | private: |
104 | |
105 | //noncopyable |
106 | BOOST_MOVABLE_BUT_NOT_COPYABLE(splaytree_impl) |
107 | |
108 | /// @endcond |
109 | |
110 | public: |
111 | |
112 | typedef typename implementation_defined::insert_commit_data insert_commit_data; |
113 | |
114 | //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &) |
115 | explicit splaytree_impl( const key_compare &cmp = key_compare() |
116 | , const value_traits &v_traits = value_traits()) |
117 | : tree_type(cmp, v_traits) |
118 | {} |
119 | |
120 | //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &) |
121 | template<class Iterator> |
122 | splaytree_impl( bool unique, Iterator b, Iterator e |
123 | , const key_compare &cmp = key_compare() |
124 | , const value_traits &v_traits = value_traits()) |
125 | : tree_type(cmp, v_traits) |
126 | { |
127 | if(unique) |
128 | this->insert_unique(b, e); |
129 | else |
130 | this->insert_equal(b, e); |
131 | } |
132 | |
133 | //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) |
134 | splaytree_impl(BOOST_RV_REF(splaytree_impl) x) |
135 | : tree_type(BOOST_MOVE_BASE(tree_type, x)) |
136 | {} |
137 | |
138 | //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) |
139 | splaytree_impl& operator=(BOOST_RV_REF(splaytree_impl) x) |
140 | { return static_cast<splaytree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } |
141 | |
142 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
143 | //! @copydoc ::boost::intrusive::bstree::~bstree() |
144 | ~splaytree_impl(); |
145 | |
146 | //! @copydoc ::boost::intrusive::bstree::begin() |
147 | iterator begin(); |
148 | |
149 | //! @copydoc ::boost::intrusive::bstree::begin()const |
150 | const_iterator begin() const; |
151 | |
152 | //! @copydoc ::boost::intrusive::bstree::cbegin()const |
153 | const_iterator cbegin() const; |
154 | |
155 | //! @copydoc ::boost::intrusive::bstree::end() |
156 | iterator end(); |
157 | |
158 | //! @copydoc ::boost::intrusive::bstree::end()const |
159 | const_iterator end() const; |
160 | |
161 | //! @copydoc ::boost::intrusive::bstree::cend()const |
162 | const_iterator cend() const; |
163 | |
164 | //! @copydoc ::boost::intrusive::bstree::rbegin() |
165 | reverse_iterator rbegin(); |
166 | |
167 | //! @copydoc ::boost::intrusive::bstree::rbegin()const |
168 | const_reverse_iterator rbegin() const; |
169 | |
170 | //! @copydoc ::boost::intrusive::bstree::crbegin()const |
171 | const_reverse_iterator crbegin() const; |
172 | |
173 | //! @copydoc ::boost::intrusive::bstree::rend() |
174 | reverse_iterator rend(); |
175 | |
176 | //! @copydoc ::boost::intrusive::bstree::rend()const |
177 | const_reverse_iterator rend() const; |
178 | |
179 | //! @copydoc ::boost::intrusive::bstree::crend()const |
180 | const_reverse_iterator crend() const; |
181 | |
182 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) |
183 | static splaytree_impl &container_from_end_iterator(iterator end_iterator); |
184 | |
185 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) |
186 | static const splaytree_impl &container_from_end_iterator(const_iterator end_iterator); |
187 | |
188 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) |
189 | static splaytree_impl &container_from_iterator(iterator it); |
190 | |
191 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) |
192 | static const splaytree_impl &container_from_iterator(const_iterator it); |
193 | |
194 | //! @copydoc ::boost::intrusive::bstree::key_comp()const |
195 | key_compare key_comp() const; |
196 | |
197 | //! @copydoc ::boost::intrusive::bstree::value_comp()const |
198 | value_compare value_comp() const; |
199 | |
200 | //! @copydoc ::boost::intrusive::bstree::empty()const |
201 | bool empty() const; |
202 | |
203 | //! @copydoc ::boost::intrusive::bstree::size()const |
204 | size_type size() const; |
205 | |
206 | //! @copydoc ::boost::intrusive::bstree::swap |
207 | void swap(splaytree_impl& other); |
208 | |
209 | //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer) |
210 | //! Additional notes: it also copies the alpha factor from the source container. |
211 | template <class Cloner, class Disposer> |
212 | void clone_from(const splaytree_impl &src, Cloner cloner, Disposer disposer); |
213 | |
214 | #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED |
215 | |
216 | using tree_type::clone_from; |
217 | |
218 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
219 | |
220 | //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) |
221 | template <class Cloner, class Disposer> |
222 | void clone_from(BOOST_RV_REF(splaytree_impl) src, Cloner cloner, Disposer disposer) |
223 | { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } |
224 | |
225 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
226 | |
227 | //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) |
228 | iterator insert_equal(reference value); |
229 | |
230 | //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference) |
231 | iterator insert_equal(const_iterator hint, reference value); |
232 | |
233 | //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator) |
234 | template<class Iterator> |
235 | void insert_equal(Iterator b, Iterator e); |
236 | |
237 | //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) |
238 | std::pair<iterator, bool> insert_unique(reference value); |
239 | |
240 | //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference) |
241 | iterator insert_unique(const_iterator hint, reference value); |
242 | |
243 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) |
244 | template<class KeyType, class KeyTypeKeyCompare> |
245 | std::pair<iterator, bool> insert_unique_check |
246 | (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); |
247 | |
248 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) |
249 | template<class KeyType, class KeyTypeKeyCompare> |
250 | std::pair<iterator, bool> insert_unique_check |
251 | (const_iterator hint, const KeyType &key |
252 | ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); |
253 | |
254 | //! @copydoc ::boost::intrusive::bstree::insert_unique_commit |
255 | iterator insert_unique_commit(reference value, const insert_commit_data &commit_data); |
256 | |
257 | //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator) |
258 | template<class Iterator> |
259 | void insert_unique(Iterator b, Iterator e); |
260 | |
261 | //! @copydoc ::boost::intrusive::bstree::insert_before |
262 | iterator insert_before(const_iterator pos, reference value); |
263 | |
264 | //! @copydoc ::boost::intrusive::bstree::push_back |
265 | void push_back(reference value); |
266 | |
267 | //! @copydoc ::boost::intrusive::bstree::push_front |
268 | void push_front(reference value); |
269 | |
270 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator) |
271 | iterator erase(const_iterator i); |
272 | |
273 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator) |
274 | iterator erase(const_iterator b, const_iterator e); |
275 | |
276 | //! @copydoc ::boost::intrusive::bstree::erase(const key_type &) |
277 | size_type erase(const key_type &key); |
278 | |
279 | //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare) |
280 | template<class KeyType, class KeyTypeKeyCompare> |
281 | size_type erase(const KeyType& key, KeyTypeKeyCompare comp); |
282 | |
283 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer) |
284 | template<class Disposer> |
285 | iterator erase_and_dispose(const_iterator i, Disposer disposer); |
286 | |
287 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer) |
288 | template<class Disposer> |
289 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); |
290 | |
291 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer) |
292 | template<class Disposer> |
293 | size_type erase_and_dispose(const key_type &key, Disposer disposer); |
294 | |
295 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) |
296 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> |
297 | size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); |
298 | |
299 | //! @copydoc ::boost::intrusive::bstree::clear |
300 | void clear(); |
301 | |
302 | //! @copydoc ::boost::intrusive::bstree::clear_and_dispose |
303 | template<class Disposer> |
304 | void clear_and_dispose(Disposer disposer); |
305 | |
306 | //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const |
307 | //! Additional note: non-const function, splaying is performed. |
308 | size_type count(const key_type &key); |
309 | |
310 | //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const |
311 | //! Additional note: non-const function, splaying is performed. |
312 | template<class KeyType, class KeyTypeKeyCompare> |
313 | size_type count(const KeyType &key, KeyTypeKeyCompare comp); |
314 | |
315 | //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const |
316 | //! Additional note: const function, no splaying is performed |
317 | size_type count(const key_type &key) const; |
318 | |
319 | //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const |
320 | //! Additional note: const function, no splaying is performed |
321 | template<class KeyType, class KeyTypeKeyCompare> |
322 | size_type count(const KeyType &key, KeyTypeKeyCompare comp) const; |
323 | |
324 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) |
325 | //! Additional note: non-const function, splaying is performed. |
326 | iterator lower_bound(const key_type &key); |
327 | |
328 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const |
329 | //! Additional note: const function, no splaying is performed |
330 | const_iterator lower_bound(const key_type &key) const; |
331 | |
332 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) |
333 | //! Additional note: non-const function, splaying is performed for the first |
334 | //! element of the equal range of "key" |
335 | template<class KeyType, class KeyTypeKeyCompare> |
336 | iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp); |
337 | |
338 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const |
339 | //! Additional note: const function, no splaying is performed |
340 | template<class KeyType, class KeyTypeKeyCompare> |
341 | const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const; |
342 | |
343 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) |
344 | //! Additional note: non-const function, splaying is performed for the first |
345 | //! element of the equal range of "value" |
346 | iterator upper_bound(const key_type &key); |
347 | |
348 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const |
349 | //! Additional note: const function, no splaying is performed |
350 | const_iterator upper_bound(const key_type &key) const; |
351 | |
352 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) |
353 | //! Additional note: non-const function, splaying is performed for the first |
354 | //! element of the equal range of "key" |
355 | template<class KeyType, class KeyTypeKeyCompare> |
356 | iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp); |
357 | |
358 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const |
359 | //! Additional note: const function, no splaying is performed |
360 | template<class KeyType, class KeyTypeKeyCompare> |
361 | const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const; |
362 | |
363 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &) |
364 | //! Additional note: non-const function, splaying is performed for the first |
365 | //! element of the equal range of "value" |
366 | iterator find(const key_type &key); |
367 | |
368 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const |
369 | //! Additional note: const function, no splaying is performed |
370 | const_iterator find(const key_type &key) const; |
371 | |
372 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) |
373 | //! Additional note: non-const function, splaying is performed for the first |
374 | //! element of the equal range of "key" |
375 | template<class KeyType, class KeyTypeKeyCompare> |
376 | iterator find(const KeyType &key, KeyTypeKeyCompare comp); |
377 | |
378 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const |
379 | //! Additional note: const function, no splaying is performed |
380 | template<class KeyType, class KeyTypeKeyCompare> |
381 | const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const; |
382 | |
383 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) |
384 | //! Additional note: non-const function, splaying is performed for the first |
385 | //! element of the equal range of "value" |
386 | std::pair<iterator, iterator> equal_range(const key_type &key); |
387 | |
388 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const |
389 | //! Additional note: const function, no splaying is performed |
390 | std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const; |
391 | |
392 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) |
393 | //! Additional note: non-const function, splaying is performed for the first |
394 | //! element of the equal range of "key" |
395 | template<class KeyType, class KeyTypeKeyCompare> |
396 | std::pair<iterator, iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp); |
397 | |
398 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const |
399 | //! Additional note: const function, no splaying is performed |
400 | template<class KeyType, class KeyTypeKeyCompare> |
401 | std::pair<const_iterator, const_iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp) const; |
402 | |
403 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) |
404 | std::pair<iterator,iterator> bounded_range |
405 | (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed); |
406 | |
407 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) |
408 | template<class KeyType, class KeyTypeKeyCompare> |
409 | std::pair<iterator,iterator> bounded_range |
410 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); |
411 | |
412 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const |
413 | std::pair<const_iterator, const_iterator> bounded_range |
414 | (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; |
415 | |
416 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const |
417 | template<class KeyType, class KeyTypeKeyCompare> |
418 | std::pair<const_iterator, const_iterator> bounded_range |
419 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; |
420 | |
421 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) |
422 | static iterator s_iterator_to(reference value); |
423 | |
424 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) |
425 | static const_iterator s_iterator_to(const_reference value); |
426 | |
427 | //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) |
428 | iterator iterator_to(reference value); |
429 | |
430 | //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const |
431 | const_iterator iterator_to(const_reference value) const; |
432 | |
433 | //! @copydoc ::boost::intrusive::bstree::init_node(reference) |
434 | static void init_node(reference value); |
435 | |
436 | //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance |
437 | pointer unlink_leftmost_without_rebalance(); |
438 | |
439 | //! @copydoc ::boost::intrusive::bstree::replace_node |
440 | void replace_node(iterator replace_this, reference with_this); |
441 | |
442 | //! @copydoc ::boost::intrusive::bstree::remove_node |
443 | void remove_node(reference value); |
444 | |
445 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
446 | |
447 | //! <b>Requires</b>: i must be a valid iterator of *this. |
448 | //! |
449 | //! <b>Effects</b>: Rearranges the container so that the element pointed by i |
450 | //! is placed as the root of the tree, improving future searches of this value. |
451 | //! |
452 | //! <b>Complexity</b>: Amortized logarithmic. |
453 | //! |
454 | //! <b>Throws</b>: Nothing. |
455 | void splay_up(iterator i) |
456 | { return node_algorithms::splay_up(i.pointed_node(), tree_type::header_ptr()); } |
457 | |
458 | //! <b>Effects</b>: Rearranges the container so that if *this stores an element |
459 | //! with a key equivalent to value the element is placed as the root of the |
460 | //! tree. If the element is not present returns the last node compared with the key. |
461 | //! If the tree is empty, end() is returned. |
462 | //! |
463 | //! <b>Complexity</b>: Amortized logarithmic. |
464 | //! |
465 | //! <b>Returns</b>: An iterator to the new root of the tree, end() if the tree is empty. |
466 | //! |
467 | //! <b>Throws</b>: If the comparison functor throws. |
468 | template<class KeyType, class KeyTypeKeyCompare> |
469 | iterator splay_down(const KeyType &key, KeyTypeKeyCompare comp) |
470 | { |
471 | detail::key_nodeptr_comp<value_compare, value_traits> |
472 | key_node_comp(comp, &this->get_value_traits()); |
473 | node_ptr r = node_algorithms::splay_down(tree_type::header_ptr(), key, key_node_comp); |
474 | return iterator(r, this->priv_value_traits_ptr()); |
475 | } |
476 | |
477 | //! <b>Effects</b>: Rearranges the container so that if *this stores an element |
478 | //! with a key equivalent to value the element is placed as the root of the |
479 | //! tree. |
480 | //! |
481 | //! <b>Complexity</b>: Amortized logarithmic. |
482 | //! |
483 | //! <b>Returns</b>: An iterator to the new root of the tree, end() if the tree is empty. |
484 | //! |
485 | //! <b>Throws</b>: If the predicate throws. |
486 | iterator splay_down(const key_type &key) |
487 | { return this->splay_down(key, this->key_comp()); } |
488 | |
489 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
490 | //! @copydoc ::boost::intrusive::bstree::rebalance |
491 | void rebalance(); |
492 | |
493 | //! @copydoc ::boost::intrusive::bstree::rebalance_subtree |
494 | iterator rebalance_subtree(iterator root); |
495 | |
496 | friend bool operator< (const splaytree_impl &x, const splaytree_impl &y); |
497 | |
498 | friend bool operator==(const splaytree_impl &x, const splaytree_impl &y); |
499 | |
500 | friend bool operator!= (const splaytree_impl &x, const splaytree_impl &y); |
501 | |
502 | friend bool operator>(const splaytree_impl &x, const splaytree_impl &y); |
503 | |
504 | friend bool operator<=(const splaytree_impl &x, const splaytree_impl &y); |
505 | |
506 | friend bool operator>=(const splaytree_impl &x, const splaytree_impl &y); |
507 | |
508 | friend void swap(splaytree_impl &x, splaytree_impl &y); |
509 | |
510 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
511 | }; |
512 | |
513 | //! Helper metafunction to define a \c splaytree that yields to the same type when the |
514 | //! same options (either explicitly or implicitly) are used. |
515 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
516 | template<class T, class ...Options> |
517 | #else |
518 | template<class T, class O1 = void, class O2 = void |
519 | , class O3 = void, class O4 = void |
520 | , class O5 = void, class O6 = void> |
521 | #endif |
522 | struct make_splaytree |
523 | { |
524 | /// @cond |
525 | typedef typename pack_options |
526 | < splaytree_defaults, |
527 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
528 | O1, O2, O3, O4, O5, O6 |
529 | #else |
530 | Options... |
531 | #endif |
532 | >::type packed_options; |
533 | |
534 | typedef typename detail::get_value_traits |
535 | <T, typename packed_options::proto_value_traits>::type value_traits; |
536 | |
537 | typedef splaytree_impl |
538 | < value_traits |
539 | , typename packed_options::key_of_value |
540 | , typename packed_options::compare |
541 | , typename packed_options::size_type |
542 | , packed_options::constant_time_size |
543 | , typename packed_options::header_holder_type |
544 | > implementation_defined; |
545 | /// @endcond |
546 | typedef implementation_defined type; |
547 | }; |
548 | |
549 | |
550 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
551 | |
552 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
553 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> |
554 | #else |
555 | template<class T, class ...Options> |
556 | #endif |
557 | class splaytree |
558 | : public make_splaytree<T, |
559 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
560 | O1, O2, O3, O4, O5, O6 |
561 | #else |
562 | Options... |
563 | #endif |
564 | >::type |
565 | { |
566 | typedef typename make_splaytree |
567 | <T, |
568 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
569 | O1, O2, O3, O4, O5, O6 |
570 | #else |
571 | Options... |
572 | #endif |
573 | >::type Base; |
574 | BOOST_MOVABLE_BUT_NOT_COPYABLE(splaytree) |
575 | |
576 | public: |
577 | typedef typename Base::key_compare key_compare; |
578 | typedef typename Base::value_traits value_traits; |
579 | typedef typename Base::iterator iterator; |
580 | typedef typename Base::const_iterator const_iterator; |
581 | typedef typename Base::reverse_iterator reverse_iterator; |
582 | typedef typename Base::const_reverse_iterator const_reverse_iterator; |
583 | |
584 | //Assert if passed value traits are compatible with the type |
585 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); |
586 | |
587 | explicit splaytree( const key_compare &cmp = key_compare() |
588 | , const value_traits &v_traits = value_traits()) |
589 | : Base(cmp, v_traits) |
590 | {} |
591 | |
592 | template<class Iterator> |
593 | splaytree( bool unique, Iterator b, Iterator e |
594 | , const key_compare &cmp = key_compare() |
595 | , const value_traits &v_traits = value_traits()) |
596 | : Base(unique, b, e, cmp, v_traits) |
597 | {} |
598 | |
599 | splaytree(BOOST_RV_REF(splaytree) x) |
600 | : Base(BOOST_MOVE_BASE(Base, x)) |
601 | {} |
602 | |
603 | splaytree& operator=(BOOST_RV_REF(splaytree) x) |
604 | { return static_cast<splaytree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } |
605 | |
606 | template <class Cloner, class Disposer> |
607 | void clone_from(const splaytree &src, Cloner cloner, Disposer disposer) |
608 | { Base::clone_from(src, cloner, disposer); } |
609 | |
610 | template <class Cloner, class Disposer> |
611 | void clone_from(BOOST_RV_REF(splaytree) src, Cloner cloner, Disposer disposer) |
612 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } |
613 | |
614 | static splaytree &container_from_end_iterator(iterator end_iterator) |
615 | { return static_cast<splaytree &>(Base::container_from_end_iterator(end_iterator)); } |
616 | |
617 | static const splaytree &container_from_end_iterator(const_iterator end_iterator) |
618 | { return static_cast<const splaytree &>(Base::container_from_end_iterator(end_iterator)); } |
619 | |
620 | static splaytree &container_from_iterator(iterator it) |
621 | { return static_cast<splaytree &>(Base::container_from_iterator(it)); } |
622 | |
623 | static const splaytree &container_from_iterator(const_iterator it) |
624 | { return static_cast<const splaytree &>(Base::container_from_iterator(it)); } |
625 | }; |
626 | |
627 | #endif |
628 | |
629 | } //namespace intrusive |
630 | } //namespace boost |
631 | |
632 | #include <boost/intrusive/detail/config_end.hpp> |
633 | |
634 | #endif //BOOST_INTRUSIVE_SPLAYTREE_HPP |
635 | |