Line data Source code
1 : //
2 : //=======================================================================
3 : // Copyright 2009 Trustees of Indiana University
4 : // Authors: Jeremiah J. Willcock, Andrew Lumsdaine
5 : //
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 : //=======================================================================
10 : //
11 : #ifndef BOOST_D_ARY_HEAP_HPP
12 : #define BOOST_D_ARY_HEAP_HPP
13 :
14 : #include <vector>
15 : #include <cstddef>
16 : #include <algorithm>
17 : #include <utility>
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>
22 :
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.
27 :
28 : namespace boost {
29 :
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(
34 : PropMap prop_map,
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);
40 : }
41 :
42 : namespace detail {
43 : template <typename Value>
44 : class fixed_max_size_vector {
45 : boost::shared_array<Value> m_data;
46 : std::size_t m_size;
47 :
48 : public:
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];}
60 : };
61 : }
62 :
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.
71 : //
72 : // - d_ary_heap_indirect is a model of UpdatableQueue as is needed for
73 : // dijkstra_shortest_paths.
74 : //
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
84 : // distance_type.
85 : // - Container must be a random-access, contiguous container (in practice,
86 : // the operations used probably require that it is std::vector<Value>).
87 : //
88 : template <typename Value,
89 : std::size_t Arity,
90 : typename IndexInHeapPropertyMap,
91 : typename DistanceMap,
92 : typename Compare = std::less<Value>,
93 : typename Container = std::vector<Value> >
94 0 : class d_ary_heap_indirect {
95 : BOOST_STATIC_ASSERT (Arity >= 2);
96 :
97 : public:
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;
102 :
103 0 : 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 0 : index_in_heap(index_in_heap) {}
109 : /* Implicit copy constructor */
110 : /* Implicit assignment operator */
111 :
112 : size_type size() const {
113 : return data.size();
114 : }
115 :
116 0 : bool empty() const {
117 0 : return data.empty();
118 : }
119 :
120 0 : void push(const Value& v) {
121 0 : size_type index = data.size();
122 0 : data.push_back(v);
123 0 : put(index_in_heap, v, index);
124 0 : preserve_heap_property_up(index);
125 0 : verify_heap();
126 0 : }
127 :
128 0 : Value& top() {
129 0 : BOOST_ASSERT (!this->empty());
130 0 : return data[0];
131 : }
132 :
133 : const Value& top() const {
134 : BOOST_ASSERT (!this->empty());
135 : return data[0];
136 : }
137 :
138 0 : void pop() {
139 0 : BOOST_ASSERT (!this->empty());
140 0 : put(index_in_heap, data[0], (size_type)(-1));
141 0 : if (data.size() != 1) {
142 0 : data[0] = data.back();
143 0 : put(index_in_heap, data[0], (size_type)(0));
144 0 : data.pop_back();
145 0 : preserve_heap_property_down();
146 0 : verify_heap();
147 : } else {
148 0 : data.pop_back();
149 : }
150 0 : }
151 :
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 0 : void update(const Value& v) { /* decrease-key */
156 0 : size_type index = get(index_in_heap, v);
157 0 : preserve_heap_property_up(index);
158 0 : verify_heap();
159 : }
160 :
161 : bool contains(const Value& v) const {
162 : size_type index = get(index_in_heap, v);
163 : return (index != (size_type)(-1));
164 : }
165 :
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)) {
169 : index = data.size();
170 : data.push_back(v);
171 : put(index_in_heap, v, index);
172 : }
173 : preserve_heap_property_up(index);
174 : verify_heap();
175 : }
176 :
177 : DistanceMap keys() const {
178 : return distance;
179 : }
180 :
181 : private:
182 : Compare compare;
183 : Container data;
184 : DistanceMap distance;
185 : IndexInHeapPropertyMap index_in_heap;
186 :
187 : // The distances being compared using compare and that are stored in the
188 : // distance map
189 : typedef typename boost::property_traits<DistanceMap>::value_type distance_type;
190 :
191 : // Get the parent of a given node in the heap
192 0 : static size_type parent(size_type index) {
193 0 : return (index - 1) / Arity;
194 : }
195 :
196 : // Get the child_idx'th child of a given node; 0 <= child_idx < Arity
197 0 : static size_type child(size_type index, std::size_t child_idx) {
198 0 : return index * Arity + child_idx + 1;
199 : }
200 :
201 : // Swap two elements in the heap by index, updating index_in_heap
202 0 : void swap_heap_elements(size_type index_a, size_type index_b) {
203 : using std::swap;
204 0 : Value value_a = data[index_a];
205 0 : Value value_b = data[index_b];
206 0 : data[index_a] = value_b;
207 0 : data[index_b] = value_a;
208 0 : put(index_in_heap, value_a, index_b);
209 0 : put(index_in_heap, value_b, index_a);
210 : }
211 :
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));
215 : }
216 :
217 : // Verify that the array forms a heap; commented out by default
218 0 : void verify_heap() const {
219 : // This is a very expensive test so it should be disabled even when
220 : // NDEBUG is not defined
221 : #if 0
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");
225 : }
226 : }
227 : #endif
228 : }
229 :
230 : // Starting at a node, move up the tree swapping elements to preserve the
231 : // heap property
232 0 : void preserve_heap_property_up(size_type index) {
233 0 : size_type orig_index = index;
234 0 : 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 0 : if (index == 0) return; // Do nothing on root
239 0 : Value currently_being_moved = data[index];
240 0 : distance_type currently_being_moved_dist =
241 0 : get(distance, currently_being_moved);
242 0 : for (;;) {
243 0 : if (index == 0) break; // Stop at root
244 0 : size_type parent_index = parent(index);
245 0 : Value parent_value = data[parent_index];
246 0 : if (compare(currently_being_moved_dist, get(distance, parent_value))) {
247 0 : ++num_levels_moved;
248 0 : index = parent_index;
249 : continue;
250 : } else {
251 : break; // Heap property satisfied
252 : }
253 : }
254 : // Actually do the moves -- move num_levels_moved elements down in the
255 : // tree, then put currently_being_moved at the top
256 0 : index = orig_index;
257 0 : for (size_type i = 0; i < num_levels_moved; ++i) {
258 0 : size_type parent_index = parent(index);
259 0 : Value parent_value = data[parent_index];
260 0 : put(index_in_heap, parent_value, index);
261 0 : data[index] = parent_value;
262 0 : index = parent_index;
263 : }
264 0 : data[index] = currently_being_moved;
265 0 : put(index_in_heap, currently_being_moved, index);
266 0 : verify_heap();
267 : }
268 :
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 0 : void preserve_heap_property_down() {
272 0 : if (data.empty()) return;
273 0 : size_type index = 0;
274 0 : Value currently_being_moved = data[0];
275 0 : distance_type currently_being_moved_dist =
276 0 : get(distance, currently_being_moved);
277 0 : size_type heap_size = data.size();
278 0 : Value* data_ptr = &data[0];
279 : for (;;) {
280 0 : size_type first_child_index = child(index, 0);
281 0 : if (first_child_index >= heap_size) break; /* No children */
282 0 : Value* child_base_ptr = data_ptr + first_child_index;
283 0 : size_type smallest_child_index = 0;
284 0 : distance_type smallest_child_dist = get(distance, child_base_ptr[smallest_child_index]);
285 0 : if (first_child_index + Arity <= heap_size) {
286 : // Special case for a statically known loop count (common case)
287 0 : for (size_t i = 1; i < Arity; ++i) {
288 0 : Value i_value = child_base_ptr[i];
289 0 : distance_type i_dist = get(distance, i_value);
290 0 : if (compare(i_dist, smallest_child_dist)) {
291 0 : smallest_child_index = i;
292 0 : smallest_child_dist = i_dist;
293 : }
294 : }
295 : } else {
296 0 : for (size_t i = 1; i < heap_size - first_child_index; ++i) {
297 0 : distance_type i_dist = get(distance, child_base_ptr[i]);
298 0 : if (compare(i_dist, smallest_child_dist)) {
299 0 : smallest_child_index = i;
300 0 : smallest_child_dist = i_dist;
301 : }
302 : }
303 : }
304 0 : if (compare(smallest_child_dist, currently_being_moved_dist)) {
305 0 : swap_heap_elements(smallest_child_index + first_child_index, index);
306 0 : index = smallest_child_index + first_child_index;
307 0 : continue;
308 : } else {
309 : break; // Heap property satisfied
310 : }
311 : }
312 : verify_heap();
313 : }
314 :
315 : };
316 :
317 : } // namespace boost
318 :
319 : #endif // BOOST_D_ARY_HEAP_HPP
|
