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 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 | |
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 */ |
411 | |