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