]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // boost heap: helper classes for stable priority queues |
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_DETAIL_STABLE_HEAP_HPP | |
10 | #define BOOST_HEAP_DETAIL_STABLE_HEAP_HPP | |
11 | ||
12 | #include <limits> | |
13 | #include <stdexcept> | |
14 | #include <utility> | |
15 | ||
16 | #include <boost/cstdint.hpp> | |
17 | #include <boost/throw_exception.hpp> | |
18 | #include <boost/iterator/iterator_adaptor.hpp> | |
19 | ||
20 | #include <boost/heap/policies.hpp> | |
21 | #include <boost/heap/heap_merge.hpp> | |
22 | ||
23 | #include <boost/type_traits/is_nothrow_move_constructible.hpp> | |
24 | #include <boost/type_traits/is_nothrow_move_assignable.hpp> | |
25 | ||
26 | namespace boost { | |
27 | namespace heap { | |
28 | namespace detail { | |
29 | ||
30 | template<bool ConstantSize, class SizeType> | |
31 | struct size_holder | |
32 | { | |
33 | static const bool constant_time_size = ConstantSize; | |
34 | typedef SizeType size_type; | |
35 | ||
36 | size_holder(void) BOOST_NOEXCEPT: | |
37 | size_(0) | |
38 | {} | |
39 | ||
40 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
41 | size_holder(size_holder && rhs) BOOST_NOEXCEPT: | |
42 | size_(rhs.size_) | |
43 | { | |
44 | rhs.size_ = 0; | |
45 | } | |
46 | ||
47 | size_holder(size_holder const & rhs) BOOST_NOEXCEPT: | |
48 | size_(rhs.size_) | |
49 | {} | |
50 | ||
51 | size_holder & operator=(size_holder && rhs) BOOST_NOEXCEPT | |
52 | { | |
53 | size_ = rhs.size_; | |
54 | rhs.size_ = 0; | |
55 | return *this; | |
56 | } | |
57 | ||
58 | size_holder & operator=(size_holder const & rhs) BOOST_NOEXCEPT | |
59 | { | |
60 | size_ = rhs.size_; | |
61 | return *this; | |
62 | } | |
63 | #endif | |
64 | ||
65 | SizeType get_size() const BOOST_NOEXCEPT | |
66 | { return size_; } | |
67 | ||
68 | void set_size(SizeType size) BOOST_NOEXCEPT | |
69 | { size_ = size; } | |
70 | ||
71 | void decrement() BOOST_NOEXCEPT | |
72 | { --size_; } | |
73 | ||
74 | void increment() BOOST_NOEXCEPT | |
75 | { ++size_; } | |
76 | ||
77 | void add(SizeType value) BOOST_NOEXCEPT | |
78 | { size_ += value; } | |
79 | ||
80 | void sub(SizeType value) BOOST_NOEXCEPT | |
81 | { size_ -= value; } | |
82 | ||
83 | void swap(size_holder & rhs) BOOST_NOEXCEPT | |
84 | { std::swap(size_, rhs.size_); } | |
85 | ||
86 | SizeType size_; | |
87 | }; | |
88 | ||
89 | template<class SizeType> | |
90 | struct size_holder<false, SizeType> | |
91 | { | |
92 | static const bool constant_time_size = false; | |
93 | typedef SizeType size_type; | |
94 | ||
95 | size_holder(void) BOOST_NOEXCEPT | |
96 | {} | |
97 | ||
98 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
99 | size_holder(size_holder && rhs) BOOST_NOEXCEPT | |
100 | {} | |
101 | ||
102 | size_holder(size_holder const & rhs) BOOST_NOEXCEPT | |
103 | {} | |
104 | ||
105 | size_holder & operator=(size_holder && rhs) BOOST_NOEXCEPT | |
106 | { | |
107 | return *this; | |
108 | } | |
109 | ||
110 | size_holder & operator=(size_holder const & rhs) BOOST_NOEXCEPT | |
111 | { | |
112 | return *this; | |
113 | } | |
114 | #endif | |
115 | ||
116 | size_type get_size() const BOOST_NOEXCEPT | |
117 | { return 0; } | |
118 | ||
119 | void set_size(size_type) BOOST_NOEXCEPT | |
120 | {} | |
121 | ||
122 | void decrement() BOOST_NOEXCEPT | |
123 | {} | |
124 | ||
125 | void increment() BOOST_NOEXCEPT | |
126 | {} | |
127 | ||
128 | void add(SizeType /*value*/) BOOST_NOEXCEPT | |
129 | {} | |
130 | ||
131 | void sub(SizeType /*value*/) BOOST_NOEXCEPT | |
132 | {} | |
133 | ||
134 | void swap(size_holder & /*rhs*/) BOOST_NOEXCEPT | |
135 | {} | |
136 | }; | |
137 | ||
138 | // note: MSVC does not implement lookup correctly, we therefore have to place the Cmp object as member inside the | |
139 | // struct. of course, this prevents EBO and significantly reduces the readability of this code | |
140 | template <typename T, | |
141 | typename Cmp, | |
142 | bool constant_time_size, | |
143 | typename StabilityCounterType = boost::uintmax_t, | |
144 | bool stable = false | |
145 | > | |
146 | struct heap_base: | |
147 | #ifndef BOOST_MSVC | |
148 | Cmp, | |
149 | #endif | |
150 | size_holder<constant_time_size, size_t> | |
151 | { | |
152 | typedef StabilityCounterType stability_counter_type; | |
153 | typedef T value_type; | |
154 | typedef T internal_type; | |
155 | typedef size_holder<constant_time_size, size_t> size_holder_type; | |
156 | typedef Cmp value_compare; | |
157 | typedef Cmp internal_compare; | |
158 | static const bool is_stable = stable; | |
159 | ||
160 | #ifdef BOOST_MSVC | |
161 | Cmp cmp_; | |
162 | #endif | |
163 | ||
164 | heap_base (Cmp const & cmp = Cmp()): | |
165 | #ifndef BOOST_MSVC | |
166 | Cmp(cmp) | |
167 | #else | |
168 | cmp_(cmp) | |
169 | #endif | |
170 | {} | |
171 | ||
172 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
173 | heap_base(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value): | |
174 | #ifndef BOOST_MSVC | |
175 | Cmp(std::move(static_cast<Cmp&>(rhs))), | |
176 | #else | |
177 | cmp_(std::move(rhs.cmp_)), | |
178 | #endif | |
179 | size_holder_type(std::move(static_cast<size_holder_type&>(rhs))) | |
180 | {} | |
181 | ||
182 | heap_base(heap_base const & rhs): | |
183 | #ifndef BOOST_MSVC | |
184 | Cmp(static_cast<Cmp const &>(rhs)), | |
185 | #else | |
186 | cmp_(rhs.value_comp()), | |
187 | #endif | |
188 | size_holder_type(static_cast<size_holder_type const &>(rhs)) | |
189 | {} | |
190 | ||
191 | heap_base & operator=(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_assignable<Cmp>::value) | |
192 | { | |
193 | value_comp_ref().operator=(std::move(rhs.value_comp_ref())); | |
194 | size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs))); | |
195 | return *this; | |
196 | } | |
197 | ||
198 | heap_base & operator=(heap_base const & rhs) | |
199 | { | |
200 | value_comp_ref().operator=(rhs.value_comp()); | |
201 | size_holder_type::operator=(static_cast<size_holder_type const &>(rhs)); | |
202 | return *this; | |
203 | } | |
204 | #endif | |
205 | ||
206 | bool operator()(internal_type const & lhs, internal_type const & rhs) const | |
207 | { | |
208 | return value_comp().operator()(lhs, rhs); | |
209 | } | |
210 | ||
211 | internal_type make_node(T const & val) | |
212 | { | |
213 | return val; | |
214 | } | |
215 | ||
216 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
217 | T && make_node(T && val) | |
218 | { | |
219 | return std::forward<T>(val); | |
220 | } | |
221 | #endif | |
222 | ||
223 | #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
224 | template <class... Args> | |
225 | internal_type make_node(Args && ... val) | |
226 | { | |
227 | return internal_type(std::forward<Args>(val)...); | |
228 | } | |
229 | #endif | |
230 | ||
231 | static T & get_value(internal_type & val) BOOST_NOEXCEPT | |
232 | { | |
233 | return val; | |
234 | } | |
235 | ||
236 | static T const & get_value(internal_type const & val) BOOST_NOEXCEPT | |
237 | { | |
238 | return val; | |
239 | } | |
240 | ||
241 | Cmp const & value_comp(void) const BOOST_NOEXCEPT | |
242 | { | |
243 | #ifndef BOOST_MSVC | |
244 | return *this; | |
245 | #else | |
246 | return cmp_; | |
247 | #endif | |
248 | } | |
249 | ||
250 | Cmp const & get_internal_cmp(void) const BOOST_NOEXCEPT | |
251 | { | |
252 | return value_comp(); | |
253 | } | |
254 | ||
255 | void swap(heap_base & rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value && boost::is_nothrow_move_assignable<Cmp>::value) | |
256 | { | |
257 | std::swap(value_comp_ref(), rhs.value_comp_ref()); | |
258 | size_holder<constant_time_size, size_t>::swap(rhs); | |
259 | } | |
260 | ||
261 | stability_counter_type get_stability_count(void) const BOOST_NOEXCEPT | |
262 | { | |
263 | return 0; | |
264 | } | |
265 | ||
266 | void set_stability_count(stability_counter_type) BOOST_NOEXCEPT | |
267 | {} | |
268 | ||
269 | template <typename Heap1, typename Heap2> | |
270 | friend struct heap_merge_emulate; | |
271 | ||
272 | private: | |
273 | Cmp & value_comp_ref(void) | |
274 | { | |
275 | #ifndef BOOST_MSVC | |
276 | return *this; | |
277 | #else | |
278 | return cmp_; | |
279 | #endif | |
280 | } | |
281 | }; | |
282 | ||
283 | ||
284 | template <typename T, | |
285 | typename Cmp, | |
286 | bool constant_time_size, | |
287 | typename StabilityCounterType | |
288 | > | |
289 | struct heap_base<T, Cmp, constant_time_size, StabilityCounterType, true>: | |
290 | #ifndef BOOST_MSVC | |
291 | Cmp, | |
292 | #endif | |
293 | size_holder<constant_time_size, size_t> | |
294 | { | |
295 | typedef StabilityCounterType stability_counter_type; | |
296 | typedef T value_type; | |
297 | ||
298 | struct internal_type | |
299 | { | |
300 | #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
301 | template <class ...Args> | |
302 | internal_type(stability_counter_type cnt, Args && ... args): | |
303 | first(std::forward<Args>(args)...), second(cnt) | |
304 | {} | |
305 | #endif | |
306 | ||
307 | internal_type(stability_counter_type const & cnt, T const & value): | |
308 | first(value), second(cnt) | |
309 | {} | |
310 | ||
311 | T first; | |
312 | stability_counter_type second; | |
313 | }; | |
314 | ||
315 | typedef size_holder<constant_time_size, size_t> size_holder_type; | |
316 | typedef Cmp value_compare; | |
317 | ||
318 | #ifdef BOOST_MSVC | |
319 | Cmp cmp_; | |
320 | #endif | |
321 | ||
322 | heap_base (Cmp const & cmp = Cmp()): | |
323 | #ifndef BOOST_MSVC | |
324 | Cmp(cmp), | |
325 | #else | |
326 | cmp_(cmp), | |
327 | #endif | |
328 | counter_(0) | |
329 | {} | |
330 | ||
331 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
332 | heap_base(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value): | |
333 | #ifndef BOOST_MSVC | |
334 | Cmp(std::move(static_cast<Cmp&>(rhs))), | |
335 | #else | |
336 | cmp_(std::move(rhs.cmp_)), | |
337 | #endif | |
338 | size_holder_type(std::move(static_cast<size_holder_type&>(rhs))), counter_(rhs.counter_) | |
339 | { | |
340 | rhs.counter_ = 0; | |
341 | } | |
342 | ||
343 | heap_base(heap_base const & rhs): | |
344 | #ifndef BOOST_MSVC | |
345 | Cmp(static_cast<Cmp const&>(rhs)), | |
346 | #else | |
347 | cmp_(rhs.value_comp()), | |
348 | #endif | |
349 | size_holder_type(static_cast<size_holder_type const &>(rhs)), counter_(rhs.counter_) | |
350 | {} | |
351 | ||
352 | heap_base & operator=(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_assignable<Cmp>::value) | |
353 | { | |
354 | value_comp_ref().operator=(std::move(rhs.value_comp_ref())); | |
355 | size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs))); | |
356 | ||
357 | counter_ = rhs.counter_; | |
358 | rhs.counter_ = 0; | |
359 | return *this; | |
360 | } | |
361 | ||
362 | heap_base & operator=(heap_base const & rhs) | |
363 | { | |
364 | value_comp_ref().operator=(rhs.value_comp()); | |
365 | size_holder_type::operator=(static_cast<size_holder_type const &>(rhs)); | |
366 | ||
367 | counter_ = rhs.counter_; | |
368 | return *this; | |
369 | } | |
370 | #endif | |
371 | ||
372 | bool operator()(internal_type const & lhs, internal_type const & rhs) const | |
373 | { | |
374 | return get_internal_cmp()(lhs, rhs); | |
375 | } | |
376 | ||
377 | bool operator()(T const & lhs, T const & rhs) const | |
378 | { | |
379 | return value_comp()(lhs, rhs); | |
380 | } | |
381 | ||
382 | internal_type make_node(T const & val) | |
383 | { | |
384 | stability_counter_type count = ++counter_; | |
385 | if (counter_ == (std::numeric_limits<stability_counter_type>::max)()) | |
386 | BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow")); | |
387 | return internal_type(count, val); | |
388 | } | |
389 | ||
390 | #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
391 | template <class... Args> | |
392 | internal_type make_node(Args&&... args) | |
393 | { | |
394 | stability_counter_type count = ++counter_; | |
395 | if (counter_ == (std::numeric_limits<stability_counter_type>::max)()) | |
396 | BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow")); | |
397 | return internal_type (count, std::forward<Args>(args)...); | |
398 | } | |
399 | #endif | |
400 | ||
401 | static T & get_value(internal_type & val) BOOST_NOEXCEPT | |
402 | { | |
403 | return val.first; | |
404 | } | |
405 | ||
406 | static T const & get_value(internal_type const & val) BOOST_NOEXCEPT | |
407 | { | |
408 | return val.first; | |
409 | } | |
410 | ||
411 | Cmp const & value_comp(void) const BOOST_NOEXCEPT | |
412 | { | |
413 | #ifndef BOOST_MSVC | |
414 | return *this; | |
415 | #else | |
416 | return cmp_; | |
417 | #endif | |
418 | } | |
419 | ||
420 | struct internal_compare: | |
421 | Cmp | |
422 | { | |
423 | internal_compare(Cmp const & cmp = Cmp()): | |
424 | Cmp(cmp) | |
425 | {} | |
426 | ||
427 | bool operator()(internal_type const & lhs, internal_type const & rhs) const | |
428 | { | |
429 | if (Cmp::operator()(lhs.first, rhs.first)) | |
430 | return true; | |
431 | ||
432 | if (Cmp::operator()(rhs.first, lhs.first)) | |
433 | return false; | |
434 | ||
435 | return lhs.second > rhs.second; | |
436 | } | |
437 | }; | |
438 | ||
439 | internal_compare get_internal_cmp(void) const | |
440 | { | |
441 | return internal_compare(value_comp()); | |
442 | } | |
443 | ||
444 | void swap(heap_base & rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value && boost::is_nothrow_move_assignable<Cmp>::value) | |
445 | { | |
446 | #ifndef BOOST_MSVC | |
447 | std::swap(static_cast<Cmp&>(*this), static_cast<Cmp&>(rhs)); | |
448 | #else | |
449 | std::swap(cmp_, rhs.cmp_); | |
450 | #endif | |
451 | std::swap(counter_, rhs.counter_); | |
452 | size_holder<constant_time_size, size_t>::swap(rhs); | |
453 | } | |
454 | ||
455 | stability_counter_type get_stability_count(void) const | |
456 | { | |
457 | return counter_; | |
458 | } | |
459 | ||
460 | void set_stability_count(stability_counter_type new_count) | |
461 | { | |
462 | counter_ = new_count; | |
463 | } | |
464 | ||
465 | template <typename Heap1, typename Heap2> | |
466 | friend struct heap_merge_emulate; | |
467 | ||
468 | private: | |
469 | Cmp & value_comp_ref(void) BOOST_NOEXCEPT | |
470 | { | |
471 | #ifndef BOOST_MSVC | |
472 | return *this; | |
473 | #else | |
474 | return cmp_; | |
475 | #endif | |
476 | } | |
477 | ||
478 | stability_counter_type counter_; | |
479 | }; | |
480 | ||
481 | template <typename node_pointer, | |
482 | typename extractor, | |
483 | typename reference | |
484 | > | |
485 | struct node_handle | |
486 | { | |
487 | explicit node_handle(node_pointer n = 0): | |
488 | node_(n) | |
489 | {} | |
490 | ||
491 | reference operator*() const | |
492 | { | |
493 | return extractor::get_value(node_->value); | |
494 | } | |
495 | ||
496 | bool operator==(node_handle const & rhs) const | |
497 | { | |
498 | return node_ == rhs.node_; | |
499 | } | |
500 | ||
501 | bool operator!=(node_handle const & rhs) const | |
502 | { | |
503 | return node_ != rhs.node_; | |
504 | } | |
505 | ||
506 | node_pointer node_; | |
507 | }; | |
508 | ||
509 | template <typename value_type, | |
510 | typename internal_type, | |
511 | typename extractor | |
512 | > | |
513 | struct value_extractor | |
514 | { | |
515 | value_type const & operator()(internal_type const & data) const | |
516 | { | |
517 | return extractor::get_value(data); | |
518 | } | |
519 | }; | |
520 | ||
521 | template <typename T, | |
522 | typename ContainerIterator, | |
523 | typename Extractor> | |
524 | class stable_heap_iterator: | |
525 | public boost::iterator_adaptor<stable_heap_iterator<T, ContainerIterator, Extractor>, | |
526 | ContainerIterator, | |
527 | T const, | |
528 | boost::random_access_traversal_tag> | |
529 | { | |
530 | typedef boost::iterator_adaptor<stable_heap_iterator, | |
531 | ContainerIterator, | |
532 | T const, | |
533 | boost::random_access_traversal_tag> super_t; | |
534 | ||
535 | public: | |
536 | stable_heap_iterator(void): | |
537 | super_t(0) | |
538 | {} | |
539 | ||
540 | explicit stable_heap_iterator(ContainerIterator const & it): | |
541 | super_t(it) | |
542 | {} | |
543 | ||
544 | private: | |
545 | friend class boost::iterator_core_access; | |
546 | ||
547 | T const & dereference() const | |
548 | { | |
549 | return Extractor::get_value(*super_t::base()); | |
550 | } | |
551 | }; | |
552 | ||
553 | template <typename T, typename Parspec, bool constant_time_size> | |
554 | struct make_heap_base | |
555 | { | |
556 | typedef typename parameter::binding<Parspec, tag::compare, std::less<T> >::type compare_argument; | |
557 | typedef typename parameter::binding<Parspec, tag::allocator, std::allocator<T> >::type allocator_argument; | |
558 | typedef typename parameter::binding<Parspec, tag::stability_counter_type, boost::uintmax_t >::type stability_counter_type; | |
559 | ||
560 | static const bool is_stable = extract_stable<Parspec>::value; | |
561 | ||
562 | typedef heap_base<T, compare_argument, constant_time_size, stability_counter_type, is_stable> type; | |
563 | }; | |
564 | ||
565 | ||
566 | template <typename Alloc> | |
567 | struct extract_allocator_types | |
568 | { | |
569 | typedef typename Alloc::size_type size_type; | |
570 | typedef typename Alloc::difference_type difference_type; | |
571 | typedef typename Alloc::reference reference; | |
572 | typedef typename Alloc::const_reference const_reference; | |
573 | typedef typename Alloc::pointer pointer; | |
574 | typedef typename Alloc::const_pointer const_pointer; | |
575 | }; | |
576 | ||
577 | ||
578 | } /* namespace detail */ | |
579 | } /* namespace heap */ | |
580 | } /* namespace boost */ | |
581 | ||
582 | #endif /* BOOST_HEAP_DETAIL_STABLE_HEAP_HPP */ |