]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // // boost heap: d-ary heap as containter adaptor |
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_D_ARY_HEAP_HPP | |
10 | #define BOOST_HEAP_D_ARY_HEAP_HPP | |
11 | ||
12 | #include <algorithm> | |
13 | #include <utility> | |
14 | #include <vector> | |
15 | ||
16 | #include <boost/assert.hpp> | |
17 | ||
18 | #include <boost/mem_fn.hpp> | |
19 | #include <boost/heap/detail/heap_comparison.hpp> | |
20 | #include <boost/heap/detail/ordered_adaptor_iterator.hpp> | |
21 | #include <boost/heap/detail/stable_heap.hpp> | |
22 | #include <boost/heap/detail/mutable_heap.hpp> | |
23 | ||
24 | #ifdef BOOST_HAS_PRAGMA_ONCE | |
25 | #pragma once | |
26 | #endif | |
27 | ||
28 | ||
29 | #ifndef BOOST_DOXYGEN_INVOKED | |
30 | #ifdef BOOST_HEAP_SANITYCHECKS | |
31 | #define BOOST_HEAP_ASSERT BOOST_ASSERT | |
32 | #else | |
33 | #define BOOST_HEAP_ASSERT(expression) | |
34 | #endif | |
35 | #endif | |
36 | ||
37 | namespace boost { | |
38 | namespace heap { | |
39 | namespace detail { | |
40 | ||
41 | struct nop_index_updater | |
42 | { | |
43 | template <typename T> | |
44 | static void run(T &, std::size_t) | |
45 | {} | |
46 | }; | |
47 | ||
48 | typedef parameter::parameters<boost::parameter::required<tag::arity>, | |
49 | boost::parameter::optional<tag::allocator>, | |
50 | boost::parameter::optional<tag::compare>, | |
51 | boost::parameter::optional<tag::stable>, | |
52 | boost::parameter::optional<tag::stability_counter_type>, | |
53 | boost::parameter::optional<tag::constant_time_size> | |
54 | > d_ary_heap_signature; | |
55 | ||
56 | ||
57 | /* base class for d-ary heap */ | |
58 | template <typename T, | |
59 | class BoundArgs, | |
60 | class IndexUpdater> | |
61 | class d_ary_heap: | |
62 | private make_heap_base<T, BoundArgs, false>::type | |
63 | { | |
64 | typedef make_heap_base<T, BoundArgs, false> heap_base_maker; | |
65 | ||
66 | typedef typename heap_base_maker::type super_t; | |
67 | typedef typename super_t::internal_type internal_type; | |
68 | ||
69 | typedef typename heap_base_maker::allocator_argument::template rebind<internal_type>::other internal_type_allocator; | |
70 | typedef std::vector<internal_type, internal_type_allocator> container_type; | |
71 | typedef typename container_type::const_iterator container_iterator; | |
72 | ||
73 | typedef IndexUpdater index_updater; | |
74 | ||
75 | container_type q_; | |
76 | ||
77 | static const unsigned int D = parameter::binding<BoundArgs, tag::arity>::type::value; | |
78 | ||
79 | template <typename Heap1, typename Heap2> | |
80 | friend struct heap_merge_emulate; | |
81 | ||
82 | struct implementation_defined: | |
83 | extract_allocator_types<typename heap_base_maker::allocator_argument> | |
84 | { | |
85 | typedef T value_type; | |
86 | typedef typename detail::extract_allocator_types<typename heap_base_maker::allocator_argument>::size_type size_type; | |
87 | ||
88 | typedef typename heap_base_maker::compare_argument value_compare; | |
89 | typedef typename heap_base_maker::allocator_argument allocator_type; | |
90 | ||
91 | struct ordered_iterator_dispatcher | |
92 | { | |
93 | static size_type max_index(const d_ary_heap * heap) | |
94 | { | |
95 | return heap->q_.size() - 1; | |
96 | } | |
97 | ||
98 | static bool is_leaf(const d_ary_heap * heap, size_type index) | |
99 | { | |
100 | return !heap->not_leaf(index); | |
101 | } | |
102 | ||
103 | static std::pair<size_type, size_type> get_child_nodes(const d_ary_heap * heap, size_type index) | |
104 | { | |
105 | BOOST_HEAP_ASSERT(!is_leaf(heap, index)); | |
106 | return std::make_pair(d_ary_heap::first_child_index(index), | |
107 | heap->last_child_index(index)); | |
108 | } | |
109 | ||
110 | static internal_type const & get_internal_value(const d_ary_heap * heap, size_type index) | |
111 | { | |
112 | return heap->q_[index]; | |
113 | } | |
114 | ||
115 | static value_type const & get_value(internal_type const & arg) | |
116 | { | |
117 | return super_t::get_value(arg); | |
118 | } | |
119 | }; | |
120 | ||
121 | typedef detail::ordered_adaptor_iterator<const value_type, | |
122 | internal_type, | |
123 | d_ary_heap, | |
124 | allocator_type, | |
125 | typename super_t::internal_compare, | |
126 | ordered_iterator_dispatcher | |
127 | > ordered_iterator; | |
128 | ||
129 | typedef detail::stable_heap_iterator<const value_type, container_iterator, super_t> iterator; | |
130 | typedef iterator const_iterator; | |
131 | typedef void * handle_type; | |
132 | ||
133 | }; | |
134 | ||
135 | typedef typename implementation_defined::ordered_iterator_dispatcher ordered_iterator_dispatcher; | |
136 | ||
137 | public: | |
138 | typedef T value_type; | |
139 | ||
140 | typedef typename implementation_defined::size_type size_type; | |
141 | typedef typename implementation_defined::difference_type difference_type; | |
142 | typedef typename implementation_defined::value_compare value_compare; | |
143 | typedef typename implementation_defined::allocator_type allocator_type; | |
144 | typedef typename implementation_defined::reference reference; | |
145 | typedef typename implementation_defined::const_reference const_reference; | |
146 | typedef typename implementation_defined::pointer pointer; | |
147 | typedef typename implementation_defined::const_pointer const_pointer; | |
148 | typedef typename implementation_defined::iterator iterator; | |
149 | typedef typename implementation_defined::const_iterator const_iterator; | |
150 | typedef typename implementation_defined::ordered_iterator ordered_iterator; | |
151 | typedef typename implementation_defined::handle_type handle_type; | |
152 | ||
153 | static const bool is_stable = extract_stable<BoundArgs>::value; | |
154 | ||
155 | explicit d_ary_heap(value_compare const & cmp = value_compare()): | |
156 | super_t(cmp) | |
157 | {} | |
158 | ||
159 | d_ary_heap(d_ary_heap const & rhs): | |
160 | super_t(rhs), q_(rhs.q_) | |
161 | {} | |
162 | ||
163 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
164 | d_ary_heap(d_ary_heap && rhs): | |
165 | super_t(std::move(rhs)), q_(std::move(rhs.q_)) | |
166 | {} | |
167 | ||
168 | d_ary_heap & operator=(d_ary_heap && rhs) | |
169 | { | |
170 | super_t::operator=(std::move(rhs)); | |
171 | q_ = std::move(rhs.q_); | |
172 | return *this; | |
173 | } | |
174 | #endif | |
175 | ||
176 | d_ary_heap & operator=(d_ary_heap const & rhs) | |
177 | { | |
178 | static_cast<super_t&>(*this) = static_cast<super_t const &>(rhs); | |
179 | q_ = rhs.q_; | |
180 | return *this; | |
181 | } | |
182 | ||
183 | bool empty(void) const | |
184 | { | |
185 | return q_.empty(); | |
186 | } | |
187 | ||
188 | size_type size(void) const | |
189 | { | |
190 | return q_.size(); | |
191 | } | |
192 | ||
193 | size_type max_size(void) const | |
194 | { | |
195 | return q_.max_size(); | |
196 | } | |
197 | ||
198 | void clear(void) | |
199 | { | |
200 | q_.clear(); | |
201 | } | |
202 | ||
203 | allocator_type get_allocator(void) const | |
204 | { | |
205 | return q_.get_allocator(); | |
206 | } | |
207 | ||
208 | value_type const & top(void) const | |
209 | { | |
210 | BOOST_ASSERT(!empty()); | |
211 | return super_t::get_value(q_.front()); | |
212 | } | |
213 | ||
214 | void push(value_type const & v) | |
215 | { | |
216 | q_.push_back(super_t::make_node(v)); | |
217 | reset_index(size() - 1, size() - 1); | |
218 | siftup(q_.size() - 1); | |
219 | } | |
220 | ||
221 | #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
222 | template <class... Args> | |
223 | void emplace(Args&&... args) | |
224 | { | |
225 | q_.emplace_back(super_t::make_node(std::forward<Args>(args)...)); | |
226 | reset_index(size() - 1, size() - 1); | |
227 | siftup(q_.size() - 1); | |
228 | } | |
229 | #endif | |
230 | void pop(void) | |
231 | { | |
232 | BOOST_ASSERT(!empty()); | |
233 | std::swap(q_.front(), q_.back()); | |
234 | q_.pop_back(); | |
235 | ||
236 | if (q_.empty()) | |
237 | return; | |
238 | ||
239 | reset_index(0, 0); | |
240 | siftdown(0); | |
241 | } | |
242 | ||
243 | void swap(d_ary_heap & rhs) | |
244 | { | |
245 | super_t::swap(rhs); | |
246 | q_.swap(rhs.q_); | |
247 | } | |
248 | ||
249 | iterator begin(void) const | |
250 | { | |
251 | return iterator(q_.begin()); | |
252 | } | |
253 | ||
254 | iterator end(void) const | |
255 | { | |
256 | return iterator(q_.end()); | |
257 | } | |
258 | ||
259 | ordered_iterator ordered_begin(void) const | |
260 | { | |
261 | return ordered_iterator(0, this, super_t::get_internal_cmp()); | |
262 | } | |
263 | ||
264 | ordered_iterator ordered_end(void) const | |
265 | { | |
266 | return ordered_iterator(size(), this, super_t::get_internal_cmp()); | |
267 | } | |
268 | ||
269 | void reserve (size_type element_count) | |
270 | { | |
271 | q_.reserve(element_count); | |
272 | } | |
273 | ||
274 | value_compare const & value_comp(void) const | |
275 | { | |
276 | return super_t::value_comp(); | |
277 | } | |
278 | ||
279 | private: | |
280 | void reset_index(size_type index, size_type new_index) | |
281 | { | |
282 | BOOST_HEAP_ASSERT(index < q_.size()); | |
283 | index_updater::run(q_[index], new_index); | |
284 | } | |
285 | ||
286 | void siftdown(size_type index) | |
287 | { | |
288 | while (not_leaf(index)) { | |
289 | size_type max_child_index = top_child_index(index); | |
290 | if (!super_t::operator()(q_[max_child_index], q_[index])) { | |
291 | reset_index(index, max_child_index); | |
292 | reset_index(max_child_index, index); | |
293 | std::swap(q_[max_child_index], q_[index]); | |
294 | index = max_child_index; | |
295 | } | |
296 | else | |
297 | return; | |
298 | } | |
299 | } | |
300 | ||
301 | /* returns new index */ | |
302 | void siftup(size_type index) | |
303 | { | |
304 | while (index != 0) { | |
305 | size_type parent = parent_index(index); | |
306 | ||
307 | if (super_t::operator()(q_[parent], q_[index])) { | |
308 | reset_index(index, parent); | |
309 | reset_index(parent, index); | |
310 | std::swap(q_[parent], q_[index]); | |
311 | index = parent; | |
312 | } | |
313 | else | |
314 | return; | |
315 | } | |
316 | } | |
317 | ||
318 | bool not_leaf(size_type index) const | |
319 | { | |
320 | const size_t first_child = first_child_index(index); | |
321 | return first_child < q_.size(); | |
322 | } | |
323 | ||
324 | size_type top_child_index(size_type index) const | |
325 | { | |
326 | // invariant: index is not a leaf, so the iterator range is not empty | |
327 | ||
328 | const size_t first_index = first_child_index(index); | |
329 | typedef typename container_type::const_iterator container_iterator; | |
330 | ||
331 | const container_iterator first_child = q_.begin() + first_index; | |
332 | const container_iterator end = q_.end(); | |
333 | ||
334 | const size_type max_elements = std::distance(first_child, end); | |
335 | ||
336 | const container_iterator last_child = (max_elements > D) ? first_child + D | |
337 | : end; | |
338 | ||
339 | const container_iterator min_element = std::max_element(first_child, last_child, static_cast<super_t const &>(*this)); | |
340 | ||
341 | return min_element - q_.begin(); | |
342 | } | |
343 | ||
344 | static size_type parent_index(size_type index) | |
345 | { | |
346 | return (index - 1) / D; | |
347 | } | |
348 | ||
349 | static size_type first_child_index(size_type index) | |
350 | { | |
351 | return index * D + 1; | |
352 | } | |
353 | ||
354 | size_type last_child_index(size_type index) const | |
355 | { | |
356 | const size_t first_index = first_child_index(index); | |
357 | const size_type last_index = (std::min)(first_index + D - 1, size() - 1); | |
358 | ||
359 | return last_index; | |
360 | } | |
361 | ||
362 | template<typename U, | |
363 | typename V, | |
364 | typename W, | |
365 | typename X> | |
366 | struct rebind { | |
367 | typedef d_ary_heap<U, typename d_ary_heap_signature::bind<boost::heap::stable<heap_base_maker::is_stable>, | |
368 | boost::heap::stability_counter_type<typename heap_base_maker::stability_counter_type>, | |
369 | boost::heap::arity<D>, | |
370 | boost::heap::compare<V>, | |
371 | boost::heap::allocator<W> | |
372 | >::type, | |
373 | X | |
374 | > other; | |
375 | }; | |
376 | ||
377 | template <class U> friend class priority_queue_mutable_wrapper; | |
378 | ||
379 | void update(size_type index) | |
380 | { | |
381 | if (index == 0) { | |
382 | siftdown(index); | |
383 | return; | |
384 | } | |
385 | size_type parent = parent_index(index); | |
386 | ||
387 | if (super_t::operator()(q_[parent], q_[index])) | |
388 | siftup(index); | |
389 | else | |
390 | siftdown(index); | |
391 | } | |
392 | ||
393 | void erase(size_type index) | |
394 | { | |
395 | while (index != 0) | |
396 | { | |
397 | size_type parent = parent_index(index); | |
398 | ||
399 | reset_index(index, parent); | |
400 | reset_index(parent, index); | |
401 | std::swap(q_[parent], q_[index]); | |
402 | index = parent; | |
403 | } | |
404 | pop(); | |
405 | } | |
406 | ||
407 | void increase(size_type index) | |
408 | { | |
409 | siftup(index); | |
410 | } | |
411 | ||
412 | void decrease(size_type index) | |
413 | { | |
414 | siftdown(index); | |
415 | } | |
416 | }; | |
417 | ||
418 | ||
419 | template <typename T, typename BoundArgs> | |
420 | struct select_dary_heap | |
421 | { | |
422 | static const bool is_mutable = extract_mutable<BoundArgs>::value; | |
423 | ||
424 | typedef typename mpl::if_c< is_mutable, | |
425 | priority_queue_mutable_wrapper<d_ary_heap<T, BoundArgs, nop_index_updater > >, | |
426 | d_ary_heap<T, BoundArgs, nop_index_updater > | |
427 | >::type type; | |
428 | }; | |
429 | ||
430 | } /* namespace detail */ | |
431 | ||
432 | ||
433 | ||
434 | /** | |
435 | * \class d_ary_heap | |
436 | * \brief d-ary heap class | |
437 | * | |
438 | * This class implements an immutable priority queue. Internally, the d-ary heap is represented | |
439 | * as dynamically sized array (std::vector), that directly stores the values. | |
440 | * | |
441 | * The template parameter T is the type to be managed by the container. | |
442 | * The user can specify additional options and if no options are provided default options are used. | |
443 | * | |
444 | * The container supports the following options: | |
445 | * - \c boost::heap::arity<>, required | |
446 | * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> > | |
447 | * - \c boost::heap::stable<>, defaults to \c stable<false> | |
448 | * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t> | |
449 | * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> > | |
450 | * - \c boost::heap::mutable_<>, defaults to \c mutable_<false> | |
451 | * | |
452 | */ | |
453 | #ifdef BOOST_DOXYGEN_INVOKED | |
454 | template<class T, class ...Options> | |
455 | #else | |
456 | template <typename T, | |
457 | class A0 = boost::parameter::void_, | |
458 | class A1 = boost::parameter::void_, | |
459 | class A2 = boost::parameter::void_, | |
460 | class A3 = boost::parameter::void_, | |
461 | class A4 = boost::parameter::void_, | |
462 | class A5 = boost::parameter::void_ | |
463 | > | |
464 | #endif | |
465 | class d_ary_heap: | |
466 | public detail::select_dary_heap<T, typename detail::d_ary_heap_signature::bind<A0, A1, A2, A3, A4, A5>::type>::type | |
467 | { | |
468 | typedef typename detail::d_ary_heap_signature::bind<A0, A1, A2, A3, A4, A5>::type bound_args; | |
469 | typedef typename detail::select_dary_heap<T, bound_args>::type super_t; | |
470 | ||
471 | template <typename Heap1, typename Heap2> | |
472 | friend struct heap_merge_emulate; | |
473 | ||
474 | #ifndef BOOST_DOXYGEN_INVOKED | |
475 | static const bool is_mutable = detail::extract_mutable<bound_args>::value; | |
476 | ||
477 | #define BOOST_HEAP_TYPEDEF_FROM_SUPER_T(NAME) \ | |
478 | typedef typename super_t::NAME NAME; | |
479 | ||
480 | struct implementation_defined | |
481 | { | |
482 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(size_type) | |
483 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(difference_type) | |
484 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(value_compare) | |
485 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(allocator_type) | |
486 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(reference) | |
487 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_reference) | |
488 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(pointer) | |
489 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_pointer) | |
490 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(iterator) | |
491 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_iterator) | |
492 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(ordered_iterator) | |
493 | BOOST_HEAP_TYPEDEF_FROM_SUPER_T(handle_type) | |
494 | }; | |
495 | #undef BOOST_HEAP_TYPEDEF_FROM_SUPER_T | |
496 | ||
497 | #endif | |
498 | public: | |
499 | static const bool constant_time_size = true; | |
500 | static const bool has_ordered_iterators = true; | |
501 | static const bool is_mergable = false; | |
502 | static const bool has_reserve = true; | |
503 | static const bool is_stable = super_t::is_stable; | |
504 | ||
505 | typedef T value_type; | |
506 | typedef typename implementation_defined::size_type size_type; | |
507 | typedef typename implementation_defined::difference_type difference_type; | |
508 | typedef typename implementation_defined::value_compare value_compare; | |
509 | typedef typename implementation_defined::allocator_type allocator_type; | |
510 | typedef typename implementation_defined::reference reference; | |
511 | typedef typename implementation_defined::const_reference const_reference; | |
512 | typedef typename implementation_defined::pointer pointer; | |
513 | typedef typename implementation_defined::const_pointer const_pointer; | |
514 | /// \copydoc boost::heap::priority_queue::iterator | |
515 | typedef typename implementation_defined::iterator iterator; | |
516 | typedef typename implementation_defined::const_iterator const_iterator; | |
517 | typedef typename implementation_defined::ordered_iterator ordered_iterator; | |
518 | typedef typename implementation_defined::handle_type handle_type; | |
519 | ||
520 | /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &) | |
521 | explicit d_ary_heap(value_compare const & cmp = value_compare()): | |
522 | super_t(cmp) | |
523 | {} | |
524 | ||
525 | /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &) | |
526 | d_ary_heap(d_ary_heap const & rhs): | |
527 | super_t(rhs) | |
528 | {} | |
529 | ||
530 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
531 | /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&) | |
532 | d_ary_heap(d_ary_heap && rhs): | |
533 | super_t(std::move(rhs)) | |
534 | {} | |
535 | ||
536 | /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&) | |
537 | d_ary_heap & operator=(d_ary_heap && rhs) | |
538 | { | |
539 | super_t::operator=(std::move(rhs)); | |
540 | return *this; | |
541 | } | |
542 | #endif | |
543 | ||
544 | /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &) | |
545 | d_ary_heap & operator=(d_ary_heap const & rhs) | |
546 | { | |
547 | super_t::operator=(rhs); | |
548 | return *this; | |
549 | } | |
550 | ||
551 | /// \copydoc boost::heap::priority_queue::empty | |
552 | bool empty(void) const | |
553 | { | |
554 | return super_t::empty(); | |
555 | } | |
556 | ||
557 | /// \copydoc boost::heap::priority_queue::size | |
558 | size_type size(void) const | |
559 | { | |
560 | return super_t::size(); | |
561 | } | |
562 | ||
563 | /// \copydoc boost::heap::priority_queue::max_size | |
564 | size_type max_size(void) const | |
565 | { | |
566 | return super_t::max_size(); | |
567 | } | |
568 | ||
569 | /// \copydoc boost::heap::priority_queue::clear | |
570 | void clear(void) | |
571 | { | |
572 | super_t::clear(); | |
573 | } | |
574 | ||
575 | /// \copydoc boost::heap::priority_queue::get_allocator | |
576 | allocator_type get_allocator(void) const | |
577 | { | |
578 | return super_t::get_allocator(); | |
579 | } | |
580 | ||
581 | /// \copydoc boost::heap::priority_queue::top | |
582 | value_type const & top(void) const | |
583 | { | |
584 | return super_t::top(); | |
585 | } | |
586 | ||
587 | /// \copydoc boost::heap::priority_queue::push | |
588 | typename mpl::if_c<is_mutable, handle_type, void>::type push(value_type const & v) | |
589 | { | |
590 | return super_t::push(v); | |
591 | } | |
592 | ||
593 | #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
594 | /// \copydoc boost::heap::priority_queue::emplace | |
595 | template <class... Args> | |
596 | typename mpl::if_c<is_mutable, handle_type, void>::type emplace(Args&&... args) | |
597 | { | |
598 | return super_t::emplace(std::forward<Args>(args)...); | |
599 | } | |
600 | #endif | |
601 | ||
602 | /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const | |
603 | template <typename HeapType> | |
604 | bool operator<(HeapType const & rhs) const | |
605 | { | |
606 | return detail::heap_compare(*this, rhs); | |
607 | } | |
608 | ||
609 | /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const | |
610 | template <typename HeapType> | |
611 | bool operator>(HeapType const & rhs) const | |
612 | { | |
613 | return detail::heap_compare(rhs, *this); | |
614 | } | |
615 | ||
616 | /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const | |
617 | template <typename HeapType> | |
618 | bool operator>=(HeapType const & rhs) const | |
619 | { | |
620 | return !operator<(rhs); | |
621 | } | |
622 | ||
623 | /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const | |
624 | template <typename HeapType> | |
625 | bool operator<=(HeapType const & rhs) const | |
626 | { | |
627 | return !operator>(rhs); | |
628 | } | |
629 | ||
630 | /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const | |
631 | template <typename HeapType> | |
632 | bool operator==(HeapType const & rhs) const | |
633 | { | |
634 | return detail::heap_equality(*this, rhs); | |
635 | } | |
636 | ||
637 | /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const | |
638 | template <typename HeapType> | |
639 | bool operator!=(HeapType const & rhs) const | |
640 | { | |
641 | return !(*this == rhs); | |
642 | } | |
643 | ||
644 | /** | |
645 | * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. | |
646 | * | |
647 | * \b Complexity: Logarithmic. | |
648 | * | |
649 | * \b Requirement: data structure must be configured as mutable | |
650 | * */ | |
651 | void update(handle_type handle, const_reference v) | |
652 | { | |
653 | BOOST_STATIC_ASSERT(is_mutable); | |
654 | super_t::update(handle, v); | |
655 | } | |
656 | ||
657 | /** | |
658 | * \b Effects: Updates the heap after the element handled by \c handle has been changed. | |
659 | * | |
660 | * \b Complexity: Logarithmic. | |
661 | * | |
662 | * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! | |
663 | * | |
664 | * \b Requirement: data structure must be configured as mutable | |
665 | * */ | |
666 | void update(handle_type handle) | |
667 | { | |
668 | BOOST_STATIC_ASSERT(is_mutable); | |
669 | super_t::update(handle); | |
670 | } | |
671 | ||
672 | /** | |
673 | * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. | |
674 | * | |
675 | * \b Complexity: Logarithmic. | |
676 | * | |
677 | * \b Note: The new value is expected to be greater than the current one | |
678 | * | |
679 | * \b Requirement: data structure must be configured as mutable | |
680 | * */ | |
681 | void increase(handle_type handle, const_reference v) | |
682 | { | |
683 | BOOST_STATIC_ASSERT(is_mutable); | |
684 | super_t::increase(handle, v); | |
685 | } | |
686 | ||
687 | /** | |
688 | * \b Effects: Updates the heap after the element handled by \c handle has been changed. | |
689 | * | |
690 | * \b Complexity: Logarithmic. | |
691 | * | |
692 | * \b Note: The new value is expected to be greater than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined! | |
693 | * | |
694 | * \b Requirement: data structure must be configured as mutable | |
695 | * */ | |
696 | void increase(handle_type handle) | |
697 | { | |
698 | BOOST_STATIC_ASSERT(is_mutable); | |
699 | super_t::increase(handle); | |
700 | } | |
701 | ||
702 | /** | |
703 | * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. | |
704 | * | |
705 | * \b Complexity: Logarithmic. | |
706 | * | |
707 | * \b Note: The new value is expected to be less than the current one | |
708 | * | |
709 | * \b Requirement: data structure must be configured as mutable | |
710 | * */ | |
711 | void decrease(handle_type handle, const_reference v) | |
712 | { | |
713 | BOOST_STATIC_ASSERT(is_mutable); | |
714 | super_t::decrease(handle, v); | |
715 | } | |
716 | ||
717 | /** | |
718 | * \b Effects: Updates the heap after the element handled by \c handle has been changed. | |
719 | * | |
720 | * \b Complexity: Logarithmic. | |
721 | * | |
722 | * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined! | |
723 | * | |
724 | * \b Requirement: data structure must be configured as mutable | |
725 | * */ | |
726 | void decrease(handle_type handle) | |
727 | { | |
728 | BOOST_STATIC_ASSERT(is_mutable); | |
729 | super_t::decrease(handle); | |
730 | } | |
731 | ||
732 | /** | |
733 | * \b Effects: Removes the element handled by \c handle from the priority_queue. | |
734 | * | |
735 | * \b Complexity: Logarithmic. | |
736 | * | |
737 | * \b Requirement: data structure must be configured as mutable | |
738 | * */ | |
739 | void erase(handle_type handle) | |
740 | { | |
741 | BOOST_STATIC_ASSERT(is_mutable); | |
742 | super_t::erase(handle); | |
743 | } | |
744 | ||
745 | /** | |
746 | * \b Effects: Casts an iterator to a node handle. | |
747 | * | |
748 | * \b Complexity: Constant. | |
749 | * | |
750 | * \b Requirement: data structure must be configured as mutable | |
751 | * */ | |
752 | static handle_type s_handle_from_iterator(iterator const & it) | |
753 | { | |
754 | BOOST_STATIC_ASSERT(is_mutable); | |
755 | return super_t::s_handle_from_iterator(it); | |
756 | } | |
757 | ||
758 | /// \copydoc boost::heap::priority_queue::pop | |
759 | void pop(void) | |
760 | { | |
761 | super_t::pop(); | |
762 | } | |
763 | ||
764 | /// \copydoc boost::heap::priority_queue::swap | |
765 | void swap(d_ary_heap & rhs) | |
766 | { | |
767 | super_t::swap(rhs); | |
768 | } | |
769 | ||
770 | /// \copydoc boost::heap::priority_queue::begin | |
771 | const_iterator begin(void) const | |
772 | { | |
773 | return super_t::begin(); | |
774 | } | |
775 | ||
776 | /// \copydoc boost::heap::priority_queue::begin | |
777 | iterator begin(void) | |
778 | { | |
779 | return super_t::begin(); | |
780 | } | |
781 | ||
782 | /// \copydoc boost::heap::priority_queue::end | |
783 | iterator end(void) | |
784 | { | |
785 | return super_t::end(); | |
786 | } | |
787 | ||
788 | /// \copydoc boost::heap::priority_queue::end | |
789 | const_iterator end(void) const | |
790 | { | |
791 | return super_t::end(); | |
792 | } | |
793 | ||
794 | /// \copydoc boost::heap::fibonacci_heap::ordered_begin | |
795 | ordered_iterator ordered_begin(void) const | |
796 | { | |
797 | return super_t::ordered_begin(); | |
798 | } | |
799 | ||
800 | /// \copydoc boost::heap::fibonacci_heap::ordered_end | |
801 | ordered_iterator ordered_end(void) const | |
802 | { | |
803 | return super_t::ordered_end(); | |
804 | } | |
805 | ||
806 | /// \copydoc boost::heap::priority_queue::reserve | |
807 | void reserve (size_type element_count) | |
808 | { | |
809 | super_t::reserve(element_count); | |
810 | } | |
811 | ||
812 | /// \copydoc boost::heap::priority_queue::value_comp | |
813 | value_compare const & value_comp(void) const | |
814 | { | |
815 | return super_t::value_comp(); | |
816 | } | |
817 | }; | |
818 | ||
819 | } /* namespace heap */ | |
820 | } /* namespace boost */ | |
821 | ||
822 | #undef BOOST_HEAP_ASSERT | |
823 | ||
824 | #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */ |