summaryrefslogtreecommitdiff
path: root/utils/d_ary_heap.h
blob: 2ec716d3af322663a882c199452babb5cc75d7e0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
//
//=======================================================================
// 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