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.hpp | 305 --------------------------------------------------- 1 file changed, 305 deletions(-) delete mode 100644 utils/d_ary_heap.hpp (limited to 'utils/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