]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 */ |