boost/graph/detail/d_ary_heap.hpp

   1 //
   2 //=======================================================================
   3 // Copyright 2009 Trustees of Indiana University
   4 // Authors: Jeremiah J. Willcock, Andrew Lumsdaine
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11 #ifndef BOOST_D_ARY_HEAP_HPP
  12 #define BOOST_D_ARY_HEAP_HPP
  13
  14 #include <vector>
  15 #include <cstddef>
  16 #include <algorithm>
  17 #include <utility>
  18 #include <boost/assert.hpp>
  19 #include <boost/static_assert.hpp>
  20 #include <boost/shared_array.hpp>
  21 #include <boost/property_map/property_map.hpp>
  22
  23 namespace boost {
  24
  25   // Swap two elements in a property map without assuming they model
  26   // LvaluePropertyMap -- currently not used
  27   template <typename PropMap>
  28   inline void property_map_swap(
  29          PropMap prop_map,
  30          const typename boost::property_traits<PropMap>::key_type& ka,
  31          const typename boost::property_traits<PropMap>::key_type& kb) {
  32     typename boost::property_traits<PropMap>::value_type va = get(prop_map, ka);
  33     put(prop_map, ka, get(prop_map, kb));
  34     put(prop_map, kb, va);
  35   }
  36
  37   namespace detail {
  38     template <typename Value>
  39     class fixed_max_size_vector {
  40       boost::shared_array<Value> m_data;
  41       std::size_t m_size;
  42
  43       public:
  44       typedef std::size_t size_type;
  45       fixed_max_size_vector(std::size_t max_size)
  46         : m_data(new Value[max_size]), m_size(0) {}
  47       std::size_t size() const {return m_size;}
  48       bool empty() const {return m_size == 0;}
  49       Value& operator[](std::size_t i) {return m_data[i];}
  50       const Value& operator[](std::size_t i) const {return m_data[i];}
  51       void push_back(Value v) {m_data[m_size++] = v;}
  52       void pop_back() {--m_size;}
  53       Value& back() {return m_data[m_size - 1];}
  54       const Value& back() const {return m_data[m_size - 1];}
  55     };
  56   }
  57
  58   // D-ary heap using an indirect compare operator (use identity_property_map
  59   // as DistanceMap to get a direct compare operator).  This heap appears to be
  60   // commonly used for Dijkstra's algorithm for its good practical performance
  61   // on some platforms; asymptotically, it has an O(lg N) decrease-key
  62   // operation while that can be done in constant time on a relaxed heap.  The
  63   // implementation is mostly based on the binary heap page on Wikipedia and
  64   // online sources that state that the operations are the same for d-ary
  65   // heaps.  This code is not based on the old Boost d-ary heap code.
  66   //
  67   // - d_ary_heap_indirect is a model of UpdatableQueue as is needed for
  68   //   dijkstra_shortest_paths.
  69   //
  70   // - Value must model Assignable.
  71   // - Arity must be at least 2 (optimal value appears to be 4, both in my and
  72   //   third-party experiments).
  73   // - IndexInHeapMap must be a ReadWritePropertyMap from Value to
  74   //   Container::size_type (to store the index of each stored value within the
  75   //   heap for decrease-key aka update).
  76   // - DistanceMap must be a ReadablePropertyMap from Value to something
  77   //   (typedef'ed as distance_type).
  78   // - Compare must be a BinaryPredicate used as a less-than operator on
  79   //   distance_type.
  80   // - Container must be a random-access, contiguous container (in practice,
  81   //   the operations used probably require that it is std::vector<Value>).
  82   //
  83   template <typename Value,
  84             std::size_t Arity,
  85             typename IndexInHeapPropertyMap,
  86             typename DistanceMap,
  87             typename Compare = std::less<Value>,
  88             typename Container = std::vector<Value> >
  89   class d_ary_heap_indirect {
  90     BOOST_STATIC_ASSERT (Arity >= 2);
  91
  92     public:
  93     typedef typename Container::size_type size_type;
  94     typedef Value value_type;
  95     typedef typename boost::property_traits<DistanceMap>::value_type key_type;
  96     typedef DistanceMap key_map;
  97
  98     d_ary_heap_indirect(DistanceMap distance,
  99                         IndexInHeapPropertyMap index_in_heap,
 100                         const Compare& compare = Compare(),
 101                         const Container& data = Container())
 102       : compare(compare), data(data), distance(distance),
 103         index_in_heap(index_in_heap) {}
 104     /* Implicit copy constructor */
 105     /* Implicit assignment operator */
 106
 107     size_type size() const {
 108       return data.size();
 109     }
 110
 111     bool empty() const {
 112       return data.empty();
 113     }
 114
 115     void push(const Value& v) {
 116       size_type index = data.size();
 117       data.push_back(v);
 118       put(index_in_heap, v, index);
 119       preserve_heap_property_up(index);
 120       verify_heap();
 121     }
 122
 123     Value& top() {
 124       return data[0];
 125     }
 126
 127     const Value& top() const {
 128       return data[0];
 129     }
 130
 131     void pop() {
 132       put(index_in_heap, data[0], (size_type)(-1));
 133       if (data.size() != 1) {
 134         data[0] = data.back();
 135         put(index_in_heap, data[0], 0);
 136         data.pop_back();
 137         preserve_heap_property_down();
 138         verify_heap();
 139       } else {
 140         data.pop_back();
 141       }
 142     }
 143
 144     // This function assumes the key has been updated (using an external write
 145     // to the distance map or such)
 146     // See http://coding.derkeiler.com/Archive/General/comp.theory/2007-05/msg00043.html
 147     void update(const Value& v) { /* decrease-key */
 148       size_type index = get(index_in_heap, v);
 149       preserve_heap_property_up(index);
 150       verify_heap();
 151     }
 152
 153     bool contains(const Value& v) const {
 154       size_type index = get(index_in_heap, v);
 155       return (index != (size_type)(-1));
 156     }
 157
 158     void push_or_update(const Value& v) { /* insert if not present, else update */
 159       size_type index = get(index_in_heap, v);
 160       if (index == (size_type)(-1)) {
 161         index = data.size();
 162         data.push_back(v);
 163         put(index_in_heap, v, index);
 164       }
 165       preserve_heap_property_up(index);
 166       verify_heap();
 167     }
 168
 169     DistanceMap keys() const {
 170       return distance;
 171     }
 172
 173     private:
 174     Compare compare;
 175     Container data;
 176     DistanceMap distance;
 177     IndexInHeapPropertyMap index_in_heap;
 178
 179     // The distances being compared using compare and that are stored in the
 180     // distance map
 181     typedef typename boost::property_traits<DistanceMap>::value_type distance_type;
 182
 183     // Get the parent of a given node in the heap
 184     static size_type parent(size_type index) {
 185       return (index - 1) / Arity;
 186     }
 187
 188     // Get the child_idx'th child of a given node; 0 <= child_idx < Arity
 189     static size_type child(size_type index, std::size_t child_idx) {
 190       return index * Arity + child_idx + 1;
 191     }
 192
 193     // Swap two elements in the heap by index, updating index_in_heap
 194     void swap_heap_elements(size_type index_a, size_type index_b) {
 195       using std::swap;
 196       Value value_a = data[index_a];
 197       Value value_b = data[index_b];
 198       data[index_a] = value_b;
 199       data[index_b] = value_a;
 200       put(index_in_heap, value_a, index_b);
 201       put(index_in_heap, value_b, index_a);
 202     }
 203
 204     // Emulate the indirect_cmp that is now folded into this heap class
 205     bool compare_indirect(const Value& a, const Value& b) const {
 206       return compare(get(distance, a), get(distance, b));
 207     }
 208
 209     // Verify that the array forms a heap; commented out by default
 210     void verify_heap() const {
 211       // This is a very expensive test so it should be disabled even when
 212       // NDEBUG is not defined
 213 #if 0
 214       for (size_t i = 1; i < data.size(); ++i) {
 215         if (compare_indirect(data[i], data[parent(i)])) {
 216           BOOST_ASSERT (!"Element is smaller than its parent");
 217         }
 218       }
 219 #endif
 220     }
 221
 222     // Starting at a node, move up the tree swapping elements to preserve the
 223     // heap property
 224     void preserve_heap_property_up(size_type index) {
 225       size_type orig_index = index;
 226       size_type num_levels_moved = 0;
 227       // The first loop just saves swaps that need to be done in order to avoid
 228       // aliasing issues in its search; there is a second loop that does the
 229       // necessary swap operations
 230       if (index == 0) return; // Do nothing on root
 231       Value currently_being_moved = data[index];
 232       distance_type currently_being_moved_dist =
 233         get(distance, currently_being_moved);
 234       for (;;) {
 235         if (index == 0) break; // Stop at root
 236         size_type parent_index = parent(index);
 237         Value parent_value = data[parent_index];
 238         if (compare(currently_being_moved_dist, get(distance, parent_value))) {
 239           ++num_levels_moved;
 240           index = parent_index;
 241           continue;
 242         } else {
 243           break; // Heap property satisfied
 244         }
 245       }
 246       // Actually do the moves -- move num_levels_moved elements down in the
 247       // tree, then put currently_being_moved at the top
 248       index = orig_index;
 249       for (size_type i = 0; i < num_levels_moved; ++i) {
 250         size_type parent_index = parent(index);
 251         Value parent_value = data[parent_index];
 252         put(index_in_heap, parent_value, index);
 253         data[index] = parent_value;
 254         index = parent_index;
 255       }
 256       data[index] = currently_being_moved;
 257       put(index_in_heap, currently_being_moved, index);
 258       verify_heap();
 259     }
 260
 261     // From the root, swap elements (each one with its smallest child) if there
 262     // are any parent-child pairs that violate the heap property
 263     void preserve_heap_property_down() {
 264       if (data.empty()) return;
 265       size_type index = 0;
 266       Value currently_being_moved = data[0];
 267       distance_type currently_being_moved_dist =
 268         get(distance, currently_being_moved);
 269       size_type heap_size = data.size();
 270       Value* data_ptr = &data[0];
 271       for (;;) {
 272         size_type first_child_index = child(index, 0);
 273         if (first_child_index >= heap_size) break; /* No children */
 274         Value* child_base_ptr = data_ptr + first_child_index;
 275         size_type smallest_child_index = 0;
 276         distance_type smallest_child_dist = get(distance, child_base_ptr[smallest_child_index]);
 277         if (first_child_index + Arity <= heap_size) {
 278           // Special case for a statically known loop count (common case)
 279           for (size_t i = 1; i < Arity; ++i) {
 280             Value i_value = child_base_ptr[i];
 281             distance_type i_dist = get(distance, i_value);
 282             if (compare(i_dist, smallest_child_dist)) {
 283               smallest_child_index = i;
 284               smallest_child_dist = i_dist;
 285             }
 286           }
 287         } else {
 288           for (size_t i = 1; i < heap_size - first_child_index; ++i) {
 289             distance_type i_dist = get(distance, child_base_ptr[i]);
 290             if (compare(i_dist, smallest_child_dist)) {
 291               smallest_child_index = i;
 292               smallest_child_dist = i_dist;
 293             }
 294           }
 295         }
 296         if (compare(smallest_child_dist, currently_being_moved_dist)) {
 297           swap_heap_elements(smallest_child_index + first_child_index, index);
 298           index = smallest_child_index + first_child_index;
 299           continue;
 300         } else {
 301           break; // Heap property satisfied
 302         }
 303       }
 304       verify_heap();
 305     }
 306
 307   };
 308
 309 } // namespace boost
 310
 311 #endif // BOOST_D_ARY_HEAP_HPP