This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome, as it requires keeping track of the BinaryHeap::Element* type, however, it should be as fast as it gets with an updatable heap. More...
#include <BinaryHeap.h>
Classes | |
| class | Element |
| When an element is added to the heap, an instance of Element* is created. This instance contains the data that was added and internal information about the position of the data in the heap's internal storage. More... | |
Public Types | |
| typedef void(* | EventAfterInsert )(Element *, void *) |
| Event that gets called after an insertion. | |
| typedef void(* | EventBeforeRemove )(Element *, void *) |
| Event that gets called just before a removal. | |
Public Member Functions | |
| BinaryHeap (void) | |
| void | buildFrom (const std::vector< _T > &list) |
| Clear the heap, add the set of elements list to it and rebuild it. | |
| void | clear (void) |
| Clear the heap. | |
| bool | empty (void) const |
| Check if the heap is empty. | |
| 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 * | insert (const _T &data) |
| Add a new element. | |
| void | onAfterInsert (EventAfterInsert event, void *arg) |
| Set the event that gets called after insertion. | |
| void | onBeforeRemove (EventBeforeRemove event, void *arg) |
| Set the event that gets called before a removal. | |
| void | pop (void) |
| Remove the top element. | |
| void | rebuild (void) |
| Rebuild the heap. | |
| void | remove (Element *element) |
| Remove a specific element. | |
| unsigned int | size (void) const |
| Get the number of elements in the heap. | |
| void | sort (std::vector< _T > &list) |
| Sort an array of elements. This does not affect the content of the heap. | |
| Element * | top (void) const |
| Return the top element. NULL for an empty heap. | |
| void | update (Element *element) |
| Update an element in the heap. | |
| ~BinaryHeap (void) | |
Private Member Functions | |
| void | build (void) |
| Element * | newElement (_T &data, unsigned int pos) const |
| void | percolateDown (const unsigned int pos) |
| void | percolateUp (const unsigned int pos) |
| void | removePos (unsigned int pos) |
Private Attributes | |
| EventAfterInsert | eventAfterInsert_ |
| void * | eventAfterInsertData_ |
| EventBeforeRemove | eventBeforeRemove_ |
| void * | eventBeforeRemoveData_ |
| LessThan | lt_ |
| std::vector< Element * > | vector_ |
This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome, as it requires keeping track of the BinaryHeap::Element* type, however, it should be as fast as it gets with an updatable heap.
Definition at line 53 of file BinaryHeap.h.
| typedef void(* ompl::BinaryHeap< _T, LessThan >::EventAfterInsert)(Element *, void *) |
Event that gets called after an insertion.
Definition at line 73 of file BinaryHeap.h.
| typedef void(* ompl::BinaryHeap< _T, LessThan >::EventBeforeRemove)(Element *, void *) |
Event that gets called just before a removal.
Definition at line 76 of file BinaryHeap.h.
| ompl::BinaryHeap< _T, LessThan >::BinaryHeap | ( | void | ) | [inline] |
Definition at line 78 of file BinaryHeap.h.
| ompl::BinaryHeap< _T, LessThan >::~BinaryHeap | ( | void | ) | [inline] |
Definition at line 84 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::build | ( | void | ) | [inline, private] |
Definition at line 261 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::buildFrom | ( | const std::vector< _T > & | list | ) | [inline] |
Clear the heap, add the set of elements list to it and rebuild it.
Definition at line 163 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::clear | ( | void | ) | [inline] |
Clear the heap.
Definition at line 104 of file BinaryHeap.h.
| bool ompl::BinaryHeap< _T, LessThan >::empty | ( | void | ) | const [inline] |
Check if the heap is empty.
Definition at line 188 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::getContent | ( | std::vector< _T > & | content | ) | const [inline] |
Get the data stored in this heap.
Definition at line 200 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::insert | ( | const std::vector< _T > & | list | ) | [inline] |
Add a set of elements to the heap.
Definition at line 147 of file BinaryHeap.h.
| Element* ompl::BinaryHeap< _T, LessThan >::insert | ( | const _T & | data | ) | [inline] |
Add a new element.
Definition at line 133 of file BinaryHeap.h.
| Element* ompl::BinaryHeap< _T, LessThan >::newElement | ( | _T & | data, | |
| unsigned int | pos | |||
| ) | const [inline, private] |
Definition at line 253 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::onAfterInsert | ( | EventAfterInsert | event, | |
| void * | arg | |||
| ) | [inline] |
Set the event that gets called after insertion.
Definition at line 90 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::onBeforeRemove | ( | EventBeforeRemove | event, | |
| void * | arg | |||
| ) | [inline] |
Set the event that gets called before a removal.
Definition at line 97 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::percolateDown | ( | const unsigned int | pos | ) | [inline, private] |
Definition at line 267 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::percolateUp | ( | const unsigned int | pos | ) | [inline, private] |
Definition at line 304 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::pop | ( | void | ) | [inline] |
Remove the top element.
Definition at line 119 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::rebuild | ( | void | ) | [inline] |
Rebuild the heap.
Definition at line 173 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::remove | ( | Element * | element | ) | [inline] |
Remove a specific element.
Definition at line 125 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::removePos | ( | unsigned int | pos | ) | [inline, private] |
Definition at line 238 of file BinaryHeap.h.
| unsigned int ompl::BinaryHeap< _T, LessThan >::size | ( | void | ) | const [inline] |
Get the number of elements in the heap.
Definition at line 194 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::sort | ( | std::vector< _T > & | list | ) | [inline] |
Sort an array of elements. This does not affect the content of the heap.
Definition at line 208 of file BinaryHeap.h.
| Element* ompl::BinaryHeap< _T, LessThan >::top | ( | void | ) | const [inline] |
Return the top element. NULL for an empty heap.
Definition at line 113 of file BinaryHeap.h.
| void ompl::BinaryHeap< _T, LessThan >::update | ( | Element * | element | ) | [inline] |
Update an element in the heap.
Definition at line 179 of file BinaryHeap.h.
EventAfterInsert ompl::BinaryHeap< _T, LessThan >::eventAfterInsert_ [private] |
Definition at line 233 of file BinaryHeap.h.
void* ompl::BinaryHeap< _T, LessThan >::eventAfterInsertData_ [private] |
Definition at line 234 of file BinaryHeap.h.
EventBeforeRemove ompl::BinaryHeap< _T, LessThan >::eventBeforeRemove_ [private] |
Definition at line 235 of file BinaryHeap.h.
void* ompl::BinaryHeap< _T, LessThan >::eventBeforeRemoveData_ [private] |
Definition at line 236 of file BinaryHeap.h.
LessThan ompl::BinaryHeap< _T, LessThan >::lt_ [private] |
Definition at line 229 of file BinaryHeap.h.
std::vector<Element*> ompl::BinaryHeap< _T, LessThan >::vector_ [private] |
Definition at line 231 of file BinaryHeap.h.
