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