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 <vector>
42 #include <cassert>
43 
44 namespace ompl
45 {
50  template <typename _T, class LessThan = std::less<_T>>
51  class BinaryHeap
52  {
53  public:
58  class Element
59  {
60  friend class BinaryHeap;
61 
62  private:
63  Element() = default;
64  ~Element() = default;
66  unsigned int position;
67 
68  public:
70  _T data;
71  };
72 
74  using EventAfterInsert = void (*)(Element *, void *);
75 
77  using EventBeforeRemove = void (*)(Element *, void *);
78 
79  BinaryHeap()
80  {
81  eventAfterInsert_ = nullptr;
82  eventBeforeRemove_ = nullptr;
83  }
84 
85  BinaryHeap(const LessThan &lt) : lt_(lt)
86  {
87  eventAfterInsert_ = nullptr;
88  eventBeforeRemove_ = nullptr;
89  }
90 
91  ~BinaryHeap()
92  {
93  clear();
94  }
95 
97  void onAfterInsert(EventAfterInsert event, void *arg)
98  {
99  eventAfterInsert_ = event;
100  eventAfterInsertData_ = arg;
101  }
102 
104  void onBeforeRemove(EventBeforeRemove event, void *arg)
105  {
106  eventBeforeRemove_ = event;
107  eventBeforeRemoveData_ = arg;
108  }
109 
111  void clear()
112  {
113  for (auto i = vector_.begin(); i != vector_.end(); ++i)
114  delete *i;
115  vector_.clear();
116  }
117 
119  Element *top() const
120  {
121  return vector_.empty() ? nullptr : vector_.at(0);
122  }
123 
125  void pop()
126  {
127  removePos(0);
128  }
129 
131  void remove(Element *element)
132  {
133  if (eventBeforeRemove_)
134  eventBeforeRemove_(element, eventBeforeRemoveData_);
135  removePos(element->position);
136  }
137 
139  Element *insert(const _T &data)
140  {
141  auto *element = new Element();
142  element->data = data;
143  const unsigned int pos = vector_.size();
144  element->position = pos;
145  vector_.push_back(element);
146  percolateUp(pos);
147  if (eventAfterInsert_)
148  eventAfterInsert_(element, eventAfterInsertData_);
149  return element;
150  }
151 
153  void insert(const std::vector<_T> &list)
154  {
155  const unsigned int n = vector_.size();
156  const unsigned int m = list.size();
157  for (unsigned int i = 0; i < m; ++i)
158  {
159  const unsigned int pos = i + n;
160  Element *element = newElement(list[i], pos);
161  vector_.push_back(element);
162  percolateUp(pos);
163  if (eventAfterInsert_)
164  eventAfterInsert_(element, eventAfterInsertData_);
165  }
166  }
167 
169  void buildFrom(const std::vector<_T> &list)
170  {
171  clear();
172  const unsigned int m = list.size();
173  for (unsigned int i = 0; i < m; ++i)
174  vector_.push_back(newElement(list[i], i));
175  build();
176  }
177 
179  void rebuild()
180  {
181  build();
182  }
183 
185  void update(Element *element)
186  {
187  const unsigned int pos = element->position;
188  assert(vector_[pos] == element);
189  percolateUp(pos);
190  percolateDown(pos);
191  }
192 
194  bool empty() const
195  {
196  return vector_.empty();
197  }
198 
200  unsigned int size() const
201  {
202  return vector_.size();
203  }
204 
206  void getContent(std::vector<_T> &content) const
207  {
208  for (auto i = vector_.begin(); i != vector_.end(); ++i)
209  content.push_back((*i)->data);
210  }
211 
213  void sort(std::vector<_T> &list)
214  {
215  const unsigned int n = list.size();
216  std::vector<Element *> backup = vector_;
217  vector_.clear();
218  for (unsigned int i = 0; i < n; ++i)
219  vector_.push_back(newElement(list[i], i));
220  build();
221  list.clear();
222  list.reserve(n);
223 
224  for (unsigned int i = 0; i < n; ++i)
225  {
226  list.push_back(vector_[0]->data);
227  removePos(0);
228  }
229  vector_ = backup;
230  }
231 
234  {
235  return lt_;
236  }
237 
238  private:
239  LessThan lt_;
240 
241  std::vector<Element *> vector_;
242 
243  EventAfterInsert eventAfterInsert_;
244  void *eventAfterInsertData_;
245  EventBeforeRemove eventBeforeRemove_;
246  void *eventBeforeRemoveData_;
247 
248  void removePos(unsigned int pos)
249  {
250  const int n = vector_.size() - 1;
251  delete vector_[pos];
252  if ((int)pos < n)
253  {
254  vector_[pos] = vector_.back();
255  vector_[pos]->position = pos;
256  vector_.pop_back();
257  percolateDown(pos);
258  }
259  else
260  vector_.pop_back();
261  }
262 
263  Element *newElement(_T &data, unsigned int pos) const
264  {
265  auto *element = new Element();
266  element->data = data;
267  element->position = pos;
268  return element;
269  }
270 
271  void build()
272  {
273  for (int i = vector_.size() / 2 - 1; i >= 0; --i)
274  percolateDown(i);
275  }
276 
277  void percolateDown(const unsigned int pos)
278  {
279  const unsigned int n = vector_.size();
280  Element *tmp = vector_[pos];
281  unsigned int parent = pos;
282  unsigned int child = (pos + 1) << 1;
283 
284  while (child < n)
285  {
286  if (lt_(vector_[child - 1]->data, vector_[child]->data))
287  --child;
288  if (lt_(vector_[child]->data, tmp->data))
289  {
290  vector_[parent] = vector_[child];
291  vector_[parent]->position = parent;
292  }
293  else
294  break;
295  parent = child;
296  child = (child + 1) << 1;
297  }
298  if (child == n)
299  {
300  --child;
301  if (lt_(vector_[child]->data, tmp->data))
302  {
303  vector_[parent] = vector_[child];
304  vector_[parent]->position = parent;
305  parent = child;
306  }
307  }
308  if (parent != pos)
309  {
310  vector_[parent] = tmp;
311  vector_[parent]->position = parent;
312  }
313  }
314 
315  void percolateUp(const unsigned int pos)
316  {
317  Element *tmp = vector_[pos];
318  unsigned int child = pos;
319  unsigned int parent = (pos - 1) >> 1;
320 
321  while (child > 0 && lt_(tmp->data, vector_[parent]->data))
322  {
323  vector_[child] = vector_[parent];
324  vector_[child]->position = child;
325  child = parent;
326  parent = (parent - 1) >> 1;
327  }
328  if (child != pos)
329  {
330  vector_[child] = tmp;
331  vector_[child]->position = child;
332  }
333  }
334  };
335 }
336 
337 #endif
void onBeforeRemove(EventBeforeRemove event, void *arg)
Set the event that gets called before a removal.
Definition: BinaryHeap.h:104
_T data
The data of this element.
Definition: BinaryHeap.h:70
void clear()
Clear the heap.
Definition: BinaryHeap.h:111
void rebuild()
Rebuild the heap.
Definition: BinaryHeap.h:179
When an element is added to the heap, an instance of Element* is created. This instance contains the ...
Definition: BinaryHeap.h:58
void(*)(Element *, void *) EventBeforeRemove
Event that gets called just before a removal.
Definition: BinaryHeap.h:77
bool empty() const
Check if the heap is empty.
Definition: BinaryHeap.h:194
void update(Element *element)
Update an element in the heap.
Definition: BinaryHeap.h:185
This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome...
Definition: BinaryHeap.h:51
void buildFrom(const std::vector< _T > &list)
Clear the heap, add the set of elements list to it and rebuild it.
Definition: BinaryHeap.h:169
Main namespace. Contains everything in this library.
Definition: AppBase.h:21
void pop()
Remove the top element.
Definition: BinaryHeap.h:125
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
Definition: BinaryHeap.h:97
void getContent(std::vector< _T > &content) const
Get the data stored in this heap.
Definition: BinaryHeap.h:206
void insert(const std::vector< _T > &list)
Add a set of elements to the heap.
Definition: BinaryHeap.h:153
Element * top() const
Return the top element. nullptr for an empty heap.
Definition: BinaryHeap.h:119
void(*)(Element *, void *) EventAfterInsert
Event that gets called after an insertion.
Definition: BinaryHeap.h:74
LessThan & getComparisonOperator()
Return a reference to the comparison operator.
Definition: BinaryHeap.h:233
unsigned int size() const
Get the number of elements in the heap.
Definition: BinaryHeap.h:200
Element * insert(const _T &data)
Add a new element.
Definition: BinaryHeap.h:139
void sort(std::vector< _T > &list)
Sort an array of elements. This does not affect the content of the heap.
Definition: BinaryHeap.h:213