KiCad PCB EDA Suite
RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator Class Reference

Iterator is not remove safe. More...

#include <rtree.h>

Classes

struct  StackElement
 

Public Member Functions

 Iterator ()
 
 ~Iterator ()
 
bool IsNull ()
 Is iterator invalid. More...
 
bool IsNotNull ()
 Is iterator pointing to valid data. More...
 
DATATYPE & operator* ()
 Access the current data element. Caller must be sure iterator is not NULL first. More...
 
const DATATYPE & operator* () const
 Access the current data element. Caller must be sure iterator is not NULL first. More...
 
bool operator++ ()
 Find the next data element. More...
 
void GetBounds (ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS])
 Get the bounds for this node. More...
 

Private Types

enum  { MAX_STACK = 32 }
 

Private Member Functions

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

Private Attributes

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

Friends

class RTree
 

Detailed Description

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

Iterator is not remove safe.

Definition at line 205 of file rtree.h.

Member Enumeration Documentation

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
anonymous enum
private
Enumerator
MAX_STACK 

Definition at line 209 of file rtree.h.

209 { 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 ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Iterator ( )
inline

Definition at line 218 of file rtree.h.

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

218 { Init(); }
void Init()
Reset iterator.
Definition: rtree.h:264
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::~Iterator ( )
inline

Definition at line 220 of file rtree.h.

220 { }

Member Function Documentation

template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::FindNextData ( )
inlineprivate

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

Definition at line 267 of file rtree.h.

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

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

268  {
269  for( ; ; )
270  {
271  if( m_tos <= 0 )
272  {
273  return false;
274  }
275 
276  StackElement curTos = Pop(); // Copy stack top cause it may change as we use it
277 
278  if( curTos.m_node->IsLeaf() )
279  {
280  // Keep walking through data while we can
281  if( curTos.m_branchIndex + 1 < curTos.m_node->m_count )
282  {
283  // There is more data, just point to the next one
284  Push( curTos.m_node, curTos.m_branchIndex + 1 );
285  return true;
286  }
287 
288  // No more data, so it will fall back to previous level
289  }
290  else
291  {
292  if( curTos.m_branchIndex + 1 < curTos.m_node->m_count )
293  {
294  // Push sibling on for future tree walk
295  // This is the 'fall back' node when we finish with the current level
296  Push( curTos.m_node, curTos.m_branchIndex + 1 );
297  }
298 
299  // Since cur node is not a leaf, push first of next level to get deeper into the tree
300  Node* nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child;
301  Push( nextLevelnode, 0 );
302 
303  // If we pushed on a new leaf, exit as the data is ready at TOS
304  if( nextLevelnode->IsLeaf() )
305  {
306  return true;
307  }
308  }
309  }
310  }
StackElement & Pop()
Pop element off iteration stack (For internal use only)
Definition: rtree.h:322
void Push(Node *a_node, int a_branchIndex)
Push node and branch onto iteration stack (For internal use only)
Definition: rtree.h:313
int m_tos
Top Of Stack index.
Definition: rtree.h:330
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::GetBounds ( ELEMTYPE  a_min[NUMDIMS],
ELEMTYPE  a_max[NUMDIMS] 
)
inline

Get the bounds for this node.

Definition at line 248 of file rtree.h.

References ASSERT, RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNotNull(), RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Node::m_branch, RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_branchIndex, RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Rect::m_max, RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Rect::m_min, RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_node, RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Branch::m_rect, RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_stack, and RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::m_tos.

249  {
250  ASSERT( IsNotNull() );
251  StackElement& curTos = m_stack[m_tos - 1];
252  Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];
253 
254  for( int index = 0; index < NUMDIMS; ++index )
255  {
256  a_min[index] = curBranch.m_rect.m_min[index];
257  a_max[index] = curBranch.m_rect.m_max[index];
258  }
259  }
ELEMTYPE m_min[NUMDIMS]
Min dimensions of bounding box.
Definition: rtree.h:375
Rect m_rect
Bounds.
Definition: rtree.h:384
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:226
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:329
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:400
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:330
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Init ( )
inlineprivate
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNotNull ( )
inline
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::IsNull ( )
inline

Is iterator invalid.

Definition at line 223 of file rtree.h.

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

223 { return m_tos <= 0; }
int m_tos
Top Of Stack index.
Definition: rtree.h:330
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
DATATYPE& RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator* ( )
inline

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

Definition at line 229 of file rtree.h.

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

230  {
231  ASSERT( IsNotNull() );
232  StackElement& curTos = m_stack[m_tos - 1];
233  return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
234  }
DATATYPE m_data
Data Id or Ptr.
Definition: rtree.h:388
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:226
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:329
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:400
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:330
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
const DATATYPE& RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator* ( ) const
inline

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

Definition at line 237 of file rtree.h.

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

238  {
239  ASSERT( IsNotNull() );
240  StackElement& curTos = m_stack[m_tos - 1];
241  return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
242  }
DATATYPE m_data
Data Id or Ptr.
Definition: rtree.h:388
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:226
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:329
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:400
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:330
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
bool RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::operator++ ( )
inline

Find the next data element.

Definition at line 245 of file rtree.h.

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

245 { return FindNextData(); }
bool FindNextData()
Find the next data element in the tree (For internal use only)
Definition: rtree.h:267
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
StackElement& RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Pop ( )
inlineprivate

Pop element off iteration stack (For internal use only)

Definition at line 322 of file rtree.h.

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

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

323  {
324  ASSERT( m_tos > 0 );
325  --m_tos;
326  return m_stack[m_tos];
327  }
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:329
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:330
template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
void RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::Push ( Node a_node,
int  a_branchIndex 
)
inlineprivate

Friends And Related Function Documentation

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

Definition at line 332 of file rtree.h.

Member Data Documentation

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

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