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