KiCad PCB EDA Suite
pns_index.h
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software: you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
10  * Free Software Foundation, either version 3 of the License, or (at your
11  * option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #ifndef __PNS_INDEX_H
23 #define __PNS_INDEX_H
24 
26 #include <map>
27 
28 #include <boost/range/adaptor/map.hpp>
29 
30 #include <list>
31 #include <geometry/shape_index.h>
32 
33 #include "pns_item.h"
34 
35 namespace PNS {
36 
37 
45 class INDEX
46 {
47 public:
48  typedef std::list<ITEM*> NET_ITEMS_LIST;
50  typedef boost::unordered_set<ITEM*> ITEM_SET;
51 
52  INDEX();
53  ~INDEX();
54 
60  void Add( ITEM* aItem );
61 
67  void Remove( ITEM* aItem );
68 
74  void Replace( ITEM* aOldItem, ITEM* aNewItem );
75 
89  template<class Visitor>
90  int Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor );
91 
105  template<class Visitor>
106  int Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor );
107 
113  void Clear();
114 
120  NET_ITEMS_LIST* GetItemsForNet( int aNet );
121 
127  bool Contains( ITEM* aItem ) const
128  {
129  return m_allItems.find( aItem ) != m_allItems.end();
130  }
131 
137  int Size() const { return m_allItems.size(); }
138 
139  ITEM_SET::iterator begin() { return m_allItems.begin(); }
140  ITEM_SET::iterator end() { return m_allItems.end(); }
141 
142 private:
143  static const int MaxSubIndices = 128;
144  static const int SI_Multilayer = 2;
145  static const int SI_SegDiagonal = 0;
146  static const int SI_SegStraight = 1;
147  static const int SI_Traces = 3;
148  static const int SI_PadsTop = 0;
149  static const int SI_PadsBottom = 1;
150 
151  template <class Visitor>
152  int querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor );
153 
154  ITEM_SHAPE_INDEX* getSubindex( const ITEM* aItem );
155 
156  ITEM_SHAPE_INDEX* m_subIndices[MaxSubIndices];
157  std::map<int, NET_ITEMS_LIST> m_netMap;
158  ITEM_SET m_allItems;
159 };
160 
162 {
163  memset( m_subIndices, 0, sizeof( m_subIndices ) );
164 }
165 
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 }
210 
211 void INDEX::Add( ITEM* aItem )
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 }
227 
228 void INDEX::Remove( ITEM* aItem )
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 }
242 
243 void INDEX::Replace( ITEM* aOldItem, ITEM* aNewItem )
244 {
245  Remove( aOldItem );
246  Add( aNewItem );
247 }
248 
249 template<class Visitor>
250 int INDEX::querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
251 {
252  if( !m_subIndices[index] )
253  return 0;
254 
255  return m_subIndices[index]->Query( aShape, aMinDistance, aVisitor, false );
256 }
257 
258 template<class Visitor>
259 int INDEX::Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor )
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 }
290 
291 template<class Visitor>
292 int INDEX::Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
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 }
301 
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 }
314 
316 {
317  Clear();
318 }
319 
321 {
322  if( m_netMap.find( aNet ) == m_netMap.end() )
323  return NULL;
324 
325  return &m_netMap[aNet];
326 }
327 
328 }
329 
330 #endif
Class ITEM.
Definition: pns_item.h:53
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
static const int SI_Traces
Definition: pns_index.h:147
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:207
bool Contains(ITEM *aItem) const
Function Contains()
Definition: pns_index.h:127
virtual const SHAPE * Shape() const
Function Shape()
Definition: pns_item.h:296
int Size() const
Function Size()
Definition: pns_index.h:137
void Add(T aShape)
Function Add()
Definition: shape_index.h:310
SHAPE_INDEX< ITEM * > ITEM_SHAPE_INDEX
Definition: pns_index.h:49
int End() const
Definition: pns_layerset.h:88
void Remove(T aShape)
Function Remove()
Definition: shape_index.h:320
void Clear()
Function Clear()
Definition: pns_index.h:302
static const int SI_SegStraight
Definition: pns_index.h:146
ITEM_SHAPE_INDEX * m_subIndices[MaxSubIndices]
Definition: pns_index.h:156
Class SHAPE.
Definition: shape.h:57
int Start() const
Definition: pns_layerset.h:83
ITEM_SET m_allItems
Definition: pns_index.h:158
static const int SI_PadsBottom
Definition: pns_index.h:149
PnsKind Kind() const
Function Kind()
Definition: pns_item.h:120
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.h:320
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:259
void Replace(ITEM *aOldItem, ITEM *aNewItem)
Function Add()
Definition: pns_index.h:243
ITEM_SET::iterator end()
Definition: pns_index.h:140
ITEM_SET::iterator begin()
Definition: pns_index.h:139
Board layer functions and definitions.
std::map< int, NET_ITEMS_LIST > m_netMap
Definition: pns_index.h:157
static const int SI_Multilayer
Definition: pns_index.h:144
boost::unordered_set< ITEM * > ITEM_SET
Definition: pns_index.h:50
static const int SI_PadsTop
Definition: pns_index.h:148
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:211
int Query(const SHAPE *aShape, int aMinDistance, V &aVisitor, bool aExact)
Function Query()
Definition: shape_index.h:270
int Net() const
Function Net()
Definition: pns_item.h:177
bool IsMultilayer() const
Definition: pns_layerset.h:78
static const int MaxSubIndices
Definition: pns_index.h:143
ITEM_SHAPE_INDEX * getSubindex(const ITEM *aItem)
Definition: pns_index.h:166
int querySingle(int index, const SHAPE *aShape, int aMinDistance, Visitor &aVisitor)
Definition: pns_index.h:250
Push and Shove diff pair dimensions (gap) settings dialog.
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:228
static const int SI_SegDiagonal
Definition: pns_index.h:145
Class INDEX.
Definition: pns_index.h:45
Class LAYER_RANGE.
Definition: pns_layerset.h:32