KiCad PCB EDA Suite
PNS::INDEX Class Reference

INDEX. More...

#include <pns_index.h>

Public Types

typedef std::list< ITEM * > NET_ITEMS_LIST
 
typedef SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
 
typedef std::unordered_set< ITEM * > ITEM_SET
 

Public Member Functions

 INDEX ()
 
void Add (ITEM *aItem)
 Adds item to the spatial index. More...
 
void Remove (ITEM *aItem)
 Removes an item from the spatial index. More...
 
void Replace (ITEM *aOldItem, ITEM *aNewItem)
 Replaces one item with another. More...
 
template<class Visitor >
int Query (const ITEM *aItem, int aMinDistance, Visitor &aVisitor) const
 Searches items in the index that are in proximity of aItem. More...
 
template<class Visitor >
int Query (const SHAPE *aShape, int aMinDistance, Visitor &aVisitor) const
 Searches items in the index that are in proximity of aShape. More...
 
NET_ITEMS_LISTGetItemsForNet (int aNet)
 Returns list of all items in a given net. More...
 
bool Contains (ITEM *aItem) const
 Function Contains() More...
 
int Size () const
 Returns number of items stored in the index. More...
 
ITEM_SET::iterator begin ()
 
ITEM_SET::iterator end ()
 

Private Member Functions

template<class Visitor >
int querySingle (std::size_t aIndex, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor) const
 

Private Attributes

std::deque< ITEM_SHAPE_INDEXm_subIndices
 
std::map< int, NET_ITEMS_LISTm_netMap
 
ITEM_SET m_allItems
 

Detailed Description

INDEX.

Custom spatial index, holding our board items and allowing for very fast searches. Items are assigned to separate R-Tree subindices depending on their type and spanned layers, reducing overlap and improving search time.

Definition at line 45 of file pns_index.h.

Member Typedef Documentation

◆ ITEM_SET

typedef std::unordered_set<ITEM*> PNS::INDEX::ITEM_SET

Definition at line 50 of file pns_index.h.

◆ ITEM_SHAPE_INDEX

Definition at line 49 of file pns_index.h.

◆ NET_ITEMS_LIST

typedef std::list<ITEM*> PNS::INDEX::NET_ITEMS_LIST

Definition at line 48 of file pns_index.h.

Constructor & Destructor Documentation

◆ INDEX()

PNS::INDEX::INDEX ( )
inline

Definition at line 52 of file pns_index.h.

52 {};

Member Function Documentation

◆ Add()

void PNS::INDEX::Add ( ITEM aItem)

Adds item to the spatial index.

Definition at line 28 of file pns_index.cpp.

29 {
30  const LAYER_RANGE& range = aItem->Layers();
31 
32  if( m_subIndices.size() <= static_cast<size_t>( range.End() ) )
33  m_subIndices.resize( 2 * range.End() + 1 ); // +1 handles the 0 case
34 
35  for( int i = range.Start(); i <= range.End(); ++i )
36  m_subIndices[i].Add( aItem );
37 
38  m_allItems.insert( aItem );
39  int net = aItem->Net();
40 
41  if( net >= 0 )
42  m_netMap[net].push_back( aItem );
43 }
std::deque< ITEM_SHAPE_INDEX > m_subIndices
Definition: pns_index.h:125
int Start() const
Definition: pns_layerset.h:82
int End() const
Definition: pns_layerset.h:87
ITEM_SET m_allItems
Definition: pns_index.h:127
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:126
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:31

References LAYER_RANGE::End(), PNS::ITEM::Layers(), m_allItems, m_netMap, m_subIndices, PNS::ITEM::Net(), and LAYER_RANGE::Start().

Referenced by PNS::NODE::addArc(), PNS::NODE::addSegment(), PNS::NODE::addSolid(), PNS::NODE::addVia(), PNS::NODE::Branch(), and Replace().

◆ begin()

ITEM_SET::iterator PNS::INDEX::begin ( )
inline

Definition at line 117 of file pns_index.h.

117 { return m_allItems.begin(); }
ITEM_SET m_allItems
Definition: pns_index.h:127

References m_allItems.

Referenced by PNS::NODE::GetUpdatedItems().

◆ Contains()

bool PNS::INDEX::Contains ( ITEM aItem) const
inline

Function Contains()

Returns true if item aItem exists in the index.

Definition at line 107 of file pns_index.h.

108  {
109  return m_allItems.find( aItem ) != m_allItems.end();
110  }
ITEM_SET m_allItems
Definition: pns_index.h:127

References m_allItems.

◆ end()

ITEM_SET::iterator PNS::INDEX::end ( )
inline

Definition at line 118 of file pns_index.h.

118 { return m_allItems.end(); }
ITEM_SET m_allItems
Definition: pns_index.h:127

References m_allItems.

Referenced by PNS::NODE::GetUpdatedItems().

◆ GetItemsForNet()

INDEX::NET_ITEMS_LIST * PNS::INDEX::GetItemsForNet ( int  aNet)

Returns list of all items in a given net.

Definition at line 71 of file pns_index.cpp.

72 {
73  if( m_netMap.find( aNet ) == m_netMap.end() )
74  return nullptr;
75 
76  return &m_netMap[aNet];
77 }
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:126

References m_netMap.

Referenced by PNS::NODE::AllItemsInNet(), and PNS::NODE::FindItemByParent().

◆ Query() [1/2]

template<class Visitor >
int PNS::INDEX::Query ( const ITEM aItem,
int  aMinDistance,
Visitor &  aVisitor 
) const

Searches items in the index that are in proximity of aItem.

For each item, function object aVisitor is called. Only items on overlapping layers are considered.

Parameters
aItemitem to search against
aMinDistanceproximity distance (wrs to the item's shape)
aVisitorfunction object called on each found item. Return false from the visitor to stop searching.
Returns
number of items found.

Definition at line 141 of file pns_index.h.

142 {
143  int total = 0;
144 
145  const LAYER_RANGE& layers = aItem->Layers();
146 
147  for( int i = layers.Start(); i <= layers.End(); ++i )
148  total += querySingle( i, aItem->Shape(), aMinDistance, aVisitor );
149 
150  return total;
151 }
int Start() const
Definition: pns_layerset.h:82
int End() const
Definition: pns_layerset.h:87
int querySingle(std::size_t aIndex, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor) const
Definition: pns_index.h:132
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:31

References LAYER_RANGE::End(), PNS::ITEM::Layers(), querySingle(), PNS::ITEM::Shape(), and LAYER_RANGE::Start().

Referenced by PNS::NODE::HitTest(), and PNS::NODE::QueryColliding().

◆ Query() [2/2]

template<class Visitor >
int PNS::INDEX::Query ( const SHAPE aShape,
int  aMinDistance,
Visitor &  aVisitor 
) const

Searches items in the index that are in proximity of aShape.

For each item, function object aVisitor is called. Treats all layers as colliding.

Parameters
aShapeshape to search against
aMinDistanceproximity distance (wrs to the item's shape)
aVisitorfunction object called on each found item. Return false from the visitor to stop searching.
Returns
number of items found.

Definition at line 154 of file pns_index.h.

155 {
156  int total = 0;
157 
158  for( std::size_t i = 0; i < m_subIndices.size(); ++i )
159  total += querySingle( i, aShape, aMinDistance, aVisitor );
160 
161  return total;
162 }
std::deque< ITEM_SHAPE_INDEX > m_subIndices
Definition: pns_index.h:125
int querySingle(std::size_t aIndex, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor) const
Definition: pns_index.h:132

References m_subIndices, and querySingle().

◆ querySingle()

template<class Visitor >
int PNS::INDEX::querySingle ( std::size_t  aIndex,
const SHAPE aShape,
int  aMinDistance,
Visitor &  aVisitor 
) const
private

Definition at line 132 of file pns_index.h.

133 {
134  if( aIndex >= m_subIndices.size() )
135  return 0;
136 
137  return m_subIndices[aIndex].Query( aShape, aMinDistance, aVisitor);
138 }
std::deque< ITEM_SHAPE_INDEX > m_subIndices
Definition: pns_index.h:125

References m_subIndices.

Referenced by Query().

◆ Remove()

void PNS::INDEX::Remove ( ITEM aItem)

Removes an item from the spatial index.

Definition at line 46 of file pns_index.cpp.

47 {
48  const LAYER_RANGE& range = aItem->Layers();
49 
50  if( m_subIndices.size() <= static_cast<size_t>( range.End() ) )
51  return;
52 
53  for( int i = range.Start(); i <= range.End(); ++i )
54  m_subIndices[i].Remove( aItem );
55 
56  m_allItems.erase( aItem );
57  int net = aItem->Net();
58 
59  if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
60  m_netMap[net].remove( aItem );
61 }
std::deque< ITEM_SHAPE_INDEX > m_subIndices
Definition: pns_index.h:125
int Start() const
Definition: pns_layerset.h:82
int End() const
Definition: pns_layerset.h:87
ITEM_SET m_allItems
Definition: pns_index.h:127
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:126
void Remove(ITEM *aItem)
Removes an item from the spatial index.
Definition: pns_index.cpp:46
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:31

References LAYER_RANGE::End(), PNS::ITEM::Layers(), m_allItems, m_netMap, m_subIndices, PNS::ITEM::Net(), and LAYER_RANGE::Start().

Referenced by PNS::NODE::doRemove(), and Replace().

◆ Replace()

void PNS::INDEX::Replace ( ITEM aOldItem,
ITEM aNewItem 
)

Replaces one item with another.

Definition at line 64 of file pns_index.cpp.

65 {
66  Remove( aOldItem );
67  Add( aNewItem );
68 }
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28
void Remove(ITEM *aItem)
Removes an item from the spatial index.
Definition: pns_index.cpp:46

References Add(), and Remove().

◆ Size()

int PNS::INDEX::Size ( ) const
inline

Returns number of items stored in the index.

Definition at line 115 of file pns_index.h.

115 { return m_allItems.size(); }
ITEM_SET m_allItems
Definition: pns_index.h:127

References m_allItems.

Referenced by PNS::NODE::Branch(), and PNS::NODE::GetUpdatedItems().

Member Data Documentation

◆ m_allItems

ITEM_SET PNS::INDEX::m_allItems
private

Definition at line 127 of file pns_index.h.

Referenced by Add(), begin(), Contains(), end(), Remove(), and Size().

◆ m_netMap

std::map<int, NET_ITEMS_LIST> PNS::INDEX::m_netMap
private

Definition at line 126 of file pns_index.h.

Referenced by Add(), GetItemsForNet(), and Remove().

◆ m_subIndices

std::deque<ITEM_SHAPE_INDEX> PNS::INDEX::m_subIndices
private

Definition at line 125 of file pns_index.h.

Referenced by Add(), Query(), querySingle(), and Remove().


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