RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator Class Reference

#include <RTree.h>

Detailed Description

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
class RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator

Iterator is not remove safe.

Definition at line 131 of file RTree.h.


Public Member Functions

bool IsNotNull ()
 Is iterator pointing to valid data.
bool IsNull ()
 Is iterator invalid.
 Iterator ()
const DATATYPE & operator* () const
 Access the current data element. Caller must be sure iterator is not NULL first.
DATATYPE & operator* ()
 Access the current data element. Caller must be sure iterator is not NULL first.
bool operator++ ()
 Find the next data element.
 ~Iterator ()

Private Types

enum  { MAX_STACK = 32 }

Private Member Functions

bool FindNextData ()
 Find the next data element in the tree (For internal use only).
void Init ()
 Reset iterator.
StackElement & Pop ()
 Pop element off iteration stack (For internal use only).
void Push (Node *a_node, int a_branchIndex)
 Push node and branch onto iteration stack (For internal use only).

Private Attributes

StackElement m_stack [MAX_STACK]
 Stack as we are doing iteration instead of recursion.
int m_tos
 Top Of Stack index.

Friends

class RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >

Data Structures

struct  StackElement

Member Enumeration Documentation

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
anonymous enum [private]

Enumerator:
MAX_STACK 

Definition at line 135 of file RTree.h.

00135 { MAX_STACK = 32 }; //  Max stack size. Allows almost n^32 where n is number of branches in node

Constructor & Destructor Documentation

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Iterator (  )  [inline]

Definition at line 145 of file RTree.h.

References RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Init().

00145 { Init(); }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::~Iterator (  )  [inline]

Definition at line 147 of file RTree.h.

00147 { }

Member Function Documentation

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::FindNextData (  )  [inline, private]

Find the next data element in the tree (For internal use only).

Definition at line 180 of file RTree.h.

References RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Node::IsLeaf(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Node::m_branch, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_branchIndex, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Branch::m_child, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Node::m_count, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_node, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Pop(), and RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Push().

Referenced by RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator++().

00181     {
00182       for(;;)
00183       {
00184         if(m_tos <= 0)
00185         {
00186           return false;
00187         }
00188         StackElement curTos = Pop(); // Copy stack top cause it may change as we use it
00189 
00190         if(curTos.m_node->IsLeaf())
00191         {
00192           // Keep walking through data while we can
00193           if(curTos.m_branchIndex+1 < curTos.m_node->m_count)
00194           {
00195             // There is more data, just point to the next one
00196             Push(curTos.m_node, curTos.m_branchIndex + 1);
00197             return true;
00198           }
00199           // No more data, so it will fall back to previous level
00200         }
00201         else
00202         {
00203           if(curTos.m_branchIndex+1 < curTos.m_node->m_count)
00204           {
00205             // Push sibling on for future tree walk
00206             // This is the 'fall back' node when we finish with the current level
00207             Push(curTos.m_node, curTos.m_branchIndex + 1);
00208           }
00209           // Since cur node is not a leaf, push first of next level to get deeper into the tree
00210           Node* nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child;
00211           Push(nextLevelnode, 0);
00212           
00213           // If we pushed on a new leaf, exit as the data is ready at TOS
00214           if(nextLevelnode->IsLeaf())
00215           {
00216             return true;
00217           }
00218         }
00219       }
00220     }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Init (  )  [inline, private]

Reset iterator.

Definition at line 177 of file RTree.h.

References RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos.

Referenced by RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Iterator().

00177 { m_tos = 0; }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNotNull (  )  [inline]

Is iterator pointing to valid data.

Definition at line 153 of file RTree.h.

References RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos.

Referenced by RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator*().

00153 { return (m_tos > 0); }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNull (  )  [inline]

Is iterator invalid.

Definition at line 150 of file RTree.h.

References RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos.

00150 { return (m_tos <= 0); }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
const DATATYPE& RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator* (  )  const [inline]

Access the current data element. Caller must be sure iterator is not NULL first.

Definition at line 164 of file RTree.h.

References ASSERT, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNotNull(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Node::m_branch, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_branchIndex, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Branch::m_data, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_node, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_stack, and RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos.

00165     {
00166       ASSERT(IsNotNull());
00167       StackElement& curTos = m_stack[m_tos - 1];
00168       return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
00169     }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
DATATYPE& RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator* (  )  [inline]

Access the current data element. Caller must be sure iterator is not NULL first.

Definition at line 156 of file RTree.h.

References ASSERT, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNotNull(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Node::m_branch, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_branchIndex, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Branch::m_data, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_node, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_stack, and RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos.

00157     {
00158       ASSERT(IsNotNull());
00159       StackElement& curTos = m_stack[m_tos - 1];
00160       return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
00161     }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator++ (  )  [inline]

Find the next data element.

Definition at line 172 of file RTree.h.

References RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::FindNextData().

00172 { return FindNextData(); }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
StackElement& RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Pop (  )  [inline, private]

Pop element off iteration stack (For internal use only).

Definition at line 232 of file RTree.h.

References ASSERT, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_stack, and RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos.

Referenced by RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::FindNextData().

00233     {
00234       ASSERT(m_tos > 0);
00235       --m_tos;
00236       return m_stack[m_tos];
00237     }

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Push ( Node *  a_node,
int  a_branchIndex 
) [inline, private]

Push node and branch onto iteration stack (For internal use only).

Definition at line 223 of file RTree.h.

References ASSERT, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_branchIndex, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_node, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_stack, RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos, and RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::MAX_STACK.

Referenced by RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::FindNextData().

00224     {
00225       m_stack[m_tos].m_node = a_node;
00226       m_stack[m_tos].m_branchIndex = a_branchIndex;
00227       ++m_tos;
00228       ASSERT(m_tos <= MAX_STACK);
00229     }

Friends And Related Function Documentation

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
friend class RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES > [friend]

Definition at line 242 of file RTree.h.

Field Documentation

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
StackElement RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_stack[MAX_STACK] [private]

Stack as we are doing iteration instead of recursion.

Definition at line 239 of file RTree.h.

Referenced by RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator*(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Pop(), and RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Push().

template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
int RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos [private]

Top Of Stack index.

Definition at line 240 of file RTree.h.

Referenced by RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::FindNextData(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Init(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNotNull(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNull(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator*(), RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Pop(), and RTree< DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Push().

The documentation for this class was generated from the following file:
Generated on Wed May 5 00:07:00 2010 for Sumo - Simulation of Urban MObility by  doxygen 1.5.6