KiCad PCB EDA Suite
connectivity_items.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KICAD, a free EDA CAD application.
3  *
4  * Copyright (C) 2013-2017 CERN
5  * Copyright (C) 2018 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Maciej Suminski <maciej.suminski@cern.ch>
8  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
28 
29 #ifndef PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_
30 #define PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_
31 
32 #include <class_board.h>
33 #include <class_pad.h>
34 #include <class_module.h>
35 #include <class_zone.h>
36 
39 
40 #include <memory>
41 #include <algorithm>
42 #include <functional>
43 #include <vector>
44 #include <deque>
45 #include <intrusive_list.h>
46 
49 
50 class CN_ITEM;
51 class CN_CLUSTER;
52 
53 class CN_ANCHOR
54 {
55 public:
57  {
58  m_item = nullptr;
59  }
60 
61  CN_ANCHOR( const VECTOR2I& aPos, CN_ITEM* aItem )
62  {
63  m_pos = aPos;
64  m_item = aItem;
65  assert( m_item );
66  }
67 
68  bool Valid() const;
69 
70 
71  CN_ITEM* Item() const
72  {
73  return m_item;
74  }
75 
77 
78  const VECTOR2I& Pos() const
79  {
80  return m_pos;
81  }
82 
84  inline int GetTag() const
85  {
86  return m_tag;
87  }
88 
90  inline void SetTag( int aTag )
91  {
92  m_tag = aTag;
93  }
94 
96  inline void SetNoLine( bool aEnable )
97  {
98  m_noline = aEnable;
99  }
100 
102  inline const bool& GetNoLine() const
103  {
104  return m_noline;
105  }
106 
107  inline void SetCluster( std::shared_ptr<CN_CLUSTER> aCluster )
108  {
109  m_cluster = aCluster;
110  }
111 
112  inline const std::shared_ptr<CN_CLUSTER>& GetCluster() const
113  {
114  return m_cluster;
115  }
116 
125  bool IsDangling() const;
126 
131  int ConnectedItemsCount() const;
132 
133  // Tag used for unconnected items.
134  static const int TAG_UNCONNECTED = -1;
135 
136 private:
139 
141  CN_ITEM* m_item = nullptr;
142 
144  int m_tag = -1;
145 
147  bool m_noline = false;
148 
150  std::shared_ptr<CN_CLUSTER> m_cluster;
151 };
152 
153 
154 typedef std::shared_ptr<CN_ANCHOR> CN_ANCHOR_PTR;
155 typedef std::vector<CN_ANCHOR_PTR> CN_ANCHORS;
156 
157 
158 // basic connectivity item
159 class CN_ITEM : public INTRUSIVE_LIST<CN_ITEM>
160 {
161 public:
162  using CONNECTED_ITEMS = std::vector<CN_ITEM*>;
163 
164 private:
166 
169 
171 
173  bool m_visited;
174 
177 
179  bool m_valid;
180 
182  std::mutex m_listLock;
183 
184 protected:
186  bool m_dirty;
187 
190 
193 
194 public:
195  void Dump();
196 
197  CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
198  {
199  m_parent = aParent;
200  m_canChangeNet = aCanChangeNet;
201  m_visited = false;
202  m_valid = true;
203  m_dirty = true;
204  m_anchors.reserve( std::max( 6, aAnchorCount ) );
206  m_connected.reserve( 8 );
207  }
208 
209  virtual ~CN_ITEM() {};
210 
211  void AddAnchor( const VECTOR2I& aPos )
212  {
213  m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
214  }
215 
217  {
218  return m_anchors;
219  }
220 
221  void SetValid( bool aValid )
222  {
223  m_valid = aValid;
224  }
225 
226  bool Valid() const
227  {
228  return m_valid;
229  }
230 
231  void SetDirty( bool aDirty )
232  {
233  m_dirty = aDirty;
234  }
235 
236  bool Dirty() const
237  {
238  return m_dirty;
239  }
240 
246  void SetLayers( const LAYER_RANGE& aLayers )
247  {
248  m_layers = aLayers;
249  }
250 
256  void SetLayer( int aLayer )
257  {
258  m_layers = LAYER_RANGE( aLayer, aLayer );
259  }
260 
266  const LAYER_RANGE& Layers() const
267  {
268  return m_layers;
269  }
270 
276  virtual int Layer() const
277  {
278  return Layers().Start();
279  }
280 
281  const BOX2I& BBox()
282  {
283  if( m_dirty && m_valid )
284  {
286  m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
287  }
288  return m_bbox;
289  }
290 
292  {
293  return m_parent;
294  }
295 
297  {
298  return m_connected;
299  }
300 
302  {
303  m_connected.clear();
304  }
305 
306  void SetVisited( bool aVisited )
307  {
308  m_visited = aVisited;
309  }
310 
311  bool Visited() const
312  {
313  return m_visited;
314  }
315 
316  bool CanChangeNet() const
317  {
318  return m_canChangeNet;
319  }
320 
321  void Connect( CN_ITEM* b )
322  {
323  std::lock_guard<std::mutex> lock( m_listLock );
324 
325  auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
326 
327  if( i != m_connected.end() && *i == b )
328  return;
329 
330  m_connected.insert( i, b );
331  }
332 
333  void RemoveInvalidRefs();
334 
335  virtual int AnchorCount() const;
336  virtual const VECTOR2I GetAnchor( int n ) const;
337 
338  int Net() const;
339 };
340 
341 typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
342 
343 class CN_ZONE : public CN_ITEM
344 {
345 public:
346  CN_ZONE( ZONE_CONTAINER* aParent, bool aCanChangeNet, int aSubpolyIndex ) :
347  CN_ITEM( aParent, aCanChangeNet ),
348  m_subpolyIndex( aSubpolyIndex )
349  {
350  SHAPE_LINE_CHAIN outline = aParent->GetFilledPolysList().COutline( aSubpolyIndex );
351 
352  outline.SetClosed( true );
353  outline.Simplify();
354 
355  m_cachedPoly = std::make_unique<POLY_GRID_PARTITION>( outline, 16 );
356  }
357 
358  int SubpolyIndex() const
359  {
360  return m_subpolyIndex;
361  }
362 
363  bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
364  {
365  return ContainsPoint( anchor->Pos() );
366  }
367 
368  bool ContainsPoint( const VECTOR2I p ) const
369  {
370  auto zone = static_cast<ZONE_CONTAINER*> ( Parent() );
371  int clearance = zone->GetFilledPolysUseThickness() ? zone->GetMinThickness() / 2 : 0;
372  return m_cachedPoly->ContainsPoint( p, clearance );
373  }
374 
375  const BOX2I& BBox()
376  {
377  if( m_dirty )
378  m_bbox = m_cachedPoly->BBox();
379 
380  return m_bbox;
381  }
382 
383  virtual int AnchorCount() const override;
384  virtual const VECTOR2I GetAnchor( int n ) const override;
385 
386 private:
387  std::vector<VECTOR2I> m_testOutlinePoints;
388  std::unique_ptr<POLY_GRID_PARTITION> m_cachedPoly;
390 };
391 
392 class CN_LIST
393 {
394 private:
395  bool m_dirty;
397 
399 
400 protected:
401  std::vector<CN_ITEM*> m_items;
402 
403  void addItemtoTree( CN_ITEM* item )
404  {
405  m_index.Insert( item );
406  }
407 
408 public:
410  {
411  m_dirty = false;
412  m_hasInvalid = false;
413  }
414 
415  void Clear()
416  {
417  for( auto item : m_items )
418  delete item;
419 
420  m_items.clear();
421  m_index.RemoveAll();
422  }
423 
424  using ITER = decltype(m_items)::iterator;
425 
426  ITER begin() { return m_items.begin(); };
427  ITER end() { return m_items.end(); };
428 
429  CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
430 
431  template <class T>
432  void FindNearby( CN_ITEM *aItem, T aFunc )
433  {
434  m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
435  }
436 
437  void SetHasInvalid( bool aInvalid = true )
438  {
439  m_hasInvalid = aInvalid;
440  }
441 
442  void SetDirty( bool aDirty = true )
443  {
444  m_dirty = aDirty;
445  }
446 
447  bool IsDirty() const
448  {
449  return m_dirty;
450  }
451 
452  void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
453 
455  {
456  for( auto item : m_items )
457  item->SetDirty( false );
458 
459  SetDirty( false );
460  }
461 
463  {
464  for( auto item : m_items )
465  item->SetDirty( true );
466 
467  SetDirty( true );
468  }
469 
470  int Size() const
471  {
472  return m_items.size();
473  }
474 
475  CN_ITEM* Add( D_PAD* pad );
476 
477  CN_ITEM* Add( TRACK* track );
478 
479  CN_ITEM* Add( VIA* via );
480 
481  const std::vector<CN_ITEM*> Add( ZONE_CONTAINER* zone );
482 };
483 
485 {
486 private:
487 
488  bool m_conflicting = false;
489  int m_originNet = 0;
490  CN_ITEM* m_originPad = nullptr;
491  std::vector<CN_ITEM*> m_items;
492 
493 public:
494  CN_CLUSTER();
495  ~CN_CLUSTER();
496 
497  bool HasValidNet() const
498  {
499  return m_originNet > 0;
500  }
501 
502  int OriginNet() const
503  {
504  return m_originNet;
505  }
506 
507  wxString OriginNetName() const;
508 
509  bool Contains( const CN_ITEM* aItem );
510  bool Contains( const BOARD_CONNECTED_ITEM* aItem );
511  void Dump();
512 
513  int Size() const
514  {
515  return m_items.size();
516  }
517 
518  bool HasNet() const
519  {
520  return m_originNet > 0;
521  }
522 
523  bool IsOrphaned() const
524  {
525  return m_originPad == nullptr;
526  }
527 
528  bool IsConflicting() const
529  {
530  return m_conflicting;
531  }
532 
533  void Add( CN_ITEM* item );
534 
535  using ITER = decltype(m_items)::iterator;
536 
537  ITER begin() { return m_items.begin(); };
538  ITER end() { return m_items.end(); };
539 };
540 
541 typedef std::shared_ptr<CN_CLUSTER> CN_CLUSTER_PTR;
542 
543 
544 #endif /* PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_ */
std::vector< CN_ITEM * > CONNECTED_ITEMS
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
const CONNECTED_ITEMS & ConnectedItems() const
bool Contains(const CN_ITEM *aItem)
int GetTag() const
Returns tag, common identifier for connected nodes.
virtual int AnchorCount() const override
std::vector< CN_ITEM * > m_items
ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:60
BOX2< VECTOR2I > BOX2I
Definition: box2.h:521
decltype(m_items)::iterator ITER
BOARD_CONNECTED_ITEM * m_parent
int Size() const
void SetHasInvalid(bool aInvalid=true)
std::shared_ptr< CN_CLUSTER > m_cluster
Cluster to which the anchor belongs.
int SubpolyIndex() const
std::vector< VECTOR2I > m_testOutlinePoints
void addItemtoTree(CN_ITEM *item)
bool m_valid
valid flag, used to identify garbage items (we use lazy removal)
A lightweight intrusive list container
CN_ITEM * Add(D_PAD *pad)
void ClearDirtyFlags()
const bool & GetNoLine() const
Returns true if this node can be a target for ratsnest lines.
void ClearConnections()
CN_ITEM * operator[](int aIndex)
LAYER_RANGE m_layers
layer range over which the item exists
const BOX2I & BBox()
void SetVisited(bool aVisited)
bool IsDirty() const
bool Dirty() const
BOARD_CONNECTED_ITEM * Parent() const
static const int TAG_UNCONNECTED
CN_ITEM * Item() const
bool HasNet() const
void SetCluster(std::shared_ptr< CN_CLUSTER > aCluster)
bool IsDangling() const
has meaning only for tracks and vias.
CN_ANCHORS & Anchors()
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
void SetDirty(bool aDirty=true)
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
int ConnectedItemsCount() const
has meaning only for tracks and vias.
int Net() const
bool Visited() const
void MarkAllAsDirty()
VECTOR2I m_pos
Position of the anchor.
virtual int AnchorCount() const
int Start() const
Definition: pns_layerset.h:83
void SetValid(bool aValid)
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
std::vector< CN_ITEM * > m_items
void SetClosed(bool aClosed)
Function SetClosed()
bool m_visited
visited flag for the BFS scan
std::vector< CN_ANCHOR_PTR > CN_ANCHORS
int OriginNet() const
CN_ANCHOR(const VECTOR2I &aPos, CN_ITEM *aItem)
const wxPoint GetPosition() const
Definition: eda_rect.h:115
int Size() const
bool m_dirty
dirty flag, used to identify recently added item not yet scanned into the connectivity search
decltype(m_items)::iterator ITER
void SetLayers(const LAYER_RANGE &aLayers)
Function SetLayers()
std::mutex m_listLock
mutex protecting this item's connected_items set to allow parallel connection threads
virtual ~CN_ITEM()
BOX2I m_bbox
bounding box for the item
void SetTag(int aTag)
Sets tag, common identifier for connected nodes.
void Add(CN_ITEM *item)
bool m_canChangeNet
can the net propagator modify the netcode?
void Query(const BOX2I &aBounds, const LAYER_RANGE &aRange, Visitor &aVisitor)
Function Query() Executes a function object aVisitor for each item whose bounding box intersects with...
const std::shared_ptr< CN_CLUSTER > & GetCluster() const
bool ContainsPoint(const VECTOR2I p) const
bool Valid() const
Pad object description.
bool IsConflicting() const
virtual const VECTOR2I GetAnchor(int n) const
void SetDirty(bool aDirty)
int m_tag
Tag for quick connection resolution.
std::unique_ptr< POLY_GRID_PARTITION > m_cachedPoly
bool CanChangeNet() const
wxString OriginNetName() const
bool HasValidNet() const
void AddAnchor(const VECTOR2I &aPos)
void FindNearby(CN_ITEM *aItem, T aFunc)
CN_ZONE(ZONE_CONTAINER *aParent, bool aCanChangeNet, int aSubpolyIndex)
virtual const VECTOR2I GetAnchor(int n) const override
CN_ITEM * m_item
Item owning the anchor.
SHAPE_LINE_CHAIN.
void SetLayer(int aLayer)
Function SetLayer()
CN_ITEM * m_originPad
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
const LAYER_RANGE & Layers() const
Function Layers()
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
BOARD_CONNECTED_ITEM * Parent() const
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
CN_ITEM(BOARD_CONNECTED_ITEM *aParent, bool aCanChangeNet, int aAnchorCount=2)
virtual int Layer() const
Function Layer()
std::shared_ptr< CN_ITEM > CN_ITEM_PTR
void SetNoLine(bool aEnable)
Decides whether this node can be a ratsnest line target.
const VECTOR2I & Pos() const
CONNECTED_ITEMS m_connected
list of items physically connected (touching)
bool ContainsAnchor(const CN_ANCHOR_PTR anchor) const
void Connect(CN_ITEM *b)
Module description (excepted pads)
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
bool IsOrphaned() const
LAYER_RANGE.
Definition: pns_layerset.h:32
const BOX2I & BBox()
void RemoveInvalidRefs()
bool m_noline
Whether it the node can be a target for ratsnest lines.
const wxSize GetSize() const
Definition: eda_rect.h:103
bool Valid() const
CN_RTREE< CN_ITEM * > m_index
CN_ANCHORS m_anchors
const SHAPE_POLY_SET & GetFilledPolysList() const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: class_zone.h:553