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> property_map_swap(PropMap prop_map,const typename boost::property_traits<PropMap>::key_type & ka,const typename boost::property_traits<PropMap>::key_type & kb)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; fixed_max_size_vector(std::size_t max_size)50 fixed_max_size_vector(std::size_t max_size) 51 : m_data(new Value[max_size]), m_size(0) {} size() const52 std::size_t size() const {return m_size;} empty() const53 bool empty() const {return m_size == 0;} operator [](std::size_t i)54 Value& operator[](std::size_t i) {return m_data[i];} operator [](std::size_t i) const55 const Value& operator[](std::size_t i) const {return m_data[i];} push_back(Value v)56 void push_back(Value v) {m_data[m_size++] = v;} pop_back()57 void pop_back() {--m_size;} back()58 Value& back() {return m_data[m_size - 1];} back() const59 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 d_ary_heap_indirect(DistanceMap distance,IndexInHeapPropertyMap index_in_heap,const Compare & compare=Compare (),const Container & data=Container ())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 size() const112 size_type size() const { 113 return data.size(); 114 } 115 empty() const116 bool empty() const { 117 return data.empty(); 118 } 119 push(const Value & v)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 top()128 Value& top() { 129 BOOST_ASSERT (!this->empty()); 130 return data[0]; 131 } 132 top() const133 const Value& top() const { 134 BOOST_ASSERT (!this->empty()); 135 return data[0]; 136 } 137 pop()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 update(const Value & v)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 contains(const Value & v) const161 bool contains(const Value& v) const { 162 size_type index = get(index_in_heap, v); 163 return (index != (size_type)(-1)); 164 } 165 push_or_update(const Value & v)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 keys() const177 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 parent(size_type index)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 child(size_type index,std::size_t child_idx)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 swap_heap_elements(size_type index_a,size_type index_b)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 compare_indirect(const Value & a,const Value & b) const213 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 verify_heap() const218 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 preserve_heap_property_up(size_type index)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 preserve_heap_property_down()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 320