diff options
| -rw-r--r-- | utils/d_ary_heap.hpp | 305 |
1 files changed, 305 insertions, 0 deletions
diff --git a/utils/d_ary_heap.hpp b/utils/d_ary_heap.hpp new file mode 100644 index 00000000..2ec716d3 --- /dev/null +++ b/utils/d_ary_heap.hpp @@ -0,0 +1,305 @@ +// +//======================================================================= +// 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 <cassert> +#include <boost/static_assert.hpp> +#include <boost/shared_array.hpp> +#include <boost/property_map/property_map.hpp> + +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; + + 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() { + return data[0]; + } + + const Value& top() const { + return data[0]; + } + + void pop() { + put(index_in_heap, data[0], (size_type)(-1)); + if (data.size() != 1) { + data[0] = data.back(); + put(index_in_heap, data[0], 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(); + } + + 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)])) { + 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 |