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 private:
157 
158  using CONNECTED_ITEMS = std::set<CN_ITEM*>;
159 
162 
164 
166  bool m_visited;
167 
170 
172  bool m_valid;
173 
175  std::mutex m_listLock;
176 
177 protected:
179  bool m_dirty;
180 
183 
186 
187 public:
188  void Dump();
189 
190  CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
191  {
192  m_parent = aParent;
193  m_canChangeNet = aCanChangeNet;
194  m_visited = false;
195  m_valid = true;
196  m_dirty = true;
197  m_anchors.reserve( 2 );
198  m_layers = LAYER_RANGE( 0, PCB_LAYER_ID_COUNT );
199  }
200 
201  virtual ~CN_ITEM() {};
202 
203  void AddAnchor( const VECTOR2I& aPos )
204  {
205  m_anchors.emplace_back( std::make_unique<CN_ANCHOR>( aPos, this ) );
206  }
207 
209  {
210  return m_anchors;
211  }
212 
213  void SetValid( bool aValid )
214  {
215  m_valid = aValid;
216  }
217 
218  bool Valid() const
219  {
220  return m_valid;
221  }
222 
223  void SetDirty( bool aDirty )
224  {
225  m_dirty = aDirty;
226  }
227 
228  bool Dirty() const
229  {
230  return m_dirty;
231  }
232 
238  void SetLayers( const LAYER_RANGE& aLayers )
239  {
240  m_layers = aLayers;
241  }
242 
248  void SetLayer( int aLayer )
249  {
250  m_layers = LAYER_RANGE( aLayer, aLayer );
251  }
252 
258  const LAYER_RANGE& Layers() const
259  {
260  return m_layers;
261  }
262 
268  virtual int Layer() const
269  {
270  return Layers().Start();
271  }
272 
273  const BOX2I& BBox()
274  {
275  if( m_dirty && m_valid )
276  {
277  EDA_RECT box = m_parent->GetBoundingBox();
278  m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
279  }
280  return m_bbox;
281  }
282 
284  {
285  return m_parent;
286  }
287 
289  {
290  return m_connected;
291  }
292 
294  {
295  m_connected.clear();
296  }
297 
298  void SetVisited( bool aVisited )
299  {
300  m_visited = aVisited;
301  }
302 
303  bool Visited() const
304  {
305  return m_visited;
306  }
307 
308  bool CanChangeNet() const
309  {
310  return m_canChangeNet;
311  }
312 
313  void Connect( CN_ITEM* b )
314  {
315  std::lock_guard<std::mutex> lock( m_listLock );
316  m_connected.insert( b );
317  }
318 
319  void RemoveInvalidRefs();
320 
321  virtual int AnchorCount() const;
322  virtual const VECTOR2I GetAnchor( int n ) const;
323 
324  int Net() const;
325 };
326 
327 typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
328 
329 class CN_ZONE : public CN_ITEM
330 {
331 public:
332  CN_ZONE( ZONE_CONTAINER* aParent, bool aCanChangeNet, int aSubpolyIndex ) :
333  CN_ITEM( aParent, aCanChangeNet ),
334  m_subpolyIndex( aSubpolyIndex )
335  {
336  SHAPE_LINE_CHAIN outline = aParent->GetFilledPolysList().COutline( aSubpolyIndex );
337 
338  outline.SetClosed( true );
339  outline.Simplify();
340 
341  m_cachedPoly.reset( new POLY_GRID_PARTITION( outline, 16 ) );
342  }
343 
344  int SubpolyIndex() const
345  {
346  return m_subpolyIndex;
347  }
348 
349  bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
350  {
351  return ContainsPoint( anchor->Pos() );
352  }
353 
354  bool ContainsPoint( const VECTOR2I p ) const
355  {
356  auto zone = static_cast<ZONE_CONTAINER*> ( Parent() );
357  return m_cachedPoly->ContainsPoint( p, zone->GetMinThickness() );
358  }
359 
360  const BOX2I& BBox()
361  {
362  if( m_dirty )
363  m_bbox = m_cachedPoly->BBox();
364 
365  return m_bbox;
366  }
367 
368  virtual int AnchorCount() const override;
369  virtual const VECTOR2I GetAnchor( int n ) const override;
370 
371 private:
372  std::vector<VECTOR2I> m_testOutlinePoints;
373  std::unique_ptr<POLY_GRID_PARTITION> m_cachedPoly;
375 };
376 
377 class CN_LIST
378 {
379 private:
380  bool m_dirty;
382 
384 
385 protected:
386  std::vector<CN_ITEM*> m_items;
387 
388  void addItemtoTree( CN_ITEM* item )
389  {
390  m_index.Insert( item );
391  }
392 
393 public:
395  {
396  m_dirty = false;
397  m_hasInvalid = false;
398  }
399 
400  void Clear()
401  {
402  for( auto item : m_items )
403  delete item;
404 
405  m_items.clear();
406  m_index.RemoveAll();
407  }
408 
409  using ITER = decltype(m_items)::iterator;
410 
411  ITER begin() { return m_items.begin(); };
412  ITER end() { return m_items.end(); };
413 
414  CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
415 
416  template <class T>
417  void FindNearby( CN_ITEM *aItem, T aFunc )
418  {
419  m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
420  }
421 
422  void SetHasInvalid( bool aInvalid = true )
423  {
424  m_hasInvalid = aInvalid;
425  }
426 
427  void SetDirty( bool aDirty = true )
428  {
429  m_dirty = aDirty;
430  }
431 
432  bool IsDirty() const
433  {
434  return m_dirty;
435  }
436 
437  void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
438 
440  {
441  for( auto item : m_items )
442  item->SetDirty( false );
443 
444  SetDirty( false );
445  }
446 
448  {
449  for( auto item : m_items )
450  item->SetDirty( true );
451 
452  SetDirty( true );
453  }
454 
455  int Size() const
456  {
457  return m_items.size();
458  }
459 
460  CN_ITEM* Add( D_PAD* pad );
461 
462  CN_ITEM* Add( TRACK* track );
463 
464  CN_ITEM* Add( VIA* via );
465 
466  const std::vector<CN_ITEM*> Add( ZONE_CONTAINER* zone );
467 };
468 
470 {
471 private:
472 
473  bool m_conflicting = false;
474  int m_originNet = 0;
475  CN_ITEM* m_originPad = nullptr;
476  std::vector<CN_ITEM*> m_items;
477 
478 public:
479  CN_CLUSTER();
480  ~CN_CLUSTER();
481 
482  bool HasValidNet() const
483  {
484  return m_originNet >= 0;
485  }
486 
487  int OriginNet() const
488  {
489  return m_originNet;
490  }
491 
492  wxString OriginNetName() const;
493 
494  bool Contains( const CN_ITEM* aItem );
495  bool Contains( const BOARD_CONNECTED_ITEM* aItem );
496  void Dump();
497 
498  int Size() const
499  {
500  return m_items.size();
501  }
502 
503  bool HasNet() const
504  {
505  return m_originNet >= 0;
506  }
507 
508  bool IsOrphaned() const
509  {
510  return m_originPad == nullptr;
511  }
512 
513  bool IsConflicting() const
514  {
515  return m_conflicting;
516  }
517 
518  void Add( CN_ITEM* item );
519 
520  using ITER = decltype(m_items)::iterator;
521 
522  ITER begin() { return m_items.begin(); };
523  ITER end() { return m_items.end(); };
524 };
525 
526 typedef std::shared_ptr<CN_CLUSTER> CN_CLUSTER_PTR;
527 
528 
529 #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:60
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:561
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