1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2013 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 #ifndef BOOST_INTRUSIVE_AVLTREE_HPP 13 #define BOOST_INTRUSIVE_AVLTREE_HPP 14 15 #include <boost/intrusive/detail/config_begin.hpp> 16 #include <boost/intrusive/intrusive_fwd.hpp> 17 #include <cstddef> 18 #include <boost/intrusive/detail/minimal_less_equal_header.hpp> 19 #include <boost/intrusive/detail/minimal_pair_header.hpp> 20 21 #include <boost/static_assert.hpp> 22 #include <boost/intrusive/avl_set_hook.hpp> 23 #include <boost/intrusive/detail/avltree_node.hpp> 24 #include <boost/intrusive/bstree.hpp> 25 #include <boost/intrusive/detail/tree_node.hpp> 26 #include <boost/intrusive/detail/ebo_functor_holder.hpp> 27 #include <boost/intrusive/detail/mpl.hpp> 28 #include <boost/intrusive/pointer_traits.hpp> 29 #include <boost/intrusive/detail/get_value_traits.hpp> 30 #include <boost/intrusive/avltree_algorithms.hpp> 31 #include <boost/intrusive/link_mode.hpp> 32 #include <boost/move/utility_core.hpp> 33 34 #if defined(BOOST_HAS_PRAGMA_ONCE) 35 # pragma once 36 #endif 37 38 namespace boost { 39 namespace intrusive { 40 41 /// @cond 42 43 struct default_avltree_hook_applier 44 { template <class T> struct apply{ typedef typename T::default_avltree_hook type; }; }; 45 46 template<> 47 struct is_default_hook_tag<default_avltree_hook_applier> 48 { static const bool value = true; }; 49 50 struct avltree_defaults 51 : bstree_defaults 52 { 53 typedef default_avltree_hook_applier proto_value_traits; 54 }; 55 56 /// @endcond 57 58 //! The class template avltree is an intrusive AVL tree container, that 59 //! is used to construct intrusive avl_set and avl_multiset containers. 60 //! The no-throw guarantee holds only, if the key_compare object 61 //! doesn't throw. 62 //! 63 //! The template parameter \c T is the type to be managed by the container. 64 //! The user can specify additional options and if no options are provided 65 //! default options are used. 66 //! 67 //! The container supports the following options: 68 //! \c base_hook<>/member_hook<>/value_traits<>, 69 //! \c constant_time_size<>, \c size_type<> and 70 //! \c compare<>. 71 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 72 template<class T, class ...Options> 73 #else 74 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder> 75 #endif 76 class avltree_impl 77 /// @cond 78 : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder> 79 /// @endcond 80 { 81 public: 82 typedef ValueTraits value_traits; 83 /// @cond 84 typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType 85 , ConstantTimeSize, AvlTreeAlgorithms 86 , HeaderHolder> tree_type; 87 typedef tree_type implementation_defined; 88 /// @endcond 89 90 typedef typename implementation_defined::pointer pointer; 91 typedef typename implementation_defined::const_pointer const_pointer; 92 typedef typename implementation_defined::value_type value_type; 93 typedef typename implementation_defined::key_type key_type; 94 typedef typename implementation_defined::key_of_value key_of_value; 95 typedef typename implementation_defined::reference reference; 96 typedef typename implementation_defined::const_reference const_reference; 97 typedef typename implementation_defined::difference_type difference_type; 98 typedef typename implementation_defined::size_type size_type; 99 typedef typename implementation_defined::value_compare value_compare; 100 typedef typename implementation_defined::key_compare key_compare; 101 typedef typename implementation_defined::iterator iterator; 102 typedef typename implementation_defined::const_iterator const_iterator; 103 typedef typename implementation_defined::reverse_iterator reverse_iterator; 104 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; 105 typedef typename implementation_defined::node_traits node_traits; 106 typedef typename implementation_defined::node node; 107 typedef typename implementation_defined::node_ptr node_ptr; 108 typedef typename implementation_defined::const_node_ptr const_node_ptr; 109 typedef typename implementation_defined::node_algorithms node_algorithms; 110 111 static const bool constant_time_size = implementation_defined::constant_time_size; 112 /// @cond 113 private: 114 115 //noncopyable 116 BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree_impl) 117 118 /// @endcond 119 120 public: 121 122 typedef typename implementation_defined::insert_commit_data insert_commit_data; 123 124 //! @copydoc ::boost::intrusive::bstree::bstree() avltree_impl()125 avltree_impl() 126 : tree_type() 127 {} 128 129 //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &) avltree_impl(const key_compare & cmp,const value_traits & v_traits=value_traits ())130 explicit avltree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) 131 : tree_type(cmp, v_traits) 132 {} 133 134 //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &) 135 template<class Iterator> avltree_impl(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())136 avltree_impl( bool unique, Iterator b, Iterator e 137 , const key_compare &cmp = key_compare() 138 , const value_traits &v_traits = value_traits()) 139 : tree_type(unique, b, e, cmp, v_traits) 140 {} 141 142 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) avltree_impl(BOOST_RV_REF (avltree_impl)x)143 avltree_impl(BOOST_RV_REF(avltree_impl) x) 144 : tree_type(BOOST_MOVE_BASE(tree_type, x)) 145 {} 146 147 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) operator =(BOOST_RV_REF (avltree_impl)x)148 avltree_impl& operator=(BOOST_RV_REF(avltree_impl) x) 149 { return static_cast<avltree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } 150 151 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 152 153 //! @copydoc ::boost::intrusive::bstree::~bstree() 154 ~avltree_impl(); 155 156 //! @copydoc ::boost::intrusive::bstree::begin() 157 iterator begin(); 158 159 //! @copydoc ::boost::intrusive::bstree::begin()const 160 const_iterator begin() const; 161 162 //! @copydoc ::boost::intrusive::bstree::cbegin()const 163 const_iterator cbegin() const; 164 165 //! @copydoc ::boost::intrusive::bstree::end() 166 iterator end(); 167 168 //! @copydoc ::boost::intrusive::bstree::end()const 169 const_iterator end() const; 170 171 //! @copydoc ::boost::intrusive::bstree::cend()const 172 const_iterator cend() const; 173 174 //! @copydoc ::boost::intrusive::bstree::rbegin() 175 reverse_iterator rbegin(); 176 177 //! @copydoc ::boost::intrusive::bstree::rbegin()const 178 const_reverse_iterator rbegin() const; 179 180 //! @copydoc ::boost::intrusive::bstree::crbegin()const 181 const_reverse_iterator crbegin() const; 182 183 //! @copydoc ::boost::intrusive::bstree::rend() 184 reverse_iterator rend(); 185 186 //! @copydoc ::boost::intrusive::bstree::rend()const 187 const_reverse_iterator rend() const; 188 189 //! @copydoc ::boost::intrusive::bstree::crend()const 190 const_reverse_iterator crend() const; 191 192 //! @copydoc ::boost::intrusive::bstree::root() 193 iterator root(); 194 195 //! @copydoc ::boost::intrusive::bstree::root()const 196 const_iterator root() const; 197 198 //! @copydoc ::boost::intrusive::bstree::croot()const 199 const_iterator croot() const; 200 201 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) 202 static avltree_impl &container_from_end_iterator(iterator end_iterator); 203 204 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) 205 static const avltree_impl &container_from_end_iterator(const_iterator end_iterator); 206 207 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) 208 static avltree_impl &container_from_iterator(iterator it); 209 210 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) 211 static const avltree_impl &container_from_iterator(const_iterator it); 212 213 //! @copydoc ::boost::intrusive::bstree::key_comp()const 214 key_compare key_comp() const; 215 216 //! @copydoc ::boost::intrusive::bstree::value_comp()const 217 value_compare value_comp() const; 218 219 //! @copydoc ::boost::intrusive::bstree::empty()const 220 bool empty() const; 221 222 //! @copydoc ::boost::intrusive::bstree::size()const 223 size_type size() const; 224 225 //! @copydoc ::boost::intrusive::bstree::swap 226 void swap(avltree_impl& other); 227 228 //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer) 229 template <class Cloner, class Disposer> 230 void clone_from(const avltree_impl &src, Cloner cloner, Disposer disposer); 231 232 #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED 233 234 using tree_type::clone_from; 235 236 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 237 238 //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) 239 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (avltree_impl)src,Cloner cloner,Disposer disposer)240 void clone_from(BOOST_RV_REF(avltree_impl) src, Cloner cloner, Disposer disposer) 241 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } 242 243 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 244 245 //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) 246 iterator insert_equal(reference value); 247 248 //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference) 249 iterator insert_equal(const_iterator hint, reference value); 250 251 //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator) 252 template<class Iterator> 253 void insert_equal(Iterator b, Iterator e); 254 255 //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) 256 std::pair<iterator, bool> insert_unique(reference value); 257 258 //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference) 259 iterator insert_unique(const_iterator hint, reference value); 260 261 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) 262 template<class KeyType, class KeyTypeKeyCompare> 263 std::pair<iterator, bool> insert_unique_check 264 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); 265 266 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) 267 template<class KeyType, class KeyTypeKeyCompare> 268 std::pair<iterator, bool> insert_unique_check 269 (const_iterator hint, const KeyType &key 270 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); 271 272 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&) 273 std::pair<iterator, bool> insert_unique_check 274 (const key_type &key, insert_commit_data &commit_data); 275 276 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&) 277 std::pair<iterator, bool> insert_unique_check 278 (const_iterator hint, const key_type &key, insert_commit_data &commit_data); 279 280 //! @copydoc ::boost::intrusive::bstree::insert_unique_commit 281 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data); 282 283 //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator) 284 template<class Iterator> 285 void insert_unique(Iterator b, Iterator e); 286 287 //! @copydoc ::boost::intrusive::bstree::insert_before 288 iterator insert_before(const_iterator pos, reference value); 289 290 //! @copydoc ::boost::intrusive::bstree::push_back 291 void push_back(reference value); 292 293 //! @copydoc ::boost::intrusive::bstree::push_front 294 void push_front(reference value); 295 296 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator) 297 iterator erase(const_iterator i); 298 299 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator) 300 iterator erase(const_iterator b, const_iterator e); 301 302 //! @copydoc ::boost::intrusive::bstree::erase(const key_type &) 303 size_type erase(const key_type &key); 304 305 //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare) 306 template<class KeyType, class KeyTypeKeyCompare> 307 size_type erase(const KeyType& key, KeyTypeKeyCompare comp); 308 309 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer) 310 template<class Disposer> 311 iterator erase_and_dispose(const_iterator i, Disposer disposer); 312 313 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer) 314 template<class Disposer> 315 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); 316 317 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer) 318 template<class Disposer> 319 size_type erase_and_dispose(const key_type &key, Disposer disposer); 320 321 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) 322 template<class KeyType, class KeyTypeKeyCompare, class Disposer> 323 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); 324 325 //! @copydoc ::boost::intrusive::bstree::clear 326 void clear(); 327 328 //! @copydoc ::boost::intrusive::bstree::clear_and_dispose 329 template<class Disposer> 330 void clear_and_dispose(Disposer disposer); 331 332 //! @copydoc ::boost::intrusive::bstree::count(const key_type &ke)const 333 size_type count(const key_type &key) const; 334 335 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const 336 template<class KeyType, class KeyTypeKeyCompare> 337 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; 338 339 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) 340 iterator lower_bound(const key_type &key); 341 342 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) 343 template<class KeyType, class KeyTypeKeyCompare> 344 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); 345 346 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const 347 const_iterator lower_bound(const key_type &key) const; 348 349 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const 350 template<class KeyType, class KeyTypeKeyCompare> 351 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 352 353 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &key) 354 iterator upper_bound(const key_type &key); 355 356 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) 357 template<class KeyType, class KeyTypeKeyCompare> 358 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); 359 360 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const 361 const_iterator upper_bound(const key_type &key) const; 362 363 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const 364 template<class KeyType, class KeyTypeKeyCompare> 365 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 366 367 //! @copydoc ::boost::intrusive::bstree::find(const key_type &) 368 iterator find(const key_type &key); 369 370 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) 371 template<class KeyType, class KeyTypeKeyCompare> 372 iterator find(const KeyType& key, KeyTypeKeyCompare comp); 373 374 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const 375 const_iterator find(const key_type &key) const; 376 377 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const 378 template<class KeyType, class KeyTypeKeyCompare> 379 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; 380 381 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) 382 std::pair<iterator,iterator> equal_range(const key_type &key); 383 384 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) 385 template<class KeyType, class KeyTypeKeyCompare> 386 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); 387 388 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const 389 std::pair<const_iterator, const_iterator> 390 equal_range(const key_type &key) const; 391 392 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const 393 template<class KeyType, class KeyTypeKeyCompare> 394 std::pair<const_iterator, const_iterator> 395 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; 396 397 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) 398 std::pair<iterator,iterator> bounded_range 399 (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed); 400 401 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) 402 template<class KeyType, class KeyTypeKeyCompare> 403 std::pair<iterator,iterator> bounded_range 404 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); 405 406 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const 407 std::pair<const_iterator, const_iterator> 408 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; 409 410 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const 411 template<class KeyType, class KeyTypeKeyCompare> 412 std::pair<const_iterator, const_iterator> bounded_range 413 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; 414 415 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) 416 static iterator s_iterator_to(reference value); 417 418 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) 419 static const_iterator s_iterator_to(const_reference value); 420 421 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) 422 iterator iterator_to(reference value); 423 424 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const 425 const_iterator iterator_to(const_reference value) const; 426 427 //! @copydoc ::boost::intrusive::bstree::init_node(reference) 428 static void init_node(reference value); 429 430 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance 431 pointer unlink_leftmost_without_rebalance(); 432 433 //! @copydoc ::boost::intrusive::bstree::replace_node 434 void replace_node(iterator replace_this, reference with_this); 435 436 //! @copydoc ::boost::intrusive::bstree::remove_node 437 void remove_node(reference value); 438 439 //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&) 440 template<class T, class ...Options2> 441 void merge_unique(avltree<T, Options2...> &); 442 443 //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&) 444 template<class T, class ...Options2> 445 void merge_equal(avltree<T, Options2...> &); 446 447 friend bool operator< (const avltree_impl &x, const avltree_impl &y); 448 449 friend bool operator==(const avltree_impl &x, const avltree_impl &y); 450 451 friend bool operator!= (const avltree_impl &x, const avltree_impl &y); 452 453 friend bool operator>(const avltree_impl &x, const avltree_impl &y); 454 455 friend bool operator<=(const avltree_impl &x, const avltree_impl &y); 456 457 friend bool operator>=(const avltree_impl &x, const avltree_impl &y); 458 459 friend void swap(avltree_impl &x, avltree_impl &y); 460 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 461 }; 462 463 464 //! Helper metafunction to define a \c avltree that yields to the same type when the 465 //! same options (either explicitly or implicitly) are used. 466 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 467 template<class T, class ...Options> 468 #else 469 template<class T, class O1 = void, class O2 = void 470 , class O3 = void, class O4 = void 471 , class O5 = void, class O6 = void> 472 #endif 473 struct make_avltree 474 { 475 /// @cond 476 typedef typename pack_options 477 < avltree_defaults, 478 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 479 O1, O2, O3, O4, O5, O6 480 #else 481 Options... 482 #endif 483 >::type packed_options; 484 485 typedef typename detail::get_value_traits 486 <T, typename packed_options::proto_value_traits>::type value_traits; 487 488 typedef avltree_impl 489 < value_traits 490 , typename packed_options::key_of_value 491 , typename packed_options::compare 492 , typename packed_options::size_type 493 , packed_options::constant_time_size 494 , typename packed_options::header_holder_type 495 > implementation_defined; 496 /// @endcond 497 typedef implementation_defined type; 498 }; 499 500 501 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 502 503 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 504 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 505 #else 506 template<class T, class ...Options> 507 #endif 508 class avltree 509 : public make_avltree<T, 510 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 511 O1, O2, O3, O4, O5, O6 512 #else 513 Options... 514 #endif 515 >::type 516 { 517 typedef typename make_avltree 518 <T, 519 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 520 O1, O2, O3, O4, O5, O6 521 #else 522 Options... 523 #endif 524 >::type Base; 525 BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree) 526 527 public: 528 typedef typename Base::key_compare key_compare; 529 typedef typename Base::value_traits value_traits; 530 typedef typename Base::iterator iterator; 531 typedef typename Base::const_iterator const_iterator; 532 typedef typename Base::reverse_iterator reverse_iterator; 533 typedef typename Base::const_reverse_iterator const_reverse_iterator; 534 535 //Assert if passed value traits are compatible with the type 536 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); 537 avltree()538 BOOST_INTRUSIVE_FORCEINLINE avltree() 539 : Base() 540 {} 541 avltree(const key_compare & cmp,const value_traits & v_traits=value_traits ())542 BOOST_INTRUSIVE_FORCEINLINE explicit avltree( const key_compare &cmp, const value_traits &v_traits = value_traits()) 543 : Base(cmp, v_traits) 544 {} 545 546 template<class Iterator> avltree(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())547 BOOST_INTRUSIVE_FORCEINLINE avltree( bool unique, Iterator b, Iterator e 548 , const key_compare &cmp = key_compare() 549 , const value_traits &v_traits = value_traits()) 550 : Base(unique, b, e, cmp, v_traits) 551 {} 552 avltree(BOOST_RV_REF (avltree)x)553 BOOST_INTRUSIVE_FORCEINLINE avltree(BOOST_RV_REF(avltree) x) 554 : Base(BOOST_MOVE_BASE(Base, x)) 555 {} 556 operator =(BOOST_RV_REF (avltree)x)557 BOOST_INTRUSIVE_FORCEINLINE avltree& operator=(BOOST_RV_REF(avltree) x) 558 { return static_cast<avltree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 559 560 template <class Cloner, class Disposer> clone_from(const avltree & src,Cloner cloner,Disposer disposer)561 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const avltree &src, Cloner cloner, Disposer disposer) 562 { Base::clone_from(src, cloner, disposer); } 563 564 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (avltree)src,Cloner cloner,Disposer disposer)565 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(avltree) src, Cloner cloner, Disposer disposer) 566 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 567 container_from_end_iterator(iterator end_iterator)568 BOOST_INTRUSIVE_FORCEINLINE static avltree &container_from_end_iterator(iterator end_iterator) 569 { return static_cast<avltree &>(Base::container_from_end_iterator(end_iterator)); } 570 container_from_end_iterator(const_iterator end_iterator)571 BOOST_INTRUSIVE_FORCEINLINE static const avltree &container_from_end_iterator(const_iterator end_iterator) 572 { return static_cast<const avltree &>(Base::container_from_end_iterator(end_iterator)); } 573 container_from_iterator(iterator it)574 BOOST_INTRUSIVE_FORCEINLINE static avltree &container_from_iterator(iterator it) 575 { return static_cast<avltree &>(Base::container_from_iterator(it)); } 576 container_from_iterator(const_iterator it)577 BOOST_INTRUSIVE_FORCEINLINE static const avltree &container_from_iterator(const_iterator it) 578 { return static_cast<const avltree &>(Base::container_from_iterator(it)); } 579 }; 580 581 #endif 582 583 } //namespace intrusive 584 } //namespace boost 585 586 #include <boost/intrusive/detail/config_end.hpp> 587 588 #endif //BOOST_INTRUSIVE_AVLTREE_HPP 589