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