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 BOX2I &aRect) const
 
EE_TYPE Overlapping (const VECTOR2I &aPoint, int aAccuracy=0) const
 
EE_TYPE Overlapping (KICAD_T aType, const VECTOR2I &aPoint, int aAccuracy=0) const
 
EE_TYPE Overlapping (KICAD_T aType, const BOX2I &aRect) const
 
iterator begin ()
 Returns a read/write iterator that points to the first element in the EE_RTREE N.B. More...
 
iterator end ()
 Returns a read/write iterator that points to one past the last element in the EE_RTREE. More...
 
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 39 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 42 of file sch_rtree.h.

◆ iterator

using EE_RTREE::iterator = typename ee_rtree::Iterator

Definition at line 181 of file sch_rtree.h.

Constructor & Destructor Documentation

◆ EE_RTREE()

EE_RTREE::EE_RTREE ( )
inline

Definition at line 45 of file sch_rtree.h.

46 {
47 this->m_tree = new ee_rtree();
48 m_count = 0;
49 }
RTree< SCH_ITEM *, int, 3, double > ee_rtree
Definition: sch_rtree.h:42
size_t m_count
Definition: sch_rtree.h:304
ee_rtree * m_tree
Definition: sch_rtree.h:303

References m_count, and m_tree.

◆ ~EE_RTREE()

EE_RTREE::~EE_RTREE ( )
inline

Definition at line 51 of file sch_rtree.h.

52 {
53 delete this->m_tree;
54 }

References m_tree.

Member Function Documentation

◆ begin() [1/2]

iterator EE_RTREE::begin ( )
inline

Returns a read/write iterator that points to the first element in the EE_RTREE N.B.

The iteration order of the RTree is not readily apparent and will change if/when you add or move items and the RTree is re-balanced. Any exposure of the RTree contents to the user MUST be sorted before being presented. See SCH_SEXPR_PLUGIN::Format or SCH_EDITOR_CONTROL::nextMatch for examples.

Returns
Complete RTree of the screen's items

Definition at line 276 of file sch_rtree.h.

277 {
278 return m_tree->begin();
279 }

References m_tree.

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

◆ begin() [2/2]

const iterator EE_RTREE::begin ( ) const
inline

Definition at line 291 of file sch_rtree.h.

292 {
293 return m_tree->begin();
294 }

References m_tree.

◆ clear()

void EE_RTREE::clear ( )
inline

Remove all items from the RTree.

Definition at line 111 of file sch_rtree.h.

112 {
113 m_tree->RemoveAll();
114 m_count = 0;
115 }

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 125 of file sch_rtree.h.

126 {
127 BOX2I bbox = aItem->GetBoundingBox();
128
129 // Inflate a bit for safety, selection shadows, etc.
130 bbox.Inflate( aItem->GetPenWidth() );
131
132 const int type = int( aItem->Type() );
133 const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
134 const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
135 bool found = false;
136
137 auto search =
138 [&found, &aItem]( const SCH_ITEM* aSearchItem )
139 {
140 if( aSearchItem == aItem )
141 {
142 found = true;
143 return false;
144 }
145
146 return true;
147 };
148
149 m_tree->Search( mmin, mmax, search );
150
151 if( !found && aRobust )
152 {
153 // N.B. We must search the whole tree for the pointer to remove
154 // because the item may have been moved. We do not expand the item
155 // type search as this should not change.
156
157 const int mmin2[3] = { type, INT_MIN, INT_MIN };
158 const int mmax2[3] = { type, INT_MAX, INT_MAX };
159
160 m_tree->Search( mmin2, mmax2, search );
161 }
162
163 return found;
164 }
coord_type GetY() const
Definition: box2.h:181
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
coord_type GetX() const
Definition: box2.h:180
coord_type GetRight() const
Definition: box2.h:189
coord_type GetBottom() const
Definition: box2.h:190
virtual const BOX2I GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:74
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:97
Base class for any item which can be embedded within the SCHEMATIC container class,...
Definition: sch_item.h:147
virtual int GetPenWidth() const
Definition: sch_item.h:263

References BOX2< Vec >::GetBottom(), EDA_ITEM::GetBoundingBox(), SCH_ITEM::GetPenWidth(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), BOX2< Vec >::Inflate(), m_tree, and EDA_ITEM::Type().

Referenced by SCH_SCREEN::CheckIfOnDrawList().

◆ empty()

bool EE_RTREE::empty ( ) const
inline

Definition at line 176 of file sch_rtree.h.

177 {
178 return m_count == 0;
179 }

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

Returns a read/write iterator that points to one past the last element in the EE_RTREE.

Definition at line 285 of file sch_rtree.h.

286 {
287 return m_tree->end();
288 }

References m_tree.

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

◆ end() [2/2]

const iterator EE_RTREE::end ( ) const
inline

Definition at line 296 of file sch_rtree.h.

297 {
298 return m_tree->end();
299 }

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 59 of file sch_rtree.h.

60 {
61 BOX2I bbox = aItem->GetBoundingBox();
62
63 // Inflate a bit for safety, selection shadows, etc.
64 bbox.Inflate( aItem->GetPenWidth() );
65
66 const int type = int( aItem->Type() );
67 const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
68 const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
69
70 m_tree->Insert( mmin, mmax, aItem );
71 m_count++;
72 }

References BOX2< Vec >::GetBottom(), EDA_ITEM::GetBoundingBox(), SCH_ITEM::GetPenWidth(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), BOX2< Vec >::Inflate(), 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 238 of file sch_rtree.h.

239 {
240 return EE_TYPE( m_tree, aType );
241 }

References m_tree.

Referenced by SCH_EAGLE_PLUGIN::addBusEntries(), SCH_SHEET_LIST::AnnotatePowerSymbols(), SCH_EDIT_FRAME::AutoRotateItem(), SCH_EDIT_FRAME::BreakSegmentsOnJunctions(), CONNECTION_GRAPH::buildConnectionGraph(), SCH_SCREENS::buildScreenList(), SCH_SCREENS::ChangeSymbolLibNickname(), SCH_SHEET::CleanupSheet(), SCH_SHEET::CountSheets(), findItemsFromSyncSelection(), SCH_EDITOR_CONTROL::FindSymbolAndItem(), SCH_LINE_WIRE_BUS_TOOL::finishSegments(), SCH_SCREEN::HasItems(), SCH_SHEET::HasUndefinedPins(), SCH_DRAWING_TOOLS::importHierLabel(), SCH_SEXPR_PLUGIN::loadHierarchy(), SCH_LEGACY_PLUGIN::loadHierarchy(), SCH_EAGLE_PLUGIN::loadSheet(), SCH_SHEET::LocatePathOfScreen(), EDIT_POINTS_FACTORY::Make(), NETLIST_EXPORTER_XML::makeSymbols(), SCH_SHEET_LIST::MigrateSimModelNameFields(), DIALOG_SHEET_PIN_PROPERTIES::onComboBox(), DIALOG_ERC::OnERCItemRClick(), SCH_ALTIUM_PLUGIN::ParseAltiumSch(), DIALOG_CHANGE_SYMBOLS::processMatchingSymbols(), DIALOG_SYMBOL_REMAP::remapSymbolsToLibTable(), SCH_SCREEN::Remove(), SCH_EDITOR_CONTROL::RepairSchematic(), 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(), SCH_SHEET_LIST::UpdateSymbolInstances(), SIM_PLOT_FRAME::UpdateTunerValue(), and NETLIST_EXPORTER_ORCADPCB2::WriteNetlist().

◆ Overlapping() [1/4]

◆ Overlapping() [2/4]

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

Definition at line 248 of file sch_rtree.h.

249 {
250 BOX2I rect( aPoint, VECTOR2I( 0, 0 ) );
251 rect.Inflate( aAccuracy );
252 return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
253 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

References BOX2< Vec >::Inflate(), m_tree, and SCH_LOCATE_ANY_T.

◆ Overlapping() [3/4]

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

Definition at line 262 of file sch_rtree.h.

263 {
264 return EE_TYPE( m_tree, aType, aRect );
265 }

References m_tree.

◆ Overlapping() [4/4]

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

Definition at line 255 of file sch_rtree.h.

256 {
257 BOX2I rect( aPoint, VECTOR2I( 0, 0 ) );
258 rect.Inflate( aAccuracy );
259 return EE_TYPE( m_tree, aType, rect );
260 }

References BOX2< Vec >::Inflate(), and 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 78 of file sch_rtree.h.

79 {
80 // First, attempt to remove the item using its given BBox
81 BOX2I bbox = aItem->GetBoundingBox();
82
83 // Inflate a bit for safety, selection shadows, etc.
84 bbox.Inflate( aItem->GetPenWidth() );
85
86 const int type = int( aItem->Type() );
87 const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
88 const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
89
90 // If we are not successful ( true == not found ), then we expand
91 // the search to the full tree
92 if( m_tree->Remove( mmin, mmax, aItem ) )
93 {
94 // N.B. We must search the whole tree for the pointer to remove
95 // because the item may have been moved before we have the chance to
96 // delete it from the tree
97 const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
98 const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
99
100 if( m_tree->Remove( mmin2, mmax2, aItem ) )
101 return false;
102 }
103
104 m_count--;
105 return true;
106 }

References BOX2< Vec >::GetBottom(), EDA_ITEM::GetBoundingBox(), SCH_ITEM::GetPenWidth(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), BOX2< Vec >::Inflate(), 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 171 of file sch_rtree.h.

172 {
173 return m_count;
174 }

References m_count.

Member Data Documentation

◆ m_count

size_t EE_RTREE::m_count
private

Definition at line 304 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 303 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: