ceph/src/boost/libs/heap/include/boost/heap/pairing_heap.hpp

   1 // boost heap: pairing heap
   2 //
   3 // Copyright (C) 2010 Tim Blechmann
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_HEAP_PAIRING_HEAP_HPP
  10 #define BOOST_HEAP_PAIRING_HEAP_HPP
  11
  12 #include <algorithm>
  13 #include <utility>
  14 #include <vector>
  15
  16 #include <boost/assert.hpp>
  17
  18 #include <boost/heap/detail/heap_comparison.hpp>
  19 #include <boost/heap/detail/heap_node.hpp>
  20 #include <boost/heap/policies.hpp>
  21 #include <boost/heap/detail/stable_heap.hpp>
  22 #include <boost/heap/detail/tree_iterator.hpp>
  23
  24 #ifdef BOOST_HAS_PRAGMA_ONCE
  25 #pragma once
  26 #endif
  27
  28
  29 #ifndef BOOST_DOXYGEN_INVOKED
  30 #ifdef BOOST_HEAP_SANITYCHECKS
  31 #define BOOST_HEAP_ASSERT BOOST_ASSERT
  32 #else
  33 #define BOOST_HEAP_ASSERT(expression)
  34 #endif
  35 #endif
  36
  37 namespace boost  {
  38 namespace heap   {
  39 namespace detail {
  40
  41 typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
  42                               boost::parameter::optional<tag::compare>,
  43                               boost::parameter::optional<tag::stable>,
  44                               boost::parameter::optional<tag::constant_time_size>,
  45                               boost::parameter::optional<tag::stability_counter_type>
  46                              > pairing_heap_signature;
  47
  48 template <typename T, typename Parspec>
  49 struct make_pairing_heap_base
  50 {
  51     static const bool constant_time_size = parameter::binding<Parspec,
  52                                                               tag::constant_time_size,
  53                                                               boost::mpl::true_
  54                                                              >::type::value;
  55     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type;
  56     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument;
  57     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument;
  58
  59     typedef heap_node<typename base_type::internal_type, false> node_type;
  60
  61     typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
  62
  63     struct type:
  64         base_type,
  65         allocator_type
  66     {
  67         type(compare_argument const & arg):
  68             base_type(arg)
  69         {}
  70
  71 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
  72         type(type const & rhs):
  73             base_type(rhs), allocator_type(rhs)
  74         {}
  75
  76         type(type && rhs):
  77             base_type(std::move(static_cast<base_type&>(rhs))),
  78             allocator_type(std::move(static_cast<allocator_type&>(rhs)))
  79         {}
  80
  81         type & operator=(type && rhs)
  82         {
  83             base_type::operator=(std::move(static_cast<base_type&>(rhs)));
  84             allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
  85             return *this;
  86         }
  87
  88         type & operator=(type const & rhs)
  89         {
  90             base_type::operator=(static_cast<base_type const &>(rhs));
  91             allocator_type::operator=(static_cast<const allocator_type&>(rhs));
  92             return *this;
  93         }
  94 #endif
  95     };
  96 };
  97
  98 }
  99
 100 /**
 101  * \class pairing_heap
 102  * \brief pairing heap
 103  *
 104  * Pairing heaps are self-adjusting binary heaps. Although design and implementation are rather simple,
 105  * the complexity analysis is yet unsolved. For details, consult:
 106  *
 107  * Pettie, Seth (2005), "Towards a final analysis of pairing heaps",
 108  * Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174-183
 109  *
 110  * The template parameter T is the type to be managed by the container.
 111  * The user can specify additional options and if no options are provided default options are used.
 112  *
 113  * The container supports the following options:
 114  * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
 115  * - \c boost::heap::stable<>, defaults to \c stable<false>
 116  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
 117  * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
 118  * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
 119  *
 120  *
 121  */
 122 #ifdef BOOST_DOXYGEN_INVOKED
 123 template<class T, class ...Options>
 124 #else
 125 template <typename T,
 126           class A0 = boost::parameter::void_,
 127           class A1 = boost::parameter::void_,
 128           class A2 = boost::parameter::void_,
 129           class A3 = boost::parameter::void_,
 130           class A4 = boost::parameter::void_
 131          >
 132 #endif
 133 class pairing_heap:
 134     private detail::make_pairing_heap_base<T,
 135                                            typename detail::pairing_heap_signature::bind<A0, A1, A2, A3, A4>::type
 136                                           >::type
 137 {
 138     typedef typename detail::pairing_heap_signature::bind<A0, A1, A2, A3, A4>::type bound_args;
 139     typedef detail::make_pairing_heap_base<T, bound_args> base_maker;
 140     typedef typename base_maker::type super_t;
 141
 142     typedef typename super_t::internal_type internal_type;
 143     typedef typename super_t::size_holder_type size_holder;
 144     typedef typename base_maker::allocator_argument allocator_argument;
 145
 146 private:
 147     template <typename Heap1, typename Heap2>
 148     friend struct heap_merge_emulate;
 149
 150 #ifndef BOOST_DOXYGEN_INVOKED
 151     struct implementation_defined:
 152         detail::extract_allocator_types<typename base_maker::allocator_argument>
 153     {
 154         typedef T value_type;
 155         typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type;
 156         typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
 157
 158         typedef typename base_maker::compare_argument value_compare;
 159         typedef typename base_maker::allocator_type allocator_type;
 160
 161         typedef typename allocator_type::pointer node_pointer;
 162         typedef typename allocator_type::const_pointer const_node_pointer;
 163
 164         typedef detail::heap_node_list node_list_type;
 165         typedef typename node_list_type::iterator node_list_iterator;
 166         typedef typename node_list_type::const_iterator node_list_const_iterator;
 167
 168         typedef typename base_maker::node_type node;
 169
 170         typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
 171         typedef typename super_t::internal_compare internal_compare;
 172         typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
 173
 174         typedef detail::tree_iterator<node,
 175                                       const value_type,
 176                                       allocator_type,
 177                                       value_extractor,
 178                                       detail::pointer_to_reference<node>,
 179                                       false,
 180                                       false,
 181                                       value_compare
 182                                      > iterator;
 183
 184         typedef iterator const_iterator;
 185
 186         typedef detail::tree_iterator<node,
 187                                       const value_type,
 188                                       allocator_type,
 189                                       value_extractor,
 190                                       detail::pointer_to_reference<node>,
 191                                       false,
 192                                       true,
 193                                       value_compare
 194                                      > ordered_iterator;
 195     };
 196
 197     typedef typename implementation_defined::node node;
 198     typedef typename implementation_defined::node_pointer node_pointer;
 199     typedef typename implementation_defined::node_list_type node_list_type;
 200     typedef typename implementation_defined::node_list_iterator node_list_iterator;
 201     typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
 202     typedef typename implementation_defined::internal_compare internal_compare;
 203
 204     typedef boost::intrusive::list<detail::heap_node_base<true>,
 205                                    boost::intrusive::constant_time_size<false>
 206                                   > node_child_list;
 207 #endif
 208
 209 public:
 210     typedef T value_type;
 211
 212     typedef typename implementation_defined::size_type size_type;
 213     typedef typename implementation_defined::difference_type difference_type;
 214     typedef typename implementation_defined::value_compare value_compare;
 215     typedef typename implementation_defined::allocator_type allocator_type;
 216     typedef typename implementation_defined::reference reference;
 217     typedef typename implementation_defined::const_reference const_reference;
 218     typedef typename implementation_defined::pointer pointer;
 219     typedef typename implementation_defined::const_pointer const_pointer;
 220     /// \copydoc boost::heap::priority_queue::iterator
 221     typedef typename implementation_defined::iterator iterator;
 222     typedef typename implementation_defined::const_iterator const_iterator;
 223     typedef typename implementation_defined::ordered_iterator ordered_iterator;
 224
 225     typedef typename implementation_defined::handle_type handle_type;
 226
 227     static const bool constant_time_size = super_t::constant_time_size;
 228     static const bool has_ordered_iterators = true;
 229     static const bool is_mergable = true;
 230     static const bool is_stable = detail::extract_stable<bound_args>::value;
 231     static const bool has_reserve = false;
 232
 233     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
 234     explicit pairing_heap(value_compare const & cmp = value_compare()):
 235         super_t(cmp), root(NULL)
 236     {}
 237
 238     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
 239     pairing_heap(pairing_heap const & rhs):
 240         super_t(rhs), root(NULL)
 241     {
 242         if (rhs.empty())
 243             return;
 244
 245         clone_tree(rhs);
 246         size_holder::set_size(rhs.get_size());
 247     }
 248
 249 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 250     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
 251     pairing_heap(pairing_heap && rhs):
 252         super_t(std::move(rhs)), root(rhs.root)
 253     {
 254         rhs.root = NULL;
 255     }
 256
 257     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
 258     pairing_heap & operator=(pairing_heap && rhs)
 259     {
 260         super_t::operator=(std::move(rhs));
 261         root = rhs.root;
 262         rhs.root = NULL;
 263         return *this;
 264     }
 265 #endif
 266
 267     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs)
 268     pairing_heap & operator=(pairing_heap const & rhs)
 269     {
 270         clear();
 271         size_holder::set_size(rhs.get_size());
 272         static_cast<super_t&>(*this) = rhs;
 273
 274         clone_tree(rhs);
 275         return *this;
 276     }
 277
 278     ~pairing_heap(void)
 279     {
 280         while (!empty())
 281             pop();
 282     }
 283
 284     /// \copydoc boost::heap::priority_queue::empty
 285     bool empty(void) const
 286     {
 287         return root == NULL;
 288     }
 289
 290     /// \copydoc boost::heap::binomial_heap::size
 291     size_type size(void) const
 292     {
 293         if (constant_time_size)
 294             return size_holder::get_size();
 295
 296         if (root == NULL)
 297             return 0;
 298         else
 299             return detail::count_nodes(root);
 300     }
 301
 302     /// \copydoc boost::heap::priority_queue::max_size
 303     size_type max_size(void) const
 304     {
 305         return allocator_type::max_size();
 306     }
 307
 308     /// \copydoc boost::heap::priority_queue::clear
 309     void clear(void)
 310     {
 311         if (empty())
 312             return;
 313
 314         root->template clear_subtree<allocator_type>(*this);
 315         root->~node();
 316         allocator_type::deallocate(root, 1);
 317         root = NULL;
 318         size_holder::set_size(0);
 319     }
 320
 321     /// \copydoc boost::heap::priority_queue::get_allocator
 322     allocator_type get_allocator(void) const
 323     {
 324         return *this;
 325     }
 326
 327     /// \copydoc boost::heap::priority_queue::swap
 328     void swap(pairing_heap & rhs)
 329     {
 330         super_t::swap(rhs);
 331         std::swap(root, rhs.root);
 332     }
 333
 334
 335     /// \copydoc boost::heap::priority_queue::top
 336     const_reference top(void) const
 337     {
 338         BOOST_ASSERT(!empty());
 339
 340         return super_t::get_value(root->value);
 341     }
 342
 343     /**
 344      * \b Effects: Adds a new element to the priority queue. Returns handle to element
 345      *
 346      * \cond
 347      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 348      * \endcond
 349      *
 350      * \b Complexity: 2**2*log(log(N)) (amortized).
 351      *
 352      * */
 353     handle_type push(value_type const & v)
 354     {
 355         size_holder::increment();
 356
 357         node_pointer n = allocator_type::allocate(1);
 358
 359         new(n) node(super_t::make_node(v));
 360
 361         merge_node(n);
 362         return handle_type(n);
 363     }
 364
 365 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 366     /**
 367      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
 368      *
 369      * \cond
 370      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 371      * \endcond
 372      *
 373      * \b Complexity: 2**2*log(log(N)) (amortized).
 374      *
 375      * */
 376     template <class... Args>
 377     handle_type emplace(Args&&... args)
 378     {
 379         size_holder::increment();
 380
 381         node_pointer n = allocator_type::allocate(1);
 382
 383         new(n) node(super_t::make_node(std::forward<Args>(args)...));
 384
 385         merge_node(n);
 386         return handle_type(n);
 387     }
 388 #endif
 389
 390     /**
 391      * \b Effects: Removes the top element from the priority queue.
 392      *
 393      * \b Complexity: Logarithmic (amortized).
 394      *
 395      * */
 396     void pop(void)
 397     {
 398         BOOST_ASSERT(!empty());
 399
 400         erase(handle_type(root));
 401     }
 402
 403     /**
 404      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 405      *
 406      * \cond
 407      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 408      * \endcond
 409      *
 410      * \b Complexity: 2**2*log(log(N)) (amortized).
 411      *
 412      * */
 413     void update (handle_type handle, const_reference v)
 414     {
 415         handle.node_->value = super_t::make_node(v);
 416         update(handle);
 417     }
 418
 419     /**
 420      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 421      *
 422      * \cond
 423      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 424      * \endcond
 425      *
 426      * \b Complexity: 2**2*log(log(N)) (amortized).
 427      *
 428      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 429      * */
 430     void update (handle_type handle)
 431     {
 432         node_pointer n = handle.node_;
 433
 434         n->unlink();
 435         if (!n->children.empty())
 436             n = merge_nodes(n, merge_node_list(n->children));
 437
 438         if (n != root)
 439             merge_node(n);
 440     }
 441
 442      /**
 443      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 444      *
 445      * \cond
 446      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 447      * \endcond
 448      *
 449      * \b Complexity: 2**2*log(log(N)) (amortized).
 450      *
 451      * \b Note: The new value is expected to be greater than the current one
 452      * */
 453     void increase (handle_type handle, const_reference v)
 454     {
 455         update(handle, v);
 456     }
 457
 458     /**
 459      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 460      *
 461      * \cond
 462      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 463      * \endcond
 464      *
 465      * \b Complexity: 2**2*log(log(N)) (amortized).
 466      *
 467      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 468      * */
 469     void increase (handle_type handle)
 470     {
 471         update(handle);
 472     }
 473
 474     /**
 475      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 476      *
 477      * \cond
 478      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 479      * \endcond
 480      *
 481      * \b Complexity: 2**2*log(log(N)) (amortized).
 482      *
 483      * \b Note: The new value is expected to be less than the current one
 484      * */
 485     void decrease (handle_type handle, const_reference v)
 486     {
 487         update(handle, v);
 488     }
 489
 490     /**
 491      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 492      *
 493      * \cond
 494      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 495      * \endcond
 496      *
 497      * \b Complexity: 2**2*log(log(N)) (amortized).
 498      *
 499      * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 500      * */
 501     void decrease (handle_type handle)
 502     {
 503         update(handle);
 504     }
 505
 506     /**
 507      * \b Effects: Removes the element handled by \c handle from the priority_queue.
 508      *
 509      * \cond
 510      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 511      * \endcond
 512      *
 513      * \b Complexity: 2**2*log(log(N)) (amortized).
 514      * */
 515     void erase(handle_type handle)
 516     {
 517         node_pointer n = handle.node_;
 518         if (n != root) {
 519             n->unlink();
 520             if (!n->children.empty())
 521                 merge_node(merge_node_list(n->children));
 522         } else {
 523             if (!n->children.empty())
 524                 root = merge_node_list(n->children);
 525             else
 526                 root = NULL;
 527         }
 528
 529         size_holder::decrement();
 530         n->~node();
 531         allocator_type::deallocate(n, 1);
 532     }
 533
 534     /// \copydoc boost::heap::priority_queue::begin
 535     iterator begin(void) const
 536     {
 537         return iterator(root, super_t::value_comp());
 538     }
 539
 540     /// \copydoc boost::heap::priority_queue::end
 541     iterator end(void) const
 542     {
 543         return iterator(super_t::value_comp());
 544     }
 545
 546     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
 547     ordered_iterator ordered_begin(void) const
 548     {
 549         return ordered_iterator(root, super_t::value_comp());
 550     }
 551
 552     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
 553     ordered_iterator ordered_end(void) const
 554     {
 555         return ordered_iterator(NULL, super_t::value_comp());
 556     }
 557
 558
 559     /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
 560     static handle_type s_handle_from_iterator(iterator const & it)
 561     {
 562         node * ptr = const_cast<node *>(it.get_node());
 563         return handle_type(ptr);
 564     }
 565
 566     /**
 567      * \b Effects: Merge all elements from rhs into this
 568      *
 569      * \cond
 570      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
 571      * \endcond
 572      *
 573      * \b Complexity: 2**2*log(log(N)) (amortized).
 574      *
 575      * */
 576     void merge(pairing_heap & rhs)
 577     {
 578         if (rhs.empty())
 579             return;
 580
 581         merge_node(rhs.root);
 582
 583         size_holder::add(rhs.get_size());
 584         rhs.set_size(0);
 585         rhs.root = NULL;
 586
 587         super_t::set_stability_count((std::max)(super_t::get_stability_count(),
 588                                      rhs.get_stability_count()));
 589         rhs.set_stability_count(0);
 590     }
 591
 592     /// \copydoc boost::heap::priority_queue::value_comp
 593     value_compare const & value_comp(void) const
 594     {
 595         return super_t::value_comp();
 596     }
 597
 598     /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
 599     template <typename HeapType>
 600     bool operator<(HeapType const & rhs) const
 601     {
 602         return detail::heap_compare(*this, rhs);
 603     }
 604
 605     /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
 606     template <typename HeapType>
 607     bool operator>(HeapType const & rhs) const
 608     {
 609         return detail::heap_compare(rhs, *this);
 610     }
 611
 612     /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
 613     template <typename HeapType>
 614     bool operator>=(HeapType const & rhs) const
 615     {
 616         return !operator<(rhs);
 617     }
 618
 619     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
 620     template <typename HeapType>
 621     bool operator<=(HeapType const & rhs) const
 622     {
 623         return !operator>(rhs);
 624     }
 625
 626     /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
 627     template <typename HeapType>
 628     bool operator==(HeapType const & rhs) const
 629     {
 630         return detail::heap_equality(*this, rhs);
 631     }
 632
 633     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
 634     template <typename HeapType>
 635     bool operator!=(HeapType const & rhs) const
 636     {
 637         return !(*this == rhs);
 638     }
 639
 640 private:
 641 #if !defined(BOOST_DOXYGEN_INVOKED)
 642     void clone_tree(pairing_heap const & rhs)
 643     {
 644         BOOST_HEAP_ASSERT(root == NULL);
 645         if (rhs.empty())
 646             return;
 647
 648         root = allocator_type::allocate(1);
 649
 650         new(root) node(static_cast<node const &>(*rhs.root), static_cast<allocator_type&>(*this));
 651     }
 652
 653     void merge_node(node_pointer other)
 654     {
 655         BOOST_HEAP_ASSERT(other);
 656         if (root != NULL)
 657             root = merge_nodes(root, other);
 658         else
 659             root = other;
 660     }
 661
 662     node_pointer merge_node_list(node_child_list & children)
 663     {
 664         BOOST_HEAP_ASSERT(!children.empty());
 665         node_pointer merged = merge_first_pair(children);
 666         if (children.empty())
 667             return merged;
 668
 669         node_child_list node_list;
 670         node_list.push_back(*merged);
 671
 672         do {
 673             node_pointer next_merged = merge_first_pair(children);
 674             node_list.push_back(*next_merged);
 675         } while (!children.empty());
 676
 677         return merge_node_list(node_list);
 678     }
 679
 680     node_pointer merge_first_pair(node_child_list & children)
 681     {
 682         BOOST_HEAP_ASSERT(!children.empty());
 683         node_pointer first_child = static_cast<node_pointer>(&children.front());
 684         children.pop_front();
 685         if (children.empty())
 686             return first_child;
 687
 688         node_pointer second_child = static_cast<node_pointer>(&children.front());
 689         children.pop_front();
 690
 691         return merge_nodes(first_child, second_child);
 692     }
 693
 694     node_pointer merge_nodes(node_pointer node1, node_pointer node2)
 695     {
 696         if (super_t::operator()(node1->value, node2->value))
 697             std::swap(node1, node2);
 698
 699         node2->unlink();
 700         node1->children.push_front(*node2);
 701         return node1;
 702     }
 703
 704     node_pointer root;
 705 #endif
 706 };
 707
 708
 709 } /* namespace heap */
 710 } /* namespace boost */
 711
 712 #undef BOOST_HEAP_ASSERT
 713 #endif /* BOOST_HEAP_PAIRING_HEAP_HPP */