From fd703fce188a05b64eafabfa0a3b133879e2ca2d Mon Sep 17 00:00:00 2001
From: graehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>
Date: Sat, 21 Aug 2010 00:39:39 +0000
Subject: rename
git-svn-id: https://ws10smt.googlecode.com/svn/trunk@607 ec762483-ff6d-05da-a07a-a48fb63a330f
---
utils/d_ary_heap.h | 305 +++++++++++++++++++++++++++++++++++++++++++++++++++
utils/d_ary_heap.hpp | 305 ---------------------------------------------------
2 files changed, 305 insertions(+), 305 deletions(-)
create mode 100644 utils/d_ary_heap.h
delete mode 100644 utils/d_ary_heap.hpp
diff --git a/utils/d_ary_heap.h b/utils/d_ary_heap.h
new file mode 100644
index 00000000..2ec716d3
--- /dev/null
+++ b/utils/d_ary_heap.h
@@ -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
diff --git a/utils/d_ary_heap.hpp b/utils/d_ary_heap.hpp
deleted file mode 100644
index 2ec716d3..00000000
--- a/utils/d_ary_heap.hpp
+++ /dev/null
@@ -1,305 +0,0 @@
-//
-//=======================================================================
-// 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
--
cgit v1.2.3