BinaryHeap.h
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2008, Willow Garage, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the Willow Garage nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *********************************************************************/
34 
35 /* Author: Ioan Sucan */
36 
37 #ifndef OMPL_DATASTRUCTURES_BINARY_HEAP_
38 #define OMPL_DATASTRUCTURES_BINARY_HEAP_
39 
40 #include <functional>
41 #include <utility>
42 #include <vector>
43 #include <cassert>
44 
45 namespace ompl
46 {
51  template <typename _T, class LessThan = std::less<_T>>
52  class BinaryHeap
53  {
54  public:
59  class Element
60  {
61  friend class BinaryHeap;
62 
63  private:
64  Element() = default;
65  ~Element() = default;
67  unsigned int position;
68 
69  public:
71  _T data;
72  };
73 
75  using EventAfterInsert = void (*)(Element *, void *);
76 
78  using EventBeforeRemove = void (*)(Element *, void *);
79 
80  BinaryHeap()
81  {
82  eventAfterInsert_ = nullptr;
83  eventBeforeRemove_ = nullptr;
84  }
85 
86  BinaryHeap(LessThan lt) : lt_(std::move(lt))
87  {
88  eventAfterInsert_ = nullptr;
89  eventBeforeRemove_ = nullptr;
90  }
91 
92  ~BinaryHeap()
93  {
94  clear();
95  }
96 
98  void onAfterInsert(EventAfterInsert event, void *arg)
99  {
100  eventAfterInsert_ = event;
101  eventAfterInsertData_ = arg;
102  }
103 
105  void onBeforeRemove(EventBeforeRemove event, void *arg)
106  {
107  eventBeforeRemove_ = event;
108  eventBeforeRemoveData_ = arg;
109  }
110 
112  void clear()
113  {
114  for (auto i = vector_.begin(); i != vector_.end(); ++i)
115  delete *i;
116  vector_.clear();
117  }
118 
120  Element *top() const
121  {
122  return vector_.empty() ? nullptr : vector_.at(0);
123  }
124 
126  void pop()
127  {
128  removePos(0);
129  }
130 
132  void remove(Element *element)
133  {
134  if (eventBeforeRemove_)
135  eventBeforeRemove_(element, eventBeforeRemoveData_);
136  removePos(element->position);
137  }
138 
140  Element *insert(const _T &data)
141  {
142  auto *element = new Element();
143  element->data = data;
144  const unsigned int pos = vector_.size();
145  element->position = pos;
146  vector_.push_back(element);
147  percolateUp(pos);
148  if (eventAfterInsert_)
149  eventAfterInsert_(element, eventAfterInsertData_);
150  return element;
151  }
152 
154  void insert(const std::vector<_T> &list)
155  {
156  const unsigned int n = vector_.size();
157  const unsigned int m = list.size();
158  for (unsigned int i = 0; i < m; ++i)
159  {
160  const unsigned int pos = i + n;
161  Element *element = newElement(list[i], pos);
162  vector_.push_back(element);
163  percolateUp(pos);
164  if (eventAfterInsert_)
165  eventAfterInsert_(element, eventAfterInsertData_);
166  }
167  }
168 
170  void buildFrom(const std::vector<_T> &list)
171  {
172  clear();
173  const unsigned int m = list.size();
174  for (unsigned int i = 0; i < m; ++i)
175  vector_.push_back(newElement(list[i], i));
176  build();
177  }
178 
180  void rebuild()
181  {
182  build();
183  }
184 
186  void update(Element *element)
187  {
188  const unsigned int pos = element->position;
189  assert(vector_[pos] == element);
190  percolateUp(pos);
191  percolateDown(pos);
192  }
193 
195  bool empty() const
196  {
197  return vector_.empty();
198  }
199 
201  unsigned int size() const
202  {
203  return vector_.size();
204  }
205 
207  void getContent(std::vector<_T> &content) const
208  {
209  for (auto i = vector_.begin(); i != vector_.end(); ++i)
210  content.push_back((*i)->data);
211  }
212 
214  void sort(std::vector<_T> &list)
215  {
216  const unsigned int n = list.size();
217  std::vector<Element *> backup = vector_;
218  vector_.clear();
219  for (unsigned int i = 0; i < n; ++i)
220  vector_.push_back(newElement(list[i], i));
221  build();
222  list.clear();
223  list.reserve(n);
224 
225  for (unsigned int i = 0; i < n; ++i)
226  {
227  list.push_back(vector_[0]->data);
228  removePos(0);
229  }
230  vector_ = backup;
231  }
232 
235  {
236  return lt_;
237  }
238 
239  private:
240  LessThan lt_;
241 
242  std::vector<Element *> vector_;
243 
244  EventAfterInsert eventAfterInsert_;
245  void *eventAfterInsertData_;
246  EventBeforeRemove eventBeforeRemove_;
247  void *eventBeforeRemoveData_;
248 
249  void removePos(unsigned int pos)
250  {
251  const int n = vector_.size() - 1;
252  delete vector_[pos];
253  if ((int)pos < n)
254  {
255  vector_[pos] = vector_.back();
256  vector_[pos]->position = pos;
257  vector_.pop_back();
258  percolateDown(pos);
259  }
260  else
261  vector_.pop_back();
262  }
263 
264  Element *newElement(_T &data, unsigned int pos) const
265  {
266  auto *element = new Element();
267  element->data = data;
268  element->position = pos;
269  return element;
270  }
271 
272  void build()
273  {
274  for (int i = vector_.size() / 2 - 1; i >= 0; --i)
275  percolateDown(i);
276  }
277 
278  void percolateDown(const unsigned int pos)
279  {
280  const unsigned int n = vector_.size();
281  Element *tmp = vector_[pos];
282  unsigned int parent = pos;
283  unsigned int child = (pos + 1) << 1;
284 
285  while (child < n)
286  {
287  if (lt_(vector_[child - 1]->data, vector_[child]->data))
288  --child;
289  if (lt_(vector_[child]->data, tmp->data))
290  {
291  vector_[parent] = vector_[child];
292  vector_[parent]->position = parent;
293  }
294  else
295  break;
296  parent = child;
297  child = (child + 1) << 1;
298  }
299  if (child == n)
300  {
301  --child;
302  if (lt_(vector_[child]->data, tmp->data))
303  {
304  vector_[parent] = vector_[child];
305  vector_[parent]->position = parent;
306  parent = child;
307  }
308  }
309  if (parent != pos)
310  {
311  vector_[parent] = tmp;
312  vector_[parent]->position = parent;
313  }
314  }
315 
316  void percolateUp(const unsigned int pos)
317  {
318  Element *tmp = vector_[pos];
319  unsigned int child = pos;
320  unsigned int parent = (pos - 1) >> 1;
321 
322  while (child > 0 && lt_(tmp->data, vector_[parent]->data))
323  {
324  vector_[child] = vector_[parent];
325  vector_[child]->position = child;
326  child = parent;
327  parent = (parent - 1) >> 1;
328  }
329  if (child != pos)
330  {
331  vector_[child] = tmp;
332  vector_[child]->position = child;
333  }
334  }
335  };
336 }
337 
338 #endif
void onBeforeRemove(EventBeforeRemove event, void *arg)
Set the event that gets called before a removal.
Definition: BinaryHeap.h:105
_T data
The data of this element.
Definition: BinaryHeap.h:71
void clear()
Clear the heap.
Definition: BinaryHeap.h:112
void rebuild()
Rebuild the heap.
Definition: BinaryHeap.h:180
When an element is added to the heap, an instance of Element* is created. This instance contains the ...
Definition: BinaryHeap.h:59
void(*)(Element *, void *) EventBeforeRemove
Event that gets called just before a removal.
Definition: BinaryHeap.h:78
bool empty() const
Check if the heap is empty.
Definition: BinaryHeap.h:195
void update(Element *element)
Update an element in the heap.
Definition: BinaryHeap.h:186
This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome...
Definition: BinaryHeap.h:52
void buildFrom(const std::vector< _T > &list)
Clear the heap, add the set of elements list to it and rebuild it.
Definition: BinaryHeap.h:170
Main namespace. Contains everything in this library.
Definition: AppBase.h:21
void pop()
Remove the top element.
Definition: BinaryHeap.h:126
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
Definition: BinaryHeap.h:98
void getContent(std::vector< _T > &content) const
Get the data stored in this heap.
Definition: BinaryHeap.h:207
void insert(const std::vector< _T > &list)
Add a set of elements to the heap.
Definition: BinaryHeap.h:154
Element * top() const
Return the top element. nullptr for an empty heap.
Definition: BinaryHeap.h:120
void(*)(Element *, void *) EventAfterInsert
Event that gets called after an insertion.
Definition: BinaryHeap.h:75
LessThan & getComparisonOperator()
Return a reference to the comparison operator.
Definition: BinaryHeap.h:234
unsigned int size() const
Get the number of elements in the heap.
Definition: BinaryHeap.h:201
Element * insert(const _T &data)
Add a new element.
Definition: BinaryHeap.h:140
void sort(std::vector< _T > &list)
Sort an array of elements. This does not affect the content of the heap.
Definition: BinaryHeap.h:214