Loading...
Searching...
No Matches
ompl::BinaryHeap< _T, LessThan > Class Template Reference

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 <ompl/datastructures/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

using EventAfterInsert = void (*)(Element *, void *)
 Event that gets called after an insertion.
using EventBeforeRemove = void (*)(Element *, void *)
 Event that gets called just before a removal.

Public Member Functions

 BinaryHeap (LessThan lt)
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 clear ()
 Clear the heap.
Elementtop () const
 Return the top element. nullptr for an empty heap.
void pop ()
 Remove the top element.
void remove (Element *element)
 Remove a specific element.
Elementinsert (const _T &data)
 Add a new element.
void insert (const std::vector< _T > &list)
 Add a set of elements to the 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 update (Element *element)
 Update an element in the heap.
bool empty () const
 Check if the heap is empty.
unsigned int size () const
 Get the number of elements in the heap.
void getContent (std::vector< _T > &content) const
 Get the data stored in this heap.
void sort (std::vector< _T > &list)
 Sort an array of elements. This does not affect the content of the heap.
LessThan & getComparisonOperator ()
 Return a reference to the comparison operator.

Detailed Description

template<typename _T, class LessThan = std::less<_T>>
class ompl::BinaryHeap< _T, LessThan >

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 52 of file BinaryHeap.h.

Member Typedef Documentation

◆ EventAfterInsert

template<typename _T, class LessThan = std::less<_T>>
using ompl::BinaryHeap< _T, LessThan >::EventAfterInsert = void (*)(Element *, void *)

Event that gets called after an insertion.

Definition at line 75 of file BinaryHeap.h.

◆ EventBeforeRemove

template<typename _T, class LessThan = std::less<_T>>
using ompl::BinaryHeap< _T, LessThan >::EventBeforeRemove = void (*)(Element *, void *)

Event that gets called just before a removal.

Definition at line 78 of file BinaryHeap.h.

Constructor & Destructor Documentation

◆ BinaryHeap() [1/2]

template<typename _T, class LessThan = std::less<_T>>
ompl::BinaryHeap< _T, LessThan >::BinaryHeap ( )
inline

Definition at line 80 of file BinaryHeap.h.

◆ BinaryHeap() [2/2]

template<typename _T, class LessThan = std::less<_T>>
ompl::BinaryHeap< _T, LessThan >::BinaryHeap ( LessThan lt)
inline

Definition at line 86 of file BinaryHeap.h.

◆ ~BinaryHeap()

template<typename _T, class LessThan = std::less<_T>>
ompl::BinaryHeap< _T, LessThan >::~BinaryHeap ( )
inline

Definition at line 92 of file BinaryHeap.h.

Member Function Documentation

◆ buildFrom()

template<typename _T, class LessThan = std::less<_T>>
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 170 of file BinaryHeap.h.

◆ clear()

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::clear ( )
inline

Clear the heap.

Definition at line 112 of file BinaryHeap.h.

◆ empty()

template<typename _T, class LessThan = std::less<_T>>
bool ompl::BinaryHeap< _T, LessThan >::empty ( ) const
inline

Check if the heap is empty.

Definition at line 195 of file BinaryHeap.h.

◆ getComparisonOperator()

template<typename _T, class LessThan = std::less<_T>>
LessThan & ompl::BinaryHeap< _T, LessThan >::getComparisonOperator ( )
inline

Return a reference to the comparison operator.

Definition at line 234 of file BinaryHeap.h.

◆ getContent()

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::getContent ( std::vector< _T > & content) const
inline

Get the data stored in this heap.

Definition at line 207 of file BinaryHeap.h.

◆ insert() [1/2]

template<typename _T, class LessThan = std::less<_T>>
Element * ompl::BinaryHeap< _T, LessThan >::insert ( const _T & data)
inline

Add a new element.

Definition at line 140 of file BinaryHeap.h.

◆ insert() [2/2]

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::insert ( const std::vector< _T > & list)
inline

Add a set of elements to the heap.

Definition at line 154 of file BinaryHeap.h.

◆ onAfterInsert()

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::onAfterInsert ( EventAfterInsert event,
void * arg )
inline

Set the event that gets called after insertion.

Definition at line 98 of file BinaryHeap.h.

◆ onBeforeRemove()

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::onBeforeRemove ( EventBeforeRemove event,
void * arg )
inline

Set the event that gets called before a removal.

Definition at line 105 of file BinaryHeap.h.

◆ pop()

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::pop ( )
inline

Remove the top element.

Definition at line 126 of file BinaryHeap.h.

◆ rebuild()

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::rebuild ( )
inline

Rebuild the heap.

Definition at line 180 of file BinaryHeap.h.

◆ remove()

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::remove ( Element * element)
inline

Remove a specific element.

Definition at line 132 of file BinaryHeap.h.

◆ size()

template<typename _T, class LessThan = std::less<_T>>
unsigned int ompl::BinaryHeap< _T, LessThan >::size ( ) const
inline

Get the number of elements in the heap.

Definition at line 201 of file BinaryHeap.h.

◆ sort()

template<typename _T, class LessThan = std::less<_T>>
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 214 of file BinaryHeap.h.

◆ top()

template<typename _T, class LessThan = std::less<_T>>
Element * ompl::BinaryHeap< _T, LessThan >::top ( ) const
inline

Return the top element. nullptr for an empty heap.

Definition at line 120 of file BinaryHeap.h.

◆ update()

template<typename _T, class LessThan = std::less<_T>>
void ompl::BinaryHeap< _T, LessThan >::update ( Element * element)
inline

Update an element in the heap.

Definition at line 186 of file BinaryHeap.h.


The documentation for this class was generated from the following file: