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 boost::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 45 of file pns_index.h.

Member Typedef Documentation

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

Definition at line 50 of file pns_index.h.

Definition at line 49 of file pns_index.h.

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

Definition at line 48 of file pns_index.h.

Constructor & Destructor Documentation

PNS::INDEX::INDEX ( )

Definition at line 161 of file pns_index.h.

References m_subIndices.

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

Definition at line 315 of file pns_index.h.

References Clear().

316 {
317  Clear();
318 }
void Clear()
Function Clear()
Definition: pns_index.h:302

Member Function Documentation

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

Function Add()

Adds item to the spatial index.

Definition at line 211 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().

212 {
213  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
214 
215  if( !idx )
216  return;
217 
218  idx->Add( aItem );
219  m_allItems.insert( aItem );
220  int net = aItem->Net();
221 
222  if( net >= 0 )
223  {
224  m_netMap[net].push_back( aItem );
225  }
226 }
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:49
ITEM_SET m_allItems
Definition: pns_index.h:158
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:157
ITEM_SHAPE_INDEX * getSubindex(const ITEM *aItem)
Definition: pns_index.h:166
ITEM_SET::iterator PNS::INDEX::begin ( )
inline
void PNS::INDEX::Clear ( )

Function Clear()

Removes all items from the index.

Definition at line 302 of file pns_index.h.

References m_subIndices, and MaxSubIndices.

Referenced by ~INDEX().

303 {
304  for( int i = 0; i < MaxSubIndices; ++i )
305  {
306  ITEM_SHAPE_INDEX* idx = m_subIndices[i];
307 
308  if( idx )
309  delete idx;
310 
311  m_subIndices[i] = NULL;
312  }
313 }
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:49
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:156
static const int MaxSubIndices
Definition: pns_index.h:143
bool PNS::INDEX::Contains ( ITEM aItem) const
inline

Function Contains()

Returns true if item aItem exists in the index.

Definition at line 127 of file pns_index.h.

References m_allItems.

128  {
129  return m_allItems.find( aItem ) != m_allItems.end();
130  }
ITEM_SET m_allItems
Definition: pns_index.h:158
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 320 of file pns_index.h.

References m_netMap.

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

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

Definition at line 166 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().

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

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

References MaxSubIndices, and querySingle().

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

Definition at line 250 of file pns_index.h.

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

Referenced by Query().

251 {
252  if( !m_subIndices[index] )
253  return 0;
254 
255  return m_subIndices[index]->Query( aShape, aMinDistance, aVisitor, false );
256 }
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:156
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 228 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().

229 {
230  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
231 
232  if( !idx )
233  return;
234 
235  idx->Remove( aItem );
236  m_allItems.erase( aItem );
237  int net = aItem->Net();
238 
239  if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
240  m_netMap[net].remove( aItem );
241 }
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:49
ITEM_SET m_allItems
Definition: pns_index.h:158
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:157
ITEM_SHAPE_INDEX * getSubindex(const ITEM *aItem)
Definition: pns_index.h:166
void PNS::INDEX::Replace ( ITEM aOldItem,
ITEM aNewItem 
)

Function Add()

Replaces one item with another.

Definition at line 243 of file pns_index.h.

References Add(), and Remove().

244 {
245  Remove( aOldItem );
246  Add( aNewItem );
247 }
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:211
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:228
int PNS::INDEX::Size ( ) const
inline

Function Size()

Returns number of items stored in the index.

Definition at line 137 of file pns_index.h.

References m_allItems.

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

137 { return m_allItems.size(); }
ITEM_SET m_allItems
Definition: pns_index.h:158

Member Data Documentation

ITEM_SET PNS::INDEX::m_allItems
private

Definition at line 158 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 157 of file pns_index.h.

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

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

Definition at line 156 of file pns_index.h.

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

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

Definition at line 143 of file pns_index.h.

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

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

Definition at line 144 of file pns_index.h.

Referenced by getSubindex(), and Query().

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

Definition at line 149 of file pns_index.h.

Referenced by getSubindex(), and Query().

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

Definition at line 148 of file pns_index.h.

Referenced by getSubindex(), and Query().

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

Definition at line 145 of file pns_index.h.

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

Definition at line 146 of file pns_index.h.

Referenced by getSubindex(), and Query().

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

Definition at line 147 of file pns_index.h.

Referenced by getSubindex(), and Query().


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