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 206 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 210 of file rtree.h.

210 { 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 219 of file rtree.h.

219 { Init(); }
void Init()
Reset iterator.
Definition: rtree.h:265
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 221 of file rtree.h.

221 { }

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 268 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, and RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_node.

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

References ASSERT, 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, and RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Branch::m_rect.

250  {
251  ASSERT( IsNotNull() );
252  StackElement& curTos = m_stack[m_tos - 1];
253  Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];
254 
255  for( int index = 0; index < NUMDIMS; ++index )
256  {
257  a_min[index] = curBranch.m_rect.m_min[index];
258  a_max[index] = curBranch.m_rect.m_max[index];
259  }
260  }
ELEMTYPE m_min[NUMDIMS]
Min dimensions of bounding box.
Definition: rtree.h:376
Rect m_rect
Bounds.
Definition: rtree.h:385
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:227
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:330
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:401
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:331
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

Reset iterator.

Definition at line 265 of file rtree.h.

265 { m_tos = 0; }
int m_tos
Top Of Stack index.
Definition: rtree.h:331
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

Is iterator pointing to valid data.

Definition at line 227 of file rtree.h.

227 { return m_tos > 0; }
int m_tos
Top Of Stack index.
Definition: rtree.h:331
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 224 of file rtree.h.

224 { return m_tos <= 0; }
int m_tos
Top Of Stack index.
Definition: rtree.h:331
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 230 of file rtree.h.

References ASSERT, 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, and RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_node.

231  {
232  ASSERT( IsNotNull() );
233  StackElement& curTos = m_stack[m_tos - 1];
234  return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
235  }
DATATYPE m_data
Data Id or Ptr.
Definition: rtree.h:389
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:227
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:330
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:401
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:331
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 238 of file rtree.h.

References ASSERT, 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, and RTree< DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES >::Iterator::StackElement::m_node.

239  {
240  ASSERT( IsNotNull() );
241  StackElement& curTos = m_stack[m_tos - 1];
242  return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
243  }
DATATYPE m_data
Data Id or Ptr.
Definition: rtree.h:389
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:227
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:330
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:401
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:331
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 246 of file rtree.h.

246 { return FindNextData(); }
bool FindNextData()
Find the next data element in the tree (For internal use only)
Definition: rtree.h:268
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 323 of file rtree.h.

References ASSERT.

324  {
325  ASSERT( m_tos > 0 );
326  --m_tos;
327  return m_stack[m_tos];
328  }
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:330
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:331
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

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

Definition at line 314 of file rtree.h.

References ASSERT.

315  {
316  m_stack[m_tos].m_node = a_node;
317  m_stack[m_tos].m_branchIndex = a_branchIndex;
318  ++m_tos;
319  ASSERT( m_tos <= MAX_STACK );
320  }
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:330
#define ASSERT
Definition: rtree.h:33
int m_tos
Top Of Stack index.
Definition: rtree.h:331

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 333 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

Stack as we are doing iteration instead of recursion.

Definition at line 330 of file rtree.h.

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

Top Of Stack index.

Definition at line 331 of file rtree.h.


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