1 // boost heap: heap merge algorithms
3 // Copyright (C) 2011 Tim Blechmann
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)
9 #ifndef BOOST_HEAP_MERGE_HPP
10 #define BOOST_HEAP_MERGE_HPP
12 #include <boost/concept/assert.hpp>
13 #include <boost/heap/heap_concepts.hpp>
14 #include <boost/type_traits/is_same.hpp>
16 #ifdef BOOST_HAS_PRAGMA_ONCE
25 template <typename Heap1, typename Heap2>
26 struct heap_merge_emulate
30 static void reserve (Heap1 & lhs, std::size_t required_size)
36 static void reserve (Heap1 & lhs, std::size_t required_size)
38 lhs.reserve(required_size);
42 typedef typename boost::mpl::if_c<Heap1::has_reserve,
44 dummy_reserver>::type space_reserver;
46 static void merge(Heap1 & lhs, Heap2 & rhs)
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);
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
59 while (!rhs.empty()) {
64 lhs.set_stability_count((std::max)(lhs.get_stability_count(),
65 rhs.get_stability_count()));
66 rhs.set_stability_count(0);
72 template <typename Heap>
73 struct heap_merge_same_mergable
75 static void merge(Heap & lhs, Heap & rhs)
82 template <typename Heap>
83 struct heap_merge_same
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>
91 static void merge(Heap & lhs, Heap & rhs)
93 heap_merger::merge(lhs, rhs);
97 } /* namespace detail */
100 /** merge rhs into lhs
102 * \b Effect: lhs contains all elements that have been part of rhs, rhs is empty.
105 template <typename Heap1,
108 void heap_merge(Heap1 & lhs, Heap2 & rhs)
110 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
111 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
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));
116 const bool same_heaps = boost::is_same<Heap1, Heap2>::value;
118 typedef typename boost::mpl::if_c<same_heaps,
119 detail::heap_merge_same<Heap1>,
120 detail::heap_merge_emulate<Heap1, Heap2>
123 heap_merger::merge(lhs, rhs);
127 } /* namespace heap */
128 } /* namespace boost */
130 #endif /* BOOST_HEAP_MERGE_HPP */