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() splaytree_impl()115 splaytree_impl() 116 : tree_type() 117 {} 118 119 //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &) splaytree_impl(const key_compare & cmp,const value_traits & v_traits=value_traits ())120 explicit splaytree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) 121 : tree_type(cmp, v_traits) 122 {} 123 124 //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &) 125 template<class Iterator> splaytree_impl(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())126 splaytree_impl( bool unique, Iterator b, Iterator e 127 , const key_compare &cmp = key_compare() 128 , const value_traits &v_traits = value_traits()) 129 : tree_type(cmp, v_traits) 130 { 131 if(unique) 132 this->insert_unique(b, e); 133 else 134 this->insert_equal(b, e); 135 } 136 137 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) splaytree_impl(BOOST_RV_REF (splaytree_impl)x)138 splaytree_impl(BOOST_RV_REF(splaytree_impl) x) 139 : tree_type(BOOST_MOVE_BASE(tree_type, x)) 140 {} 141 142 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) operator =(BOOST_RV_REF (splaytree_impl)x)143 splaytree_impl& operator=(BOOST_RV_REF(splaytree_impl) x) 144 { return static_cast<splaytree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } 145 146 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 147 //! @copydoc ::boost::intrusive::bstree::~bstree() 148 ~splaytree_impl(); 149 150 //! @copydoc ::boost::intrusive::bstree::begin() 151 iterator begin(); 152 153 //! @copydoc ::boost::intrusive::bstree::begin()const 154 const_iterator begin() const; 155 156 //! @copydoc ::boost::intrusive::bstree::cbegin()const 157 const_iterator cbegin() const; 158 159 //! @copydoc ::boost::intrusive::bstree::end() 160 iterator end(); 161 162 //! @copydoc ::boost::intrusive::bstree::end()const 163 const_iterator end() const; 164 165 //! @copydoc ::boost::intrusive::bstree::cend()const 166 const_iterator cend() const; 167 168 //! @copydoc ::boost::intrusive::bstree::rbegin() 169 reverse_iterator rbegin(); 170 171 //! @copydoc ::boost::intrusive::bstree::rbegin()const 172 const_reverse_iterator rbegin() const; 173 174 //! @copydoc ::boost::intrusive::bstree::crbegin()const 175 const_reverse_iterator crbegin() const; 176 177 //! @copydoc ::boost::intrusive::bstree::rend() 178 reverse_iterator rend(); 179 180 //! @copydoc ::boost::intrusive::bstree::rend()const 181 const_reverse_iterator rend() const; 182 183 //! @copydoc ::boost::intrusive::bstree::crend()const 184 const_reverse_iterator crend() const; 185 186 //! @copydoc ::boost::intrusive::bstree::root() 187 iterator root(); 188 189 //! @copydoc ::boost::intrusive::bstree::root()const 190 const_iterator root() const; 191 192 //! @copydoc ::boost::intrusive::bstree::croot()const 193 const_iterator croot() const; 194 195 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) 196 static splaytree_impl &container_from_end_iterator(iterator end_iterator); 197 198 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) 199 static const splaytree_impl &container_from_end_iterator(const_iterator end_iterator); 200 201 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) 202 static splaytree_impl &container_from_iterator(iterator it); 203 204 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) 205 static const splaytree_impl &container_from_iterator(const_iterator it); 206 207 //! @copydoc ::boost::intrusive::bstree::key_comp()const 208 key_compare key_comp() const; 209 210 //! @copydoc ::boost::intrusive::bstree::value_comp()const 211 value_compare value_comp() const; 212 213 //! @copydoc ::boost::intrusive::bstree::empty()const 214 bool empty() const; 215 216 //! @copydoc ::boost::intrusive::bstree::size()const 217 size_type size() const; 218 219 //! @copydoc ::boost::intrusive::bstree::swap 220 void swap(splaytree_impl& other); 221 222 //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer) 223 //! Additional notes: it also copies the alpha factor from the source container. 224 template <class Cloner, class Disposer> 225 void clone_from(const splaytree_impl &src, Cloner cloner, Disposer disposer); 226 227 #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED 228 229 using tree_type::clone_from; 230 231 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 232 233 //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) 234 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (splaytree_impl)src,Cloner cloner,Disposer disposer)235 void clone_from(BOOST_RV_REF(splaytree_impl) src, Cloner cloner, Disposer disposer) 236 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } 237 238 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 239 240 //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) 241 iterator insert_equal(reference value); 242 243 //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference) 244 iterator insert_equal(const_iterator hint, reference value); 245 246 //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator) 247 template<class Iterator> 248 void insert_equal(Iterator b, Iterator e); 249 250 //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) 251 std::pair<iterator, bool> insert_unique(reference value); 252 253 //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference) 254 iterator insert_unique(const_iterator hint, reference value); 255 256 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&) 257 std::pair<iterator, bool> insert_unique_check 258 (const key_type &key, insert_commit_data &commit_data); 259 260 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&) 261 std::pair<iterator, bool> insert_unique_check 262 (const_iterator hint, const key_type &key, insert_commit_data &commit_data); 263 264 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) 265 template<class KeyType, class KeyTypeKeyCompare> 266 std::pair<iterator, bool> insert_unique_check 267 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); 268 269 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) 270 template<class KeyType, class KeyTypeKeyCompare> 271 std::pair<iterator, bool> insert_unique_check 272 (const_iterator hint, const KeyType &key 273 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); 274 275 //! @copydoc ::boost::intrusive::bstree::insert_unique_commit 276 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data); 277 278 //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator) 279 template<class Iterator> 280 void insert_unique(Iterator b, Iterator e); 281 282 //! @copydoc ::boost::intrusive::bstree::insert_before 283 iterator insert_before(const_iterator pos, reference value); 284 285 //! @copydoc ::boost::intrusive::bstree::push_back 286 void push_back(reference value); 287 288 //! @copydoc ::boost::intrusive::bstree::push_front 289 void push_front(reference value); 290 291 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator) 292 iterator erase(const_iterator i); 293 294 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator) 295 iterator erase(const_iterator b, const_iterator e); 296 297 //! @copydoc ::boost::intrusive::bstree::erase(const key_type &) 298 size_type erase(const key_type &key); 299 300 //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare) 301 template<class KeyType, class KeyTypeKeyCompare> 302 size_type erase(const KeyType& key, KeyTypeKeyCompare comp); 303 304 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer) 305 template<class Disposer> 306 iterator erase_and_dispose(const_iterator i, Disposer disposer); 307 308 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer) 309 template<class Disposer> 310 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); 311 312 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer) 313 template<class Disposer> 314 size_type erase_and_dispose(const key_type &key, Disposer disposer); 315 316 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) 317 template<class KeyType, class KeyTypeKeyCompare, class Disposer> 318 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); 319 320 //! @copydoc ::boost::intrusive::bstree::clear 321 void clear(); 322 323 //! @copydoc ::boost::intrusive::bstree::clear_and_dispose 324 template<class Disposer> 325 void clear_and_dispose(Disposer disposer); 326 327 //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const 328 //! Additional note: non-const function, splaying is performed. 329 size_type count(const key_type &key); 330 331 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const 332 //! Additional note: non-const function, splaying is performed. 333 template<class KeyType, class KeyTypeKeyCompare> 334 size_type count(const KeyType &key, KeyTypeKeyCompare comp); 335 336 //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const 337 //! Additional note: const function, no splaying is performed 338 size_type count(const key_type &key) const; 339 340 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const 341 //! Additional note: const function, no splaying is performed 342 template<class KeyType, class KeyTypeKeyCompare> 343 size_type count(const KeyType &key, KeyTypeKeyCompare comp) const; 344 345 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) 346 //! Additional note: non-const function, splaying is performed. 347 iterator lower_bound(const key_type &key); 348 349 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const 350 //! Additional note: const function, no splaying is performed 351 const_iterator lower_bound(const key_type &key) const; 352 353 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) 354 //! Additional note: non-const function, splaying is performed for the first 355 //! element of the equal range of "key" 356 template<class KeyType, class KeyTypeKeyCompare> 357 iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp); 358 359 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const 360 //! Additional note: const function, no splaying is performed 361 template<class KeyType, class KeyTypeKeyCompare> 362 const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const; 363 364 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) 365 //! Additional note: non-const function, splaying is performed for the first 366 //! element of the equal range of "value" 367 iterator upper_bound(const key_type &key); 368 369 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const 370 //! Additional note: const function, no splaying is performed 371 const_iterator upper_bound(const key_type &key) const; 372 373 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) 374 //! Additional note: non-const function, splaying is performed for the first 375 //! element of the equal range of "key" 376 template<class KeyType, class KeyTypeKeyCompare> 377 iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp); 378 379 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const 380 //! Additional note: const function, no splaying is performed 381 template<class KeyType, class KeyTypeKeyCompare> 382 const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const; 383 384 //! @copydoc ::boost::intrusive::bstree::find(const key_type &) 385 //! Additional note: non-const function, splaying is performed for the first 386 //! element of the equal range of "value" 387 iterator find(const key_type &key); 388 389 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const 390 //! Additional note: const function, no splaying is performed 391 const_iterator find(const key_type &key) const; 392 393 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) 394 //! Additional note: non-const function, splaying is performed for the first 395 //! element of the equal range of "key" 396 template<class KeyType, class KeyTypeKeyCompare> 397 iterator find(const KeyType &key, KeyTypeKeyCompare comp); 398 399 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const 400 //! Additional note: const function, no splaying is performed 401 template<class KeyType, class KeyTypeKeyCompare> 402 const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const; 403 404 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) 405 //! Additional note: non-const function, splaying is performed for the first 406 //! element of the equal range of "value" 407 std::pair<iterator, iterator> equal_range(const key_type &key); 408 409 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const 410 //! Additional note: const function, no splaying is performed 411 std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const; 412 413 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) 414 //! Additional note: non-const function, splaying is performed for the first 415 //! element of the equal range of "key" 416 template<class KeyType, class KeyTypeKeyCompare> 417 std::pair<iterator, iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp); 418 419 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const 420 //! Additional note: const function, no splaying is performed 421 template<class KeyType, class KeyTypeKeyCompare> 422 std::pair<const_iterator, const_iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp) const; 423 424 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) 425 std::pair<iterator,iterator> bounded_range 426 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed); 427 428 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) 429 template<class KeyType, class KeyTypeKeyCompare> 430 std::pair<iterator,iterator> bounded_range 431 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); 432 433 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const 434 std::pair<const_iterator, const_iterator> bounded_range 435 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; 436 437 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const 438 template<class KeyType, class KeyTypeKeyCompare> 439 std::pair<const_iterator, const_iterator> bounded_range 440 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; 441 442 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) 443 static iterator s_iterator_to(reference value); 444 445 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) 446 static const_iterator s_iterator_to(const_reference value); 447 448 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) 449 iterator iterator_to(reference value); 450 451 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const 452 const_iterator iterator_to(const_reference value) const; 453 454 //! @copydoc ::boost::intrusive::bstree::init_node(reference) 455 static void init_node(reference value); 456 457 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance 458 pointer unlink_leftmost_without_rebalance(); 459 460 //! @copydoc ::boost::intrusive::bstree::replace_node 461 void replace_node(iterator replace_this, reference with_this); 462 463 //! @copydoc ::boost::intrusive::bstree::remove_node 464 void remove_node(reference value); 465 466 //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&) 467 template<class T, class ...Options2> 468 void merge_unique(splaytree<T, Options2...> &); 469 470 //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&) 471 template<class T, class ...Options2> 472 void merge_equal(splaytree<T, Options2...> &); 473 474 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 475 476 //! <b>Requires</b>: i must be a valid iterator of *this. 477 //! 478 //! <b>Effects</b>: Rearranges the container so that the element pointed by i 479 //! is placed as the root of the tree, improving future searches of this value. 480 //! 481 //! <b>Complexity</b>: Amortized logarithmic. 482 //! 483 //! <b>Throws</b>: Nothing. splay_up(iterator i)484 void splay_up(iterator i) 485 { return node_algorithms::splay_up(i.pointed_node(), tree_type::header_ptr()); } 486 487 //! <b>Effects</b>: Rearranges the container so that if *this stores an element 488 //! with a key equivalent to value the element is placed as the root of the 489 //! tree. If the element is not present returns the last node compared with the key. 490 //! If the tree is empty, end() is returned. 491 //! 492 //! <b>Complexity</b>: Amortized logarithmic. 493 //! 494 //! <b>Returns</b>: An iterator to the new root of the tree, end() if the tree is empty. 495 //! 496 //! <b>Throws</b>: If the comparison functor throws. 497 template<class KeyType, class KeyTypeKeyCompare> splay_down(const KeyType & key,KeyTypeKeyCompare comp)498 iterator splay_down(const KeyType &key, KeyTypeKeyCompare comp) 499 { 500 detail::key_nodeptr_comp<value_compare, value_traits> 501 key_node_comp(comp, &this->get_value_traits()); 502 node_ptr r = node_algorithms::splay_down(tree_type::header_ptr(), key, key_node_comp); 503 return iterator(r, this->priv_value_traits_ptr()); 504 } 505 506 //! <b>Effects</b>: Rearranges the container so that if *this stores an element 507 //! with a key equivalent to value the element is placed as the root of the 508 //! tree. 509 //! 510 //! <b>Complexity</b>: Amortized logarithmic. 511 //! 512 //! <b>Returns</b>: An iterator to the new root of the tree, end() if the tree is empty. 513 //! 514 //! <b>Throws</b>: If the predicate throws. splay_down(const key_type & key)515 iterator splay_down(const key_type &key) 516 { return this->splay_down(key, this->key_comp()); } 517 518 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 519 //! @copydoc ::boost::intrusive::bstree::rebalance 520 void rebalance(); 521 522 //! @copydoc ::boost::intrusive::bstree::rebalance_subtree 523 iterator rebalance_subtree(iterator root); 524 525 friend bool operator< (const splaytree_impl &x, const splaytree_impl &y); 526 527 friend bool operator==(const splaytree_impl &x, const splaytree_impl &y); 528 529 friend bool operator!= (const splaytree_impl &x, const splaytree_impl &y); 530 531 friend bool operator>(const splaytree_impl &x, const splaytree_impl &y); 532 533 friend bool operator<=(const splaytree_impl &x, const splaytree_impl &y); 534 535 friend bool operator>=(const splaytree_impl &x, const splaytree_impl &y); 536 537 friend void swap(splaytree_impl &x, splaytree_impl &y); 538 539 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 540 }; 541 542 //! Helper metafunction to define a \c splaytree that yields to the same type when the 543 //! same options (either explicitly or implicitly) are used. 544 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 545 template<class T, class ...Options> 546 #else 547 template<class T, class O1 = void, class O2 = void 548 , class O3 = void, class O4 = void 549 , class O5 = void, class O6 = void> 550 #endif 551 struct make_splaytree 552 { 553 /// @cond 554 typedef typename pack_options 555 < splaytree_defaults, 556 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 557 O1, O2, O3, O4, O5, O6 558 #else 559 Options... 560 #endif 561 >::type packed_options; 562 563 typedef typename detail::get_value_traits 564 <T, typename packed_options::proto_value_traits>::type value_traits; 565 566 typedef splaytree_impl 567 < value_traits 568 , typename packed_options::key_of_value 569 , typename packed_options::compare 570 , typename packed_options::size_type 571 , packed_options::constant_time_size 572 , typename packed_options::header_holder_type 573 > implementation_defined; 574 /// @endcond 575 typedef implementation_defined type; 576 }; 577 578 579 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 580 581 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 582 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 583 #else 584 template<class T, class ...Options> 585 #endif 586 class splaytree 587 : public make_splaytree<T, 588 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 589 O1, O2, O3, O4, O5, O6 590 #else 591 Options... 592 #endif 593 >::type 594 { 595 typedef typename make_splaytree 596 <T, 597 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 598 O1, O2, O3, O4, O5, O6 599 #else 600 Options... 601 #endif 602 >::type Base; 603 BOOST_MOVABLE_BUT_NOT_COPYABLE(splaytree) 604 605 public: 606 typedef typename Base::key_compare key_compare; 607 typedef typename Base::value_traits value_traits; 608 typedef typename Base::iterator iterator; 609 typedef typename Base::const_iterator const_iterator; 610 typedef typename Base::reverse_iterator reverse_iterator; 611 typedef typename Base::const_reverse_iterator const_reverse_iterator; 612 613 //Assert if passed value traits are compatible with the type 614 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); 615 splaytree()616 splaytree() 617 : Base() 618 {} 619 splaytree(const key_compare & cmp,const value_traits & v_traits=value_traits ())620 explicit splaytree( const key_compare &cmp, const value_traits &v_traits = value_traits()) 621 : Base(cmp, v_traits) 622 {} 623 624 template<class Iterator> splaytree(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())625 splaytree( bool unique, Iterator b, Iterator e 626 , const key_compare &cmp = key_compare() 627 , const value_traits &v_traits = value_traits()) 628 : Base(unique, b, e, cmp, v_traits) 629 {} 630 splaytree(BOOST_RV_REF (splaytree)x)631 splaytree(BOOST_RV_REF(splaytree) x) 632 : Base(BOOST_MOVE_BASE(Base, x)) 633 {} 634 operator =(BOOST_RV_REF (splaytree)x)635 splaytree& operator=(BOOST_RV_REF(splaytree) x) 636 { return static_cast<splaytree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 637 638 template <class Cloner, class Disposer> clone_from(const splaytree & src,Cloner cloner,Disposer disposer)639 void clone_from(const splaytree &src, Cloner cloner, Disposer disposer) 640 { Base::clone_from(src, cloner, disposer); } 641 642 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (splaytree)src,Cloner cloner,Disposer disposer)643 void clone_from(BOOST_RV_REF(splaytree) src, Cloner cloner, Disposer disposer) 644 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 645 container_from_end_iterator(iterator end_iterator)646 static splaytree &container_from_end_iterator(iterator end_iterator) 647 { return static_cast<splaytree &>(Base::container_from_end_iterator(end_iterator)); } 648 container_from_end_iterator(const_iterator end_iterator)649 static const splaytree &container_from_end_iterator(const_iterator end_iterator) 650 { return static_cast<const splaytree &>(Base::container_from_end_iterator(end_iterator)); } 651 container_from_iterator(iterator it)652 static splaytree &container_from_iterator(iterator it) 653 { return static_cast<splaytree &>(Base::container_from_iterator(it)); } 654 container_from_iterator(const_iterator it)655 static const splaytree &container_from_iterator(const_iterator it) 656 { return static_cast<const splaytree &>(Base::container_from_iterator(it)); } 657 }; 658 659 #endif 660 661 } //namespace intrusive 662 } //namespace boost 663 664 #include <boost/intrusive/detail/config_end.hpp> 665 666 #endif //BOOST_INTRUSIVE_SPLAYTREE_HPP 667