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
24namespace boost {
25namespace heap {
26namespace detail {
27
28template <typename Heap1, typename Heap2>
29struct heap_merge_emulate
30{
31 struct dummy_reserver
32 {
33 static void reserve (Heap1 & lhs, std::size_t required_size)
34 {}
35 };
36
37 struct reserver
38 {
39 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
49 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
75template <typename Heap>
76struct heap_merge_same_mergable
77{
78 static void merge(Heap & lhs, Heap & rhs)
79 {
80 lhs.merge(rhs);
81 }
82};
83
84
85template <typename Heap>
86struct 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
94 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 * */
108template <typename Heap1,
109 typename Heap2
110 >
111void 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

source code of boost/libs/heap/include/boost/heap/heap_merge.hpp