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