1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Ion Gaztanaga 2008-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_TREAP_HPP |
13 | #define BOOST_INTRUSIVE_TREAP_HPP |
14 | |
15 | #include <boost/intrusive/detail/config_begin.hpp> |
16 | #include <boost/intrusive/intrusive_fwd.hpp> |
17 | |
18 | #include <boost/intrusive/detail/assert.hpp> |
19 | #include <boost/intrusive/bs_set_hook.hpp> |
20 | #include <boost/intrusive/bstree.hpp> |
21 | #include <boost/intrusive/detail/tree_node.hpp> |
22 | #include <boost/intrusive/detail/ebo_functor_holder.hpp> |
23 | #include <boost/intrusive/pointer_traits.hpp> |
24 | #include <boost/intrusive/detail/get_value_traits.hpp> |
25 | #include <boost/intrusive/detail/mpl.hpp> |
26 | #include <boost/intrusive/treap_algorithms.hpp> |
27 | #include <boost/intrusive/link_mode.hpp> |
28 | #include <boost/intrusive/priority_compare.hpp> |
29 | #include <boost/intrusive/detail/node_cloner_disposer.hpp> |
30 | #include <boost/intrusive/detail/key_nodeptr_comp.hpp> |
31 | |
32 | #include <boost/static_assert.hpp> |
33 | #include <boost/move/utility_core.hpp> |
34 | #include <boost/move/adl_move_swap.hpp> |
35 | |
36 | #include <cstddef> |
37 | #include <boost/intrusive/detail/minimal_less_equal_header.hpp> |
38 | #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair |
39 | |
40 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
41 | # pragma once |
42 | #endif |
43 | |
44 | namespace boost { |
45 | namespace intrusive { |
46 | |
47 | /// @cond |
48 | |
49 | struct treap_defaults |
50 | : bstree_defaults |
51 | { |
52 | typedef void priority; |
53 | }; |
54 | |
55 | /// @endcond |
56 | |
57 | //! The class template treap is an intrusive treap container that |
58 | //! is used to construct intrusive set and multiset containers. The no-throw |
59 | //! guarantee holds only, if the key_compare object and priority_compare object |
60 | //! don't throw. |
61 | //! |
62 | //! The template parameter \c T is the type to be managed by the container. |
63 | //! The user can specify additional options and if no options are provided |
64 | //! default options are used. |
65 | //! |
66 | //! The container supports the following options: |
67 | //! \c base_hook<>/member_hook<>/value_traits<>, |
68 | //! \c constant_time_size<>, \c size_type<>, |
69 | //! \c compare<> and \c priority_compare<> |
70 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
71 | template<class T, class ...Options> |
72 | #else |
73 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder> |
74 | #endif |
75 | class treap_impl |
76 | /// @cond |
77 | : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder> |
78 | //Use public inheritance to avoid MSVC bugs with closures |
79 | , public detail::ebo_functor_holder |
80 | < typename get_prio |
81 | < VoidOrPrioComp |
82 | , typename bstree_impl |
83 | <ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder>::value_type>::type |
84 | > |
85 | /// @endcond |
86 | { |
87 | public: |
88 | typedef ValueTraits value_traits; |
89 | /// @cond |
90 | typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType |
91 | , ConstantTimeSize, BsTreeAlgorithms |
92 | , HeaderHolder> tree_type; |
93 | typedef tree_type implementation_defined; |
94 | typedef get_prio |
95 | < VoidOrPrioComp |
96 | , typename tree_type::value_type> get_prio_type; |
97 | |
98 | typedef detail::ebo_functor_holder |
99 | <typename get_prio_type::type> prio_base; |
100 | |
101 | /// @endcond |
102 | |
103 | typedef typename implementation_defined::pointer pointer; |
104 | typedef typename implementation_defined::const_pointer const_pointer; |
105 | typedef typename implementation_defined::value_type value_type; |
106 | typedef typename implementation_defined::key_type key_type; |
107 | typedef typename implementation_defined::key_of_value key_of_value; |
108 | typedef typename implementation_defined::reference reference; |
109 | typedef typename implementation_defined::const_reference const_reference; |
110 | typedef typename implementation_defined::difference_type difference_type; |
111 | typedef typename implementation_defined::size_type size_type; |
112 | typedef typename implementation_defined::value_compare value_compare; |
113 | typedef typename implementation_defined::key_compare key_compare; |
114 | typedef typename implementation_defined::iterator iterator; |
115 | typedef typename implementation_defined::const_iterator const_iterator; |
116 | typedef typename implementation_defined::reverse_iterator reverse_iterator; |
117 | typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; |
118 | typedef typename implementation_defined::node_traits node_traits; |
119 | typedef typename implementation_defined::node node; |
120 | typedef typename implementation_defined::node_ptr node_ptr; |
121 | typedef typename implementation_defined::const_node_ptr const_node_ptr; |
122 | typedef BOOST_INTRUSIVE_IMPDEF(treap_algorithms<node_traits>) node_algorithms; |
123 | typedef BOOST_INTRUSIVE_IMPDEF(typename get_prio_type::type) priority_compare; |
124 | |
125 | static const bool constant_time_size = implementation_defined::constant_time_size; |
126 | static const bool stateful_value_traits = implementation_defined::stateful_value_traits; |
127 | static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; |
128 | |
129 | typedef detail::key_nodeptr_comp<priority_compare, value_traits> value_node_prio_comp_t; |
130 | |
131 | template<class KeyPrioComp> |
132 | detail::key_nodeptr_comp<KeyPrioComp, value_traits> key_node_prio_comp(KeyPrioComp keypriocomp) const |
133 | { return detail::key_nodeptr_comp<KeyPrioComp, value_traits>(keypriocomp, &this->get_value_traits()); } |
134 | |
135 | value_node_prio_comp_t value_node_prio_comp() const |
136 | { return this->key_node_prio_comp(this->priv_pcomp()); } |
137 | |
138 | /// @cond |
139 | private: |
140 | |
141 | //noncopyable |
142 | BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_impl) |
143 | |
144 | const priority_compare &priv_pcomp() const |
145 | { return static_cast<const prio_base&>(*this).get(); } |
146 | |
147 | priority_compare &priv_pcomp() |
148 | { return static_cast<prio_base&>(*this).get(); } |
149 | |
150 | /// @endcond |
151 | |
152 | public: |
153 | typedef typename node_algorithms::insert_commit_data insert_commit_data; |
154 | |
155 | //! <b>Effects</b>: Constructs an empty container. |
156 | //! |
157 | //! <b>Complexity</b>: Constant. |
158 | //! |
159 | //! <b>Throws</b>: If value_traits::node_traits::node |
160 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) |
161 | //! or the copy constructor of the value_compare/priority_compare objects throw. Basic guarantee. |
162 | explicit treap_impl( const key_compare &cmp = key_compare() |
163 | , const priority_compare &pcmp = priority_compare() |
164 | , const value_traits &v_traits = value_traits()) |
165 | : tree_type(cmp, v_traits), prio_base(pcmp) |
166 | {} |
167 | |
168 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. |
169 | //! cmp must be a comparison function that induces a strict weak ordering. |
170 | //! |
171 | //! <b>Effects</b>: Constructs an empty container and inserts elements from |
172 | //! [b, e). |
173 | //! |
174 | //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using |
175 | //! comp and otherwise N * log N, where N is the distance between first and last. |
176 | //! |
177 | //! <b>Throws</b>: If value_traits::node_traits::node |
178 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) |
179 | //! or the copy constructor/operator() of the key_compare/priority_compare objects |
180 | //! throw. Basic guarantee. |
181 | template<class Iterator> |
182 | treap_impl( bool unique, Iterator b, Iterator e |
183 | , const key_compare &cmp = key_compare() |
184 | , const priority_compare &pcmp = priority_compare() |
185 | , const value_traits &v_traits = value_traits()) |
186 | : tree_type(cmp, v_traits), prio_base(pcmp) |
187 | { |
188 | if(unique) |
189 | this->insert_unique(b, e); |
190 | else |
191 | this->insert_equal(b, e); |
192 | } |
193 | |
194 | //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) |
195 | treap_impl(BOOST_RV_REF(treap_impl) x) |
196 | : tree_type(BOOST_MOVE_BASE(tree_type, x)) |
197 | , prio_base(::boost::move(x.priv_pcomp())) |
198 | {} |
199 | |
200 | //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) |
201 | treap_impl& operator=(BOOST_RV_REF(treap_impl) x) |
202 | { this->swap(x); return *this; } |
203 | |
204 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
205 | //! @copydoc ::boost::intrusive::bstree::~bstree() |
206 | ~treap_impl(); |
207 | |
208 | //! @copydoc ::boost::intrusive::bstree::begin() |
209 | iterator begin(); |
210 | |
211 | //! @copydoc ::boost::intrusive::bstree::begin()const |
212 | const_iterator begin() const; |
213 | |
214 | //! @copydoc ::boost::intrusive::bstree::cbegin()const |
215 | const_iterator cbegin() const; |
216 | |
217 | //! @copydoc ::boost::intrusive::bstree::end() |
218 | iterator end(); |
219 | |
220 | //! @copydoc ::boost::intrusive::bstree::end()const |
221 | const_iterator end() const; |
222 | |
223 | //! @copydoc ::boost::intrusive::bstree::cend()const |
224 | const_iterator cend() const; |
225 | #endif |
226 | |
227 | //! <b>Effects</b>: Returns an iterator pointing to the highest priority object of the treap. |
228 | //! |
229 | //! <b>Complexity</b>: Constant. |
230 | //! |
231 | //! <b>Throws</b>: Nothing. |
232 | iterator top() |
233 | { return this->tree_type::root(); } |
234 | |
235 | //! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the treap.. |
236 | //! |
237 | //! <b>Complexity</b>: Constant. |
238 | //! |
239 | //! <b>Throws</b>: Nothing. |
240 | const_iterator top() const |
241 | { return this->ctop(); } |
242 | |
243 | //! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the treap.. |
244 | //! |
245 | //! <b>Complexity</b>: Constant. |
246 | //! |
247 | //! <b>Throws</b>: Nothing. |
248 | const_iterator ctop() const |
249 | { return this->tree_type::root(); } |
250 | |
251 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
252 | //! @copydoc ::boost::intrusive::bstree::rbegin() |
253 | reverse_iterator rbegin(); |
254 | |
255 | //! @copydoc ::boost::intrusive::bstree::rbegin()const |
256 | const_reverse_iterator rbegin() const; |
257 | |
258 | //! @copydoc ::boost::intrusive::bstree::crbegin()const |
259 | const_reverse_iterator crbegin() const; |
260 | |
261 | //! @copydoc ::boost::intrusive::bstree::rend() |
262 | reverse_iterator rend(); |
263 | |
264 | //! @copydoc ::boost::intrusive::bstree::rend()const |
265 | const_reverse_iterator rend() const; |
266 | |
267 | //! @copydoc ::boost::intrusive::bstree::crend()const |
268 | const_reverse_iterator crend() const; |
269 | #endif |
270 | |
271 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the highest priority object of the |
272 | //! reversed treap. |
273 | //! |
274 | //! <b>Complexity</b>: Constant. |
275 | //! |
276 | //! <b>Throws</b>: Nothing. |
277 | reverse_iterator rtop() |
278 | { return reverse_iterator(this->top()); } |
279 | |
280 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority objec |
281 | //! of the reversed treap. |
282 | //! |
283 | //! <b>Complexity</b>: Constant. |
284 | //! |
285 | //! <b>Throws</b>: Nothing. |
286 | const_reverse_iterator rtop() const |
287 | { return const_reverse_iterator(this->top()); } |
288 | |
289 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority object |
290 | //! of the reversed treap. |
291 | //! |
292 | //! <b>Complexity</b>: Constant. |
293 | //! |
294 | //! <b>Throws</b>: Nothing. |
295 | const_reverse_iterator crtop() const |
296 | { return const_reverse_iterator(this->top()); } |
297 | |
298 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
299 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) |
300 | static treap_impl &container_from_end_iterator(iterator end_iterator); |
301 | |
302 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) |
303 | static const treap_impl &container_from_end_iterator(const_iterator end_iterator); |
304 | |
305 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) |
306 | static treap_impl &container_from_iterator(iterator it); |
307 | |
308 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) |
309 | static const treap_impl &container_from_iterator(const_iterator it); |
310 | |
311 | //! @copydoc ::boost::intrusive::bstree::key_comp()const |
312 | key_compare key_comp() const; |
313 | |
314 | //! @copydoc ::boost::intrusive::bstree::value_comp()const |
315 | value_compare value_comp() const; |
316 | |
317 | //! @copydoc ::boost::intrusive::bstree::empty()const |
318 | bool empty() const; |
319 | |
320 | //! @copydoc ::boost::intrusive::bstree::size()const |
321 | size_type size() const; |
322 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
323 | |
324 | //! <b>Effects</b>: Returns the priority_compare object used by the container. |
325 | //! |
326 | //! <b>Complexity</b>: Constant. |
327 | //! |
328 | //! <b>Throws</b>: If priority_compare copy-constructor throws. |
329 | priority_compare priority_comp() const |
330 | { return this->priv_pcomp(); } |
331 | |
332 | //! <b>Effects</b>: Swaps the contents of two treaps. |
333 | //! |
334 | //! <b>Complexity</b>: Constant. |
335 | //! |
336 | //! <b>Throws</b>: If the comparison functor's swap call throws. |
337 | void swap(treap_impl& other) |
338 | { |
339 | tree_type::swap(other); |
340 | //This can throw |
341 | ::boost::adl_move_swap(this->priv_pcomp(), other.priv_pcomp()); |
342 | } |
343 | |
344 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
345 | //! Cloner should yield to nodes equivalent to the original nodes. |
346 | //! |
347 | //! <b>Effects</b>: Erases all the elements from *this |
348 | //! calling Disposer::operator()(pointer), clones all the |
349 | //! elements from src calling Cloner::operator()(const_reference ) |
350 | //! and inserts them on *this. Copies the predicate from the source container. |
351 | //! |
352 | //! If cloner throws, all cloned elements are unlinked and disposed |
353 | //! calling Disposer::operator()(pointer). |
354 | //! |
355 | //! <b>Complexity</b>: Linear to erased plus inserted elements. |
356 | //! |
357 | //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. |
358 | template <class Cloner, class Disposer> |
359 | void clone_from(const treap_impl &src, Cloner cloner, Disposer disposer) |
360 | { |
361 | tree_type::clone_from(src, cloner, disposer); |
362 | this->priv_pcomp() = src.priv_pcomp(); |
363 | } |
364 | |
365 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
366 | //! Cloner should yield to nodes equivalent to the original nodes. |
367 | //! |
368 | //! <b>Effects</b>: Erases all the elements from *this |
369 | //! calling Disposer::operator()(pointer), clones all the |
370 | //! elements from src calling Cloner::operator()(reference) |
371 | //! and inserts them on *this. Copies the predicate from the source container. |
372 | //! |
373 | //! If cloner throws, all cloned elements are unlinked and disposed |
374 | //! calling Disposer::operator()(pointer). |
375 | //! |
376 | //! <b>Complexity</b>: Linear to erased plus inserted elements. |
377 | //! |
378 | //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. |
379 | template <class Cloner, class Disposer> |
380 | void clone_from(BOOST_RV_REF(treap_impl) src, Cloner cloner, Disposer disposer) |
381 | { |
382 | tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); |
383 | this->priv_pcomp() = ::boost::move(src.priv_pcomp()); |
384 | } |
385 | |
386 | //! <b>Requires</b>: value must be an lvalue |
387 | //! |
388 | //! <b>Effects</b>: Inserts value into the container before the upper bound. |
389 | //! |
390 | //! <b>Complexity</b>: Average complexity for insert element is at |
391 | //! most logarithmic. |
392 | //! |
393 | //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. Strong guarantee. |
394 | //! |
395 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
396 | //! No copy-constructors are called. |
397 | iterator insert_equal(reference value) |
398 | { |
399 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
400 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
401 | iterator ret |
402 | ( node_algorithms::insert_equal_upper_bound |
403 | ( this->tree_type::header_ptr() |
404 | , to_insert |
405 | , this->key_node_comp(this->key_comp()) |
406 | , this->value_node_prio_comp()) |
407 | , this->priv_value_traits_ptr()); |
408 | this->tree_type::sz_traits().increment(); |
409 | return ret; |
410 | } |
411 | |
412 | //! <b>Requires</b>: value must be an lvalue, and "hint" must be |
413 | //! a valid iterator. |
414 | //! |
415 | //! <b>Effects</b>: Inserts x into the container, using "hint" as a hint to |
416 | //! where it will be inserted. If "hint" is the upper_bound |
417 | //! the insertion takes constant time (two comparisons in the worst case) |
418 | //! |
419 | //! <b>Complexity</b>: Logarithmic in general, but it is amortized |
420 | //! constant time if t is inserted immediately before hint. |
421 | //! |
422 | //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. Strong guarantee. |
423 | //! |
424 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
425 | //! No copy-constructors are called. |
426 | iterator insert_equal(const_iterator hint, reference value) |
427 | { |
428 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
429 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
430 | iterator ret |
431 | (node_algorithms::insert_equal |
432 | ( this->tree_type::header_ptr() |
433 | , hint.pointed_node() |
434 | , to_insert |
435 | , this->key_node_comp(this->key_comp()) |
436 | , this->value_node_prio_comp()) |
437 | , this->priv_value_traits_ptr()); |
438 | this->tree_type::sz_traits().increment(); |
439 | return ret; |
440 | } |
441 | |
442 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue |
443 | //! of type value_type. |
444 | //! |
445 | //! <b>Effects</b>: Inserts a each element of a range into the container |
446 | //! before the upper bound of the key of each element. |
447 | //! |
448 | //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the |
449 | //! size of the range. However, it is linear in N if the range is already sorted |
450 | //! by key_comp(). |
451 | //! |
452 | //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. |
453 | //! Strong guarantee. |
454 | //! |
455 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
456 | //! No copy-constructors are called. |
457 | template<class Iterator> |
458 | void insert_equal(Iterator b, Iterator e) |
459 | { |
460 | iterator iend(this->end()); |
461 | for (; b != e; ++b) |
462 | this->insert_equal(iend, *b); |
463 | } |
464 | |
465 | //! <b>Requires</b>: value must be an lvalue |
466 | //! |
467 | //! <b>Effects</b>: Inserts value into the container if the value |
468 | //! is not already present. |
469 | //! |
470 | //! <b>Complexity</b>: Average complexity for insert element is at |
471 | //! most logarithmic. |
472 | //! |
473 | //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. |
474 | //! Strong guarantee. |
475 | //! |
476 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
477 | //! No copy-constructors are called. |
478 | std::pair<iterator, bool> insert_unique(reference value) |
479 | { |
480 | insert_commit_data commit_data; |
481 | std::pair<iterator, bool> ret = this->insert_unique_check |
482 | (value, this->comp(), this->priv_pcomp(), commit_data); |
483 | if(!ret.second) |
484 | return ret; |
485 | return std::pair<iterator, bool> (this->insert_unique_commit(value, commit_data), true); |
486 | } |
487 | |
488 | //! <b>Requires</b>: value must be an lvalue, and "hint" must be |
489 | //! a valid iterator |
490 | //! |
491 | //! <b>Effects</b>: Tries to insert x into the container, using "hint" as a hint |
492 | //! to where it will be inserted. |
493 | //! |
494 | //! <b>Complexity</b>: Logarithmic in general, but it is amortized |
495 | //! constant time (two comparisons in the worst case) |
496 | //! if t is inserted immediately before hint. |
497 | //! |
498 | //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. |
499 | //! Strong guarantee. |
500 | //! |
501 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
502 | //! No copy-constructors are called. |
503 | iterator insert_unique(const_iterator hint, reference value) |
504 | { |
505 | insert_commit_data commit_data; |
506 | std::pair<iterator, bool> ret = this->insert_unique_check |
507 | (hint, value, this->comp(), this->priv_pcomp(), commit_data); |
508 | if(!ret.second) |
509 | return ret.first; |
510 | return this->insert_unique_commit(value, commit_data); |
511 | } |
512 | |
513 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue |
514 | //! of type value_type. |
515 | //! |
516 | //! <b>Effects</b>: Tries to insert each element of a range into the container. |
517 | //! |
518 | //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the |
519 | //! size of the range. However, it is linear in N if the range is already sorted |
520 | //! by key_comp(). |
521 | //! |
522 | //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. |
523 | //! Strong guarantee. |
524 | //! |
525 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
526 | //! No copy-constructors are called. |
527 | template<class Iterator> |
528 | void insert_unique(Iterator b, Iterator e) |
529 | { |
530 | if(this->empty()){ |
531 | iterator iend(this->end()); |
532 | for (; b != e; ++b) |
533 | this->insert_unique(iend, *b); |
534 | } |
535 | else{ |
536 | for (; b != e; ++b) |
537 | this->insert_unique(*b); |
538 | } |
539 | } |
540 | |
541 | //! <b>Requires</b>: comp must be a comparison function that induces |
542 | //! the same strict weak ordering as key_compare. |
543 | //! key_value_pcomp must be a comparison function that induces |
544 | //! the same strict weak ordering as priority_compare. The difference is that |
545 | //! key_value_pcomp and comp compare an arbitrary key with the contained values. |
546 | //! |
547 | //! <b>Effects</b>: Checks if a value can be inserted in the container, using |
548 | //! a user provided key instead of the value itself. |
549 | //! |
550 | //! <b>Returns</b>: If there is an equivalent value |
551 | //! returns a pair containing an iterator to the already present value |
552 | //! and false. If the value can be inserted returns true in the returned |
553 | //! pair boolean and fills "commit_data" that is meant to be used with |
554 | //! the "insert_commit" function. |
555 | //! |
556 | //! <b>Complexity</b>: Average complexity is at most logarithmic. |
557 | //! |
558 | //! <b>Throws</b>: If the comp or key_value_pcomp |
559 | //! ordering functions throw. Strong guarantee. |
560 | //! |
561 | //! <b>Notes</b>: This function is used to improve performance when constructing |
562 | //! a value_type is expensive: if there is an equivalent value |
563 | //! the constructed object must be discarded. Many times, the part of the |
564 | //! node that is used to impose the order is much cheaper to construct |
565 | //! than the value_type and this function offers the possibility to use that |
566 | //! part to check if the insertion will be successful. |
567 | //! |
568 | //! If the check is successful, the user can construct the value_type and use |
569 | //! "insert_commit" to insert the object in constant-time. This gives a total |
570 | //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). |
571 | //! |
572 | //! "commit_data" remains valid for a subsequent "insert_commit" only if no more |
573 | //! objects are inserted or erased from the container. |
574 | template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare> |
575 | std::pair<iterator, bool> insert_unique_check |
576 | ( const KeyType &key, KeyTypeKeyCompare comp |
577 | , KeyValuePrioCompare key_value_pcomp, insert_commit_data &commit_data) |
578 | { |
579 | std::pair<node_ptr, bool> const ret = |
580 | (node_algorithms::insert_unique_check |
581 | ( this->tree_type::header_ptr(), key |
582 | , this->key_node_comp(comp), this->key_node_prio_comp(key_value_pcomp), commit_data)); |
583 | return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second); |
584 | } |
585 | |
586 | //! <b>Requires</b>: comp must be a comparison function that induces |
587 | //! the same strict weak ordering as key_compare. |
588 | //! key_value_pcomp must be a comparison function that induces |
589 | //! the same strict weak ordering as priority_compare. The difference is that |
590 | //! key_value_pcomp and comp compare an arbitrary key with the contained values. |
591 | //! |
592 | //! <b>Effects</b>: Checks if a value can be inserted in the container, using |
593 | //! a user provided key instead of the value itself, using "hint" |
594 | //! as a hint to where it will be inserted. |
595 | //! |
596 | //! <b>Returns</b>: If there is an equivalent value |
597 | //! returns a pair containing an iterator to the already present value |
598 | //! and false. If the value can be inserted returns true in the returned |
599 | //! pair boolean and fills "commit_data" that is meant to be used with |
600 | //! the "insert_commit" function. |
601 | //! |
602 | //! <b>Complexity</b>: Logarithmic in general, but it's amortized |
603 | //! constant time if t is inserted immediately before hint. |
604 | //! |
605 | //! <b>Throws</b>: If the comp or key_value_pcomp |
606 | //! ordering functions throw. Strong guarantee. |
607 | //! |
608 | //! <b>Notes</b>: This function is used to improve performance when constructing |
609 | //! a value_type is expensive: if there is an equivalent value |
610 | //! the constructed object must be discarded. Many times, the part of the |
611 | //! constructing that is used to impose the order is much cheaper to construct |
612 | //! than the value_type and this function offers the possibility to use that key |
613 | //! to check if the insertion will be successful. |
614 | //! |
615 | //! If the check is successful, the user can construct the value_type and use |
616 | //! "insert_commit" to insert the object in constant-time. This can give a total |
617 | //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)). |
618 | //! |
619 | //! "commit_data" remains valid for a subsequent "insert_commit" only if no more |
620 | //! objects are inserted or erased from the container. |
621 | template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare> |
622 | std::pair<iterator, bool> insert_unique_check |
623 | ( const_iterator hint, const KeyType &key |
624 | , KeyTypeKeyCompare comp |
625 | , KeyValuePrioCompare key_value_pcomp |
626 | , insert_commit_data &commit_data) |
627 | { |
628 | std::pair<node_ptr, bool> const ret = |
629 | (node_algorithms::insert_unique_check |
630 | ( this->tree_type::header_ptr(), hint.pointed_node(), key |
631 | , this->key_node_comp(comp), this->key_node_prio_comp(key_value_pcomp), commit_data)); |
632 | return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second); |
633 | } |
634 | |
635 | //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data |
636 | //! must have been obtained from a previous call to "insert_check". |
637 | //! No objects should have been inserted or erased from the container between |
638 | //! the "insert_check" that filled "commit_data" and the call to "insert_commit". |
639 | //! |
640 | //! <b>Effects</b>: Inserts the value in the avl_set using the information obtained |
641 | //! from the "commit_data" that a previous "insert_check" filled. |
642 | //! |
643 | //! <b>Returns</b>: An iterator to the newly inserted object. |
644 | //! |
645 | //! <b>Complexity</b>: Constant time. |
646 | //! |
647 | //! <b>Throws</b>: Nothing |
648 | //! |
649 | //! <b>Notes</b>: This function has only sense if a "insert_check" has been |
650 | //! previously executed to fill "commit_data". No value should be inserted or |
651 | //! erased between the "insert_check" and "insert_commit" calls. |
652 | iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) |
653 | { |
654 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
655 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
656 | node_algorithms::insert_unique_commit(this->tree_type::header_ptr(), to_insert, commit_data); |
657 | this->tree_type::sz_traits().increment(); |
658 | return iterator(to_insert, this->priv_value_traits_ptr()); |
659 | } |
660 | |
661 | //! <b>Requires</b>: value must be an lvalue, "pos" must be |
662 | //! a valid iterator (or end) and must be the succesor of value |
663 | //! once inserted according to the predicate |
664 | //! |
665 | //! <b>Effects</b>: Inserts x into the container before "pos". |
666 | //! |
667 | //! <b>Complexity</b>: Constant time. |
668 | //! |
669 | //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee. |
670 | //! |
671 | //! <b>Note</b>: This function does not check preconditions so if "pos" is not |
672 | //! the successor of "value" container ordering invariant will be broken. |
673 | //! This is a low-level function to be used only for performance reasons |
674 | //! by advanced users. |
675 | iterator insert_before(const_iterator pos, reference value) |
676 | { |
677 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
678 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
679 | iterator ret |
680 | ( node_algorithms::insert_before |
681 | ( this->tree_type::header_ptr(), pos.pointed_node(), to_insert, this->value_node_prio_comp()) |
682 | , this->priv_value_traits_ptr()); |
683 | this->tree_type::sz_traits().increment(); |
684 | return ret; |
685 | } |
686 | |
687 | //! <b>Requires</b>: value must be an lvalue, and it must be no less |
688 | //! than the greatest inserted key |
689 | //! |
690 | //! <b>Effects</b>: Inserts x into the container in the last position. |
691 | //! |
692 | //! <b>Complexity</b>: Constant time. |
693 | //! |
694 | //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee. |
695 | //! |
696 | //! <b>Note</b>: This function does not check preconditions so if value is |
697 | //! less than the greatest inserted key container ordering invariant will be broken. |
698 | //! This function is slightly more efficient than using "insert_before". |
699 | //! This is a low-level function to be used only for performance reasons |
700 | //! by advanced users. |
701 | void push_back(reference value) |
702 | { |
703 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
704 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
705 | node_algorithms::push_back(this->tree_type::header_ptr(), to_insert, this->value_node_prio_comp()); |
706 | this->tree_type::sz_traits().increment(); |
707 | } |
708 | |
709 | //! <b>Requires</b>: value must be an lvalue, and it must be no greater |
710 | //! than the minimum inserted key |
711 | //! |
712 | //! <b>Effects</b>: Inserts x into the container in the first position. |
713 | //! |
714 | //! <b>Complexity</b>: Constant time. |
715 | //! |
716 | //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee. |
717 | //! |
718 | //! <b>Note</b>: This function does not check preconditions so if value is |
719 | //! greater than the minimum inserted key container ordering invariant will be broken. |
720 | //! This function is slightly more efficient than using "insert_before". |
721 | //! This is a low-level function to be used only for performance reasons |
722 | //! by advanced users. |
723 | void push_front(reference value) |
724 | { |
725 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
726 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
727 | node_algorithms::push_front(this->tree_type::header_ptr(), to_insert, this->value_node_prio_comp()); |
728 | this->tree_type::sz_traits().increment(); |
729 | } |
730 | |
731 | //! <b>Effects</b>: Erases the element pointed to by i. |
732 | //! |
733 | //! <b>Complexity</b>: Average complexity for erase element is constant time. |
734 | //! |
735 | //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. |
736 | //! |
737 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
738 | //! to the erased elements. No destructors are called. |
739 | iterator erase(const_iterator i) |
740 | { |
741 | const_iterator ret(i); |
742 | ++ret; |
743 | node_ptr to_erase(i.pointed_node()); |
744 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(to_erase)); |
745 | node_algorithms::erase(this->tree_type::header_ptr(), to_erase, this->value_node_prio_comp()); |
746 | this->tree_type::sz_traits().decrement(); |
747 | if(safemode_or_autounlink) |
748 | node_algorithms::init(to_erase); |
749 | return ret.unconst(); |
750 | } |
751 | |
752 | //! <b>Effects</b>: Erases the range pointed to by b end e. |
753 | //! |
754 | //! <b>Complexity</b>: Average complexity for erase range is at most |
755 | //! O(log(size() + N)), where N is the number of elements in the range. |
756 | //! |
757 | //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. |
758 | //! |
759 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
760 | //! to the erased elements. No destructors are called. |
761 | iterator erase(const_iterator b, const_iterator e) |
762 | { size_type n; return private_erase(b, e, n); } |
763 | |
764 | //! <b>Effects</b>: Erases all the elements with the given value. |
765 | //! |
766 | //! <b>Returns</b>: The number of erased elements. |
767 | //! |
768 | //! <b>Complexity</b>: O(log(size() + N). |
769 | //! |
770 | //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. |
771 | //! |
772 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
773 | //! to the erased elements. No destructors are called. |
774 | size_type erase(const key_type &key) |
775 | { return this->erase(key, this->key_comp()); } |
776 | |
777 | //! <b>Effects</b>: Erases all the elements with the given key. |
778 | //! according to the comparison functor "comp". |
779 | //! |
780 | //! <b>Returns</b>: The number of erased elements. |
781 | //! |
782 | //! <b>Complexity</b>: O(log(size() + N). |
783 | //! |
784 | //! <b>Throws</b>: if the internal priority_compare function throws. |
785 | //! Equivalent guarantee to <i>while(beg != end) erase(beg++);</i> |
786 | //! |
787 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
788 | //! to the erased elements. No destructors are called. |
789 | template<class KeyType, class KeyTypeKeyCompare> |
790 | BOOST_INTRUSIVE_DOC1ST(size_type |
791 | , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) |
792 | erase(const KeyType& key, KeyTypeKeyCompare comp) |
793 | { |
794 | std::pair<iterator,iterator> p = this->equal_range(key, comp); |
795 | size_type n; |
796 | private_erase(p.first, p.second, n); |
797 | return n; |
798 | } |
799 | |
800 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
801 | //! |
802 | //! <b>Effects</b>: Erases the element pointed to by i. |
803 | //! Disposer::operator()(pointer) is called for the removed element. |
804 | //! |
805 | //! <b>Complexity</b>: Average complexity for erase element is constant time. |
806 | //! |
807 | //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. |
808 | //! |
809 | //! <b>Note</b>: Invalidates the iterators |
810 | //! to the erased elements. |
811 | template<class Disposer> |
812 | iterator erase_and_dispose(const_iterator i, Disposer disposer) |
813 | { |
814 | node_ptr to_erase(i.pointed_node()); |
815 | iterator ret(this->erase(i)); |
816 | disposer(this->get_value_traits().to_value_ptr(to_erase)); |
817 | return ret; |
818 | } |
819 | |
820 | #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
821 | template<class Disposer> |
822 | iterator erase_and_dispose(iterator i, Disposer disposer) |
823 | { return this->erase_and_dispose(const_iterator(i), disposer); } |
824 | #endif |
825 | |
826 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
827 | //! |
828 | //! <b>Effects</b>: Erases the range pointed to by b end e. |
829 | //! Disposer::operator()(pointer) is called for the removed elements. |
830 | //! |
831 | //! <b>Complexity</b>: Average complexity for erase range is at most |
832 | //! O(log(size() + N)), where N is the number of elements in the range. |
833 | //! |
834 | //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. |
835 | //! |
836 | //! <b>Note</b>: Invalidates the iterators |
837 | //! to the erased elements. |
838 | template<class Disposer> |
839 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) |
840 | { size_type n; return private_erase(b, e, n, disposer); } |
841 | |
842 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
843 | //! |
844 | //! <b>Effects</b>: Erases all the elements with the given value. |
845 | //! Disposer::operator()(pointer) is called for the removed elements. |
846 | //! |
847 | //! <b>Returns</b>: The number of erased elements. |
848 | //! |
849 | //! <b>Complexity</b>: O(log(size() + N). |
850 | //! |
851 | //! <b>Throws</b>: if the priority_compare function throws then weak guarantee and heap invariants are broken. |
852 | //! The safest thing would be to clear or destroy the container. |
853 | //! |
854 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
855 | //! to the erased elements. No destructors are called. |
856 | template<class Disposer> |
857 | size_type erase_and_dispose(const key_type &key, Disposer disposer) |
858 | { |
859 | std::pair<iterator,iterator> p = this->equal_range(key); |
860 | size_type n; |
861 | private_erase(p.first, p.second, n, disposer); |
862 | return n; |
863 | } |
864 | |
865 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
866 | //! |
867 | //! <b>Effects</b>: Erases all the elements with the given key. |
868 | //! according to the comparison functor "comp". |
869 | //! Disposer::operator()(pointer) is called for the removed elements. |
870 | //! |
871 | //! <b>Returns</b>: The number of erased elements. |
872 | //! |
873 | //! <b>Complexity</b>: O(log(size() + N). |
874 | //! |
875 | //! <b>Throws</b>: if the priority_compare function throws then weak guarantee and heap invariants are broken. |
876 | //! The safest thing would be to clear or destroy the container. |
877 | //! |
878 | //! <b>Note</b>: Invalidates the iterators |
879 | //! to the erased elements. |
880 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> |
881 | BOOST_INTRUSIVE_DOC1ST(size_type |
882 | , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) |
883 | erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer) |
884 | { |
885 | std::pair<iterator,iterator> p = this->equal_range(key, comp); |
886 | size_type n; |
887 | private_erase(p.first, p.second, n, disposer); |
888 | return n; |
889 | } |
890 | |
891 | //! <b>Effects</b>: Erases all of the elements. |
892 | //! |
893 | //! <b>Complexity</b>: Linear to the number of elements on the container. |
894 | //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. |
895 | //! |
896 | //! <b>Throws</b>: Nothing. |
897 | //! |
898 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
899 | //! to the erased elements. No destructors are called. |
900 | void clear() |
901 | { tree_type::clear(); } |
902 | |
903 | //! <b>Effects</b>: Erases all of the elements calling disposer(p) for |
904 | //! each node to be erased. |
905 | //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)), |
906 | //! where N is the number of elements in the container. |
907 | //! |
908 | //! <b>Throws</b>: Nothing. |
909 | //! |
910 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
911 | //! to the erased elements. Calls N times to disposer functor. |
912 | template<class Disposer> |
913 | void clear_and_dispose(Disposer disposer) |
914 | { |
915 | node_algorithms::clear_and_dispose(this->tree_type::header_ptr() |
916 | , detail::node_disposer<Disposer, value_traits, TreapAlgorithms>(disposer, &this->get_value_traits())); |
917 | node_algorithms::init_header(this->tree_type::header_ptr()); |
918 | this->tree_type::sz_traits().set_size(0); |
919 | } |
920 | |
921 | //! @copydoc ::boost::intrusive::bstree::check(ExtraChecker)const |
922 | template <class ExtraChecker> |
923 | void check(ExtraChecker ) const |
924 | { |
925 | tree_type::check(detail::treap_node_extra_checker |
926 | <ValueTraits, value_node_prio_comp_t, ExtraChecker>(this->value_node_prio_comp(), extra_checker)); |
927 | } |
928 | |
929 | //! @copydoc ::boost::intrusive::bstree::check()const |
930 | void check() const |
931 | { check(detail::empty_node_checker<ValueTraits>()); } |
932 | |
933 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
934 | //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const |
935 | size_type count(const key_type &key) const; |
936 | |
937 | //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const |
938 | template<class KeyType, class KeyTypeKeyCompare> |
939 | size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; |
940 | |
941 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) |
942 | iterator lower_bound(const key_type &key); |
943 | |
944 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) |
945 | template<class KeyType, class KeyTypeKeyCompare> |
946 | iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); |
947 | |
948 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const |
949 | const_iterator lower_bound(const key_type &key) const; |
950 | |
951 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const |
952 | template<class KeyType, class KeyTypeKeyCompare> |
953 | const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; |
954 | |
955 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) |
956 | iterator upper_bound(const key_type &key); |
957 | |
958 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) |
959 | template<class KeyType, class KeyTypeKeyCompare> |
960 | iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); |
961 | |
962 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const |
963 | const_iterator upper_bound(const key_type &key) const; |
964 | |
965 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const |
966 | template<class KeyType, class KeyTypeKeyCompare> |
967 | const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; |
968 | |
969 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &) |
970 | iterator find(const key_type &key); |
971 | |
972 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) |
973 | template<class KeyType, class KeyTypeKeyCompare> |
974 | iterator find(const KeyType& key, KeyTypeKeyCompare comp); |
975 | |
976 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const |
977 | const_iterator find(const key_type &key) const; |
978 | |
979 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const |
980 | template<class KeyType, class KeyTypeKeyCompare> |
981 | const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; |
982 | |
983 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) |
984 | std::pair<iterator,iterator> equal_range(const key_type &key); |
985 | |
986 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) |
987 | template<class KeyType, class KeyTypeKeyCompare> |
988 | std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); |
989 | |
990 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const |
991 | std::pair<const_iterator, const_iterator> |
992 | equal_range(const key_type &key) const; |
993 | |
994 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const |
995 | template<class KeyType, class KeyTypeKeyCompare> |
996 | std::pair<const_iterator, const_iterator> |
997 | equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; |
998 | |
999 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) |
1000 | std::pair<iterator,iterator> bounded_range |
1001 | (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed); |
1002 | |
1003 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) |
1004 | template<class KeyType, class KeyTypeKeyCompare> |
1005 | std::pair<iterator,iterator> bounded_range |
1006 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); |
1007 | |
1008 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const |
1009 | std::pair<const_iterator, const_iterator> |
1010 | bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; |
1011 | |
1012 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const |
1013 | template<class KeyType, class KeyTypeKeyCompare> |
1014 | std::pair<const_iterator, const_iterator> bounded_range |
1015 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; |
1016 | |
1017 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) |
1018 | static iterator s_iterator_to(reference value); |
1019 | |
1020 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) |
1021 | static const_iterator s_iterator_to(const_reference value); |
1022 | |
1023 | //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) |
1024 | iterator iterator_to(reference value); |
1025 | |
1026 | //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const |
1027 | const_iterator iterator_to(const_reference value) const; |
1028 | |
1029 | //! @copydoc ::boost::intrusive::bstree::init_node(reference) |
1030 | static void init_node(reference value); |
1031 | |
1032 | //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance |
1033 | pointer unlink_leftmost_without_rebalance(); |
1034 | |
1035 | //! @copydoc ::boost::intrusive::bstree::replace_node |
1036 | void replace_node(iterator replace_this, reference with_this); |
1037 | |
1038 | //! @copydoc ::boost::intrusive::bstree::remove_node |
1039 | void remove_node(reference value); |
1040 | |
1041 | friend bool operator< (const treap_impl &x, const treap_impl &y); |
1042 | |
1043 | friend bool operator==(const treap_impl &x, const treap_impl &y); |
1044 | |
1045 | friend bool operator!= (const treap_impl &x, const treap_impl &y); |
1046 | |
1047 | friend bool operator>(const treap_impl &x, const treap_impl &y); |
1048 | |
1049 | friend bool operator<=(const treap_impl &x, const treap_impl &y); |
1050 | |
1051 | friend bool operator>=(const treap_impl &x, const treap_impl &y); |
1052 | |
1053 | friend void swap(treap_impl &x, treap_impl &y); |
1054 | |
1055 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
1056 | |
1057 | /// @cond |
1058 | private: |
1059 | template<class Disposer> |
1060 | iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer) |
1061 | { |
1062 | for(n = 0; b != e; ++n) |
1063 | this->erase_and_dispose(b++, disposer); |
1064 | return b.unconst(); |
1065 | } |
1066 | |
1067 | iterator private_erase(const_iterator b, const_iterator e, size_type &n) |
1068 | { |
1069 | for(n = 0; b != e; ++n) |
1070 | this->erase(b++); |
1071 | return b.unconst(); |
1072 | } |
1073 | /// @endcond |
1074 | }; |
1075 | |
1076 | |
1077 | //! Helper metafunction to define a \c treap that yields to the same type when the |
1078 | //! same options (either explicitly or implicitly) are used. |
1079 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1080 | template<class T, class ...Options> |
1081 | #else |
1082 | template<class T, class O1 = void, class O2 = void |
1083 | , class O3 = void, class O4 = void |
1084 | , class O5 = void, class O6 = void> |
1085 | #endif |
1086 | struct make_treap |
1087 | { |
1088 | typedef typename pack_options |
1089 | < treap_defaults, |
1090 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1091 | O1, O2, O3, O4, O5, O6 |
1092 | #else |
1093 | Options... |
1094 | #endif |
1095 | >::type packed_options; |
1096 | |
1097 | typedef typename detail::get_value_traits |
1098 | <T, typename packed_options::proto_value_traits>::type value_traits; |
1099 | |
1100 | typedef treap_impl |
1101 | < value_traits |
1102 | , typename packed_options::key_of_value |
1103 | , typename packed_options::compare |
1104 | , typename packed_options::priority |
1105 | , typename packed_options::size_type |
1106 | , packed_options::constant_time_size |
1107 | , typename packed_options::header_holder_type |
1108 | > implementation_defined; |
1109 | /// @endcond |
1110 | typedef implementation_defined type; |
1111 | }; |
1112 | |
1113 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
1114 | |
1115 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1116 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> |
1117 | #else |
1118 | template<class T, class ...Options> |
1119 | #endif |
1120 | class treap |
1121 | : public make_treap<T, |
1122 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1123 | O1, O2, O3, O4, O5, O6 |
1124 | #else |
1125 | Options... |
1126 | #endif |
1127 | >::type |
1128 | { |
1129 | typedef typename make_treap |
1130 | <T, |
1131 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1132 | O1, O2, O3, O4, O5, O6 |
1133 | #else |
1134 | Options... |
1135 | #endif |
1136 | >::type Base; |
1137 | BOOST_MOVABLE_BUT_NOT_COPYABLE(treap) |
1138 | |
1139 | public: |
1140 | typedef typename Base::key_compare key_compare; |
1141 | typedef typename Base::priority_compare priority_compare; |
1142 | typedef typename Base::value_traits value_traits; |
1143 | typedef typename Base::iterator iterator; |
1144 | typedef typename Base::const_iterator const_iterator; |
1145 | typedef typename Base::reverse_iterator reverse_iterator; |
1146 | typedef typename Base::const_reverse_iterator const_reverse_iterator; |
1147 | |
1148 | //Assert if passed value traits are compatible with the type |
1149 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); |
1150 | |
1151 | explicit treap( const key_compare &cmp = key_compare() |
1152 | , const priority_compare &pcmp = priority_compare() |
1153 | , const value_traits &v_traits = value_traits()) |
1154 | : Base(cmp, pcmp, v_traits) |
1155 | {} |
1156 | |
1157 | template<class Iterator> |
1158 | treap( bool unique, Iterator b, Iterator e |
1159 | , const key_compare &cmp = key_compare() |
1160 | , const priority_compare &pcmp = priority_compare() |
1161 | , const value_traits &v_traits = value_traits()) |
1162 | : Base(unique, b, e, cmp, pcmp, v_traits) |
1163 | {} |
1164 | |
1165 | treap(BOOST_RV_REF(treap) x) |
1166 | : Base(BOOST_MOVE_BASE(Base, x)) |
1167 | {} |
1168 | |
1169 | treap& operator=(BOOST_RV_REF(treap) x) |
1170 | { return static_cast<treap&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } |
1171 | |
1172 | template <class Cloner, class Disposer> |
1173 | void clone_from(const treap &src, Cloner cloner, Disposer disposer) |
1174 | { Base::clone_from(src, cloner, disposer); } |
1175 | |
1176 | template <class Cloner, class Disposer> |
1177 | void clone_from(BOOST_RV_REF(treap) src, Cloner cloner, Disposer disposer) |
1178 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } |
1179 | |
1180 | static treap &container_from_end_iterator(iterator end_iterator) |
1181 | { return static_cast<treap &>(Base::container_from_end_iterator(end_iterator)); } |
1182 | |
1183 | static const treap &container_from_end_iterator(const_iterator end_iterator) |
1184 | { return static_cast<const treap &>(Base::container_from_end_iterator(end_iterator)); } |
1185 | |
1186 | static treap &container_from_iterator(iterator it) |
1187 | { return static_cast<treap &>(Base::container_from_iterator(it)); } |
1188 | |
1189 | static const treap &container_from_iterator(const_iterator it) |
1190 | { return static_cast<const treap &>(Base::container_from_iterator(it)); } |
1191 | }; |
1192 | |
1193 | #endif |
1194 | |
1195 | } //namespace intrusive |
1196 | } //namespace boost |
1197 | |
1198 | #include <boost/intrusive/detail/config_end.hpp> |
1199 | |
1200 | #endif //BOOST_INTRUSIVE_TREAP_HPP |
1201 | |