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 ...
bool empty() const
Check if the heap is empty.
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.
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. NULL for an empty heap.
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(* 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.