KiCad PCB EDA Suite
Loading...
Searching...
No Matches
Classes | Public Member Functions | Private Types | Private Attributes | List of all members
EE_RTREE Class Reference

Implement 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 Member Functions

 EE_RTREE ()=default
 
 EE_RTREE (const EE_RTREE &)=delete
 
EE_RTREE & operator= (const EE_RTREE &)=delete
 
 EE_RTREE (EE_RTREE &&aOther) noexcept
 
EE_RTREE & operator= (EE_RTREE &&aOther) noexcept
 
 ~EE_RTREE ()=default
 
void insert (SCH_ITEM *aItem)
 Insert an item into the tree.
 
bool remove (SCH_ITEM *aItem)
 Remove an item from the tree.
 
void clear ()
 Remove all items from the RTree.
 
bool contains (const SCH_ITEM *aItem, bool aRobust=false) const
 Determine if a given item exists in the tree.
 
size_t size () const
 Return the number of items in the tree.
 
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
 
ee_rtree::Iterator begin () const
 Return a read/write iterator that points to the first.
 
ee_rtree::Iterator end () const
 Return a read/write iterator that points to one past the last element in the EE_RTREE.
 

Private Types

using ee_rtree = KIRTREE::DYNAMIC_RTREE<SCH_ITEM*, int, 3>
 

Private Attributes

ee_rtree m_tree
 
std::unordered_multiset< const SCH_ITEM * > m_members
 

Detailed Description

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

Non-owning.

Definition at line 36 of file sch_rtree.h.

Member Typedef Documentation

◆ ee_rtree

using EE_RTREE::ee_rtree = KIRTREE::DYNAMIC_RTREE<SCH_ITEM*, int, 3>
private

Definition at line 39 of file sch_rtree.h.

Constructor & Destructor Documentation

◆ EE_RTREE() [1/3]

EE_RTREE::EE_RTREE ( )
default

Referenced by EE_RTREE(), EE_RTREE(), operator=(), and operator=().

◆ EE_RTREE() [2/3]

EE_RTREE::EE_RTREE ( const EE_RTREE & )
delete

References EE_RTREE().

◆ EE_RTREE() [3/3]

EE_RTREE::EE_RTREE ( EE_RTREE && aOther)
inlinenoexcept

Definition at line 46 of file sch_rtree.h.

References EE_RTREE().

◆ ~EE_RTREE()

EE_RTREE::~EE_RTREE ( )
default

Member Function Documentation

◆ begin()

ee_rtree::Iterator EE_RTREE::begin ( ) const
inline

Return a read/write iterator that points to the first.

element in the EE_RTREE.

Note
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_IO_KICAD_SEXPR::Format() or SCH_EDITOR_CONTROL::nextMatch() for examples.
Returns
Complete RTree of the screen's items.

Definition at line 288 of file sch_rtree.h.

References m_tree.

Referenced by CADSTAR_SCH_ARCHIVE_LOADER::Load(), and SCH_IO_EAGLE::loadSheet().

◆ clear()

void EE_RTREE::clear ( )
inline

Remove all items from the RTree.

Definition at line 124 of file sch_rtree.h.

References m_members, and m_tree.

Referenced by BOOST_AUTO_TEST_CASE().

◆ contains()

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

Determine if a given item exists in the tree.

Note
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, use exact pointer membership without evaluating the bounding box.
Returns
true if the item definitely exists, false if it does not exist within bbox.

Definition at line 140 of file sch_rtree.h.

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

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and SCH_EDIT_FRAME::onNetNavigatorSelection().

◆ empty()

bool EE_RTREE::empty ( ) const
inline

Definition at line 182 of file sch_rtree.h.

References m_members.

Referenced by SCH_EDIT_FRAME::setupUIConditions().

◆ end()

ee_rtree::Iterator EE_RTREE::end ( ) const
inline

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

Definition at line 296 of file sch_rtree.h.

References m_tree.

Referenced by CADSTAR_SCH_ARCHIVE_LOADER::Load(), and SCH_IO_EAGLE::loadSheet().

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

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

Referenced by JUNCTION_HELPERS::AnalyzePoint(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), and PADS_SCH_BINARY::PADS_SCH_BINARY_BUILDER::Build().

◆ OfType()

EE_TYPE EE_RTREE::OfType ( KICAD_T aType) const
inline

Definition at line 248 of file sch_rtree.h.

References m_tree.

Referenced by SCH_IO_EAGLE::addBusEntries(), AlignSchematicItemsToGrid(), SCH_SHEET_LIST::AnnotatePowerSymbols(), KICAD_DIFF::SCH_MERGE_APPLIER::Apply(), SCH_EDIT_FRAME::AutoRotateItem(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), SCH_LINE_WIRE_BUS_TOOL::BreakSegmentsOnJunctions(), PADS_SCH_BINARY::PADS_SCH_BINARY_BUILDER::Build(), SCH_CONNECTIVITY::NETCHAIN_MANAGER::buildBridgeAdjacency(), CONNECTION_GRAPH::buildConnectionGraph(), ISSUE22864_FIXTURE::BuildPositionToWiresMap(), SCH_SCREENS::buildScreenList(), SCH_SCREENS::ChangeSymbolLibNickname(), SCHEMATIC::CleanUp(), collectImportedRefs(), DIPTRACE_SCH_IMPORT_FIXTURE::CountFilledPolysForRefdes(), DIPTRACE_SCH_IMPORT_FIXTURE::CountJunctionsOnSheet(), DIPTRACE_SCH_IMPORT_FIXTURE::CountLabelsOnSheet(), DIPTRACE_SCH_IMPORT_FIXTURE::CountLinesOnSheet(), DIPTRACE_SCH_IMPORT_FIXTURE::CountOpenPolysWithPointCountForRefdes(), DIPTRACE_SCH_IMPORT_FIXTURE::CountSheetGraphicLines(), DIPTRACE_SCH_IMPORT_FIXTURE::CountSymbolsForRefdesOnSheet(), DIPTRACE_SCH_IMPORT_FIXTURE::CountSymbolShapes(), SCH_IO_ALTIUM::CreateAliases(), SCH_IO_ALTIUM::EnsureSheetSymbolNames(), SCH_SELECTION_TOOL::expandConnectionWithGraph(), DIPTRACE_SCH_IMPORT_FIXTURE::FieldHorizJustify(), DIPTRACE_SCH_IMPORT_FIXTURE::FieldPosForRefdes(), findConvertedSymbol(), findItemsFromSyncSelection(), findSubSheetScreen(), SCH_EDITOR_CONTROL::FindSymbolAndItem(), TEST_ISSUE22286_FIXTURE::FindSymbolByRef(), PCAD_SCH_IMPORT_FIXTURE::forEachItemOfType(), DIPTRACE_SCH_IMPORT_FIXTURE::GetFieldValueForRefdes(), TEST_SCH_SYMBOL_FIXTURE::GetFirstSymbol(), DIPTRACE_SCH_IMPORT_FIXTURE::GetFootprintForRefdes(), TEST_VARIANT_FIELD_RESOLUTION_FIXTURE::GetR1(), DIPTRACE_SCH_IMPORT_FIXTURE::GetSheetNameForRefdes(), TEST_AUTOPLACE_FIELDS_FIXTURE::GetSymbolByRef(), GetSymbolReferences(), DIPTRACE_SCH_IMPORT_FIXTURE::HasLabelOnSheet(), DIPTRACE_SCH_IMPORT_FIXTURE::HasLabelStartingWithOnSheet(), SCH_DRAWING_TOOLS::importHierLabel(), SCH_DRAWING_TOOLS::importHierLabels(), EESCHEMA_JOBS_HANDLER::JobImport(), DIPTRACE_SCH_IMPORT_FIXTURE::LabelConnectsToWireOnSheet(), DIPTRACE_SCH_IMPORT_FIXTURE::LibPinCountForRefdesUnitOnSheet(), DIPTRACE_SCH_IMPORT_FIXTURE::LibPinNamesForRefdesUnitOnSheet(), SCH_IO_KICAD_LEGACY::loadHierarchy(), SCH_IO_KICAD_SEXPR::loadHierarchy(), SCH_IO_EAGLE::loadModuleInstance(), SCH_IO_ALTIUM::LoadSchematicFile(), SCH_IO_EAGLE::loadSheet(), DIPTRACE_SCH_IMPORT_FIXTURE::MaxPinCountForRefdes(), PADS_SCH::PADS_SCH_SYMBOL_BUILDER::NextFreePowerOrdinal(), SCH_IO_ALTIUM::NormalizeRepeatedSheetInstances(), DIALOG_SHEET_PIN_PROPERTIES::onComboBox(), SCH_IO_ALTIUM::ParseAltiumSch(), SCH_IO_ALTIUM::ParseSheetName(), DIPTRACE_SCH_IMPORT_FIXTURE::PinOrientationCounts(), SCH_IO_ALTIUM::PostProcessBusLabels(), DIALOG_CHANGE_SYMBOLS::processMatchingSymbols(), SCH_CONNECTIVITY::NETCHAIN_MANAGER::rebuild(), ORCAD_CONVERTER::recordNetNameMap(), DIPTRACE_SCH_IMPORT_FIXTURE::RefValueFieldSeparation(), ISSUE24858_FIXTURE::reload(), PIN_MAP_OVERRIDE_FIXTURE::reload(), DIALOG_SYMBOL_REMAP::remapSymbolsToLibTable(), ORCAD_CONVERTER::rememberInterfaceLabelSource(), SCH_CONNECTIVITY::NETCHAIN_MANAGER::resolveTerminals(), ISSUE22864_FIXTURE::RunAlignmentAndVerify(), ISSUE22864_FIXTURE::RunAlignmentAndVerifyNoSkew(), EESCHEMA_JOBS_HANDLER::runSchMerge(), SCH_EDIT_FRAME::SaveProject(), SCH_LABEL_BASE::SetLabelShape(), DIPTRACE_SCH_IMPORT_FIXTURE::ShowsPinNames(), ERC_TESTER::TestDuplicatePinNets(), ERC_TESTER::TestDuplicateSheetNames(), ERC_TESTER::TestEmptyLabelNames(), ERC_TESTER::TestFieldNameWhitespace(), ERC_TESTER::TestFourWayJunction(), ERC_TESTER::TestGroundPins(), ERC_TESTER::TestStackedPinNotation(), ERC_TESTER::TestTextVars(), ERC_TESTER::TestVariantSymbols(), DIALOG_SHEET_PIN_PROPERTIES::TransferDataToWindow(), UniqueGroupName(), UniqueSheetName(), DIPTRACE_SCH_IMPORT_FIXTURE::UnitCountForRefdes(), DIPTRACE_SCH_IMPORT_FIXTURE::UnitsForRefdesOnSheet(), DIALOG_CHANGE_SYMBOLS::updateFieldsList(), SCH_SHEET_LIST::UpdateSymbolInstanceData(), and DIPTRACE_SCH_IMPORT_FIXTURE::ValueFieldAngleDegrees().

◆ operator=() [1/2]

EE_RTREE & EE_RTREE::operator= ( const EE_RTREE & )
delete

References EE_RTREE().

◆ operator=() [2/2]

EE_RTREE & EE_RTREE::operator= ( EE_RTREE && aOther)
inlinenoexcept

Definition at line 53 of file sch_rtree.h.

References EE_RTREE(), m_members, and m_tree.

◆ Overlapping() [1/4]

EE_TYPE EE_RTREE::Overlapping ( const BOX2I & aRect) const
inline

Definition at line 253 of file sch_rtree.h.

References m_tree, and SCH_LOCATE_ANY_T.

Referenced by JUNCTION_HELPERS::AnalyzePoint(), SCH_CONNECTIVITY::NETCHAIN_MANAGER::buildBridgeAdjacency(), SCH_LINE::BuildWireWithHopShape(), SCH_COLLECTOR::Collect(), SCH_IO_ALTIUM::CreateAliases(), SCH_EDIT_FRAME::DeleteJunction(), SCH_LINE_WIRE_BUS_TOOL::doUnfoldBus(), CONNECTION_GRAPH::ercCheckNoConnects(), SCH_SELECTION_TOOL::expandConnectionWithGraph(), SCH_MOVE_TOOL::getConnectedDragItems(), SCH_MOVE_TOOL::getConnectedItems(), SCH_SHEET::GetNoConnects(), SCH_LINE_WIRE_BUS_TOOL::getSheetPin(), SCH_EDIT_TOOL::Mirror(), SCH_IO_EAGLE::moveLabels(), SCH_IO_ALTIUM::PostProcessBusLabels(), SCH_DRAG_NET_COLLISION_MONITOR::recordOriginalConnections(), SCH_RULE_AREA::RefreshContainedItemsAndDirectives(), SCH_EDIT_TOOL::Rotate(), SCH_LINE_WIRE_BUS_TOOL::TrimOverLappingWires(), SCH_EDIT_FRAME::TrimWire(), and CONNECTION_GRAPH::updateItemConnectivity().

◆ Overlapping() [2/4]

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

Definition at line 258 of file sch_rtree.h.

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

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

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

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

Referenced by BOOST_AUTO_TEST_CASE(), and PADS_SCH_BINARY::PADS_SCH_BINARY_BUILDER::Build().

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

References m_members.

Referenced by JUNCTION_HELPERS::AnalyzePoint(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

Member Data Documentation

◆ m_members

std::unordered_multiset<const SCH_ITEM*> EE_RTREE::m_members
private

Definition at line 304 of file sch_rtree.h.

Referenced by clear(), contains(), empty(), insert(), operator=(), 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(), end(), insert(), OfType(), operator=(), Overlapping(), Overlapping(), Overlapping(), Overlapping(), and remove().

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