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  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 }
209 
210 void INDEX::Add( ITEM* aItem )
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 }
226 
227 void INDEX::Remove( ITEM* aItem )
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 }
241 
242 void INDEX::Replace( ITEM* aOldItem, ITEM* aNewItem )
243 {
244  Remove( aOldItem );
245  Add( aNewItem );
246 }
247 
248 template<class Visitor>
249 int INDEX::querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
250 {
251  if( !m_subIndices[index] )
252  return 0;
253 
254  return m_subIndices[index]->Query( aShape, aMinDistance, aVisitor, false );
255 }
256 
257 template<class Visitor>
258 int INDEX::Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor )
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 }
289 
290 template<class Visitor>
291 int INDEX::Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
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 }
300 
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 }
313 
315 {
316  Clear();
317 }
318 
320 {
321  if( m_netMap.find( aNet ) == m_netMap.end() )
322  return NULL;
323 
324  return &m_netMap[aNet];
325 }
326 
327 }
328 
329 #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:301
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:319
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:258
void Replace(ITEM *aOldItem, ITEM *aNewItem)
Function Add()
Definition: pns_index.h:242
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:210
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:249
Push and Shove diff pair dimensions (gap) settings dialog.
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:227
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