KiCad PCB EDA Suite
EE_RTREE Class Reference

EE_RTREE - Implements an R-tree for fast spatial and type indexing of schematic items. More...

#include <sch_rtree.h>

Classes

struct  EE_TYPE
 The EE_TYPE struct provides a type-specific auto-range iterator to the RTree. More...
 

Public Types

using iterator = typename ee_rtree::Iterator
 

Public Member Functions

 EE_RTREE ()
 
 ~EE_RTREE ()
 
void insert (SCH_ITEM *aItem)
 Function Insert() Inserts an item into the tree. More...
 
bool remove (SCH_ITEM *aItem)
 Function Remove() Removes an item from the tree. More...
 
void clear ()
 Function RemoveAll() Removes all items from the RTree. More...
 
bool contains (SCH_ITEM *aItem, bool aRobust=false)
 Determine if a given item exists in the tree. More...
 
size_t size ()
 Returns the number of items in the tree. More...
 
bool empty ()
 
EE_TYPE OfType (KICAD_T aType)
 
EE_TYPE Overlapping (const EDA_RECT &aRect)
 
EE_TYPE Overlapping (const wxPoint &aPoint, int aAccuracy=0)
 
EE_TYPE Overlapping (KICAD_T aType, const wxPoint &aPoint, int aAccuracy=0)
 
EE_TYPE Overlapping (KICAD_T aType, const EDA_RECT &aRect)
 
iterator begin ()
 
iterator end ()
 
const iterator begin () const
 
const iterator end () const
 

Private Types

using ee_rtree = RTree< SCH_ITEM *, int, 3, double >
 

Private Attributes

ee_rtreem_tree
 
size_t m_count
 

Detailed Description

EE_RTREE - Implements an R-tree for fast spatial and type indexing of schematic items.

Non-owning.

Definition at line 41 of file sch_rtree.h.

Member Typedef Documentation

◆ ee_rtree

using EE_RTREE::ee_rtree = RTree<SCH_ITEM*, int, 3, double>
private

Definition at line 44 of file sch_rtree.h.

◆ iterator

using EE_RTREE::iterator = typename ee_rtree::Iterator

Definition at line 171 of file sch_rtree.h.

Constructor & Destructor Documentation

◆ EE_RTREE()

EE_RTREE::EE_RTREE ( )
inline

Definition at line 47 of file sch_rtree.h.

48  {
49  this->m_tree = new ee_rtree();
50  m_count = 0;
51  }
ee_rtree * m_tree
Definition: sch_rtree.h:271
RTree< SCH_ITEM *, int, 3, double > ee_rtree
Definition: sch_rtree.h:44
size_t m_count
Definition: sch_rtree.h:272

References m_count, and m_tree.

◆ ~EE_RTREE()

EE_RTREE::~EE_RTREE ( )
inline

Definition at line 53 of file sch_rtree.h.

54  {
55  delete this->m_tree;
56  }
ee_rtree * m_tree
Definition: sch_rtree.h:271

References m_tree.

Member Function Documentation

◆ begin() [1/2]

iterator EE_RTREE::begin ( )
inline

Definition at line 248 of file sch_rtree.h.

249  {
250  return m_tree->begin();
251  }
ee_rtree * m_tree
Definition: sch_rtree.h:271

References m_tree.

Referenced by SCH_SCREEN::FreeDrawList().

◆ begin() [2/2]

const iterator EE_RTREE::begin ( ) const
inline

Definition at line 259 of file sch_rtree.h.

260  {
261  return m_tree->begin();
262  }
ee_rtree * m_tree
Definition: sch_rtree.h:271

References m_tree.

◆ clear()

void EE_RTREE::clear ( )
inline

Function RemoveAll() Removes all items from the RTree.

Definition at line 108 of file sch_rtree.h.

109  {
110  m_tree->RemoveAll();
111  m_count = 0;
112  }
ee_rtree * m_tree
Definition: sch_rtree.h:271
size_t m_count
Definition: sch_rtree.h:272

References m_count, and m_tree.

Referenced by SCH_SCREEN::Clear(), and SCH_SCREEN::FreeDrawList().

◆ contains()

bool EE_RTREE::contains ( SCH_ITEM aItem,
bool  aRobust = false 
)
inline

Determine if a given item exists in the tree.

Note that this does not search the full tree so if the item has been moved, this will return false when it should be true.

Parameters
aItemItem that may potentially exist in the tree
aRobustIf true, search the whole tree, not just the bounding box
Returns
true if the item definitely exists, false if it does not exist within bbox

Definition at line 122 of file sch_rtree.h.

123  {
124  const EDA_RECT& bbox = aItem->GetBoundingBox();
125  const int type = int( aItem->Type() );
126  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
127  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
128  bool found = false;
129 
130  auto search = [&found, &aItem]( const SCH_ITEM* aSearchItem ) {
131  if( aSearchItem == aItem )
132  {
133  found = true;
134  return false;
135  }
136 
137  return true;
138  };
139 
140  m_tree->Search( mmin, mmax, search );
141 
142  if( !found && aRobust )
143  {
144  // N.B. We must search the whole tree for the pointer to remove
145  // because the item may have been moved. We do not expand the item
146  // type search as this should not change.
147 
148  const int mmin2[3] = { type, INT_MIN, INT_MIN };
149  const int mmax2[3] = { type, INT_MAX, INT_MAX };
150 
151  m_tree->Search( mmin2, mmax2, search );
152  }
153 
154  return found;
155  }
int GetX() const
Definition: eda_rect.h:111
int GetBottom() const
Definition: eda_rect.h:124
ee_rtree * m_tree
Definition: sch_rtree.h:271
int GetRight() const
Definition: eda_rect.h:121
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
int GetY() const
Definition: eda_rect.h:112
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
Definition: base_struct.cpp:97
Base class for any item which can be embedded within the SCHEMATIC container class,...
Definition: sch_item.h:187
KICAD_T Type() const
Function Type()
Definition: base_struct.h:193

References EDA_RECT::GetBottom(), EDA_ITEM::GetBoundingBox(), EDA_RECT::GetRight(), EDA_RECT::GetX(), EDA_RECT::GetY(), m_tree, and EDA_ITEM::Type().

Referenced by SCH_SCREEN::CheckIfOnDrawList().

◆ empty()

bool EE_RTREE::empty ( )
inline

Definition at line 166 of file sch_rtree.h.

167  {
168  return m_count == 0;
169  }
size_t m_count
Definition: sch_rtree.h:272

References m_count.

Referenced by SCH_SCREEN::IsEmpty().

◆ end() [1/2]

iterator EE_RTREE::end ( )
inline

Definition at line 253 of file sch_rtree.h.

254  {
255  return m_tree->end();
256  }
ee_rtree * m_tree
Definition: sch_rtree.h:271

References m_tree.

Referenced by SCH_SCREEN::FreeDrawList().

◆ end() [2/2]

const iterator EE_RTREE::end ( ) const
inline

Definition at line 264 of file sch_rtree.h.

265  {
266  return m_tree->end();
267  }
ee_rtree * m_tree
Definition: sch_rtree.h:271

References m_tree.

◆ insert()

void EE_RTREE::insert ( SCH_ITEM aItem)
inline

Function Insert() Inserts an item into the tree.

Item's bounding box is taken via its BBox() method.

Definition at line 62 of file sch_rtree.h.

63  {
64  const EDA_RECT& bbox = aItem->GetBoundingBox();
65  const int type = int( aItem->Type() );
66  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
67  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
68 
69  m_tree->Insert( mmin, mmax, aItem );
70  m_count++;
71  }
int GetX() const
Definition: eda_rect.h:111
int GetBottom() const
Definition: eda_rect.h:124
ee_rtree * m_tree
Definition: sch_rtree.h:271
int GetRight() const
Definition: eda_rect.h:121
size_t m_count
Definition: sch_rtree.h:272
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
int GetY() const
Definition: eda_rect.h:112
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
Definition: base_struct.cpp:97
KICAD_T Type() const
Function Type()
Definition: base_struct.h:193

References EDA_RECT::GetBottom(), EDA_ITEM::GetBoundingBox(), EDA_RECT::GetRight(), EDA_RECT::GetX(), EDA_RECT::GetY(), m_count, m_tree, and EDA_ITEM::Type().

Referenced by SCH_SCREEN::Append(), and SCH_SCREEN::UpdateLocalLibSymbolLinks().

◆ OfType()

EE_TYPE EE_RTREE::OfType ( KICAD_T  aType)
inline

Definition at line 219 of file sch_rtree.h.

220  {
221  return EE_TYPE( m_tree, aType );
222  }
ee_rtree * m_tree
Definition: sch_rtree.h:271

References m_tree.

Referenced by SCH_SHEET_LIST::AnnotatePowerSymbols(), SCH_EDIT_FRAME::BreakSegmentsOnJunctions(), SCH_SCREENS::buildScreenList(), SCH_SCREENS::ChangeSymbolLibNickname(), SCH_SHEET::CleanupSheet(), EE_COLLECTOR::Collect(), SCH_SHEET::ComponentCount(), SCH_SHEET::CountSheets(), SCH_EDIT_FRAME::DeleteAnnotation(), DIALOG_UPDATE_FIELDS::DIALOG_UPDATE_FIELDS(), SCH_EDITOR_CONTROL::FindComponentAndItem(), SCH_LINE_WIRE_BUS_TOOL::finishSegments(), SCH_EDIT_FRAME::FixupJunctions(), SCH_MOVE_TOOL::getConnectedDragItems(), SCH_SCREENS::HasNoFullyDefinedLibIds(), SCH_SHEET::HasUndefinedPins(), SCH_EDIT_FRAME::ImportHierLabel(), SCH_SEXPR_PLUGIN::loadHierarchy(), SCH_LEGACY_PLUGIN::loadHierarchy(), SCH_EDIT_FRAME::LoadSheetFromFile(), SCH_SHEET::LocatePathOfScreen(), EDIT_POINTS_FACTORY::Make(), DIALOG_EDIT_SHEET_PIN::onComboBox(), NETLIST_EXPORTER_PSPICE::ProcessNetlist(), BACK_ANNOTATE::processNetNameChange(), DIALOG_SYMBOL_REMAP::remapSymbolsToLibTable(), SCH_SHEET_LIST::ReplaceLegacySheetPaths(), SCH_EDIT_FRAME::SaveProject(), SCH_EDIT_FRAME::SchematicCleanUp(), SCH_SHEET::SearchHierarchy(), ERC_TESTER::TestDuplicateSheetNames(), DIALOG_ERC::TestErc(), DIALOG_SCH_SHEET_PROPS::TransferDataFromWindow(), DIALOG_EDIT_SHEET_PIN::TransferDataToWindow(), SCH_EDIT_FRAME::TrimWire(), and NETLIST_EXPORTER_ORCADPCB2::WriteNetlist().

◆ Overlapping() [1/4]

EE_TYPE EE_RTREE::Overlapping ( const EDA_RECT aRect)
inline

◆ Overlapping() [2/4]

EE_TYPE EE_RTREE::Overlapping ( const wxPoint aPoint,
int  aAccuracy = 0 
)
inline

Definition at line 229 of file sch_rtree.h.

230  {
231  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
232  rect.Inflate( aAccuracy );
233  return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
234  }
ee_rtree * m_tree
Definition: sch_rtree.h:271
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44

References EDA_RECT::Inflate(), m_tree, and SCH_LOCATE_ANY_T.

◆ Overlapping() [3/4]

EE_TYPE EE_RTREE::Overlapping ( KICAD_T  aType,
const wxPoint aPoint,
int  aAccuracy = 0 
)
inline

Definition at line 236 of file sch_rtree.h.

237  {
238  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
239  rect.Inflate( aAccuracy );
240  return EE_TYPE( m_tree, aType, rect );
241  }
ee_rtree * m_tree
Definition: sch_rtree.h:271
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44

References EDA_RECT::Inflate(), and m_tree.

◆ Overlapping() [4/4]

EE_TYPE EE_RTREE::Overlapping ( KICAD_T  aType,
const EDA_RECT aRect 
)
inline

Definition at line 243 of file sch_rtree.h.

244  {
245  return EE_TYPE( m_tree, aType, aRect );
246  }
ee_rtree * m_tree
Definition: sch_rtree.h:271

References m_tree.

◆ remove()

bool EE_RTREE::remove ( SCH_ITEM aItem)
inline

Function Remove() Removes an item from the tree.

Removal is done by comparing pointers, attempting to remove a copy of the item will fail.

Definition at line 78 of file sch_rtree.h.

79  {
80  // First, attempt to remove the item using its given BBox
81  const EDA_RECT& bbox = aItem->GetBoundingBox();
82  const int type = int( aItem->Type() );
83  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
84  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
85 
86  // If we are not successful ( true == not found ), then we expand
87  // the search to the full tree
88  if( m_tree->Remove( mmin, mmax, aItem ) )
89  {
90  // N.B. We must search the whole tree for the pointer to remove
91  // because the item may have been moved before we have the chance to
92  // delete it from the tree
93  const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
94  const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
95 
96  if( m_tree->Remove( mmin2, mmax2, aItem ) )
97  return false;
98  }
99 
100  m_count--;
101  return true;
102  }
int GetX() const
Definition: eda_rect.h:111
int GetBottom() const
Definition: eda_rect.h:124
ee_rtree * m_tree
Definition: sch_rtree.h:271
int GetRight() const
Definition: eda_rect.h:121
size_t m_count
Definition: sch_rtree.h:272
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
int GetY() const
Definition: eda_rect.h:112
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
Definition: base_struct.cpp:97
KICAD_T Type() const
Function Type()
Definition: base_struct.h:193

References EDA_RECT::GetBottom(), EDA_ITEM::GetBoundingBox(), EDA_RECT::GetRight(), EDA_RECT::GetX(), EDA_RECT::GetY(), m_count, m_tree, and EDA_ITEM::Type().

Referenced by SCH_SCREEN::Remove(), and SCH_SCREEN::UpdateLocalLibSymbolLinks().

◆ size()

size_t EE_RTREE::size ( )
inline

Returns the number of items in the tree.

Returns
number of elements in the tree;

Definition at line 161 of file sch_rtree.h.

162  {
163  return m_count;
164  }
size_t m_count
Definition: sch_rtree.h:272

References m_count.

Member Data Documentation

◆ m_count

size_t EE_RTREE::m_count
private

Definition at line 272 of file sch_rtree.h.

Referenced by clear(), EE_RTREE(), empty(), insert(), remove(), and size().

◆ m_tree

ee_rtree* EE_RTREE::m_tree
private

Definition at line 271 of file sch_rtree.h.

Referenced by begin(), clear(), contains(), EE_RTREE(), end(), insert(), OfType(), Overlapping(), remove(), and ~EE_RTREE().


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