KiCad PCB EDA Suite
EE_RTREE Class Reference

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)
 Insert an item into the tree. More...
 
bool remove (SCH_ITEM *aItem)
 Remove an item from the tree. More...
 
void clear ()
 Remove all items from the RTree. More...
 
bool contains (const SCH_ITEM *aItem, bool aRobust=false) const
 Determine if a given item exists in the tree. More...
 
size_t size () const
 Return the number of items in the tree. More...
 
bool empty () const
 
EE_TYPE OfType (KICAD_T aType) const
 
EE_TYPE Overlapping (const EDA_RECT &aRect) const
 
EE_TYPE Overlapping (const wxPoint &aPoint, int aAccuracy=0) const
 
EE_TYPE Overlapping (KICAD_T aType, const wxPoint &aPoint, int aAccuracy=0) const
 
EE_TYPE Overlapping (KICAD_T aType, const EDA_RECT &aRect) const
 
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

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

Non-owning.

Definition at line 40 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 43 of file sch_rtree.h.

◆ iterator

using EE_RTREE::iterator = typename ee_rtree::Iterator

Definition at line 168 of file sch_rtree.h.

Constructor & Destructor Documentation

◆ EE_RTREE()

EE_RTREE::EE_RTREE ( )
inline

Definition at line 46 of file sch_rtree.h.

47  {
48  this->m_tree = new ee_rtree();
49  m_count = 0;
50  }
ee_rtree * m_tree
Definition: sch_rtree.h:268
RTree< SCH_ITEM *, int, 3, double > ee_rtree
Definition: sch_rtree.h:43
size_t m_count
Definition: sch_rtree.h:269

References m_count, and m_tree.

◆ ~EE_RTREE()

EE_RTREE::~EE_RTREE ( )
inline

Definition at line 52 of file sch_rtree.h.

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

References m_tree.

Member Function Documentation

◆ begin() [1/2]

iterator EE_RTREE::begin ( )
inline

Definition at line 245 of file sch_rtree.h.

246  {
247  return m_tree->begin();
248  }
ee_rtree * m_tree
Definition: sch_rtree.h:268

References m_tree.

Referenced by SCH_SCREEN::FreeDrawList(), and CADSTAR_SCH_ARCHIVE_LOADER::Load().

◆ begin() [2/2]

const iterator EE_RTREE::begin ( ) const
inline

Definition at line 256 of file sch_rtree.h.

257  {
258  return m_tree->begin();
259  }
ee_rtree * m_tree
Definition: sch_rtree.h:268

References m_tree.

◆ clear()

void EE_RTREE::clear ( )
inline

Remove all items from the RTree.

Definition at line 104 of file sch_rtree.h.

105  {
106  m_tree->RemoveAll();
107  m_count = 0;
108  }
ee_rtree * m_tree
Definition: sch_rtree.h:268
size_t m_count
Definition: sch_rtree.h:269

References m_count, and m_tree.

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

◆ contains()

bool EE_RTREE::contains ( const SCH_ITEM aItem,
bool  aRobust = false 
) const
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 118 of file sch_rtree.h.

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

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 ( ) const
inline

Definition at line 163 of file sch_rtree.h.

164  {
165  return m_count == 0;
166  }
size_t m_count
Definition: sch_rtree.h:269

References m_count.

Referenced by SCH_EDIT_TOOL::Init(), SCH_SCREEN::IsEmpty(), and SCH_EDIT_FRAME::setupUIConditions().

◆ end() [1/2]

iterator EE_RTREE::end ( )
inline

Definition at line 250 of file sch_rtree.h.

251  {
252  return m_tree->end();
253  }
ee_rtree * m_tree
Definition: sch_rtree.h:268

References m_tree.

Referenced by SCH_SCREEN::FreeDrawList(), and CADSTAR_SCH_ARCHIVE_LOADER::Load().

◆ end() [2/2]

const iterator EE_RTREE::end ( ) const
inline

Definition at line 261 of file sch_rtree.h.

262  {
263  return m_tree->end();
264  }
ee_rtree * m_tree
Definition: sch_rtree.h:268

References m_tree.

◆ insert()

void EE_RTREE::insert ( SCH_ITEM aItem)
inline

Insert an item into the tree.

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

Definition at line 60 of file sch_rtree.h.

61  {
62  const EDA_RECT& bbox = aItem->GetBoundingBox();
63  const int type = int( aItem->Type() );
64  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
65  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
66 
67  m_tree->Insert( mmin, mmax, aItem );
68  m_count++;
69  }
int GetX() const
Definition: eda_rect.h:103
int GetBottom() const
Definition: eda_rect.h:119
ee_rtree * m_tree
Definition: sch_rtree.h:268
int GetRight() const
Definition: eda_rect.h:116
size_t m_count
Definition: sch_rtree.h:269
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:104
virtual const EDA_RECT GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:73
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:163

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) const
inline

Definition at line 216 of file sch_rtree.h.

217  {
218  return EE_TYPE( m_tree, aType );
219  }
ee_rtree * m_tree
Definition: sch_rtree.h:268

References m_tree.

Referenced by SCH_SHEET_LIST::AnnotatePowerSymbols(), SCH_EDIT_FRAME::BreakSegmentsOnJunctions(), CONNECTION_GRAPH::buildConnectionGraph(), SCH_SCREENS::buildScreenList(), SCH_SCREENS::ChangeSymbolLibNickname(), SCH_SHEET::CleanupSheet(), EE_COLLECTOR::Collect(), SCH_SHEET::CountSheets(), SCH_EDIT_FRAME::DeleteAnnotation(), SCH_EDITOR_CONTROL::FindSymbolAndItem(), SCH_LINE_WIRE_BUS_TOOL::finishSegments(), SCH_EDIT_FRAME::FixupJunctions(), SCH_SCREEN::HasItems(), SCH_SCREENS::HasNoFullyDefinedLibIds(), SCH_SHEET::HasUndefinedPins(), SCH_DRAWING_TOOLS::importHierLabel(), SCH_SEXPR_PLUGIN::loadHierarchy(), SCH_LEGACY_PLUGIN::loadHierarchy(), SCH_EDIT_FRAME::LoadSheetFromFile(), SCH_SHEET::LocatePathOfScreen(), EDIT_POINTS_FACTORY::Make(), NETLIST_EXPORTER_XML::makeSymbols(), DIALOG_SHEET_PIN_PROPERTIES::onComboBox(), DIALOG_ERC::OnERCItemRClick(), DIALOG_CHANGE_SYMBOLS::processMatchingSymbols(), NETLIST_EXPORTER_PSPICE::ProcessNetlist(), DIALOG_SYMBOL_REMAP::remapSymbolsToLibTable(), SCH_EDIT_FRAME::SaveProject(), SCH_EDIT_FRAME::SchematicCleanUp(), SCH_SHEET::SearchHierarchy(), SCH_SHEET::SymbolCount(), ERC_TESTER::TestDuplicateSheetNames(), DIALOG_ERC::testErc(), ERC_TESTER::TestTextVars(), DIALOG_SHEET_PROPERTIES::TransferDataFromWindow(), DIALOG_SHEET_PIN_PROPERTIES::TransferDataToWindow(), DIALOG_CHANGE_SYMBOLS::updateFieldsList(), and NETLIST_EXPORTER_ORCADPCB2::WriteNetlist().

◆ Overlapping() [1/4]

EE_TYPE EE_RTREE::Overlapping ( const EDA_RECT aRect) const
inline

◆ Overlapping() [2/4]

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

Definition at line 226 of file sch_rtree.h.

227  {
228  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
229  rect.Inflate( aAccuracy );
230  return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
231  }
ee_rtree * m_tree
Definition: sch_rtree.h:268
Handle the component boundary box.
Definition: eda_rect.h:42

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 
) const
inline

Definition at line 233 of file sch_rtree.h.

234  {
235  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
236  rect.Inflate( aAccuracy );
237  return EE_TYPE( m_tree, aType, rect );
238  }
ee_rtree * m_tree
Definition: sch_rtree.h:268
Handle the component boundary box.
Definition: eda_rect.h:42

References EDA_RECT::Inflate(), and m_tree.

◆ Overlapping() [4/4]

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

Definition at line 240 of file sch_rtree.h.

241  {
242  return EE_TYPE( m_tree, aType, aRect );
243  }
ee_rtree * m_tree
Definition: sch_rtree.h:268

References m_tree.

◆ remove()

bool EE_RTREE::remove ( SCH_ITEM aItem)
inline

Remove an item from the tree.

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

Definition at line 75 of file sch_rtree.h.

76  {
77  // First, attempt to remove the item using its given BBox
78  const EDA_RECT& bbox = aItem->GetBoundingBox();
79  const int type = int( aItem->Type() );
80  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
81  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
82 
83  // If we are not successful ( true == not found ), then we expand
84  // the search to the full tree
85  if( m_tree->Remove( mmin, mmax, aItem ) )
86  {
87  // N.B. We must search the whole tree for the pointer to remove
88  // because the item may have been moved before we have the chance to
89  // delete it from the tree
90  const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
91  const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
92 
93  if( m_tree->Remove( mmin2, mmax2, aItem ) )
94  return false;
95  }
96 
97  m_count--;
98  return true;
99  }
int GetX() const
Definition: eda_rect.h:103
int GetBottom() const
Definition: eda_rect.h:119
ee_rtree * m_tree
Definition: sch_rtree.h:268
int GetRight() const
Definition: eda_rect.h:116
size_t m_count
Definition: sch_rtree.h:269
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:104
virtual const EDA_RECT GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:73
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:163

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 ( ) const
inline

Return the number of items in the tree.

Returns
number of elements in the tree.

Definition at line 158 of file sch_rtree.h.

159  {
160  return m_count;
161  }
size_t m_count
Definition: sch_rtree.h:269

References m_count.

Member Data Documentation

◆ m_count

size_t EE_RTREE::m_count
private

Definition at line 269 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 268 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: