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