Loading...
Searching...
No Matches
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
45namespace ompl
46{
51 template <typename _T, class LessThan = std::less<_T>>
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
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 &element : vector_)
115 delete element;
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 &element : vector_)
210 content.push_back(element->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(const _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
When an element is added to the heap, an instance of Element* is created. This instance contains the ...
Definition BinaryHeap.h:60
_T data
The data of this element.
Definition BinaryHeap.h:71
This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome,...
Definition BinaryHeap.h:53
void(*)(Element *, void *) EventBeforeRemove
Event that gets called just before a removal.
Definition BinaryHeap.h:78
Element * insert(const _T &data)
Add a new element.
Definition BinaryHeap.h:140
void pop()
Remove the top element.
Definition BinaryHeap.h:126
void insert(const std::vector< _T > &list)
Add a set of elements to the heap.
Definition BinaryHeap.h:154
bool empty() const
Check if the heap is empty.
Definition BinaryHeap.h:195
void remove(Element *element)
Remove a specific element.
Definition BinaryHeap.h:132
void onBeforeRemove(EventBeforeRemove event, void *arg)
Set the event that gets called before a removal.
Definition BinaryHeap.h:105
void update(Element *element)
Update an element in the heap.
Definition BinaryHeap.h:186
void getContent(std::vector< _T > &content) const
Get the data stored in this heap.
Definition BinaryHeap.h:207
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
void rebuild()
Rebuild the heap.
Definition BinaryHeap.h:180
void sort(std::vector< _T > &list)
Sort an array of elements. This does not affect the content of the heap.
Definition BinaryHeap.h:214
Element * top() const
Return the top element. nullptr for an empty heap.
Definition BinaryHeap.h:120
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
Definition BinaryHeap.h:98
void clear()
Clear the heap.
Definition BinaryHeap.h:112
void(*)(Element *, void *) EventAfterInsert
Event that gets called after an insertion.
Definition BinaryHeap.h:75
unsigned int size() const
Get the number of elements in the heap.
Definition BinaryHeap.h:201
LessThan & getComparisonOperator()
Return a reference to the comparison operator.
Definition BinaryHeap.h:234
Main namespace. Contains everything in this library.
STL namespace.