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 26 of file pns_index.cpp.

27 {
28  memset( m_subIndices, 0, sizeof( m_subIndices ) );
29 }
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:157

References m_subIndices.

◆ ~INDEX()

PNS::INDEX::~INDEX ( )

Definition at line 32 of file pns_index.cpp.

33 {
34  Clear();
35 }
void Clear()
Function Clear()
Definition: pns_index.cpp:124

References Clear().

Member Function Documentation

◆ Add()

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

Function Add()

Adds item to the spatial index.

Definition at line 85 of file pns_index.cpp.

86 {
87  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
88 
89  if( !idx )
90  return;
91 
92  idx->Add( aItem );
93  m_allItems.insert( aItem );
94  int net = aItem->Net();
95 
96  if( net >= 0 )
97  {
98  m_netMap[net].push_back( aItem );
99  }
100 }
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.cpp:38

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 124 of file pns_index.cpp.

125 {
126  for( int i = 0; i < MaxSubIndices; ++i )
127  {
129 
130  if( idx )
131  delete idx;
132 
133  m_subIndices[i] = NULL;
134  }
135 }
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 138 of file pns_index.cpp.

139 {
140  if( m_netMap.find( aNet ) == m_netMap.end() )
141  return NULL;
142 
143  return &m_netMap[aNet];
144 }
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 38 of file pns_index.cpp.

39 {
40  int idx_n = -1;
41 
42  const LAYER_RANGE l = aItem->Layers();
43 
44  switch( aItem->Kind() )
45  {
46  case ITEM::VIA_T:
47  idx_n = SI_Multilayer;
48  break;
49 
50  case ITEM::SOLID_T:
51  {
52  if( l.IsMultilayer() )
53  idx_n = SI_Multilayer;
54  else if( l.Start() == B_Cu ) // fixme: use kicad layer codes
55  idx_n = SI_PadsTop;
56  else if( l.Start() == F_Cu )
57  idx_n = SI_PadsBottom;
58  else
59  idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
60  }
61  break;
62 
63  case ITEM::SEGMENT_T:
64  case ITEM::LINE_T:
65  idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
66  break;
67 
68  default:
69  break;
70  }
71 
72  if( idx_n < 0 || idx_n >= MaxSubIndices )
73  {
74  wxASSERT( idx_n >= 0 );
75  wxASSERT( idx_n < MaxSubIndices );
76  return nullptr;
77  }
78 
79  if( !m_subIndices[idx_n] )
80  m_subIndices[idx_n] = new ITEM_SHAPE_INDEX;
81 
82  return m_subIndices[idx_n];
83 }
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 173 of file pns_index.h.

174 {
175  const SHAPE* shape = aItem->Shape();
176  int total = 0;
177 
178  total += querySingle( SI_Multilayer, shape, aMinDistance, aVisitor );
179 
180  const LAYER_RANGE layers = aItem->Layers();
181 
182  if( layers.IsMultilayer() )
183  {
184  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
185  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
186 
187  for( int i = layers.Start(); i <= layers.End(); ++i )
188  total += querySingle( SI_Traces + 2 * i + SI_SegStraight, shape, aMinDistance, aVisitor );
189  }
190  else
191  {
192  int l = layers.Start();
193 
194  if( l == B_Cu )
195  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
196  else if( l == F_Cu )
197  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
198 
199  total += querySingle( SI_Traces + 2 * l + SI_SegStraight, shape, aMinDistance, aVisitor );
200  }
201 
202  return total;
203 }
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:164
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 206 of file pns_index.h.

207 {
208  int total = 0;
209 
210  for( int i = 0; i < MaxSubIndices; i++ )
211  total += querySingle( i, aShape, aMinDistance, aVisitor );
212 
213  return total;
214 }
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:164

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

165 {
166  if( !m_subIndices[index] )
167  return 0;
168 
169  return m_subIndices[index]->Query( aShape, aMinDistance, aVisitor, false );
170 }
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 102 of file pns_index.cpp.

103 {
104  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
105 
106  if( !idx )
107  return;
108 
109  idx->Remove( aItem );
110  m_allItems.erase( aItem );
111  int net = aItem->Net();
112 
113  if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
114  m_netMap[net].remove( aItem );
115 }
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.cpp:38

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 117 of file pns_index.cpp.

118 {
119  Remove( aOldItem );
120  Add( aNewItem );
121 }
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:85
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.cpp:102

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 files: