1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2007-2009
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_SPLAYTREE_HPP
13 #define BOOST_INTRUSIVE_SPLAYTREE_HPP
14
15 #include <boost/intrusive/detail/config_begin.hpp>
16 #include <functional>
17 #include <iterator>
18 #include <utility>
19 #include <cstddef>
20 #include <algorithm>
21 #include <boost/intrusive/detail/assert.hpp>
22 #include <boost/static_assert.hpp>
23 #include <boost/intrusive/intrusive_fwd.hpp>
24 #include <boost/intrusive/detail/pointer_to_other.hpp>
25 #include <boost/intrusive/splay_set_hook.hpp>
26 #include <boost/intrusive/detail/tree_node.hpp>
27 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
28 #include <boost/intrusive/detail/clear_on_destructor_base.hpp>
29 #include <boost/intrusive/detail/mpl.hpp>
30 #include <boost/intrusive/options.hpp>
31 #include <boost/intrusive/splaytree_algorithms.hpp>
32 #include <boost/intrusive/link_mode.hpp>
33
34
35 namespace boost {
36 namespace intrusive {
37
38 /// @cond
39
40 template <class ValueTraits, class Compare, class SizeType, bool ConstantTimeSize>
41 struct splaysetopt
42 {
43 typedef ValueTraits value_traits;
44 typedef Compare compare;
45 typedef SizeType size_type;
46 static const bool constant_time_size = ConstantTimeSize;
47 };
48
49 template <class T>
50 struct splay_set_defaults
51 : pack_options
52 < none
53 , base_hook<detail::default_splay_set_hook>
54 , constant_time_size<true>
55 , size_type<std::size_t>
56 , compare<std::less<T> >
57 >::type
58 {};
59
60 /// @endcond
61
62 //! The class template splaytree is an intrusive splay tree container that
63 //! is used to construct intrusive splay_set and splay_multiset containers. The no-throw
64 //! guarantee holds only, if the value_compare object
65 //! doesn't throw.
66 //!
67 //! The template parameter \c T is the type to be managed by the container.
68 //! The user can specify additional options and if no options are provided
69 //! default options are used.
70 //!
71 //! The container supports the following options:
72 //! \c base_hook<>/member_hook<>/value_traits<>,
73 //! \c constant_time_size<>, \c size_type<> and
74 //! \c compare<>.
75 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
76 template<class T, class ...Options>
77 #else
78 template<class Config>
79 #endif
80 class splaytree_impl
81 : private detail::clear_on_destructor_base<splaytree_impl<Config> >
82 {
83 template<class C> friend class detail::clear_on_destructor_base;
84 public:
85 typedef typename Config::value_traits value_traits;
86 /// @cond
87 static const bool external_value_traits =
88 detail::external_value_traits_is_true<value_traits>::value;
89 typedef typename detail::eval_if_c
90 < external_value_traits
91 , detail::eval_value_traits<value_traits>
92 , detail::identity<value_traits>
93 >::type real_value_traits;
94 /// @endcond
95 typedef typename real_value_traits::pointer pointer;
96 typedef typename real_value_traits::const_pointer const_pointer;
97 typedef typename std::iterator_traits<pointer>::value_type value_type;
98 typedef value_type key_type;
99 typedef typename std::iterator_traits<pointer>::reference reference;
100 typedef typename std::iterator_traits<const_pointer>::reference const_reference;
101 typedef typename std::iterator_traits<pointer>::difference_type difference_type;
102 typedef typename Config::size_type size_type;
103 typedef typename Config::compare value_compare;
104 typedef value_compare key_compare;
105 typedef tree_iterator<splaytree_impl, false> iterator;
106 typedef tree_iterator<splaytree_impl, true> const_iterator;
107 typedef std::reverse_iterator<iterator> reverse_iterator;
108 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
109 typedef typename real_value_traits::node_traits node_traits;
110 typedef typename node_traits::node node;
111 typedef typename boost::pointer_to_other
112 <pointer, node>::type node_ptr;
113 typedef typename boost::pointer_to_other
114 <node_ptr, const node>::type const_node_ptr;
115 typedef splaytree_algorithms<node_traits> node_algorithms;
116
117 static const bool constant_time_size = Config::constant_time_size;
118 static const bool stateful_value_traits = detail::is_stateful_value_traits<real_value_traits>::value;
119
120 /// @cond
121 private:
122 typedef detail::size_holder<constant_time_size, size_type> size_traits;
123
124 //noncopyable
125 splaytree_impl (const splaytree_impl&);
126 splaytree_impl operator =(const splaytree_impl&);
127
128 enum { safemode_or_autounlink =
129 (int)real_value_traits::link_mode == (int)auto_unlink ||
130 (int)real_value_traits::link_mode == (int)safe_link };
131
132 //Constant-time size is incompatible with auto-unlink hooks!
133 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)real_value_traits::link_mode == (int)auto_unlink)));
134
135 struct header_plus_size : public size_traits
136 { node header_; };
137
138 struct node_plus_pred_t : public detail::ebo_functor_holder<value_compare>
139 {
node_plus_pred_tboost::intrusive::splaytree_impl::node_plus_pred_t140 node_plus_pred_t(const value_compare &comp)
141 : detail::ebo_functor_holder<value_compare>(comp)
142 {}
143 header_plus_size header_plus_size_;
144 };
145
146 struct data_t : public splaytree_impl::value_traits
147 {
148 typedef typename splaytree_impl::value_traits value_traits;
data_tboost::intrusive::splaytree_impl::data_t149 data_t(const value_compare & comp, const value_traits &val_traits)
150 : value_traits(val_traits), node_plus_pred_(comp)
151 {}
152 node_plus_pred_t node_plus_pred_;
153 } data_;
154
priv_comp() const155 const value_compare &priv_comp() const
156 { return data_.node_plus_pred_.get(); }
157
priv_comp()158 value_compare &priv_comp()
159 { return data_.node_plus_pred_.get(); }
160
priv_header() const161 const node &priv_header() const
162 { return data_.node_plus_pred_.header_plus_size_.header_; }
163
priv_header()164 node &priv_header()
165 { return data_.node_plus_pred_.header_plus_size_.header_; }
166
uncast(const_node_ptr ptr)167 static node_ptr uncast(const_node_ptr ptr)
168 {
169 return node_ptr(const_cast<node*>(detail::boost_intrusive_get_pointer(ptr)));
170 }
171
priv_size_traits()172 size_traits &priv_size_traits()
173 { return data_.node_plus_pred_.header_plus_size_; }
174
priv_size_traits() const175 const size_traits &priv_size_traits() const
176 { return data_.node_plus_pred_.header_plus_size_; }
177
get_real_value_traits(detail::bool_<false>) const178 const real_value_traits &get_real_value_traits(detail::bool_<false>) const
179 { return data_; }
180
get_real_value_traits(detail::bool_<true>) const181 const real_value_traits &get_real_value_traits(detail::bool_<true>) const
182 { return data_.get_value_traits(*this); }
183
get_real_value_traits(detail::bool_<false>)184 real_value_traits &get_real_value_traits(detail::bool_<false>)
185 { return data_; }
186
get_real_value_traits(detail::bool_<true>)187 real_value_traits &get_real_value_traits(detail::bool_<true>)
188 { return data_.get_value_traits(*this); }
189
190 /// @endcond
191
192 public:
193
get_real_value_traits() const194 const real_value_traits &get_real_value_traits() const
195 { return this->get_real_value_traits(detail::bool_<external_value_traits>()); }
196
get_real_value_traits()197 real_value_traits &get_real_value_traits()
198 { return this->get_real_value_traits(detail::bool_<external_value_traits>()); }
199
200 typedef typename node_algorithms::insert_commit_data insert_commit_data;
201
202 //! <b>Effects</b>: Constructs an empty tree.
203 //!
204 //! <b>Complexity</b>: Constant.
205 //!
206 //! <b>Throws</b>: If value_traits::node_traits::node
207 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
208 //! or the copy constructorof the value_compare object throws. Basic guarantee.
splaytree_impl(const value_compare & cmp=value_compare (),const value_traits & v_traits=value_traits ())209 splaytree_impl( const value_compare &cmp = value_compare()
210 , const value_traits &v_traits = value_traits())
211 : data_(cmp, v_traits)
212 {
213 node_algorithms::init_header(&priv_header());
214 this->priv_size_traits().set_size(size_type(0));
215 }
216
217 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
218 //! cmp must be a comparison function that induces a strict weak ordering.
219 //!
220 //! <b>Effects</b>: Constructs an empty tree and inserts elements from
221 //! [b, e).
222 //!
223 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
224 //! comp and otherwise amortized N * log N, where N is the distance between first and last.
225 //!
226 //! <b>Throws</b>: If value_traits::node_traits::node
227 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
228 //! or the copy constructor/operator() of the value_compare object throws. Basic guarantee.
229 template<class Iterator>
splaytree_impl(bool unique,Iterator b,Iterator e,const value_compare & cmp=value_compare (),const value_traits & v_traits=value_traits ())230 splaytree_impl ( bool unique, Iterator b, Iterator e
231 , const value_compare &cmp = value_compare()
232 , const value_traits &v_traits = value_traits())
233 : data_(cmp, v_traits)
234 {
235 node_algorithms::init_header(&priv_header());
236 this->priv_size_traits().set_size(size_type(0));
237 if(unique)
238 this->insert_unique(b, e);
239 else
240 this->insert_equal(b, e);
241 }
242
243 //! <b>Effects</b>: Detaches all elements from this. The objects in the set
244 //! are not deleted (i.e. no destructors are called), but the nodes according to
245 //! the value_traits template parameter are reinitialized and thus can be reused.
246 //!
247 //! <b>Complexity</b>: Linear to the number of elements on the container.
248 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
249 //!
250 //! <b>Throws</b>: Nothing.
~splaytree_impl()251 ~splaytree_impl()
252 {}
253
254 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the tree.
255 //!
256 //! <b>Complexity</b>: Constant.
257 //!
258 //! <b>Throws</b>: Nothing.
begin()259 iterator begin()
260 { return iterator(node_algorithms::begin_node(&priv_header()), this); }
261
262 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the tree.
263 //!
264 //! <b>Complexity</b>: Constant.
265 //!
266 //! <b>Throws</b>: Nothing.
begin() const267 const_iterator begin() const
268 { return cbegin(); }
269
270 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the tree.
271 //!
272 //! <b>Complexity</b>: Constant.
273 //!
274 //! <b>Throws</b>: Nothing.
cbegin() const275 const_iterator cbegin() const
276 { return const_iterator(node_algorithms::begin_node(&priv_header()), this); }
277
278 //! <b>Effects</b>: Returns an iterator pointing to the end of the tree.
279 //!
280 //! <b>Complexity</b>: Constant.
281 //!
282 //! <b>Throws</b>: Nothing.
end()283 iterator end()
284 { return iterator (node_ptr(&priv_header()), this); }
285
286 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the tree.
287 //!
288 //! <b>Complexity</b>: Constant.
289 //!
290 //! <b>Throws</b>: Nothing.
end() const291 const_iterator end() const
292 { return cend(); }
293
294 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the tree.
295 //!
296 //! <b>Complexity</b>: Constant.
297 //!
298 //! <b>Throws</b>: Nothing.
cend() const299 const_iterator cend() const
300 { return const_iterator (uncast(const_node_ptr(&priv_header())), this); }
301
302 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
303 //! reversed tree.
304 //!
305 //! <b>Complexity</b>: Constant.
306 //!
307 //! <b>Throws</b>: Nothing.
rbegin()308 reverse_iterator rbegin()
309 { return reverse_iterator(end()); }
310
311 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
312 //! of the reversed tree.
313 //!
314 //! <b>Complexity</b>: Constant.
315 //!
316 //! <b>Throws</b>: Nothing.
rbegin() const317 const_reverse_iterator rbegin() const
318 { return const_reverse_iterator(end()); }
319
320 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
321 //! of the reversed tree.
322 //!
323 //! <b>Complexity</b>: Constant.
324 //!
325 //! <b>Throws</b>: Nothing.
crbegin() const326 const_reverse_iterator crbegin() const
327 { return const_reverse_iterator(end()); }
328
329 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
330 //! of the reversed tree.
331 //!
332 //! <b>Complexity</b>: Constant.
333 //!
334 //! <b>Throws</b>: Nothing.
rend()335 reverse_iterator rend()
336 { return reverse_iterator(begin()); }
337
338 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
339 //! of the reversed tree.
340 //!
341 //! <b>Complexity</b>: Constant.
342 //!
343 //! <b>Throws</b>: Nothing.
rend() const344 const_reverse_iterator rend() const
345 { return const_reverse_iterator(begin()); }
346
347 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
348 //! of the reversed tree.
349 //!
350 //! <b>Complexity</b>: Constant.
351 //!
352 //! <b>Throws</b>: Nothing.
crend() const353 const_reverse_iterator crend() const
354 { return const_reverse_iterator(begin()); }
355
356 //! <b>Precondition</b>: end_iterator must be a valid end iterator
357 //! of splaytree.
358 //!
359 //! <b>Effects</b>: Returns a const reference to the splaytree associated to the end iterator
360 //!
361 //! <b>Throws</b>: Nothing.
362 //!
363 //! <b>Complexity</b>: Constant.
container_from_end_iterator(iterator end_iterator)364 static splaytree_impl &container_from_end_iterator(iterator end_iterator)
365 { return priv_container_from_end_iterator(end_iterator); }
366
367 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
368 //! of splaytree.
369 //!
370 //! <b>Effects</b>: Returns a const reference to the splaytree associated to the end iterator
371 //!
372 //! <b>Throws</b>: Nothing.
373 //!
374 //! <b>Complexity</b>: Constant.
container_from_end_iterator(const_iterator end_iterator)375 static const splaytree_impl &container_from_end_iterator(const_iterator end_iterator)
376 { return priv_container_from_end_iterator(end_iterator); }
377
378 //! <b>Precondition</b>: it must be a valid iterator
379 //! of rbtree.
380 //!
381 //! <b>Effects</b>: Returns a const reference to the tree associated to the iterator
382 //!
383 //! <b>Throws</b>: Nothing.
384 //!
385 //! <b>Complexity</b>: Logarithmic.
container_from_iterator(iterator it)386 static splaytree_impl &container_from_iterator(iterator it)
387 { return priv_container_from_iterator(it); }
388
389 //! <b>Precondition</b>: it must be a valid end const_iterator
390 //! of rbtree.
391 //!
392 //! <b>Effects</b>: Returns a const reference to the tree associated to the iterator
393 //!
394 //! <b>Throws</b>: Nothing.
395 //!
396 //! <b>Complexity</b>: Logarithmic.
container_from_iterator(const_iterator it)397 static const splaytree_impl &container_from_iterator(const_iterator it)
398 { return priv_container_from_iterator(it); }
399
400 //! <b>Effects</b>: Returns the value_compare object used by the tree.
401 //!
402 //! <b>Complexity</b>: Constant.
403 //!
404 //! <b>Throws</b>: If value_compare copy-constructor throws.
value_comp() const405 value_compare value_comp() const
406 { return priv_comp(); }
407
408 //! <b>Effects</b>: Returns true if the container is empty.
409 //!
410 //! <b>Complexity</b>: Constant.
411 //!
412 //! <b>Throws</b>: Nothing.
empty() const413 bool empty() const
414 { return this->cbegin() == this->cend(); }
415
416 //! <b>Effects</b>: Returns the number of elements stored in the tree.
417 //!
418 //! <b>Complexity</b>: Linear to elements contained in *this
419 //! if constant-time size option is disabled. Constant time otherwise.
420 //!
421 //! <b>Throws</b>: Nothing.
size() const422 size_type size() const
423 {
424 if(constant_time_size){
425 return this->priv_size_traits().get_size();
426 }
427 else{
428 return (size_type)node_algorithms::size(const_node_ptr(&priv_header()));
429 }
430 }
431
432 //! <b>Effects</b>: Swaps the contents of two splaytrees.
433 //!
434 //! <b>Complexity</b>: Constant.
435 //!
436 //! <b>Throws</b>: If the comparison functor's swap call throws.
swap(splaytree_impl & other)437 void swap(splaytree_impl& other)
438 {
439 //This can throw
440 using std::swap;
441 swap(priv_comp(), priv_comp());
442 //These can't throw
443 node_algorithms::swap_tree(node_ptr(&priv_header()), node_ptr(&other.priv_header()));
444 if(constant_time_size){
445 size_type backup = this->priv_size_traits().get_size();
446 this->priv_size_traits().set_size(other.priv_size_traits().get_size());
447 other.priv_size_traits().set_size(backup);
448 }
449 }
450
451 //! <b>Requires</b>: value must be an lvalue
452 //!
453 //! <b>Effects</b>: Inserts value into the tree before the lower bound.
454 //!
455 //! <b>Complexity</b>: Average complexity for insert element is amortized
456 //! logarithmic.
457 //!
458 //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
459 //!
460 //! <b>Note</b>: Does not affect the validity of iterators and references.
461 //! No copy-constructors are called.
insert_equal(reference value)462 iterator insert_equal(reference value)
463 {
464 detail::key_nodeptr_comp<value_compare, splaytree_impl>
465 key_node_comp(priv_comp(), this);
466 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
467 if(safemode_or_autounlink)
468 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
469 iterator ret (node_algorithms::insert_equal_lower_bound
470 (node_ptr(&priv_header()), to_insert, key_node_comp), this);
471 this->priv_size_traits().increment();
472 return ret;
473 }
474
475 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
476 //! a valid iterator.
477 //!
478 //! <b>Effects</b>: Inserts x into the tree, using "hint" as a hint to
479 //! where it will be inserted. If "hint" is the upper_bound
480 //! the insertion takes constant time (two comparisons in the worst case)
481 //!
482 //! <b>Complexity</b>: Amortized logarithmic in general, but it is amortized
483 //! constant time if t is inserted immediately before hint.
484 //!
485 //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
486 //!
487 //! <b>Note</b>: Does not affect the validity of iterators and references.
488 //! No copy-constructors are called.
insert_equal(const_iterator hint,reference value)489 iterator insert_equal(const_iterator hint, reference value)
490 {
491 detail::key_nodeptr_comp<value_compare, splaytree_impl>
492 key_node_comp(priv_comp(), this);
493 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
494 if(safemode_or_autounlink)
495 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
496 iterator ret(node_algorithms::insert_equal
497 (node_ptr(&priv_header()), hint.pointed_node(), to_insert, key_node_comp), this);
498 this->priv_size_traits().increment();
499 return ret;
500 }
501
502 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
503 //! of type value_type.
504 //!
505 //! <b>Effects</b>: Inserts a each element of a range into the tree
506 //! before the upper bound of the key of each element.
507 //!
508 //! <b>Complexity</b>: Insert range is in general amortized O(N * log(N)), where N is the
509 //! size of the range. However, it is linear in N if the range is already sorted
510 //! by value_comp().
511 //!
512 //! <b>Throws</b>: Nothing.
513 //!
514 //! <b>Note</b>: Does not affect the validity of iterators and references.
515 //! No copy-constructors are called.
516 template<class Iterator>
insert_equal(Iterator b,Iterator e)517 void insert_equal(Iterator b, Iterator e)
518 {
519 if(this->empty()){
520 iterator end(this->end());
521 for (; b != e; ++b)
522 this->insert_equal(end, *b);
523 }
524 }
525
526 //! <b>Requires</b>: value must be an lvalue
527 //!
528 //! <b>Effects</b>: Inserts value into the tree if the value
529 //! is not already present.
530 //!
531 //! <b>Complexity</b>: Amortized logarithmic.
532 //!
533 //! <b>Throws</b>: Nothing.
534 //!
535 //! <b>Note</b>: Does not affect the validity of iterators and references.
536 //! No copy-constructors are called.
insert_unique(reference value)537 std::pair<iterator, bool> insert_unique(reference value)
538 {
539 insert_commit_data commit_data;
540 std::pair<iterator, bool> ret = insert_unique_check(value, priv_comp(), commit_data);
541 if(!ret.second)
542 return ret;
543 return std::pair<iterator, bool> (insert_unique_commit(value, commit_data), true);
544 }
545
546 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
547 //! a valid iterator
548 //!
549 //! <b>Effects</b>: Tries to insert x into the tree, using "hint" as a hint
550 //! to where it will be inserted.
551 //!
552 //! <b>Complexity</b>: Amortized logarithmic in general, but it is amortized
553 //! constant time (two comparisons in the worst case)
554 //! if t is inserted immediately before hint.
555 //!
556 //! <b>Throws</b>: Nothing.
557 //!
558 //! <b>Note</b>: Does not affect the validity of iterators and references.
559 //! No copy-constructors are called.
insert_unique(const_iterator hint,reference value)560 iterator insert_unique(const_iterator hint, reference value)
561 {
562 insert_commit_data commit_data;
563 std::pair<iterator, bool> ret = insert_unique_check(hint, value, priv_comp(), commit_data);
564 if(!ret.second)
565 return ret.first;
566 return insert_unique_commit(value, commit_data);
567 }
568
569 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
570 //! of type value_type.
571 //!
572 //! <b>Effects</b>: Tries to insert each element of a range into the tree.
573 //!
574 //! <b>Complexity</b>: Insert range is in general amortized O(N * log(N)), where N is the
575 //! size of the range. However, it is linear in N if the range is already sorted
576 //! by value_comp().
577 //!
578 //! <b>Throws</b>: Nothing.
579 //!
580 //! <b>Note</b>: Does not affect the validity of iterators and references.
581 //! No copy-constructors are called.
582 template<class Iterator>
insert_unique(Iterator b,Iterator e)583 void insert_unique(Iterator b, Iterator e)
584 {
585 for (; b != e; ++b)
586 this->insert_unique(*b);
587 }
588
589 //! <b>Requires</b>: key_value_comp must be a comparison function that induces
590 //! the same strict weak ordering as value_compare. The difference is that
591 //! key_value_comp compares an arbitrary key with the contained values.
592 //!
593 //! <b>Effects</b>: Checks if a value can be inserted in the container, using
594 //! a user provided key instead of the value itself.
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>: Average complexity is at most logarithmic.
603 //!
604 //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
605 //!
606 //! <b>Notes</b>: This function is used to improve performance when constructing
607 //! a value_type is expensive: if there is an equivalent value
608 //! the constructed object must be discarded. Many times, the part of the
609 //! node that is used to impose the order is much cheaper to construct
610 //! than the value_type and this function offers the possibility to use that
611 //! part to check if the insertion will be successful.
612 //!
613 //! If the check is successful, the user can construct the value_type and use
614 //! "insert_commit" to insert the object in constant-time. This gives a total
615 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
616 //!
617 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
618 //! objects are inserted or erased from the container.
619 template<class KeyType, class KeyValueCompare>
insert_unique_check(const KeyType & key,KeyValueCompare key_value_comp,insert_commit_data & commit_data)620 std::pair<iterator, bool> insert_unique_check
621 (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
622 {
623 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
624 comp(key_value_comp, this);
625 std::pair<node_ptr, bool> ret =
626 (node_algorithms::insert_unique_check
627 (node_ptr(&priv_header()), key, comp, commit_data));
628 return std::pair<iterator, bool>(iterator(ret.first, this), ret.second);
629 }
630
631 //! <b>Requires</b>: key_value_comp must be a comparison function that induces
632 //! the same strict weak ordering as value_compare. The difference is that
633 //! key_value_comp compares an arbitrary key with the contained values.
634 //!
635 //! <b>Effects</b>: Checks if a value can be inserted in the container, using
636 //! a user provided key instead of the value itself, using "hint"
637 //! as a hint to where it will be inserted.
638 //!
639 //! <b>Returns</b>: If there is an equivalent value
640 //! returns a pair containing an iterator to the already present value
641 //! and false. If the value can be inserted returns true in the returned
642 //! pair boolean and fills "commit_data" that is meant to be used with
643 //! the "insert_commit" function.
644 //!
645 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
646 //! constant time if t is inserted immediately before hint.
647 //!
648 //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
649 //!
650 //! <b>Notes</b>: This function is used to improve performance when constructing
651 //! a value_type is expensive: if there is an equivalent value
652 //! the constructed object must be discarded. Many times, the part of the
653 //! constructing that is used to impose the order is much cheaper to construct
654 //! than the value_type and this function offers the possibility to use that key
655 //! to check if the insertion will be successful.
656 //!
657 //! If the check is successful, the user can construct the value_type and use
658 //! "insert_commit" to insert the object in constant-time. This can give a total
659 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)).
660 //!
661 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
662 //! objects are inserted or erased from the container.
663 template<class KeyType, class KeyValueCompare>
insert_unique_check(const_iterator hint,const KeyType & key,KeyValueCompare key_value_comp,insert_commit_data & commit_data)664 std::pair<iterator, bool> insert_unique_check
665 (const_iterator hint, const KeyType &key
666 ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
667 {
668 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
669 comp(key_value_comp, this);
670 std::pair<node_ptr, bool> ret =
671 node_algorithms::insert_unique_check
672 (node_ptr(&priv_header()), hint.pointed_node(), key, comp, commit_data);
673 return std::pair<iterator, bool>(iterator(ret.first, this), ret.second);
674 }
675
676 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
677 //! must have been obtained from a previous call to "insert_check".
678 //! No objects should have been inserted or erased from the container between
679 //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
680 //!
681 //! <b>Effects</b>: Inserts the value in the avl_set using the information obtained
682 //! from the "commit_data" that a previous "insert_check" filled.
683 //!
684 //! <b>Returns</b>: An iterator to the newly inserted object.
685 //!
686 //! <b>Complexity</b>: Constant time.
687 //!
688 //! <b>Throws</b>: Nothing.
689 //!
690 //! <b>Notes</b>: This function has only sense if a "insert_check" has been
691 //! previously executed to fill "commit_data". No value should be inserted or
692 //! erased between the "insert_check" and "insert_commit" calls.
insert_unique_commit(reference value,const insert_commit_data & commit_data)693 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
694 {
695 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
696 if(safemode_or_autounlink)
697 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
698 node_algorithms::insert_unique_commit
699 (node_ptr(&priv_header()), to_insert, commit_data);
700 this->priv_size_traits().increment();
701 return iterator(to_insert, this);
702 }
703
704 //! <b>Effects</b>: Erases the element pointed to by pos.
705 //!
706 //! <b>Complexity</b>: Average complexity for erase element is constant time.
707 //!
708 //! <b>Throws</b>: Nothing.
709 //!
710 //! <b>Note</b>: Invalidates the iterators (but not the references)
711 //! to the erased elements. No destructors are called.
erase(const_iterator i)712 iterator erase(const_iterator i)
713 {
714 const_iterator ret(i);
715 ++ret;
716 node_ptr to_erase(i.pointed_node());
717 if(safemode_or_autounlink)
718 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!node_algorithms::unique(to_erase));
719 node_algorithms::erase(&priv_header(), to_erase);
720 this->priv_size_traits().decrement();
721 if(safemode_or_autounlink)
722 node_algorithms::init(to_erase);
723 return ret.unconst();
724 }
725
726 //! <b>Effects</b>: Erases the range pointed to by b end e.
727 //!
728 //! <b>Complexity</b>: Average complexity for erase range is amortized
729 //! O(log(size() + N)), where N is the number of elements in the range.
730 //!
731 //! <b>Throws</b>: Nothing.
732 //!
733 //! <b>Note</b>: Invalidates the iterators (but not the references)
734 //! to the erased elements. No destructors are called.
erase(const_iterator b,const_iterator e)735 iterator erase(const_iterator b, const_iterator e)
736 { size_type n; return private_erase(b, e, n); }
737
738 //! <b>Effects</b>: Erases all the elements with the given value.
739 //!
740 //! <b>Returns</b>: The number of erased elements.
741 //!
742 //! <b>Complexity</b>: Amortized O(log(size() + N).
743 //!
744 //! <b>Throws</b>: Nothing.
745 //!
746 //! <b>Note</b>: Invalidates the iterators (but not the references)
747 //! to the erased elements. No destructors are called.
erase(const_reference value)748 size_type erase(const_reference value)
749 { return this->erase(value, priv_comp()); }
750
751 //! <b>Effects</b>: Erases all the elements with the given key.
752 //! according to the comparison functor "comp".
753 //!
754 //! <b>Returns</b>: The number of erased elements.
755 //!
756 //! <b>Complexity</b>: Amortized O(log(size() + N).
757 //!
758 //! <b>Throws</b>: Nothing.
759 //!
760 //! <b>Note</b>: Invalidates the iterators (but not the references)
761 //! to the erased elements. No destructors are called.
762 template<class KeyType, class KeyValueCompare>
erase(const KeyType & key,KeyValueCompare comp,typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare,const_iterator>::value>::type * =0)763 size_type erase(const KeyType& key, KeyValueCompare comp
764 /// @cond
765 , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
766 /// @endcond
767 )
768 {
769 std::pair<iterator,iterator> p = this->equal_range(key, comp);
770 size_type n;
771 private_erase(p.first, p.second, n);
772 return n;
773 }
774
775 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
776 //!
777 //! <b>Effects</b>: Erases the element pointed to by pos.
778 //! Disposer::operator()(pointer) is called for the removed element.
779 //!
780 //! <b>Complexity</b>: Average complexity for erase element is constant time.
781 //!
782 //! <b>Throws</b>: Nothing.
783 //!
784 //! <b>Note</b>: Invalidates the iterators
785 //! to the erased elements.
786 template<class Disposer>
erase_and_dispose(const_iterator i,Disposer disposer)787 iterator erase_and_dispose(const_iterator i, Disposer disposer)
788 {
789 node_ptr to_erase(i.pointed_node());
790 iterator ret(this->erase(i));
791 disposer(get_real_value_traits().to_value_ptr(to_erase));
792 return ret;
793 }
794
795 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
796 template<class Disposer>
erase_and_dispose(iterator i,Disposer disposer)797 iterator erase_and_dispose(iterator i, Disposer disposer)
798 { return this->erase_and_dispose(const_iterator(i), disposer); }
799 #endif
800
801 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
802 //!
803 //! <b>Effects</b>: Erases the range pointed to by b end e.
804 //! Disposer::operator()(pointer) is called for the removed elements.
805 //!
806 //! <b>Complexity</b>: Average complexity for erase range is amortized
807 //! O(log(size() + N)), where N is the number of elements in the range.
808 //!
809 //! <b>Throws</b>: Nothing.
810 //!
811 //! <b>Note</b>: Invalidates the iterators
812 //! to the erased elements.
813 template<class Disposer>
erase_and_dispose(const_iterator b,const_iterator e,Disposer disposer)814 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
815 { size_type n; return private_erase(b, e, n, disposer); }
816
817 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
818 //!
819 //! <b>Effects</b>: Erases all the elements with the given value.
820 //! Disposer::operator()(pointer) is called for the removed elements.
821 //!
822 //! <b>Returns</b>: The number of erased elements.
823 //!
824 //! <b>Complexity</b>: Amortized O(log(size() + N).
825 //!
826 //! <b>Throws</b>: Nothing.
827 //!
828 //! <b>Note</b>: Invalidates the iterators (but not the references)
829 //! to the erased elements. No destructors are called.
830 template<class Disposer>
erase_and_dispose(const_reference value,Disposer disposer)831 size_type erase_and_dispose(const_reference value, Disposer disposer)
832 {
833 std::pair<iterator,iterator> p = this->equal_range(value);
834 size_type n;
835 private_erase(p.first, p.second, n, disposer);
836 return n;
837 }
838
839 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
840 //!
841 //! <b>Effects</b>: Erases all the elements with the given key.
842 //! according to the comparison functor "comp".
843 //! Disposer::operator()(pointer) is called for the removed elements.
844 //!
845 //! <b>Returns</b>: The number of erased elements.
846 //!
847 //! <b>Complexity</b>: Amortized O(log(size() + N).
848 //!
849 //! <b>Throws</b>: Nothing.
850 //!
851 //! <b>Note</b>: Invalidates the iterators
852 //! to the erased elements.
853 template<class KeyType, class KeyValueCompare, class Disposer>
erase_and_dispose(const KeyType & key,KeyValueCompare comp,Disposer disposer,typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare,const_iterator>::value>::type * =0)854 size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
855 /// @cond
856 , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
857 /// @endcond
858 )
859 {
860 std::pair<iterator,iterator> p = this->equal_range(key, comp);
861 size_type n;
862 private_erase(p.first, p.second, n, disposer);
863 return n;
864 }
865
866 //! <b>Effects</b>: Erases all of the elements.
867 //!
868 //! <b>Complexity</b>: Linear to the number of elements on the container.
869 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
870 //!
871 //! <b>Throws</b>: Nothing.
872 //!
873 //! <b>Note</b>: Invalidates the iterators (but not the references)
874 //! to the erased elements. No destructors are called.
clear()875 void clear()
876 {
877 if(safemode_or_autounlink){
878 this->clear_and_dispose(detail::null_disposer());
879 }
880 else{
881 node_algorithms::init_header(&priv_header());
882 this->priv_size_traits().set_size(0);
883 }
884 }
885
886 //! <b>Effects</b>: Erases all of the elements calling disposer(p) for
887 //! each node to be erased.
888 //! <b>Complexity</b>: Amortized O(log(size() + N)),
889 //! where N is the number of elements in the container.
890 //!
891 //! <b>Throws</b>: Nothing.
892 //!
893 //! <b>Note</b>: Invalidates the iterators (but not the references)
894 //! to the erased elements. Calls N times to disposer functor.
895 template<class Disposer>
clear_and_dispose(Disposer disposer)896 void clear_and_dispose(Disposer disposer)
897 {
898 node_algorithms::clear_and_dispose(node_ptr(&priv_header())
899 , detail::node_disposer<Disposer, splaytree_impl>(disposer, this));
900 this->priv_size_traits().set_size(0);
901 }
902
903 //! <b>Effects</b>: Returns the number of contained elements with the given value
904 //!
905 //! <b>Complexity</b>: Amortized logarithmic to the number of elements contained plus lineal
906 //! to number of objects with the given value.
907 //!
908 //! <b>Throws</b>: Nothing.
count(const_reference value)909 size_type count(const_reference value)
910 { return this->count(value, priv_comp()); }
911
912 //! <b>Effects</b>: Returns the number of contained elements with the given key
913 //!
914 //! <b>Complexity</b>: Amortized logarithmic to the number of elements contained plus lineal
915 //! to number of objects with the given key.
916 //!
917 //! <b>Throws</b>: Nothing.
918 template<class KeyType, class KeyValueCompare>
count(const KeyType & key,KeyValueCompare comp)919 size_type count(const KeyType &key, KeyValueCompare comp)
920 {
921 std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp);
922 return std::distance(ret.first, ret.second);
923 }
924
925 //! <b>Effects</b>: Returns the number of contained elements with the given value
926 //!
927 //! <b>Complexity</b>: Amortized logarithmic to the number of elements contained plus lineal
928 //! to number of objects with the given value.
929 //!
930 //! <b>Throws</b>: Nothing.
count_dont_splay(const_reference value) const931 size_type count_dont_splay(const_reference value) const
932 { return this->count_dont_splay(value, priv_comp()); }
933
934 //! <b>Effects</b>: Returns the number of contained elements with the given key
935 //!
936 //! <b>Complexity</b>: Amortized logarithmic to the number of elements contained plus lineal
937 //! to number of objects with the given key.
938 //!
939 //! <b>Throws</b>: Nothing.
940 template<class KeyType, class KeyValueCompare>
count_dont_splay(const KeyType & key,KeyValueCompare comp) const941 size_type count_dont_splay(const KeyType &key, KeyValueCompare comp) const
942 {
943 std::pair<const_iterator, const_iterator> ret = this->equal_range_dont_splay(key, comp);
944 return std::distance(ret.first, ret.second);
945 }
946
947 //! <b>Effects</b>: Returns an iterator to the first element whose
948 //! key is not less than k or end() if that element does not exist.
949 //!
950 //! <b>Complexity</b>: Amortized logarithmic.
951 //!
952 //! <b>Throws</b>: Nothing.
lower_bound(const_reference value)953 iterator lower_bound(const_reference value)
954 { return this->lower_bound(value, priv_comp()); }
955
956 //! <b>Effects</b>: Returns an iterator to the first element whose
957 //! key is not less than k or end() if that element does not exist.
958 //!
959 //! <b>Complexity</b>: Logarithmic.
960 //!
961 //! <b>Throws</b>: Nothing.
lower_bound_dont_splay(const_reference value) const962 const_iterator lower_bound_dont_splay(const_reference value) const
963 { return this->lower_bound_dont_splay(value, priv_comp()); }
964
965 //! <b>Effects</b>: Returns an iterator to the first element whose
966 //! key is not less than k or end() if that element does not exist.
967 //!
968 //! <b>Complexity</b>: Logarithmic.
969 //!
970 //! <b>Throws</b>: Nothing.
971 template<class KeyType, class KeyValueCompare>
lower_bound(const KeyType & key,KeyValueCompare comp)972 iterator lower_bound(const KeyType &key, KeyValueCompare comp)
973 {
974 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
975 key_node_comp(comp, this);
976 return iterator(node_algorithms::lower_bound
977 (const_node_ptr(&priv_header()), key, key_node_comp), this);
978 }
979
980 //! <b>Effects</b>: Returns a const iterator to the first element whose
981 //! key is not less than k or end() if that element does not exist.
982 //!
983 //! <b>Complexity</b>: Logarithmic.
984 //!
985 //! <b>Throws</b>: Nothing.
986 template<class KeyType, class KeyValueCompare>
lower_bound_dont_splay(const KeyType & key,KeyValueCompare comp) const987 const_iterator lower_bound_dont_splay(const KeyType &key, KeyValueCompare comp) const
988 {
989 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
990 key_node_comp(comp, this);
991 return const_iterator(node_algorithms::lower_bound
992 (const_node_ptr(&priv_header()), key, key_node_comp, false), this);
993 }
994
995 //! <b>Effects</b>: Returns an iterator to the first element whose
996 //! key is greater than k or end() if that element does not exist.
997 //!
998 //! <b>Complexity</b>: Amortized logarithmic.
999 //!
1000 //! <b>Throws</b>: Nothing.
upper_bound(const_reference value)1001 iterator upper_bound(const_reference value)
1002 { return this->upper_bound(value, priv_comp()); }
1003
1004 //! <b>Effects</b>: Returns an iterator to the first element whose
1005 //! key is greater than k according to comp or end() if that element
1006 //! does not exist.
1007 //!
1008 //! <b>Complexity</b>: Amortized logarithmic.
1009 //!
1010 //! <b>Throws</b>: Nothing.
1011 template<class KeyType, class KeyValueCompare>
upper_bound(const KeyType & key,KeyValueCompare comp)1012 iterator upper_bound(const KeyType &key, KeyValueCompare comp)
1013 {
1014 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
1015 key_node_comp(comp, this);
1016 return iterator(node_algorithms::upper_bound
1017 (const_node_ptr(&priv_header()), key, key_node_comp), this);
1018 }
1019
1020 //! <b>Effects</b>: Returns an iterator to the first element whose
1021 //! key is greater than k or end() if that element does not exist.
1022 //!
1023 //! <b>Complexity</b>: Logarithmic.
1024 //!
1025 //! <b>Throws</b>: Nothing.
upper_bound_dont_splay(const_reference value) const1026 const_iterator upper_bound_dont_splay(const_reference value) const
1027 { return this->upper_bound_dont_splay(value, priv_comp()); }
1028
1029 //! <b>Effects</b>: Returns an iterator to the first element whose
1030 //! key is greater than k according to comp or end() if that element
1031 //! does not exist.
1032 //!
1033 //! <b>Complexity</b>: Logarithmic.
1034 //!
1035 //! <b>Throws</b>: Nothing.
1036 template<class KeyType, class KeyValueCompare>
upper_bound_dont_splay(const KeyType & key,KeyValueCompare comp) const1037 const_iterator upper_bound_dont_splay(const KeyType &key, KeyValueCompare comp) const
1038 {
1039 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
1040 key_node_comp(comp, this);
1041 return const_iterator(node_algorithms::upper_bound_dont_splay
1042 (const_node_ptr(&priv_header()), key, key_node_comp, false), this);
1043 }
1044
1045 //! <b>Effects</b>: Finds an iterator to the first element whose key is
1046 //! k or end() if that element does not exist.
1047 //!
1048 //! <b>Complexity</b>: Amortized logarithmic.
1049 //!
1050 //! <b>Throws</b>: Nothing.
find(const_reference value)1051 iterator find(const_reference value)
1052 { return this->find(value, priv_comp()); }
1053
1054 //! <b>Effects</b>: Finds an iterator to the first element whose key is
1055 //! k or end() if that element does not exist.
1056 //!
1057 //! <b>Complexity</b>: Amortized logarithmic.
1058 //!
1059 //! <b>Throws</b>: Nothing.
1060 template<class KeyType, class KeyValueCompare>
find(const KeyType & key,KeyValueCompare comp)1061 iterator find(const KeyType &key, KeyValueCompare comp)
1062 {
1063 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
1064 key_node_comp(comp, this);
1065 return iterator
1066 (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp), this);
1067 }
1068
1069 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
1070 //! k or end() if that element does not exist.
1071 //!
1072 //! <b>Complexity</b>: Logarithmic.
1073 //!
1074 //! <b>Throws</b>: Nothing.
find_dont_splay(const_reference value) const1075 const_iterator find_dont_splay(const_reference value) const
1076 { return this->find_dont_splay(value, priv_comp()); }
1077
1078 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
1079 //! k or end() if that element does not exist.
1080 //!
1081 //! <b>Complexity</b>: Logarithmic.
1082 //!
1083 //! <b>Throws</b>: Nothing.
1084 template<class KeyType, class KeyValueCompare>
find_dont_splay(const KeyType & key,KeyValueCompare comp) const1085 const_iterator find_dont_splay(const KeyType &key, KeyValueCompare comp) const
1086 {
1087 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
1088 key_node_comp(comp, this);
1089 return const_iterator
1090 (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp, false), this);
1091 }
1092
1093 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
1094 //! an empty range that indicates the position where those elements would be
1095 //! if they there is no elements with key k.
1096 //!
1097 //! <b>Complexity</b>: Amortized logarithmic.
1098 //!
1099 //! <b>Throws</b>: Nothing.
equal_range(const_reference value)1100 std::pair<iterator,iterator> equal_range(const_reference value)
1101 { return this->equal_range(value, priv_comp()); }
1102
1103 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
1104 //! an empty range that indicates the position where those elements would be
1105 //! if they there is no elements with key k.
1106 //!
1107 //! <b>Complexity</b>: Amortized logarithmic.
1108 //!
1109 //! <b>Throws</b>: Nothing.
1110 template<class KeyType, class KeyValueCompare>
equal_range(const KeyType & key,KeyValueCompare comp)1111 std::pair<iterator,iterator> equal_range(const KeyType &key, KeyValueCompare comp)
1112 {
1113 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
1114 key_node_comp(comp, this);
1115 std::pair<node_ptr, node_ptr> ret
1116 (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));
1117 return std::pair<iterator, iterator>(iterator(ret.first, this), iterator(ret.second, this));
1118 }
1119
1120 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
1121 //! an empty range that indicates the position where those elements would be
1122 //! if they there is no elements with key k.
1123 //!
1124 //! <b>Complexity</b>: Logarithmic.
1125 //!
1126 //! <b>Throws</b>: Nothing.
1127 std::pair<const_iterator, const_iterator>
equal_range_dont_splay(const_reference value) const1128 equal_range_dont_splay(const_reference value) const
1129 { return this->equal_range_dont_splay(value, priv_comp()); }
1130
1131 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
1132 //! an empty range that indicates the position where those elements would be
1133 //! if they there is no elements with key k.
1134 //!
1135 //! <b>Complexity</b>: Logarithmic.
1136 //!
1137 //! <b>Throws</b>: Nothing.
1138 template<class KeyType, class KeyValueCompare>
1139 std::pair<const_iterator, const_iterator>
equal_range_dont_splay(const KeyType & key,KeyValueCompare comp) const1140 equal_range_dont_splay(const KeyType &key, KeyValueCompare comp) const
1141 {
1142 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
1143 key_node_comp(comp, this);
1144 std::pair<node_ptr, node_ptr> ret
1145 (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp, false));
1146 return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
1147 }
1148
1149 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1150 //! Cloner should yield to nodes equivalent to the original nodes.
1151 //!
1152 //! <b>Effects</b>: Erases all the elements from *this
1153 //! calling Disposer::operator()(pointer), clones all the
1154 //! elements from src calling Cloner::operator()(const_reference )
1155 //! and inserts them on *this. Copies the predicate from the source container.
1156 //!
1157 //! If cloner throws, all cloned elements are unlinked and disposed
1158 //! calling Disposer::operator()(pointer).
1159 //!
1160 //! <b>Complexity</b>: Linear to erased plus inserted elements.
1161 //!
1162 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
1163 template <class Cloner, class Disposer>
clone_from(const splaytree_impl & src,Cloner cloner,Disposer disposer)1164 void clone_from(const splaytree_impl &src, Cloner cloner, Disposer disposer)
1165 {
1166 this->clear_and_dispose(disposer);
1167 if(!src.empty()){
1168 detail::exception_disposer<splaytree_impl, Disposer>
1169 rollback(*this, disposer);
1170 node_algorithms::clone
1171 (const_node_ptr(&src.priv_header())
1172 ,node_ptr(&this->priv_header())
1173 ,detail::node_cloner<Cloner, splaytree_impl>(cloner, this)
1174 ,detail::node_disposer<Disposer, splaytree_impl>(disposer, this));
1175 this->priv_size_traits().set_size(src.priv_size_traits().get_size());
1176 this->priv_comp() = src.priv_comp();
1177 rollback.release();
1178 }
1179 }
1180
1181 //! <b>Effects</b>: Unlinks the leftmost node from the tree.
1182 //!
1183 //! <b>Complexity</b>: Average complexity is constant time.
1184 //!
1185 //! <b>Throws</b>: Nothing.
1186 //!
1187 //! <b>Notes</b>: This function breaks the tree and the tree can
1188 //! only be used for more unlink_leftmost_without_rebalance calls.
1189 //! This function is normally used to achieve a step by step
1190 //! controlled destruction of the tree.
unlink_leftmost_without_rebalance()1191 pointer unlink_leftmost_without_rebalance()
1192 {
1193 node_ptr to_be_disposed(node_algorithms::unlink_leftmost_without_rebalance
1194 (node_ptr(&priv_header())));
1195 if(!to_be_disposed)
1196 return 0;
1197 this->priv_size_traits().decrement();
1198 if(safemode_or_autounlink)//If this is commented does not work with normal_link
1199 node_algorithms::init(to_be_disposed);
1200 return get_real_value_traits().to_value_ptr(to_be_disposed);
1201 }
1202
1203 //! <b>Requires</b>: i must be a valid iterator of *this.
1204 //!
1205 //! <b>Effects</b>: Rearranges the splay set so that the element pointed by i
1206 //! is placed as the root of the tree, improving future searches of this value.
1207 //!
1208 //! <b>Complexity</b>: Amortized logarithmic.
1209 //!
1210 //! <b>Throws</b>: Nothing.
splay_up(iterator i)1211 void splay_up(iterator i)
1212 { return node_algorithms::splay_up(i.pointed_node(), &priv_header()); }
1213
1214 //! <b>Effects</b>: Rearranges the splay set so that if *this stores an element
1215 //! with a key equivalent to value the element is placed as the root of the
1216 //! tree. If the element is not present returns the last node compared with the key.
1217 //! If the tree is empty, end() is returned.
1218 //!
1219 //! <b>Complexity</b>: Amortized logarithmic.
1220 //!
1221 //! <b>Returns</b>: An iterator to the new root of the tree, end() if the tree is empty.
1222 //!
1223 //! <b>Throws</b>: If the comparison functor throws.
1224 template<class KeyType, class KeyValueCompare>
splay_down(const KeyType & key,KeyValueCompare comp)1225 iterator splay_down(const KeyType &key, KeyValueCompare comp)
1226 {
1227 detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
1228 key_node_comp(comp, this);
1229 node_ptr r = node_algorithms::splay_down(&priv_header(), key, key_node_comp);
1230 return iterator(r, this);
1231 }
1232
1233 //! <b>Effects</b>: Rearranges the splay set so that if *this stores an element
1234 //! with a key equivalent to value the element is placed as the root of the
1235 //! tree.
1236 //!
1237 //! <b>Complexity</b>: Amortized logarithmic.
1238 //!
1239 //! <b>Returns</b>: An iterator to the new root of the tree, end() if the tree is empty.
1240 //!
1241 //! <b>Throws</b>: If the predicate throws.
splay_down(const value_type & value)1242 iterator splay_down(const value_type &value)
1243 { return this->splay_down(value, priv_comp()); }
1244
1245 //! <b>Requires</b>: replace_this must be a valid iterator of *this
1246 //! and with_this must not be inserted in any tree.
1247 //!
1248 //! <b>Effects</b>: Replaces replace_this in its position in the
1249 //! tree with with_this. The tree does not need to be rebalanced.
1250 //!
1251 //! <b>Complexity</b>: Constant.
1252 //!
1253 //! <b>Throws</b>: Nothing.
1254 //!
1255 //! <b>Note</b>: This function will break container ordering invariants if
1256 //! with_this is not equivalent to *replace_this according to the
1257 //! ordering rules. This function is faster than erasing and inserting
1258 //! the node, since no rebalancing or comparison is needed.
replace_node(iterator replace_this,reference with_this)1259 void replace_node(iterator replace_this, reference with_this)
1260 {
1261 node_algorithms::replace_node( get_real_value_traits().to_node_ptr(*replace_this)
1262 , node_ptr(&priv_header())
1263 , get_real_value_traits().to_node_ptr(with_this));
1264 }
1265
1266 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1267 //! appropriate type. Otherwise the behavior is undefined.
1268 //!
1269 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
1270 //! that points to the value
1271 //!
1272 //! <b>Complexity</b>: Constant.
1273 //!
1274 //! <b>Throws</b>: Nothing.
1275 //!
1276 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1277 //! is stateless.
s_iterator_to(reference value)1278 static iterator s_iterator_to(reference value)
1279 {
1280 BOOST_STATIC_ASSERT((!stateful_value_traits));
1281 return iterator (value_traits::to_node_ptr(value), 0);
1282 }
1283
1284 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1285 //! appropriate type. Otherwise the behavior is undefined.
1286 //!
1287 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
1288 //! set that points to the value
1289 //!
1290 //! <b>Complexity</b>: Constant.
1291 //!
1292 //! <b>Throws</b>: Nothing.
1293 //!
1294 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1295 //! is stateless.
s_iterator_to(const_reference value)1296 static const_iterator s_iterator_to(const_reference value)
1297 {
1298 BOOST_STATIC_ASSERT((!stateful_value_traits));
1299 return const_iterator (value_traits::to_node_ptr(const_cast<reference> (value)), 0);
1300 }
1301
1302 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1303 //! appropriate type. Otherwise the behavior is undefined.
1304 //!
1305 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
1306 //! that points to the value
1307 //!
1308 //! <b>Complexity</b>: Constant.
1309 //!
1310 //! <b>Throws</b>: Nothing.
iterator_to(reference value)1311 iterator iterator_to(reference value)
1312 { return iterator (value_traits::to_node_ptr(value), this); }
1313
1314 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1315 //! appropriate type. Otherwise the behavior is undefined.
1316 //!
1317 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
1318 //! set that points to the value
1319 //!
1320 //! <b>Complexity</b>: Constant.
1321 //!
1322 //! <b>Throws</b>: Nothing.
iterator_to(const_reference value) const1323 const_iterator iterator_to(const_reference value) const
1324 { return const_iterator (value_traits::to_node_ptr(const_cast<reference> (value)), this); }
1325
1326 //! <b>Requires</b>: value shall not be in a tree.
1327 //!
1328 //! <b>Effects</b>: init_node puts the hook of a value in a well-known default
1329 //! state.
1330 //!
1331 //! <b>Throws</b>: Nothing.
1332 //!
1333 //! <b>Complexity</b>: Constant time.
1334 //!
1335 //! <b>Note</b>: This function puts the hook in the well-known default state
1336 //! used by auto_unlink and safe hooks.
init_node(reference value)1337 static void init_node(reference value)
1338 { node_algorithms::init(value_traits::to_node_ptr(value)); }
1339
1340 //! <b>Effects</b>: Rebalances the tree.
1341 //!
1342 //! <b>Throws</b>: Nothing.
1343 //!
1344 //! <b>Complexity</b>: Linear.
rebalance()1345 void rebalance()
1346 { node_algorithms::rebalance(node_ptr(&priv_header())); }
1347
1348 //! <b>Requires</b>: old_root is a node of a tree.
1349 //!
1350 //! <b>Effects</b>: Rebalances the subtree rooted at old_root.
1351 //!
1352 //! <b>Returns</b>: The new root of the subtree.
1353 //!
1354 //! <b>Throws</b>: Nothing.
1355 //!
1356 //! <b>Complexity</b>: Linear to the elements in the subtree.
rebalance_subtree(iterator root)1357 iterator rebalance_subtree(iterator root)
1358 { return iterator(node_algorithms::rebalance_subtree(root.pointed_node()), this); }
1359
1360 /*
1361 //! <b>Effects</b>: removes x from a tree of the appropriate type. It has no effect,
1362 //! if x is not in such a tree.
1363 //!
1364 //! <b>Throws</b>: Nothing.
1365 //!
1366 //! <b>Complexity</b>: Constant time.
1367 //!
1368 //! <b>Note</b>: This static function is only usable with the "safe mode"
1369 //! hook and non-constant time size lists. Otherwise, the user must use
1370 //! the non-static "erase(reference )" member. If the user calls
1371 //! this function with a non "safe mode" or constant time size list
1372 //! a compilation error will be issued.
1373 template<class T>
1374 static void remove_node(T& value)
1375 {
1376 //This function is only usable for safe mode hooks and non-constant
1377 //time lists.
1378 //BOOST_STATIC_ASSERT((!(safemode_or_autounlink && constant_time_size)));
1379 BOOST_STATIC_ASSERT((!constant_time_size));
1380 BOOST_STATIC_ASSERT((boost::is_convertible<T, value_type>::value));
1381 node_ptr to_remove(value_traits::to_node_ptr(value));
1382 node_algorithms::unlink_and_rebalance(to_remove);
1383 if(safemode_or_autounlink)
1384 node_algorithms::init(to_remove);
1385 }
1386 */
1387
1388 /// @cond
1389 private:
1390 template<class Disposer>
private_erase(const_iterator b,const_iterator e,size_type & n,Disposer disposer)1391 iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer)
1392 {
1393 for(n = 0; b != e; ++n)
1394 this->erase_and_dispose(b++, disposer);
1395 return b.unconst();
1396 }
1397
private_erase(const_iterator b,const_iterator e,size_type & n)1398 iterator private_erase(const_iterator b, const_iterator e, size_type &n)
1399 {
1400 for(n = 0; b != e; ++n)
1401 this->erase(b++);
1402 return b.unconst();
1403 }
1404 /// @endcond
1405
1406 private:
priv_container_from_end_iterator(const const_iterator & end_iterator)1407 static splaytree_impl &priv_container_from_end_iterator(const const_iterator &end_iterator)
1408 {
1409 header_plus_size *r = detail::parent_from_member<header_plus_size, node>
1410 ( detail::boost_intrusive_get_pointer(end_iterator.pointed_node()), &header_plus_size::header_);
1411 node_plus_pred_t *n = detail::parent_from_member
1412 <node_plus_pred_t, header_plus_size>(r, &node_plus_pred_t::header_plus_size_);
1413 data_t *d = detail::parent_from_member<data_t, node_plus_pred_t>(n, &data_t::node_plus_pred_);
1414 splaytree_impl *rb = detail::parent_from_member<splaytree_impl, data_t>(d, &splaytree_impl::data_);
1415 return *rb;
1416 }
1417
priv_container_from_iterator(const const_iterator & it)1418 static splaytree_impl &priv_container_from_iterator(const const_iterator &it)
1419 { return priv_container_from_end_iterator(it.end_iterator_from_it()); }
1420 };
1421
1422 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1423 template<class T, class ...Options>
1424 #else
1425 template<class Config>
1426 #endif
operator <(const splaytree_impl<T,Options...> & x,const splaytree_impl<T,Options...> & y)1427 inline bool operator<
1428 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1429 (const splaytree_impl<T, Options...> &x, const splaytree_impl<T, Options...> &y)
1430 #else
1431 (const splaytree_impl<Config> &x, const splaytree_impl<Config> &y)
1432 #endif
1433 { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1434
1435 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1436 template<class T, class ...Options>
1437 #else
1438 template<class Config>
1439 #endif
operator ==(const splaytree_impl<T,Options...> & x,const splaytree_impl<T,Options...> & y)1440 bool operator==
1441 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1442 (const splaytree_impl<T, Options...> &x, const splaytree_impl<T, Options...> &y)
1443 #else
1444 (const splaytree_impl<Config> &x, const splaytree_impl<Config> &y)
1445 #endif
1446 {
1447 typedef splaytree_impl<Config> tree_type;
1448 typedef typename tree_type::const_iterator const_iterator;
1449
1450 if(tree_type::constant_time_size && x.size() != y.size()){
1451 return false;
1452 }
1453 const_iterator end1 = x.end();
1454 const_iterator i1 = x.begin();
1455 const_iterator i2 = y.begin();
1456 if(tree_type::constant_time_size){
1457 while (i1 != end1 && *i1 == *i2) {
1458 ++i1;
1459 ++i2;
1460 }
1461 return i1 == end1;
1462 }
1463 else{
1464 const_iterator end2 = y.end();
1465 while (i1 != end1 && i2 != end2 && *i1 == *i2) {
1466 ++i1;
1467 ++i2;
1468 }
1469 return i1 == end1 && i2 == end2;
1470 }
1471 }
1472
1473 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1474 template<class T, class ...Options>
1475 #else
1476 template<class Config>
1477 #endif
operator !=(const splaytree_impl<T,Options...> & x,const splaytree_impl<T,Options...> & y)1478 inline bool operator!=
1479 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1480 (const splaytree_impl<T, Options...> &x, const splaytree_impl<T, Options...> &y)
1481 #else
1482 (const splaytree_impl<Config> &x, const splaytree_impl<Config> &y)
1483 #endif
1484 { return !(x == y); }
1485
1486 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1487 template<class T, class ...Options>
1488 #else
1489 template<class Config>
1490 #endif
operator >(const splaytree_impl<T,Options...> & x,const splaytree_impl<T,Options...> & y)1491 inline bool operator>
1492 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1493 (const splaytree_impl<T, Options...> &x, const splaytree_impl<T, Options...> &y)
1494 #else
1495 (const splaytree_impl<Config> &x, const splaytree_impl<Config> &y)
1496 #endif
1497 { return y < x; }
1498
1499 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1500 template<class T, class ...Options>
1501 #else
1502 template<class Config>
1503 #endif
operator <=(const splaytree_impl<T,Options...> & x,const splaytree_impl<T,Options...> & y)1504 inline bool operator<=
1505 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1506 (const splaytree_impl<T, Options...> &x, const splaytree_impl<T, Options...> &y)
1507 #else
1508 (const splaytree_impl<Config> &x, const splaytree_impl<Config> &y)
1509 #endif
1510 { return !(y < x); }
1511
1512 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1513 template<class T, class ...Options>
1514 #else
1515 template<class Config>
1516 #endif
operator >=(const splaytree_impl<T,Options...> & x,const splaytree_impl<T,Options...> & y)1517 inline bool operator>=
1518 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1519 (const splaytree_impl<T, Options...> &x, const splaytree_impl<T, Options...> &y)
1520 #else
1521 (const splaytree_impl<Config> &x, const splaytree_impl<Config> &y)
1522 #endif
1523 { return !(x < y); }
1524
1525 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1526 template<class T, class ...Options>
1527 #else
1528 template<class Config>
1529 #endif
swap(splaytree_impl<T,Options...> & x,splaytree_impl<T,Options...> & y)1530 inline void swap
1531 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1532 (splaytree_impl<T, Options...> &x, splaytree_impl<T, Options...> &y)
1533 #else
1534 (splaytree_impl<Config> &x, splaytree_impl<Config> &y)
1535 #endif
1536 { x.swap(y); }
1537
1538 /// @cond
1539
1540 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1541 template<class T, class O1 = none, class O2 = none
1542 , class O3 = none, class O4 = none>
1543 #else
1544 template<class T, class ...Options>
1545 #endif
1546 struct make_splaytree_opt
1547 {
1548 typedef typename pack_options
1549 < splay_set_defaults<T>,
1550 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1551 O1, O2, O3, O4
1552 #else
1553 Options...
1554 #endif
1555 >::type packed_options;
1556 typedef typename detail::get_value_traits
1557 <T, typename packed_options::value_traits>::type value_traits;
1558
1559 typedef splaysetopt
1560 < value_traits
1561 , typename packed_options::compare
1562 , typename packed_options::size_type
1563 , packed_options::constant_time_size
1564 > type;
1565 };
1566 /// @endcond
1567
1568 //! Helper metafunction to define a \c splaytree that yields to the same type when the
1569 //! same options (either explicitly or implicitly) are used.
1570 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1571 template<class T, class ...Options>
1572 #else
1573 template<class T, class O1 = none, class O2 = none
1574 , class O3 = none, class O4 = none>
1575 #endif
1576 struct make_splaytree
1577 {
1578 /// @cond
1579 typedef splaytree_impl
1580 < typename make_splaytree_opt<T,
1581 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1582 O1, O2, O3, O4
1583 #else
1584 Options...
1585 #endif
1586 >::type
1587 > implementation_defined;
1588 /// @endcond
1589 typedef implementation_defined type;
1590 };
1591
1592 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1593 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1594 template<class T, class O1, class O2, class O3, class O4>
1595 #else
1596 template<class T, class ...Options>
1597 #endif
1598 class splaytree
1599 : public make_splaytree<T,
1600 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1601 O1, O2, O3, O4
1602 #else
1603 Options...
1604 #endif
1605 >::type
1606 {
1607 typedef typename make_splaytree
1608 <T,
1609 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1610 O1, O2, O3, O4
1611 #else
1612 Options...
1613 #endif
1614 >::type Base;
1615
1616 public:
1617 typedef typename Base::value_compare value_compare;
1618 typedef typename Base::value_traits value_traits;
1619 typedef typename Base::real_value_traits real_value_traits;
1620 typedef typename Base::iterator iterator;
1621 typedef typename Base::const_iterator const_iterator;
1622
1623 //Assert if passed value traits are compatible with the type
1624 BOOST_STATIC_ASSERT((detail::is_same<typename real_value_traits::value_type, T>::value));
1625
splaytree(const value_compare & cmp=value_compare (),const value_traits & v_traits=value_traits ())1626 splaytree( const value_compare &cmp = value_compare()
1627 , const value_traits &v_traits = value_traits())
1628 : Base(cmp, v_traits)
1629 {}
1630
1631 template<class Iterator>
splaytree(bool unique,Iterator b,Iterator e,const value_compare & cmp=value_compare (),const value_traits & v_traits=value_traits ())1632 splaytree( bool unique, Iterator b, Iterator e
1633 , const value_compare &cmp = value_compare()
1634 , const value_traits &v_traits = value_traits())
1635 : Base(unique, b, e, cmp, v_traits)
1636 {}
1637
container_from_end_iterator(iterator end_iterator)1638 static splaytree &container_from_end_iterator(iterator end_iterator)
1639 { return static_cast<splaytree &>(Base::container_from_end_iterator(end_iterator)); }
1640
container_from_end_iterator(const_iterator end_iterator)1641 static const splaytree &container_from_end_iterator(const_iterator end_iterator)
1642 { return static_cast<const splaytree &>(Base::container_from_end_iterator(end_iterator)); }
1643 };
1644
1645 #endif
1646
1647
1648 } //namespace intrusive
1649 } //namespace boost
1650
1651 #include <boost/intrusive/detail/config_end.hpp>
1652
1653 #endif //BOOST_INTRUSIVE_SPLAYTREE_HPP
1654