G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator Class Reference

#include <KDTree.h>

Public Member Functions
bool	operator!= (const BoxIntersectionIterator &other) const
bool	operator== (const BoxIntersectionIterator &other) const
BoxIntersectionIterator &	operator++ ()
const T &	operator* () const
T const *	operator-> () const
	operator T * () const

Private Member Functions
	BoxIntersectionIterator ()
	BoxIntersectionIterator (const AABox &b, const Node *root)
BoxIntersectionIterator	operator++ (int)

Private Attributes
bool	isEnd
AABox	box
Node *	node
Array< Node * >	stack
int	nextValueArrayIndex

Friends
class	TreeType

Detailed Description

template<class T, class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>
class G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator

C++ STL style iterator variable. See beginBoxIntersection(). The iterator overloads the -> (dereference) operator, so this acts like a pointer to the current member.

Constructor & Destructor Documentation

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::BoxIntersectionIterator ( )

inlineprivate

: isEnd(true) {}

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::BoxIntersectionIterator ( const AABox &  b, const Node *  root  )

inlineprivate

 : 
 isEnd(root == NULL), box(b), 
 node(const_cast<Node*>(root)), nextValueArrayIndex(-1) {

 // We intentionally start at the "-1" index of the current
 // node so we can use the preincrement operator to move
 // ourselves to element 0 instead of repeating all of the
 // code from the preincrement method. Note that this might
 // cause us to become the "end" instance.
 ++(*this);
 }

Member Function Documentation

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator T * ( ) const

inline

Overloaded cast operator so the iterator can masquerade as a pointer to a member

 {
 alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator");
 return &(stack.last()->valueArray[nextValueArrayIndex]->value);
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

bool G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator!= ( const BoxIntersectionIterator &  other ) const

inline

 {
 return ! (*this == other);
 }

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

const T& G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator* ( ) const

inline

Overloaded dereference operator so the iterator can masquerade as a pointer to a member

 {
 alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator");
 return node->valueArray[nextValueArrayIndex]->value;
 }

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

BoxIntersectionIterator& G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++ ( )

inline

Pre increment.

 {
 ++nextValueArrayIndex;

 bool foundIntersection = false;
 while (! isEnd && ! foundIntersection) {

 // Search for the next node if we've exhausted this one
 while ((! isEnd) && (nextValueArrayIndex >= node->valueArray.length())) {
 // If we entered this loop, then the iterator has exhausted the elements at 
 // node (possibly because it just switched to a child node with no members).
 // This loop continues until it finds a node with members or reaches
 // the end of the whole intersection search.
 
 // If the right child overlaps the box, push it onto the stack for
 // processing.
 if ((node->child[1] != NULL) &&
 (box.high()[node->splitAxis] > node->splitLocation)) {
 stack.push(node->child[1]);
 }
 
 // If the left child overlaps the box, push it onto the stack for
 // processing.
 if ((node->child[0] != NULL) &&
 (box.low()[node->splitAxis] < node->splitLocation)) {
 stack.push(node->child[0]);
 }
 
 if (stack.length() > 0) {
 // Go on to the next node (which may be either one of the ones we 
 // just pushed, or one from farther back the tree).
 node = stack.pop();
 nextValueArrayIndex = 0;
 } else {
 // That was the last node; we're done iterating
 isEnd = true;
 }
 }
 
 // Search for the next intersection at this node until we run out of children
 while (! isEnd && ! foundIntersection && (nextValueArrayIndex < node->valueArray.length())) {
 if (box.intersects(node->boundsArray[nextValueArrayIndex])) {
 foundIntersection = true;
 } else {
 ++nextValueArrayIndex;
 // If we exhaust this node, we'll loop around the master loop 
 // to find a new node.
 }
 }
 }

 return *this;
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

BoxIntersectionIterator G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++ ( int  )

private

Post increment (much slower than preincrement!). Intentionally overloaded to preclude accidentally slow code.

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

T const* G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator-> ( ) const

inline

Overloaded dereference operator so the iterator can masquerade as a pointer to a member

 {
 alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator");
 return &(stack.last()->valueArray[nextValueArrayIndex]->value);
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

bool G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator== ( const BoxIntersectionIterator &  other ) const

inline

 {
 if (isEnd) {
 return other.isEnd;
 } else if (other.isEnd) {
 return false;
 } else {
 // Two non-end iterators; see if they match. This is kind of 
 // silly; users shouldn't call == on iterators in general unless
 // one of them is the end iterator.
 if ((box != other.box) || (node != other.node) || 
 (nextValueArrayIndex != other.nextValueArrayIndex) ||
 (stack.length() != other.stack.length())) {
 return false;
 }

 // See if the stacks are the same
 for (int i = 0; i < stack.length(); ++i) {
 if (stack[i] != other.stack[i]) {
 return false;
 }
 }

 // We failed to find a difference; they must be the same
 return true;
 }
 }

Here is the call graph for this function:

Friends And Related Function Documentation

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

friend class TreeType

friend

Member Data Documentation

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

AABox G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::box

private

The box that we're testing against.

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

bool G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::isEnd

private

True if this is the "end" iterator instance

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

int G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::nextValueArrayIndex

private

The next index of current->valueArray to return. Undefined when isEnd is true.

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Node* G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::node

private

Node that we're currently looking at. Undefined if isEnd is true.

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Array<Node*> G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::stack

private

Nodes waiting to be processed

---

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

• dep/g3dlite/include/G3D/KDTree.h