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 i = vector_.begin(); i != vector_.end(); ++i)
122 return vector_.empty() ? nullptr : vector_.at(0);
132 void remove(Element *element)
134 if (eventBeforeRemove_)
135 eventBeforeRemove_(element, eventBeforeRemoveData_);
136 removePos(element->position);
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);
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 i = vector_.begin(); i != vector_.end(); ++i)
210 content.push_back((*i)->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(_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;
void onBeforeRemove(EventBeforeRemove event, void *arg)
Set the event that gets called before a removal.
_T data
The data of this element.
void clear()
Clear the heap.
void rebuild()
Rebuild the heap.
When an element is added to the heap, an instance of Element* is created. This instance contains the ...
void(*)(Element *, void *) EventBeforeRemove
Event that gets called just before a removal.
bool empty() const
Check if the heap is empty.
void update(Element *element)
Update an element in the heap.
This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome...
void buildFrom(const std::vector< _T > &list)
Clear the heap, add the set of elements list to it and rebuild it.
Main namespace. Contains everything in this library.
void pop()
Remove the top element.
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
void getContent(std::vector< _T > &content) const
Get the data stored in this heap.
void insert(const std::vector< _T > &list)
Add a set of elements to the heap.
Element * top() const
Return the top element. nullptr for an empty heap.
void(*)(Element *, void *) EventAfterInsert
Event that gets called after an insertion.
LessThan & getComparisonOperator()
Return a reference to the comparison operator.
unsigned int size() const
Get the number of elements in the heap.
Element * insert(const _T &data)
Add a new element.
void sort(std::vector< _T > &list)
Sort an array of elements. This does not affect the content of the heap.