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 (const SCH_ITEM *aItem, bool aRobust=false) const
	Determine if a given item exists in the tree. More...

size_t	size () const
	Returns 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)

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_rtree *	m_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.

     {
         this->m_tree = new ee_rtree();
         m_count      = 0;
     }

References m_count, and m_tree.

◆ ~EE_RTREE()

EE_RTREE::~EE_RTREE ( )

inline

Definition at line 53 of file sch_rtree.h.

     {
         delete this->m_tree;
     }

References m_tree.

Member Function Documentation

◆ begin() [1/2]

iterator EE_RTREE::begin ( )

inline

Definition at line 248 of file sch_rtree.h.

     {
         return m_tree->begin();
     }

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

     {
         return m_tree->begin();
     }

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.

     {
         m_tree->RemoveAll();
         m_count = 0;
     }

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

aItem	Item that may potentially exist in the tree
aRobust	If 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.

     {
         const EDA_RECT& bbox    = aItem->GetBoundingBox();
         const int       type    = int( aItem->Type() );
         const int       mmin[3] = { type, bbox.GetX(), bbox.GetY() };
         const int       mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
         bool            found   = false;
 
         auto search = [&found, &aItem]( const SCH_ITEM* aSearchItem ) {
             if( aSearchItem == aItem )
             {
                 found = true;
                 return false;
             }
 
             return true;
         };
 
         m_tree->Search( mmin, mmax, search );
 
         if( !found && aRobust )
         {
             // N.B. We must search the whole tree for the pointer to remove
             // because the item may have been moved.  We do not expand the item
             // type search as this should not change.
 
             const int mmin2[3] = { type, INT_MIN, INT_MIN };
             const int mmax2[3] = { type, INT_MAX, INT_MAX };
 
             m_tree->Search( mmin2, mmax2, search );
         }
 
         return found;
     }

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

     {
         return m_count == 0;
     }

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

     {
         return m_tree->end();
     }

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

     {
         return m_tree->end();
     }

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.

     {
         const EDA_RECT& bbox    = aItem->GetBoundingBox();
         const int       type    = int( aItem->Type() );
         const int       mmin[3] = { type, bbox.GetX(), bbox.GetY() };
         const int       mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
 
         m_tree->Insert( mmin, mmax, aItem );
         m_count++;
     }

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

     {
         return EE_TYPE( m_tree, aType );
     }

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::FindComponentAndItem(), 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_SHEET_LIST::ReplaceLegacySheetPaths(), 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 )

inline

Definition at line 224 of file sch_rtree.h.

     {
         return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, aRect );
     }

References m_tree, and SCH_LOCATE_ANY_T.

Referenced by SCH_EDIT_FRAME::BreakSegments(), SCH_EDIT_FRAME::DeleteJunction(), SCH_MOVE_TOOL::getConnectedDragItems(), AUTOPLACER::getPossibleCollisions(), SCH_LINE_WIRE_BUS_TOOL::getSheetPin(), SCH_SCREEN::IsJunctionNeeded(), and SCH_EDIT_FRAME::TrimWire().

◆ Overlapping() [2/4]

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

inline

Definition at line 229 of file sch_rtree.h.

     {
         EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
         rect.Inflate( aAccuracy );
         return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
     }

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.

     {
         EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
         rect.Inflate( aAccuracy );
         return EE_TYPE( m_tree, aType, rect );
     }

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.

     {
         return EE_TYPE( m_tree, aType, aRect );
     }

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.

     {
         // First, attempt to remove the item using its given BBox
         const EDA_RECT& bbox    = aItem->GetBoundingBox();
         const int       type    = int( aItem->Type() );
         const int       mmin[3] = { type, bbox.GetX(), bbox.GetY() };
         const int       mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
 
         // If we are not successful ( true == not found ), then we expand
         // the search to the full tree
         if( m_tree->Remove( mmin, mmax, aItem ) )
         {
             // N.B. We must search the whole tree for the pointer to remove
             // because the item may have been moved before we have the chance to
             // delete it from the tree
             const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
             const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
 
             if( m_tree->Remove( mmin2, mmax2, aItem ) )
                 return false;
         }
 
         m_count--;
         return true;
     }

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

Returns the number of items in the tree.

Returns: number of elements in the tree;

Definition at line 161 of file sch_rtree.h.

     {
         return m_count;
     }

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:

sch_rtree.h

Classes

Public Types

Public Member Functions

Private Types

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ee_rtree

◆ iterator

Constructor & Destructor Documentation

◆ EE_RTREE()

◆ ~EE_RTREE()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ contains()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ insert()

◆ OfType()

◆ Overlapping() [1/4]

◆ Overlapping() [2/4]

◆ Overlapping() [3/4]

◆ Overlapping() [4/4]

◆ remove()

◆ size()

Member Data Documentation

◆ m_count

◆ m_tree