Mercurial > hg > vamp-build-and-test

comparison DEPENDENCIES/generic/include/boost/intrusive/avl_set.hpp @ 16:2665513ce2d3

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