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

References Clear().

315 {
316  Clear();
317 }
void Clear()
Function Clear()
Definition: pns_index.h:301

Member Function Documentation

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

Function Add()

Adds item to the spatial index.

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

211 {
212  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
213 
214  if( !idx )
215  return;
216 
217  idx->Add( aItem );
218  m_allItems.insert( aItem );
219  int net = aItem->Net();
220 
221  if( net >= 0 )
222  {
223  m_netMap[net].push_back( aItem );
224  }
225 }
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 301 of file pns_index.h.

References m_subIndices, and MaxSubIndices.

Referenced by ~INDEX().

302 {
303  for( int i = 0; i < MaxSubIndices; ++i )
304  {
305  ITEM_SHAPE_INDEX* idx = m_subIndices[i];
306 
307  if( idx )
308  delete idx;
309 
310  m_subIndices[i] = NULL;
311  }
312 }
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 319 of file pns_index.h.

References m_netMap.

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

320 {
321  if( m_netMap.find( aNet ) == m_netMap.end() )
322  return NULL;
323 
324  return &m_netMap[aNet];
325 }
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  assert( false );
201  return nullptr;
202  }
203 
204  if( !m_subIndices[idx_n] )
205  m_subIndices[idx_n] = new ITEM_SHAPE_INDEX;
206 
207  return m_subIndices[idx_n];
208 }
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 258 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().

259 {
260  const SHAPE* shape = aItem->Shape();
261  int total = 0;
262 
263  total += querySingle( SI_Multilayer, shape, aMinDistance, aVisitor );
264 
265  const LAYER_RANGE layers = aItem->Layers();
266 
267  if( layers.IsMultilayer() )
268  {
269  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
270  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
271 
272  for( int i = layers.Start(); i <= layers.End(); ++i )
273  total += querySingle( SI_Traces + 2 * i + SI_SegStraight, shape, aMinDistance, aVisitor );
274  }
275  else
276  {
277  int l = layers.Start();
278 
279  if( l == B_Cu )
280  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
281  else if( l == F_Cu )
282  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
283 
284  total += querySingle( SI_Traces + 2 * l + SI_SegStraight, shape, aMinDistance, aVisitor );
285  }
286 
287  return total;
288 }
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:249
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 291 of file pns_index.h.

References MaxSubIndices, and querySingle().

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

Definition at line 249 of file pns_index.h.

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

Referenced by Query().

250 {
251  if( !m_subIndices[index] )
252  return 0;
253 
254  return m_subIndices[index]->Query( aShape, aMinDistance, aVisitor, false );
255 }
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 227 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().

228 {
229  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
230 
231  if( !idx )
232  return;
233 
234  idx->Remove( aItem );
235  m_allItems.erase( aItem );
236  int net = aItem->Net();
237 
238  if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
239  m_netMap[net].remove( aItem );
240 }
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 242 of file pns_index.h.

References Add(), and Remove().

243 {
244  Remove( aOldItem );
245  Add( aNewItem );
246 }
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:210
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:227
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: