From bb480adcc7177a76e2f3d2e1c428fa729ce067d3 Mon Sep 17 00:00:00 2001 From: graehl 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 +#include +#include +#include +#include +#include +#include +#include + +namespace boost { + + // Swap two elements in a property map without assuming they model + // LvaluePropertyMap -- currently not used + template + inline void property_map_swap( + PropMap prop_map, + const typename boost::property_traits::key_type& ka, + const typename boost::property_traits::key_type& kb) { + typename boost::property_traits::value_type va = get(prop_map, ka); + put(prop_map, ka, get(prop_map, kb)); + put(prop_map, kb, va); + } + + namespace detail { + template + class fixed_max_size_vector { + boost::shared_array 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). + // + template , + typename Container = std::vector > + 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::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 -#include -#include -#include -#include -#include -#include -#include - -namespace boost { - - // Swap two elements in a property map without assuming they model - // LvaluePropertyMap -- currently not used - template - inline void property_map_swap( - PropMap prop_map, - const typename boost::property_traits::key_type& ka, - const typename boost::property_traits::key_type& kb) { - typename boost::property_traits::value_type va = get(prop_map, ka); - put(prop_map, ka, get(prop_map, kb)); - put(prop_map, kb, va); - } - - namespace detail { - template - class fixed_max_size_vector { - boost::shared_array 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). - // - template , - typename Container = std::vector > - 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::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