1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Ion Gaztanaga 2007-2013 |
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_AVLTREE_HPP |
13 | #define BOOST_INTRUSIVE_AVLTREE_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> |
20 | |
21 | #include <boost/static_assert.hpp> |
22 | #include <boost/intrusive/avl_set_hook.hpp> |
23 | #include <boost/intrusive/detail/avltree_node.hpp> |
24 | #include <boost/intrusive/bstree.hpp> |
25 | #include <boost/intrusive/detail/tree_node.hpp> |
26 | #include <boost/intrusive/detail/ebo_functor_holder.hpp> |
27 | #include <boost/intrusive/detail/mpl.hpp> |
28 | #include <boost/intrusive/pointer_traits.hpp> |
29 | #include <boost/intrusive/detail/get_value_traits.hpp> |
30 | #include <boost/intrusive/avltree_algorithms.hpp> |
31 | #include <boost/intrusive/link_mode.hpp> |
32 | #include <boost/move/utility_core.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_avltree_hook_applier |
44 | { template <class T> struct apply{ typedef typename T::default_avltree_hook type; }; }; |
45 | |
46 | template<> |
47 | struct is_default_hook_tag<default_avltree_hook_applier> |
48 | { static const bool value = true; }; |
49 | |
50 | struct avltree_defaults |
51 | : bstree_defaults |
52 | { |
53 | typedef default_avltree_hook_applier proto_value_traits; |
54 | }; |
55 | |
56 | /// @endcond |
57 | |
58 | //! The class template avltree is an intrusive AVL tree container, that |
59 | //! is used to construct intrusive avl_set and avl_multiset containers. |
60 | //! The no-throw 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 avltree_impl |
77 | /// @cond |
78 | : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder> |
79 | /// @endcond |
80 | { |
81 | public: |
82 | typedef ValueTraits value_traits; |
83 | /// @cond |
84 | typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType |
85 | , ConstantTimeSize, AvlTreeAlgorithms |
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(avltree_impl) |
117 | |
118 | /// @endcond |
119 | |
120 | public: |
121 | |
122 | typedef typename implementation_defined::insert_commit_data insert_commit_data; |
123 | |
124 | |
125 | //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &) |
126 | explicit avltree_impl( const key_compare &cmp = key_compare() |
127 | , const value_traits &v_traits = value_traits()) |
128 | : tree_type(cmp, v_traits) |
129 | {} |
130 | |
131 | //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &) |
132 | template<class Iterator> |
133 | avltree_impl( bool unique, Iterator b, Iterator e |
134 | , const key_compare &cmp = key_compare() |
135 | , const value_traits &v_traits = value_traits()) |
136 | : tree_type(unique, b, e, cmp, v_traits) |
137 | {} |
138 | |
139 | //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) |
140 | avltree_impl(BOOST_RV_REF(avltree_impl) x) |
141 | : tree_type(BOOST_MOVE_BASE(tree_type, x)) |
142 | {} |
143 | |
144 | //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) |
145 | avltree_impl& operator=(BOOST_RV_REF(avltree_impl) x) |
146 | { return static_cast<avltree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } |
147 | |
148 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
149 | |
150 | //! @copydoc ::boost::intrusive::bstree::~bstree() |
151 | ~avltree_impl(); |
152 | |
153 | //! @copydoc ::boost::intrusive::bstree::begin() |
154 | iterator begin(); |
155 | |
156 | //! @copydoc ::boost::intrusive::bstree::begin()const |
157 | const_iterator begin() const; |
158 | |
159 | //! @copydoc ::boost::intrusive::bstree::cbegin()const |
160 | const_iterator cbegin() const; |
161 | |
162 | //! @copydoc ::boost::intrusive::bstree::end() |
163 | iterator end(); |
164 | |
165 | //! @copydoc ::boost::intrusive::bstree::end()const |
166 | const_iterator end() const; |
167 | |
168 | //! @copydoc ::boost::intrusive::bstree::cend()const |
169 | const_iterator cend() const; |
170 | |
171 | //! @copydoc ::boost::intrusive::bstree::rbegin() |
172 | reverse_iterator rbegin(); |
173 | |
174 | //! @copydoc ::boost::intrusive::bstree::rbegin()const |
175 | const_reverse_iterator rbegin() const; |
176 | |
177 | //! @copydoc ::boost::intrusive::bstree::crbegin()const |
178 | const_reverse_iterator crbegin() const; |
179 | |
180 | //! @copydoc ::boost::intrusive::bstree::rend() |
181 | reverse_iterator rend(); |
182 | |
183 | //! @copydoc ::boost::intrusive::bstree::rend()const |
184 | const_reverse_iterator rend() const; |
185 | |
186 | //! @copydoc ::boost::intrusive::bstree::crend()const |
187 | const_reverse_iterator crend() const; |
188 | |
189 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) |
190 | static avltree_impl &container_from_end_iterator(iterator end_iterator); |
191 | |
192 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) |
193 | static const avltree_impl &container_from_end_iterator(const_iterator end_iterator); |
194 | |
195 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) |
196 | static avltree_impl &container_from_iterator(iterator it); |
197 | |
198 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) |
199 | static const avltree_impl &container_from_iterator(const_iterator it); |
200 | |
201 | //! @copydoc ::boost::intrusive::bstree::key_comp()const |
202 | key_compare key_comp() const; |
203 | |
204 | //! @copydoc ::boost::intrusive::bstree::value_comp()const |
205 | value_compare value_comp() const; |
206 | |
207 | //! @copydoc ::boost::intrusive::bstree::empty()const |
208 | bool empty() const; |
209 | |
210 | //! @copydoc ::boost::intrusive::bstree::size()const |
211 | size_type size() const; |
212 | |
213 | //! @copydoc ::boost::intrusive::bstree::swap |
214 | void swap(avltree_impl& other); |
215 | |
216 | //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer) |
217 | template <class Cloner, class Disposer> |
218 | void clone_from(const avltree_impl &src, Cloner cloner, Disposer disposer); |
219 | |
220 | #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED |
221 | |
222 | using tree_type::clone_from; |
223 | |
224 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
225 | |
226 | //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) |
227 | template <class Cloner, class Disposer> |
228 | void clone_from(BOOST_RV_REF(avltree_impl) src, Cloner cloner, Disposer disposer) |
229 | { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } |
230 | |
231 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
232 | |
233 | //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) |
234 | iterator insert_equal(reference value); |
235 | |
236 | //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference) |
237 | iterator insert_equal(const_iterator hint, reference value); |
238 | |
239 | //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator) |
240 | template<class Iterator> |
241 | void insert_equal(Iterator b, Iterator e); |
242 | |
243 | //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) |
244 | std::pair<iterator, bool> insert_unique(reference value); |
245 | |
246 | //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference) |
247 | iterator insert_unique(const_iterator hint, reference value); |
248 | |
249 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) |
250 | template<class KeyType, class KeyTypeKeyCompare> |
251 | std::pair<iterator, bool> insert_unique_check |
252 | (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); |
253 | |
254 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) |
255 | template<class KeyType, class KeyTypeKeyCompare> |
256 | std::pair<iterator, bool> insert_unique_check |
257 | (const_iterator hint, const KeyType &key |
258 | ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); |
259 | |
260 | //! @copydoc ::boost::intrusive::bstree::insert_unique_commit |
261 | iterator insert_unique_commit(reference value, const insert_commit_data &commit_data); |
262 | |
263 | //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator) |
264 | template<class Iterator> |
265 | void insert_unique(Iterator b, Iterator e); |
266 | |
267 | //! @copydoc ::boost::intrusive::bstree::insert_before |
268 | iterator insert_before(const_iterator pos, reference value); |
269 | |
270 | //! @copydoc ::boost::intrusive::bstree::push_back |
271 | void push_back(reference value); |
272 | |
273 | //! @copydoc ::boost::intrusive::bstree::push_front |
274 | void push_front(reference value); |
275 | |
276 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator) |
277 | iterator erase(const_iterator i); |
278 | |
279 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator) |
280 | iterator erase(const_iterator b, const_iterator e); |
281 | |
282 | //! @copydoc ::boost::intrusive::bstree::erase(const key_type &) |
283 | size_type erase(const key_type &key); |
284 | |
285 | //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare) |
286 | template<class KeyType, class KeyTypeKeyCompare> |
287 | size_type erase(const KeyType& key, KeyTypeKeyCompare comp); |
288 | |
289 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer) |
290 | template<class Disposer> |
291 | iterator erase_and_dispose(const_iterator i, Disposer disposer); |
292 | |
293 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer) |
294 | template<class Disposer> |
295 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); |
296 | |
297 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer) |
298 | template<class Disposer> |
299 | size_type erase_and_dispose(const key_type &key, Disposer disposer); |
300 | |
301 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) |
302 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> |
303 | size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); |
304 | |
305 | //! @copydoc ::boost::intrusive::bstree::clear |
306 | void clear(); |
307 | |
308 | //! @copydoc ::boost::intrusive::bstree::clear_and_dispose |
309 | template<class Disposer> |
310 | void clear_and_dispose(Disposer disposer); |
311 | |
312 | //! @copydoc ::boost::intrusive::bstree::count(const key_type &ke)const |
313 | size_type count(const key_type &key) const; |
314 | |
315 | //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const |
316 | template<class KeyType, class KeyTypeKeyCompare> |
317 | size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; |
318 | |
319 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) |
320 | iterator lower_bound(const key_type &key); |
321 | |
322 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) |
323 | template<class KeyType, class KeyTypeKeyCompare> |
324 | iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); |
325 | |
326 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const |
327 | const_iterator lower_bound(const key_type &key) const; |
328 | |
329 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const |
330 | template<class KeyType, class KeyTypeKeyCompare> |
331 | const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; |
332 | |
333 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &key) |
334 | iterator upper_bound(const key_type &key); |
335 | |
336 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) |
337 | template<class KeyType, class KeyTypeKeyCompare> |
338 | iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); |
339 | |
340 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const |
341 | const_iterator upper_bound(const key_type &key) const; |
342 | |
343 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const |
344 | template<class KeyType, class KeyTypeKeyCompare> |
345 | const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; |
346 | |
347 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &) |
348 | iterator find(const key_type &key); |
349 | |
350 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) |
351 | template<class KeyType, class KeyTypeKeyCompare> |
352 | iterator find(const KeyType& key, KeyTypeKeyCompare comp); |
353 | |
354 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const |
355 | const_iterator find(const key_type &key) const; |
356 | |
357 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const |
358 | template<class KeyType, class KeyTypeKeyCompare> |
359 | const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; |
360 | |
361 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) |
362 | std::pair<iterator,iterator> equal_range(const key_type &key); |
363 | |
364 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) |
365 | template<class KeyType, class KeyTypeKeyCompare> |
366 | std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); |
367 | |
368 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const |
369 | std::pair<const_iterator, const_iterator> |
370 | equal_range(const key_type &key) const; |
371 | |
372 | //! @copydoc ::boost::intrusive::bstree::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 | |
377 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) |
378 | std::pair<iterator,iterator> bounded_range |
379 | (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed); |
380 | |
381 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) |
382 | template<class KeyType, class KeyTypeKeyCompare> |
383 | std::pair<iterator,iterator> bounded_range |
384 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); |
385 | |
386 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const |
387 | std::pair<const_iterator, const_iterator> |
388 | bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; |
389 | |
390 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const |
391 | template<class KeyType, class KeyTypeKeyCompare> |
392 | std::pair<const_iterator, const_iterator> bounded_range |
393 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; |
394 | |
395 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) |
396 | static iterator s_iterator_to(reference value); |
397 | |
398 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) |
399 | static const_iterator s_iterator_to(const_reference value); |
400 | |
401 | //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) |
402 | iterator iterator_to(reference value); |
403 | |
404 | //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const |
405 | const_iterator iterator_to(const_reference value) const; |
406 | |
407 | //! @copydoc ::boost::intrusive::bstree::init_node(reference) |
408 | static void init_node(reference value); |
409 | |
410 | //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance |
411 | pointer unlink_leftmost_without_rebalance(); |
412 | |
413 | //! @copydoc ::boost::intrusive::bstree::replace_node |
414 | void replace_node(iterator replace_this, reference with_this); |
415 | |
416 | //! @copydoc ::boost::intrusive::bstree::remove_node |
417 | void remove_node(reference value); |
418 | |
419 | friend bool operator< (const avltree_impl &x, const avltree_impl &y); |
420 | |
421 | friend bool operator==(const avltree_impl &x, const avltree_impl &y); |
422 | |
423 | friend bool operator!= (const avltree_impl &x, const avltree_impl &y); |
424 | |
425 | friend bool operator>(const avltree_impl &x, const avltree_impl &y); |
426 | |
427 | friend bool operator<=(const avltree_impl &x, const avltree_impl &y); |
428 | |
429 | friend bool operator>=(const avltree_impl &x, const avltree_impl &y); |
430 | |
431 | friend void swap(avltree_impl &x, avltree_impl &y); |
432 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
433 | }; |
434 | |
435 | |
436 | //! Helper metafunction to define a \c avltree that yields to the same type when the |
437 | //! same options (either explicitly or implicitly) are used. |
438 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
439 | template<class T, class ...Options> |
440 | #else |
441 | template<class T, class O1 = void, class O2 = void |
442 | , class O3 = void, class O4 = void |
443 | , class O5 = void, class O6 = void> |
444 | #endif |
445 | struct make_avltree |
446 | { |
447 | /// @cond |
448 | typedef typename pack_options |
449 | < avltree_defaults, |
450 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
451 | O1, O2, O3, O4, O5, O6 |
452 | #else |
453 | Options... |
454 | #endif |
455 | >::type packed_options; |
456 | |
457 | typedef typename detail::get_value_traits |
458 | <T, typename packed_options::proto_value_traits>::type value_traits; |
459 | |
460 | typedef avltree_impl |
461 | < value_traits |
462 | , typename packed_options::key_of_value |
463 | , typename packed_options::compare |
464 | , typename packed_options::size_type |
465 | , packed_options::constant_time_size |
466 | , typename packed_options::header_holder_type |
467 | > implementation_defined; |
468 | /// @endcond |
469 | typedef implementation_defined type; |
470 | }; |
471 | |
472 | |
473 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
474 | |
475 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
476 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> |
477 | #else |
478 | template<class T, class ...Options> |
479 | #endif |
480 | class avltree |
481 | : public make_avltree<T, |
482 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
483 | O1, O2, O3, O4, O5, O6 |
484 | #else |
485 | Options... |
486 | #endif |
487 | >::type |
488 | { |
489 | typedef typename make_avltree |
490 | <T, |
491 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
492 | O1, O2, O3, O4, O5, O6 |
493 | #else |
494 | Options... |
495 | #endif |
496 | >::type Base; |
497 | BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree) |
498 | |
499 | public: |
500 | typedef typename Base::key_compare key_compare; |
501 | typedef typename Base::value_traits value_traits; |
502 | typedef typename Base::iterator iterator; |
503 | typedef typename Base::const_iterator const_iterator; |
504 | typedef typename Base::reverse_iterator reverse_iterator; |
505 | typedef typename Base::const_reverse_iterator const_reverse_iterator; |
506 | |
507 | //Assert if passed value traits are compatible with the type |
508 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); |
509 | |
510 | explicit avltree( const key_compare &cmp = key_compare() |
511 | , const value_traits &v_traits = value_traits()) |
512 | : Base(cmp, v_traits) |
513 | {} |
514 | |
515 | template<class Iterator> |
516 | avltree( bool unique, Iterator b, Iterator e |
517 | , const key_compare &cmp = key_compare() |
518 | , const value_traits &v_traits = value_traits()) |
519 | : Base(unique, b, e, cmp, v_traits) |
520 | {} |
521 | |
522 | avltree(BOOST_RV_REF(avltree) x) |
523 | : Base(BOOST_MOVE_BASE(Base, x)) |
524 | {} |
525 | |
526 | avltree& operator=(BOOST_RV_REF(avltree) x) |
527 | { return static_cast<avltree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } |
528 | |
529 | template <class Cloner, class Disposer> |
530 | void clone_from(const avltree &src, Cloner cloner, Disposer disposer) |
531 | { Base::clone_from(src, cloner, disposer); } |
532 | |
533 | template <class Cloner, class Disposer> |
534 | void clone_from(BOOST_RV_REF(avltree) src, Cloner cloner, Disposer disposer) |
535 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } |
536 | |
537 | static avltree &container_from_end_iterator(iterator end_iterator) |
538 | { return static_cast<avltree &>(Base::container_from_end_iterator(end_iterator)); } |
539 | |
540 | static const avltree &container_from_end_iterator(const_iterator end_iterator) |
541 | { return static_cast<const avltree &>(Base::container_from_end_iterator(end_iterator)); } |
542 | |
543 | static avltree &container_from_iterator(iterator it) |
544 | { return static_cast<avltree &>(Base::container_from_iterator(it)); } |
545 | |
546 | static const avltree &container_from_iterator(const_iterator it) |
547 | { return static_cast<const avltree &>(Base::container_from_iterator(it)); } |
548 | }; |
549 | |
550 | #endif |
551 | |
552 | } //namespace intrusive |
553 | } //namespace boost |
554 | |
555 | #include <boost/intrusive/detail/config_end.hpp> |
556 | |
557 | #endif //BOOST_INTRUSIVE_AVLTREE_HPP |
558 | |