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
27namespace boost {
28namespace heap {
29namespace detail {
30
31typedef 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
54template<class T, class ...Options>
55#else
56template <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
63class 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 boost::allocator_rebind<typename heap_base_maker::allocator_argument, internal_type>::type 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
89public:
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 */
411

source code of boost/libs/heap/include/boost/heap/priority_queue.hpp