Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright 2009 Trustees of Indiana University
Chris@16: // Authors: Jeremiah J. Willcock, Andrew Lumsdaine
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: #ifndef BOOST_D_ARY_HEAP_HPP
Chris@16: #define BOOST_D_ARY_HEAP_HPP
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <cstddef>
Chris@16: #include <algorithm>
Chris@16: #include <utility>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/shared_array.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: 
Chris@16: // WARNING: it is not safe to copy a d_ary_heap_indirect and then modify one of
Chris@16: // the copies.  The class is required to be copyable so it can be passed around
Chris@16: // (without move support from C++11), but it deep-copies the heap contents yet
Chris@16: // shallow-copies the index_in_heap_map.
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   // Swap two elements in a property map without assuming they model
Chris@16:   // LvaluePropertyMap -- currently not used
Chris@16:   template <typename PropMap>
Chris@16:   inline void property_map_swap(
Chris@16:          PropMap prop_map,
Chris@16:          const typename boost::property_traits<PropMap>::key_type& ka, 
Chris@16:          const typename boost::property_traits<PropMap>::key_type& kb) {
Chris@16:     typename boost::property_traits<PropMap>::value_type va = get(prop_map, ka);
Chris@16:     put(prop_map, ka, get(prop_map, kb));
Chris@16:     put(prop_map, kb, va);
Chris@16:   }
Chris@16: 
Chris@16:   namespace detail {
Chris@16:     template <typename Value>
Chris@16:     class fixed_max_size_vector {
Chris@16:       boost::shared_array<Value> m_data;
Chris@16:       std::size_t m_size;
Chris@16: 
Chris@16:       public:
Chris@16:       typedef std::size_t size_type;
Chris@16:       fixed_max_size_vector(std::size_t max_size)
Chris@16:         : m_data(new Value[max_size]), m_size(0) {}
Chris@16:       std::size_t size() const {return m_size;}
Chris@16:       bool empty() const {return m_size == 0;}
Chris@16:       Value& operator[](std::size_t i) {return m_data[i];}
Chris@16:       const Value& operator[](std::size_t i) const {return m_data[i];}
Chris@16:       void push_back(Value v) {m_data[m_size++] = v;}
Chris@16:       void pop_back() {--m_size;}
Chris@16:       Value& back() {return m_data[m_size - 1];}
Chris@16:       const Value& back() const {return m_data[m_size - 1];}
Chris@16:     };
Chris@16:   }
Chris@16: 
Chris@16:   // D-ary heap using an indirect compare operator (use identity_property_map
Chris@16:   // as DistanceMap to get a direct compare operator).  This heap appears to be
Chris@16:   // commonly used for Dijkstra's algorithm for its good practical performance
Chris@16:   // on some platforms; asymptotically, it has an O(lg N) decrease-key
Chris@16:   // operation while that can be done in constant time on a relaxed heap.  The
Chris@16:   // implementation is mostly based on the binary heap page on Wikipedia and
Chris@16:   // online sources that state that the operations are the same for d-ary
Chris@16:   // heaps.  This code is not based on the old Boost d-ary heap code.
Chris@16:   //
Chris@16:   // - d_ary_heap_indirect is a model of UpdatableQueue as is needed for
Chris@16:   //   dijkstra_shortest_paths.
Chris@16:   //
Chris@16:   // - Value must model Assignable.
Chris@16:   // - Arity must be at least 2 (optimal value appears to be 4, both in my and
Chris@16:   //   third-party experiments).
Chris@16:   // - IndexInHeapMap must be a ReadWritePropertyMap from Value to
Chris@16:   //   Container::size_type (to store the index of each stored value within the
Chris@16:   //   heap for decrease-key aka update).
Chris@16:   // - DistanceMap must be a ReadablePropertyMap from Value to something
Chris@16:   //   (typedef'ed as distance_type).
Chris@16:   // - Compare must be a BinaryPredicate used as a less-than operator on
Chris@16:   //   distance_type.
Chris@16:   // - Container must be a random-access, contiguous container (in practice,
Chris@16:   //   the operations used probably require that it is std::vector<Value>).
Chris@16:   //
Chris@16:   template <typename Value,
Chris@16:             std::size_t Arity,
Chris@16:             typename IndexInHeapPropertyMap,
Chris@16:             typename DistanceMap,
Chris@16:             typename Compare = std::less<Value>,
Chris@16:             typename Container = std::vector<Value> >
Chris@16:   class d_ary_heap_indirect {
Chris@16:     BOOST_STATIC_ASSERT (Arity >= 2);
Chris@16: 
Chris@16:     public:
Chris@16:     typedef typename Container::size_type size_type;
Chris@16:     typedef Value value_type;
Chris@16:     typedef typename boost::property_traits<DistanceMap>::value_type key_type;
Chris@16:     typedef DistanceMap key_map;
Chris@16: 
Chris@16:     d_ary_heap_indirect(DistanceMap distance,
Chris@16:                         IndexInHeapPropertyMap index_in_heap,
Chris@16:                         const Compare& compare = Compare(),
Chris@16:                         const Container& data = Container())
Chris@16:       : compare(compare), data(data), distance(distance),
Chris@16:         index_in_heap(index_in_heap) {}
Chris@16:     /* Implicit copy constructor */
Chris@16:     /* Implicit assignment operator */
Chris@16: 
Chris@16:     size_type size() const {
Chris@16:       return data.size();
Chris@16:     }
Chris@16: 
Chris@16:     bool empty() const {
Chris@16:       return data.empty();
Chris@16:     }
Chris@16: 
Chris@16:     void push(const Value& v) {
Chris@16:       size_type index = data.size();
Chris@16:       data.push_back(v);
Chris@16:       put(index_in_heap, v, index);
Chris@16:       preserve_heap_property_up(index);
Chris@16:       verify_heap();
Chris@16:     }
Chris@16: 
Chris@16:     Value& top() {
Chris@16:       BOOST_ASSERT (!this->empty());
Chris@16:       return data[0];
Chris@16:     }
Chris@16: 
Chris@16:     const Value& top() const {
Chris@16:       BOOST_ASSERT (!this->empty());
Chris@16:       return data[0];
Chris@16:     }
Chris@16: 
Chris@16:     void pop() {
Chris@16:       BOOST_ASSERT (!this->empty());
Chris@16:       put(index_in_heap, data[0], (size_type)(-1));
Chris@16:       if (data.size() != 1) {
Chris@16:         data[0] = data.back();
Chris@16:         put(index_in_heap, data[0], (size_type)(0));
Chris@16:         data.pop_back();
Chris@16:         preserve_heap_property_down();
Chris@16:         verify_heap();
Chris@16:       } else {
Chris@16:         data.pop_back();
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // This function assumes the key has been updated (using an external write
Chris@16:     // to the distance map or such)
Chris@16:     // See http://coding.derkeiler.com/Archive/General/comp.theory/2007-05/msg00043.html
Chris@16:     void update(const Value& v) { /* decrease-key */
Chris@16:       size_type index = get(index_in_heap, v);
Chris@16:       preserve_heap_property_up(index);
Chris@16:       verify_heap();
Chris@16:     }
Chris@16: 
Chris@16:     bool contains(const Value& v) const {
Chris@16:       size_type index = get(index_in_heap, v);
Chris@16:       return (index != (size_type)(-1));
Chris@16:     }
Chris@16: 
Chris@16:     void push_or_update(const Value& v) { /* insert if not present, else update */
Chris@16:       size_type index = get(index_in_heap, v);
Chris@16:       if (index == (size_type)(-1)) {
Chris@16:         index = data.size();
Chris@16:         data.push_back(v);
Chris@16:         put(index_in_heap, v, index);
Chris@16:       }
Chris@16:       preserve_heap_property_up(index);
Chris@16:       verify_heap();
Chris@16:     }
Chris@16: 
Chris@16:     DistanceMap keys() const {
Chris@16:       return distance;
Chris@16:     }
Chris@16: 
Chris@16:     private:
Chris@16:     Compare compare;
Chris@16:     Container data;
Chris@16:     DistanceMap distance;
Chris@16:     IndexInHeapPropertyMap index_in_heap;
Chris@16: 
Chris@16:     // The distances being compared using compare and that are stored in the
Chris@16:     // distance map
Chris@16:     typedef typename boost::property_traits<DistanceMap>::value_type distance_type;
Chris@16: 
Chris@16:     // Get the parent of a given node in the heap
Chris@16:     static size_type parent(size_type index) {
Chris@16:       return (index - 1) / Arity;
Chris@16:     }
Chris@16: 
Chris@16:     // Get the child_idx'th child of a given node; 0 <= child_idx < Arity
Chris@16:     static size_type child(size_type index, std::size_t child_idx) {
Chris@16:       return index * Arity + child_idx + 1;
Chris@16:     }
Chris@16: 
Chris@16:     // Swap two elements in the heap by index, updating index_in_heap
Chris@16:     void swap_heap_elements(size_type index_a, size_type index_b) {
Chris@16:       using std::swap;
Chris@16:       Value value_a = data[index_a];
Chris@16:       Value value_b = data[index_b];
Chris@16:       data[index_a] = value_b;
Chris@16:       data[index_b] = value_a;
Chris@16:       put(index_in_heap, value_a, index_b);
Chris@16:       put(index_in_heap, value_b, index_a);
Chris@16:     }
Chris@16: 
Chris@16:     // Emulate the indirect_cmp that is now folded into this heap class
Chris@16:     bool compare_indirect(const Value& a, const Value& b) const {
Chris@16:       return compare(get(distance, a), get(distance, b));
Chris@16:     }
Chris@16: 
Chris@16:     // Verify that the array forms a heap; commented out by default
Chris@16:     void verify_heap() const {
Chris@16:       // This is a very expensive test so it should be disabled even when
Chris@16:       // NDEBUG is not defined
Chris@16: #if 0
Chris@16:       for (size_t i = 1; i < data.size(); ++i) {
Chris@16:         if (compare_indirect(data[i], data[parent(i)])) {
Chris@16:           BOOST_ASSERT (!"Element is smaller than its parent");
Chris@16:         }
Chris@16:       }
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     // Starting at a node, move up the tree swapping elements to preserve the
Chris@16:     // heap property
Chris@16:     void preserve_heap_property_up(size_type index) {
Chris@16:       size_type orig_index = index;
Chris@16:       size_type num_levels_moved = 0;
Chris@16:       // The first loop just saves swaps that need to be done in order to avoid
Chris@16:       // aliasing issues in its search; there is a second loop that does the
Chris@16:       // necessary swap operations
Chris@16:       if (index == 0) return; // Do nothing on root
Chris@16:       Value currently_being_moved = data[index];
Chris@16:       distance_type currently_being_moved_dist =
Chris@16:         get(distance, currently_being_moved);
Chris@16:       for (;;) {
Chris@16:         if (index == 0) break; // Stop at root
Chris@16:         size_type parent_index = parent(index);
Chris@16:         Value parent_value = data[parent_index];
Chris@16:         if (compare(currently_being_moved_dist, get(distance, parent_value))) {
Chris@16:           ++num_levels_moved;
Chris@16:           index = parent_index;
Chris@16:           continue;
Chris@16:         } else {
Chris@16:           break; // Heap property satisfied
Chris@16:         }
Chris@16:       }
Chris@16:       // Actually do the moves -- move num_levels_moved elements down in the
Chris@16:       // tree, then put currently_being_moved at the top
Chris@16:       index = orig_index;
Chris@16:       for (size_type i = 0; i < num_levels_moved; ++i) {
Chris@16:         size_type parent_index = parent(index);
Chris@16:         Value parent_value = data[parent_index];
Chris@16:         put(index_in_heap, parent_value, index);
Chris@16:         data[index] = parent_value;
Chris@16:         index = parent_index;
Chris@16:       }
Chris@16:       data[index] = currently_being_moved;
Chris@16:       put(index_in_heap, currently_being_moved, index);
Chris@16:       verify_heap();
Chris@16:     }
Chris@16: 
Chris@16:     // From the root, swap elements (each one with its smallest child) if there
Chris@16:     // are any parent-child pairs that violate the heap property
Chris@16:     void preserve_heap_property_down() {
Chris@16:       if (data.empty()) return;
Chris@16:       size_type index = 0;
Chris@16:       Value currently_being_moved = data[0];
Chris@16:       distance_type currently_being_moved_dist =
Chris@16:         get(distance, currently_being_moved);
Chris@16:       size_type heap_size = data.size();
Chris@16:       Value* data_ptr = &data[0];
Chris@16:       for (;;) {
Chris@16:         size_type first_child_index = child(index, 0);
Chris@16:         if (first_child_index >= heap_size) break; /* No children */
Chris@16:         Value* child_base_ptr = data_ptr + first_child_index;
Chris@16:         size_type smallest_child_index = 0;
Chris@16:         distance_type smallest_child_dist = get(distance, child_base_ptr[smallest_child_index]);
Chris@16:         if (first_child_index + Arity <= heap_size) {
Chris@16:           // Special case for a statically known loop count (common case)
Chris@16:           for (size_t i = 1; i < Arity; ++i) {
Chris@16:             Value i_value = child_base_ptr[i];
Chris@16:             distance_type i_dist = get(distance, i_value);
Chris@16:             if (compare(i_dist, smallest_child_dist)) {
Chris@16:               smallest_child_index = i;
Chris@16:               smallest_child_dist = i_dist;
Chris@16:             }
Chris@16:           }
Chris@16:         } else {
Chris@16:           for (size_t i = 1; i < heap_size - first_child_index; ++i) {
Chris@16:             distance_type i_dist = get(distance, child_base_ptr[i]);
Chris@16:             if (compare(i_dist, smallest_child_dist)) {
Chris@16:               smallest_child_index = i;
Chris@16:               smallest_child_dist = i_dist;
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:         if (compare(smallest_child_dist, currently_being_moved_dist)) {
Chris@16:           swap_heap_elements(smallest_child_index + first_child_index, index);
Chris@16:           index = smallest_child_index + first_child_index;
Chris@16:           continue;
Chris@16:         } else {
Chris@16:           break; // Heap property satisfied
Chris@16:         }
Chris@16:       }
Chris@16:       verify_heap();
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_D_ARY_HEAP_HPP