37 #ifndef OMPL_DATASTRUCTURES_BINARY_HEAP_
38 #define OMPL_DATASTRUCTURES_BINARY_HEAP_
51 template <
typename _T,
class LessThan = std::less<_T>>
67 unsigned int position;
82 eventAfterInsert_ =
nullptr;
83 eventBeforeRemove_ =
nullptr;
88 eventAfterInsert_ =
nullptr;
89 eventBeforeRemove_ =
nullptr;
100 eventAfterInsert_ = event;
101 eventAfterInsertData_ = arg;
107 eventBeforeRemove_ = event;
108 eventBeforeRemoveData_ = arg;
114 for (
auto &element : vector_)
122 return vector_.empty() ? nullptr : vector_.at(0);
134 if (eventBeforeRemove_)
135 eventBeforeRemove_(element, eventBeforeRemoveData_);
136 removePos(element->position);
143 element->data = data;
144 const unsigned int pos = vector_.size();
145 element->position = pos;
146 vector_.push_back(element);
148 if (eventAfterInsert_)
149 eventAfterInsert_(element, eventAfterInsertData_);
156 const unsigned int n = vector_.size();
157 const unsigned int m = list.size();
158 for (
unsigned int i = 0; i < m; ++i)
160 const unsigned int pos = i + n;
161 Element *element = newElement(list[i], pos);
162 vector_.push_back(element);
164 if (eventAfterInsert_)
165 eventAfterInsert_(element, eventAfterInsertData_);
173 const unsigned int m = list.size();
174 for (
unsigned int i = 0; i < m; ++i)
175 vector_.push_back(newElement(list[i], i));
188 const unsigned int pos = element->position;
189 assert(vector_[pos] == element);
197 return vector_.empty();
203 return vector_.size();
209 for (
auto &element : vector_)
210 content.push_back(element->data);
214 void sort(std::vector<_T> &list)
216 const unsigned int n = list.size();
217 std::vector<Element *> backup = vector_;
219 for (
unsigned int i = 0; i < n; ++i)
220 vector_.push_back(newElement(list[i], i));
225 for (
unsigned int i = 0; i < n; ++i)
227 list.push_back(vector_[0]->data);
242 std::vector<Element *> vector_;
245 void *eventAfterInsertData_;
247 void *eventBeforeRemoveData_;
249 void removePos(
unsigned int pos)
251 const int n = vector_.size() - 1;
255 vector_[pos] = vector_.back();
256 vector_[pos]->position = pos;
264 Element *newElement(
const _T &data,
unsigned int pos)
const
266 auto *element =
new Element();
267 element->data = data;
268 element->position = pos;
274 for (
int i = vector_.size() / 2 - 1; i >= 0; --i)
278 void percolateDown(
const unsigned int pos)
280 const unsigned int n = vector_.size();
281 Element *tmp = vector_[pos];
282 unsigned int parent = pos;
283 unsigned int child = (pos + 1) << 1;
287 if (lt_(vector_[child - 1]->data, vector_[child]->data))
289 if (lt_(vector_[child]->data, tmp->data))
291 vector_[parent] = vector_[child];
292 vector_[parent]->position = parent;
297 child = (child + 1) << 1;
302 if (lt_(vector_[child]->data, tmp->data))
304 vector_[parent] = vector_[child];
305 vector_[parent]->position = parent;
311 vector_[parent] = tmp;
312 vector_[parent]->position = parent;
316 void percolateUp(
const unsigned int pos)
318 Element *tmp = vector_[pos];
319 unsigned int child = pos;
320 unsigned int parent = (pos - 1) >> 1;
322 while (child > 0 && lt_(tmp->data, vector_[parent]->data))
324 vector_[child] = vector_[parent];
325 vector_[child]->position = child;
327 parent = (parent - 1) >> 1;
331 vector_[child] = tmp;
332 vector_[child]->position = child;
When an element is added to the heap, an instance of Element* is created. This instance contains the ...
_T data
The data of this element.
This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome,...
void(*)(Element *, void *) EventBeforeRemove
Event that gets called just before a removal.
void pop()
Remove the top element.
void insert(const std::vector< _T > &list)
Add a set of elements to the heap.
bool empty() const
Check if the heap is empty.
void remove(Element *element)
Remove a specific element.
void onBeforeRemove(EventBeforeRemove event, void *arg)
Set the event that gets called before a removal.
Element * top() const
Return the top element. nullptr for an empty heap.
Element * insert(const _T &data)
Add a new element.
void update(Element *element)
Update an element in the heap.
LessThan & getComparisonOperator()
Return a reference to the comparison operator.
void getContent(std::vector< _T > &content) const
Get the data stored in this heap.
void buildFrom(const std::vector< _T > &list)
Clear the heap, add the set of elements list to it and rebuild it.
void rebuild()
Rebuild the heap.
void sort(std::vector< _T > &list)
Sort an array of elements. This does not affect the content of the heap.
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
void clear()
Clear the heap.
void(*)(Element *, void *) EventAfterInsert
Event that gets called after an insertion.
unsigned int size() const
Get the number of elements in the heap.
Main namespace. Contains everything in this library.