Horizon
pns_index.h
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 #include <unordered_set>
28 
29 #include <boost/range/adaptor/map.hpp>
30 
31 #include <list>
32 #include <geometry/shape_index.h>
33 
34 #include "pns_item.h"
35 
36 namespace PNS {
37 
38 
46 class INDEX
47 {
48 public:
49  typedef std::list<ITEM*> NET_ITEMS_LIST;
51  typedef std::unordered_set<ITEM*> ITEM_SET;
52 
53  INDEX();
54  ~INDEX();
55 
61  void Add( ITEM* aItem );
62 
68  void Remove( ITEM* aItem );
69 
75  void Replace( ITEM* aOldItem, ITEM* aNewItem );
76 
90  template<class Visitor>
91  int Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor );
92 
106  template<class Visitor>
107  int Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor );
108 
114  void Clear();
115 
121  NET_ITEMS_LIST* GetItemsForNet( int aNet );
122 
128  bool Contains( ITEM* aItem ) const
129  {
130  return m_allItems.find( aItem ) != m_allItems.end();
131  }
132 
138  int Size() const { return m_allItems.size(); }
139 
140  ITEM_SET::iterator begin() { return m_allItems.begin(); }
141  ITEM_SET::iterator end() { return m_allItems.end(); }
142 
143 private:
144  static const int MaxSubIndices = 128;
145  static const int SI_Multilayer = 2;
146  static const int SI_SegDiagonal = 0;
147  static const int SI_SegStraight = 1;
148  static const int SI_Traces = 3;
149  static const int SI_PadsTop = 0;
150  static const int SI_PadsBottom = 1;
151 
152  template <class Visitor>
153  int querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor );
154 
155  ITEM_SHAPE_INDEX* getSubindex( const ITEM* aItem );
156 
157  ITEM_SHAPE_INDEX* m_subIndices[MaxSubIndices];
158  std::map<int, NET_ITEMS_LIST> m_netMap;
159  ITEM_SET m_allItems;
160 };
161 
162 INDEX::INDEX()
163 {
164  memset( m_subIndices, 0, sizeof( m_subIndices ) );
165 }
166 
167 INDEX::ITEM_SHAPE_INDEX* INDEX::getSubindex( const ITEM* aItem )
168 {
169  int idx_n = -1;
170 
171  const LAYER_RANGE l = aItem->Layers();
172 
173  switch( aItem->Kind() )
174  {
175  case ITEM::VIA_T:
176  idx_n = SI_Multilayer;
177  break;
178 
179  case ITEM::SOLID_T:
180  {
181  if( l.IsMultilayer() )
182  idx_n = SI_Multilayer;
183  else if( l.Start() == B_Cu ) // fixme: use kicad layer codes
184  idx_n = SI_PadsTop;
185  else if( l.Start() == F_Cu )
186  idx_n = SI_PadsBottom;
187  }
188  break;
189 
190  case ITEM::SEGMENT_T:
191  case ITEM::LINE_T:
192  idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
193  break;
194 
195  default:
196  break;
197  }
198 
199  if( idx_n < 0 || idx_n >= MaxSubIndices )
200  {
201  assert( idx_n >= 0 );
202  assert( idx_n < MaxSubIndices );
203  return nullptr;
204  }
205 
206  if( !m_subIndices[idx_n] )
207  m_subIndices[idx_n] = new ITEM_SHAPE_INDEX;
208 
209  return m_subIndices[idx_n];
210 }
211 
212 void INDEX::Add( ITEM* aItem )
213 {
214  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
215 
216  if( !idx )
217  return;
218 
219  idx->Add( aItem );
220  m_allItems.insert( aItem );
221  int net = aItem->Net();
222 
223  if( net >= 0 )
224  {
225  m_netMap[net].push_back( aItem );
226  }
227 }
228 
229 void INDEX::Remove( ITEM* aItem )
230 {
231  ITEM_SHAPE_INDEX* idx = getSubindex( aItem );
232 
233  if( !idx )
234  return;
235 
236  idx->Remove( aItem );
237  m_allItems.erase( aItem );
238  int net = aItem->Net();
239 
240  if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
241  m_netMap[net].remove( aItem );
242 }
243 
244 void INDEX::Replace( ITEM* aOldItem, ITEM* aNewItem )
245 {
246  Remove( aOldItem );
247  Add( aNewItem );
248 }
249 
250 template<class Visitor>
251 int INDEX::querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
252 {
253  if( !m_subIndices[index] )
254  return 0;
255 
256  return m_subIndices[index]->Query( aShape, aMinDistance, aVisitor, false );
257 }
258 
259 template<class Visitor>
260 int INDEX::Query( const ITEM* aItem, int aMinDistance, Visitor& aVisitor )
261 {
262  const SHAPE* shape = aItem->Shape();
263  int total = 0;
264 
265  total += querySingle( SI_Multilayer, shape, aMinDistance, aVisitor );
266 
267  const LAYER_RANGE layers = aItem->Layers();
268 
269  if( layers.IsMultilayer() )
270  {
271  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
272  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
273 
274  for( int i = layers.Start(); i <= layers.End(); ++i )
275  total += querySingle( SI_Traces + 2 * i + SI_SegStraight, shape, aMinDistance, aVisitor );
276  }
277  else
278  {
279  int l = layers.Start();
280 
281  if( l == B_Cu )
282  total += querySingle( SI_PadsTop, shape, aMinDistance, aVisitor );
283  else if( l == F_Cu )
284  total += querySingle( SI_PadsBottom, shape, aMinDistance, aVisitor );
285 
286  total += querySingle( SI_Traces + 2 * l + SI_SegStraight, shape, aMinDistance, aVisitor );
287  }
288 
289  return total;
290 }
291 
292 template<class Visitor>
293 int INDEX::Query( const SHAPE* aShape, int aMinDistance, Visitor& aVisitor )
294 {
295  int total = 0;
296 
297  for( int i = 0; i < MaxSubIndices; i++ )
298  total += querySingle( i, aShape, aMinDistance, aVisitor );
299 
300  return total;
301 }
302 
304 {
305  for( int i = 0; i < MaxSubIndices; ++i )
306  {
307  ITEM_SHAPE_INDEX* idx = m_subIndices[i];
308 
309  if( idx )
310  delete idx;
311 
312  m_subIndices[i] = NULL;
313  }
314 }
315 
316 INDEX::~INDEX()
317 {
318  Clear();
319 }
320 
321 INDEX::NET_ITEMS_LIST* INDEX::GetItemsForNet( int aNet )
322 {
323  if( m_netMap.find( aNet ) == m_netMap.end() )
324  return NULL;
325 
326  return &m_netMap[aNet];
327 }
328 
329 }
330 
331 #endif
Class ITEM.
Definition: pns_item.h:54
Definition: shape_index.h:107
void Add(T aShape)
Function Add()
Definition: shape_index.h:310
virtual const SHAPE * Shape() const
Function Shape()
Definition: pns_item.h:297
int Net() const
Function Net()
Definition: pns_item.h:178
void Remove(T aShape)
Function Remove()
Definition: shape_index.h:320
void Clear()
Function Clear()
Definition: pns_index.h:303
Class SHAPE.
Definition: shape.h:57
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.h:321
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:260
bool Contains(ITEM *aItem) const
Function Contains()
Definition: pns_index.h:128
void Replace(ITEM *aOldItem, ITEM *aNewItem)
Function Add()
Definition: pns_index.h:244
Board layer functions and definitions.
int Size() const
Function Size()
Definition: pns_index.h:138
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.h:212
int Query(const SHAPE *aShape, int aMinDistance, V &aVisitor, bool aExact)
Function Query()
Definition: shape_index.h:270
PnsKind Kind() const
Function Kind()
Definition: pns_item.h:121
Definition: pns_algo_base.cpp:26
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.h:229
Class INDEX.
Definition: pns_index.h:46
Class LAYER_RANGE.
Definition: pns_layerset.h:32
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:208