KiCad PCB EDA Suite
PNS::INDEX Class Reference

Class 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 ()
 
 ~INDEX ()
 
void Add (ITEM *aItem)
 Function Add() More...
 
void Remove (ITEM *aItem)
 Function Remove() More...
 
void Replace (ITEM *aOldItem, ITEM *aNewItem)
 Function Add() More...
 
template<class Visitor >
int Query (const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
 Function Query() More...
 
template<class Visitor >
int Query (const SHAPE *aShape, int aMinDistance, Visitor &aVisitor)
 Function Query() More...
 
void Clear ()
 Function Clear() More...
 
NET_ITEMS_LISTGetItemsForNet (int aNet)
 Function GetItemsForNet() More...
 
bool Contains (ITEM *aItem) const
 Function Contains() More...
 
int Size () const
 Function Size() More...
 
ITEM_SET::iterator begin ()
 
ITEM_SET::iterator end ()
 

Private Member Functions

template<class Visitor >
int querySingle (int index, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor)
 
ITEM_SHAPE_INDEXgetSubindex (const ITEM *aItem)
 

Private Attributes

ITEM_SHAPE_INDEXm_subIndices [MaxSubIndices]
 
std::map< int, NET_ITEMS_LISTm_netMap
 
ITEM_SET m_allItems
 

Static Private Attributes

static const int MaxSubIndices = 128
 
static const int SI_Multilayer = 2
 
static const int SI_SegDiagonal = 0
 
static const int SI_SegStraight = 1
 
static const int SI_Traces = 3
 
static const int SI_PadsTop = 0
 
static const int SI_PadsBottom = 1
 

Detailed Description

Class 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 46 of file pns_index.h.

Member Typedef Documentation

◆ ITEM_SET

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

Definition at line 51 of file pns_index.h.

◆ ITEM_SHAPE_INDEX

Definition at line 50 of file pns_index.h.

◆ NET_ITEMS_LIST

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

Definition at line 49 of file pns_index.h.

Constructor & Destructor Documentation

◆ INDEX()

PNS::INDEX::INDEX ( )

Definition at line 162 of file pns_index.h.

163 {
164  memset( m_subIndices, 0, sizeof( m_subIndices ) );
165 }
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:157

References m_subIndices.

◆ ~INDEX()

PNS::INDEX::~INDEX ( )

Definition at line 318 of file pns_index.h.

319 {
320  Clear();
321 }
void Clear()
Function Clear()
Definition: pns_index.h:305

References Clear().

Member Function Documentation

◆ Add()

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

Function Add()

Adds item to the spatial index.

Definition at line 214 of file pns_index.h.

215 {
216  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
217 
218  if( !idx )
219  return;
220 
221  idx->Add( aItem );
222  m_allItems.insert( aItem );
223  int net = aItem->Net();
224 
225  if( net >= 0 )
226  {
227  m_netMap[net].push_back( aItem );
228  }
229 }
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:50
ITEM_SET m_allItems
Definition: pns_index.h:159
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:158
ITEM_SHAPE_INDEX * getSubindex(const ITEM *aItem)
Definition: pns_index.h:167

References SHAPE_INDEX< T >::Add(), getSubindex(), m_allItems, m_netMap, and PNS::ITEM::Net().

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

◆ begin()

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

◆ Clear()

void PNS::INDEX::Clear ( )

Function Clear()

Removes all items from the index.

Definition at line 305 of file pns_index.h.

306 {
307  for( int i = 0; i < MaxSubIndices; ++i )
308  {
310 
311  if( idx )
312  delete idx;
313 
314  m_subIndices[i] = NULL;
315  }
316 }
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:50
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:157
size_t i
Definition: json11.cpp:597
static const int MaxSubIndices
Definition: pns_index.h:144

References i, m_subIndices, and MaxSubIndices.

Referenced by ~INDEX().

◆ Contains()

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

Function Contains()

Returns true if item aItem exists in the index.

Definition at line 128 of file pns_index.h.

129  {
130  return m_allItems.find( aItem ) != m_allItems.end();
131  }
ITEM_SET m_allItems
Definition: pns_index.h:159

References m_allItems.

◆ end()

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

◆ GetItemsForNet()

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

Function GetItemsForNet()

Returns list of all items in a given net.

Definition at line 323 of file pns_index.h.

324 {
325  if( m_netMap.find( aNet ) == m_netMap.end() )
326  return NULL;
327 
328  return &m_netMap[aNet];
329 }
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:158

References m_netMap.

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

◆ getSubindex()

INDEX::ITEM_SHAPE_INDEX * PNS::INDEX::getSubindex ( const ITEM aItem)
private

Definition at line 167 of file pns_index.h.

168 {
169  int idx_n = -1;
170 
171  const LAYER_RANGE l = aItem->Layers();
172 
173  switch( aItem->Kind() )
174  {
175  case ITEM::VIA_T:
176  idx_n = SI_Multilayer;
177  break;
178 
179  case ITEM::SOLID_T:
180  {
181  if( l.IsMultilayer() )
182  idx_n = SI_Multilayer;
183  else if( l.Start() == B_Cu ) // fixme: use kicad layer codes
184  idx_n = SI_PadsTop;
185  else if( l.Start() == F_Cu )
186  idx_n = SI_PadsBottom;
187  else
188  idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
189  }
190  break;
191 
192  case ITEM::SEGMENT_T:
193  case ITEM::LINE_T:
194  idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
195  break;
196 
197  default:
198  break;
199  }
200 
201  if( idx_n < 0 || idx_n >= MaxSubIndices )
202  {
203  wxASSERT( idx_n >= 0 );
204  wxASSERT( idx_n < MaxSubIndices );
205  return nullptr;
206  }
207 
208  if( !m_subIndices[idx_n] )
209  m_subIndices[idx_n] = new ITEM_SHAPE_INDEX;
210 
211  return m_subIndices[idx_n];
212 }
static const int SI_Traces
Definition: pns_index.h:148
bool IsMultilayer() const
Definition: pns_layerset.h:78
int Start() const
Definition: pns_layerset.h:83
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:50
static const int SI_SegStraight
Definition: pns_index.h:147
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:157
static const int SI_PadsBottom
Definition: pns_index.h:150
static const int SI_Multilayer
Definition: pns_index.h:145
static const int SI_PadsTop
Definition: pns_index.h:149
static const int MaxSubIndices
Definition: pns_index.h:144
Class LAYER_RANGE.
Definition: pns_layerset.h:32

References B_Cu, F_Cu, LAYER_RANGE::IsMultilayer(), PNS::ITEM::Kind(), PNS::ITEM::Layers(), PNS::ITEM::LINE_T, m_subIndices, MaxSubIndices, PNS::ITEM::SEGMENT_T, SI_Multilayer, SI_PadsBottom, SI_PadsTop, SI_SegStraight, SI_Traces, PNS::ITEM::SOLID_T, LAYER_RANGE::Start(), and PNS::ITEM::VIA_T.

Referenced by Add(), and Remove().

◆ Query() [1/2]

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

Function Query()

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 262 of file pns_index.h.

263 {
264  const SHAPE* shape = aItem->Shape();
265  int total = 0;
266 
267  total += querySingle( SI_Multilayer, shape, aMinDistance, aVisitor );
268 
269  const LAYER_RANGE layers = aItem->Layers();
270 
271  if( layers.IsMultilayer() )
272  {
273  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
274  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
275 
276  for( int i = layers.Start(); i <= layers.End(); ++i )
277  total += querySingle( SI_Traces + 2 * i + SI_SegStraight, shape, aMinDistance, aVisitor );
278  }
279  else
280  {
281  int l = layers.Start();
282 
283  if( l == B_Cu )
284  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
285  else if( l == F_Cu )
286  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
287 
288  total += querySingle( SI_Traces + 2 * l + SI_SegStraight, shape, aMinDistance, aVisitor );
289  }
290 
291  return total;
292 }
static const int SI_Traces
Definition: pns_index.h:148
bool IsMultilayer() const
Definition: pns_layerset.h:78
int Start() const
Definition: pns_layerset.h:83
int End() const
Definition: pns_layerset.h:88
static const int SI_SegStraight
Definition: pns_index.h:147
Class SHAPE.
Definition: shape.h:58
static const int SI_PadsBottom
Definition: pns_index.h:150
static const int SI_Multilayer
Definition: pns_index.h:145
size_t i
Definition: json11.cpp:597
static const int SI_PadsTop
Definition: pns_index.h:149
int querySingle(int index, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor)
Definition: pns_index.h:253
Class LAYER_RANGE.
Definition: pns_layerset.h:32

References B_Cu, LAYER_RANGE::End(), F_Cu, i, LAYER_RANGE::IsMultilayer(), PNS::ITEM::Layers(), querySingle(), PNS::ITEM::Shape(), SI_Multilayer, SI_PadsBottom, SI_PadsTop, SI_SegStraight, SI_Traces, 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 
)

Function Query()

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 295 of file pns_index.h.

296 {
297  int total = 0;
298 
299  for( int i = 0; i < MaxSubIndices; i++ )
300  total += querySingle( i, aShape, aMinDistance, aVisitor );
301 
302  return total;
303 }
size_t i
Definition: json11.cpp:597
static const int MaxSubIndices
Definition: pns_index.h:144
int querySingle(int index, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor)
Definition: pns_index.h:253

References i, MaxSubIndices, and querySingle().

◆ querySingle()

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

Definition at line 253 of file pns_index.h.

254 {
255  if( !m_subIndices[index] )
256  return 0;
257 
258  return m_subIndices[index]->Query( aShape, aMinDistance, aVisitor, false );
259 }
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:157
int Query(const SHAPE *aShape, int aMinDistance, V &aVisitor, bool aExact)
Function Query()
Definition: shape_index.h:270

References m_subIndices, and SHAPE_INDEX< T >::Query().

Referenced by Query().

◆ Remove()

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

Function Remove()

Removes an item from the spatial index.

Definition at line 231 of file pns_index.h.

232 {
233  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
234 
235  if( !idx )
236  return;
237 
238  idx->Remove( aItem );
239  m_allItems.erase( aItem );
240  int net = aItem->Net();
241 
242  if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
243  m_netMap[net].remove( aItem );
244 }
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:50
ITEM_SET m_allItems
Definition: pns_index.h:159
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:158
ITEM_SHAPE_INDEX * getSubindex(const ITEM *aItem)
Definition: pns_index.h:167

References getSubindex(), m_allItems, m_netMap, PNS::ITEM::Net(), and SHAPE_INDEX< T >::Remove().

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

◆ Replace()

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

Function Add()

Replaces one item with another.

Definition at line 246 of file pns_index.h.

247 {
248  Remove( aOldItem );
249  Add( aNewItem );
250 }
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:214
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:231

References Add(), and Remove().

◆ Size()

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

Function Size()

Returns number of items stored in the index.

Definition at line 138 of file pns_index.h.

138 { return m_allItems.size(); }
ITEM_SET m_allItems
Definition: pns_index.h:159

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 159 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 158 of file pns_index.h.

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

◆ m_subIndices

ITEM_SHAPE_INDEX* PNS::INDEX::m_subIndices[MaxSubIndices]
private

Definition at line 157 of file pns_index.h.

Referenced by Clear(), getSubindex(), INDEX(), and querySingle().

◆ MaxSubIndices

const int PNS::INDEX::MaxSubIndices = 128
staticprivate

Definition at line 144 of file pns_index.h.

Referenced by Clear(), getSubindex(), and Query().

◆ SI_Multilayer

const int PNS::INDEX::SI_Multilayer = 2
staticprivate

Definition at line 145 of file pns_index.h.

Referenced by getSubindex(), and Query().

◆ SI_PadsBottom

const int PNS::INDEX::SI_PadsBottom = 1
staticprivate

Definition at line 150 of file pns_index.h.

Referenced by getSubindex(), and Query().

◆ SI_PadsTop

const int PNS::INDEX::SI_PadsTop = 0
staticprivate

Definition at line 149 of file pns_index.h.

Referenced by getSubindex(), and Query().

◆ SI_SegDiagonal

const int PNS::INDEX::SI_SegDiagonal = 0
staticprivate

Definition at line 146 of file pns_index.h.

◆ SI_SegStraight

const int PNS::INDEX::SI_SegStraight = 1
staticprivate

Definition at line 147 of file pns_index.h.

Referenced by getSubindex(), and Query().

◆ SI_Traces

const int PNS::INDEX::SI_Traces = 3
staticprivate

Definition at line 148 of file pns_index.h.

Referenced by getSubindex(), and Query().


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