37 #ifndef OMPL_DATASTRUCTURES_BINARY_HEAP_
38 #define OMPL_DATASTRUCTURES_BINARY_HEAP_
51 template <
typename _T,
52 class LessThan = std::less<_T> >
68 unsigned int position;
82 eventAfterInsert_ = NULL;
83 eventBeforeRemove_ = NULL;
94 eventAfterInsert_ = event;
95 eventAfterInsertData_ = arg;
101 eventBeforeRemove_ = event;
102 eventBeforeRemoveData_ = arg;
108 for (
typename std::vector<Element*>::iterator i = vector_.begin() ;
109 i != vector_.end() ; ++i)
117 return vector_.empty() ? NULL : vector_.at(0);
127 void remove(Element *element)
129 if (eventBeforeRemove_)
130 eventBeforeRemove_(element, eventBeforeRemoveData_);
131 removePos(element->position);
137 Element *element =
new Element();
138 element->data = data;
139 const unsigned int pos = vector_.size();
140 element->position = pos;
141 vector_.push_back(element);
143 if (eventAfterInsert_)
144 eventAfterInsert_(element, eventAfterInsertData_);
151 const unsigned int n = vector_.size();
152 const unsigned int m = list.size();
153 for (
unsigned int i = 0 ; i < m ; ++i)
155 const unsigned int pos = i + n;
156 Element *element = newElement(list[i], pos);
157 vector_.push_back(element);
159 if (eventAfterInsert_)
160 eventAfterInsert_(element, eventAfterInsertData_);
168 const unsigned int m = list.size();
169 for (
unsigned int i = 0 ; i < m ; ++i)
170 vector_.push_back(newElement(list[i], i));
183 const unsigned int pos = element->position;
184 assert(vector_[pos] == element);
192 return vector_.empty();
198 return vector_.size();
204 for (
typename std::vector<Element*>::const_iterator i = vector_.begin();
205 i != vector_.end() ; ++i)
206 content.push_back((*i)->data);
210 void sort(std::vector<_T>& list)
212 const unsigned int n = list.size();
213 std::vector<Element*> backup = vector_;
215 for (
unsigned int i = 0 ; i < n ; ++i)
216 vector_.push_back(newElement(list[i], i));
221 for (
unsigned int i = 0 ; i < n ; ++i)
223 list.push_back(vector_[0]->data);
239 std::vector<Element*> vector_;
242 void *eventAfterInsertData_;
244 void *eventBeforeRemoveData_;
246 void removePos(
unsigned int pos)
248 const int n = vector_.size() - 1;
252 vector_[pos] = vector_.back();
253 vector_[pos]->position = pos;
261 Element* newElement(_T& data,
unsigned int pos)
const
263 Element *element =
new Element();
264 element->data = data;
265 element->position = pos;
271 for(
int i = vector_.size() / 2 - 1; i >= 0; --i)
275 void percolateDown(
const unsigned int pos)
277 const unsigned int n = vector_.size();
278 Element *tmp = vector_[pos];
279 unsigned int parent = pos;
280 unsigned int child = (pos + 1) << 1;
284 if (lt_(vector_[child - 1]->data, vector_[child]->data)) --child;
285 if (lt_(vector_[child]->data, tmp->data))
287 vector_[parent] = vector_[child];
288 vector_[parent]->position = parent;
293 child = (child + 1) << 1;
298 if (lt_(vector_[child]->data, tmp->data))
300 vector_[parent] = vector_[child];
301 vector_[parent]->position = parent;
307 vector_[parent] = tmp;
308 vector_[parent]->position = parent;
312 void percolateUp(
const unsigned int pos)
314 Element *tmp = vector_[pos];
315 unsigned int child = pos;
316 unsigned int parent = (pos - 1) >> 1;
318 while (child > 0 && lt_(tmp->data, vector_[parent]->data))
320 vector_[child] = vector_[parent];
321 vector_[child]->position = child;
323 parent = (parent - 1) >> 1;
327 vector_[child] = tmp;
328 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 getContent(std::vector< _T > &content) const
Get the data stored in this heap.
void update(Element *element)
Update an element in the heap.
void(* EventBeforeRemove)(Element *, void *)
Event that gets called just before a removal.
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.
Element * top() const
Return the top element. NULL for an empty heap.
bool empty() const
Check if the heap is empty.
void pop()
Remove the top element.
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
void insert(const std::vector< _T > &list)
Add a set of elements to the heap.
unsigned int size() const
Get the number of elements in the heap.
LessThan & getComparisonOperator()
Return a reference to the comparison operator.
Element * insert(const _T &data)
Add a new element.
void(* EventAfterInsert)(Element *, void *)
Event that gets called after an insertion.
void sort(std::vector< _T > &list)
Sort an array of elements. This does not affect the content of the heap.