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