]>
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_SPLAY_SET_HPP | |
13 | #define BOOST_INTRUSIVE_SPLAY_SET_HPP | |
14 | ||
15 | #include <boost/intrusive/detail/config_begin.hpp> | |
16 | #include <boost/intrusive/intrusive_fwd.hpp> | |
17 | #include <boost/intrusive/splaytree.hpp> | |
18 | #include <boost/intrusive/detail/mpl.hpp> | |
19 | #include <boost/move/utility_core.hpp> | |
20 | #include <boost/static_assert.hpp> | |
21 | ||
22 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
23 | # pragma once | |
24 | #endif | |
25 | ||
26 | #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
27 | template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder> | |
28 | class splay_multiset_impl; | |
29 | #endif | |
30 | ||
31 | namespace boost { | |
32 | namespace intrusive { | |
33 | ||
34 | //! The class template splay_set is an intrusive container, that mimics most of | |
35 | //! the interface of std::set as described in the C++ standard. | |
36 | //! | |
37 | //! The template parameter \c T is the type to be managed by the container. | |
38 | //! The user can specify additional options and if no options are provided | |
39 | //! default options are used. | |
40 | //! | |
41 | //! The container supports the following options: | |
42 | //! \c base_hook<>/member_hook<>/value_traits<>, | |
43 | //! \c constant_time_size<>, \c size_type<> and | |
44 | //! \c compare<>. | |
45 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
46 | template<class T, class ...Options> | |
47 | #else | |
48 | template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder> | |
49 | #endif | |
50 | class splay_set_impl | |
51 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
52 | : public splaytree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, HeaderHolder> | |
53 | #endif | |
54 | { | |
55 | /// @cond | |
56 | typedef splaytree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, HeaderHolder> tree_type; | |
57 | BOOST_MOVABLE_BUT_NOT_COPYABLE(splay_set_impl) | |
58 | ||
59 | typedef tree_type implementation_defined; | |
60 | /// @endcond | |
61 | ||
62 | public: | |
63 | typedef typename implementation_defined::value_type value_type; | |
64 | typedef typename implementation_defined::key_type key_type; | |
65 | typedef typename implementation_defined::key_of_value key_of_value; | |
66 | typedef typename implementation_defined::value_traits value_traits; | |
67 | typedef typename implementation_defined::pointer pointer; | |
68 | typedef typename implementation_defined::const_pointer const_pointer; | |
69 | typedef typename implementation_defined::reference reference; | |
70 | typedef typename implementation_defined::const_reference const_reference; | |
71 | typedef typename implementation_defined::difference_type difference_type; | |
72 | typedef typename implementation_defined::size_type size_type; | |
73 | typedef typename implementation_defined::value_compare value_compare; | |
74 | typedef typename implementation_defined::key_compare key_compare; | |
75 | typedef typename implementation_defined::iterator iterator; | |
76 | typedef typename implementation_defined::const_iterator const_iterator; | |
77 | typedef typename implementation_defined::reverse_iterator reverse_iterator; | |
78 | typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; | |
79 | typedef typename implementation_defined::insert_commit_data insert_commit_data; | |
80 | typedef typename implementation_defined::node_traits node_traits; | |
81 | typedef typename implementation_defined::node node; | |
82 | typedef typename implementation_defined::node_ptr node_ptr; | |
83 | typedef typename implementation_defined::const_node_ptr const_node_ptr; | |
84 | typedef typename implementation_defined::node_algorithms node_algorithms; | |
85 | ||
86 | static const bool constant_time_size = tree_type::constant_time_size; | |
87 | ||
88 | public: | |
89 | //! @copydoc ::boost::intrusive::splaytree::splaytree() | |
90 | splay_set_impl() | |
91 | : tree_type() | |
92 | {} | |
93 | ||
94 | //! @copydoc ::boost::intrusive::splaytree::splaytree(const key_compare &,const value_traits &) | |
95 | explicit splay_set_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) | |
96 | : tree_type(cmp, v_traits) | |
97 | {} | |
98 | ||
99 | //! @copydoc ::boost::intrusive::splaytree::splaytree(bool,Iterator,Iterator,const key_compare &,const value_traits &) | |
100 | template<class Iterator> | |
101 | splay_set_impl( Iterator b, Iterator e | |
102 | , const key_compare &cmp = key_compare() | |
103 | , const value_traits &v_traits = value_traits()) | |
104 | : tree_type(true, b, e, cmp, v_traits) | |
105 | {} | |
106 | ||
107 | //! @copydoc ::boost::intrusive::splaytree::splaytree(splaytree &&) | |
108 | splay_set_impl(BOOST_RV_REF(splay_set_impl) x) | |
109 | : tree_type(BOOST_MOVE_BASE(tree_type, x)) | |
110 | {} | |
111 | ||
112 | //! @copydoc ::boost::intrusive::splaytree::operator=(splaytree &&) | |
113 | splay_set_impl& operator=(BOOST_RV_REF(splay_set_impl) x) | |
114 | { return static_cast<splay_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } | |
115 | ||
116 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
117 | //! @copydoc ::boost::intrusive::splaytree::~splaytree() | |
118 | ~splay_set_impl(); | |
119 | ||
120 | //! @copydoc ::boost::intrusive::splaytree::begin() | |
121 | iterator begin(); | |
122 | ||
123 | //! @copydoc ::boost::intrusive::splaytree::begin()const | |
124 | const_iterator begin() const; | |
125 | ||
126 | //! @copydoc ::boost::intrusive::splaytree::cbegin()const | |
127 | const_iterator cbegin() const; | |
128 | ||
129 | //! @copydoc ::boost::intrusive::splaytree::end() | |
130 | iterator end(); | |
131 | ||
132 | //! @copydoc ::boost::intrusive::splaytree::end()const | |
133 | const_iterator end() const; | |
134 | ||
135 | //! @copydoc ::boost::intrusive::splaytree::cend()const | |
136 | const_iterator cend() const; | |
137 | ||
138 | //! @copydoc ::boost::intrusive::splaytree::rbegin() | |
139 | reverse_iterator rbegin(); | |
140 | ||
141 | //! @copydoc ::boost::intrusive::splaytree::rbegin()const | |
142 | const_reverse_iterator rbegin() const; | |
143 | ||
144 | //! @copydoc ::boost::intrusive::splaytree::crbegin()const | |
145 | const_reverse_iterator crbegin() const; | |
146 | ||
147 | //! @copydoc ::boost::intrusive::splaytree::rend() | |
148 | reverse_iterator rend(); | |
149 | ||
150 | //! @copydoc ::boost::intrusive::splaytree::rend()const | |
151 | const_reverse_iterator rend() const; | |
152 | ||
153 | //! @copydoc ::boost::intrusive::splaytree::crend()const | |
154 | const_reverse_iterator crend() const; | |
155 | ||
156 | //! @copydoc ::boost::intrusive::splaytree::root() | |
157 | iterator root(); | |
158 | ||
159 | //! @copydoc ::boost::intrusive::splaytree::root()const | |
160 | const_iterator root() const; | |
161 | ||
162 | //! @copydoc ::boost::intrusive::splaytree::croot()const | |
163 | const_iterator croot() const; | |
164 | ||
165 | //! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(iterator) | |
166 | static splay_set_impl &container_from_end_iterator(iterator end_iterator); | |
167 | ||
168 | //! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(const_iterator) | |
169 | static const splay_set_impl &container_from_end_iterator(const_iterator end_iterator); | |
170 | ||
171 | //! @copydoc ::boost::intrusive::splaytree::container_from_iterator(iterator) | |
172 | static splay_set_impl &container_from_iterator(iterator it); | |
173 | ||
174 | //! @copydoc ::boost::intrusive::splaytree::container_from_iterator(const_iterator) | |
175 | static const splay_set_impl &container_from_iterator(const_iterator it); | |
176 | ||
177 | //! @copydoc ::boost::intrusive::splaytree::key_comp()const | |
178 | key_compare key_comp() const; | |
179 | ||
180 | //! @copydoc ::boost::intrusive::splaytree::value_comp()const | |
181 | value_compare value_comp() const; | |
182 | ||
183 | //! @copydoc ::boost::intrusive::splaytree::empty()const | |
184 | bool empty() const; | |
185 | ||
186 | //! @copydoc ::boost::intrusive::splaytree::size()const | |
187 | size_type size() const; | |
188 | ||
189 | //! @copydoc ::boost::intrusive::splaytree::swap | |
190 | void swap(splay_set_impl& other); | |
191 | ||
192 | //! @copydoc ::boost::intrusive::splaytree::clone_from(const splaytree&,Cloner,Disposer) | |
193 | template <class Cloner, class Disposer> | |
194 | void clone_from(const splay_set_impl &src, Cloner cloner, Disposer disposer); | |
195 | ||
196 | #else | |
197 | ||
198 | using tree_type::clone_from; | |
199 | ||
200 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
201 | ||
202 | //! @copydoc ::boost::intrusive::splaytree::clone_from(splaytree&&,Cloner,Disposer) | |
203 | template <class Cloner, class Disposer> | |
204 | void clone_from(BOOST_RV_REF(splay_set_impl) src, Cloner cloner, Disposer disposer) | |
205 | { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } | |
206 | ||
207 | //! @copydoc ::boost::intrusive::splaytree::insert_unique(reference) | |
208 | std::pair<iterator, bool> insert(reference value) | |
209 | { return tree_type::insert_unique(value); } | |
210 | ||
211 | //! @copydoc ::boost::intrusive::splaytree::insert_unique(const_iterator,reference) | |
212 | iterator insert(const_iterator hint, reference value) | |
213 | { return tree_type::insert_unique(hint, value); } | |
214 | ||
215 | //! @copydoc ::boost::intrusive::rbtree::insert_unique_check(const key_type&,insert_commit_data&) | |
216 | std::pair<iterator, bool> insert_check | |
217 | (const key_type &key, insert_commit_data &commit_data) | |
218 | { return tree_type::insert_unique_check(key, commit_data); } | |
219 | ||
220 | //! @copydoc ::boost::intrusive::rbtree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&) | |
221 | std::pair<iterator, bool> insert_check | |
222 | (const_iterator hint, const key_type &key | |
223 | ,insert_commit_data &commit_data) | |
224 | { return tree_type::insert_unique_check(hint, key, commit_data); } | |
225 | ||
226 | //! @copydoc ::boost::intrusive::splaytree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) | |
227 | template<class KeyType, class KeyTypeKeyCompare> | |
228 | std::pair<iterator, bool> insert_check | |
229 | (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data) | |
230 | { return tree_type::insert_unique_check(key, comp, commit_data); } | |
231 | ||
232 | //! @copydoc ::boost::intrusive::splaytree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) | |
233 | template<class KeyType, class KeyTypeKeyCompare> | |
234 | std::pair<iterator, bool> insert_check | |
235 | (const_iterator hint, const KeyType &key | |
236 | ,KeyTypeKeyCompare comp, insert_commit_data &commit_data) | |
237 | { return tree_type::insert_unique_check(hint, key, comp, commit_data); } | |
238 | ||
239 | //! @copydoc ::boost::intrusive::splaytree::insert_unique(Iterator,Iterator) | |
240 | template<class Iterator> | |
241 | void insert(Iterator b, Iterator e) | |
242 | { tree_type::insert_unique(b, e); } | |
243 | ||
244 | //! @copydoc ::boost::intrusive::splaytree::insert_unique_commit | |
245 | iterator insert_commit(reference value, const insert_commit_data &commit_data) | |
246 | { return tree_type::insert_unique_commit(value, commit_data); } | |
247 | ||
248 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
249 | //! @copydoc ::boost::intrusive::splaytree::insert_before | |
250 | iterator insert_before(const_iterator pos, reference value); | |
251 | ||
252 | //! @copydoc ::boost::intrusive::splaytree::push_back | |
253 | void push_back(reference value); | |
254 | ||
255 | //! @copydoc ::boost::intrusive::splaytree::push_front | |
256 | void push_front(reference value); | |
257 | ||
258 | //! @copydoc ::boost::intrusive::splaytree::erase(const_iterator) | |
259 | iterator erase(const_iterator i); | |
260 | ||
261 | //! @copydoc ::boost::intrusive::splaytree::erase(const_iterator,const_iterator) | |
262 | iterator erase(const_iterator b, const_iterator e); | |
263 | ||
264 | //! @copydoc ::boost::intrusive::splaytree::erase(const key_type &) | |
265 | size_type erase(const key_type &key); | |
266 | ||
267 | //! @copydoc ::boost::intrusive::splaytree::erase(const KeyType&,KeyTypeKeyCompare) | |
268 | template<class KeyType, class KeyTypeKeyCompare> | |
269 | size_type erase(const KeyType& key, KeyTypeKeyCompare comp); | |
270 | ||
271 | //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const_iterator,Disposer) | |
272 | template<class Disposer> | |
273 | iterator erase_and_dispose(const_iterator i, Disposer disposer); | |
274 | ||
275 | //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const_iterator,const_iterator,Disposer) | |
276 | template<class Disposer> | |
277 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); | |
278 | ||
279 | //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const key_type &, Disposer) | |
280 | template<class Disposer> | |
281 | size_type erase_and_dispose(const key_type &key, Disposer disposer); | |
282 | ||
283 | //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) | |
284 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> | |
285 | size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); | |
286 | ||
287 | //! @copydoc ::boost::intrusive::splaytree::clear | |
288 | void clear(); | |
289 | ||
290 | //! @copydoc ::boost::intrusive::splaytree::clear_and_dispose | |
291 | template<class Disposer> | |
292 | void clear_and_dispose(Disposer disposer); | |
293 | ||
294 | #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
295 | ||
296 | //! @copydoc ::boost::intrusive::splaytree::count(const key_type &)const | |
297 | size_type count(const key_type &key) const | |
298 | { return static_cast<size_type>(this->tree_type::find(key) != this->tree_type::cend()); } | |
299 | ||
300 | //! @copydoc ::boost::intrusive::splaytree::count(const KeyType&,KeyTypeKeyCompare)const | |
301 | template<class KeyType, class KeyTypeKeyCompare> | |
302 | size_type count(const KeyType& key, KeyTypeKeyCompare comp) const | |
303 | { return static_cast<size_type>(this->tree_type::find(key, comp) != this->tree_type::cend()); } | |
304 | ||
305 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
306 | ||
307 | //! @copydoc ::boost::intrusive::splaytree::count(const key_type &)const | |
308 | size_type count(const key_type &key) const; | |
309 | ||
310 | //! @copydoc ::boost::intrusive::splaytree::count(const KeyType&,KeyTypeKeyCompare)const | |
311 | template<class KeyType, class KeyTypeKeyCompare> | |
312 | size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; | |
313 | ||
314 | //! @copydoc ::boost::intrusive::splaytree::lower_bound(const key_type &) | |
315 | iterator lower_bound(const key_type &key); | |
316 | ||
317 | //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyTypeKeyCompare) | |
318 | template<class KeyType, class KeyTypeKeyCompare> | |
319 | iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); | |
320 | ||
321 | //! @copydoc ::boost::intrusive::splaytree::lower_bound(const key_type &)const | |
322 | const_iterator lower_bound(const key_type &key) const; | |
323 | ||
324 | //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyTypeKeyCompare)const | |
325 | template<class KeyType, class KeyTypeKeyCompare> | |
326 | const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; | |
327 | ||
328 | //! @copydoc ::boost::intrusive::splaytree::upper_bound(const key_type &) | |
329 | iterator upper_bound(const key_type &key); | |
330 | ||
331 | //! @copydoc ::boost::intrusive::splaytree::upper_bound(const KeyType&,KeyTypeKeyCompare) | |
332 | template<class KeyType, class KeyTypeKeyCompare> | |
333 | iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); | |
334 | ||
335 | //! @copydoc ::boost::intrusive::splaytree::upper_bound(const key_type &)const | |
336 | const_iterator upper_bound(const key_type &key) const; | |
337 | ||
338 | //! @copydoc ::boost::intrusive::splaytree::upper_bound(const KeyType&,KeyTypeKeyCompare)const | |
339 | template<class KeyType, class KeyTypeKeyCompare> | |
340 | const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; | |
341 | ||
342 | //! @copydoc ::boost::intrusive::splaytree::find(const key_type &) | |
343 | iterator find(const key_type &key); | |
344 | ||
345 | //! @copydoc ::boost::intrusive::splaytree::find(const KeyType&,KeyTypeKeyCompare) | |
346 | template<class KeyType, class KeyTypeKeyCompare> | |
347 | iterator find(const KeyType& key, KeyTypeKeyCompare comp); | |
348 | ||
349 | //! @copydoc ::boost::intrusive::splaytree::find(const key_type &)const | |
350 | const_iterator find(const key_type &key) const; | |
351 | ||
352 | //! @copydoc ::boost::intrusive::splaytree::find(const KeyType&,KeyTypeKeyCompare)const | |
353 | template<class KeyType, class KeyTypeKeyCompare> | |
354 | const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; | |
355 | ||
356 | #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
357 | ||
358 | //! @copydoc ::boost::intrusive::rbtree::equal_range(const key_type &) | |
359 | std::pair<iterator,iterator> equal_range(const key_type &key) | |
360 | { return this->tree_type::lower_bound_range(key); } | |
361 | ||
362 | //! @copydoc ::boost::intrusive::rbtree::equal_range(const KeyType&,KeyTypeKeyCompare) | |
363 | template<class KeyType, class KeyTypeKeyCompare> | |
364 | std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp) | |
365 | { return this->tree_type::equal_range(key, comp); } | |
366 | ||
367 | //! @copydoc ::boost::intrusive::rbtree::equal_range(const key_type &)const | |
368 | std::pair<const_iterator, const_iterator> | |
369 | equal_range(const key_type &key) const | |
370 | { return this->tree_type::lower_bound_range(key); } | |
371 | ||
372 | //! @copydoc ::boost::intrusive::rbtree::equal_range(const KeyType&,KeyTypeKeyCompare)const | |
373 | template<class KeyType, class KeyTypeKeyCompare> | |
374 | std::pair<const_iterator, const_iterator> | |
375 | equal_range(const KeyType& key, KeyTypeKeyCompare comp) const | |
376 | { return this->tree_type::equal_range(key, comp); } | |
377 | ||
378 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
379 | ||
380 | //! @copydoc ::boost::intrusive::splaytree::bounded_range(const key_type&,const key_type&,bool,bool) | |
381 | std::pair<iterator,iterator> bounded_range | |
382 | (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed); | |
383 | ||
384 | //! @copydoc ::boost::intrusive::splaytree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) | |
385 | template<class KeyType, class KeyTypeKeyCompare> | |
386 | std::pair<iterator,iterator> bounded_range | |
387 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); | |
388 | ||
389 | //! @copydoc ::boost::intrusive::splaytree::bounded_range(const key_type&,const key_type&,bool,bool)const | |
390 | std::pair<const_iterator, const_iterator> bounded_range | |
391 | (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; | |
392 | ||
393 | //! @copydoc ::boost::intrusive::splaytree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const | |
394 | template<class KeyType, class KeyTypeKeyCompare> | |
395 | std::pair<const_iterator, const_iterator> bounded_range | |
396 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; | |
397 | ||
398 | //! @copydoc ::boost::intrusive::splaytree::s_iterator_to(reference) | |
399 | static iterator s_iterator_to(reference value); | |
400 | ||
401 | //! @copydoc ::boost::intrusive::splaytree::s_iterator_to(const_reference) | |
402 | static const_iterator s_iterator_to(const_reference value); | |
403 | ||
404 | //! @copydoc ::boost::intrusive::splaytree::iterator_to(reference) | |
405 | iterator iterator_to(reference value); | |
406 | ||
407 | //! @copydoc ::boost::intrusive::splaytree::iterator_to(const_reference)const | |
408 | const_iterator iterator_to(const_reference value) const; | |
409 | ||
410 | //! @copydoc ::boost::intrusive::splaytree::init_node(reference) | |
411 | static void init_node(reference value); | |
412 | ||
413 | //! @copydoc ::boost::intrusive::splaytree::unlink_leftmost_without_rebalance | |
414 | pointer unlink_leftmost_without_rebalance(); | |
415 | ||
416 | //! @copydoc ::boost::intrusive::splaytree::replace_node | |
417 | void replace_node(iterator replace_this, reference with_this); | |
418 | ||
419 | //! @copydoc ::boost::intrusive::splaytree::remove_node | |
420 | void remove_node(reference value); | |
421 | ||
422 | //! @copydoc ::boost::intrusive::splaytree::splay_up(iterator) | |
423 | void splay_up(iterator i); | |
424 | ||
425 | //! @copydoc ::boost::intrusive::splaytree::splay_down(const KeyType&,KeyTypeKeyCompare) | |
426 | template<class KeyType, class KeyTypeKeyCompare> | |
427 | iterator splay_down(const KeyType &key, KeyTypeKeyCompare comp); | |
428 | ||
429 | //! @copydoc ::boost::intrusive::splaytree::splay_down(const key_type &key) | |
430 | iterator splay_down(const key_type &key); | |
431 | ||
432 | //! @copydoc ::boost::intrusive::splaytree::rebalance | |
433 | void rebalance(); | |
434 | ||
435 | //! @copydoc ::boost::intrusive::splaytree::rebalance_subtree | |
436 | iterator rebalance_subtree(iterator root); | |
437 | ||
438 | //! @copydoc ::boost::intrusive::splaytree::merge_unique | |
439 | template<class ...Options2> | |
440 | void merge(splay_set<T, Options2...> &source); | |
441 | ||
442 | //! @copydoc ::boost::intrusive::splaytree::merge_unique | |
443 | template<class ...Options2> | |
444 | void merge(splay_multiset<T, Options2...> &source); | |
445 | ||
446 | #else | |
447 | ||
448 | template<class Compare2> | |
449 | void merge(splay_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source) | |
450 | { return tree_type::merge_unique(source); } | |
451 | ||
452 | ||
453 | template<class Compare2> | |
454 | void merge(splay_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source) | |
455 | { return tree_type::merge_unique(source); } | |
456 | ||
457 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
458 | }; | |
459 | ||
460 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
461 | ||
462 | template<class T, class ...Options> | |
463 | bool operator!= (const splay_set_impl<T, Options...> &x, const splay_set_impl<T, Options...> &y); | |
464 | ||
465 | template<class T, class ...Options> | |
466 | bool operator>(const splay_set_impl<T, Options...> &x, const splay_set_impl<T, Options...> &y); | |
467 | ||
468 | template<class T, class ...Options> | |
469 | bool operator<=(const splay_set_impl<T, Options...> &x, const splay_set_impl<T, Options...> &y); | |
470 | ||
471 | template<class T, class ...Options> | |
472 | bool operator>=(const splay_set_impl<T, Options...> &x, const splay_set_impl<T, Options...> &y); | |
473 | ||
474 | template<class T, class ...Options> | |
475 | void swap(splay_set_impl<T, Options...> &x, splay_set_impl<T, Options...> &y); | |
476 | ||
477 | #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
478 | ||
479 | //! Helper metafunction to define a \c splay_set that yields to the same type when the | |
480 | //! same options (either explicitly or implicitly) are used. | |
481 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
482 | template<class T, class ...Options> | |
483 | #else | |
484 | template<class T, class O1 = void, class O2 = void | |
485 | , class O3 = void, class O4 = void | |
486 | , class O5 = void, class O6 = void> | |
487 | #endif | |
488 | struct make_splay_set | |
489 | { | |
490 | /// @cond | |
491 | typedef typename pack_options | |
492 | < splaytree_defaults, | |
493 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
494 | O1, O2, O3, O4, O5, O6 | |
495 | #else | |
496 | Options... | |
497 | #endif | |
498 | >::type packed_options; | |
499 | ||
500 | typedef typename detail::get_value_traits | |
501 | <T, typename packed_options::proto_value_traits>::type value_traits; | |
502 | ||
503 | typedef splay_set_impl | |
504 | < value_traits | |
505 | , typename packed_options::key_of_value | |
506 | , typename packed_options::compare | |
507 | , typename packed_options::size_type | |
508 | , packed_options::constant_time_size | |
509 | , typename packed_options::header_holder_type | |
510 | > implementation_defined; | |
511 | /// @endcond | |
512 | typedef implementation_defined type; | |
513 | }; | |
514 | ||
515 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
516 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
517 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> | |
518 | #else | |
519 | template<class T, class ...Options> | |
520 | #endif | |
521 | class splay_set | |
522 | : public make_splay_set<T, | |
523 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
524 | O1, O2, O3, O4, O5, O6 | |
525 | #else | |
526 | Options... | |
527 | #endif | |
528 | >::type | |
529 | { | |
530 | typedef typename make_splay_set | |
531 | <T, | |
532 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
533 | O1, O2, O3, O4, O5, O6 | |
534 | #else | |
535 | Options... | |
536 | #endif | |
537 | >::type Base; | |
538 | ||
539 | BOOST_MOVABLE_BUT_NOT_COPYABLE(splay_set) | |
540 | public: | |
541 | typedef typename Base::key_compare key_compare; | |
542 | typedef typename Base::value_traits value_traits; | |
543 | typedef typename Base::iterator iterator; | |
544 | typedef typename Base::const_iterator const_iterator; | |
545 | ||
546 | //Assert if passed value traits are compatible with the type | |
547 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); | |
548 | ||
549 | splay_set() | |
550 | : Base() | |
551 | {} | |
552 | ||
553 | explicit splay_set( const key_compare &cmp, const value_traits &v_traits = value_traits()) | |
554 | : Base(cmp, v_traits) | |
555 | {} | |
556 | ||
557 | template<class Iterator> | |
558 | splay_set( Iterator b, Iterator e | |
559 | , const key_compare &cmp = key_compare() | |
560 | , const value_traits &v_traits = value_traits()) | |
561 | : Base(b, e, cmp, v_traits) | |
562 | {} | |
563 | ||
564 | splay_set(BOOST_RV_REF(splay_set) x) | |
565 | : Base(::boost::move(static_cast<Base&>(x))) | |
566 | {} | |
567 | ||
568 | splay_set& operator=(BOOST_RV_REF(splay_set) x) | |
569 | { return static_cast<splay_set &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } | |
570 | ||
571 | template <class Cloner, class Disposer> | |
572 | void clone_from(const splay_set &src, Cloner cloner, Disposer disposer) | |
573 | { Base::clone_from(src, cloner, disposer); } | |
574 | ||
575 | template <class Cloner, class Disposer> | |
576 | void clone_from(BOOST_RV_REF(splay_set) src, Cloner cloner, Disposer disposer) | |
577 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } | |
578 | ||
579 | static splay_set &container_from_end_iterator(iterator end_iterator) | |
580 | { return static_cast<splay_set &>(Base::container_from_end_iterator(end_iterator)); } | |
581 | ||
582 | static const splay_set &container_from_end_iterator(const_iterator end_iterator) | |
583 | { return static_cast<const splay_set &>(Base::container_from_end_iterator(end_iterator)); } | |
584 | ||
585 | static splay_set &container_from_iterator(iterator it) | |
586 | { return static_cast<splay_set &>(Base::container_from_iterator(it)); } | |
587 | ||
588 | static const splay_set &container_from_iterator(const_iterator it) | |
589 | { return static_cast<const splay_set &>(Base::container_from_iterator(it)); } | |
590 | }; | |
591 | ||
592 | #endif | |
593 | ||
594 | //! The class template splay_multiset is an intrusive container, that mimics most of | |
595 | //! the interface of std::multiset as described in the C++ standard. | |
596 | //! | |
597 | //! The template parameter \c T is the type to be managed by the container. | |
598 | //! The user can specify additional options and if no options are provided | |
599 | //! default options are used. | |
600 | //! | |
601 | //! The container supports the following options: | |
602 | //! \c base_hook<>/member_hook<>/value_traits<>, | |
603 | //! \c constant_time_size<>, \c size_type<> and | |
604 | //! \c compare<>. | |
605 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
606 | template<class T, class ...Options> | |
607 | #else | |
608 | template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder> | |
609 | #endif | |
610 | class splay_multiset_impl | |
611 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
612 | : public splaytree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, HeaderHolder> | |
613 | #endif | |
614 | { | |
615 | /// @cond | |
616 | typedef splaytree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, HeaderHolder> tree_type; | |
617 | ||
618 | BOOST_MOVABLE_BUT_NOT_COPYABLE(splay_multiset_impl) | |
619 | typedef tree_type implementation_defined; | |
620 | /// @endcond | |
621 | ||
622 | public: | |
623 | typedef typename implementation_defined::value_type value_type; | |
624 | typedef typename implementation_defined::key_type key_type; | |
625 | typedef typename implementation_defined::key_of_value key_of_value; | |
626 | typedef typename implementation_defined::value_traits value_traits; | |
627 | typedef typename implementation_defined::pointer pointer; | |
628 | typedef typename implementation_defined::const_pointer const_pointer; | |
629 | typedef typename implementation_defined::reference reference; | |
630 | typedef typename implementation_defined::const_reference const_reference; | |
631 | typedef typename implementation_defined::difference_type difference_type; | |
632 | typedef typename implementation_defined::size_type size_type; | |
633 | typedef typename implementation_defined::value_compare value_compare; | |
634 | typedef typename implementation_defined::key_compare key_compare; | |
635 | typedef typename implementation_defined::iterator iterator; | |
636 | typedef typename implementation_defined::const_iterator const_iterator; | |
637 | typedef typename implementation_defined::reverse_iterator reverse_iterator; | |
638 | typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; | |
639 | typedef typename implementation_defined::insert_commit_data insert_commit_data; | |
640 | typedef typename implementation_defined::node_traits node_traits; | |
641 | typedef typename implementation_defined::node node; | |
642 | typedef typename implementation_defined::node_ptr node_ptr; | |
643 | typedef typename implementation_defined::const_node_ptr const_node_ptr; | |
644 | typedef typename implementation_defined::node_algorithms node_algorithms; | |
645 | ||
646 | static const bool constant_time_size = tree_type::constant_time_size; | |
647 | ||
648 | public: | |
649 | //! @copydoc ::boost::intrusive::splaytree::splaytree() | |
650 | splay_multiset_impl() | |
651 | : tree_type() | |
652 | {} | |
653 | ||
654 | //! @copydoc ::boost::intrusive::splaytree::splaytree(const key_compare &,const value_traits &) | |
655 | explicit splay_multiset_impl(const key_compare &cmp, const value_traits &v_traits = value_traits()) | |
656 | : tree_type(cmp, v_traits) | |
657 | {} | |
658 | ||
659 | //! @copydoc ::boost::intrusive::splaytree::splaytree(bool,Iterator,Iterator,const key_compare &,const value_traits &) | |
660 | template<class Iterator> | |
661 | splay_multiset_impl( Iterator b, Iterator e | |
662 | , const key_compare &cmp = key_compare() | |
663 | , const value_traits &v_traits = value_traits()) | |
664 | : tree_type(false, b, e, cmp, v_traits) | |
665 | {} | |
666 | ||
667 | //! @copydoc ::boost::intrusive::splaytree::splaytree(splaytree &&) | |
668 | splay_multiset_impl(BOOST_RV_REF(splay_multiset_impl) x) | |
669 | : tree_type(::boost::move(static_cast<tree_type&>(x))) | |
670 | {} | |
671 | ||
672 | //! @copydoc ::boost::intrusive::splaytree::operator=(splaytree &&) | |
673 | splay_multiset_impl& operator=(BOOST_RV_REF(splay_multiset_impl) x) | |
674 | { return static_cast<splay_multiset_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } | |
675 | ||
676 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
677 | //! @copydoc ::boost::intrusive::splaytree::~splaytree() | |
678 | ~splay_multiset_impl(); | |
679 | ||
680 | //! @copydoc ::boost::intrusive::splaytree::begin() | |
681 | iterator begin(); | |
682 | ||
683 | //! @copydoc ::boost::intrusive::splaytree::begin()const | |
684 | const_iterator begin() const; | |
685 | ||
686 | //! @copydoc ::boost::intrusive::splaytree::cbegin()const | |
687 | const_iterator cbegin() const; | |
688 | ||
689 | //! @copydoc ::boost::intrusive::splaytree::end() | |
690 | iterator end(); | |
691 | ||
692 | //! @copydoc ::boost::intrusive::splaytree::end()const | |
693 | const_iterator end() const; | |
694 | ||
695 | //! @copydoc ::boost::intrusive::splaytree::cend()const | |
696 | const_iterator cend() const; | |
697 | ||
698 | //! @copydoc ::boost::intrusive::splaytree::rbegin() | |
699 | reverse_iterator rbegin(); | |
700 | ||
701 | //! @copydoc ::boost::intrusive::splaytree::rbegin()const | |
702 | const_reverse_iterator rbegin() const; | |
703 | ||
704 | //! @copydoc ::boost::intrusive::splaytree::crbegin()const | |
705 | const_reverse_iterator crbegin() const; | |
706 | ||
707 | //! @copydoc ::boost::intrusive::splaytree::rend() | |
708 | reverse_iterator rend(); | |
709 | ||
710 | //! @copydoc ::boost::intrusive::splaytree::rend()const | |
711 | const_reverse_iterator rend() const; | |
712 | ||
713 | //! @copydoc ::boost::intrusive::splaytree::crend()const | |
714 | const_reverse_iterator crend() const; | |
715 | ||
716 | //! @copydoc ::boost::intrusive::splaytree::root() | |
717 | iterator root(); | |
718 | ||
719 | //! @copydoc ::boost::intrusive::splaytree::root()const | |
720 | const_iterator root() const; | |
721 | ||
722 | //! @copydoc ::boost::intrusive::splaytree::croot()const | |
723 | const_iterator croot() const; | |
724 | ||
725 | //! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(iterator) | |
726 | static splay_multiset_impl &container_from_end_iterator(iterator end_iterator); | |
727 | ||
728 | //! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(const_iterator) | |
729 | static const splay_multiset_impl &container_from_end_iterator(const_iterator end_iterator); | |
730 | ||
731 | //! @copydoc ::boost::intrusive::splaytree::container_from_iterator(iterator) | |
732 | static splay_multiset_impl &container_from_iterator(iterator it); | |
733 | ||
734 | //! @copydoc ::boost::intrusive::splaytree::container_from_iterator(const_iterator) | |
735 | static const splay_multiset_impl &container_from_iterator(const_iterator it); | |
736 | ||
737 | //! @copydoc ::boost::intrusive::splaytree::key_comp()const | |
738 | key_compare key_comp() const; | |
739 | ||
740 | //! @copydoc ::boost::intrusive::splaytree::value_comp()const | |
741 | value_compare value_comp() const; | |
742 | ||
743 | //! @copydoc ::boost::intrusive::splaytree::empty()const | |
744 | bool empty() const; | |
745 | ||
746 | //! @copydoc ::boost::intrusive::splaytree::size()const | |
747 | size_type size() const; | |
748 | ||
749 | //! @copydoc ::boost::intrusive::splaytree::swap | |
750 | void swap(splay_multiset_impl& other); | |
751 | ||
752 | //! @copydoc ::boost::intrusive::splaytree::clone_from(const splaytree&,Cloner,Disposer) | |
753 | template <class Cloner, class Disposer> | |
754 | void clone_from(const splay_multiset_impl &src, Cloner cloner, Disposer disposer); | |
755 | ||
756 | #else | |
757 | ||
758 | using tree_type::clone_from; | |
759 | ||
760 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
761 | ||
762 | //! @copydoc ::boost::intrusive::splaytree::clone_from(splaytree&&,Cloner,Disposer) | |
763 | template <class Cloner, class Disposer> | |
764 | void clone_from(BOOST_RV_REF(splay_multiset_impl) src, Cloner cloner, Disposer disposer) | |
765 | { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } | |
766 | ||
767 | //! @copydoc ::boost::intrusive::splaytree::insert_equal(reference) | |
768 | iterator insert(reference value) | |
769 | { return tree_type::insert_equal(value); } | |
770 | ||
771 | //! @copydoc ::boost::intrusive::splaytree::insert_equal(const_iterator,reference) | |
772 | iterator insert(const_iterator hint, reference value) | |
773 | { return tree_type::insert_equal(hint, value); } | |
774 | ||
775 | //! @copydoc ::boost::intrusive::splaytree::insert_equal(Iterator,Iterator) | |
776 | template<class Iterator> | |
777 | void insert(Iterator b, Iterator e) | |
778 | { tree_type::insert_equal(b, e); } | |
779 | ||
780 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
781 | //! @copydoc ::boost::intrusive::splaytree::insert_before | |
782 | iterator insert_before(const_iterator pos, reference value); | |
783 | ||
784 | //! @copydoc ::boost::intrusive::splaytree::push_back | |
785 | void push_back(reference value); | |
786 | ||
787 | //! @copydoc ::boost::intrusive::splaytree::push_front | |
788 | void push_front(reference value); | |
789 | ||
790 | //! @copydoc ::boost::intrusive::splaytree::erase(const_iterator) | |
791 | iterator erase(const_iterator i); | |
792 | ||
793 | //! @copydoc ::boost::intrusive::splaytree::erase(const_iterator,const_iterator) | |
794 | iterator erase(const_iterator b, const_iterator e); | |
795 | ||
796 | //! @copydoc ::boost::intrusive::splaytree::erase(const key_type&) | |
797 | size_type erase(const key_type &key); | |
798 | ||
799 | //! @copydoc ::boost::intrusive::splaytree::erase(const KeyType&,KeyTypeKeyCompare) | |
800 | template<class KeyType, class KeyTypeKeyCompare> | |
801 | size_type erase(const KeyType& key, KeyTypeKeyCompare comp); | |
802 | ||
803 | //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const_iterator,Disposer) | |
804 | template<class Disposer> | |
805 | iterator erase_and_dispose(const_iterator i, Disposer disposer); | |
806 | ||
807 | //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const_iterator,const_iterator,Disposer) | |
808 | template<class Disposer> | |
809 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); | |
810 | ||
811 | //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const key_type&, Disposer) | |
812 | template<class Disposer> | |
813 | size_type erase_and_dispose(const key_type &key, Disposer disposer); | |
814 | ||
815 | //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) | |
816 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> | |
817 | size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); | |
818 | ||
819 | //! @copydoc ::boost::intrusive::splaytree::clear | |
820 | void clear(); | |
821 | ||
822 | //! @copydoc ::boost::intrusive::splaytree::clear_and_dispose | |
823 | template<class Disposer> | |
824 | void clear_and_dispose(Disposer disposer); | |
825 | ||
826 | //! @copydoc ::boost::intrusive::splaytree::count(const key_type&) | |
827 | size_type count(const key_type&); | |
828 | ||
829 | //! @copydoc ::boost::intrusive::splaytree::count(const KeyType&,KeyTypeKeyCompare)const | |
830 | template<class KeyType, class KeyTypeKeyCompare> | |
831 | size_type count(const KeyType& key, KeyTypeKeyCompare comp); | |
832 | ||
833 | //! @copydoc ::boost::intrusive::splaytree::lower_bound(const key_type&) | |
834 | iterator lower_bound(const key_type &key); | |
835 | ||
836 | //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyTypeKeyCompare) | |
837 | template<class KeyType, class KeyTypeKeyCompare> | |
838 | iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); | |
839 | ||
840 | //! @copydoc ::boost::intrusive::splaytree::lower_bound(const key_type&)const | |
841 | const_iterator lower_bound(const key_type &key) const; | |
842 | ||
843 | //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyTypeKeyCompare)const | |
844 | template<class KeyType, class KeyTypeKeyCompare> | |
845 | const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; | |
846 | ||
847 | //! @copydoc ::boost::intrusive::splaytree::upper_bound(const key_type&) | |
848 | iterator upper_bound(const key_type &key); | |
849 | ||
850 | //! @copydoc ::boost::intrusive::splaytree::upper_bound(const KeyType&,KeyTypeKeyCompare) | |
851 | template<class KeyType, class KeyTypeKeyCompare> | |
852 | iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); | |
853 | ||
854 | //! @copydoc ::boost::intrusive::splaytree::upper_bound(const key_type&)const | |
855 | const_iterator upper_bound(const key_type &key) const; | |
856 | ||
857 | //! @copydoc ::boost::intrusive::splaytree::upper_bound(const KeyType&,KeyTypeKeyCompare)const | |
858 | template<class KeyType, class KeyTypeKeyCompare> | |
859 | const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; | |
860 | ||
861 | //! @copydoc ::boost::intrusive::splaytree::find(const key_type&) | |
862 | iterator find(const key_type &key); | |
863 | ||
864 | //! @copydoc ::boost::intrusive::splaytree::find(const KeyType&,KeyTypeKeyCompare) | |
865 | template<class KeyType, class KeyTypeKeyCompare> | |
866 | iterator find(const KeyType& key, KeyTypeKeyCompare comp); | |
867 | ||
868 | //! @copydoc ::boost::intrusive::splaytree::find(const key_type&)const | |
869 | const_iterator find(const key_type &key) const; | |
870 | ||
871 | //! @copydoc ::boost::intrusive::splaytree::find(const KeyType&,KeyTypeKeyCompare)const | |
872 | template<class KeyType, class KeyTypeKeyCompare> | |
873 | const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; | |
874 | ||
875 | //! @copydoc ::boost::intrusive::splaytree::equal_range(const key_type&) | |
876 | std::pair<iterator,iterator> equal_range(const key_type &key); | |
877 | ||
878 | //! @copydoc ::boost::intrusive::splaytree::equal_range(const KeyType&,KeyTypeKeyCompare) | |
879 | template<class KeyType, class KeyTypeKeyCompare> | |
880 | std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); | |
881 | ||
882 | //! @copydoc ::boost::intrusive::splaytree::equal_range(const key_type&)const | |
883 | std::pair<const_iterator, const_iterator> | |
884 | equal_range(const key_type &key) const; | |
885 | ||
886 | //! @copydoc ::boost::intrusive::splaytree::equal_range(const KeyType&,KeyTypeKeyCompare)const | |
887 | template<class KeyType, class KeyTypeKeyCompare> | |
888 | std::pair<const_iterator, const_iterator> | |
889 | equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; | |
890 | ||
891 | //! @copydoc ::boost::intrusive::splaytree::bounded_range(const key_type&, const key_type&,bool,bool) | |
892 | std::pair<iterator,iterator> bounded_range | |
893 | (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed); | |
894 | ||
895 | //! @copydoc ::boost::intrusive::splaytree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) | |
896 | template<class KeyType, class KeyTypeKeyCompare> | |
897 | std::pair<iterator,iterator> bounded_range | |
898 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); | |
899 | ||
900 | //! @copydoc ::boost::intrusive::splaytree::bounded_range(const key_type&, const key_type&,bool,bool)const | |
901 | std::pair<const_iterator, const_iterator> bounded_range | |
902 | (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const; | |
903 | ||
904 | //! @copydoc ::boost::intrusive::splaytree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const | |
905 | template<class KeyType, class KeyTypeKeyCompare> | |
906 | std::pair<const_iterator, const_iterator> bounded_range | |
907 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; | |
908 | ||
909 | //! @copydoc ::boost::intrusive::splaytree::s_iterator_to(reference) | |
910 | static iterator s_iterator_to(reference value); | |
911 | ||
912 | //! @copydoc ::boost::intrusive::splaytree::s_iterator_to(const_reference) | |
913 | static const_iterator s_iterator_to(const_reference value); | |
914 | ||
915 | //! @copydoc ::boost::intrusive::splaytree::iterator_to(reference) | |
916 | iterator iterator_to(reference value); | |
917 | ||
918 | //! @copydoc ::boost::intrusive::splaytree::iterator_to(const_reference)const | |
919 | const_iterator iterator_to(const_reference value) const; | |
920 | ||
921 | //! @copydoc ::boost::intrusive::splaytree::init_node(reference) | |
922 | static void init_node(reference value); | |
923 | ||
924 | //! @copydoc ::boost::intrusive::splaytree::unlink_leftmost_without_rebalance | |
925 | pointer unlink_leftmost_without_rebalance(); | |
926 | ||
927 | //! @copydoc ::boost::intrusive::splaytree::replace_node | |
928 | void replace_node(iterator replace_this, reference with_this); | |
929 | ||
930 | //! @copydoc ::boost::intrusive::splaytree::remove_node | |
931 | void remove_node(reference value); | |
932 | ||
933 | //! @copydoc ::boost::intrusive::splaytree::splay_up(iterator) | |
934 | void splay_up(iterator i); | |
935 | ||
936 | //! @copydoc ::boost::intrusive::splaytree::splay_down(const KeyType&,KeyTypeKeyCompare) | |
937 | template<class KeyType, class KeyTypeKeyCompare> | |
938 | iterator splay_down(const KeyType &key, KeyTypeKeyCompare comp); | |
939 | ||
940 | //! @copydoc ::boost::intrusive::splaytree::splay_down(const key_type &key) | |
941 | iterator splay_down(const key_type &key); | |
942 | ||
943 | //! @copydoc ::boost::intrusive::splaytree::rebalance | |
944 | void rebalance(); | |
945 | ||
946 | //! @copydoc ::boost::intrusive::splaytree::rebalance_subtree | |
947 | iterator rebalance_subtree(iterator root); | |
948 | ||
949 | //! @copydoc ::boost::intrusive::splaytree::merge_equal | |
950 | template<class ...Options2> | |
951 | void merge(splay_multiset<T, Options2...> &source); | |
952 | ||
953 | //! @copydoc ::boost::intrusive::splaytree::merge_equal | |
954 | template<class ...Options2> | |
955 | void merge(splay_set<T, Options2...> &source); | |
956 | ||
957 | #else | |
958 | ||
959 | template<class Compare2> | |
960 | void merge(splay_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source) | |
961 | { return tree_type::merge_equal(source); } | |
962 | ||
963 | template<class Compare2> | |
964 | void merge(splay_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source) | |
965 | { return tree_type::merge_equal(source); } | |
966 | ||
967 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
968 | }; | |
969 | ||
970 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
971 | ||
972 | template<class T, class ...Options> | |
973 | bool operator!= (const splay_multiset_impl<T, Options...> &x, const splay_multiset_impl<T, Options...> &y); | |
974 | ||
975 | template<class T, class ...Options> | |
976 | bool operator>(const splay_multiset_impl<T, Options...> &x, const splay_multiset_impl<T, Options...> &y); | |
977 | ||
978 | template<class T, class ...Options> | |
979 | bool operator<=(const splay_multiset_impl<T, Options...> &x, const splay_multiset_impl<T, Options...> &y); | |
980 | ||
981 | template<class T, class ...Options> | |
982 | bool operator>=(const splay_multiset_impl<T, Options...> &x, const splay_multiset_impl<T, Options...> &y); | |
983 | ||
984 | template<class T, class ...Options> | |
985 | void swap(splay_multiset_impl<T, Options...> &x, splay_multiset_impl<T, Options...> &y); | |
986 | ||
987 | #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
988 | ||
989 | //! Helper metafunction to define a \c splay_multiset that yields to the same type when the | |
990 | //! same options (either explicitly or implicitly) are used. | |
991 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
992 | template<class T, class ...Options> | |
993 | #else | |
994 | template<class T, class O1 = void, class O2 = void | |
995 | , class O3 = void, class O4 = void | |
996 | , class O5 = void, class O6 = void> | |
997 | #endif | |
998 | struct make_splay_multiset | |
999 | { | |
1000 | /// @cond | |
1001 | typedef typename pack_options | |
1002 | < splaytree_defaults, | |
1003 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
1004 | O1, O2, O3, O4, O5, O6 | |
1005 | #else | |
1006 | Options... | |
1007 | #endif | |
1008 | >::type packed_options; | |
1009 | ||
1010 | typedef typename detail::get_value_traits | |
1011 | <T, typename packed_options::proto_value_traits>::type value_traits; | |
1012 | ||
1013 | typedef splay_multiset_impl | |
1014 | < value_traits | |
1015 | , typename packed_options::key_of_value | |
1016 | , typename packed_options::compare | |
1017 | , typename packed_options::size_type | |
1018 | , packed_options::constant_time_size | |
1019 | , typename packed_options::header_holder_type | |
1020 | > implementation_defined; | |
1021 | /// @endcond | |
1022 | typedef implementation_defined type; | |
1023 | }; | |
1024 | ||
1025 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
1026 | ||
1027 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
1028 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> | |
1029 | #else | |
1030 | template<class T, class ...Options> | |
1031 | #endif | |
1032 | class splay_multiset | |
1033 | : public make_splay_multiset<T, | |
1034 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
1035 | O1, O2, O3, O4, O5, O6 | |
1036 | #else | |
1037 | Options... | |
1038 | #endif | |
1039 | >::type | |
1040 | { | |
1041 | typedef typename make_splay_multiset<T, | |
1042 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
1043 | O1, O2, O3, O4, O5, O6 | |
1044 | #else | |
1045 | Options... | |
1046 | #endif | |
1047 | >::type Base; | |
1048 | ||
1049 | BOOST_MOVABLE_BUT_NOT_COPYABLE(splay_multiset) | |
1050 | ||
1051 | public: | |
1052 | typedef typename Base::key_compare key_compare; | |
1053 | typedef typename Base::value_traits value_traits; | |
1054 | typedef typename Base::iterator iterator; | |
1055 | typedef typename Base::const_iterator const_iterator; | |
1056 | ||
1057 | //Assert if passed value traits are compatible with the type | |
1058 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); | |
1059 | ||
1060 | splay_multiset() | |
1061 | : Base() | |
1062 | {} | |
1063 | ||
1064 | explicit splay_multiset( const key_compare &cmp, const value_traits &v_traits = value_traits()) | |
1065 | : Base(cmp, v_traits) | |
1066 | {} | |
1067 | ||
1068 | template<class Iterator> | |
1069 | splay_multiset( Iterator b, Iterator e | |
1070 | , const key_compare &cmp = key_compare() | |
1071 | , const value_traits &v_traits = value_traits()) | |
1072 | : Base(b, e, cmp, v_traits) | |
1073 | {} | |
1074 | ||
1075 | splay_multiset(BOOST_RV_REF(splay_multiset) x) | |
1076 | : Base(::boost::move(static_cast<Base&>(x))) | |
1077 | {} | |
1078 | ||
1079 | splay_multiset& operator=(BOOST_RV_REF(splay_multiset) x) | |
1080 | { return static_cast<splay_multiset &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } | |
1081 | ||
1082 | template <class Cloner, class Disposer> | |
1083 | void clone_from(const splay_multiset &src, Cloner cloner, Disposer disposer) | |
1084 | { Base::clone_from(src, cloner, disposer); } | |
1085 | ||
1086 | template <class Cloner, class Disposer> | |
1087 | void clone_from(BOOST_RV_REF(splay_multiset) src, Cloner cloner, Disposer disposer) | |
1088 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } | |
1089 | ||
1090 | static splay_multiset &container_from_end_iterator(iterator end_iterator) | |
1091 | { return static_cast<splay_multiset &>(Base::container_from_end_iterator(end_iterator)); } | |
1092 | ||
1093 | static const splay_multiset &container_from_end_iterator(const_iterator end_iterator) | |
1094 | { return static_cast<const splay_multiset &>(Base::container_from_end_iterator(end_iterator)); } | |
1095 | ||
1096 | static splay_multiset &container_from_iterator(iterator it) | |
1097 | { return static_cast<splay_multiset &>(Base::container_from_iterator(it)); } | |
1098 | ||
1099 | static const splay_multiset &container_from_iterator(const_iterator it) | |
1100 | { return static_cast<const splay_multiset &>(Base::container_from_iterator(it)); } | |
1101 | }; | |
1102 | ||
1103 | #endif | |
1104 | ||
1105 | } //namespace intrusive | |
1106 | } //namespace boost | |
1107 | ||
1108 | #include <boost/intrusive/detail/config_end.hpp> | |
1109 | ||
1110 | #endif //BOOST_INTRUSIVE_SPLAY_SET_HPP |