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