summaryrefslogtreecommitdiff
path: root/utils/d_ary_heap.hpp
diff options
context:
space:
mode:
authorgraehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>2010-08-21 00:39:10 +0000
committergraehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>2010-08-21 00:39:10 +0000
commit35d409935c9085ed481ec5b7cf17fde4ac6e8afc (patch)
treeafe8fd233aca0e6bb14ea1f0b46326b0335360ee /utils/d_ary_heap.hpp
parentc664c1c1a5d8196dd5a8c9397e60afeef4c06229 (diff)
from boost graph detail
git-svn-id: https://ws10smt.googlecode.com/svn/trunk@606 ec762483-ff6d-05da-a07a-a48fb63a330f
Diffstat (limited to 'utils/d_ary_heap.hpp')
-rw-r--r--utils/d_ary_heap.hpp305
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