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 201 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 205 of file rtree.h.

205 { 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 214 of file rtree.h.

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

216 { }

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 263 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.

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

245  {
246  ASSERT( IsNotNull() );
247  StackElement& curTos = m_stack[m_tos - 1];
248  Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];
249 
250  for( int index = 0; index < NUMDIMS; ++index )
251  {
252  a_min[index] = curBranch.m_rect.m_min[index];
253  a_max[index] = curBranch.m_rect.m_max[index];
254  }
255  }
ELEMTYPE m_min[NUMDIMS]
Min dimensions of bounding box.
Definition: rtree.h:371
Rect m_rect
Bounds.
Definition: rtree.h:380
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:222
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:325
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:396
#define ASSERT
Definition: rtree.h:36
int m_tos
Top Of Stack index.
Definition: rtree.h:326
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 260 of file rtree.h.

260 { m_tos = 0; }
int m_tos
Top Of Stack index.
Definition: rtree.h:326
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 222 of file rtree.h.

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

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

226  {
227  ASSERT( IsNotNull() );
228  StackElement& curTos = m_stack[m_tos - 1];
229  return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
230  }
DATATYPE m_data
Data Id or Ptr.
Definition: rtree.h:384
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:222
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:325
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:396
#define ASSERT
Definition: rtree.h:36
int m_tos
Top Of Stack index.
Definition: rtree.h:326
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 233 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.

234  {
235  ASSERT( IsNotNull() );
236  StackElement& curTos = m_stack[m_tos - 1];
237  return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
238  }
DATATYPE m_data
Data Id or Ptr.
Definition: rtree.h:384
bool IsNotNull()
Is iterator pointing to valid data.
Definition: rtree.h:222
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:325
Branch m_branch[MAXNODES]
Branch.
Definition: rtree.h:396
#define ASSERT
Definition: rtree.h:36
int m_tos
Top Of Stack index.
Definition: rtree.h:326
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 241 of file rtree.h.

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

References ASSERT.

319  {
320  ASSERT( m_tos > 0 );
321  --m_tos;
322  return m_stack[m_tos];
323  }
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:325
#define ASSERT
Definition: rtree.h:36
int m_tos
Top Of Stack index.
Definition: rtree.h:326
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 309 of file rtree.h.

References ASSERT.

310  {
311  m_stack[m_tos].m_node = a_node;
312  m_stack[m_tos].m_branchIndex = a_branchIndex;
313  ++m_tos;
314  ASSERT( m_tos <= MAX_STACK );
315  }
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
Definition: rtree.h:325
#define ASSERT
Definition: rtree.h:36
int m_tos
Top Of Stack index.
Definition: rtree.h:326

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 328 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 325 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 326 of file rtree.h.


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