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

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

Definition at line 51 of file pns_index.h.

Definition at line 50 of file pns_index.h.

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

Definition at line 49 of file pns_index.h.

Constructor & Destructor Documentation

PNS::INDEX::INDEX ( )

Definition at line 162 of file pns_index.h.

References m_subIndices.

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

Definition at line 316 of file pns_index.h.

References Clear().

317 {
318  Clear();
319 }
void Clear()
Function Clear()
Definition: pns_index.h:303

Member Function Documentation

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

Function Add()

Adds item to the spatial index.

Definition at line 212 of file pns_index.h.

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().

213 {
214  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
215 
216  if( !idx )
217  return;
218 
219  idx->Add( aItem );
220  m_allItems.insert( aItem );
221  int net = aItem->Net();
222 
223  if( net >= 0 )
224  {
225  m_netMap[net].push_back( aItem );
226  }
227 }
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
ITEM_SET::iterator PNS::INDEX::begin ( )
inline
void PNS::INDEX::Clear ( )

Function Clear()

Removes all items from the index.

Definition at line 303 of file pns_index.h.

References m_subIndices, and MaxSubIndices.

Referenced by ~INDEX().

304 {
305  for( int i = 0; i < MaxSubIndices; ++i )
306  {
307  ITEM_SHAPE_INDEX* idx = m_subIndices[i];
308 
309  if( idx )
310  delete idx;
311 
312  m_subIndices[i] = NULL;
313  }
314 }
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:50
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:157
static const int MaxSubIndices
Definition: pns_index.h:144
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.

References m_allItems.

129  {
130  return m_allItems.find( aItem ) != m_allItems.end();
131  }
ITEM_SET m_allItems
Definition: pns_index.h:159
ITEM_SET::iterator PNS::INDEX::end ( )
inline
INDEX::NET_ITEMS_LIST * PNS::INDEX::GetItemsForNet ( int  aNet)

Function GetItemsForNet()

Returns list of all items in a given net.

Definition at line 321 of file pns_index.h.

References m_netMap.

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

322 {
323  if( m_netMap.find( aNet ) == m_netMap.end() )
324  return NULL;
325 
326  return &m_netMap[aNet];
327 }
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:158
INDEX::ITEM_SHAPE_INDEX * PNS::INDEX::getSubindex ( const ITEM aItem)
private

Definition at line 167 of file pns_index.h.

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().

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  }
188  break;
189 
190  case ITEM::SEGMENT_T:
191  case ITEM::LINE_T:
192  idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
193  break;
194 
195  default:
196  break;
197  }
198 
199  if( idx_n < 0 || idx_n >= MaxSubIndices )
200  {
201  wxASSERT( idx_n >= 0 );
202  wxASSERT( idx_n < MaxSubIndices );
203  return nullptr;
204  }
205 
206  if( !m_subIndices[idx_n] )
207  m_subIndices[idx_n] = new ITEM_SHAPE_INDEX;
208 
209  return m_subIndices[idx_n];
210 }
static const int SI_Traces
Definition: pns_index.h:148
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
int Start() const
Definition: pns_layerset.h:83
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
bool IsMultilayer() const
Definition: pns_layerset.h:78
static const int MaxSubIndices
Definition: pns_index.h:144
Class LAYER_RANGE.
Definition: pns_layerset.h:32
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 260 of file pns_index.h.

References B_Cu, LAYER_RANGE::End(), F_Cu, 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().

261 {
262  const SHAPE* shape = aItem->Shape();
263  int total = 0;
264 
265  total += querySingle( SI_Multilayer, shape, aMinDistance, aVisitor );
266 
267  const LAYER_RANGE layers = aItem->Layers();
268 
269  if( layers.IsMultilayer() )
270  {
271  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
272  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
273 
274  for( int i = layers.Start(); i <= layers.End(); ++i )
275  total += querySingle( SI_Traces + 2 * i + SI_SegStraight, shape, aMinDistance, aVisitor );
276  }
277  else
278  {
279  int l = layers.Start();
280 
281  if( l == B_Cu )
282  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
283  else if( l == F_Cu )
284  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
285 
286  total += querySingle( SI_Traces + 2 * l + SI_SegStraight, shape, aMinDistance, aVisitor );
287  }
288 
289  return total;
290 }
static const int SI_Traces
Definition: pns_index.h:148
int End() const
Definition: pns_layerset.h:88
static const int SI_SegStraight
Definition: pns_index.h:147
Class SHAPE.
Definition: shape.h:57
int Start() const
Definition: pns_layerset.h:83
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
bool IsMultilayer() const
Definition: pns_layerset.h:78
int querySingle(int index, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor)
Definition: pns_index.h:251
Class LAYER_RANGE.
Definition: pns_layerset.h:32
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 293 of file pns_index.h.

References MaxSubIndices, and querySingle().

294 {
295  int total = 0;
296 
297  for( int i = 0; i < MaxSubIndices; i++ )
298  total += querySingle( i, aShape, aMinDistance, aVisitor );
299 
300  return total;
301 }
static const int MaxSubIndices
Definition: pns_index.h:144
int querySingle(int index, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor)
Definition: pns_index.h:251
template<class Visitor >
int PNS::INDEX::querySingle ( int  index,
const SHAPE aShape,
int  aMinDistance,
Visitor &  aVisitor 
)
private

Definition at line 251 of file pns_index.h.

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

Referenced by Query().

252 {
253  if( !m_subIndices[index] )
254  return 0;
255 
256  return m_subIndices[index]->Query( aShape, aMinDistance, aVisitor, false );
257 }
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
void PNS::INDEX::Remove ( ITEM aItem)

Function Remove()

Removes an item from the spatial index.

Definition at line 229 of file pns_index.h.

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

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

230 {
231  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
232 
233  if( !idx )
234  return;
235 
236  idx->Remove( aItem );
237  m_allItems.erase( aItem );
238  int net = aItem->Net();
239 
240  if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
241  m_netMap[net].remove( aItem );
242 }
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
void PNS::INDEX::Replace ( ITEM aOldItem,
ITEM aNewItem 
)

Function Add()

Replaces one item with another.

Definition at line 244 of file pns_index.h.

References Add(), and Remove().

245 {
246  Remove( aOldItem );
247  Add( aNewItem );
248 }
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:212
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:229
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.

References m_allItems.

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

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

Member Data Documentation

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().

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().

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().

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

Definition at line 144 of file pns_index.h.

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

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

Definition at line 145 of file pns_index.h.

Referenced by getSubindex(), and Query().

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

Definition at line 150 of file pns_index.h.

Referenced by getSubindex(), and Query().

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

Definition at line 149 of file pns_index.h.

Referenced by getSubindex(), and Query().

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

Definition at line 146 of file pns_index.h.

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

Definition at line 147 of file pns_index.h.

Referenced by getSubindex(), and Query().

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: