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

   1 // boost heap: wrapper for stl 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_PRIORITY_QUEUE_HPP
  10 #define BOOST_HEAP_PRIORITY_QUEUE_HPP
  11
  12 #include <algorithm>
  13 #include <queue>
  14 #include <utility>
  15 #include <vector>
  16
  17 #include <boost/assert.hpp>
  18
  19 #include <boost/heap/detail/heap_comparison.hpp>
  20 #include <boost/heap/detail/stable_heap.hpp>
  21
  22 #ifdef BOOST_HAS_PRAGMA_ONCE
  23 #pragma once
  24 #endif
  25
  26
  27 namespace boost  {
  28 namespace heap   {
  29 namespace detail {
  30
  31 typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
  32                               boost::parameter::optional<tag::compare>,
  33                               boost::parameter::optional<tag::stable>,
  34                               boost::parameter::optional<tag::stability_counter_type>
  35                              > priority_queue_signature;
  36 }
  37
  38 /**
  39  * \class priority_queue
  40  * \brief priority queue, based on stl heap functions
  41  *
  42  * The priority_queue class is a wrapper for the stl heap functions.<br>
  43  * The template parameter T is the type to be managed by the container.
  44  * The user can specify additional options and if no options are provided default options are used.
  45  *
  46  * The container supports the following options:
  47  * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
  48  * - \c boost::heap::stable<>, defaults to \c stable<false>
  49  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
  50  * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
  51  *
  52  */
  53 #ifdef BOOST_DOXYGEN_INVOKED
  54 template<class T, class ...Options>
  55 #else
  56 template <typename T,
  57           class A0 = boost::parameter::void_,
  58           class A1 = boost::parameter::void_,
  59           class A2 = boost::parameter::void_,
  60           class A3 = boost::parameter::void_
  61          >
  62 #endif
  63 class priority_queue:
  64     private detail::make_heap_base<T, typename detail::priority_queue_signature::bind<A0, A1, A2, A3>::type, false>::type
  65 {
  66     typedef detail::make_heap_base<T, typename detail::priority_queue_signature::bind<A0, A1, A2, A3>::type, false> heap_base_maker;
  67
  68     typedef typename heap_base_maker::type super_t;
  69     typedef typename super_t::internal_type internal_type;
  70     typedef typename heap_base_maker::allocator_argument::template rebind<internal_type>::other internal_type_allocator;
  71     typedef std::vector<internal_type, internal_type_allocator> container_type;
  72
  73     template <typename Heap1, typename Heap2>
  74     friend struct detail::heap_merge_emulate;
  75
  76     container_type q_;
  77
  78 #ifndef BOOST_DOXYGEN_INVOKED
  79     struct implementation_defined:
  80         detail::extract_allocator_types<typename heap_base_maker::allocator_argument>
  81     {
  82         typedef typename heap_base_maker::compare_argument value_compare;
  83         typedef detail::stable_heap_iterator<T, typename container_type::const_iterator, super_t> iterator;
  84         typedef iterator const_iterator;
  85         typedef typename container_type::allocator_type allocator_type;
  86     };
  87 #endif
  88
  89 public:
  90     typedef T value_type;
  91     typedef typename implementation_defined::size_type size_type;
  92     typedef typename implementation_defined::difference_type difference_type;
  93     typedef typename implementation_defined::value_compare value_compare;
  94     typedef typename implementation_defined::allocator_type allocator_type;
  95     typedef typename implementation_defined::reference reference;
  96     typedef typename implementation_defined::const_reference const_reference;
  97     typedef typename implementation_defined::pointer pointer;
  98     typedef typename implementation_defined::const_pointer const_pointer;
  99     /**
 100      * \b Note: The iterator does not traverse the priority queue in order of the priorities.
 101      * */
 102     typedef typename implementation_defined::iterator iterator;
 103     typedef typename implementation_defined::const_iterator const_iterator;
 104
 105     static const bool constant_time_size = true;
 106     static const bool has_ordered_iterators = false;
 107     static const bool is_mergable = false;
 108     static const bool is_stable = heap_base_maker::is_stable;
 109     static const bool has_reserve = true;
 110
 111     /**
 112      * \b Effects: constructs an empty priority queue.
 113      *
 114      * \b Complexity: Constant.
 115      *
 116      * */
 117     explicit priority_queue(value_compare const & cmp = value_compare()):
 118         super_t(cmp)
 119     {}
 120
 121     /**
 122      * \b Effects: copy-constructs priority queue from rhs.
 123      *
 124      * \b Complexity: Linear.
 125      *
 126      * */
 127     priority_queue (priority_queue const & rhs):
 128         super_t(rhs), q_(rhs.q_)
 129     {}
 130
 131 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 132     /**
 133      * \b Effects: C++11-style move constructor.
 134      *
 135      * \b Complexity: Constant.
 136      *
 137      * \b Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
 138      * */
 139     priority_queue(priority_queue && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<super_t>::value):
 140         super_t(std::move(rhs)), q_(std::move(rhs.q_))
 141     {}
 142
 143     /**
 144      * \b Effects: C++11-style move assignment.
 145      *
 146      * \b Complexity: Constant.
 147      *
 148      * \b Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
 149      * */
 150     priority_queue & operator=(priority_queue && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_assignable<super_t>::value)
 151     {
 152         super_t::operator=(std::move(rhs));
 153         q_ = std::move(rhs.q_);
 154         return *this;
 155     }
 156 #endif
 157
 158     /**
 159      * \b Effects: Assigns priority queue from rhs.
 160      *
 161      * \b Complexity: Linear.
 162      *
 163      * */
 164     priority_queue & operator=(priority_queue const & rhs)
 165     {
 166         static_cast<super_t&>(*this) = static_cast<super_t const &>(rhs);
 167         q_ = rhs.q_;
 168         return *this;
 169     }
 170
 171     /**
 172      * \b Effects: Returns true, if the priority queue contains no elements.
 173      *
 174      * \b Complexity: Constant.
 175      *
 176      * */
 177     bool empty(void) const BOOST_NOEXCEPT
 178     {
 179         return q_.empty();
 180     }
 181
 182     /**
 183      * \b Effects: Returns the number of elements contained in the priority queue.
 184      *
 185      * \b Complexity: Constant.
 186      *
 187      * */
 188     size_type size(void) const BOOST_NOEXCEPT
 189     {
 190         return q_.size();
 191     }
 192
 193     /**
 194      * \b Effects: Returns the maximum number of elements the priority queue can contain.
 195      *
 196      * \b Complexity: Constant.
 197      *
 198      * */
 199     size_type max_size(void) const BOOST_NOEXCEPT
 200     {
 201         return q_.max_size();
 202     }
 203
 204     /**
 205      * \b Effects: Removes all elements from the priority queue.
 206      *
 207      * \b Complexity: Linear.
 208      *
 209      * */
 210     void clear(void) BOOST_NOEXCEPT
 211     {
 212         q_.clear();
 213     }
 214
 215     /**
 216      * \b Effects: Returns allocator.
 217      *
 218      * \b Complexity: Constant.
 219      *
 220      * */
 221     allocator_type get_allocator(void) const
 222     {
 223         return q_.get_allocator();
 224     }
 225
 226     /**
 227      * \b Effects: Returns a const_reference to the maximum element.
 228      *
 229      * \b Complexity: Constant.
 230      *
 231      * */
 232     const_reference top(void) const
 233     {
 234         BOOST_ASSERT(!empty());
 235         return super_t::get_value(q_.front());
 236     }
 237
 238     /**
 239      * \b Effects: Adds a new element to the priority queue.
 240      *
 241      * \b Complexity: Logarithmic (amortized). Linear (worst case).
 242      *
 243      * */
 244     void push(value_type const & v)
 245     {
 246         q_.push_back(super_t::make_node(v));
 247         std::push_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
 248     }
 249
 250 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 251     /**
 252      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place.
 253      *
 254      * \b Complexity: Logarithmic (amortized). Linear (worst case).
 255      *
 256      * */
 257     template <class... Args>
 258     void emplace(Args&&... args)
 259     {
 260         q_.emplace_back(super_t::make_node(std::forward<Args>(args)...));
 261         std::push_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
 262     }
 263 #endif
 264
 265     /**
 266      * \b Effects: Removes the top element from the priority queue.
 267      *
 268      * \b Complexity: Logarithmic (amortized). Linear (worst case).
 269      *
 270      * */
 271     void pop(void)
 272     {
 273         BOOST_ASSERT(!empty());
 274         std::pop_heap(q_.begin(), q_.end(), static_cast<super_t const &>(*this));
 275         q_.pop_back();
 276     }
 277
 278     /**
 279      * \b Effects: Swaps two priority queues.
 280      *
 281      * \b Complexity: Constant.
 282      *
 283      * */
 284     void swap(priority_queue & rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<super_t>::value && boost::is_nothrow_move_assignable<super_t>::value)
 285     {
 286         super_t::swap(rhs);
 287         q_.swap(rhs.q_);
 288     }
 289
 290     /**
 291      * \b Effects: Returns an iterator to the first element contained in the priority queue.
 292      *
 293      * \b Complexity: Constant.
 294      *
 295      * */
 296     iterator begin(void) const BOOST_NOEXCEPT
 297     {
 298         return iterator(q_.begin());
 299     }
 300
 301     /**
 302      * \b Effects: Returns an iterator to the end of the priority queue.
 303      *
 304      * \b Complexity: Constant.
 305      *
 306      * */
 307     iterator end(void) const BOOST_NOEXCEPT
 308     {
 309         return iterator(q_.end());
 310     }
 311
 312     /**
 313      * \b Effects: Reserves memory for element_count elements
 314      *
 315      * \b Complexity: Linear.
 316      *
 317      * \b Node: Invalidates iterators
 318      *
 319      * */
 320     void reserve(size_type element_count)
 321     {
 322         q_.reserve(element_count);
 323     }
 324
 325     /**
 326      * \b Effect: Returns the value_compare object used by the priority queue
 327      *
 328      * */
 329     value_compare const & value_comp(void) const
 330     {
 331         return super_t::value_comp();
 332     }
 333
 334     /**
 335      * \b Returns: Element-wise comparison of heap data structures
 336      *
 337      * \b Requirement: the \c value_compare object of both heaps must match.
 338      *
 339      * */
 340     template <typename HeapType>
 341     bool operator<(HeapType const & rhs) const
 342     {
 343         return detail::heap_compare(*this, rhs);
 344     }
 345
 346     /**
 347      * \b Returns: Element-wise comparison of heap data structures
 348      *
 349      * \b Requirement: the \c value_compare object of both heaps must match.
 350      *
 351      * */
 352     template <typename HeapType>
 353     bool operator>(HeapType const & rhs) const
 354     {
 355         return detail::heap_compare(rhs, *this);
 356     }
 357
 358     /**
 359      * \b Returns: Element-wise comparison of heap data structures
 360      *
 361      * \b Requirement: the \c value_compare object of both heaps must match.
 362      *
 363      * */
 364     template <typename HeapType>
 365     bool operator>=(HeapType const & rhs) const
 366     {
 367         return !operator<(rhs);
 368     }
 369
 370     /**
 371      * \b Returns: Element-wise comparison of heap data structures
 372      *
 373      * \b Requirement: the \c value_compare object of both heaps must match.
 374      *
 375      * */
 376     template <typename HeapType>
 377     bool operator<=(HeapType const & rhs) const
 378     {
 379         return !operator>(rhs);
 380     }
 381
 382     /** \brief Equivalent comparison
 383      * \b Returns: True, if both heap data structures are equivalent.
 384      *
 385      * \b Requirement: the \c value_compare object of both heaps must match.
 386      *
 387      * */
 388     template <typename HeapType>
 389     bool operator==(HeapType const & rhs) const
 390     {
 391         return detail::heap_equality(*this, rhs);
 392     }
 393
 394     /** \brief Equivalent comparison
 395      * \b Returns: True, if both heap data structures are not equivalent.
 396      *
 397      * \b Requirement: the \c value_compare object of both heaps must match.
 398      *
 399      * */
 400     template <typename HeapType>
 401     bool operator!=(HeapType const & rhs) const
 402     {
 403         return !(*this == rhs);
 404     }
 405 };
 406
 407 } /* namespace heap */
 408 } /* namespace boost */
 409
 410 #endif /* BOOST_HEAP_PRIORITY_QUEUE_HPP */