]>
Commit | Line | Data |
---|---|---|
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 | 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 | 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 */ | |
111 | ||
112 | size_type size() const { | |
113 | return data.size(); | |
114 | } | |
115 | ||
116 | bool empty() const { | |
117 | return data.empty(); | |
118 | } | |
119 | ||
120 | void push(const Value& v) { | |
121 | size_type index = data.size(); | |
122 | data.push_back(v); | |
123 | put(index_in_heap, v, index); | |
124 | preserve_heap_property_up(index); | |
125 | verify_heap(); | |
126 | } | |
127 | ||
128 | Value& top() { | |
129 | BOOST_ASSERT (!this->empty()); | |
130 | return data[0]; | |
131 | } | |
132 | ||
133 | const Value& top() const { | |
134 | BOOST_ASSERT (!this->empty()); | |
135 | return data[0]; | |
136 | } | |
137 | ||
138 | void pop() { | |
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)); | |
144 | data.pop_back(); | |
145 | preserve_heap_property_down(); | |
146 | verify_heap(); | |
147 | } else { | |
148 | data.pop_back(); | |
149 | } | |
150 | } | |
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 | void update(const Value& v) { /* decrease-key */ | |
156 | size_type index = get(index_in_heap, v); | |
157 | preserve_heap_property_up(index); | |
158 | 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 | static size_type parent(size_type index) { | |
193 | return (index - 1) / Arity; | |
194 | } | |
195 | ||
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; | |
199 | } | |
200 | ||
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) { | |
203 | using std::swap; | |
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); | |
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 | 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 | 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); | |
242 | for (;;) { | |
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))) { | |
247 | ++num_levels_moved; | |
248 | 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 | index = orig_index; | |
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; | |
263 | } | |
264 | data[index] = currently_being_moved; | |
265 | put(index_in_heap, currently_being_moved, index); | |
266 | 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 | void preserve_heap_property_down() { | |
272 | if (data.empty()) return; | |
273 | size_type index = 0; | |
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]; | |
279 | for (;;) { | |
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; | |
293 | } | |
294 | } | |
295 | } else { | |
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; | |
301 | } | |
302 | } | |
303 | } | |
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; | |
307 | 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 |