2 //=======================================================================
3 // Copyright 2009 Trustees of Indiana University
4 // Authors: Jeremiah J. Willcock, Andrew Lumsdaine
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
11 #ifndef BOOST_D_ARY_HEAP_HPP
12 #define BOOST_D_ARY_HEAP_HPP
18 #include <boost/assert.hpp>
19 #include <boost/static_assert.hpp>
20 #include <boost/shared_array.hpp>
21 #include <boost/property_map/property_map.hpp>
23 // WARNING: it is not safe to copy a d_ary_heap_indirect and then modify one of
24 // the copies. The class is required to be copyable so it can be passed around
25 // (without move support from C++11), but it deep-copies the heap contents yet
26 // shallow-copies the index_in_heap_map.
30 // Swap two elements in a property map without assuming they model
31 // LvaluePropertyMap -- currently not used
32 template <typename PropMap>
33 inline void property_map_swap(
35 const typename boost::property_traits<PropMap>::key_type& ka,
36 const typename boost::property_traits<PropMap>::key_type& kb) {
37 typename boost::property_traits<PropMap>::value_type va = get(prop_map, ka);
38 put(prop_map, ka, get(prop_map, kb));
39 put(prop_map, kb, va);
43 template <typename Value>
44 class fixed_max_size_vector {
45 boost::shared_array<Value> m_data;
49 typedef std::size_t size_type;
50 fixed_max_size_vector(std::size_t max_size)
51 : m_data(new Value[max_size]), m_size(0) {}
52 std::size_t size() const {return m_size;}
53 bool empty() const {return m_size == 0;}
54 Value& operator[](std::size_t i) {return m_data[i];}
55 const Value& operator[](std::size_t i) const {return m_data[i];}
56 void push_back(Value v) {m_data[m_size++] = v;}
57 void pop_back() {--m_size;}
58 Value& back() {return m_data[m_size - 1];}
59 const Value& back() const {return m_data[m_size - 1];}
63 // D-ary heap using an indirect compare operator (use identity_property_map
64 // as DistanceMap to get a direct compare operator). This heap appears to be
65 // commonly used for Dijkstra's algorithm for its good practical performance
66 // on some platforms; asymptotically, it has an O(lg N) decrease-key
67 // operation while that can be done in constant time on a relaxed heap. The
68 // implementation is mostly based on the binary heap page on Wikipedia and
69 // online sources that state that the operations are the same for d-ary
70 // heaps. This code is not based on the old Boost d-ary heap code.
72 // - d_ary_heap_indirect is a model of UpdatableQueue as is needed for
73 // dijkstra_shortest_paths.
75 // - Value must model Assignable.
76 // - Arity must be at least 2 (optimal value appears to be 4, both in my and
77 // third-party experiments).
78 // - IndexInHeapMap must be a ReadWritePropertyMap from Value to
79 // Container::size_type (to store the index of each stored value within the
80 // heap for decrease-key aka update).
81 // - DistanceMap must be a ReadablePropertyMap from Value to something
82 // (typedef'ed as distance_type).
83 // - Compare must be a BinaryPredicate used as a less-than operator on
85 // - Container must be a random-access, contiguous container (in practice,
86 // the operations used probably require that it is std::vector<Value>).
88 template <typename Value,
90 typename IndexInHeapPropertyMap,
92 typename Compare = std::less<Value>,
93 typename Container = std::vector<Value> >
94 class d_ary_heap_indirect {
95 BOOST_STATIC_ASSERT (Arity >= 2);
98 typedef typename Container::size_type size_type;
99 typedef Value value_type;
100 typedef typename boost::property_traits<DistanceMap>::value_type key_type;
101 typedef DistanceMap key_map;
103 d_ary_heap_indirect(DistanceMap distance,
104 IndexInHeapPropertyMap index_in_heap,
105 const Compare& compare = Compare(),
106 const Container& data = Container())
107 : compare(compare), data(data), distance(distance),
108 index_in_heap(index_in_heap) {}
109 /* Implicit copy constructor */
110 /* Implicit assignment operator */
112 size_type size() const {
120 void push(const Value& v) {
121 size_type index = data.size();
123 put(index_in_heap, v, index);
124 preserve_heap_property_up(index);
129 BOOST_ASSERT (!this->empty());
133 const Value& top() const {
134 BOOST_ASSERT (!this->empty());
139 BOOST_ASSERT (!this->empty());
140 put(index_in_heap, data[0], (size_type)(-1));
141 if (data.size() != 1) {
142 data[0] = data.back();
143 put(index_in_heap, data[0], (size_type)(0));
145 preserve_heap_property_down();
152 // This function assumes the key has been updated (using an external write
153 // to the distance map or such)
154 // See http://coding.derkeiler.com/Archive/General/comp.theory/2007-05/msg00043.html
155 void update(const Value& v) { /* decrease-key */
156 size_type index = get(index_in_heap, v);
157 preserve_heap_property_up(index);
161 bool contains(const Value& v) const {
162 size_type index = get(index_in_heap, v);
163 return (index != (size_type)(-1));
166 void push_or_update(const Value& v) { /* insert if not present, else update */
167 size_type index = get(index_in_heap, v);
168 if (index == (size_type)(-1)) {
171 put(index_in_heap, v, index);
173 preserve_heap_property_up(index);
177 DistanceMap keys() const {
184 DistanceMap distance;
185 IndexInHeapPropertyMap index_in_heap;
187 // The distances being compared using compare and that are stored in the
189 typedef typename boost::property_traits<DistanceMap>::value_type distance_type;
191 // Get the parent of a given node in the heap
192 static size_type parent(size_type index) {
193 return (index - 1) / Arity;
196 // Get the child_idx'th child of a given node; 0 <= child_idx < Arity
197 static size_type child(size_type index, std::size_t child_idx) {
198 return index * Arity + child_idx + 1;
201 // Swap two elements in the heap by index, updating index_in_heap
202 void swap_heap_elements(size_type index_a, size_type index_b) {
204 Value value_a = data[index_a];
205 Value value_b = data[index_b];
206 data[index_a] = value_b;
207 data[index_b] = value_a;
208 put(index_in_heap, value_a, index_b);
209 put(index_in_heap, value_b, index_a);
212 // Emulate the indirect_cmp that is now folded into this heap class
213 bool compare_indirect(const Value& a, const Value& b) const {
214 return compare(get(distance, a), get(distance, b));
217 // Verify that the array forms a heap; commented out by default
218 void verify_heap() const {
219 // This is a very expensive test so it should be disabled even when
220 // NDEBUG is not defined
222 for (size_t i = 1; i < data.size(); ++i) {
223 if (compare_indirect(data[i], data[parent(i)])) {
224 BOOST_ASSERT (!"Element is smaller than its parent");
230 // Starting at a node, move up the tree swapping elements to preserve the
232 void preserve_heap_property_up(size_type index) {
233 size_type orig_index = index;
234 size_type num_levels_moved = 0;
235 // The first loop just saves swaps that need to be done in order to avoid
236 // aliasing issues in its search; there is a second loop that does the
237 // necessary swap operations
238 if (index == 0) return; // Do nothing on root
239 Value currently_being_moved = data[index];
240 distance_type currently_being_moved_dist =
241 get(distance, currently_being_moved);
243 if (index == 0) break; // Stop at root
244 size_type parent_index = parent(index);
245 Value parent_value = data[parent_index];
246 if (compare(currently_being_moved_dist, get(distance, parent_value))) {
248 index = parent_index;
251 break; // Heap property satisfied
254 // Actually do the moves -- move num_levels_moved elements down in the
255 // tree, then put currently_being_moved at the top
257 for (size_type i = 0; i < num_levels_moved; ++i) {
258 size_type parent_index = parent(index);
259 Value parent_value = data[parent_index];
260 put(index_in_heap, parent_value, index);
261 data[index] = parent_value;
262 index = parent_index;
264 data[index] = currently_being_moved;
265 put(index_in_heap, currently_being_moved, index);
269 // From the root, swap elements (each one with its smallest child) if there
270 // are any parent-child pairs that violate the heap property
271 void preserve_heap_property_down() {
272 if (data.empty()) return;
274 Value currently_being_moved = data[0];
275 distance_type currently_being_moved_dist =
276 get(distance, currently_being_moved);
277 size_type heap_size = data.size();
278 Value* data_ptr = &data[0];
280 size_type first_child_index = child(index, 0);
281 if (first_child_index >= heap_size) break; /* No children */
282 Value* child_base_ptr = data_ptr + first_child_index;
283 size_type smallest_child_index = 0;
284 distance_type smallest_child_dist = get(distance, child_base_ptr[smallest_child_index]);
285 if (first_child_index + Arity <= heap_size) {
286 // Special case for a statically known loop count (common case)
287 for (size_t i = 1; i < Arity; ++i) {
288 Value i_value = child_base_ptr[i];
289 distance_type i_dist = get(distance, i_value);
290 if (compare(i_dist, smallest_child_dist)) {
291 smallest_child_index = i;
292 smallest_child_dist = i_dist;
296 for (size_t i = 1; i < heap_size - first_child_index; ++i) {
297 distance_type i_dist = get(distance, child_base_ptr[i]);
298 if (compare(i_dist, smallest_child_dist)) {
299 smallest_child_index = i;
300 smallest_child_dist = i_dist;
304 if (compare(smallest_child_dist, currently_being_moved_dist)) {
305 swap_heap_elements(smallest_child_index + first_child_index, index);
306 index = smallest_child_index + first_child_index;
309 break; // Heap property satisfied
319 #endif // BOOST_D_ARY_HEAP_HPP