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

source code of boost/boost/intrusive/treap_set.hpp