]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // boost heap: heap merge algorithms |
2 | // | |
3 | // Copyright (C) 2011 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_MERGE_HPP | |
10 | #define BOOST_HEAP_MERGE_HPP | |
11 | ||
12 | #include <boost/concept/assert.hpp> | |
13 | #include <boost/heap/heap_concepts.hpp> | |
14 | #include <boost/type_traits/is_same.hpp> | |
15 | ||
16 | #ifdef BOOST_HAS_PRAGMA_ONCE | |
17 | #pragma once | |
18 | #endif | |
19 | ||
20 | ||
21 | namespace boost { | |
22 | namespace heap { | |
23 | namespace detail { | |
24 | ||
25 | template <typename Heap1, typename Heap2> | |
26 | struct heap_merge_emulate | |
27 | { | |
28 | struct dummy_reserver | |
29 | { | |
30 | static void reserve (Heap1 & lhs, std::size_t required_size) | |
31 | {} | |
32 | }; | |
33 | ||
34 | struct reserver | |
35 | { | |
36 | static void reserve (Heap1 & lhs, std::size_t required_size) | |
37 | { | |
38 | lhs.reserve(required_size); | |
39 | } | |
40 | }; | |
41 | ||
42 | typedef typename boost::mpl::if_c<Heap1::has_reserve, | |
43 | reserver, | |
44 | dummy_reserver>::type space_reserver; | |
45 | ||
46 | static void merge(Heap1 & lhs, Heap2 & rhs) | |
47 | { | |
48 | if (Heap1::constant_time_size && Heap2::constant_time_size) { | |
49 | if (Heap1::has_reserve) { | |
50 | std::size_t required_size = lhs.size() + rhs.size(); | |
51 | space_reserver::reserve(lhs, required_size); | |
52 | } | |
53 | } | |
54 | ||
55 | // FIXME: container adaptors could benefit from first appending all elements and then restoring the heap order | |
56 | // FIXME: optimize: if we have ordered iterators and we can efficiently insert keys with a below the lowest key in the heap | |
57 | // d-ary, b and fibonacci heaps fall into this category | |
58 | ||
59 | while (!rhs.empty()) { | |
60 | lhs.push(rhs.top()); | |
61 | rhs.pop(); | |
62 | } | |
63 | ||
64 | lhs.set_stability_count((std::max)(lhs.get_stability_count(), | |
65 | rhs.get_stability_count())); | |
66 | rhs.set_stability_count(0); | |
67 | } | |
68 | ||
69 | }; | |
70 | ||
71 | ||
72 | template <typename Heap> | |
73 | struct heap_merge_same_mergable | |
74 | { | |
75 | static void merge(Heap & lhs, Heap & rhs) | |
76 | { | |
77 | lhs.merge(rhs); | |
78 | } | |
79 | }; | |
80 | ||
81 | ||
82 | template <typename Heap> | |
83 | struct heap_merge_same | |
84 | { | |
85 | static const bool is_mergable = Heap::is_mergable; | |
86 | typedef typename boost::mpl::if_c<is_mergable, | |
87 | heap_merge_same_mergable<Heap>, | |
88 | heap_merge_emulate<Heap, Heap> | |
89 | >::type heap_merger; | |
90 | ||
91 | static void merge(Heap & lhs, Heap & rhs) | |
92 | { | |
93 | heap_merger::merge(lhs, rhs); | |
94 | } | |
95 | }; | |
96 | ||
97 | } /* namespace detail */ | |
98 | ||
99 | ||
100 | /** merge rhs into lhs | |
101 | * | |
102 | * \b Effect: lhs contains all elements that have been part of rhs, rhs is empty. | |
103 | * | |
104 | * */ | |
105 | template <typename Heap1, | |
106 | typename Heap2 | |
107 | > | |
108 | void heap_merge(Heap1 & lhs, Heap2 & rhs) | |
109 | { | |
110 | BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>)); | |
111 | BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>)); | |
112 | ||
113 | // if this assertion is triggered, the value_compare types are incompatible | |
114 | BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value)); | |
115 | ||
116 | const bool same_heaps = boost::is_same<Heap1, Heap2>::value; | |
117 | ||
118 | typedef typename boost::mpl::if_c<same_heaps, | |
119 | detail::heap_merge_same<Heap1>, | |
120 | detail::heap_merge_emulate<Heap1, Heap2> | |
121 | >::type heap_merger; | |
122 | ||
123 | heap_merger::merge(lhs, rhs); | |
124 | } | |
125 | ||
126 | ||
127 | } /* namespace heap */ | |
128 | } /* namespace boost */ | |
129 | ||
130 | #endif /* BOOST_HEAP_MERGE_HPP */ |