& v, bool shrink = true) {
for (int i = 0; i < v.size(); ++i) {
remove(v[i], shrink);
}
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
class Iterator {
private:
friend class ThisType;
bool m_isEnd;
const ThisType* m_grid;
typename CellTable::Iterator m_tableIterator;
/** Index within m_tableIterator->value of the current value. */
int m_arrayIndex;
const int m_epoch;
/** End iterator. Note that the m_tableIterator is initialized to the end iterator
of a temporary value! This is ok because we'll never look at the value of the
m_tableIterator, since we're initializing the "end" Iterator.*/
Iterator() : m_isEnd(true), m_grid(NULL), m_tableIterator(CellTable().end()),
m_arrayIndex(0), m_epoch(0) {}
Iterator(const ThisType* grid) :
m_isEnd(grid->size() == 0),
m_grid(grid),
m_tableIterator( grid->m_data.begin() ),
m_arrayIndex(0),
m_epoch(grid->m_epoch) { }
private:
const Value& value() const {
debugAssert(! m_isEnd);
debugAssertM(m_tableIterator->value.size() > m_arrayIndex,
"No more elements");
return m_tableIterator->value[m_arrayIndex].value;
}
public:
inline bool operator!=(const Iterator& other) const {
if (other.m_isEnd && m_isEnd) {
return false;
} else {
return (m_isEnd != other.m_isEnd) ||
(m_tableIterator != other.m_tableIterator) ||
(m_arrayIndex != other.m_arrayIndex);
}
}
bool isValid() const {
return ! m_isEnd;
}
/** @deprecated Use isValid */
bool hasMore() const {
return ! m_isEnd;
}
bool operator==(const Iterator& other) const {
return !(*this != other);
}
/** Preincrement */
Iterator& operator++() {
debugAssert(! m_isEnd);
debugAssertM(m_epoch == m_grid->m_epoch,
"It is illegal to mutate the HashGrid "
"while iterating through it.");
++m_arrayIndex;
if (m_arrayIndex >= m_tableIterator->value.size()) {
// Move on to the next cell
++m_tableIterator;
m_arrayIndex = 0;
// Check to see if we're at the end
m_isEnd = (m_tableIterator == m_grid->m_data.end());
}
return *this;
}
/** Post increment (slower) */
Iterator operator++(int) {
debugAssert(! m_isEnd);
Iterator old = *this;
++(*this);
return old;
}
const Value& operator*() const { return value(); }
const Value* operator->() const { return &value(); }
operator Value*() const { return &value(); }
}; // Iterator
/** Iterate through all members. It is an error to mutate the HashGrid
while iterating through it. Each member can be accessed by "dereferencing"
the iterator:
for (Grid::Iterator i = grid.begin(); i != grid.end(), ++i) {
const Value& = *i;
...
}
*/
Iterator begin() const {
return Iterator(this);
}
const Iterator& end() const {
static const Iterator it;
return it;
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
// Forward declaration required by older gcc versions for friend declaration in BoxIterator
class SphereIterator;
class BoxIterator {
private:
friend class ThisType;
friend class SphereIterator;
bool m_isEnd;
const ThisType* m_grid;
/** Lower bound on the boxes covered, inclusive. */
Vector3int32 m_lo;
/** Upper bound on the boxes covered, inclusive.*/
Vector3int32 m_hi;
/** If true, test values against m_box before returning them.*/
bool m_exact;
/** The underlying box in 3D space */
AABox m_box;
/** The iterator winds through the 3D grid between m_lo and (m_lo + m_extent) in
Z,Y,X-major order. This is the index keeping track of how
far it has come */
Vector3int32 m_current;
/** The current cell. */
Cell* m_cell;
/** Index within m_cell of the current value */
int m_arrayIndex;
const int m_epoch;
/** Called from advance() */
void advanceCell() {
do {
++m_current.x;
if (m_current.x > m_hi.x) {
m_current.x = m_lo.x;
++m_current.y;
if (m_current.y > m_hi.y) {
m_current.y = m_lo.y;
++m_current.z;
if (m_current.z > m_hi.z) {
m_isEnd = true;
return;
}
}
}
// Pick up the new cell
m_cell = m_grid->m_data.getPointer(m_current);
// Keep advancing if the cell does not exist
} while ((m_cell == NULL) || (m_cell->size() == 0));
}
/** Advance to the next value */
void advance() {
debugAssert(! m_isEnd);
do {
++m_arrayIndex;
bool inConstructor = (m_cell == NULL);
if (inConstructor || m_arrayIndex >= m_cell->size()) {
advanceCell();
m_arrayIndex = 0;
if (m_isEnd) {
// Ran out of values
return;
}
debugAssert(m_cell != NULL);
}
// Advance until we have a value that can be returned, either
// because we don't care about exactness or because it is
// guaranteed to be within the box.
} while (m_exact && ! m_box.contains(position()));
}
/** End iterator */
BoxIterator() : m_isEnd(true), m_grid(NULL), m_exact(true), m_current(0,0,0), m_cell(NULL), m_arrayIndex(0), m_epoch(0) {}
/** Begin iterator */
BoxIterator(const ThisType* grid, bool exact, const AABox& box) :
m_isEnd(false),
m_grid(grid),
m_exact(exact),
m_box(box),
m_current(-1, 0 ,0),
m_cell(NULL),
m_arrayIndex(0),
m_epoch(grid->m_epoch) {
m_grid->getCellCoord(box.low(), m_lo);
m_grid->getCellCoord(box.high(), m_hi);
// Get to the first value
m_current = m_lo;
// Back up one so that advancing takes us to the first
--m_current.x;
advance();
}
const Value& value() const {
debugAssert(! m_isEnd);
return (*m_cell)[m_arrayIndex].value;
}
/** Used by SphereIterator::advance() */
const Vector3& position() const {
debugAssert(! m_isEnd);
return (*m_cell)[m_arrayIndex].position;
}
// Intentionally unimplemented
BoxIterator& operator=(const BoxIterator&);
public:
inline bool operator!=(const BoxIterator& other) const {
if (other.m_isEnd && m_isEnd) {
return false;
} else {
return (m_isEnd != other.m_isEnd) ||
(m_cell != other.m_cell) ||
(m_arrayIndex != other.m_arrayIndex);
}
}
bool operator==(const BoxIterator& other) const {
return !(*this != other);
}
/** Preincrement */
BoxIterator& operator++() {
debugAssert(! m_isEnd);
debugAssertM(m_epoch == m_grid->m_epoch,
"It is illegal to mutate the HashGrid "
"while iterating through it.");
advance();
return *this;
}
/** Post increment (slower) */
BoxIterator operator++(int) {
Iterator old = *this;
++(*this);
return old;
}
const Value& operator*() const { return value(); }
const Value* operator->() const { return &value(); }
operator Value*() const { return &value(); }
/** \deprecated Use isValid */
bool hasMore() const {
return ! m_isEnd;
}
bool isValid() const {
return ! m_isEnd;
}
}; // BoxIterator
/**
Finds all values whose positions are within @a box. It is an error to
mutate the PointHashGrid while iterating through it.
@param exact If false, the iterator will execute more quickly but will likely return some
values that lie outside the box. Set exact = false if you are going to test the
results against the yourself box anyway.
*/
BoxIterator beginBoxIntersection(const AABox& box, bool exact = true) const {
return BoxIterator(this, exact, box);
}
const BoxIterator& endBoxIntersection() const {
static const BoxIterator it;
return it;
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
class SphereIterator {
private:
friend class ThisType;
bool m_isEnd;
Sphere m_sphere;
BoxIterator m_boxIterator;
SphereIterator() : m_isEnd(true) {}
void advance() {
if (! m_boxIterator.isValid()) {
m_isEnd = true;
return;
}
while (! m_sphere.contains(m_boxIterator.position())) {
++m_boxIterator;
if (! m_boxIterator.isValid()) {
m_isEnd = true;
return;
}
}
}
static AABox getBoundingBox(const Sphere& s) {
AABox box;
s.getBounds(box);
return box;
}
SphereIterator(const ThisType* grid, const Sphere& sphere) :
m_isEnd(false),
m_sphere(sphere),
m_boxIterator(grid, false, getBoundingBox(sphere)) {
// Find the first element that is actually in the sphere,
// not just the box.
advance();
}
const Value& value() const {
return *m_boxIterator;
}
// TODO: if the sphere is very big compared to radius, check each
// cell's box to see if the cell itself is actually inside the sphere
// before iterating through it, since there may be many boxes outside the sphere.
// Intentionally unimplemented
SphereIterator& operator=(const SphereIterator&);
public:
inline bool operator!=(const SphereIterator& other) const {
if (other.m_isEnd && m_isEnd) {
return false;
} else {
return
(m_isEnd != other.m_isEnd) ||
(m_sphere != other.m_sphere) ||
(m_boxIterator != other.m_boxIterator);
}
}
bool operator==(const SphereIterator& other) const {
return !(*this != other);
}
/** Preincrement */
SphereIterator& operator++() {
debugAssert(! m_isEnd);
++m_boxIterator;
advance();
return *this;
}
/** Post increment (slower) */
SphereIterator operator++(int) {
Iterator old = *this;
++(*this);
return old;
}
const Value& operator*() const { return value(); }
const Value* operator->() const { return &value(); }
operator Value*() const { return &value(); }
/** \deprecated use isValid */
bool G3D_DEPRECATED hasMore() const {
return ! m_isEnd;
}
bool isValid() const {
return ! m_isEnd;
}
}; // SphereIterator
/** Finds all values whose positions are within \a sphere. It is
an error to mutate the PointHashGrid while iterating through
it. */
SphereIterator begin(const Sphere& sphere) const {
return SphereIterator(this, sphere);
}
/** \deprecated \sa beginIntersection */
SphereIterator G3D_DEPRECATED beginSphereIntersection(const Sphere& sphere) const {
return SphereIterator(this, sphere);
}
/** \deprecated \sa SphereIterator::hasMore */
const SphereIterator& endSphereIntersection() const {
static const SphereIterator it;
return it;
}
/** Appends results */
void getIntersectingMembers(const Sphere& sphere, Array& result) const {
for (SphereIterator it = beginSphereIntersection(sphere); it.isValid(); ++it) {
result.append(*it);
}
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
/**
Dereference to access the bounds() and size() [element count] of the underlying
cell object.
Example:
for(PointHashGrid::CellIterator iter = grid.beginCells(); iter != grid.endCells(); ++iter) {
entriesFound += iter->size();
}
*/
class CellIterator {
private:
friend class ThisType;
bool m_isEnd;
const ThisType* m_grid;
typename CellTable::Iterator m_tableIterator;
const int m_epoch;
Cell& cell() {
return m_tableIterator->value;
}
public:
class CellObject {
friend class CellIterator;
private:
const CellIterator* m_parent;
CellObject() : m_parent(NULL) {}
public:
/** Returns the bounds on this cell */
AABox bounds() const {
const Vector3int32& k = m_parent->m_tableIterator->key;
return AABox(Vector3(k) * m_parent->m_grid->m_cellWidth,
Vector3(k + Vector3int32(1, 1, 1)) * m_parent->m_grid->m_cellWidth);
}
/** Number of elements inside this cell */
int size() const {
debugAssert(! m_parent->m_isEnd);
return m_parent->m_tableIterator->value.size();
}
};
private:
/** Used to make the indirection work.*/
CellObject m_indirection;
/** End iterator. Note that the m_tableIterator is initialized to the end iterator
of a temporary value! This is ok because we'll never look at the value of the
m_tableIterator, since we're initializing the "end" Iterator.*/
CellIterator() :
m_isEnd(true),
m_grid(NULL),
m_tableIterator( CellTable().end() ),
m_epoch(0) {}
CellIterator(const ThisType* grid) :
m_isEnd(false),
m_grid(grid),
m_tableIterator( grid->m_data.begin()),
m_epoch(grid->m_epoch) {
m_indirection.m_parent = this;
m_isEnd = ! m_tableIterator.isValid();
}
// Intentionally unimplemented
CellIterator& operator=(const CellIterator&);
public:
const CellObject& operator*() const { return m_indirection; }
const CellObject* operator->() const { return &m_indirection; }
operator CellObject*() const { return &m_indirection; }
inline bool operator!=(const CellIterator& other) const {
// != is called more often than == during iteration
return !(
(m_isEnd && other.m_isEnd) ||
((m_isEnd == other.m_isEnd) &&
(m_tableIterator != other.m_tableIterator)));
}
bool operator==(const CellIterator& other) const {
return !(*this != other);
}
/** Preincrement */
CellIterator& operator++() {
debugAssertM(m_epoch == m_grid->m_epoch,
"It is illegal to mutate the HashGrid while "
"iterating through it.");
++m_tableIterator;
m_isEnd = ! m_tableIterator.isValid();
return *this;
}
/** Post increment (slower) */
CellIterator operator++(int) {
Iterator old = *this;
++(*this);
return old;
}
/** \deprecated Use isValid */
bool hasMore() const {
return ! m_isEnd;
}
bool isValid() const {
return ! m_isEnd;
}
}; // CellIterator
/** Iterates through the non-empty cells. This is intended primarily for
debugging and visualizing the data structure.*/
CellIterator beginCells() const {
return CellIterator(this);
}
const CellIterator& endCells() const {
static const CellIterator it;
return it;
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
/** Returns true if there is a value that is exactly equal to @a v. This will
check all neighboring cells to avoid roundoff error at cell boundaries.
*/
bool contains(const Value& v) const {
Cell* cell = NULL;
int index = 0;
Vector3int32 cellCoord;
return const_cast(this)->find(v, cellCoord, cell, index);
}
/** Calls delete on all of the values, which are assumed to be pointers.
This is a helper to avoid requiring you to iterate through the data
structure, removing and deleting each one. Clears the PointHashGrid at the
end.
Using objects (instead of pointers) or reference counted pointers is
recommended over using pointers and this deleteAll method.*/
void deleteAll() {
for (Iterator it = begin(); it.isValid(); ++it) {
delete *it;
}
clear();
}
void clearAndSetMemoryManager(const MemoryManager::Ref& m) {
++m_epoch;
m_size = 0;
m_bounds = AABox();
m_data.clearAndSetMemoryManager(m);
m_memoryManager = m;
}
/** Removes all data.
@param shrink If true, underlying structures are deallocated as
they are freed.*/
void clear(bool shrink = true) {
m_size = 0;
m_bounds = AABox();
if (! shrink) {
// Remove all data
for (CellIterator it = beginCells(); it.isValid(); ++it) {
it.cell().clear(true);
}
} else {
m_data.clear();
}
++m_epoch;
}
int debugGetDeepestBucketSize() const {
return (int)m_data.debugGetDeepestBucketSize();
}
float debugGetAverageBucketSize() const {
return m_data.debugGetAverageBucketSize();
}
#undef ThisType
};
} // G3D
#endif