]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | //! @copydoc ::boost::intrusive::bstree::bstree() | |
125 | avltree_impl() | |
126 | : tree_type() | |
127 | {} | |
128 | ||
129 | //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &) | |
130 | explicit avltree_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 | avltree_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 | avltree_impl(BOOST_RV_REF(avltree_impl) x) | |
144 | : tree_type(BOOST_MOVE_BASE(tree_type, x)) | |
145 | {} | |
146 | ||
147 | //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) | |
148 | avltree_impl& operator=(BOOST_RV_REF(avltree_impl) x) | |
149 | { return static_cast<avltree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } | |
150 | ||
151 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
152 | ||
153 | //! @copydoc ::boost::intrusive::bstree::~bstree() | |
154 | ~avltree_impl(); | |
155 | ||
156 | //! @copydoc ::boost::intrusive::bstree::begin() | |
1e59de90 | 157 | iterator begin() BOOST_NOEXCEPT; |
7c673cae FG |
158 | |
159 | //! @copydoc ::boost::intrusive::bstree::begin()const | |
1e59de90 | 160 | const_iterator begin() const BOOST_NOEXCEPT; |
7c673cae FG |
161 | |
162 | //! @copydoc ::boost::intrusive::bstree::cbegin()const | |
1e59de90 | 163 | const_iterator cbegin() const BOOST_NOEXCEPT; |
7c673cae FG |
164 | |
165 | //! @copydoc ::boost::intrusive::bstree::end() | |
1e59de90 | 166 | iterator end() BOOST_NOEXCEPT; |
7c673cae FG |
167 | |
168 | //! @copydoc ::boost::intrusive::bstree::end()const | |
1e59de90 | 169 | const_iterator end() const BOOST_NOEXCEPT; |
7c673cae FG |
170 | |
171 | //! @copydoc ::boost::intrusive::bstree::cend()const | |
1e59de90 | 172 | const_iterator cend() const BOOST_NOEXCEPT; |
7c673cae FG |
173 | |
174 | //! @copydoc ::boost::intrusive::bstree::rbegin() | |
1e59de90 | 175 | reverse_iterator rbegin() BOOST_NOEXCEPT; |
7c673cae FG |
176 | |
177 | //! @copydoc ::boost::intrusive::bstree::rbegin()const | |
1e59de90 | 178 | const_reverse_iterator rbegin() const BOOST_NOEXCEPT; |
7c673cae FG |
179 | |
180 | //! @copydoc ::boost::intrusive::bstree::crbegin()const | |
1e59de90 | 181 | const_reverse_iterator crbegin() const BOOST_NOEXCEPT; |
7c673cae FG |
182 | |
183 | //! @copydoc ::boost::intrusive::bstree::rend() | |
1e59de90 | 184 | reverse_iterator rend() BOOST_NOEXCEPT; |
7c673cae FG |
185 | |
186 | //! @copydoc ::boost::intrusive::bstree::rend()const | |
1e59de90 | 187 | const_reverse_iterator rend() const BOOST_NOEXCEPT; |
7c673cae FG |
188 | |
189 | //! @copydoc ::boost::intrusive::bstree::crend()const | |
1e59de90 | 190 | const_reverse_iterator crend() const BOOST_NOEXCEPT; |
7c673cae FG |
191 | |
192 | //! @copydoc ::boost::intrusive::bstree::root() | |
1e59de90 | 193 | iterator root() BOOST_NOEXCEPT; |
7c673cae FG |
194 | |
195 | //! @copydoc ::boost::intrusive::bstree::root()const | |
1e59de90 | 196 | const_iterator root() const BOOST_NOEXCEPT; |
7c673cae FG |
197 | |
198 | //! @copydoc ::boost::intrusive::bstree::croot()const | |
1e59de90 | 199 | const_iterator croot() const BOOST_NOEXCEPT; |
7c673cae FG |
200 | |
201 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) | |
1e59de90 | 202 | static avltree_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT; |
7c673cae FG |
203 | |
204 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) | |
1e59de90 | 205 | static const avltree_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT; |
7c673cae FG |
206 | |
207 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) | |
1e59de90 | 208 | static avltree_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT; |
7c673cae FG |
209 | |
210 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) | |
1e59de90 | 211 | static const avltree_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT; |
7c673cae FG |
212 | |
213 | //! @copydoc ::boost::intrusive::bstree::key_comp()const | |
214 | key_compare key_comp() const; | |
215 | ||
216 | //! @copydoc ::boost::intrusive::bstree::value_comp()const | |
217 | value_compare value_comp() const; | |
218 | ||
219 | //! @copydoc ::boost::intrusive::bstree::empty()const | |
1e59de90 | 220 | bool empty() const BOOST_NOEXCEPT; |
7c673cae FG |
221 | |
222 | //! @copydoc ::boost::intrusive::bstree::size()const | |
1e59de90 | 223 | size_type size() const BOOST_NOEXCEPT; |
7c673cae FG |
224 | |
225 | //! @copydoc ::boost::intrusive::bstree::swap | |
226 | void swap(avltree_impl& other); | |
227 | ||
228 | //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer) | |
229 | template <class Cloner, class Disposer> | |
230 | void clone_from(const avltree_impl &src, Cloner cloner, Disposer disposer); | |
231 | ||
232 | #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
233 | ||
234 | using tree_type::clone_from; | |
235 | ||
236 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
237 | ||
238 | //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) | |
239 | template <class Cloner, class Disposer> | |
240 | void clone_from(BOOST_RV_REF(avltree_impl) src, Cloner cloner, Disposer disposer) | |
241 | { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } | |
242 | ||
243 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
244 | ||
245 | //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) | |
246 | iterator insert_equal(reference value); | |
247 | ||
248 | //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference) | |
249 | iterator insert_equal(const_iterator hint, reference value); | |
250 | ||
251 | //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator) | |
252 | template<class Iterator> | |
253 | void insert_equal(Iterator b, Iterator e); | |
254 | ||
255 | //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) | |
256 | std::pair<iterator, bool> insert_unique(reference value); | |
257 | ||
258 | //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference) | |
259 | iterator insert_unique(const_iterator hint, reference value); | |
260 | ||
261 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) | |
262 | template<class KeyType, class KeyTypeKeyCompare> | |
263 | std::pair<iterator, bool> insert_unique_check | |
264 | (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); | |
265 | ||
266 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) | |
267 | template<class KeyType, class KeyTypeKeyCompare> | |
268 | std::pair<iterator, bool> insert_unique_check | |
269 | (const_iterator hint, const KeyType &key | |
270 | ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); | |
271 | ||
272 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&) | |
273 | std::pair<iterator, bool> insert_unique_check | |
274 | (const key_type &key, insert_commit_data &commit_data); | |
275 | ||
276 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&) | |
277 | std::pair<iterator, bool> insert_unique_check | |
278 | (const_iterator hint, const key_type &key, insert_commit_data &commit_data); | |
279 | ||
280 | //! @copydoc ::boost::intrusive::bstree::insert_unique_commit | |
1e59de90 | 281 | iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) BOOST_NOEXCEPT; |
7c673cae FG |
282 | |
283 | //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator) | |
284 | template<class Iterator> | |
285 | void insert_unique(Iterator b, Iterator e); | |
286 | ||
287 | //! @copydoc ::boost::intrusive::bstree::insert_before | |
1e59de90 | 288 | iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT; |
7c673cae FG |
289 | |
290 | //! @copydoc ::boost::intrusive::bstree::push_back | |
1e59de90 | 291 | void push_back(reference value) BOOST_NOEXCEPT; |
7c673cae FG |
292 | |
293 | //! @copydoc ::boost::intrusive::bstree::push_front | |
1e59de90 | 294 | void push_front(reference value) BOOST_NOEXCEPT; |
7c673cae FG |
295 | |
296 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator) | |
1e59de90 | 297 | iterator erase(const_iterator i) BOOST_NOEXCEPT; |
7c673cae FG |
298 | |
299 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator) | |
1e59de90 | 300 | iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT; |
7c673cae FG |
301 | |
302 | //! @copydoc ::boost::intrusive::bstree::erase(const key_type &) | |
303 | size_type erase(const key_type &key); | |
304 | ||
305 | //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare) | |
306 | template<class KeyType, class KeyTypeKeyCompare> | |
307 | size_type erase(const KeyType& key, KeyTypeKeyCompare comp); | |
308 | ||
309 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer) | |
310 | template<class Disposer> | |
1e59de90 | 311 | iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT; |
7c673cae FG |
312 | |
313 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer) | |
314 | template<class Disposer> | |
1e59de90 | 315 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT; |
7c673cae FG |
316 | |
317 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer) | |
318 | template<class Disposer> | |
319 | size_type erase_and_dispose(const key_type &key, Disposer disposer); | |
320 | ||
321 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) | |
322 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> | |
323 | size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); | |
324 | ||
325 | //! @copydoc ::boost::intrusive::bstree::clear | |
1e59de90 | 326 | void clear() BOOST_NOEXCEPT; |
7c673cae FG |
327 | |
328 | //! @copydoc ::boost::intrusive::bstree::clear_and_dispose | |
329 | template<class Disposer> | |
1e59de90 | 330 | void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT; |
7c673cae FG |
331 | |
332 | //! @copydoc ::boost::intrusive::bstree::count(const key_type &ke)const | |
333 | size_type count(const key_type &key) const; | |
334 | ||
335 | //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const | |
336 | template<class KeyType, class KeyTypeKeyCompare> | |
337 | size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; | |
338 | ||
339 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) | |
340 | iterator lower_bound(const key_type &key); | |
341 | ||
342 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) | |
343 | template<class KeyType, class KeyTypeKeyCompare> | |
344 | iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); | |
345 | ||
346 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const | |
347 | const_iterator lower_bound(const key_type &key) const; | |
348 | ||
349 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const | |
350 | template<class KeyType, class KeyTypeKeyCompare> | |
351 | const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; | |
352 | ||
353 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &key) | |
354 | iterator upper_bound(const key_type &key); | |
355 | ||
356 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) | |
357 | template<class KeyType, class KeyTypeKeyCompare> | |
358 | iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); | |
359 | ||
360 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const | |
361 | const_iterator upper_bound(const key_type &key) const; | |
362 | ||
363 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const | |
364 | template<class KeyType, class KeyTypeKeyCompare> | |
365 | const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; | |
366 | ||
367 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &) | |
368 | iterator find(const key_type &key); | |
369 | ||
370 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) | |
371 | template<class KeyType, class KeyTypeKeyCompare> | |
372 | iterator find(const KeyType& key, KeyTypeKeyCompare comp); | |
373 | ||
374 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const | |
375 | const_iterator find(const key_type &key) const; | |
376 | ||
377 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const | |
378 | template<class KeyType, class KeyTypeKeyCompare> | |
379 | const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; | |
380 | ||
381 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) | |
382 | std::pair<iterator,iterator> equal_range(const key_type &key); | |
383 | ||
384 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) | |
385 | template<class KeyType, class KeyTypeKeyCompare> | |
386 | std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); | |
387 | ||
388 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const | |
389 | std::pair<const_iterator, const_iterator> | |
390 | equal_range(const key_type &key) const; | |
391 | ||
392 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const | |
393 | template<class KeyType, class KeyTypeKeyCompare> | |
394 | std::pair<const_iterator, const_iterator> | |
395 | equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; | |
396 | ||
397 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) | |
398 | std::pair<iterator,iterator> bounded_range | |
399 | (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed); | |
400 | ||
401 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) | |
402 | template<class KeyType, class KeyTypeKeyCompare> | |
403 | std::pair<iterator,iterator> bounded_range | |
404 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); | |
405 | ||
406 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const | |
407 | std::pair<const_iterator, const_iterator> | |
408 | bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; | |
409 | ||
410 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const | |
411 | template<class KeyType, class KeyTypeKeyCompare> | |
412 | std::pair<const_iterator, const_iterator> bounded_range | |
413 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; | |
414 | ||
415 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) | |
1e59de90 | 416 | static iterator s_iterator_to(reference value) BOOST_NOEXCEPT; |
7c673cae FG |
417 | |
418 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) | |
1e59de90 | 419 | static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT; |
7c673cae FG |
420 | |
421 | //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) | |
1e59de90 | 422 | iterator iterator_to(reference value) BOOST_NOEXCEPT; |
7c673cae FG |
423 | |
424 | //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const | |
1e59de90 | 425 | const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT; |
7c673cae FG |
426 | |
427 | //! @copydoc ::boost::intrusive::bstree::init_node(reference) | |
1e59de90 | 428 | static void init_node(reference value) BOOST_NOEXCEPT; |
7c673cae FG |
429 | |
430 | //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance | |
1e59de90 | 431 | pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT; |
7c673cae FG |
432 | |
433 | //! @copydoc ::boost::intrusive::bstree::replace_node | |
1e59de90 | 434 | void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT; |
7c673cae FG |
435 | |
436 | //! @copydoc ::boost::intrusive::bstree::remove_node | |
1e59de90 | 437 | void remove_node(reference value) BOOST_NOEXCEPT; |
7c673cae FG |
438 | |
439 | //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&) | |
440 | template<class T, class ...Options2> | |
441 | void merge_unique(avltree<T, Options2...> &); | |
442 | ||
443 | //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&) | |
444 | template<class T, class ...Options2> | |
445 | void merge_equal(avltree<T, Options2...> &); | |
446 | ||
447 | friend bool operator< (const avltree_impl &x, const avltree_impl &y); | |
448 | ||
449 | friend bool operator==(const avltree_impl &x, const avltree_impl &y); | |
450 | ||
451 | friend bool operator!= (const avltree_impl &x, const avltree_impl &y); | |
452 | ||
453 | friend bool operator>(const avltree_impl &x, const avltree_impl &y); | |
454 | ||
455 | friend bool operator<=(const avltree_impl &x, const avltree_impl &y); | |
456 | ||
457 | friend bool operator>=(const avltree_impl &x, const avltree_impl &y); | |
458 | ||
459 | friend void swap(avltree_impl &x, avltree_impl &y); | |
460 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
461 | }; | |
462 | ||
463 | ||
464 | //! Helper metafunction to define a \c avltree that yields to the same type when the | |
465 | //! same options (either explicitly or implicitly) are used. | |
466 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
467 | template<class T, class ...Options> | |
468 | #else | |
469 | template<class T, class O1 = void, class O2 = void | |
470 | , class O3 = void, class O4 = void | |
471 | , class O5 = void, class O6 = void> | |
472 | #endif | |
473 | struct make_avltree | |
474 | { | |
475 | /// @cond | |
476 | typedef typename pack_options | |
477 | < avltree_defaults, | |
478 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
479 | O1, O2, O3, O4, O5, O6 | |
480 | #else | |
481 | Options... | |
482 | #endif | |
483 | >::type packed_options; | |
484 | ||
485 | typedef typename detail::get_value_traits | |
486 | <T, typename packed_options::proto_value_traits>::type value_traits; | |
487 | ||
488 | typedef avltree_impl | |
489 | < value_traits | |
490 | , typename packed_options::key_of_value | |
491 | , typename packed_options::compare | |
492 | , typename packed_options::size_type | |
493 | , packed_options::constant_time_size | |
494 | , typename packed_options::header_holder_type | |
495 | > implementation_defined; | |
496 | /// @endcond | |
497 | typedef implementation_defined type; | |
498 | }; | |
499 | ||
500 | ||
501 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
502 | ||
503 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
504 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> | |
505 | #else | |
506 | template<class T, class ...Options> | |
507 | #endif | |
508 | class avltree | |
509 | : public make_avltree<T, | |
510 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
511 | O1, O2, O3, O4, O5, O6 | |
512 | #else | |
513 | Options... | |
514 | #endif | |
515 | >::type | |
516 | { | |
517 | typedef typename make_avltree | |
518 | <T, | |
519 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
520 | O1, O2, O3, O4, O5, O6 | |
521 | #else | |
522 | Options... | |
523 | #endif | |
524 | >::type Base; | |
525 | BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree) | |
526 | ||
527 | public: | |
528 | typedef typename Base::key_compare key_compare; | |
529 | typedef typename Base::value_traits value_traits; | |
530 | typedef typename Base::iterator iterator; | |
531 | typedef typename Base::const_iterator const_iterator; | |
532 | typedef typename Base::reverse_iterator reverse_iterator; | |
533 | typedef typename Base::const_reverse_iterator const_reverse_iterator; | |
534 | ||
535 | //Assert if passed value traits are compatible with the type | |
536 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); | |
537 | ||
92f5a8d4 | 538 | BOOST_INTRUSIVE_FORCEINLINE avltree() |
7c673cae FG |
539 | : Base() |
540 | {} | |
541 | ||
92f5a8d4 | 542 | BOOST_INTRUSIVE_FORCEINLINE explicit avltree( const key_compare &cmp, const value_traits &v_traits = value_traits()) |
7c673cae FG |
543 | : Base(cmp, v_traits) |
544 | {} | |
545 | ||
546 | template<class Iterator> | |
92f5a8d4 | 547 | BOOST_INTRUSIVE_FORCEINLINE avltree( bool unique, Iterator b, Iterator e |
7c673cae FG |
548 | , const key_compare &cmp = key_compare() |
549 | , const value_traits &v_traits = value_traits()) | |
550 | : Base(unique, b, e, cmp, v_traits) | |
551 | {} | |
552 | ||
92f5a8d4 | 553 | BOOST_INTRUSIVE_FORCEINLINE avltree(BOOST_RV_REF(avltree) x) |
7c673cae FG |
554 | : Base(BOOST_MOVE_BASE(Base, x)) |
555 | {} | |
556 | ||
92f5a8d4 | 557 | BOOST_INTRUSIVE_FORCEINLINE avltree& operator=(BOOST_RV_REF(avltree) x) |
7c673cae FG |
558 | { return static_cast<avltree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } |
559 | ||
560 | template <class Cloner, class Disposer> | |
92f5a8d4 | 561 | BOOST_INTRUSIVE_FORCEINLINE void clone_from(const avltree &src, Cloner cloner, Disposer disposer) |
7c673cae FG |
562 | { Base::clone_from(src, cloner, disposer); } |
563 | ||
564 | template <class Cloner, class Disposer> | |
92f5a8d4 | 565 | BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(avltree) src, Cloner cloner, Disposer disposer) |
7c673cae FG |
566 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } |
567 | ||
1e59de90 | 568 | BOOST_INTRUSIVE_FORCEINLINE static avltree &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT |
7c673cae FG |
569 | { return static_cast<avltree &>(Base::container_from_end_iterator(end_iterator)); } |
570 | ||
1e59de90 | 571 | BOOST_INTRUSIVE_FORCEINLINE static const avltree &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT |
7c673cae FG |
572 | { return static_cast<const avltree &>(Base::container_from_end_iterator(end_iterator)); } |
573 | ||
1e59de90 | 574 | BOOST_INTRUSIVE_FORCEINLINE static avltree &container_from_iterator(iterator it) BOOST_NOEXCEPT |
7c673cae FG |
575 | { return static_cast<avltree &>(Base::container_from_iterator(it)); } |
576 | ||
1e59de90 | 577 | BOOST_INTRUSIVE_FORCEINLINE static const avltree &container_from_iterator(const_iterator it) BOOST_NOEXCEPT |
7c673cae FG |
578 | { return static_cast<const avltree &>(Base::container_from_iterator(it)); } |
579 | }; | |
580 | ||
581 | #endif | |
582 | ||
583 | } //namespace intrusive | |
584 | } //namespace boost | |
585 | ||
586 | #include <boost/intrusive/detail/config_end.hpp> | |
587 | ||
588 | #endif //BOOST_INTRUSIVE_AVLTREE_HPP |