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

source code of boost/libs/intrusive/include/boost/intrusive/splaytree.hpp