37 #ifndef OMPL_DATASTRUCTURES_GRID_B_
38 #define OMPL_DATASTRUCTURES_GRID_B_
40 #include "ompl/datastructures/GridN.h"
41 #include "ompl/datastructures/BinaryHeap.h"
48 template <
typename _T,
49 class LessThanExternal = std::less<_T>,
50 class LessThanInternal = LessThanExternal >
69 struct CellX :
public Cell
153 (static_cast<CellX*>(cell)->heapElement));
156 (static_cast<CellX*>(cell)->heapElement));
162 std::vector< Cell* > cells;
164 for (
int i = cells.size() - 1 ; i >= 0 ; --i)
173 CellX* cell =
new CellX();
179 for (
typename CellArray::iterator cl = list->begin() ; cl != list->end() ; ++cl)
181 CellX* c =
static_cast<CellX*
>(*cl);
182 bool wasBorder = c->border;
190 external_.
update(reinterpret_cast<typename externalBHeap::Element*>(c->heapElement));
195 external_.
remove(reinterpret_cast<typename externalBHeap::Element*>(c->heapElement));
199 internal_.
update(reinterpret_cast<typename internalBHeap::Element*>(c->heapElement));
205 cell->border =
false;
210 return static_cast<Cell*
>(cell);
216 CellX* ccell =
static_cast<CellX*
>(cell);
228 virtual bool remove(
Cell* cell)
235 for (
typename CellArray::iterator cl = list->begin() ; cl != list->end() ; ++cl)
237 CellX* c =
static_cast<CellX*
>(*cl);
238 bool wasBorder = c->border;
248 external_.
update(reinterpret_cast<typename externalBHeap::Element*>(c->heapElement));
251 internal_.
remove(reinterpret_cast<typename internalBHeap::Element*>(c->heapElement));
256 internal_.
update(reinterpret_cast<typename internalBHeap::Element*>(c->heapElement));
265 CellX* cx =
static_cast<CellX*
>(cell);
267 external_.
remove(reinterpret_cast<typename externalBHeap::Element*>(cx->heapElement));
269 internal_.
remove(reinterpret_cast<typename internalBHeap::Element*>(cx->heapElement));
282 virtual void status(std::ostream &out = std::cout)
const
321 bool operator()(
const CellX*
const a,
const CellX*
const b)
const
323 return lt_(a->data, b->data);
327 LessThanInternal lt_;
333 bool operator()(
const CellX*
const a,
const CellX*
const b)
const
335 return lt_(a->data, b->data);
338 LessThanExternal lt_;
350 element->data->heapElement =
reinterpret_cast<void*
>(element);
356 element->data->heapElement =
reinterpret_cast<void*
>(element);
virtual void add(Cell *cell)
Add the cell to the grid.
internalBHeap internal_
The heap of interior cells.
GridN< _T >::Coord Coord
Datatype for cell coordinates.
double fracInternal(void) const
Return the fraction of internal cells.
void onCellUpdate(EventCellUpdate event, void *arg)
std::vector< int > Coord
Definition of a coordinate within this grid.
virtual void status(std::ostream &out=std::cout) const
Print information about the data in this grid structure.
void remove(Element *element)
Remove a specific element.
void setupHeaps(void)
Set the update procedure for the heaps of internal and external cells.
void getCells(CellArray &cells) const
Get the set of instantiated cells in the grid.
virtual void status(std::ostream &out=std::cout) const
Print information about the data in this grid structure.
unsigned int size(void) const
Get the number of elements in the heap.
Cell * topExternal(void) const
Return the cell that is at the top of the heap maintaining external cells.
GridN< _T >::Cell Cell
Definition of a cell in this grid.
Cell * topInternal(void) const
Return the cell that is at the top of the heap maintaining internal cells.
void update(Cell *cell)
Update the position in the heaps for a particular cell.
void update(Element *element)
Update an element in the heap.
void clear(void)
Clear the heap.
unsigned int numberOfBoundaryDimensions(const Coord &coord) const
Compute how many sides of a coordinate touch the boundaries of the grid.
unsigned int countExternal(void) const
Return the number of external cells.
Grid< _T >::Coord Coord
Datatype for cell coordinates.
std::vector< Cell * > CellArray
The datatype for arrays of cells.
GridB(unsigned int dimension)
Constructor.
bool empty(void) const
Check if the heap is empty.
virtual void add(Cell *cell)
Add an instantiated cell to the grid.
EventCellUpdate eventCellUpdate_
Pointer to function to be called when a cell needs to be updated.
Define order for internal cells.
Define order for external cells.
BinaryHeap< CellX *, LessThanInternalCell > internalBHeap
Datatype for a heap of cells containing interior cells.
Representation of a grid where cells keep track of how many neighbors they have.
std::vector< Cell * > CellArray
The datatype for arrays of cells.
static void setHeapElementE(typename externalBHeap::Element *element, void *)
Routine used internally for keeping track of binary heap elements for external cells.
void updateAll(void)
Update all cells and reconstruct the heaps.
static void setHeapElementI(typename internalBHeap::Element *element, void *)
Routine used internally for keeping track of binary heap elements for internal cells.
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
BinaryHeap< CellX *, LessThanExternalCell > externalBHeap
Datatype for a heap of cells containing exterior cells.
static void noCellUpdate(Cell *, void *)
Default no-op update routine for a cell.
void * eventCellUpdateData_
Data to be passed to function pointer above.
GridN< _T >::CellArray CellArray
The datatype for arrays of cells.
Element * top(void) const
Return the top element. NULL for an empty heap.
void neighbors(const Cell *cell, CellArray &list) const
Get the list of neighbors for a given cell.
virtual Cell * createCell(const Coord &coord, CellArray *nbh=NULL)
Create a cell but do not add it to the grid; update neighboring cells however.
void rebuild(void)
Rebuild the heap.
unsigned int countInternal(void) const
Return the number of internal cells.
virtual void clear(void)
Clear all cells in the grid.
externalBHeap external_
The heap of external cells.
double fracExternal(void) const
Return the fraction of external cells.
This class defines a grid that keeps track of its boundary: it distinguishes between interior and ext...
iterator end(void) const
Return the end() iterator for the grid.
void clearHeaps(void)
Clear the data from both heaps.
Definition of a cell in this grid.
void(* EventCellUpdate)(Cell *, void *)
Event to be called when a cell's priority is to be updated.
Element * insert(const _T &data)
Add a new element.
virtual void clear(void)
Clear all cells in the grid.