37 #ifndef OMPL_DATASTRUCTURES_GRID_B_ 38 #define OMPL_DATASTRUCTURES_GRID_B_ 40 #include "ompl/datastructures/GridN.h" 41 #include "ompl/datastructures/BinaryHeap.h" 47 template <
typename _T,
class LessThanExternal = std::less<_T>,
class LessThanInternal = LessThanExternal>
64 struct CellX :
public Cell 70 ~CellX()
override =
default;
82 explicit GridB(
unsigned int dimension) :
GridN<_T>(dimension)
144 reinterpret_cast<typename externalBHeap::Element *>(static_cast<CellX *>(cell)->heapElement));
147 reinterpret_cast<typename internalBHeap::Element *>(static_cast<CellX *>(cell)->heapElement));
153 std::vector<Cell *> cells;
155 for (
int i = cells.size() - 1; i >= 0; --i)
164 auto *cell =
new CellX();
170 for (
auto cl = list->begin(); cl != list->end(); ++cl)
172 auto *c =
static_cast<CellX *
>(*cl);
173 bool wasBorder = c->border;
181 external_.
update(reinterpret_cast<typename externalBHeap::Element *>(c->heapElement));
186 external_.
remove(reinterpret_cast<typename externalBHeap::Element *>(c->heapElement));
190 internal_.
update(reinterpret_cast<typename internalBHeap::Element *>(c->heapElement));
196 cell->border =
false;
201 return static_cast<Cell *
>(cell);
207 auto *ccell =
static_cast<CellX *
>(cell);
219 virtual bool remove(
Cell *cell)
226 for (
auto cl = list->begin(); cl != list->end(); ++cl)
228 auto *c =
static_cast<CellX *
>(*cl);
229 bool wasBorder = c->border;
239 external_.
update(reinterpret_cast<typename externalBHeap::Element *>(c->heapElement));
242 internal_.
remove(reinterpret_cast<typename internalBHeap::Element *>(c->heapElement));
247 internal_.
update(reinterpret_cast<typename internalBHeap::Element *>(c->heapElement));
256 auto *cx =
static_cast<CellX *
>(cell);
258 external_.
remove(reinterpret_cast<typename externalBHeap::Element *>(cx->heapElement));
260 internal_.
remove(reinterpret_cast<typename internalBHeap::Element *>(cx->heapElement));
273 void status(std::ostream &out = std::cout)
const override 311 bool operator()(
const CellX *
const a,
const CellX *
const b)
const 313 return lt_(a->data, b->data);
317 LessThanInternal lt_;
323 bool operator()(
const CellX *
const a,
const CellX *
const b)
const 325 return lt_(a->data, b->data);
329 LessThanExternal lt_;
341 element->data->heapElement =
reinterpret_cast<void *
>(element);
347 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.
typename GridN< _T >::CellArray CellArray
The datatype for arrays of cells.
unsigned int countInternal() const
Return the number of internal cells.
void updateAll()
Update all cells and reconstruct the heaps.
double fracExternal() const
Return the fraction of external cells.
void clear()
Clear the heap.
virtual void clear()
Clear all cells in the grid.
void onCellUpdate(EventCellUpdate event, void *arg)
void rebuild()
Rebuild the heap.
typename GridN< _T >::Cell Cell
Definition of a cell in this grid.
void neighbors(const Cell *cell, CellArray &list) const
Get the list of neighbors for a given cell.
void remove(Element *element)
Remove a specific element.
std::vector< int > Coord
Definition of a coordinate within this grid.
void update(Cell *cell)
Update the position in the heaps for a particular cell.
bool empty() const
Check if the heap is empty.
void update(Element *element)
Update an element in the heap.
Main namespace. Contains everything in this library.
void(*)(Cell *, void *) EventCellUpdate
Event to be called when a cell's priority is to be updated.
virtual void status(std::ostream &out=std::cout) const
Print information about the data in this grid structure.
GridB(unsigned int dimension)
Constructor.
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.
Representation of a grid where cells keep track of how many neighbors they have.
Cell * topExternal() const
Return the cell that is at the top of the heap maintaining external cells.
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.
double fracInternal() const
Return the fraction of internal cells.
static void setHeapElementI(typename internalBHeap::Element *element, void *)
Routine used internally for keeping track of binary heap elements for internal cells.
typename Grid< _T >::Coord Coord
Datatype for cell coordinates.
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
static void noCellUpdate(Cell *, void *)
Default no-op update routine for a cell.
void * eventCellUpdateData_
Data to be passed to function pointer above.
Element * top() const
Return the top element. nullptr for an empty heap.
iterator end() const
Return the end() iterator for the grid.
unsigned int countExternal() const
Return the number of external cells.
void getCells(CellArray &cells) const
Get the set of instantiated cells in the grid.
void setupHeaps()
Set the update procedure for the heaps of internal and external cells.
externalBHeap external_
The heap of external cells.
Cell * topInternal() const
Return the cell that is at the top of the heap maintaining internal cells.
This class defines a grid that keeps track of its boundary: it distinguishes between interior and ext...
void clear() override
Clear all cells in the grid.
Definition of a cell in this grid.
void status(std::ostream &out=std::cout) const override
Print information about the data in this grid structure.
unsigned int size() const
Get the number of elements in the heap.
unsigned int numberOfBoundaryDimensions(const Coord &coord) const
Compute how many sides of a coordinate touch the boundaries of the grid.
void clearHeaps()
Clear the data from both heaps.
Element * insert(const _T &data)
Add a new element.
std::vector< Cell * > CellArray
The datatype for arrays of cells.
virtual Cell * createCell(const Coord &coord, CellArray *nbh=nullptr)
Create a cell but do not add it to the grid; update neighboring cells however.