]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2006-2014 | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. | |
6 | // (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | // | |
9 | // See http://www.boost.org/libs/intrusive for documentation. | |
10 | // | |
11 | ///////////////////////////////////////////////////////////////////////////// | |
12 | #ifndef BOOST_INTRUSIVE_RBTREE_HPP | |
13 | #define BOOST_INTRUSIVE_RBTREE_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/set_hook.hpp> | |
22 | #include <boost/intrusive/detail/rbtree_node.hpp> | |
23 | #include <boost/intrusive/bstree.hpp> | |
24 | #include <boost/intrusive/detail/tree_node.hpp> | |
25 | #include <boost/intrusive/detail/mpl.hpp> | |
26 | #include <boost/intrusive/pointer_traits.hpp> | |
27 | #include <boost/intrusive/detail/get_value_traits.hpp> | |
28 | #include <boost/intrusive/rbtree_algorithms.hpp> | |
29 | #include <boost/intrusive/link_mode.hpp> | |
30 | ||
31 | #include <boost/move/utility_core.hpp> | |
32 | #include <boost/static_assert.hpp> | |
33 | ||
34 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
35 | # pragma once | |
36 | #endif | |
37 | ||
38 | namespace boost { | |
39 | namespace intrusive { | |
40 | ||
41 | /// @cond | |
42 | ||
43 | struct default_rbtree_hook_applier | |
44 | { template <class T> struct apply{ typedef typename T::default_rbtree_hook type; }; }; | |
45 | ||
46 | template<> | |
47 | struct is_default_hook_tag<default_rbtree_hook_applier> | |
48 | { static const bool value = true; }; | |
49 | ||
50 | struct rbtree_defaults | |
51 | : bstree_defaults | |
52 | { | |
53 | typedef default_rbtree_hook_applier proto_value_traits; | |
54 | }; | |
55 | ||
56 | /// @endcond | |
57 | ||
58 | //! The class template rbtree is an intrusive red-black tree container, that | |
59 | //! is used to construct intrusive set and multiset containers. The no-throw | |
60 | //! guarantee holds only, if the key_compare object | |
61 | //! doesn't throw. | |
62 | //! | |
63 | //! The template parameter \c T is the type to be managed by the container. | |
64 | //! The user can specify additional options and if no options are provided | |
65 | //! default options are used. | |
66 | //! | |
67 | //! The container supports the following options: | |
68 | //! \c base_hook<>/member_hook<>/value_traits<>, | |
69 | //! \c constant_time_size<>, \c size_type<> and | |
70 | //! \c compare<>. | |
71 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
72 | template<class T, class ...Options> | |
73 | #else | |
74 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder> | |
75 | #endif | |
76 | class rbtree_impl | |
77 | /// @cond | |
78 | : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder> | |
79 | /// @endcond | |
80 | { | |
81 | public: | |
82 | typedef ValueTraits value_traits; | |
83 | /// @cond | |
84 | typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType | |
85 | , ConstantTimeSize, RbTreeAlgorithms | |
86 | , HeaderHolder> tree_type; | |
87 | typedef tree_type implementation_defined; | |
88 | /// @endcond | |
89 | ||
90 | typedef typename implementation_defined::pointer pointer; | |
91 | typedef typename implementation_defined::const_pointer const_pointer; | |
92 | typedef typename implementation_defined::value_type value_type; | |
93 | typedef typename implementation_defined::key_type key_type; | |
94 | typedef typename implementation_defined::key_of_value key_of_value; | |
95 | typedef typename implementation_defined::reference reference; | |
96 | typedef typename implementation_defined::const_reference const_reference; | |
97 | typedef typename implementation_defined::difference_type difference_type; | |
98 | typedef typename implementation_defined::size_type size_type; | |
99 | typedef typename implementation_defined::value_compare value_compare; | |
100 | typedef typename implementation_defined::key_compare key_compare; | |
101 | typedef typename implementation_defined::iterator iterator; | |
102 | typedef typename implementation_defined::const_iterator const_iterator; | |
103 | typedef typename implementation_defined::reverse_iterator reverse_iterator; | |
104 | typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; | |
105 | typedef typename implementation_defined::node_traits node_traits; | |
106 | typedef typename implementation_defined::node node; | |
107 | typedef typename implementation_defined::node_ptr node_ptr; | |
108 | typedef typename implementation_defined::const_node_ptr const_node_ptr; | |
109 | typedef typename implementation_defined::node_algorithms node_algorithms; | |
110 | ||
111 | static const bool constant_time_size = implementation_defined::constant_time_size; | |
112 | /// @cond | |
113 | private: | |
114 | ||
115 | //noncopyable | |
116 | BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree_impl) | |
117 | ||
118 | /// @endcond | |
119 | ||
120 | public: | |
121 | ||
122 | typedef typename implementation_defined::insert_commit_data insert_commit_data; | |
123 | ||
124 | //! @copydoc ::boost::intrusive::bstree::bstree() | |
125 | rbtree_impl() | |
126 | : tree_type() | |
127 | {} | |
128 | ||
129 | //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &) | |
130 | explicit rbtree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) | |
131 | : tree_type(cmp, v_traits) | |
132 | {} | |
133 | ||
134 | //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &) | |
135 | template<class Iterator> | |
136 | rbtree_impl( bool unique, Iterator b, Iterator e | |
137 | , const key_compare &cmp = key_compare() | |
138 | , const value_traits &v_traits = value_traits()) | |
139 | : tree_type(unique, b, e, cmp, v_traits) | |
140 | {} | |
141 | ||
142 | //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) | |
143 | rbtree_impl(BOOST_RV_REF(rbtree_impl) x) | |
144 | : tree_type(BOOST_MOVE_BASE(tree_type, x)) | |
145 | {} | |
146 | ||
147 | //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) | |
148 | rbtree_impl& operator=(BOOST_RV_REF(rbtree_impl) x) | |
149 | { return static_cast<rbtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } | |
150 | ||
151 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
152 | //! @copydoc ::boost::intrusive::bstree::~bstree() | |
153 | ~rbtree_impl(); | |
154 | ||
155 | //! @copydoc ::boost::intrusive::bstree::begin() | |
156 | iterator begin(); | |
157 | ||
158 | //! @copydoc ::boost::intrusive::bstree::begin()const | |
159 | const_iterator begin() const; | |
160 | ||
161 | //! @copydoc ::boost::intrusive::bstree::cbegin()const | |
162 | const_iterator cbegin() const; | |
163 | ||
164 | //! @copydoc ::boost::intrusive::bstree::end() | |
165 | iterator end(); | |
166 | ||
167 | //! @copydoc ::boost::intrusive::bstree::end()const | |
168 | const_iterator end() const; | |
169 | ||
170 | //! @copydoc ::boost::intrusive::bstree::cend()const | |
171 | const_iterator cend() const; | |
172 | ||
173 | //! @copydoc ::boost::intrusive::bstree::rbegin() | |
174 | reverse_iterator rbegin(); | |
175 | ||
176 | //! @copydoc ::boost::intrusive::bstree::rbegin()const | |
177 | const_reverse_iterator rbegin() const; | |
178 | ||
179 | //! @copydoc ::boost::intrusive::bstree::crbegin()const | |
180 | const_reverse_iterator crbegin() const; | |
181 | ||
182 | //! @copydoc ::boost::intrusive::bstree::rend() | |
183 | reverse_iterator rend(); | |
184 | ||
185 | //! @copydoc ::boost::intrusive::bstree::rend()const | |
186 | const_reverse_iterator rend() const; | |
187 | ||
188 | //! @copydoc ::boost::intrusive::bstree::crend()const | |
189 | const_reverse_iterator crend() const; | |
190 | ||
191 | //! @copydoc ::boost::intrusive::bstree::root() | |
192 | iterator root(); | |
193 | ||
194 | //! @copydoc ::boost::intrusive::bstree::root()const | |
195 | const_iterator root() const; | |
196 | ||
197 | //! @copydoc ::boost::intrusive::bstree::croot()const | |
198 | const_iterator croot() const; | |
199 | ||
200 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) | |
201 | static rbtree_impl &container_from_end_iterator(iterator end_iterator); | |
202 | ||
203 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) | |
204 | static const rbtree_impl &container_from_end_iterator(const_iterator end_iterator); | |
205 | ||
206 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) | |
207 | static rbtree_impl &container_from_iterator(iterator it); | |
208 | ||
209 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) | |
210 | static const rbtree_impl &container_from_iterator(const_iterator it); | |
211 | ||
212 | //! @copydoc ::boost::intrusive::bstree::key_comp()const | |
213 | key_compare key_comp() const; | |
214 | ||
215 | //! @copydoc ::boost::intrusive::bstree::value_comp()const | |
216 | value_compare value_comp() const; | |
217 | ||
218 | //! @copydoc ::boost::intrusive::bstree::empty()const | |
219 | bool empty() const; | |
220 | ||
221 | //! @copydoc ::boost::intrusive::bstree::size()const | |
222 | size_type size() const; | |
223 | ||
224 | //! @copydoc ::boost::intrusive::bstree::swap | |
225 | void swap(rbtree_impl& other); | |
226 | ||
227 | //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer) | |
228 | template <class Cloner, class Disposer> | |
229 | void clone_from(const rbtree_impl &src, Cloner cloner, Disposer disposer); | |
230 | ||
231 | #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
232 | ||
233 | using tree_type::clone_from; | |
234 | ||
235 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
236 | ||
237 | //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) | |
238 | template <class Cloner, class Disposer> | |
239 | void clone_from(BOOST_RV_REF(rbtree_impl) src, Cloner cloner, Disposer disposer) | |
240 | { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } | |
241 | ||
242 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
243 | ||
244 | //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) | |
245 | template <class Cloner, class Disposer> | |
246 | void clone_from(rbtree_impl &&src, Cloner cloner, Disposer disposer); | |
247 | ||
248 | //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) | |
249 | iterator insert_equal(reference value); | |
250 | ||
251 | //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference) | |
252 | iterator insert_equal(const_iterator hint, reference value); | |
253 | ||
254 | //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator) | |
255 | template<class Iterator> | |
256 | void insert_equal(Iterator b, Iterator e); | |
257 | ||
258 | //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) | |
259 | std::pair<iterator, bool> insert_unique(reference value); | |
260 | ||
261 | //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference) | |
262 | iterator insert_unique(const_iterator hint, reference value); | |
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_check(const key_type&,insert_commit_data&) | |
276 | std::pair<iterator, bool> insert_unique_check | |
277 | (const key_type &key, insert_commit_data &commit_data); | |
278 | ||
279 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&) | |
280 | std::pair<iterator, bool> insert_unique_check | |
281 | (const_iterator hint, const key_type &key, insert_commit_data &commit_data); | |
282 | ||
283 | //! @copydoc ::boost::intrusive::bstree::insert_unique_commit | |
284 | iterator insert_unique_commit(reference value, const insert_commit_data &commit_data); | |
285 | ||
286 | //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator) | |
287 | template<class Iterator> | |
288 | void insert_unique(Iterator b, Iterator e); | |
289 | ||
290 | //! @copydoc ::boost::intrusive::bstree::insert_before | |
291 | iterator insert_before(const_iterator pos, reference value); | |
292 | ||
293 | //! @copydoc ::boost::intrusive::bstree::push_back | |
294 | void push_back(reference value); | |
295 | ||
296 | //! @copydoc ::boost::intrusive::bstree::push_front | |
297 | void push_front(reference value); | |
298 | ||
299 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator) | |
300 | iterator erase(const_iterator i); | |
301 | ||
302 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator) | |
303 | iterator erase(const_iterator b, const_iterator e); | |
304 | ||
305 | //! @copydoc ::boost::intrusive::bstree::erase(const key_type &key) | |
306 | size_type erase(const key_type &key); | |
307 | ||
308 | //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare) | |
309 | template<class KeyType, class KeyTypeKeyCompare> | |
310 | size_type erase(const KeyType& key, KeyTypeKeyCompare comp); | |
311 | ||
312 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer) | |
313 | template<class Disposer> | |
314 | iterator erase_and_dispose(const_iterator i, Disposer disposer); | |
315 | ||
316 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer) | |
317 | template<class Disposer> | |
318 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); | |
319 | ||
320 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer) | |
321 | template<class Disposer> | |
322 | size_type erase_and_dispose(const key_type &key, Disposer disposer); | |
323 | ||
324 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) | |
325 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> | |
326 | size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); | |
327 | ||
328 | //! @copydoc ::boost::intrusive::bstree::clear | |
329 | void clear(); | |
330 | ||
331 | //! @copydoc ::boost::intrusive::bstree::clear_and_dispose | |
332 | template<class Disposer> | |
333 | void clear_and_dispose(Disposer disposer); | |
334 | ||
335 | //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const | |
336 | size_type count(const key_type &key) const; | |
337 | ||
338 | //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const | |
339 | template<class KeyType, class KeyTypeKeyCompare> | |
340 | size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; | |
341 | ||
342 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) | |
343 | iterator lower_bound(const key_type &key); | |
344 | ||
345 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) | |
346 | template<class KeyType, class KeyTypeKeyCompare> | |
347 | iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); | |
348 | ||
349 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const | |
350 | const_iterator lower_bound(const key_type &key) const; | |
351 | ||
352 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const | |
353 | template<class KeyType, class KeyTypeKeyCompare> | |
354 | const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; | |
355 | ||
356 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) | |
357 | iterator upper_bound(const key_type &key); | |
358 | ||
359 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) | |
360 | template<class KeyType, class KeyTypeKeyCompare> | |
361 | iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); | |
362 | ||
363 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const | |
364 | const_iterator upper_bound(const key_type &key) const; | |
365 | ||
366 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const | |
367 | template<class KeyType, class KeyTypeKeyCompare> | |
368 | const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; | |
369 | ||
370 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &) | |
371 | iterator find(const key_type &key); | |
372 | ||
373 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) | |
374 | template<class KeyType, class KeyTypeKeyCompare> | |
375 | iterator find(const KeyType& key, KeyTypeKeyCompare comp); | |
376 | ||
377 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const | |
378 | const_iterator find(const key_type &key) const; | |
379 | ||
380 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const | |
381 | template<class KeyType, class KeyTypeKeyCompare> | |
382 | const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; | |
383 | ||
384 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) | |
385 | std::pair<iterator,iterator> equal_range(const key_type &key); | |
386 | ||
387 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) | |
388 | template<class KeyType, class KeyTypeKeyCompare> | |
389 | std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); | |
390 | ||
391 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const | |
392 | std::pair<const_iterator, const_iterator> | |
393 | equal_range(const key_type &key) const; | |
394 | ||
395 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const | |
396 | template<class KeyType, class KeyTypeKeyCompare> | |
397 | std::pair<const_iterator, const_iterator> | |
398 | equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; | |
399 | ||
400 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) | |
401 | std::pair<iterator,iterator> bounded_range | |
402 | (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed); | |
403 | ||
404 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) | |
405 | template<class KeyType, class KeyTypeKeyCompare> | |
406 | std::pair<iterator,iterator> bounded_range | |
407 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); | |
408 | ||
409 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const | |
410 | std::pair<const_iterator, const_iterator> | |
411 | bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; | |
412 | ||
413 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const | |
414 | template<class KeyType, class KeyTypeKeyCompare> | |
415 | std::pair<const_iterator, const_iterator> bounded_range | |
416 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; | |
417 | ||
418 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) | |
419 | static iterator s_iterator_to(reference value); | |
420 | ||
421 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) | |
422 | static const_iterator s_iterator_to(const_reference value); | |
423 | ||
424 | //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) | |
425 | iterator iterator_to(reference value); | |
426 | ||
427 | //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const | |
428 | const_iterator iterator_to(const_reference value) const; | |
429 | ||
430 | //! @copydoc ::boost::intrusive::bstree::init_node(reference) | |
431 | static void init_node(reference value); | |
432 | ||
433 | //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance | |
434 | pointer unlink_leftmost_without_rebalance(); | |
435 | ||
436 | //! @copydoc ::boost::intrusive::bstree::replace_node | |
437 | void replace_node(iterator replace_this, reference with_this); | |
438 | ||
439 | //! @copydoc ::boost::intrusive::bstree::remove_node | |
440 | void remove_node(reference value); | |
441 | ||
442 | //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&) | |
443 | template<class T, class ...Options2> | |
444 | void merge_unique(rbtree<T, Options2...> &); | |
445 | ||
446 | //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&) | |
447 | template<class T, class ...Options2> | |
448 | void merge_equal(rbtree<T, Options2...> &); | |
449 | ||
450 | friend bool operator< (const rbtree_impl &x, const rbtree_impl &y); | |
451 | ||
452 | friend bool operator==(const rbtree_impl &x, const rbtree_impl &y); | |
453 | ||
454 | friend bool operator!= (const rbtree_impl &x, const rbtree_impl &y); | |
455 | ||
456 | friend bool operator>(const rbtree_impl &x, const rbtree_impl &y); | |
457 | ||
458 | friend bool operator<=(const rbtree_impl &x, const rbtree_impl &y); | |
459 | ||
460 | friend bool operator>=(const rbtree_impl &x, const rbtree_impl &y); | |
461 | ||
462 | friend void swap(rbtree_impl &x, rbtree_impl &y); | |
463 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
464 | }; | |
465 | ||
466 | ||
467 | //! Helper metafunction to define a \c rbtree that yields to the same type when the | |
468 | //! same options (either explicitly or implicitly) are used. | |
469 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
470 | template<class T, class ...Options> | |
471 | #else | |
472 | template<class T, class O1 = void, class O2 = void | |
473 | , class O3 = void, class O4 = void | |
474 | , class O5 = void, class O6 = void> | |
475 | #endif | |
476 | struct make_rbtree | |
477 | { | |
478 | /// @cond | |
479 | typedef typename pack_options | |
480 | < rbtree_defaults, | |
481 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
482 | O1, O2, O3, O4, O5, O6 | |
483 | #else | |
484 | Options... | |
485 | #endif | |
486 | >::type packed_options; | |
487 | ||
488 | typedef typename detail::get_value_traits | |
489 | <T, typename packed_options::proto_value_traits>::type value_traits; | |
490 | ||
491 | typedef rbtree_impl | |
492 | < value_traits | |
493 | , typename packed_options::key_of_value | |
494 | , typename packed_options::compare | |
495 | , typename packed_options::size_type | |
496 | , packed_options::constant_time_size | |
497 | , typename packed_options::header_holder_type | |
498 | > implementation_defined; | |
499 | /// @endcond | |
500 | typedef implementation_defined type; | |
501 | }; | |
502 | ||
503 | ||
504 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
505 | ||
506 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
507 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> | |
508 | #else | |
509 | template<class T, class ...Options> | |
510 | #endif | |
511 | class rbtree | |
512 | : public make_rbtree<T, | |
513 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
514 | O1, O2, O3, O4, O5, O6 | |
515 | #else | |
516 | Options... | |
517 | #endif | |
518 | >::type | |
519 | { | |
520 | typedef typename make_rbtree | |
521 | <T, | |
522 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
523 | O1, O2, O3, O4, O5, O6 | |
524 | #else | |
525 | Options... | |
526 | #endif | |
527 | >::type Base; | |
528 | BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree) | |
529 | ||
530 | public: | |
531 | typedef typename Base::key_compare key_compare; | |
532 | typedef typename Base::value_traits value_traits; | |
533 | typedef typename Base::iterator iterator; | |
534 | typedef typename Base::const_iterator const_iterator; | |
535 | typedef typename Base::reverse_iterator reverse_iterator; | |
536 | typedef typename Base::const_reverse_iterator const_reverse_iterator; | |
537 | ||
538 | //Assert if passed value traits are compatible with the type | |
539 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); | |
540 | ||
541 | rbtree() | |
542 | : Base() | |
543 | {} | |
544 | ||
545 | explicit rbtree( const key_compare &cmp, const value_traits &v_traits = value_traits()) | |
546 | : Base(cmp, v_traits) | |
547 | {} | |
548 | ||
549 | template<class Iterator> | |
550 | rbtree( bool unique, Iterator b, Iterator e | |
551 | , const key_compare &cmp = key_compare() | |
552 | , const value_traits &v_traits = value_traits()) | |
553 | : Base(unique, b, e, cmp, v_traits) | |
554 | {} | |
555 | ||
556 | rbtree(BOOST_RV_REF(rbtree) x) | |
557 | : Base(BOOST_MOVE_BASE(Base, x)) | |
558 | {} | |
559 | ||
560 | rbtree& operator=(BOOST_RV_REF(rbtree) x) | |
561 | { return static_cast<rbtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } | |
562 | ||
563 | template <class Cloner, class Disposer> | |
564 | void clone_from(const rbtree &src, Cloner cloner, Disposer disposer) | |
565 | { Base::clone_from(src, cloner, disposer); } | |
566 | ||
567 | template <class Cloner, class Disposer> | |
568 | void clone_from(BOOST_RV_REF(rbtree) src, Cloner cloner, Disposer disposer) | |
569 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } | |
570 | ||
571 | static rbtree &container_from_end_iterator(iterator end_iterator) | |
572 | { return static_cast<rbtree &>(Base::container_from_end_iterator(end_iterator)); } | |
573 | ||
574 | static const rbtree &container_from_end_iterator(const_iterator end_iterator) | |
575 | { return static_cast<const rbtree &>(Base::container_from_end_iterator(end_iterator)); } | |
576 | ||
577 | static rbtree &container_from_iterator(iterator it) | |
578 | { return static_cast<rbtree &>(Base::container_from_iterator(it)); } | |
579 | ||
580 | static const rbtree &container_from_iterator(const_iterator it) | |
581 | { return static_cast<const rbtree &>(Base::container_from_iterator(it)); } | |
582 | }; | |
583 | ||
584 | #endif | |
585 | ||
586 | } //namespace intrusive | |
587 | } //namespace boost | |
588 | ||
589 | #include <boost/intrusive/detail/config_end.hpp> | |
590 | ||
591 | #endif //BOOST_INTRUSIVE_RBTREE_HPP |