rename

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@607 ec762483-ff6d-05da-a07a-a48fb63a330f

1 files changed, 0 insertions, 305 deletions

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