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 std::shared_ptr<CN_CLUSTER> GetCluster() const
113  {
114  return m_cluster;
115  }
116 
125  bool IsDangling() const;
126 
127  // Tag used for unconnected items.
128  static const int TAG_UNCONNECTED = -1;
129 
130 private:
133 
135  CN_ITEM* m_item = nullptr;
136 
138  int m_tag = -1;
139 
141  bool m_noline = false;
142 
144  std::shared_ptr<CN_CLUSTER> m_cluster;
145 };
146 
147 
148 typedef std::shared_ptr<CN_ANCHOR> CN_ANCHOR_PTR;
149 typedef std::vector<CN_ANCHOR_PTR> CN_ANCHORS;
150 
151 
152 // basic connectivity item
153 class CN_ITEM : public INTRUSIVE_LIST<CN_ITEM>
154 {
155 public:
156  using CONNECTED_ITEMS = std::set<CN_ITEM*>;
157 
158 private:
160 
163 
165 
167  bool m_visited;
168 
171 
173  bool m_valid;
174 
176  std::mutex m_listLock;
177 
178 protected:
180  bool m_dirty;
181 
184 
187 
188 public:
189  void Dump();
190 
191  CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
192  {
193  m_parent = aParent;
194  m_canChangeNet = aCanChangeNet;
195  m_visited = false;
196  m_valid = true;
197  m_dirty = true;
198  m_anchors.reserve( 2 );
199  m_layers = LAYER_RANGE( 0, PCB_LAYER_ID_COUNT );
200  }
201 
202  virtual ~CN_ITEM() {};
203 
204  void AddAnchor( const VECTOR2I& aPos )
205  {
206  m_anchors.emplace_back( std::make_unique<CN_ANCHOR>( aPos, this ) );
207  }
208 
210  {
211  return m_anchors;
212  }
213 
214  void SetValid( bool aValid )
215  {
216  m_valid = aValid;
217  }
218 
219  bool Valid() const
220  {
221  return m_valid;
222  }
223 
224  void SetDirty( bool aDirty )
225  {
226  m_dirty = aDirty;
227  }
228 
229  bool Dirty() const
230  {
231  return m_dirty;
232  }
233 
239  void SetLayers( const LAYER_RANGE& aLayers )
240  {
241  m_layers = aLayers;
242  }
243 
249  void SetLayer( int aLayer )
250  {
251  m_layers = LAYER_RANGE( aLayer, aLayer );
252  }
253 
259  const LAYER_RANGE& Layers() const
260  {
261  return m_layers;
262  }
263 
269  virtual int Layer() const
270  {
271  return Layers().Start();
272  }
273 
274  const BOX2I& BBox()
275  {
276  if( m_dirty && m_valid )
277  {
278  EDA_RECT box = m_parent->GetBoundingBox();
279  m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
280  }
281  return m_bbox;
282  }
283 
285  {
286  return m_parent;
287  }
288 
290  {
291  return m_connected;
292  }
293 
295  {
296  m_connected.clear();
297  }
298 
299  void SetVisited( bool aVisited )
300  {
301  m_visited = aVisited;
302  }
303 
304  bool Visited() const
305  {
306  return m_visited;
307  }
308 
309  bool CanChangeNet() const
310  {
311  return m_canChangeNet;
312  }
313 
314  void Connect( CN_ITEM* b )
315  {
316  std::lock_guard<std::mutex> lock( m_listLock );
317  m_connected.insert( b );
318  }
319 
320  void RemoveInvalidRefs();
321 
322  virtual int AnchorCount() const;
323  virtual const VECTOR2I GetAnchor( int n ) const;
324 
325  int Net() const;
326 };
327 
328 typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
329 
330 class CN_ZONE : public CN_ITEM
331 {
332 public:
333  CN_ZONE( ZONE_CONTAINER* aParent, bool aCanChangeNet, int aSubpolyIndex ) :
334  CN_ITEM( aParent, aCanChangeNet ),
335  m_subpolyIndex( aSubpolyIndex )
336  {
337  SHAPE_LINE_CHAIN outline = aParent->GetFilledPolysList().COutline( aSubpolyIndex );
338 
339  outline.SetClosed( true );
340  outline.Simplify();
341 
342  m_cachedPoly.reset( new POLY_GRID_PARTITION( outline, 16 ) );
343  }
344 
345  int SubpolyIndex() const
346  {
347  return m_subpolyIndex;
348  }
349 
350  bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
351  {
352  return ContainsPoint( anchor->Pos() );
353  }
354 
355  bool ContainsPoint( const VECTOR2I p ) const
356  {
357  auto zone = static_cast<ZONE_CONTAINER*> ( Parent() );
358  return m_cachedPoly->ContainsPoint( p, zone->GetMinThickness() );
359  }
360 
361  const BOX2I& BBox()
362  {
363  if( m_dirty )
364  m_bbox = m_cachedPoly->BBox();
365 
366  return m_bbox;
367  }
368 
369  virtual int AnchorCount() const override;
370  virtual const VECTOR2I GetAnchor( int n ) const override;
371 
372 private:
373  std::vector<VECTOR2I> m_testOutlinePoints;
374  std::unique_ptr<POLY_GRID_PARTITION> m_cachedPoly;
376 };
377 
378 class CN_LIST
379 {
380 private:
381  bool m_dirty;
383 
385 
386 protected:
387  std::vector<CN_ITEM*> m_items;
388 
389  void addItemtoTree( CN_ITEM* item )
390  {
391  m_index.Insert( item );
392  }
393 
394 public:
396  {
397  m_dirty = false;
398  m_hasInvalid = false;
399  }
400 
401  void Clear()
402  {
403  for( auto item : m_items )
404  delete item;
405 
406  m_items.clear();
407  m_index.RemoveAll();
408  }
409 
410  using ITER = decltype(m_items)::iterator;
411 
412  ITER begin() { return m_items.begin(); };
413  ITER end() { return m_items.end(); };
414 
415  CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
416 
417  template <class T>
418  void FindNearby( CN_ITEM *aItem, T aFunc )
419  {
420  m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
421  }
422 
423  void SetHasInvalid( bool aInvalid = true )
424  {
425  m_hasInvalid = aInvalid;
426  }
427 
428  void SetDirty( bool aDirty = true )
429  {
430  m_dirty = aDirty;
431  }
432 
433  bool IsDirty() const
434  {
435  return m_dirty;
436  }
437 
438  void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
439 
441  {
442  for( auto item : m_items )
443  item->SetDirty( false );
444 
445  SetDirty( false );
446  }
447 
449  {
450  for( auto item : m_items )
451  item->SetDirty( true );
452 
453  SetDirty( true );
454  }
455 
456  int Size() const
457  {
458  return m_items.size();
459  }
460 
461  CN_ITEM* Add( D_PAD* pad );
462 
463  CN_ITEM* Add( TRACK* track );
464 
465  CN_ITEM* Add( VIA* via );
466 
467  const std::vector<CN_ITEM*> Add( ZONE_CONTAINER* zone );
468 };
469 
471 {
472 private:
473 
474  bool m_conflicting = false;
475  int m_originNet = 0;
476  CN_ITEM* m_originPad = nullptr;
477  std::vector<CN_ITEM*> m_items;
478 
479 public:
480  CN_CLUSTER();
481  ~CN_CLUSTER();
482 
483  bool HasValidNet() const
484  {
485  return m_originNet >= 0;
486  }
487 
488  int OriginNet() const
489  {
490  return m_originNet;
491  }
492 
493  wxString OriginNetName() const;
494 
495  bool Contains( const CN_ITEM* aItem );
496  bool Contains( const BOARD_CONNECTED_ITEM* aItem );
497  void Dump();
498 
499  int Size() const
500  {
501  return m_items.size();
502  }
503 
504  bool HasNet() const
505  {
506  return m_originNet >= 0;
507  }
508 
509  bool IsOrphaned() const
510  {
511  return m_originPad == nullptr;
512  }
513 
514  bool IsConflicting() const
515  {
516  return m_conflicting;
517  }
518 
519  void Add( CN_ITEM* item );
520 
521  using ITER = decltype(m_items)::iterator;
522 
523  ITER begin() { return m_items.begin(); };
524  ITER end() { return m_items.end(); };
525 };
526 
527 typedef std::shared_ptr<CN_CLUSTER> CN_CLUSTER_PTR;
528 
529 
530 #endif /* PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_ */
std::vector< CN_ITEM * > m_items
Class ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:59
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes...
BOX2< VECTOR2I > BOX2I
Definition: box2.h:520
decltype(m_items)::iterator ITER
BOARD_CONNECTED_ITEM * m_parent
void SetHasInvalid(bool aInvalid=true)
bool Valid() const
const wxSize GetSize() const
Definition: eda_rect.h:101
std::shared_ptr< CN_CLUSTER > m_cluster
Cluster to which the anchor belongs.
std::vector< VECTOR2I > m_testOutlinePoints
Class BOARD to handle a board.
void addItemtoTree(CN_ITEM *item)
bool m_valid
valid flag, used to identify garbage items (we use lazy removal)
A lightweight intrusive list container
virtual int Layer() const
Function Layer()
void ClearDirtyFlags()
void ClearConnections()
LAYER_RANGE m_layers
layer range over which the item exists
const BOX2I & BBox()
const bool & GetNoLine() const
Returns true if this node can be a target for ratsnest lines.
void SetVisited(bool aVisited)
std::set< CN_ITEM * > CONNECTED_ITEMS
BOARD_CONNECTED_ITEM * Parent() const
bool HasValidNet() const
bool ContainsAnchor(const CN_ANCHOR_PTR anchor) const
Classes to handle copper zones.
bool IsConflicting() const
CN_ITEM * Item() const
static const int TAG_UNCONNECTED
void SetCluster(std::shared_ptr< CN_CLUSTER > aCluster)
CN_ANCHORS & Anchors()
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
void SetDirty(bool aDirty=true)
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
void MarkAllAsDirty()
bool ContainsPoint(const VECTOR2I p) const
VECTOR2I m_pos
Position of the anchor.
void SetValid(bool aValid)
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
bool IsDangling() const
has meaning only for tracks and vias.
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 SubpolyIndex() const
bool Valid() const
CN_ANCHOR(const VECTOR2I &aPos, CN_ITEM *aItem)
bool Visited() 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()
int OriginNet() const
std::mutex m_listLock
mutex protecting this item&#39;s connected_items set to allow parallel connection threads ...
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
virtual ~CN_ITEM()
BOX2I m_bbox
bounding box for the item
void SetTag(int aTag)
Sets tag, common identifier for connected nodes.
const CONNECTED_ITEMS & ConnectedItems() const
bool IsOrphaned() const
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 SHAPE_POLY_SET & GetFilledPolysList() const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: class_zone.h:559
const wxPoint GetPosition() const
Definition: eda_rect.h:113
Pad object description.
void SetDirty(bool aDirty)
int m_tag
Tag for quick connection resolution.
std::unique_ptr< POLY_GRID_PARTITION > m_cachedPoly
const LAYER_RANGE & Layers() const
Function Layers()
void AddAnchor(const VECTOR2I &aPos)
void FindNearby(CN_ITEM *aItem, T aFunc)
BOARD_CONNECTED_ITEM * Parent() const
CN_ZONE(ZONE_CONTAINER *aParent, bool aCanChangeNet, int aSubpolyIndex)
bool HasNet() const
int GetTag() const
Returns tag, common identifier for connected nodes.
CN_ITEM * m_item
Item owning the anchor.
Class SHAPE_LINE_CHAIN.
void SetLayer(int aLayer)
Function SetLayer()
int Size() const
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
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)
std::shared_ptr< CN_ITEM > CN_ITEM_PTR
void SetNoLine(bool aEnable)
Decides whether this node can be a ratsnest line target.
CONNECTED_ITEMS m_connected
list of items physically connected (touching)
void Connect(CN_ITEM *b)
bool IsDirty() const
bool CanChangeNet() const
Module description (excepted pads)
Class POLY_GRID_PARTITION.
std::shared_ptr< CN_CLUSTER > GetCluster() const
bool Dirty() const
Class LAYER_RANGE.
Definition: pns_layerset.h:32
const BOX2I & BBox()
bool m_noline
Whether it the node can be a target for ratsnest lines.
int Size() const
const VECTOR2I & Pos() const
CN_RTREE< CN_ITEM * > m_index
CN_ANCHORS m_anchors